• Introduction
• Proposal
• Projective Geometry
• Registration
• Global Registration
  • Pairwise Registration
  • Global Registration by Least Squares
  • Examples
• Composing
• Implementation and Results
• Conclusion
• References
• Appendix

Global Registration

Pairwise Registration

The algorithms that we have shown in the previous section register pairs of images. When we have n images, we can possibly have pairs of images. We discard all pairs below a certain matching threshold µ, assuming that the corresponding images do not overlap. Then we will in general still end up with a number of pairs that is greater than n-1. So if we write the relations given by all pairs in terms of relative rotation matrices A and absolute (relative to an arbitrary origin) rotation matrices P, we have

Global Registration by Least Squares

This is an possibly overdetermined system of equations. If one just traverses linearly through the list of pairwise registrations, a large position error will have accumulated once a source image is re-visited. Davis [Davis98] proposed a scheme to optimize all pairwise registrations globally. He fits the problem into a simple least-squares solution. We extended this approach slightly by weighing each pair in the least squares cost function by the square of it's matching factor µ. The first matrix is arbitrarily assigned the identity matrix as absolute rotation matrix - we could choose any other rotation matrix to adapt the origin. The system of equations and the weighted least squares solution is then:

By using this approach, the positioning errors are equally distributed over the whole image instead of accumulating at some places. Our extension leads to a possibly even better positioning, because pairwise registrations that have a small matching factor (which means that they are either a bogus registration or correspond to an error-prone small overlap) are given less influence in the solution.

In practice, the overall registration quality result depended heavily on the choice of the matching quality threshold µ, chiefly because a too low threshold would lead to bogus registrations, and a too high value would discard valid registrations and sometimes lead to a singular matrix condition. We therefore in general chose a rather low matching threshold and iteratively discarded the registration pair that ended up having the worst square error after global registration, until the total square error was below another threshold. This simple approach was surprisingly successful in discarding bogus registrations, and minimized the necessary trial and error parameter optimization.

Examples

For the example in figure 1 the global positions have been obtained by linearly traversing the registration pairs (at a lower match factor threshold though to guarantee connectedness). In contrast to that, the positions for figure 2 were derived by global optimization.

Figure 1: Positioning by linear pairwise traverse

Figure 2: Positioning by global registration

This example clearly show the superiority of the global registration approach. Additional benefits are that as long as the A^TA matrix has full rank (which is true in most practical cases), it will yield a solution, and is therefore robust against the order of the registrations or the structure of the pairs.