Computation reduction for intra 4x4 mode decision with SATD criterion in H.264/AVC

In H.264 advanced video coding standard, the intra prediction made by referring to the surrounding coded pixels plays an important role in achieving the compression efficiency. To find the best prediction mode, the H.264 reference software JM 6. 1 d suggests two criteria, the sum of absolute differences (SAD) and the sum of absolute transformed differences (SATD). The SATD criterion with extra Hadamard transform achieves better coding performance, but needs more computation than the SAD criterion. A fast algorithm is developed to reduce the computation of the SATD, by using the property of linear transform and the fixed-spatial relationship of predicted pixels in each intra mode. With the fast SATD computation, about 50% computation of the original SATD algorithm can be reduced. To further reduce the SATD computation, a two-stage simplified SATD method is proposed, which first uses the SAD criterion to eliminate some unwanted modes and then performs the fast SATD computation to select the best mode. Experimental results show that the proposed two-stage simplified SATD method can save about 70% of computation costs with negligible PSNR loss for H.264 intra prediction.