Computation Elimination Algorithms for Correlation Based Fast Template Matching

Abstract

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 complex- ity. Algorithm designers face a tradeoff between these two desirable characteristics; often, fast algorithms lack robustness and robust algorithms are computationally ex- pensive. 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 coefficient to be the match measure because it is robust to linear intensity varia- tions often encountered in practical problems. To ensure computational efficiency, 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 Differences and Sum of Ab- solute Differences. For correlation coefficient, which is a more robust match measure, very limited efforts have been done to develop efficient elimination schemes. The main contribution of this thesis is the development of two different categories of bound based computation elimination algorithms for correlation coefficient based fast template matching. We have named the algorithms in the first category as Transitive Elimination Algorithms (Mahmood and Khan, 2007b, 2008, 2010), because these are based on transitive bounds on correlation coefficient. In these algorithms, before computing correlation coefficient, 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 efficiency of transitive algorithms, is present in many template matching applications, it may not be guaranteed in gen- eral. We have developed a second category of bound based computation elimination algorithms, which are more generic and do not require specific image statistics, such as high autocorrelation. We have named this category as Partial Correlation Elimina- tion algorithms (Mahmood and Khan, 2007a, 2011). These algorithms are based on a monotonic formulation of correlation coefficient. In this formulation, at a particular search location, correlation coefficient monotonically decreases as consecutive pixels are processed. As soon as the value of partial correlation becomes less than the cur- rent 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 compu- tations significantly 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 effective for small and medium sized templates. For commonly used template sizes, we have demonstrated that PCE al- gorithms out-perform existing algorithms by a significant margin. Beyond the main contribution of developing elimination algorithms for correlation, two extensions of the basic theme of this thesis have also been explored. The first direction is to extend elimination schemes for object detection. To this end, we have shown that the detection phase of an AdaBoost based edge corner detector (Mahmood, 2007; Mahmood and Khan, 2009) can be significantly speeded up by adapting elimination strategies to this problem. In the second direction we prove that in video encoders, if motion estimation is done by maximization of correlation coefficient and motion compensation is done by first order linear estimation, the vari- ance of the residue signal will always be less than the existing motion compensation schemes (Mahmood et al., 2007). This result may potentially be used to increase compression of video signal as compared to the current techniques. The fast corre- lation strategies, proposed in this thesis, may be coupled with this result to develop correlation-based video encoders, having low computational cost.