Adaptive search order determination for effective early termination in the N-step search algorithm

Motion estimation occupies most of the required computation in video compression, and many fast search algorithms were proposed to reduce huge computation. SAD (sum-of-absolute difference) calculation is the most computation-intensive process in the motion estimation. Early termination is widely used in SAD calculation, where SAD calculation is terminated and it proceeds to next search position if partial SAD during SAD calculation exceeds current minimum SAD. In this paper, we proposed an adaptive search order determination of N-step search algorithm for effective early termination where only search order of search positions are adaptive rearranged. Candidate search positions are examined in the order of their distances from the predicted motion vector, since early termination occurs earlier in the next candidate search positions if the previously examined search position has smaller SAD. From the simulation, it reduces the computation by 19~29% without performance degradation.