TY - JOUR

T1 - Multi-direction search algorithm for block motion estimation in H.264/AVC

AU - Lin, C. C.

AU - Lin, Y.

AU - Hsieh, H. J.

PY - 2009

Y1 - 2009

N2 - Many efficient search algorithms such as three-step search, new three-step search, four-step search, block-based gradient descent search, diamond search and hexagon-based search are developed for block motion estimation (ME) to search for the optimal objective function. The block ME technique involves an optimisation problem. Although these algorithms can converge to a minimal point rapidly, they suffer from becoming trapped in local minimum if the objective function has multiple minima. To solve this problem, the hybrid multi-hexagon-grid search (UMHexagonS) algorithm has been proposed in H.264/AVC, in which an unsymmetrical-cross search and an uneven UMHexagonS are employed over a wide search range to find a nearly global minimum. The experiment shows that the hybrid UMHexagonS algorithm is computation expensive and is occasionally trapped in local minimum. The authors propose a novel and fast search algorithm, called multi-direction search (MDS) algorithm, which uses an MDS first to find all possible locally optimal points and then uses the extended hexagon search to refine these points for the final optimal motion vector. The experimental results indicate that a significant improvement in computation reduction (∼30 and 50 reduction in average search points, corresponding to 19 and 37 reduction in total encoding time, for MDS and fast MDS, respectively) can be achieved while maintaining better coding performance, compared with the hybrid UMHexagonS algorithm.

AB - Many efficient search algorithms such as three-step search, new three-step search, four-step search, block-based gradient descent search, diamond search and hexagon-based search are developed for block motion estimation (ME) to search for the optimal objective function. The block ME technique involves an optimisation problem. Although these algorithms can converge to a minimal point rapidly, they suffer from becoming trapped in local minimum if the objective function has multiple minima. To solve this problem, the hybrid multi-hexagon-grid search (UMHexagonS) algorithm has been proposed in H.264/AVC, in which an unsymmetrical-cross search and an uneven UMHexagonS are employed over a wide search range to find a nearly global minimum. The experiment shows that the hybrid UMHexagonS algorithm is computation expensive and is occasionally trapped in local minimum. The authors propose a novel and fast search algorithm, called multi-direction search (MDS) algorithm, which uses an MDS first to find all possible locally optimal points and then uses the extended hexagon search to refine these points for the final optimal motion vector. The experimental results indicate that a significant improvement in computation reduction (∼30 and 50 reduction in average search points, corresponding to 19 and 37 reduction in total encoding time, for MDS and fast MDS, respectively) can be achieved while maintaining better coding performance, compared with the hybrid UMHexagonS algorithm.

UR - http://www.scopus.com/inward/record.url?scp=62649107858&partnerID=8YFLogxK

U2 - 10.1049/iet-ipr.2008.0042

DO - 10.1049/iet-ipr.2008.0042

M3 - 期刊論文

AN - SCOPUS:62649107858

SN - 1751-9659

VL - 3

SP - 88

EP - 99

JO - IET Image Processing

JF - IET Image Processing

IS - 2

ER -