%O Report %F ywang05CAMED %A Wang, Yong %A Chang, Shih-Fu %T Complexity Adaptive Motion Estimation and Mode Decision for H.264 Decoding %I Columbia University %X Emerging video coding standards like H.264 achieves significant advances in improving video quality, reducing bandwidth, but at the cost of greatly increased computational complexity at both the encoder and the decoder. Playing encoded videos produced by such compression standards requires major computational resources and thus power on various handheld devices that are getting increasingly popular in mobile applications. Among the components in the decoding system, the interpolation procedure used in the motion compensation component consumes the largest computation (about 50%) due to the use of sub-pixel motion vectors. One way to reduce this major cost is to change the coding algorithm so that the generated compressed bit streams incur less interpolation operations. In this work, we propose a novel Complexity Adaptive Motion Estimation and mode Decision (CAMED) system to optimize the selection of the motion vectors and motion compensation block modes in order to significantly reduce the computational cost while keeping the video quality virtually unchanged. We accomplish this goal by (1) applying a rigorous methodology to extend the conventional rate-distortion optimization framework to include the computation term, (2) developing a complexity model that can reliably determine the appropriate parameter (i.e., Lagrange multiplier) needed for optimizing the rate-distortion-complexity tradeoff relationships, and (3) a complexity-control algorithm to meet any specified target complexity level while keeping the complexity as consistent as possible throughout the video sequence. Our method can be applied to any existing H.264 encoder system and is compatible with any standard-compliant decoder. Our extensive experiments with different video contents, bit rates, and complexity levels show very promising results in reducing the number of interpolation by up to 60% while keeping the video quality almost intact (quality difference less than 0.2dB). Since the interpolation operation constitutes the largest computational cost component at the decoder, our results have great potential for reducing the power consumption in any practical video decoding systems using the latest video coding standard such as MPEG-4, H.264 and Motion Compensated Embedded Zero Block Coding (MC-EZBC) %U http://www.ee.columbia.edu/dvmm/publications/05/ywang_TECH05_CAMED.pdf %D 2005