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.
展开▼
