Recently established international video coding standard H.264/AVC and the upcoming standard on scalable video
coding (SVC) bring part of the solution to high compression ratio requirement and heterogeneity requirement.
However, these algorithms have unbearable complexities for real-time encoding. Therefore, there is an important
challenge to reduce encoding complexity, preferably in a scalable manner. Motion estimation and motion compensation
techniques provide significant coding gain but are the most time-intensive parts in an encoder system. They present
tremendous research challenges to design a flexible, rate-distortion optimized, yet computationally efficient encoder,
especially for various applications. In this paper, we present a scalable motion estimation framework for complexitydistortion
consideration. We propose a new progressive initial search (PIS) method to generate an accurate initial
search point, followed by a fast search method, which can greatly benefit from the tighter bounds of the PIS. Such
approach offers not only significant speedup but also an optimal distortion performance for a given complexity
constrain. We analyze the relationship between computational complexity and distortion (C-D) through probabilistic
distance measure extending from the complexity and distortion theory. A configurable complexity quantization
parameter (Q) is introduced. Simulation results demonstrate that the proposed scalable complexity-distortion
framework enables video encoder to conveniently adjust its complexity while providing best possible services.
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.