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 computational 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 (rho) is a more robust measure but has high computational cost because no ETAs for rho 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, rho is computed as a monotonically decreasing measure. At a specific search location, when the partial value of rho falls below the yet known maxima, remaining calculations are discarded. In bound based ETA, a new upper-bound on rho 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 implementation and up to 4.6 times faster than the current best known spatial domain technique.