1.

Introduction

Compared with the other existing video coding standards, the H.264/AVC standard achieves a significant improvement in compression performance.¹ 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.² 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.

2.

Proposed Intra Prediction Algorithm

In this letter, we focus on the intra prediction algorithm adopted in the latest video coding standard H.264/AVC.³ 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\times 4$ blocks and four prediction modes for $16\times 16\mathrm{MBs}$ . In addition, nine prediction modes for $8\times 8$ blocks have been added as part of the fidelity range extension (FRExt) of the standard.

Let $B_{i,j}$ be the current MB to be coded, where $i$ and $j$ are the coordinates in horizontal and vertical directions, respectively. Figure 1 shows $B_{i,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

$B_{i,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.⁴ The trade-off between the rate and distortion can be optimized using the Lagrangian method.⁵ The optimal DV $m_{i,j}$ for $B_{i,j}$ is selected by minimizing the Lagrangian functional

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 $m_{i,j}^p$ be the predicted DV for $m_{i,j}$ . In the proposed method, $m_{i,j}^p$ is set to the median value of the neighboring DVs as follows:

3.

Implementation

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 $\mathit{DV}̱\mathit{\text{flag}}$ indicating whether the DV is coded $(DV̱\mathit{\text{flag}}=1)$ or not $(DV̱\mathit{\text{flag}}=0)$ . At the decoder, the following parsing process is performed:

In order to improve the coding efficiency further, the proposed algorithm estimates the DV in the search range, including the unreconstructed MBs, $B_{i,j}$ and $B_{i+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̱\mathit{\text{flag}}=1$ , the decoder interpolates the pixels in $B_{i,j}$ used for the DV estimation based on the coded intra prediction mode. As shown in Fig. 2, the pixels in $B_{i+1,j}$ are obtained by simply copying the pixels in the last row of $B_{i+1,j-1}$ .

4.

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 $30\mathrm{fps}$ . 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 $\mathrm{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.

5.

Conclusion

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.