Research Of Reducing Local Optimal Error Of Fast Search Algorithms

Motion Estimation plays a very important part in video encoder, which accounted for more than 50% of the amount of coding. Because of computational complexity of exhaustive search, it has no practical value. In order to reduce the amount of computation, the researchers put forward a variety of fast search algorithms such as three step search, four step search, diamond search, etc.Although fast search algorithms can effectively reduce the amount of search, because of their choice to search in the search window, it can easily fall into local optimal and thus produce error, which is called as local optimal error. How to solve local optimal problem has always been a hot topic. Through analysis, the approach to reduce the local optimal error can generally be divided into two types: one is to improve the search algorithm, the other is to improve search plan, and this paper is to further the discussion on the base of the two methods.On the basis of the analysis of the classical fast search algorithms, this paper proposes a modified fast search algorithm, two-phase search algorithm. It mainly adopts improving the first step search volume to achieve the purpose of reducing local optimal error.But how to assess the quality of a fast search algorithm is the problem faced when proposes a new algorithm. In comparison to fast search algorithms, the exhaustive search algorithm has the features of the largest and highest accuracy of search, so this paper proposed exhaustive search algorithm as a reference point. All fast search algorithms for the evaluation compare with the reference point, and get a value. The value is as the quality value of a fast search algorithm.Multi-resolution motion estimation is an improvement to the search plan, and it no longer limited to the search of two adjacent frames, but by choosing initial search point to reduce the local optimal error of the fast search algorithms. The wavelet-based multi-resolution motion estimation is developed on this basis. It uses multi-scale feature of the wavelet to get sub-images which own different resolution, and then constructs the pyramid structure of multi-resolution. In comparison to relative fast search algorithms...