Abstract
Motion estimation plays an important role in motion compensation transformation coding (MCTC) video compression systems. The temporal redundancy among adjacent frames is removed by motion estimation and motion compensation techniques. Transformation coding reduces the spatial redundancy after compensation. Block matching algorithm (BMA) is the most popular method for motion estimation. For performing BMA, the input image is partitioned into non-overlapped fixed size blocks and each block determines the motion vector in a referenced search area. In this dissertation, two issues of adopting the blocking matching techniques on motion compensation transformation coding systems are addressed. The first one is the adaptation of BMA to fit into the very low bit rate communication environment. The other is the real-time processing problem of using BMA. Most MCTC based video coding algorithms employ DCT to reduce spatial redundancy after performing motion compensation. At very low bit rate, the performance of the DCT may become poor because the reserved bit-rate for DCT is limited so it is unlikely to compress the spatial information effectively in that case. Thus, we developed a new approach that could improve the performance of the traditional MCTC methods in the very low bit rate communication environment. At first, a theoretical rate-distortion analysis of the coding efficiency for variable size block matching (VSBM) and DCT is presented. The analysis result shows that employing VSBM can achieve better performance than applying DCT at very low bit rate. We also analyze the rate-distortion performance of different combination of the child motion vectors for VSBM. Based on the analysis result, two algorithms are developed. The resulting performance has an overall improvement compared to H.263. The second issue of the dissertation is the real-time processing problem of the BMAs. The full-search block matching (FSBM) is the optimal BMA but with large amount of computation. To meet the real-time processing requirement, custom hardware devices or fast BMA should be required. We developed a unified systolic array architecture for operating FSBM, discrete wavelet transform, and full-search vector quantization. The architecture contains one-dimensional processing element array, 32 cyclic shift registers, 4 delay registers and 4 minimum distortion detectors. The FSBM with block size 16´16 and the search range (-8,7), the 2-D 2 level Harr transform with block size 8´8; and the full-search vector quantization with input vector size 2´2, can be efficiently executed in the proposed architecture. Besides, we also study the software solution of fast BMAs. A complexity-distortion-based optimal fast block matching algorithm is presented. In order to approach the complexity-distortion optimization solution as close as possible, some strategies are developed. A dominate-based motion vector prediction technique is developed to set up the initial motion vector for each block. A predictive complexity-distortion benefit list is established to predict the compensated benefit for each block. An adaptive diamond searching and integral projection condition checking is employed to check the candidate motion vector. The proposed algorithm not only improves the efficiency of the traditional BMAs, but also provides a flexible motion estimation tool that allows user to terminate motion estimation at any computational complexity.