On block motion estimation using a novel search strategy for an improved adaptive pixel decimation

Block motion estimation using the exhaustive full search is computationally intensive. Previous fast algorithms tend to reduce the computation by limiting the number of locations to be searched and by reducing the number of pixels for the matching criterion. However, a large prediction error results when these two types of techniques are combined to form a fast algorithm. In this paper, first, we present a new adaptive pixel decimation algorithm with an appropriate pixel selection control. The proposed algorithm selects a targeted number of most representative pixels, which avoids the fluctuation of the computational complexity among different frames. Second, a smart search strategy is proposed which is an excellent complement of the adaptive pixel decimation to form a very efficient block motion estimation algorithm. The new search strategy uses a newly defined matching criterion to adaptively select search locations in the second step of fast motion estimation. It is found that this proposed combination is more robust than previous fast algorithms. Experimental results show that, as compared to the conventional approach, this novel algorithm is more robust, produces smaller motion compensation errors, and has simplified computational complexity. (C) 1998 Academic Press.