Applications of fast low-distortion motion estimation algorithms in video coding

Abstract

The abundant size of raw digital video data is a common problem in video coding and processing. Traditional lossless image compression techniques cannot effectively handle the redundancies in video data. Usually, a kind of hybrid coding technique - a mixture of intra-frame and inter-frame coding is used to exploit the spatial and temporal redundancies. In inter-frame coding a reference frame is required for generating predictions. The two components involved in this process are called motion compensation and motion estimation (ME), which is the focus of this research work. The easiest and straightforward implementation of motion estimation is called full Search, which is a kind of exhaustive method that sequentially search all the candidate positions. Since this method yields an optimal prediction, it is the default algorithm in all reference models. Just like a coin has two sides, this method has extremely high computational complexity, and typically consumes 40% to 90% of the overall loading of an encoder. As a result. the objective of this research is to analyze different feasible ways to speed up the ME process. as well as keep the prediction result close to optimum. The first proposed approach is to reduce the redundancy in the fine-resolution motion search. For most popular fast block-matching algorithms (BMA). the complexity is only reduced by saving the number of search points in coarse search module. whereas full search is still used for the fine-resolution inner search. Therefore. two enhanced BMAs. fast-convergence hexagon-based search (FC'HBS) and fast-convergence diamond search (FCDS). are proposed with new fast inner search techniques to improve the corresponding original search. Conventionally, inner search techniques are used to predict the minimum distortion point in the inner search area based on the group distortion of evaluated neighbors. Statistical analyses show that there is a strong correlation between the neighboring distance and distortion. As a result. the previous techniques are replaced by our point-oriented grouping strategy. and normalized group distortion calculation, which lead to substantially faster speed and better prediction accuracy. Another proposed approach targets on the encoders using long-term memory motion compensated prediction (LTMCP) where multiple reference frames are looked up for motion estimation. LTMCP improves the rate-distortion performance by introducing much higher loading to the system. Without considering temporal correlations between multiple reference frames. conventional single-frame search algorithms can still be applied to multi-frame ME, but using a rather inefficient frame-by-frame approach. In contrast to those methods that orderly search each reference frame. the proposed algorithm adopts a novel recent-biased search strategy and makes use of 3-dimensional search patterns to sub-sample the 3-dimensional memory space as a whole. This approach significantly boosts the efficiency of the block-matching process. In contrast to the previous two approaches. the third proposed method does not cut down the number of search points. but alleviate the computations by efficient distortion calculation. This kind of algorithm is classified as partial distortion algorithm. Unlike most other algorithms that sequentially search with a spiral order, the suggested three-pass partial distortion search (3PPDS) algorithm screens out the candidates in three different passes. By exploiting the correlation of neighboring rejection age, computational resources can be redistributed based on the importance of candidates. As a result, 3PPDS not only accomplishes lowest complexity among the competitors, but also carries fill1 search quality. Finally, experiments are conducted on the reference model of the state-of-the-art standard encoder. H.264. The proposed algorithms are compared with other famous BMAs as well as the fast ME used by the reference model. Experimental results indicate that our algorithms can achieve significantly faster speed with full search rate-distortion performance.

Date of Award	3 Oct 2005
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Lai Man PO (Supervisor)