A Fast Variable Block Size Motion Compensation Algorithm for H.264 Video Coding

Chih-Hung Kuo, Meiyin Shen, C. C.Jay Kuo

Research output: Contribution to journalConference article

2 Citations (Scopus)

Abstract

The emerging H.264 video coding standard can achieve a substantial coding gain as compared with existing coding standards. One major contribution of its gain comes from a very rich syntax for motion compensated prediction at the expense of a higher computational complexity. To be more specific, seven modes of different block sizes and shapes (i.e. 16×16, 16×8, 8×16, 8×8, 8×4, 4×8 and 4×4) are supported. To do full search over all modes requires an extremely large amount of computation. We propose a fast search algorithm for the variable block size motion estimation. The proposed algorithm includes three stages. First, an initial estimate of the motion vector is obtained by a multi-resolution motion search. Then, based on the estimated motion vector and its corresponding distortion measure, a rate-distortion model is used to select the initial mode for motion search. Finally, some early-termination rules are adopted to reject impossible block sizes and motion locatios sooner. By avoiding search through all block sizes, the amount of computation involved in the motion search can be substantially reduced. The proposed algorithm can achieve a speed-up factor up to 120 times when compared to the fastest full-search algorithm.

Original languageEnglish
Pages (from-to)76-87
Number of pages12
JournalProceedings of SPIE - The International Society for Optical Engineering
Volume5241
DOIs
Publication statusPublished - 2003 Dec 1
EventMultimedia Systems and Applications VI - Orlando, FL, United States
Duration: 2003 Sep 82003 Sep 9

Fingerprint

Motion Compensation
Motion compensation
Video Coding
Image coding
coding
Motion
Motion Vector
Search Algorithm
Early Termination
Motion estimation
Coding Gain
Rate-distortion
Motion Estimation
Computational complexity
Multiresolution
Fast Algorithm
syntax
Computational Complexity
Speedup
Coding

All Science Journal Classification (ASJC) codes

  • Electronic, Optical and Magnetic Materials
  • Condensed Matter Physics
  • Computer Science Applications
  • Applied Mathematics
  • Electrical and Electronic Engineering

Cite this

@article{e7337a898cdf4d0995d08d8ea892cf3b,
title = "A Fast Variable Block Size Motion Compensation Algorithm for H.264 Video Coding",
abstract = "The emerging H.264 video coding standard can achieve a substantial coding gain as compared with existing coding standards. One major contribution of its gain comes from a very rich syntax for motion compensated prediction at the expense of a higher computational complexity. To be more specific, seven modes of different block sizes and shapes (i.e. 16×16, 16×8, 8×16, 8×8, 8×4, 4×8 and 4×4) are supported. To do full search over all modes requires an extremely large amount of computation. We propose a fast search algorithm for the variable block size motion estimation. The proposed algorithm includes three stages. First, an initial estimate of the motion vector is obtained by a multi-resolution motion search. Then, based on the estimated motion vector and its corresponding distortion measure, a rate-distortion model is used to select the initial mode for motion search. Finally, some early-termination rules are adopted to reject impossible block sizes and motion locatios sooner. By avoiding search through all block sizes, the amount of computation involved in the motion search can be substantially reduced. The proposed algorithm can achieve a speed-up factor up to 120 times when compared to the fastest full-search algorithm.",
author = "Chih-Hung Kuo and Meiyin Shen and Kuo, {C. C.Jay}",
year = "2003",
month = "12",
day = "1",
doi = "10.1117/12.511333",
language = "English",
volume = "5241",
pages = "76--87",
journal = "Proceedings of SPIE - The International Society for Optical Engineering",
issn = "0277-786X",
publisher = "SPIE",

}

A Fast Variable Block Size Motion Compensation Algorithm for H.264 Video Coding. / Kuo, Chih-Hung; Shen, Meiyin; Kuo, C. C.Jay.

In: Proceedings of SPIE - The International Society for Optical Engineering, Vol. 5241, 01.12.2003, p. 76-87.

Research output: Contribution to journalConference article

TY - JOUR

T1 - A Fast Variable Block Size Motion Compensation Algorithm for H.264 Video Coding

AU - Kuo, Chih-Hung

AU - Shen, Meiyin

AU - Kuo, C. C.Jay

PY - 2003/12/1

Y1 - 2003/12/1

N2 - The emerging H.264 video coding standard can achieve a substantial coding gain as compared with existing coding standards. One major contribution of its gain comes from a very rich syntax for motion compensated prediction at the expense of a higher computational complexity. To be more specific, seven modes of different block sizes and shapes (i.e. 16×16, 16×8, 8×16, 8×8, 8×4, 4×8 and 4×4) are supported. To do full search over all modes requires an extremely large amount of computation. We propose a fast search algorithm for the variable block size motion estimation. The proposed algorithm includes three stages. First, an initial estimate of the motion vector is obtained by a multi-resolution motion search. Then, based on the estimated motion vector and its corresponding distortion measure, a rate-distortion model is used to select the initial mode for motion search. Finally, some early-termination rules are adopted to reject impossible block sizes and motion locatios sooner. By avoiding search through all block sizes, the amount of computation involved in the motion search can be substantially reduced. The proposed algorithm can achieve a speed-up factor up to 120 times when compared to the fastest full-search algorithm.

AB - The emerging H.264 video coding standard can achieve a substantial coding gain as compared with existing coding standards. One major contribution of its gain comes from a very rich syntax for motion compensated prediction at the expense of a higher computational complexity. To be more specific, seven modes of different block sizes and shapes (i.e. 16×16, 16×8, 8×16, 8×8, 8×4, 4×8 and 4×4) are supported. To do full search over all modes requires an extremely large amount of computation. We propose a fast search algorithm for the variable block size motion estimation. The proposed algorithm includes three stages. First, an initial estimate of the motion vector is obtained by a multi-resolution motion search. Then, based on the estimated motion vector and its corresponding distortion measure, a rate-distortion model is used to select the initial mode for motion search. Finally, some early-termination rules are adopted to reject impossible block sizes and motion locatios sooner. By avoiding search through all block sizes, the amount of computation involved in the motion search can be substantially reduced. The proposed algorithm can achieve a speed-up factor up to 120 times when compared to the fastest full-search algorithm.

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

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

U2 - 10.1117/12.511333

DO - 10.1117/12.511333

M3 - Conference article

VL - 5241

SP - 76

EP - 87

JO - Proceedings of SPIE - The International Society for Optical Engineering

JF - Proceedings of SPIE - The International Society for Optical Engineering

SN - 0277-786X

ER -