Exploiting Data- and Thread-Level Parallelism for Image Correlation

The correlation between two signals (cross correlation) is a standard approach to feature detection. The normalized form of cross correlation (normalized correlation coefficient) is particularly used for template matching. In this case, the two-dimensional correlation of images is considered. One of its biggest drawbacks is the need for a lot of computational power, especially when many correlation coefficients are computed. This paper presents a new method for a high performance thread- and data-parallel computation of normalized cross correlation in the spatial domain. It will be shown that a speedup of up to 5 can be achieved solely by a sophisticated programming of the SIMD unit of a standard microprocessor. Furthermore, the new data- parallel implementation in the spatial domain can even outperform an (also data-parallel) frequency domain implementation.