Video Encoding Fast Block Matching Motion Estimation Algorithm

With the development and popularization of computer and network technology, video technology has been widely applied to various applications and played a more and more important role in current information society. Therefore, real time video encoding has become a hot research field. As the main part, motion estimation accounts for about 50% to 80% of the whole encoding computation, so it is the most challenging research topic in video encoding.Block matching motion estimation is relatively simple and can be easily implemented, and is adopted by current international video coding standards. As the most direct and simplest motion estimation algorithm, full search has much high computation complexity and is difficult to be integrated into real time video encoding systems. Many fast block matching methods have been proposed to decrease computation complexity.This article firstly introduces the distribution characteristic of movement vectors and all kinds of block matching fast motion estimation algorithms presented, then a new fast algorithms, predictive cross and triangle search algorithm (PCTS) is proposed: PCTS starts with cross search in the predicted initial point by exploiting the spatial correlation, which can terminate the search at early step for smooth moving sequences.Then it conducts triangle search based on simplex algorithm, which finds optimum vector through the reflection and extension of the triangle apexes. The results show that PCTS is much more effective and efficient in ME than the classic and famous algorithms for the video sequences with smooth or moderate motions, but still tends to trap into the local minimum for those video sequences containing large or complex motion contents.To improve the performance of PCTS, a compact genetic algorithm (CGA) is imbedded in PCTS and a self adapting PCTS/CGA+CTS algorithm is proposed, which exploits an adaptive threshold to choice PCTS algorithm or the CGA+CTS algorithm for different moving blocks. The experiments demonstrate that this algorithm keep the quality in the case of smooth or moderate motions and has a stronger robustness for the sequences with high or irregular motions.