4 Establishing correspondences

The two images to be registered are now represented compactly as a hierarchy of linked lists, with the following structure:

image

= list of
columns


row

= list of
words



column

= list of
rows


word

=
length

(in pixels)

Finding a seed match

Each row in image 1 is compared with each row in image 2. Two rows are compared by comparing every word in row 1 with every word in row 2. If the length of the two words and their immediate neighbours agree to within a predefined tolerance (5 pixels was used throughout this work), then they are deemed to match. If there are three or more word matches between two rows, then the rows are deemed to match. The search terminates successfully when two pairs of consecutive rows match. For images with a 50% overlap, there are many potential row matches and a correct seed match is almost always found, even when some of the rows are incorrectly segmented into words.

Building the match list

Given a seed match, a large number of correspondences can be generated by searching matching pairs of rows away from the seed row. As before, every word in row 1 is compared with every word in row 2, and they are deemed to match if the length of the two words and their immediate neighbours agree to within a predefined tolerance. Note that the entire matching process, from finding the seed match to building the complete match list, is conservative . While segmentation errors may cause the algorithm to miss some correct matches, it is extremely unlikely to find any incorrect matches. Given that the two images overlap by about 50%, there are many more potential word matches than are required to mosaic the images. The final match list typically contains more than enough good matches.