1.

Introduction

Discrete cosine transform (DCT) and discrete wavelet transform (DWT) used in image compression are implemented by separable 1-D transforms in the rows and columns of images. The major shortcoming of the separable transform is that it cannot represent the anisotropic edges in the image sparsely. Recently, various lifting-based directional transforms^{1, 2, 3} are proposed to overcome the problem. In the traditional lifting scheme, the transform matrix is factorized into elementary matrices, which correspond to the operation of adding a multiple of a row/column to another row/column, and the augend and the addend must be in the same column/row.^{4, 5} While in the directional lifting transform, lifting steps can be performed along edges with any directions; thus, it can approximate edges better and represent images more sparsely (see Fig. 1).

Fig. 1

Exemplified elementary matrix operation: (a) nondirectional and (b) directional, where the circles are the pixels and squares are half-pixels.

However, it is noted that to transform along edges with arbitrary directions, the fractional pixels are used in adaptive directional lifting and the their values are interpolated from neighboring integer pixels. Denote the number of taps of the interpolation filter as $L$ , then the computation of direction transform is about $L$ times higher than the original one.^{1, 2} The high computation cost is a serious drawback in practice, especially for DCT, which has various faster approximations⁶ that are quite suitable to portable devices and real-time processing, such as satellite onboard image compression. In this letter, we proposed a fast directional DCT (FDDCT) without interpolation. Compared to the original lifting-based directional DCT (DDCT),² the computation of FDDCT decreases by 80%, and the peak signal-to-noise ratios (PSNR) of compressed images are higher.

2.

Proposed FDDCT

2.1.

Direction Modes without Interpolation

It is known that, in DDCT, interpolation on the fractional pixels is the main reason that causes large amounts of computation. If we can use only the integer pixels to approximate edges, then interpolation will be avoided. In this paper, we propose to use five direction modes to achieve this. These modes are shown in Fig. 2, where no fractional pixels exist and the size of transform matrix is $8\times 8$ . The corresponding directional angles are form $-45\mathrm{deg}$ [mode (a), see Fig. 2] to $45\mathrm{deg}$ [mode (e), see Fig. 2].

Fig. 2

Five direction modes in row FDDCT. The circles are integer pixels, and the dashed lines are direction lines.

These direction modes are like the prediction modes used in the intraprediction process in the recent video-coding standard H.264.⁷ For example, modes (a) and (b) correspond to the diagonal down-right and the vertical-right prediction in H.264, separately, and the only difference is that polylines are used to avoid interpolating in our modes. It also find that five modes are enough to approximate well most directions of edges in images.^{1, 2} Supposing that the direction modes of all blocks are selected, the transform can be performed along the direction lines defined in the direction modes (see Fig. 3), and the pixels on the direction line are all integer ones.

Fig. 3

Direction line across blocks.

3.

Simulation Results

Extensive experiments have been conducted to evaluate the performance of FDDCT. We report the experimental results of four common gray images: Lena, Barbara, Boat, and Photographer, which have different characteristics. FDDCT is compared to DCT and DWT (CDF9/7 used in JPEG2000) and DDCT in our experiments. The set partition coding developed by us in Ref. 8 is used to code the coefficients of FDDCT, DCT, and DWT, which is suitable for both the block transform and the subband transform. The direction mode of a block is first predicted from the coded modes of coded neighboring blocks and then is coded by the arithmetic coding.

Figure 4 shows that PSNRs of images compressed with FDDCT are close to those with DWT. And compared to DCT, the coding gain of FDDCT ranges from $0.4\text{to}1.5\mathrm{dB}$ . The compression results of DDCT-based method in Ref. 2 are also given in Fig. 4, whose PSNRs are $>1\mathrm{dB}$ lower than the proposed FDDCT based one. The decompressed Barbara is partly shown in Fig. 5. It shows that the edges in the image compressed by FDDCT are less disturbed, and the block artifacts are nearly eliminated by FDDCT. The reason should be that, in FDDCT, many direction lines are extended to the adjacent blocks; thus, the blocks are not transformed individually. It is helpful to reduce block artifacts in the compressed images.

Fig. 4

PSNR versus bit-rate curves of different transforms.

Fig. 5

Parts of Barbara compressed with DCT and FDDCT (bit rate: $0.5\text{bits}∕\text{pixel}$ ): (a) is compressed with DCT and (b) is compressed with FDDCT.

Finally, we give the computational complexity of FDDCT. If the direction modes of all blocks in the image are same, then no special lifting steps are needed; thus, the computation of FDDCT is the same as that of DCT. But, in practice, different blocks generally have different direction modes. As a result, the computation depends on the edges in the image. In other words, the computation of FDDCT is image dependent.

Here, we perform several transforms on many standard gray-scale images on a $2.93\text{-}\mathrm{GHz}$ Pentium IV. The average executing times of DCT, DWT, and FDDCT are given in Table 1. It shows that the time of FDDCT is in direct proportion to the size of the image, which is $\sim 1.4$ times than that of DCT and one-third of DWT. Comparing to DDCT, whose computation is eight times than that of DCT (eight-tap interpolation is used), the computation decreases by $\sim 80\mathrm{\%}$ .

Table 1

Executing time (second) of different transforms.

4.

Conclusion

By choosing the direction modes consisting of integer pixels, a new directional DCT called FDDCT for image compression is proposed in this paper. Because interpolations in DDCT are avoided, the computation of FDDCT decreases $\sim 80\mathrm{\%}$ compared to original DDCT. Furthermore, the use of interblock information in FDDCT derives less block artifacts and better rate-distortion performance in the compressed images.