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

Chung Yen Su, Yi Pin Hsu

Research output: Contribution to journalArticle

Abstract

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
Volume30
Issue number3
DOIs
Publication statusPublished - 2007 Jan 1

Fingerprint

Image coding
Hardware

Keywords

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

ASJC Scopus subject areas

  • Engineering(all)

Cite this

@article{ef8cc26b75ad401fa807c4f45d065380,
title = "Reused sad for partial search area in efficient three-step search algorithm",
abstract = "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.",
keywords = "Efficient three step search, Real-time motion estimation, Region-split three-step search",
author = "Su, {Chung Yen} and Hsu, {Yi Pin}",
year = "2007",
month = "1",
day = "1",
doi = "10.1080/02533839.2007.9671283",
language = "English",
volume = "30",
pages = "537--543",
journal = "Chung-kuo Kung Ch'eng Hsueh K'an/Journal of the Chinese Institute of Engineers",
issn = "0253-3839",
publisher = "Chinese Institute of Engineers",
number = "3",

}

TY - JOUR

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

AU - Su, Chung Yen

AU - Hsu, Yi Pin

PY - 2007/1/1

Y1 - 2007/1/1

N2 - 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.

AB - 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.

KW - Efficient three step search

KW - Real-time motion estimation

KW - Region-split three-step search

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

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

U2 - 10.1080/02533839.2007.9671283

DO - 10.1080/02533839.2007.9671283

M3 - Article

AN - SCOPUS:34249663252

VL - 30

SP - 537

EP - 543

JO - Chung-kuo Kung Ch'eng Hsueh K'an/Journal of the Chinese Institute of Engineers

JF - Chung-kuo Kung Ch'eng Hsueh K'an/Journal of the Chinese Institute of Engineers

SN - 0253-3839

IS - 3

ER -