Motion estimation plays an important role in modern video coders. In such coders, motion is estimated using a block matching algorithm that estimates the amount of motion on a block-by-block basis. A full search technique for finding the best matching blocks delivers good accuracy but is usually not practical because of its high computational complexity. Many other algorithms are presented for achieving a high temporal or computational efficiency, however, their accuracy is suboptimal and in some cases it could be unacceptable.

In this dissertation, a novel fast block-based motion estimation algorithm in the Walsh-Hadamard transform domain is proposed. This algorithm uses an efficient computation framework for computing WHT coefficients whose difference approximate the actual di...[ Read more ]

Motion estimation plays an important role in modern video coders. In such coders, motion is estimated using a block matching algorithm that estimates the amount of motion on a block-by-block basis. A full search technique for finding the best matching blocks delivers good accuracy but is usually not practical because of its high computational complexity. Many other algorithms are presented for achieving a high temporal or computational efficiency, however, their accuracy is suboptimal and in some cases it could be unacceptable.

In this dissertation, a novel fast block-based motion estimation algorithm in the Walsh-Hadamard transform domain is proposed. This algorithm uses an efficient computation framework for computing WHT coefficients whose difference approximate the actual distance between a pattern block and its candidate blocks. Fast WHT coefficient computation is performed with a set of highly efficient WHT basis kernels which share a special inter-relationship with their neighboring WHT basis kernels by using only 2 operations per WHT basis kernel, regardless of the size of the basis kernel.

The fast computation framework is combined with a pre-stop searching scheme called zero motion vector prejudgment, which allows rapid recognition of static image blocks. A motion vector prediction strategy is also used to predict the initial searching center in proposed algorithm in order to prevent from involving into the local optimum point and reduce searching times. Adaptive searching-templates choosing is also adapted according to the type of current block.

Experiments show that the proposed algorithm significantly outperforms popular fast motion estimation algorithms, such as three-step search, diamond search and adaptive rood pattern search.