Transform-Domain Fast Sum of the Squared Difference Computation for H.264/AVC Rate-Distortion Optimization

In H.264/AVC, the rate-distortion optimization for mode decision plays a significant role to achieve its outstanding performance in terms of both compression efficiency and video quality. However, this mode decision process also introduces extremely high complexity in the encoding process especially the computation of the sum of squared differences (SSD) between the original and reconstructed image blocks. In this paper, fast SSD (FSSD) algorithms are proposed to reduce the complexity of the rate-distortion cost function implementation. The proposed FSSD algorithm is based on the theoretical equivalent of the SSDs in spatial and transform domains and determines the distortion in integer cosine transform domain using an iterative table-lookup quantization process. This approach could avoid the inverse quantization/transform and pixel reconstructions processes with nearly no rate-distortion performance degradation. In addition, the FSSD can also be used with efficient bit rate estimation algorithms to further reduce the cost function complexity. Experimental results show that the new FSSD can save up to 15% of total encoding time with less than 0.1% coding performance degradation and it can save up to 30% with ignorable performance degradation when combining with conventional bit rate estimation algorithm