In the past, most design and optimization work on hybrid video codecs relied mainly on experimental evidence. A proper theoretical model is always desirable, since this allows us to explain the phenomena of existing codecs and to design better ones. In this paper, we make use of the first-order Markov model to derive an approximated separable autocorrelation model for the block-based motion compensation frame difference (MCFD) signal. A major assumption of our derivation is that the net deformation of pixels is directional, in general, rather than a uniform error distribution in a block. We have also shown that the imperfect block-based motion compensation is significant to the theoretical study and the behavior of motion-compensated codecs. Results of our experimental work show that the derived model can describe the statistical characteristics of the MCFD signals accurately. The model also shows that the imperfectly formulated block-based motion compensation can result in an incorrect MCFD autocorrelation function while, conversely, it can form a better block-based motion compensation scheme.

The discrete cosine transform (DCT) is widely used in modern video compression standards, such as the ITU-T H.263 and the ISO MPEG-4, to achieve high compression efficiency. A major merit of the DCT is its capability in high energy compaction for natural images. However, the motion prediction error frame is not a natural image but synthetically generated by the process of motion compensation. This process degrades the energy compaction efficiency of the DCT. We study the spatial distribution of the prediction errors resulting from either the full-search motion estimation or other fast search algorithms in order to improve the coding efficiency of the DCT. Subsequently, a mixed spatial-DCT-based coding scheme is proposed for coding the prediction errors. Our experimental results show that this coding scheme can successfully improve the compression performance of the traditional DCT-based video coder with block based motion compensation for arbitrary shaped video objects and, video sequences which contain moderate to high motion activities.

In order to reduce the computation load, many conventional fast block-matching algorithms have been developed to reduce the set of possible searching points in the search window. All of these algorithms produce some quality degradation of a predicted image. Alternatively, another kind of fast block-matching algorithms which do not introduce any prediction error as compared with the full-search algorithm is to reduce the number of necessary matching evaluations for every searching point in the search window. The partial distortion search (PDS) is a well-known technique of the second kind of algorithms. In the literature, many researches tried to improve both lossy and lossless block-matching algorithms by making use of an assumption that pixels with larger gradient magnitudes have larger matching errors on average. Based on a simple analysis, it is found that, on average, pixel matching errors with similar magnitudes tend to appear in clusters for natural video sequences. By using this clustering characteristic, we propose an adaptive PDS algorithm which significantly improves the computation efficiency of the original PDS. This approach is much better than other algorithms which make use of the pixel gradients. Furthermore, the proposed algorithm is most suitable for motion estimation of both opaque and boundary macroblocks of an arbitrary-shaped object in MPEG-4 coding.

The conventional search algorithms for block motion estimation reduce the set of possible displacements for locating the motion vector. All of these algorithms produce some quality degradation of the predicted image. To reduce the computational complexity of the full search algorithm without introducing any loss in the predicted image, we propose an adaptive partial distortion search algorithm (APDS) by selecting the most representative pixels with high activities, such as edges and texture which contribute most to the matching criterion. The APDS algorithm groups the representative pixels based on the pixel activities in the Hilbert scan. By using the grouped information and computing the accumulated partial distortion of the representative pixels before that of the other pixels, impossible candidates can be rejected sooner and the remaining computation involved in the matching criterion can be reduced remarkably. Simulation results show that the proposed APDS algorithm has a significant computational speed-up and is the fastest when compared to the conventional partial distortion search algorithms.

One of the main differences between MPEG-4 and previously standardized video coding schemes is the support of arbitrarily shaped video objects, for which most of the existing fast motion estimation algorithms are not suitable. The conventional fast motion estimation algorithm works well for opaque macroblocks, but not in the case of a boundary macroblock which contains a large number of local minima on its error surface. We propose a fast search algorithm which incorporates the binary alpha-plane to predict accurately the motion vectors of boundary macroblocks. Besides, these accurate motion vectors can be used to develop a novel priority search algorithm which is an efficient search strategy for the remaining opaque macroblocks. Experimental results show that, compared to the conventional methods, our approach requires a low computational complexity and provides a significant improvement in terms of accuracy in motion-compensated video object planes.