In order to cope with the extremely large amount of raw video data for the purpose of transmission and storage, compression is needed to reduce the video effective data rate. Popular video compression standards include CCITT H.261 and MPEG, both of which use transform coding to reduce the spatial redundancy and block-based motion estimation and compensation to reduce the temporal redundancy in video sequences....[ Read more ]

In order to cope with the extremely large amount of raw video data for the purpose of transmission and storage, compression is needed to reduce the video effective data rate. Popular video compression standards include CCITT H.261 and MPEG, both of which use transform coding to reduce the spatial redundancy and block-based motion estimation and compensation to reduce the temporal redundancy in video sequences.

In block-based motion estimation, each image frame is divided into blocks. The motion of the search blocks in a video sequence are found by performing a motion estimation procedure. The conventional approach performs an exhaustive motion search to find the best match using the mean absolute difference (MAD) as a measure of block distance. This approach is optimal in MAD sense but also requires prohibitively large amount of computation.

In this thesis, fast block matching algorithms in the features domain are proposed for motion estimation. The features concerned are called integral projections. Integral projections have special properties which can be utilized for fast implementation. Improved algorithms were devised by making use of alternating features. The performance of the proposed algorithms can be improved by introducing search area subsampling and motion field subsampling. With a search block size of NxN, the amount of computation reduction for motion estimation using the proposed algorithms is, at least, N/2. Extensive simulation, according to MPEG-1 recommendation, shows that the proposed fast block matching algorithms in the feature domain can achieve close-to-optimal performance with significant computation reductions. Owing to the special properties and the regularity of the integral projections, the fast block matching algorithms in the feature domain are highly suitable for VLSI implementation using parallel and pipeline architectures.