Fast and efficient motion estimation using diamond zonal-based algorithms

Motion estimation has always been an important part of video encoding systems because it can reduce temporal redundancy effectively and thus has significant impact on the bit rate and the output visual quality of the encoded sequence. Unfortunately, when using the brute-force full search algorithm, motion estimation consumes a very large portion of the encoding time. Previously, several algorithms have been proposed which try to reduce complexity, usually, with a significant loss in visual quality. Based on the diamond zonal search framework we introduced recently, we propose in this paper a novel algorithm called advanced diamond zonal search (ADZS), which was submitted to and well received by the Moving Pictures Experts Group (MPEG) standard committee for possible inclusion as an encoder optimization tool. ADZS was criticized in MPEG for using fixed thresholds, which may not be suitable for all video sequences. To address this issue, we further propose a threshold-adaptive version called threshold-adaptive advanced diamond zonal search (TAADZS). Simulation results verify the superior performance of ADZS and TAADZS over other fast algorithms and the robustness of TAADZS over ADZS.