PhD Dissertation Defense: Arif Mahmood

Arif Mahmood successfully defended his Ph.D. thesis on May 27, 2011 at LUMS, Lahore.

Thesis 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 complexity. Algorithm designers face a tradeoff 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 coefficient to be the match measure because it is robust to linear intensity variation s often encountered in practical problems. To ensure computational efficiency, we choose bound based computation elimination approaches because they allow high speedup without compromising accuracy. Most existing elimination algorithms are based on simple match metrics such as Sum of Squared Differences and Sum of Absolute Differences. For correlation coefficient, which is a more robust match measure, very limited efforts have been done to develop efficient elimination schemes.

The core 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, 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 near by locations.

Although high autocorrelation, required for efficiency 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 specific image statistics, such as high autocorrelation. We have named this category as Partial Correlation Elimination algorithms. 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 current known maximum, the remaining computations are skipped. If a high maximum is found at the start of the search process, the amount of skipped computations significantly increases, resulting in high speedup 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 algorithms 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 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 variance of the residue signal will always be less than the existing motion compensation schemes. This result may potentially be used to increase compression of video signal as compared to the current techniques. The fast correlation strategies, proposed in this thesis, may be coupled with this result to develop correlation-based video encoders, having low computational cost.

Defense Announcement