Fast algorithm for computing the two-dimensional correlation for video processing

Authors: Altman E. A., Zaharenko E. I.

Annotation: In this paper we propose a fast algorithm for calculating the two-dimensional correlation for а signal sizes N×N and (N + M – 1)×(N + M – 1), where N = 2 i , i and M – an integer. The method is based on the principle of the correlation recursive partitioning into shorter lengths and applying at each stage the most efficient partitioning algorithm. As a result the presented research revealed the effectiveness of various methods of computing the correlation. The authors have also developed another fast algorithm for calculating the two-dimensional correlation, partitioning it to 12. This method is effective when the length of a signal is 4×4 and it is applied on one of the steps of the recursive partitioning of the proposed algorithm. The study found that the proposed algorithm for a recursive partitioning of a two-dimensional correlation is effective for short signals (less than 32×32). The application of this approach for video processing reduces the computational complexity of full search block motion estimation by half in comparison with the straightforward approach for the block size of 8×8 points and 3% compared to the fastest known method of two-dimensional correlation.

Keywords: two-dimensional correlation, motion estimation, sum of squared difference, video encoding