Horn's method determines a translation, rotation, and scaling that will align points in one coordinate system to corresponding points in another coordinate system, while minimizing the total distance between the sets of points. The two sets of points may be collected as follows. First, the mouse is used to select a point on the mesh. Then, the stylus is used to point to the corresponding point on the object, thus specifying a correspondence pair. Horn's method requires three or more of these correspondence pairs to determine the registration transformation.
There are several sources of error in collecting the two sets of points including inaccuracies in the tracking system, and inaccuracies in matching the points on the mesh to points on the object. However, as the number of correspondence pairs is increased, small alignment errors in individual pairs are averaged out and the total alignment error decreases. Unfortunately, specifying correspondence pairs is tedious and time consuming.
An algorithm developed by Besl [1] overcomes this problem. Although two sets of points are still required, it is not necessary to specify the point-to-point correspondences between them. We collect a large set of points in tracker space by sampling the position of the stylus while randomly moving it across the surface of the physical object. We use a subset of the mesh vertices as the other set of points. Besl's algorithm determines the best transformation between the two sets of points by iterating on the following steps. First an approximate correspondence between the two sets of points is computed, based on their proximity in space. Then, Horn's method is applied to these pairs of points to align them more closely. On each successive iteration of the algorithm, the proximity-based correspondence improves, which in turn improves the transformation generated by Horn's method.
Besl's algorithm is guaranteed only to find a locally optimal alignment, not a globally optimal one. Therefore, we need to ensure that the sensor samples and the mesh are initially aligned such that the globally optimal solution can be found. The initial alignment is done by hand (see figure 2) and is often a difficult and time consuming process. To speed this process, we have added the ability to easily generate a rough alignment of the sensor samples to the mesh. Once we have collected the large set of sensor samples, we ask the user to specify three or more correspondence pairs as described at the beginning of this section. From these pairs we calculate the scale factor between the sensor samples and the mesh. We also translate the centroid of the sensor correspondence points so that it is aligned with the centroid of the mesh. This produces a rough alignment of the sensor samples to the mesh which can then be hand-refined to produce the initial alignment required for Besl's algorithm.
Our registration scheme is summarized as follows: