Motion estimation and analysis is a fundamental part of many video and image processing applications. In particular, in video coding motion information can be used for exploiting temporal correlation and for reducing the redundancy that exists between frames of video sequences. This can have a significant impact on the bit-rate and output quality of the encoded sequence. Unfortunately this approach, when using the brute force Full Search (FS) algorithm, occupies a very large portion of the encoding time, which is highly undesirable for certain applications and systems. Numerous fast techniques have been presented in the literature, which are either application dependent, for example low or high bit-rate video, or do not give a satisfactory solution since, they usually achieve reduction...[ Read more ]

Motion estimation and analysis is a fundamental part of many video and image processing applications. In particular, in video coding motion information can be used for exploiting temporal correlation and for reducing the redundancy that exists between frames of video sequences. This can have a significant impact on the bit-rate and output quality of the encoded sequence. Unfortunately this approach, when using the brute force Full Search (FS) algorithm, occupies a very large portion of the encoding time, which is highly undesirable for certain applications and systems. Numerous fast techniques have been presented in the literature, which are either application dependent, for example low or high bit-rate video, or do not give a satisfactory solution since, they usually achieve reduction in complexity at the cost of reduced quality.

The research presented in this thesis is mainly concerned with the development of such application independent algorithms for video compression, which are also highly robust and efficient. We essentially tackle the problem of motion estimation as an optimization problem, where different properties and correlation inside a video sequence are considered in order to improve efficacy while at the same time considerably reducing complexity. Our algorithms, named as the Zonal Based algorithms, have been widely acknowledged for their superior performance versus most, if not all, other motion estimation algorithms by the research community and multimedia standards. Further properties and applications of these algorithms are also analyzed. In particular, we investigate their usefulness and performance for the purpose of deinterlacing.

A general model of the zonal algorithms, named as the N-Dimensional Zonal Algorithms, is also presented which not only can be applied in video coding systems, but could also be useful in other video/image processing applications.