Small-diamond-based search algorithm for fast block motion estimation

Shen Chuan Tai, Ying Ru Chen, Yu Hung Chen

Research output: Contribution to journalArticlepeer-review

16 Citations (Scopus)


A good fast motion search algorithm should efficiently speed up the encoding time and keep the quality of encoded video stable at the same time. Researches have shown that many fast algorithms lose the quality requirement in some special video sequences. These video sequences often have heavy motions and need large search windows for motion vector search. E3SS, DS, and E-HEXBS, which are famous algorithms, are not good enough in these sequences. As to UMHexagonS, it is able to meet the high video quality requirement very well, but it costs too much computation. This paper introduces a multi-stage motion estimation algorithm. The algorithm ensures getting good video quality while decreases the motion search time efficiently. It divides the search regions into many un-overlapped small-diamond regions and forces the motion search to go outward for larger motion vectors. This method is also designed to avoid mistaking local optimal motion vectors. For this reason, the selected motion vector is refined by several stages. Experimental results show that the proposed algorithm uses almost the same number of checking points as E3SS but achieves a better quality. Furthermore, the proposed algorithm is also tested in H.264/AVC JM9.5 encoder; the experimental results show that this algorithm is also suitable for variable block-size motion estimation.

Original languageEnglish
Pages (from-to)877-890
Number of pages14
JournalSignal Processing: Image Communication
Issue number10
Publication statusPublished - 2007 Nov 1

All Science Journal Classification (ASJC) codes

  • Software
  • Signal Processing
  • Computer Vision and Pattern Recognition
  • Electrical and Electronic Engineering


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

Cite this