Placing registration marks

In industrial assembly, a registration mark can be placed on parts to aid a computer vision system in determining the position and orientation (pose) of parts. However, when sensor noise and limits on resolution introduce errors in the measured location of the registration mark, these errors can propagate into the measurement of part pose. In this paper, the authors define the registration mark problem: given an n-sided rigid planar polygonal part and a set of k poses for the part, locate a point on the surface of the part that maximizes the minimum distance between transformed points. A registration mark at this point will be maximally robust to sensor imperfections. The authors give an O(n log n+k⁴ log k:log* k) time algorithm to solve this planar problem using a result from Schwartz and Sharir (see J. Symbolic Computation, vol.10, p.371-93, 1990), and demonstrate the algorithm using a commercial vision system. The results extend to classes of curved planar parts and polyhedral parts