Complexity and PSNR comparison of several fast motion estimation algorithms for MPEG-4

Peter M. Kuhn; Georg Diebel; Stephan Herrmann; Andreas Keil; Hubert Mooshofer; Andre Kaup; Robert M. Mayer; Walter Stechele

doi:10.1117/12.323203

1 October 1998 Complexity and PSNR comparison of several fast motion estimation algorithms for MPEG-4

Peter M. Kuhn, Georg Diebel, Stephan Herrmann, Andreas Keil, Hubert Mooshofer, Andre Kaup, Robert M. Mayer, Walter Stechele

Author Affiliations +

Proceedings Volume 3460, Applications of Digital Image Processing XXI; (1998) https://doi.org/10.1117/12.323203
Event: SPIE's International Symposium on Optical Science, Engineering, and Instrumentation, 1998, San Diego, CA, United States

Abstract

A complexity and visual quality analysis of several fast motion estimation (ME) algorithms for the emerging MPEG-4 standard was performed as a basis for HW/SW partitioning for VLSI implementation of a portable multimedia terminal. While the computational complexity for the ME of previously standardized video coding schemes was predictable over time, the support of arbitrarily shaped visual objects (VO), various coding options within MPEG-4 as well as content dependent complexity (caused e.g. by summation truncation for SAD) introduce now content (and therefore time) dependent computational requirements, which can't be determined analytically. Therefore a new time dependent complexity analysis method, based on statistical analysis of memory access bandwidth, arithmetic and control instruction counts utilized by a real processor, was developed and applied. Fast ME algorithms can be classified into search area subsampling, pel decimation, feature matching, adaptive hierarchical ME and simplified distance criteria. Several specific implementations of algorithms belonging to these classes are compared in terms of complexity and PSNR to ME algorithms for arbitrarily and rectangular shaped VOs. It is shown that the average macroblock (MB) computational complexity per arbitrary shaped P-VOP (video object plane) depicts a significant variation over time for the different motion estimation algorithms. These results indicate that theoretical estimations and the number of MBs per VOP are of limited applicability as approximation for computational complexity over time, which is required e.g. for average system load specification (in contrast to worst case specification), for real-time processor task scheduling, and for Quality of Service guarantees of several VOs.

Citation Download Citation

Peter M. Kuhn, Georg Diebel, Stephan Herrmann, Andreas Keil, Hubert Mooshofer, Andre Kaup, Robert M. Mayer, and Walter Stechele "Complexity and PSNR comparison of several fast motion estimation algorithms for MPEG-4", Proc. SPIE 3460, Applications of Digital Image Processing XXI, (1 October 1998); https://doi.org/10.1117/12.323203

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