Share Email Print

Proceedings Paper

Efficient parallel algorithm for hierarchical block-matching motion estimation
Author(s): Charalampos Konstantopoulos; Andreas I. Svolos; Christos Kaklamamis
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper Abstract

Motion estimation is an integral part of most of the video coding schemes that have been proposed in the literature. It is also the most computationally intensive part in these schemes and thus is usually implemented on high performance parallel architectures. In this paper, we deal with a multiresolution (hierarchical) block matching motion estimation algorithm. Specifically, we parallelize this algorithm on a hypercube based multiprocessor. As this algorithm presents a non regular data flow, it could not be easily implemented on systolic arrays. In contrast, the use of such an advanced network as the hypercube overcomes the problem of the non regular data flow, thereby providing high performance. Another important point in our study is that our multiprocessor is assumed to be fine grained unlike most of multiprocessors that has been proposed for video coding schemes. The constraint of limited local memory in each processor leads to frequent interprocessor communication and thus the employed techniques should be carefully selected in order to lower the communication overhead. Coarse grained architectures do not have this kind of problem because each processor can take most of the data it will need throughout the algorithm execution from the beginning. This greatly reduces the communication overhead, and thus the algorithm design is rather straightforward in this case.

Paper Details

Date Published: 28 December 1998
PDF: 10 pages
Proc. SPIE 3653, Visual Communications and Image Processing '99, (28 December 1998); doi: 10.1117/12.334697
Show Author Affiliations
Charalampos Konstantopoulos, Univ. of Patras (Greece)
Andreas I. Svolos, Univ. of Patras (Greece)
Christos Kaklamamis, Univ. of Patras (Greece)

Published in SPIE Proceedings Vol. 3653:
Visual Communications and Image Processing '99
Kiyoharu Aizawa; Robert L. Stevenson; Ya-Qin Zhang, Editor(s)

© SPIE. Terms of Use
Back to Top