Fast image registration based on geometric correspondence between two levels of pyramid structure

The use of a pyramid structure has been known to reduce the time required for image registration. Discussions on a required search range without backtracking, however, have been mostly experimental. In Tanimoto's example the range of 2 × 2 was insufficient, and he suggested the use of a 4 × 4 range, namely, the choice of the best of 16. However, his discussion was not complete. This paper presents a theory based on geometric rather than analog correspondence between levels. First, the upper left corner candidate and best estimate positions in template images of each level, respectively, are defined. Then a required search range is considered. It is shown that even a range of 4 × 4 is insufficient. The discussion is extended to cover the case of analog correspondence. Results obtained are applied to the registration of dynamic images using SSDA (Sequential Similarity Detection Algorithm). A substantial reduction of time is achieved by the use of a pyramid structure in comparison with a conventional method, which uses only the lowest level.