Hexagon-based search pattern for fast block motion estimation

Ce Zhu, Xiao Lin, Lap Pui Chau

Research output: Journal article publicationJournal articleAcademic researchpeer-review

781 Citations (Scopus)


In block motion estimation, a search pattern with a different shape or size has a very important impact on search speed and distortion performance. A square-shaped search pattern is commonly adopted in many popular fast algorithms. Recently, a diamond-shaped search pattern was introduced in fast block motion estimation, which has exhibited faster search speed. Based on an in-depth examination of the influence of search pattern on speed performance, we propose a novel algorithm using a hexagon-based search pattern to achieve further improvement. The hexagon-based search pattern is investigated in comparison with diamond search pattern, which demonstrates significant speedup gain over the diamond-based search. Analysis shows that a speed improvement rate of the hexagon-based search (HEXBS) algorithm over the diamond search (DS) algorithm can be as high as over 80% for locating some motion vectors in certain scenarios. In short, the proposed HEXBS algorithm can find a same motion vector with fewer search points than the DS algorithm. Generally speaking, the larger the motion vector, the more search points the HEXBS algorithm can save, which is further justified by experimental results.

Original languageEnglish
Pages (from-to)349-355
Number of pages7
JournalIEEE Transactions on Circuits and Systems for Video Technology
Issue number5
Publication statusPublished - May 2002
Externally publishedYes


  • Block motion estimation
  • Computational complexity
  • Fast-search algorithm
  • Hexagon
  • Search pattern

ASJC Scopus subject areas

  • Media Technology
  • Electrical and Electronic Engineering


Dive into the research topics of 'Hexagon-based search pattern for fast block motion estimation'. Together they form a unique fingerprint.

Cite this