Shape from Diameter

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 ³) time and then give two planning algorithms: one constructs an optimal sensing plan in time O(n ⁴2 ⁿ ), the other constructs a suboptimal sensing plan in time O(n ² log n). Neither plan requires more than n measurements.