ICIP 2007 – Early Termination Algorithms for Correlation Coefficient Based Block Matching

Block based motion compensation techniques make frequent use of Early Termination Algorithms (ETA) to reduce the com- putational cost of block matching process. ETAs have been well studied in the context of Sum of Absolute Differences (SAD) match measure and are effective in eliminating a large percentage of computations. As compared to SAD, the correlation coefficient (ρ) is a more robust measure but has high computational cost because no ETAs for ρ have been reported in literature.

In this paper, we propose two types of ETAs for correlation coefficient: growth based and the bound based. In growth based ETA, ρ is computed as a monotonically decreas- ing measure. At a specific search location, when the partial value of ρ falls below the yet known maxima, remaining cal- culations are discarded. In bound based ETA, a new upper- bound on ρ is derived which is tighter than the currently used Cauchy-Schwartz inequality. The search locations where the proposed bound falls shorter than the yet known maxima are eliminated from the search space. Both types of algorithms are implemented in a cascade and tested on a commercial video dataset. In our experiments, up to 88% computations are found to be eliminated. In terms of execution time, our algorithm is up to 13.7 times faster than the FFTW based im- plementation and up to 4.6 times faster than the current best known spatial domain technique.