Share Email Print

Proceedings Paper

Complexity and PSNR comparison of several fast motion estimation algorithms for MPEG-4
Author(s): Peter M. Kuhn; Georg Diebel; Stephan Herrmann; Andreas Keil; Hubert Mooshofer; Andre Kaup; Robert M. Mayer; Walter Stechele
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper 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.

Paper Details

Date Published: 1 October 1998
PDF: 14 pages
Proc. SPIE 3460, Applications of Digital Image Processing XXI, (1 October 1998); doi: 10.1117/12.323203
Show Author Affiliations
Peter M. Kuhn, Technical Univ. of Munich (Japan)
Georg Diebel, Technical Univ. of Munich (Germany)
Stephan Herrmann, Technical Univ. of Munich (Germany)
Andreas Keil, Technical Univ. of Munich (Germany)
Hubert Mooshofer, Technical Univ. of Munich (Germany)
Andre Kaup, Siemens Corporate Technology (Germany)
Robert M. Mayer, Siemens Corporate Technology (Germany)
Walter Stechele, Technical Univ. of Munich (Germany)

Published in SPIE Proceedings Vol. 3460:
Applications of Digital Image Processing XXI
Andrew G. Tescher, Editor(s)

© SPIE. Terms of Use
Back to Top
Sign in to read the full article
Create a free SPIE account to get access to
premium articles and original research
Forgot your username?