1 March 2009 Estimation-based intra prediction algorithm for H.264/AVC
Author Affiliations +
We propose a new intra prediction algorithm that can improve the coding efficiency of the H.264/AVC standard. In the proposed algorithm, the prediction signal for each macroblock (MB) is formed by using all the previously reconstructed pixels of the current frame. Experimental results show that the proposed algorithm can reduce the bit rate by 1.36% to 9.07%, as compared with the conventional intra prediction, while the average PSNR is not decreased.
Park and Ko: Estimation-based intra prediction algorithm for H.264/AVC



Compared with the other existing video coding standards, the H.264/AVC standard achieves a significant improvement in compression performance.1 Its high coding efficiency is made possible by new advanced coding tools such as variable block size motion estimation (ME), multiple reference frames, quarter-pixel accuracy ME, and intra prediction. Among these, we focus on the intra prediction in the H.264/AVC standard. The basic concept of the intra prediction is to reduce the number of coded bits by exploiting the spatial correlation between adjacent macroblocks (MBs). When an MB is coded in the intra mode, a prediction signal is formed by using neighboring pixels in the upper and/or left MBs. Intra prediction is used to prevent error propagation, provide random access, and support a real-time streaming service.2 However, it is well known that the number of bits generated by intra prediction is much larger than that generated by inter prediction. In this letter, in order to enhance the coding efficiency of intra prediction, we propose an improved intra prediction algorithm. The proposed algorithm searches for the prediction signal for each MB by using all the previously reconstructed pixels of the current frame. The experimental results show that the proposed algorithm can reduce the bit rate by 1.36% to 9.07% depending on the video sequence.


Proposed Intra Prediction Algorithm

In this letter, we focus on the intra prediction algorithm adopted in the latest video coding standard H.264/AVC.3 The proposed algorithm can be easily applied to other video coding standards, including H.263 and MPEG-2. The H.264/AVC standards offers a rich set of prediction patterns for intra prediction, i.e., nine prediction modes for 4×4 blocks and four prediction modes for 16×16MBs . In addition, nine prediction modes for 8×8 blocks have been added as part of the fidelity range extension (FRExt) of the standard.

Let Bi,j be the current MB to be coded, where i and j are the coordinates in horizontal and vertical directions, respectively. Figure 1 shows Bi,j and its neighboring MBs. In H.264/AVC intra prediction, only a small number of adjacent pixels are used to construct the prediction signal (see Fig. 1). Thus, in general, the prediction signal generated by intra prediction is not well matched to the original signal, and a large number of bits are required for encoding the difference between the prediction and original signals. Note that, at the time when the current MB is encoded, all pixels of the preceding MBs in the raster scan order have been already reconstructed. Thus, the current MB can be more precisely predicted by utilizing the reconstructed pixels of the preceding MBs. We propose an estimation-based intra prediction algorithm to generate the prediction signal for intra MB. In the proposed algorithm, the best matching position of the current MB is searched in the previously reconstructed part of the current frame. Our proposed algorithm provides a displacement vector (DV) indicating the best matching position with the minimum prediction error. Figure 2 shows the proposed intra prediction algorithm using the DV.

Fig. 1

Bi,j and its neighboring MBs.


Fig. 2

Proposed intra prediction algorithm.


The use of the DV can reduce the number of bits required for the prediction error, but it causes additional overhead.4 The trade-off between the rate and distortion can be optimized using the Lagrangian method.5 The optimal DV mi,j for Bi,j is selected by minimizing the Lagrangian functional


where M is the DV search range, and λDV is the Lagrange parameter. The rate RDV(Bi,j,m) specifies the number of bits required for encoding the DV. Let mx and my be the components of the DV mi,j along the x and y axes, respectively. Then, corresponding to mi,j=(mx,my) , the distortion DDV(Bi,j,m) is calculated as


where p=1 for the sum of absolute difference (SAD), and p=2 for the sum of squared differnece (SSD). Note that in Eq. 2, the computation complexity of the proposed method is almost the same as that of the motion estimation for a 16×16MB .

From our simulation, we found that the DV of the current MB is correlated with those of neighboring MBs. Thus, instead of the original DV, we encode the difference between the original DV and the predicted one. Let mi,jp be the predicted DV for mi,j . In the proposed method, mi,jp is set to the median value of the neighboring DVs as follows:





The proposed method requires minor modification of the syntax of the H.264/AVC standard. When an MB is coded in intra mode, we add to the syntax a flag DV̱flag indicating whether the DV is coded (DV̱flag=1) or not (DV̱flag=0) . At the decoder, the following parsing process is performed:

  • If DV̱flag=0 , the decoder skips the parsing process for the DV. In this case, the MB is reconstructed based on the conventional intra prediction in H.264/AVC.

  • If DV̱flag=1 , the decoder parses the DV and constructs a prediction signal by using the proposed algorithm. The decoded residual data is added to the resultant prediction signal.

In order to improve the coding efficiency further, the proposed algorithm estimates the DV in the search range, including the unreconstructed MBs, Bi,j and Bi+1,j , as well as the previously reconstructed MBs (see Fig. 2). In the proposed algorithm, since there is no modification in the syntax of the standard except the DV and its corresponding flag, the intra prediction mode is always encoded regardless of the usage of the proposed algorithm. Thus, if DV̱flag=1 , the decoder interpolates the pixels in Bi,j used for the DV estimation based on the coded intra prediction mode. As shown in Fig. 2, the pixels in Bi+1,j are obtained by simply copying the pixels in the last row of Bi+1,j1 .


Experimental Results

For our experiments, we used Joint Scalable Video Model (JSVM) 8.7 reference software. We used three test sequences, Foreman, Crew, and Table, with CIF at 30fps . These test sequences have different characteristics. The DV search range is set to 32, and all frames were coded in the intra mode. We calculated the average bit rate and PSNR for the video sequences of 200 frames. The CAVLC entropy coding method was used in our experiments.

We compare the proposed intra prediction algorithm with the conventional one in the H.264/AVC using several quantization parameters (QPs). In Table 1, the Foreman sequence produces a higher bit saving than Crew and Table since the number of bits required for encoding the prediction error is smaller than that of the other sequences. The bit rate saving of Foreman is up to 9.07%, with QP=44 . It can be seen that the proposed intra prediction algorithm shows better performance at low bit rates with negligible visual degradation. To show the results clearly, the rate-distortion curves for the Foreman sequence are presented in Fig. 3. As shown in Fig. 3, the proposed algorithm outperforms the conventional one in terms of the rate-distortion sense.

Fig. 3

Rate-distortion curves for the Foreman sequence.


Table 1

Performance comparison of the conventional and proposed algorithms.

Bit rate(kbits/s)PSNR(dB)Saving(%)Bit rate(kbits/s)PSNR(dB)Saving(%)Bit rate(kbits/s)PSNR(dB)Saving(%)



In this letter, we proposed a new intra prediction algorithm that can improve the coding efficiency of existing video coding standards including H.264/AVC. For each MB, our proposed algorithm provides the DV that indicates the best matching position in the previously reconstructed part of the current frame. The proposed algorithm can be easily implemented by adding a single flag to the syntax of existing video coding standards.


This research was supported by Seoul Future Contents Convergence (SFCC) Cluster established by Seoul R&BD Program.


1.  T. Wiegand, G. J. Sullivan, G. Bjontegaard, and A. Luthra, “Overview of the H.264/AVC video coding standard,” IEEE Trans. Circuits Syst. Video Technol.1051-8215 10.1109/TCSVT.2003.815165 13, 560–576 (2003). Google Scholar

2.  Y. L. Lee, K. H. Han, and G. J. Sullivan, “Improved lossless intra coding for H.264/MPEG-4 AVC,” IEEE Trans. Image Process.1057-7149 15, 2610–2616 (2006). Google Scholar

3. ITU-T and ISO/IEC JTC1, “Advanced video coding for generic audio-visual services,” ITU-T Recommendation H.264 and ISO/IEC 14496–10 (MPEG4-AVC), Version 4 (2005). Google Scholar

4.  C. S. Park, C. K. Park, and S. J. Ko, “Generalization of interlayer intra prediction for scalable video coding,” Electron. Lett.0013-5194 10.1049/el:20083114 44, 337–338 (2008). Google Scholar

5.  G. J. Sullivan and T. Wiegand, “Rate-distortion optimization for video compression,” IEEE Signal Process. Mag.1053-5888 10.1109/79.733497 15, 74–90 (1998). Google Scholar

© (2009) Society of Photo-Optical Instrumentation Engineers (SPIE)
Chun-Su Park, Sung-Jea Ko, "Estimation-based intra prediction algorithm for H.264/AVC," Optical Engineering 48(3), 030506 (1 March 2009). https://doi.org/10.1117/1.3101375 . Submission:

Back to Top