Zero-motion vector-biased cross-diamond search algorithm for rapid block matching motion estimation

High compression ratio and very low encoding computational complexity are the keys in designing successful encoder for energy constrained video conversational applications since coding efficiency, speed, and energy frugality are critical. Computation-intensive motion estimation (ME) process is an obstacle to overcome for these applications. To control and optimize encoding complexity behavior, we propose a zero-motion-vector-biased cross-diamond search (ZCDS) algorithm for rapid block matching based on the well-known cross-diamond search (CDS) algorithm. Unlike many conventional fast block-matching algorithms (BMAs), which use either fixed threshold or distortion function of temporally or spatially adjacent blocks for early search termination, ZCDS is based on a dynamic block distortion threshold, via a linear model utilizing already computed statistics and information of current block. A new fine granularity halfway-stop (FGHS) method is also proposed for early termination of the search process. Designed for various motion contents, ZCDS adaptively starts with a small or large cross search pattern, which is automatically determined via an initial block matching distortion. Experimental results show that the proposed algorithm achieves smoother motion vector fields and demands significantly less search points with marginal peak-signal-to-noise-ratio (PSNR) loss when compared to those of full search and other conventional fast BMAs.