Fast-block-matching motion estimation algorithm using optimal search patterns

Dong-Keun Lim; Yo-Sung Ho

doi:10.1117/12.411857

29 December 2000 Fast-block-matching motion estimation algorithm using optimal search patterns

Dong-Keun Lim, Yo-Sung Ho

Proceedings Volume 4310, Visual Communications and Image Processing 2001; (2000) https://doi.org/10.1117/12.411857
Event: Photonics West 2001 - Electronic Imaging, 2001, San Jose, CA, United States

Abstract

For video compression, motion estimation is popularly employed to exploit temporal correlation existing in video sequences. If we employ the full search block matching algorithm for estimating motion vectors, it requires very heavy computational complexity. Although several fast block matching algorithms have been proposed to solve this problem, they sacrifice their reconstructed image quality. In this paper, we derive optimal search patterns for fast block matching motion estimation. By analyzing the block matching algorithm as a function of the block size and the shape, we find optimal search patterns for initial motion estimation. The proposed idea can provide an analytical ground for the current MPEG-2 proposals. In addition, we propose a new fast motion estimation algorithm using adaptive search patterns, considering matching criteria and statistical properties of object displacement. In order to select an appropriate search pattern, we exploit the relationship between the motion vector and the frame difference of each block. By changing the search pattern adaptively, we can improve the motion prediction accuracy, while reducing the required computational complexity compared to other fast block matching algorithms.

Citation Download Citation

Dong-Keun Lim and Yo-Sung Ho "Fast-block-matching motion estimation algorithm using optimal search patterns", Proc. SPIE 4310, Visual Communications and Image Processing 2001, (29 December 2000); https://doi.org/10.1117/12.411857

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

Members: $17.00

Non-members: $21.00 ADD TO CART

PROCEEDINGS
9 PAGES

DOWNLOAD PAPER SAVE TO MY LIBRARY

GET CITATION

RIGHTS & PERMISSIONS

Get copyright permission Get copyright permission on Copyright Marketplace

KEYWORDS

Motion estimation

Distortion

Image quality

Diamond

Statistical analysis

Video

Video compression

Show All Keywords

Keywords/Phrases

Search In:

Publication Years