Efficient multilevel successive elimination algorithms for block matching motion estimation

The authors present fast algorithms to reduce the computations of block matching algorithms, for motion estimation in video coding. Efficient multilevel successive elimination algorithms are based on the multilevel successive elimination. Efficient multilevel successive elimination algorithms consist of four algorithms. The first algorithm is given by the sum of absolute difference between the sum norms of sub-blocks in a multilevel successive elimination algorithm (MSEA) using the partial distortion elimination technique. By using the first algorithm, computations of MSEA can be reduced further. In the second algorithm, the sum of absolute difference (SAD) is calculated adaptively from large value to small value according to the absolute difference values between pixels of blocks. By using the second algorithm, the partial distortion elimination in the SAD calculation can occur early, therefore the computations of MSEA can be reduced. The second algorithm is useful not only with MSEA, but also with all kinds of block matching algorithms. In the third algorithm, the elimination level of the MSEA can be estimated. Accordingly, the computations of the MSEA related to the level lower than the estimated level can be reduced. The fourth algorithm is, first of all, to search the motion vector over the half sampled search points. At the second search, the authors search the unsampled search points around the tested search points where the motion vector may exist from the first search results. The motion estimation accuracy of the fourth algorithm is nearly 100% and the computations can be greatly reduced.