Share Email Print

Proceedings Paper

Novel computationally scalable algorithm for motion estimation
Author(s): Krisda Lengwehasatit; Antonio Ortega; Andrea Basso; Amy R. Reibman
Format Member Price Non-Member Price
PDF $14.40 $18.00
cover GOOD NEWS! Your organization subscribes to the SPIE Digital Library. You may be able to download this paper for free. Check Access

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

Paper Details

Date Published: 9 January 1998
PDF: 12 pages
Proc. SPIE 3309, Visual Communications and Image Processing '98, (9 January 1998); doi: 10.1117/12.298382
Show Author Affiliations
Krisda Lengwehasatit, Univ. of Southern California (United States)
Antonio Ortega, Univ. of Southern California (United States)
Andrea Basso, AT&T Labs. (United States)
Amy R. Reibman, AT&T Labs. (United States)

Published in SPIE Proceedings Vol. 3309:
Visual Communications and Image Processing '98
Sarah A. Rajala; Majid Rabbani, Editor(s)

© SPIE. Terms of Use
Back to Top