Motion estimation using on-line arithmetic

Abstract

This paper proposes a class of motion estimation operation technologies and MSD-first comparators, which are implemented using on-line arithmetic. In on-line arithmetic, the numbers are represented in the redundant binary representation, where carry/borrow propagation chains are eliminated. This is because most significant digit (MSD) first accumulates and subtraction algorithms are applied by signed-digit (SD) representations. Most of previous MSD-first researches are used to decrease the initiation interval of recursive computations, particularly in IIR filers. In motion pictures compression process, motion estimation (ME) is a heavy loading. Intact motion estimation implementation using online arithmetic adopts MSD-first operations. This benefits reducing redundant calculation in two parts: I. Delete redundant summation of absolute different (SAD) calculation if existence another smaller SAD has been ascertained. 2. Decrease redundant lower-digits calculation if motion vector has been found. We developed two keys for MSD-first algorithm implement ME, including SAD calculation and SD comparison. This MSD-first ME algorithm can also cooperate with existent search algorithms to lower SAD computation further. This MSD-first ME algorithm can reduce 55% primitive SD operations.