A direction-based unsymmetrical-cross multi-hexagon-grid search algorithm for h.264/avc motion estimation

Zhaoqing PAN, Sam KWONG

Research output: Journal PublicationsJournal Article (refereed)peer-review

12 Citations (Scopus)


The Unsymmetrical-cross Multi-hexagon-grid Search (UMHexagonS) is one of the best fast Motion Estimation (ME) algorithm in H.264/AVC (Advanced Video Coding) reference software. It achieves an excellent coding performance by using multiple initial search point predictors and hybrid block matching search pattern. However, the hybrid search pattern makes the computational complexity of ME increased. In this paper, we propose a Directionbased UMHexagonS (DBUMHexagonS) to further reduce the computational complexity of UMHexagonS. Each block matching search pattern of UMHexagonS is divided into four direction-based sub-search patterns, one of four directions is selected according to the difference between the Motion Vector (MV) of current block and the MV of its collocated block in previous frame, such a direction is applied to all following search patterns. As a result, the number of total search points will be dramatically reduced. Experimental results show that compared to the best UMHexagonS algorithm, the proposed algorithm can save the ME time up to 30.094 % while the rate-distortion performance is not compromised. © Springer Science+Business Media New York 2013.
Original languageEnglish
Pages (from-to)59-72
JournalJournal of Signal Processing Systems
Issue number1
Publication statusPublished - Oct 2013
Externally publishedYes

Bibliographical note

This work was supported in part by the Hong Kong Research Grants Council General Research Fund, under Project 9041495 (CityU 115109) and City University of Hong Kong Stategic Grant 7002729.


  • H264/AVC
  • Motion estimation
  • UMHexagonS
  • Video coding


Dive into the research topics of 'A direction-based unsymmetrical-cross multi-hexagon-grid search algorithm for h.264/avc motion estimation'. Together they form a unique fingerprint.

Cite this