Frequency-domain motion estimation using a complex lapped transform

Estimating the motion in image sequences is important in many areas of image processing, for example, in video coding. This paper develops a frequency-domain algorithm for motion estimation based on overlapped transforms of the image data. It is particularly intended as an alternative to block matching methods. We first define the complex lapped transform (CLT) by extending the lapped orthogonal transform (LOT) to have complex basis functions. The CLT basis functions decay smoothly to zero at their end points, and overlap by 2:1 when a data sequence is transformed. The CLT may also be viewed as a modified short time Fourier transform. We derive a method for estimating cross-correlation functions in the CLT domain. This forms the basis of a motion estimation algorithm that calculates vectors for overlapping, windowed regions of data, rather than the nonoverlapping blocks used with conventional block matching schemes. The overlapping data window used in the proposed method has no block edge discontinuities and results in smoother motion fields. Furthermore, when motion compensation is performed using similar overlapping regions, the algorithm gives comparable or smaller prediction errors than standard methods using exhaustive search block matching. Computational load is lower than exhaustive search block matching for larger displacement ranges and block sizes.