Research Of Prediction Search Starting Point And Motion Estimation Algorithm In Video Compression

Side information is the prediction of the current frame, which is used to Turbo decoding and reconstruction process in distributed video coding. The quality of side information directly influences reconstruction quality and the overall Rate-Distortion performance of the distributed video coding codec. Therefore, the side information is one of the core-techniques of distributed video coding. Using time-domain correlation of adjacent frames, edge information is obtained through interpolation of motion estimation based on reconstruction frame. How to obtain the high quality side information through motion estimation has become a hot research area and difficult in distributed video coding. Motion estimation is also the key technology in the traditional video coding technology. Efficient, fast motion estimation algorithm was studied and designed has become an important direction in the current video compression technology. Among current motion estimation methods, block-matching algorithm (BMA) is the most popular one owing to its simple principle and suitability for implementation, which have been widely applied to popular video compression coding standards to improve compression efficiency. Although these traditional fast algorithms can improve search speed significantly, they have an inherent shortcoming of being liable to get trapped in local optima. Traditional fast algorithms can degrade the quality of motion estimation to some extent. It is an important issue for motion estimation. Prediction of the search starting point is the prediction of initial search center whose essence that is to make the initial search center as close as the global optimal matching point. Prediction of the search starting point can effectively reduce the possibility of being liable to get trapped in local optima in the search process. Therefore, prediction of the search starting point has become a hot topic problem which is an important aspect of the study for motion estimation. Accurately predicting the starting point will provide a good starting point for the follow-up search, combined with the suspension of the appropriate criteria and search strategy, the algorithm can quickly find the global optimal matching point, reduce the matching calculation, speed up the searching speed and improved search accuracy.There are two the main task in this thesis, the first main task is to analyze and verify the basic characteristics of the motion vector and to study and achieve common prediction methods. On the basis of these methods, a novel method of the prediction of searching initial point was proposed. The second main task is to analyze and study several classic motion estimation algorithms, and on the basis of these algorithms, Combined with improved prediction method, Stationary block termination criteria and multi-template strategy, an improved motion estimation fast algorithm is proposed—Multi-template Search based on Prediction the starting point (PMS). Firstly, this thesis elaborates the essential principle of the motion estimation and the main technologies based on block matching, introduces Full Search method and several typical motion estimation fast algorithms based on block matching, analyzes characteristic of some algorithms and evaluates their advantage and disadvantage through the data get from experiment. Then the single-extreme and multi-extreme value distribution of SAD value, the center-biased and center offset distribution characteristic of motion vector and motional correlation of the adjacent the motion vector were verified by experiment. Then this thesis introduces the common prediction methods, such as median algorithm, mean algorithm, SAD comparison method and so on, analyzes each characteristic, and evaluates their advantage and disadvantage through the data get from experiment, and on the basis of the center of bias and the center offset distribution, an attempt is made to improve and achieve prediction methods based on fixed weights. The results showed that:new prediction method maintains the accuracy as well as DS, but the search points at least. According to the position of MBD point, different strategies are adaptively utilized. Dual judge to stationary block is to abort ahead of time search to avoid unnecessary search, Multi-template motion estimation based on prediction search starting point (PMS) is proposed. The new algorithm takes full advantage of the distribution and statistic characteristic of motion vector, adopts Double-cross-shaped search pattern as the initial template to make first step search to take into account the different moving types of macro block, adopts large diamond search to determine the next step search direction, adopts arc template to search motion vectors of large movement, adopts small diamond search to search the optimum motion vector. The new algorithm takes full advantage of spatial correlation of motion vector to predict search starting point, reduces the possibility of falling into local optimum, increases of search precision. To some extent compensated for influence of owing to fixed threshold to determine the stationary block to makes the target angular accuracy degrade. Finally, experiments are made to prove the performance of the new algorithm. Then we can find that PMS are better than others by analyzing the result of the experiment and the anticipated results are realized. According to the experiments data, the following conclusions can be drawn, for whatever small, middle and large motion of video sequences, the algorithm in this paper keeps the two relatively high-performance in the search and accuracy and search speed.