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

| September 9, 2007 | 0 Comments

Arif Mahmood, Sohaib Khan
14th IEEE International Conference on Image Processing, ICIP 2007


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.


Download PDF
(Distributed here for timely dissemination of scholarly work. Copyright retained by copyright holders. May not be posted without permission from copyright holders.)

Text Reference:

Arif Mahmood, Sohaib Khan,
"Early Termination Algorithms for Correlation Coefficient Based Block Matching", 
in Proceedings of 14th IEEE International Conference on Image Processing,
ICIP 2007, San Antonio, Texas, pp II-469 - II-472, September 16-19, 2007

Bibtex Reference:

  title={Early termination algorithms for correlation coefficient based block matching},
  author={Mahmood, A. and Khan, S.},
  booktitle={Image Processing, 2007. ICIP 2007. IEEE International Conference on},

Tags: , , , , ,

Category: Conference Papers, Publications

Leave a Reply

Your email address will not be published. Required fields are marked *