Advanced motion estimation algorithms in the frequency domain for digital video applications.

Motion estimation is a technique that is used frequently within the fields of image and video processing. Motion estimation describes the process of determining the motion between two or more frames in an image sequence. There are several different approaches to estimating the motion present within a scene. In general, the most well known motion estimation algorithms can be separated into fixed or variable block size, object based and dense motion estimation methods. Motion estimation has a variety of important applications, such as video coding, frame rate conversion, de-interlacing, object tracking and spatio-temporal segmentation. Furthermore there are medical, military and security applications. The proper motion measurement method is selected, based on the application and the available computational power. Several such motion estimation techniques are described in detail, all of which operating in the frequency domain based on phase correlation. The main objective and prepuce of this study is to improve the state-of-the-art motion estimation techniques that operate in the frequency domain, based on phase correlation and to introduce novel methods providing more accurate and reliable estimates. Furthermore, research is carried out to investigate and suggest algorithms for all motion estimation categories, based on the density of the optical flow, starting from block-based and moving to dense vector fields. Highly accurate and computationally efficient block-based techniques, utilising either gradient information or hypercomplex correlation, are suggested being suitable for estimation of motion in video sequences improving the baseline phase correlation method. Furthermore, a novel sub-pixel motion estimation technique using phase correlation, resulting in high-accuracy motion estimates, is presented in detail. A quad-tree scheme for obtaining variable size block-based sub-pixel estimates of interframe motion in the frequency domain is proposed, using either key features of the phase correlation surface or the motion compensated prediction error to manage the partition of parent block to four children quadrants. Sub-pixel estimates for arbitrarily shaped regions are obtained in a proposed frequency domain scheme without extrapolation to be required, based on phase correlation and the shape adaptive discrete Fourier transform. In the last part of this study, two fast dense motion estimation methods operating in the frequency domain are presented based either on texture segmentation or multi overlapped correlation, utilising either weighted averages or the novel gradient normalised convolution to restore missing motion vectors of the resulting dense vector field, requiring significant lower computational power compared to spatial and robust algorithms. Based on the performance study of the proposed frequency domain motion estimation techniques, performance advantages over the baseline phase correlation are achieved in terms of the motion compensated prediction error and zero-order entropy indicating higher level of compressibility and improved motion vector coherence. One of the most attractive features of the proposed schemes is that they enjoy a high degree of computational efficiency and can be implemented by fast transformation algorithms in the frequency domain. Concluding, it should be mentioned that according to the results of each of the proposed schemes, their complexity and performance are making them attractive for low computational power and real time applications. Furthermore, they provide comparable estimates to spatial domain techniques and estimates closer to the real motion present in the scene making them suitable for object tracking and 3-D scene reconstruction