Reused sad for partial search area in efficient three-step search algorithm

Chung Yen Su, Yi Pin Hsu*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review


In real-time applications, three-step search (TSS) is always preferred because it has a regular search pattern. However, it may lose its performance in coding video sequences with small motion. To overcome this drawback, some fast search algorithms are proposed, for example, new three-step search (NTSS) and efficient three step search (ETSS). In this paper, a more effective fast search algorithm called region-split three-step search (RSTSS) is proposed. In addition to the feature of a regular search pattern, the RSTSS splits the search region into four sub-regions and enters only one of the sub-regions to search for the best motion vector. The main idea used in the RSTSS is to reuse the sum of absolute difference (SAD) values of the 9 points on a 9 ×9 grid. Experimental results show that the RSTSS performs better than the ETSS in terms of the number of checking points. It can reduce the number of checking points nearly 19% on average and sacrifices only a little mean squared error. Most of all, the RSTSS retains a regular searching pattern that is suitable for hardware implementation.

Original languageEnglish
Pages (from-to)537-543
Number of pages7
JournalJournal of the Chinese Institute of Engineers, Transactions of the Chinese Institute of Engineers,Series A/Chung-kuo Kung Ch'eng Hsuch K'an
Issue number3
Publication statusPublished - 2007


  • Efficient three step search
  • Real-time motion estimation
  • Region-split three-step search

ASJC Scopus subject areas

  • General Engineering


Dive into the research topics of 'Reused sad for partial search area in efficient three-step search algorithm'. Together they form a unique fingerprint.

Cite this