Abstract
In this thesis, we propose two efficient image matching algorithms based on the normalized cross correlation (NCC) criterion for pattern matching and motion estimation, respectively. Moreover, a novel hybrid motion estimation algorithm that adaptively combines the SAD (Sum of Absolute Differences) and NCC measures is presented for video compression. First, we propose an efficient NCC-based image matching algorithm by applying the winner-update strategy on the Walsh-Hadamard transform, which is an orthogonal transformation that is easy to compute and has great energy packing capability. This efficient algorithm is based on deriving the upper bound for the cross correlation between the corresponding Hadamard coefficients in a hierarchical order. In addition, a multi-level fast NCC-based image matching algorithm and a new hybrid approach for block based motion estimation based on adaptively using the NCC and SAD measures are proposed. We use the SAD value and gradient sum as the criterion to determine which similarity measure to be used for motion estimation for a macroblock. In general, using the NCC as the similarity measure in the motion estimation leads to more uniform residuals than those of using the SAD, thus leading to more efficient video compression.