Study Of Fast Motion Estimation In Video Coding

Motion estimation is of great importance in video coding. It costs more than 40 percents of the total encoding time; hence, finding a good fast motion estimation algorithm is useful for speeding up the encoding process.In this paper, the techniques used by fast motion estimation are classified into three groups: threshold early terminating techniques, predicted techniques for motion vector, fast search algorithms for motion vectors. These three kinds of techniques are reviewed and some improvements are given out. The most popular fast search algorithms are based on some discrete search patterns, such as the diamond search and the hexagonal search algorithms. A multiple cross centers search pattern (MCCSP) is proposed in this paper. Based on MCCSP, a multiple cross centers– hexagonal search (MCCHS) algorithm is proposed. The simulation results showed that the proposed MCCHS can save half of the search points while it can maintain similar matching quality as compared with diamond search algorithm, and provide better matching quality and faster speed as compared with hexagonal search and cross-diamond search algorithms.At last, PMVFAST is improved by combining the advantages of the techniques referred above. The early terminating technique is improved by utilizing the information of the coded neighboring blocks. The temporal predicted motion vector becomes more accurate because a more suitable temporal block is chosen as the prediction block. Base on MCCSP, a predicted multiple cross centers search algorithm is proposed for fast block motion estimation. Simulation results showed that it can save about 13 percents of the search points while maintaining similar matching quality as compared to PMVFAST.