Fast template matching based on the normalized correlation by using multiresolution eigenimages

Abstract

Presents a fast computation method of the normalized correlation for multiple rotated templates by using multiresolution eigenimages. This method allows the authors to accurately detect both location and orientation of the object in a scene at faster rate than applying conventional template matching to the rotated object. Since the correlation among slightly rotated templates is high, the authors first apply the Karhunen-Loeve expansion to a set of rotated templates and extract "eigenimages" from them. Each template in this set can be approximated by a linear combination of these eigenimages and it substitute for the template in computing the normalized correlation. The number of eigenimages is smaller than that of original templates and computation cost becomes small. Second, the authors employ a multiresolution image structure to reduce the number of rotated templates and location search area. For the lower resolution image, the position and angle are coarsely obtained in a wide region. Then not only searching area for the position but also the range of rotation angle of templates at the next layer can be limited to the neighbor of the prior results. The authors implemented the proposed algorithm on a vision system and realized computation time around 600 msec and achieved sub pixel resolution for translation and 0.3 degree maximum error for 360 degree rotation on the 512 by 480 gray scale image. Experimental results are shown to demonstrate the accuracy, efficiency and feasibility of the proposed method.