Locating Polyhedral Objects from Edge Point Data

Gary Silverman, Roger Y. Tsai, Mark Lavin

Abstract

Determining the 6-DOF pose of polyhedral objects from sparse 3D data is a critical task in computer vision and robotics. This paper introduces a highly efficient localization method designed for sparse data points captured by light stripe sensors. The approach leverages "edge intervals"—geometric segments on object edges constrained by a fixed distance—and utilizes a pruned tree search followed by a 1D line search. Experimental results on 1980s-era hardware demonstrate real-time performance and significant computational reduction through effective search space pruning.

Introduction

In robotic perception, localization involves determining the precise position and orientation of an object in 3D space. While modern LiDAR provides dense point clouds, early sensors often yielded sparse data, specifically at the intersections of light stripes and object edges. The challenge lies in mapping these sparse points to the correct model edges and calculating the object's pose without the computational overhead of dense data processing. Previous techniques often relied on specific features like orthogonal corners or were too slow for real-time applications. This work proposes a general solution for any polyhedron that remains robust under sensor noise and operates efficiently.

Methodology

The proposed localization algorithm consists of three primary stages: edge interval definition, tree-based constraint propagation, and a final one-dimensional search.

Edge Intervals and Monotonicity

The core insight of the paper is the definition of "edge intervals." For any two edges in 3D space, if a line segment of fixed length $d$ (representing the distance between two sensor points) connects them, the movement of one endpoint along its edge corresponds monotonically to the movement of the other endpoint along its respective edge. This geometric property allows the definition of valid segments, or intervals, where the points must reside.

Geometric representation of monotonic edge intervals between two 3D lines.

The Edge Interval Tree

To localize an object using three points on three edges, the algorithm constructs a search tree. Each level of the tree corresponds to an edge. Constraints are propagated sequentially: from the first edge to the second, the second to the third, and finally closing the loop back to the first. The monotonic nature of the intervals allows for aggressive pruning. If an interval on one edge does not map to a valid interval on the subsequent edge, that entire branch of the search space is discarded.

Mapping of intervals between edges, illustrating the different cases used for pruning the search tree.

After the tree search narrows the possibilities to a small set of candidate intervals, the problem is reduced from a complex 6-DOF search to a simple 1D search. The algorithm iterates through a single parameter—the position on the first edge—to find the configuration that satisfies the closure of the triangle formed by the three sensor points.

Experimental Results

The method was evaluated using a simulated unit tetrahedron to generate synthetic edge point data. The implementation was tested on an IBM RT PC, a RISC-based workstation from the mid-1980s, using the C programming language.

Key findings include:

  • Search Efficiency: In the tetrahedron test case, the theoretical maximum of 84 nodes in the search tree was reduced to just 15 nodes due to effective pruning.
  • Computational Speed: The entire localization process, including tree search and 1D optimization, was completed in only a few seconds.
  • Robustness: The framework includes mathematical handling for degenerate cases, such as parallel or orthogonal edges, ensuring stability across various geometric configurations.

Conclusion

This paper presents a computationally "cheap" yet powerful method for polyhedral localization. By reducing a high-dimensional spatial search to a series of interval-matching problems and a final 1D search, it achieved real-time performance on limited hardware. However, the method currently assumes that the correspondence between data points and model edges is known. Future work could integrate this approach with automated interpretation methods to handle unknown correspondences in complex environments like robotic bin-picking.

Summary updated

BibTeX
@inproceedings{silverman1987locating,
  author = {Gary Silverman and Roger Y. Tsai and Mark Lavin},
  title = {{Locating Polyhedral Objects from Edge Point Data}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1987},
}
Figure