Geometric matching algorithm for beam scanning

In this paper, we present an object recognition technique using scanline information. Objects are scanned using a small number of on/off light sensors. The times when the beams break and unbreak constrain the object's identity, position, and orientation. We study this type of sensor because they are inexpensive, compact, very precise, and insensitive to ambient light, and so well-adapted to manufacturing environments. The information provided by the sensor is very sparse however, consisting of isolated points on the object boundary without normal information. Conventional model-based matching techniques, such as the alignment method, take O(n<SUP>3</SUP>) time for this problem. We describe an O(A + n) correspondence algorithm for objects with convex polygonal silhouettes, where n is the silhouette's complexity, and A is the total number of consistent edge pair matches for pairs of scanline points, which is O(n<SUP>2</SUP>) in the worst case, but typically O(n). Our algorithm works also for non-convex objects, but the quantity A has a somewhat larger typical value, and a worst case value of O(n<SUP>3</SUP>). The object's position and orientation can be easily computed given the correspondence information.