The Research And Implementation Of Motion Estimation In Video Coding

With the fast developing of computer and communication technology, the traditional multimedia business has been unsatisfied to the demands of people, and multimedia apply-serves on network are expected. These multimedia apply-serves have much higher demands on the transmission bandwidth and the transmission speed, especially on video. So, it has been the hotspot of the present, researches to research and develop the new video compression technology with higher quality and efficiency.Among the factors which impact the quality and efficiency of video compression, motion estimation is one of the most influencing factors. The motion estimation algorithm is the hot research point in the related field and several new algorithms were proposed each year recently. But the module of motion estimation is still the most time-exhausted one in video coding while occupying the most system resources. The performance of this kind of motion estimation algorithms having been upgraded significantly under the effort of researchers can not meet the requirement of real-time application. Whether we can find the new break-through is the key to get more advancement of the fast motion estimation algorithm in the future.In block motion estimation, search patterns with different shapes or sizes and the center-biased characteristics of motion-vector distribution have a large impact on the searching speed and quality of performance. Therefore, some novel algorithms were proposed. In this thesis, a fast three step search (FTSS) algorithm is proposed, based on extensive study of the complexity and improvement of precision in the process of search. We'll derive the FTSS from the conventional TSS algorithm. We'll keep the structure of three-step, while reducing checking points among the candidates. In the proposed algorithm, we reduce the amount of the computation for checking the candidate motion vector using the unimodal error surface assumption (UESA). The UESA means that matching error increases monotonically while getting away from the global minimum of matching error. We check only three points at first instead of checking nine points for each step.In many fast algorithms, TSS has been used for real time video encoding and low bit-rate video communications because of reduced computations, simplicity and reasonable performance. The simple and efficient (SES) algorithm requires about one half of the computation for TSS,however, it keeps the lower performance. These two algorithms both have their own advantages and disadvantages. This paper proposes a new algorithm (Fast Three-Step Search) for further reduction without serious degradation of error performance. The FTSS combines the advantage of the three-step search algorithm with the benefit of the simple and efficient algorithm. It will be shown that the fast three-step search algorithm is computationally efficient while keeping the same performance as one of TSS.