Faster image template matching in the sum of the absolute value of differences measure

Given an m x m image I and a smaller m x n image P, the computation of an (m - n + 1) X (m - n + 1) matrix C where C(i, j) is of the form C(i, j) = Sigma (n-1)(k=0) Sigma (n-1)(k ' =0) f(I(i + k, j + k '), P(k, k ')), 0 less than or equal toi, j less than or equal to m - n for some function f, is often used in template matching. Frequent choices for the function f are f(x, y) = (x - y)(2) and f(x, y) = \x - y\. For the case when f(x, y) = (x - y)(2), it is well known that C is computable in O(m(2) log n) time. For the case f(a:, y) = la: - yl, on the other hand, the brute force O((m - n + 1)(2)n(2)) time algorithm for computing C seems to be the best known. This paper gives an asymptotically Easter algorithm for computing C when f(x, y) = \x - y\, one that runs in time O(min{s, n/root logn}m(2) log n) time, where s is the size of the alphabet, i.e., the number of distinct symbols that appear in I and P. This is achieved by combining two algorithms, one of which runs in O(sm(2) log n) time, the other in O(m(2)n root log n) time. We also give a simple Monte Carlo algorithm that runs in O(m(2) log n) time and gives unbiased estimates of C.