Evaluation and Comparison of Motion Estimation Algorithms for Video Compression

Importance of digital video coding has increased significantly since the 90s when MPEG-1 first came to the picture. Compared to analog video, video coding achieves higher data compression rates without significant loss of subjective picture quality which eliminates the need of high bandwidth as required in analog video delivery to a large extent. Digital video is immune to noise, easier to transmit and is able to provide a more interactive interface to the users [1]. The specialized nature of video applications has led to the development of video processing systems having different size, quality, performance, power consumption and cost.

A major problem in a video sequence is the high requirement of memory space for storage. A typical system needs to send dozens of individual frames per second to create an illusion of a moving picture. For this reason, several standards for compression of the video have been developed. Each individual frame is coded to remove the redundancy [2]. Furthermore, between consecutive frames, a great deal of redundancy is removed with a motion compensating system. Motion estimation and compensation are used to reduce temporal redundancy between successive frames in the time domain.

A number of fast block matching motion estimation algorithms were considered in different video coding standards because massive computation were required in the implementation of exhaustive search (ES). In order to speed up the process by reducing the number of search locations, many fast algorithms have been developed, such as the existing three-step search (TSS) algorithm [3]. The Three Step Search method is based on the real world image sequence’s characteristic of centre-biased motion vector distribution, and uses centre-biased checking point patterns and a relatively small number of search locations to perform fast block matching. In order to reduce the computational complexity for motion estimation and improve the reliability of the image sequences for superresolution reconstruction, an effective three-step search algorithm is presented. Based on the center-biased characteristic and parallel processing of the motion vector, the new algorithm adopts the multi-step search strategy [4].

A simple, robust and efficient fast block-matching motion estimation ( BMME ) algorithm called diamond search, which employs two search patterns. The first pattern, called large diamond search pattern (LDSP), comprises nine checking points from which eight points surround the center one to compose a diamond shape. The second pattern consisting of five checking points forms a smaller diamond shape, called small diamond search pattern (SDSP).

A simple fast block-matching algorithm (BMA), called adaptive rood pattern searches (ARPS), which consist of two sequential search stages: 1) initial search and 2) refined local search. The initial search is performed only once at the beginning for each MB. This removes unnecessary intermediate search. For the initial search stage, ARP is proposed, based on the available motion vectors (MVs) of the neighboring MBs. In the next stage, a unit-size rood pattern (URP) is exploited repeatedly, and unrestrictedly, until the final MV is found. In this paper we have evaluated the following four algorithms: Exhaustive Search (ES), Three Step Search (TSS), Diamond Search (DS), and ARPS.

• II.    METHODS

In a conventional predictive coding [5-6], the difference between the current frame and the predicted frame is encoded. The prediction is done using any of the BMA. BMA are used to estimate the motion vectors. Block-matching consumes a significant portion of time in the encoding step.

A.    Block matching algorithm

Block matching algorithm (BMA) is widely used in many motion-compensated video coding systems such as H.261 and MPEG standards to remove interframe redundancy and thus achieve high data compression [7, 8]. The process of block-matching algorithm is illustrated in Fig.1. Motion estimation is performed on the luminance block in which the present frame is matched against candidate blocks in a search area on the reference frame for coding efficiency. The best candidate block is found and its motion vector is recorded. Typically the input frame is subtracted from the prediction of the reference frame, thus interframe redundancy is removed and data compression is achieved. At receiver end, the decoder builds the frame difference signal from the received data and adds it to the reconstructed reference frames. This algorithm is based on a translational model of the motion of objects between frames [9].

Best match

Search Window