Motion codevector based search for fast motion estimation

In this paper, we present a simple yet effective fast motion vector search algorithm, called motion codevector (MCV) based search. In a coarse-to-fine manner, two stage codebooks are generated by quantizing motion vector ensemble to generate motion codevector based search pattern, which is expected to follow the true distribution of the motion vectors more closely. Expectation maximization (EM) algorithm is adopted to estimate density of the motion codevectors, based on which appropriate search orders of the generated motion codevectors in the two codebooks are determined respectively to facilitate early termination efficiently. Experimental results show that, compared with the hybrid UMHexagonS algorithm adopted in H.264/AVC standard, the proposed approach can achieve a computational reduction of up to 30% while maintaining similar rate-distortion coding performance.