On the Design of Pattern-Based Block Motion Estimation Algorithms

Pattern-based block motion estimation (PBME) is a critical element in the contemporary video coding system because it typically dominates the coding efficiency and the computing power. Therefore, many proposals have been suggested to reduce its computational complexity, but most of them are devised...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on circuits and systems for video technology 2010-01, Vol.20 (1), p.136-143
Main Authors: TSAI, Jang-Jer, HANG, Hsueh-Ming
Format: Article
Language:English
Subjects:
Algorithm design and analysis
Algorithms
Analytical models
Application specific processors
Applied sciences
Circuit properties
Coding
Computation
Computational complexity
Design engineering
Early termination
Electric, optical and optoelectronic circuits
Electronic circuits
Electronics
Exact sciences and technology
genetic pattern searches
Image processing
Information, signal and communications theory
Mathematical analysis
Mathematical models
Miscellaneous
modeling
Motion estimation
Optimization
Pattern analysis
Proposals
Searching
Signal processing
starting points
Studies
Switches
Switching and signalling
Switching, multiplexing, switched capacity circuits
Systems, networks and services of telecommunications
Telecommunications
Telecommunications and information theory
Thresholds
Video coding
Video compression
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Pattern-based block motion estimation (PBME) is a critical element in the contemporary video coding system because it typically dominates the coding efficiency and the computing power. Therefore, many proposals have been suggested to reduce its computational complexity, but most of them are devised based on experimental data or heuristic ideas. In this letter, we look into every component of a typical PBME algorithm and fine tune the major components systematically to achieve the optimal or nearly optimal results. Our methodology is developed based on our proposed analytical model together with statistical tools. First, we use the analytic model to analyze and design effective genetic-algorithm-based search patterns. Moreover, we propose an adaptive switching strategy that dynamically switches between two search patterns. Second, we extend our PBME model to evaluate the efficiency of starting (initial search) points. A near optimal set of starting points is progressively identified. Last, we study the early termination threshold technique and suggest a metric in selecting an effective threshold. An accurate threshold mechanism is thus constructed. Combining all these techniques, we develop a PBME algorithm that outperforms most popular algorithms.
ISSN:1051-8215
1558-2205
DOI:10.1109/TCSVT.2009.2026805