Efficient block-matching motion estimation algorithms for video coding

Abstract

Digital video compression plays an important role in telecommunications and multimedia systems. In the video coding, the block-matching motion estimation is the most popular approach among others due to its simplicity in both the software and the hardware implementation. Moreover, it has been widely adopted in most international standards for video coding such as ITU-T H.26X, and ISOIIEC MPEG 1,2,4. Indeed, the simplest and most straightforward way to perform motion estimation is by exhaustively examining each block within the search window in the reference frame. This is also referred to the full-search (FS) block-matching algorithm (BMA). However, FS is computationally expensive. Hence, alternative searching methods are highly desirable especially for real-time video applications. In this research work, two novel approaches are proposed to achieve suboptimum performance at significantly reduced complexity comparing with FS method. First of all, in order to fit the highly cross-center-biased (CCB) characteristic of most real world video sequences, a kite-cross-diamond search (KCDS) algorithm is proposed in this thesis. Unlike other traditional search patterns in BMA, such as square-shaped, diamond-shaped and cross-shaped, that all are in vertically and horizontally symmetric shapes, the proposed KCDS algorithm adopts a novel asymmetric kite-shaped search patterns in the search step to achieve similar or even better distortion performance comparing with other fast BMAs. Moreover the speed performance is further boosted by the proposed method. Simulation result shows that KCDS is the fastest algorithm among all testing BMAs, such as diamond search (DS) and cross-diamond search (CDS). We suggest that it is especially suitable for videoconferencing applications. Besides restricting the number of checking blocks in BMA, another approach that uses a partial distortion method to reduce the complexity is presented next. A novel early acceptance (EA) technique is suggested to achieve further speed-up in partial distortion calculation without degrading much of its quality during motion estimation. Unlike most conventional partial distortion search (PDS) algorithms that only reject impossible candidate blocks before the full distortion calculation, the proposed EA technique is capable of accepts potential minimum candidates in a very early stage. By taking the normalized partial distortion search (NPDS) algorithm as the benchmark, simulation result shows that EA technique is able to achieve a speed-up ratio that is much close to the theoretical limit with negligible quality degradation. Furthermore, an early-accepted partial distortion search (EAPDS) algorithm, which is a combinative approach of EA and a quality control technique, is also proposed in this thesis. Experimental result shows that EAPDS not only is the fastest algorithm among other PDSs but also out-performs NPDS in both search speed and prediction accuracy. Hence, EAPDS is more robust and is suitable for a wide range of video applications. Lastly, after reviewing the state-of-the-art video compression standard - H.264/AVC, we give a performance evaluation of our proposed algorithms on H.264 by comparing other fast BMAs. The result also shows that our proposed algorithms out-perform the others by their speed performance.

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