Abstract
Pattern matching has been widely used in many applications related to computer vision and image processing, such as stereo matching, object tracking, object detection, pattern recognition and video compression, etc. The most popular similarity measures are the sum of absolute differences (SAD), the sum of squared differences (SSD) and the normalized cross correlation (NCC). The SSD measure is very popular similarity measure for object tracking and object detection by calculating the Euclidean distance between the pattern and the candidate in the search image to find the one with the minimum distance. The traditional full search method is very time-consuming. For practical applications, an efficient pattern matching algorithm is strongly demanded especially for motion-compensated video compression. Although using NCC as the similarity measure can find the pattern under uniform lighting variation, but it cannot work well under uneven lighting condition. For the practical applications of image alignment for industrial inspection and face recognition, the problem becomes to finding a given pattern in the search image under uneven lighting conditions. In this dissertation, we propose three types of new pattern matching algorithms. The first one contains several fast template matching techniques based on minimizing SAD or SSD measure for block-based motion estimation in video compression. Secondly, we propose efficient normalized cross correlation algorithms for robust pattern matching under uniform illumination variations.. In addition to the above two categories, we also develop a robust and efficient image matching algorithm that can be applied to the image alignment for industrial inspection and the face recognition under lighting variations.