Shape from Diameter
Authors:
- 1 February 1994
- journal article
- research article
- Published by SAGE Publications in The International Journal of Robotics Research
- Vol. 13 (1) , 16-37
Abstract
Our objective is to automatically recognize parts in a struc tured environment (such as a factory) using inexpensive and widely available hardware. In this article we consider the pla nar problem of determining the convex shape of a polygonal part from a sequence of projections. Projecting the part onto an axis in the plane of the part produces a scalar measure, the diameter, which is a function of the angle of projection. The diameter of a part at a particular angle can be measured using an instrumented parallel-jaw gripper. First, we present the negative result that shape cannot be uniquely recovered: for a given set of diameter measurements, there is an (uncountably) infinite set of polygonal shapes con sistent with these measurements. Because most of these shapes have parallel edges of varying lengths, we consider the related problem of identifying a representative polygon with no par allel edges. We show that, given a diameter function, deciding whether such a polygon exists is NP-complete. These results motivate us to consider the problem of recog nizing a part from a known (finite) set of parts. Given a set of polygonal parts with a total of N faces, can we find the short est sensing plan for disambiguating the parts? Only diameters at n ≤ N stable faces can be measured. We construct an in ternal representation of these stable diameters in O(N + n 3) time and then give two planning algorithms: one constructs an optimal sensing plan in time O( n42 n), the other constructs a suboptimal sensing plan in time O( n2 log n). Neither plan requires more than n measurements.Keywords
This publication has 15 references indexed in Scilit:
- Probing a scene of nonconvex polyhedraAlgorithmica, 1992
- Applications of random sampling to on-line algorithms in computational geometryDiscrete & Computational Geometry, 1992
- Applications of random sampling in computational geometry, IIDiscrete & Computational Geometry, 1989
- An algorithm for reconstructing convex bodies from their projectionsDiscrete & Computational Geometry, 1989
- Automatic Grasp Planning in the Presence of UncertaintyThe International Journal of Robotics Research, 1988
- Active perceptionProceedings of the IEEE, 1988
- Localizing Overlapping Parts by Searching the Interpretation TreeIEEE Transactions on Pattern Analysis and Machine Intelligence, 1987
- Shape from probingJournal of Algorithms, 1987
- Probing convex polytopes1986
- Tactile Recognition and Localization Using Object Models: The Case of Polyhedra on a PlaneIEEE Transactions on Pattern Analysis and Machine Intelligence, 1984