System and method for cross correlation with application to video motion

Abstract

Method and apparatus for computing cross-correlations with application to image processing and video motion estimation, particularly in video compression applications, are described. Two-dimensional Fourier transform convolution techniques form a basis for novel techniques for performing two simultaneous two-dimensional cross correlations. The size of the input data blocks for the transformations are arbitrary. Apparatus for efficiently performing real-time cross correlations, including cross-correlations using Short Length Transforms (SLTs), using cascaded stages, multi-port memories, and multiple arithmetic units are also described. In video motion vector estimator application, data blocks within a current video frame are selected and converted to form a two-dimensional matrix of complex data. The complex matrix is transformed to the frequency domain to form the frequency domain representations of the selected data blocks. A set of search blocks within the previous video frame having a one-to-one correspondence with the selected data blocks, is then selected, converted into a complex data matrix, and transformed to the frequency domain to form the frequency domain representations of the selected search blocks. Once in the frequency domain, the sets of data corresponding to the data blocks and the search blocks are multiplied together and the product is inverse transformed to return to the spatial domain. The data then passes through an adjustment process to form the cross-correlations between the pairs of data blocks and search blocks.