Fast block-matching algorithm using threshold-based half stop, cross search, and partial distortion elimination

Jong-Nam Kim; Tae-Sun Choi

doi:10.1117/12.383023

19 April 2000 Fast block-matching algorithm using threshold-based half stop, cross search, and partial distortion elimination

Jong-Nam Kim, Tae-Sun Choi

Author Affiliations +

Proceedings Volume 3974, Image and Video Communications and Processing 2000; (2000) https://doi.org/10.1117/12.383023
Event: Electronic Imaging, 2000, San Jose, CA, United States

Abstract

New three-step search (NTSS) algorithm obtains good picture quality in predicted images with more reduced computation on the average. To reduce more the computation while keeping error performance compared with NTSS, this paper proposes a fast NTSS algorithm using unimodal error surface assumption correlation of causal adjacent matching errors, partial distortion elimination (PDE) algorithm and cross search algorithm. Proposing algorithm reduces less important checking points of the first step in the NTSS by using initial sum of absolute difference (SAD) and adaptive threshold of SAD. Instead of checking seventeen candidate points in the first step like the NTSS, our search algorithm starts with nine checking points according to the result of comparison between initial SAD and adaptive threshold of SAD. We get adaptive threshold of SAD according to the causal adjacent SADs. For more computational reduction without any degradation in prediction quality, we employ PDE and cross search algorithm. Therefore, we can apply this algorithm to variety of applications because the threshold is adaptive to the characteristics of each sequence. Experimentally, our algorithm shows good performance in terms of PSNR of predicted images and average-checking points for each block compared with the conventional NTSS and TSS algorithms.

Citation Download Citation

Jong-Nam Kim and Tae-Sun Choi "Fast block-matching algorithm using threshold-based half stop, cross search, and partial distortion elimination", Proc. SPIE 3974, Image and Video Communications and Processing 2000, (19 April 2000); https://doi.org/10.1117/12.383023

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available