Efficient parallel algorithm for hierarchical block-matching motion estimation

Charalampos Konstantopoulos; Andreas I. Svolos; Christos Kaklamamis

doi:10.1117/12.334697

28 December 1998 Efficient parallel algorithm for hierarchical block-matching motion estimation

Charalampos Konstantopoulos, Andreas I. Svolos, Christos Kaklamamis

Proceedings Volume 3653, Visual Communications and Image Processing '99; (1998) https://doi.org/10.1117/12.334697
Event: Electronic Imaging '99, 1999, San Jose, CA, United States

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.

Citation Download Citation

Charalampos Konstantopoulos, Andreas I. Svolos, and Christos Kaklamamis "Efficient parallel algorithm for hierarchical block-matching motion estimation", Proc. SPIE 3653, Visual Communications and Image Processing '99, (28 December 1998); https://doi.org/10.1117/12.334697

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