A novel cross-hexagon search algorithm for fast block motion estimation

Kamel Belloulata; Shiping Zhu; Jun Tian; Xiaodong Shen

doi:10.1109/WOSSPA.2011.5931406

A novel cross-hexagon search algorithm for fast block motion estimation

Kamel Belloulata^*
, Shiping Zhu
, Jun Tian
, Xiaodong Shen

^*Corresponding author for this work

School of Instrumentation and Optoelectronic Engineering

University of Sidi-Bel-Abbès
Beihang University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

11 Scopus citations

Abstract

Search patterns and the center-biased characteristics of motion vector distribution have large impact on both searching speed and quality of block motion estimation. In this paper, we propose a new cross-hexagon search algorithm (NCHEXS) using two cross-shaped search patterns as the first two initial steps and large/small hexagon-shaped patterns as the subsequent steps for fast block motion estimation (BME). NCHEXS employs halfway stop technique to achieve significant speedup on sequences with stationary and quasi-stationary blocks. To further reduce computational complexity, NCHEXS employs Modified Partial Distortion Criterion (MPDC). Experimental results indicate that the improvements of NCHEXS over Hexagon Search (HEXS) and Cross-Diamond Search (CDS) can save 45% and 28% of search points while keeping similar PSNR, and NCHEXS provides faster searching speed and smaller distortion than other popular fast block-matching motion estimation algorithms.

Original language	English
Title of host publication	7th International Workshop on Systems, Signal Processing and their Applications, WoSSPA 2011
Pages	1-4
Number of pages	4
DOIs	https://doi.org/10.1109/WOSSPA.2011.5931406
State	Published - 2011
Event	7th International Workshop on Systems, Signal Processing and their Applications, WoSSPA 2011 - Tipaza, Algeria Duration: 9 May 2011 → 11 May 2011

Publication series

Name	7th International Workshop on Systems, Signal Processing and their Applications, WoSSPA 2011

Conference

Conference	7th International Workshop on Systems, Signal Processing and their Applications, WoSSPA 2011
Country/Territory	Algeria
City	Tipaza
Period	9/05/11 → 11/05/11

Keywords

block-matching
cross-hexagon search
modified partial distortion criterion
motion estimation

Access to Document

10.1109/WOSSPA.2011.5931406

Cite this

Belloulata, K., Zhu, S., Tian, J., & Shen, X. (2011). A novel cross-hexagon search algorithm for fast block motion estimation. In 7th International Workshop on Systems, Signal Processing and their Applications, WoSSPA 2011 (pp. 1-4). Article 5931406 (7th International Workshop on Systems, Signal Processing and their Applications, WoSSPA 2011). https://doi.org/10.1109/WOSSPA.2011.5931406

@inproceedings{37dfd02e5757447c96379c2427a97e64,

title = "A novel cross-hexagon search algorithm for fast block motion estimation",

abstract = "Search patterns and the center-biased characteristics of motion vector distribution have large impact on both searching speed and quality of block motion estimation. In this paper, we propose a new cross-hexagon search algorithm (NCHEXS) using two cross-shaped search patterns as the first two initial steps and large/small hexagon-shaped patterns as the subsequent steps for fast block motion estimation (BME). NCHEXS employs halfway stop technique to achieve significant speedup on sequences with stationary and quasi-stationary blocks. To further reduce computational complexity, NCHEXS employs Modified Partial Distortion Criterion (MPDC). Experimental results indicate that the improvements of NCHEXS over Hexagon Search (HEXS) and Cross-Diamond Search (CDS) can save 45\% and 28\% of search points while keeping similar PSNR, and NCHEXS provides faster searching speed and smaller distortion than other popular fast block-matching motion estimation algorithms.",

keywords = "block-matching, cross-hexagon search, modified partial distortion criterion, motion estimation",

author = "Kamel Belloulata and Shiping Zhu and Jun Tian and Xiaodong Shen",

year = "2011",

doi = "10.1109/WOSSPA.2011.5931406",

language = "英语",

isbn = "9781457706905",

series = "7th International Workshop on Systems, Signal Processing and their Applications, WoSSPA 2011",

pages = "1--4",

booktitle = "7th International Workshop on Systems, Signal Processing and their Applications, WoSSPA 2011",

note = "7th International Workshop on Systems, Signal Processing and their Applications, WoSSPA 2011 ; Conference date: 09-05-2011 Through 11-05-2011",

}

Belloulata, K, Zhu, S, Tian, J & Shen, X 2011, A novel cross-hexagon search algorithm for fast block motion estimation. in 7th International Workshop on Systems, Signal Processing and their Applications, WoSSPA 2011., 5931406, 7th International Workshop on Systems, Signal Processing and their Applications, WoSSPA 2011, pp. 1-4, 7th International Workshop on Systems, Signal Processing and their Applications, WoSSPA 2011, Tipaza, Algeria, 9/05/11. https://doi.org/10.1109/WOSSPA.2011.5931406

A novel cross-hexagon search algorithm for fast block motion estimation. / Belloulata, Kamel; Zhu, Shiping; Tian, Jun et al.
7th International Workshop on Systems, Signal Processing and their Applications, WoSSPA 2011. 2011. p. 1-4 5931406 (7th International Workshop on Systems, Signal Processing and their Applications, WoSSPA 2011).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - A novel cross-hexagon search algorithm for fast block motion estimation

AU - Belloulata, Kamel

AU - Zhu, Shiping

AU - Tian, Jun

AU - Shen, Xiaodong

PY - 2011

Y1 - 2011

N2 - Search patterns and the center-biased characteristics of motion vector distribution have large impact on both searching speed and quality of block motion estimation. In this paper, we propose a new cross-hexagon search algorithm (NCHEXS) using two cross-shaped search patterns as the first two initial steps and large/small hexagon-shaped patterns as the subsequent steps for fast block motion estimation (BME). NCHEXS employs halfway stop technique to achieve significant speedup on sequences with stationary and quasi-stationary blocks. To further reduce computational complexity, NCHEXS employs Modified Partial Distortion Criterion (MPDC). Experimental results indicate that the improvements of NCHEXS over Hexagon Search (HEXS) and Cross-Diamond Search (CDS) can save 45% and 28% of search points while keeping similar PSNR, and NCHEXS provides faster searching speed and smaller distortion than other popular fast block-matching motion estimation algorithms.

AB - Search patterns and the center-biased characteristics of motion vector distribution have large impact on both searching speed and quality of block motion estimation. In this paper, we propose a new cross-hexagon search algorithm (NCHEXS) using two cross-shaped search patterns as the first two initial steps and large/small hexagon-shaped patterns as the subsequent steps for fast block motion estimation (BME). NCHEXS employs halfway stop technique to achieve significant speedup on sequences with stationary and quasi-stationary blocks. To further reduce computational complexity, NCHEXS employs Modified Partial Distortion Criterion (MPDC). Experimental results indicate that the improvements of NCHEXS over Hexagon Search (HEXS) and Cross-Diamond Search (CDS) can save 45% and 28% of search points while keeping similar PSNR, and NCHEXS provides faster searching speed and smaller distortion than other popular fast block-matching motion estimation algorithms.

KW - block-matching

KW - cross-hexagon search

KW - modified partial distortion criterion

KW - motion estimation

UR - https://www.scopus.com/pages/publications/79960928408

U2 - 10.1109/WOSSPA.2011.5931406

DO - 10.1109/WOSSPA.2011.5931406

M3 - 会议稿件

AN - SCOPUS:79960928408

SN - 9781457706905

T3 - 7th International Workshop on Systems, Signal Processing and their Applications, WoSSPA 2011

SP - 1

EP - 4

BT - 7th International Workshop on Systems, Signal Processing and their Applications, WoSSPA 2011

T2 - 7th International Workshop on Systems, Signal Processing and their Applications, WoSSPA 2011

Y2 - 9 May 2011 through 11 May 2011

ER -

A novel cross-hexagon search algorithm for fast block motion estimation

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this