A two-stage variable block size motion search algorithm for H.264 encoder

We propose a fast motion search algorithm for H.264 motion estimation with variable block sizes. Motion estimation of H.264 encoder has larger computation complexity than existing video compression standards such as MPEG-4 and H.263 since search steps increase in proportion to the number of block sizes. Here, we employed two-stage motion estimation. In the first stage, 8×8 to 16×16 motion estimation is conducted where only the limited areas are searched in 8×16, 16×8, and 16×16 block sizes using the results of 8×8 block search. Then in the second stage, 4×4/8×4/4×8 block size motion search is performed only when 8×8 block mode is chosen in the first stage. Using the above two approaches, limited search area and conditional smaller block size search, very fast and highly accurate variable block size motion estimation has been achieved. The experimental results also confirmed that the proposed algorithm can greatly reduce the computational complexity while fully using seven block sizes and maintaining motion estimation efficiency.