Computation Elimination Algorithms For Correlation Based Fast Template Matching
Arif Mahmood · 2011
Template matching is frequently used in Digital Image Processing, Machine Vision, Remote Sensing and Pattern Recognition, and a large number of template matching algorithms have been proposed in literature.The performance of these algorithms may be evaluated from the perspective of accuracy as well as computational complexity.Algorithm designers face a tradeo between these two desirable characteristics; often, fast algorithms lack robustness and robust algorithms are computationally expensive. The basic problem we have addressed in this thesis is to develop fast as well as robust template matching algorithms.From the accuracy perspective, we choose correlation coecient to be the match measure because it is robust to linear intensity variations often encountered in practical problems.To ensure computational eciency, we choose bound based computation elimination approaches because they allow high speed up without compromising accuracy.Most existing elimination algorithms are based on simple match metrics such as Sum of Squared Di erences and Sum of Absolute Dierences.For correlation coecient, which is a more robust match measure, very limited eorts have been done to develop ecient elimination schemes.The main contribution of this thesis is the development of two di erent categories of bound based computation elimination algorithms for correlation coecient based fast template matching.We have named the algorithms in the rst category as Transitive Elimination Algorithms (Mahmood and Khan, 2007b, 2008, 2010), because these are based on transitive bounds on correlation coecient. In these algorithms, before computing correlation coecient, we compute bounds from neighboring search locations based on transitivity. The locations where upper bounds are less than the current known maximum are skipped from computations, as they can never become the best match location. As the percentage of skipped search locations increases, the template matching process becomes faster. Empirically, we have demonstrated speedups of up to an order of magnitude compared to existing fast algorithms without compromising accuracy. The overall speedup depends on the tightness of transitive bounds, which in turn is dependent on the strength of autocorrelation between nearby locations. Although high autocorrelation, required for eciency of transitive algorithms, is present in many template matching applications, it may not be guaranteed in general. We have developed a second category of bound based computation elimination algorithms, which are more generic and do not require speci c image statistics, such as high autocorrelation.We have named this category as Partial Correlation Elimination algorithms (Mahmood and Khan, 2007a, 2011).These algorithms are based on a monotonic formulation of correlation coecient.In this formulation, at a particular search location, correlation coecient monotonically decreases as consecutive pixels are processed.As soon as the value of partial correlation becomes less than the current known maximum, the remaining computations are skipped.If a high magnitude maximum is found at the start of the search process, the amount of skipped computations signi cantly increases, resulting in high speed up of the template matching process.In order to locate a high maximum at the start of search process, we have developed novel initialization schemes which are e ective for small and medium sized templates.For commonly used template sizes, we have demonstrated that PCE algorithms out-perform existing algorithms by a signi cant margin.