Novel computationally scalable algorithm for motion estimation

Krisda Lengwehasatit; Antonio Ortega; Andrea Basso; Amy R. Reibman

doi:10.1117/12.298382

9 January 1998 Novel computationally scalable algorithm for motion estimation

Krisda Lengwehasatit, Antonio Ortega, Andrea Basso, Amy R. Reibman

Proceedings Volume 3309, Visual Communications and Image Processing '98; (1998) https://doi.org/10.1117/12.298382
Event: Photonics West '98 Electronic Imaging, 1998, San Jose, CA, United States

Abstract

Because motion estimation represents a major computational load in typical vide encoding systems, there has been extensive research into fast motion estimation techniques. Given the nature of the process, two major classes of complexity reduction techniques have been proposed. These seek to speed up search times by (i) reducing the cost of each matching operation or (ii) reducing the number of points considered in the search region. In fast matching (FM) techniques, a typical approach is to compute the cost function based on a subset of pixels in a block. In fast search (FS) approaches, the complexity reduction comes from restricting the number of points in the search region, based on fixed rules or on initialization based on motion vectors already computed for other blocks or the previous frame. In this paper we use as a baseline algorithm the initialize- refine technique which belongs to the FS class. We concentrate on the case of real time software video encoding, which allows the flexibility of using variable complexity algorithms. Thus, we modify our baseline algorithm using a Lagrange multiplier approach similar to that of which allows us to explicitly take into account the trade-offs between search complexity and residual frame energy. Furthermore, we combine this algorithm with a novel fast matching method for SAD estimation which allows us to estimate the SAD based on successive subsets of pixels in a particular block. This method naturally possesses computational scalability because we can stop the framework and gives us one more degree of freedom to control the complexity/residual energy trade-off. We show that the combined algorithm achieves reductions of around 25 percent in computation time with respect to the original algorithm without SAD estimation. These results are further improved by designing a test structure that is optimized for typical sequences and where test for an early termination of the matching process are only included if they are though to be worthwhile in terms of the overall complexity.

Citation Download Citation

Krisda Lengwehasatit, Antonio Ortega, Andrea Basso, and Amy R. Reibman "Novel computationally scalable algorithm for motion estimation", Proc. SPIE 3309, Visual Communications and Image Processing '98, (9 January 1998); https://doi.org/10.1117/12.298382

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