Flexible Triangle Search Algorithm for Block-Based Motion Estimation
- PDF / 1,260,694 Bytes
- 14 Pages / 600.03 x 792 pts Page_size
- 55 Downloads / 263 Views
Research Article Flexible Triangle Search Algorithm for Block-Based Motion Estimation Mohamed Rehan, Pan Agathoklis, and Andreas Antoniou Department of Electrical and Computer Engineering, University of Victoria, P.O. Box 3055, Victoria, Canada BC V8W 3P6 Received 5 October 2005; Revised 24 February 2006; Accepted 7 April 2006 Recommended by Liang-Gee Chen A new fast algorithm for block-based motion estimation, the flexible triangle search (FTS) algorithm, is presented. The algorithm is based on the simplex method of optimization adapted to an integer grid. The proposed algorithm is highly flexible due to its ability to quickly change its search direction and to move towards the target of the search criterion. It is also capable of increasing or decreasing its search step size to allow coarser or finer search. Unlike other fast search algorithms, the FTS can escape from inferior local minima and thus converge to better solutions. The FTS was implemented as part of the H.264 encoder and was compared with several other block matching algorithms. The results obtained show that the FTS can reduce the number of block matching comparisons by around 30–60% with negligible effect on the image quality and compression ratio. Copyright © 2007 Hindawi Publishing Corporation. All rights reserved.
1.
INTRODUCTION
Motion estimation is one of the key components in several video compression algorithms and standards [1–7]. The main purpose of motion estimation is to reduce temporal redundancy between frames in a video sequence. Motion estimation (ME) algorithms can be classified as block-based, pixel-based, or region-based. Block-based algorithms are the most popular due to their implementation simplicity in both software and hardware. In block-based motion estimation, each frame is divided into a group of equally sized blocks called macroblocks and a single vector is used to represent motion for each macroblock. This motion vector is obtained by finding the best match between the block in the frame to be compressed, called the current frame, and the reference frame. The main parameters of the block-based ME process are the search window size, the matching criterion, and the search algorithm. The search window is the area in the reference frame in which the search for the best matching block is performed. The search window is defined by the location of its origin (its upper-left corner) and its size. The matching criterion is the evaluation function that measures the degree of matching between two blocks. Different matching criteria are available such as the sum of absolute difference (SAD), the cross correlation (CC), and the mean-square error (MSE). SAD is mostly used because of the simplicity and ease of its
implementation and is given by
SAD Vi =
N M Sl (x, y) − Sl−1 (x + dx, y + d y),
(1)
x=0 y =0
where M and N are the block width and height, respectively, Sl (x, y) is the pixel value of frame l at relative position x, y from the macroblock origin, and Vi = (dx , d y ) is the displacement vector. A wide ran
Data Loading...
