Markov model fuzzy-reasoning based algorithm for fast block motion estimation

This paper presents a Markov model fuzzy-reasoning based algorithm for fast block motion estimation. To reduce computational complexity, the existing fast search algorithms move iteratively toward the winning point based only on a finite set of search points in every stage. Despite the efficiency of these algorithms, the search process is easily trapped into local minima, especially for high activity video sequences. To overcome this difficulty, we propose a three-states Markov model based algorithm that invokes the fuzzy-reasoning to provide the search an acceptance probability of being able to move out of local minima. Two schemes are employed to further enhance the performance of the algorithm. First, a set of initial search points that exploit high correlations among the motion vectors of the temporally and spatially adjacent blocks as well as their surrounding points are used. Second, an alternate search strategy is addressed to cover more area without increasing computations. Simulation. results show that the new algorithm offers superior performance with lower computational complexity and picture quality increase in terms of search points/block and MSE/pel, respectively, compared with the previous works in various scenarios. (c) 2005 Elsevier Inc. All rights reserved.