IEEE TRANSACTIONS ON MULTIMEDIA, VOL. 16, NO. 4, JUNE 2014933

Efficient H.264/AVC Video Codingwith Adaptive Transforms
Miaohui Wang, Student Member, IEEE, King Ngi Ngan, Fellow, IEEE, and Long Xu, Member, IEEE

Abstract—Transform has been widely used to remove spatial
redundancy of prediction residuals in the modern video coding
standards. However, since the residual blocks exhibit diverse
characteristics in a video sequence, conventional transform
methods with fixed transform kernels may result in low efficiency.
To tackle this problem, we propose a novel content adaptive
transform framework for the H.264/AVC-based video coding.
The proposed method utilizes pixel rearrangement to dynamicallyadjust the transform kernels to adapt to the video content. In
addition, unlike the traditional adaptive transforms, the proposed
method obtains the transform kernels from the reconstructed
block, and hence it consumes only one logic indicator for eachtransform unit. Moreover, a spiral-scanning method is developed
to reorder the transform coefficients for better entropy coding.
Experimental results on the Key Technical Area (KTA) platform
show that the proposed method can achieve an average bitrate
reduction of about 7.95% and 7.0% under all-intra and low-delay
configurations, respectively.
Index Terms—Video coding, transform coding, 2D separable
Karhunen-Loève transform, H.264/AVC.

I. INTRODUCTIONI

N A video sequence, the frames contain both temporally
and spatially redundant information. The temporal redundancy is usually removed by motion estimation (ME) and motion compensation (MC), while the spatial redundancy is removed by color space conversion [1], predictive coding [2]–[4]or transform coding [5]. The efficiency of transform coding isdue to the fact that most of the block energy is compacted into
only a few transform coefficients in the frequency domain. In
H.264/AVC transform coding, a 2D separable discrete cosine
transform (DCT) (or more precisely integer cosine transform(ICT) [6]) is used to decorrelate prediction residuals. In addition, the H.264/AVC adopts multiple transform block sizes toimprove the coding performance. For example, in the Key Technical Area (KTA) reference software [7], it supports varioustransform sizes ranging fromtoand its successor

Manuscript received July 25, 2013; revised October 28, 2013 and December
18, 2013; accepted December 20, 2013. Date of publication February 10, 2014;
date of current version May 13, 2014. This work was supported in part by agrant from the Research Grants Council of the Hong Kong SAR, China (Project
CUHK 416010). The associate editor coordinating the review of this manuscript
and approving it for publication was Prof. Ebroul Izquierdo.
The authors are with the Department of Electronic Engineering, The Chinese University of Hong Kong, Hong Kong (e-mail: mhwang@ee.cuhk.edu.hk;
knngan@ee.cuhk.edu.hk; xulong@ee.cuhk.edu.hk).
Color versions of one or more of the figures in this paper are available online
at http://ieeexplore.ieee.org.
Digital Object Identifier 10.1109/TMM.2014.2305579

High Efficiency Video Coding (HEVC) [8] standard supports upto. Due to its high efficiency, the DCT based encoders
have been well developed, including JPEG, H.26x families [9]and AVS families [10].
Theoretically speaking, it is well known that the DCT is
popular due to its energy compaction ability approximating
the Karhunen-Loève transform (KLT) under the assumptionof a first order stationary Markov process and Gaussian distributed source [11]. In practice, the DCT has been consideredas the most suitable transform to replace the KLT for image
compression. In image coding, the separable 2D-DCT achieves
promising performance because of high correlations amongneighboring pixels in a natural image. On the other hand, thecorrelations of prediction residual blocks in the H.264/AVC
may not be high as the natural images. As a result, the DCT
would be unlikely to be the best choice for transform coding
when applied to the low correlation residuals [12], [13]. Thisbelief motivates many transforms that mainly fall into two
categories: fixed transforms and adaptive transforms.
Fixed transform methods are widely studied to replace the
DCT by the alternative transforms. The alternative transformcandidates can be 1D-DCT, discrete sine transform (DST) or
other predefined transform kernels. The advantages of the fixedtransform methods include existing fast algorithms and savingof the overhead bitrate. Zeng et al. [14] proposed the directional
DCT (D-DCT) for image coding, in which the 1D-DCT is performed along a certain pattern in a block. Chang et al. [15]developed the directional adaptive block transform (DA-BT)
for image coding with two key differences comparing with the
D-DCT method: one is the ordering of the transform coefficients and the other is the choice of the transform directions. Ye
et al. [16] proposed the mode-dependent directional transform(MDDT) for the H.264/AVC all-intra coding. In [17]–[19], sinusoidal transforms were proposed to decorrelate the H.264/AVC
residuals based on the observation that the DST outperforms the
DCT when the correlations are very low [5].
Adaptive transform methods have also received growing attention to replace the DCT by the adaptive transform kernels.
The advantage of the adaptive transforms is that it provides
a better energy compaction than the fixed transforms, but thetransform kernels are required to be transmitted to the decoder.
Due to the transmission of the transform kernels, the adaptive
transform methods result in overhead problem. In our previous
works [12] and [13], adaptive transform methods are proposed
for residual coding, in which the transform kernels are computed from the decoded block. In [20], a hybrid singular value
decomposition DCT (HSVD-DCT) method was proposed forstill image compression, where only a few big eigenvalues and1520-9210 © 2014 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission.
See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.

934

IEEE TRANSACTIONS ON MULTIMEDIA, VOL. 16, NO. 4, JUNE 2014

corresponding eigenvectors are transmitted. It should be notedthat vector quantization (VQ) is used to encode these eigenvectors. Lin et al. [21] proposed a 2D-SVD [22] based method forgroup of intra frames (GOP) coding. The transform kernels are
obtained by the 2D-SVD method based on the GOP (GOP)
that are being encoded. Then, these transform kernels are transmitted to the decoder and are used to transform the blocks in
the GOP only. Biswas et al. [23] proposed to transform the MC
residual blocks by the KLT. To save the overhead bitrate, thetransform kernels are computed by shifting and rotating the MC
block.
In this paper, we propose a content adaptive transform (CAT)framework for the H.264/AVC-based video coding. Unlike thetraditional adaptive transform methods, the proposed method
derives the adaptive transform kernels from the reconstructed
block without causing overhead problem, since the decoder cancomputed them in the same way. In addition, based on the studyof the transform coefficient distributions, we propose a spiralscanning method to reorder the quantized coefficients before
run-length-coding (RLC) and entropy coding. Extensive experimental results show that the proposed method is able to achieve
higher PSNR gain than state-of-the-art methods in the H.264/
AVC-based video coding.
The rest of the paper is organized as follows. We briefly introduce the related works in Section II. The proposed method
is then presented in Section III. The efficiency of the proposed
method is analyzed in Section IV. The simulation results arepresented in Section V and concluding remarks are given in
Section VI.
II. RELATED WORKS IN THE H.264/AVC
In this section, we review three classes of state-of-the-art
transform methods in detail: (1) directional transform methods,(2) adaptive DCT/DST methods and (3) secondary transform
methods. It should be pointed out that all of them is proposed to
improve the H.264/AVC coding performance.
A. Directional Transform Methods
In H.264/AVC, directional intra predictions have been used
to remove the spatial redundancies. As shown in Fig. 1, theresidual samples are collected in a H.264/AVC
intra-coding
experiment, where the black pixel indicates a small prediction
error and the white one indicates a large error. The prediction
errors in columns or rows will produce directional edges. For
example, in Mode 0 and Mode 1, it shows some horizontal andvertical edges, respectively. For Mode 3, diagonal-down rightedges can be easily observed, and similarly for other modes. It
is evident that the prediction residuals exhibit different statistical characteristics resulting from different prediction modes.
Based on this observation, Ye et al. [16] proposed a mode-dependent directional transform (MDDT) method for intra prediction residuals coding. It is known that the directional transformis derived from the non-separable KLT. However, the non-separable KLT entails higher complexity and larger storage space.
Therefore, the non-separable KLT is replaced by the separable
directional transforms [16]:(1)Fig. 1. Normalized magnitudes of the directional prediction residuals in theblock intra-coding.

where
denotes the transform coefficients in mode .
isthe input intra residual block.
andare the transformbasis trained off-line on a large prediction data set. Detail of the
training process can be referred to [24]. Note that the DCT isused when the prediction mode is DC (i.e.,).
There are a lot of efforts spent in the directional transforms
during the past years. Cohen et al. [25] proposed a direction
adaptive residual transform method in which several 1D transforms were employed along each direction and only the DC coefficients were further processed by the DCT. Sezer et al. [26]used -norm regularized optimization method as a more robust way to learn the 2D separable sparse transforms for the
directional residual coding. As mentioned above, the MDDT
method took only one specific transform basis for each prediction mode, so it might not give full play to its ability for intra
residual coding. From this perspective, Zhao et al. [24] extended
one basis to multiple bases. To choose the best transform basis,the rate distortion optimization (RDO) tool was used. For example, the RDO based transform (RDOT) [24] method used 16
kernels for an
block in each prediction mode.
B. Adaptive DCT/DST Methods
Based on the analysis of the intra prediction residuals, DST
type-VII [18], [19] has been proposed to encode the directional
intra residuals. Yeo et al. [19] proposed a mode-dependent fast
separable KLT (MDFT) method that has similar coding performance as compared with the MDDT method but requires nooff-line training. In the MDFT method, the statistics of intra prediction residuals were studied and mode-dependent separable
KLT transform kernels were employed for the all-intra coding:(2)
Based on the covariance models for various prediction residuals,
Yeo et al. [19] also proposed to use the traditional DCT basis forWANG et al.: EFFICIENT H.264/AVC VIDEO CODING WITH ADAPTIVE TRANSFORMS

935

CAT model can also be derived in parallel for motion compensation residual coding.

TABLE ICHOICE OF THE KLT/DCT IN THE MDFT METHOD

A. 2D Separable Karhunen-Loève Transform (KLT)KLT is a data dependent transform, and it has been consideredas the optimum energy compacting transform if only one fixedtransform basis is used for all blocks in an image. When the
input and output block are converted to column vectors
andrespectively,
1D-KLT is well known as a non-separable transform.
(4)

Fig. 2. Flowchart of the two-layer directional transform method.

some prediction modes instead of the MDFT basis (2). The DCT
basis is formulated as:

where
is the transform basis of the 1D-KLT. In practice, we
calculate the eigenvalue decomposition of the covariance matrixof the input to obtain the transform basis. Ifanddenote the covariance matrices of the input vector and output
vector respectively, then we have

(3)

(5)

The transform kernels of the MDFT method are summarized inTable I.
Adaptive DCT/DST methods have been widely studied. Lim
et al. [17] explored the possibilities of using DCT/DST type-II
to decorrelate the MC residuals. Independently, Han et al. [18]analytically derived the DST type-VII along the prediction direction and proposed an asymmetric DST (ADST) method for
all-intra coding. They showed that both the upper and the left
boundaries of the block were available for prediction for the
DC mode, and hence the ADST was used. Otherwise, adaptive ADST/DCT kernels were used for the other modes. Saxena
et al. [27] proposed an improvement of this work that finally
was adopted in recent HEVC standard [8].

is the expectation operator.
where
The 1D-KLT is easy to extend to the 2D case. Suppose that an image consists of
non-overlapping blocks.
The separable 2D-KLT is defined same as (1),, and the only difference is the transform kernels. For example, the vertical transform kernel
is given by:
(6)
where
is computed as the eigenvector of the vertical covariance matrix:

C. Secondary Transform Methods
Secondary transform methods have been developed to
improve the conventional DCT. Alshina et al. [28] used therotational transforms (ROT) as the secondary transform. The
ROT method provided four sets ofandpredefinedtransform kernels for intra residuals. Dong et al. [29] proposeda two-layer directional transform method for the MC residual
coding. As shown in Fig. 2, the Haar-based discrete wavelet
transform (DWT) is employed to quickly compact the block
energy to the LL subband in the first layer. In the second
layer, 2D non-separable directional transforms (DT) are used,
where the transform kernels are off-line trained along the four
directions.
III. PROPOSED ADAPTIVE TRANSFORM
FRAMEWORK FOR VIDEO CODING
This section presents the mathematical foundations behind the proposed method. Firstly, we introduce the content
dependent 2D separable Karhunen-Loève Transform (KLT).
Secondly, based on the flowchart of the H.264/AVC intra
coding, we demonstrate the derivation the content adaptive
transform (CAT) framework. Without loss of generality, the

(7)
where
is a column mean vector of,and. Similarly, thetransform kernel
is computed as the eigenvector of
the horizontal covariance matrix
and. Moreover, it can be derived
that when the 2D separable KLT is defined for a zero-mean
image and computed over only one block , the horizontal andvertical covariance matrices are estimated as:(8)
and in this case, the 2D separable KLT degenerates into the SVD
transform.
From (7), we can conclude that the 2D separable KLT is an
optimal transform for an image but not for a specific block.
However, if the transform kernels satisfy (8), it is an optimaltransform for a block. In the next section, we will introduce theproposed content adaptive transform (CAT) framework that isbased on (7) and (8). The proposed transform kernels of the 2D
separable KLT can be calculated by method [30].

936IEEE TRANSACTIONS ON MULTIMEDIA, VOL. 16, NO. 4, JUNE 2014

Fig. 4. Illustration of the sampling operator.

Fig. 3. Illustration of the proposed content adaptive transform framework.

B. Proposed Content Adaptive Transform Framework (CAT)for Video Coding
In video coding, a frame is first divided into non-overlapping
blocks for predictive coding, and then the transform coding
is performed on each residual block before quantization andentropy coding. To improve the coding performance, theH.264/AVC employs a quad-tree tool to segment the basic
coding unit (e.g., macroblock) based on the rate
distortion optimization (RDO). In addition, the H.264/AVC
also employs directional prediction to find the best residual
block. After the directional prediction, the DCT is employed
to transform the intra residuals. Assuming that the th block
can be transformed as(9)is the transform coefficients;
andare thewhere
horizontal and vertical DCT transform kernels, respectively.
As mentioned above, the training kernels of directional transforms depend on the off-line training methods and the qualityof training data set. Moreover, the training data contains thousands of directional residual blocks, some of which may becontaminated by noise. The off-line trained kernels are thenused to transform the time-varying residuals. As a result, theoff-line trained kernels may not adapt well to the content of

the time-varying residual blocks. Intuitively, adaptive transformkernels may provide a better coding performance than the offline trained ones, since they can be better adapted to the content
of the residual blocks. To obtain the high quality transform kernels, we propose a content adaptive transform (CAT) frameworkfor video coding. As shown in Fig. 3, the CAT framework consists of two crucial components: sampling unit and transformunit. Each part of the CAT framework is discussed in more detail as follows.
In the sampling unit, the down-sampling operator as apre-processing unit is used to rearrange the residual block
into four subsamples,. Correspondingly,
the up-sampling operator as a post-processing unit is used toreconstruct the original blockfrom.
In the CAT framework, the sampling process involves only
shift operations and thus the computational cost is low. The
proposed sampling operator is illustrated in Fig. 4. In thetransform unit, the blockis first forward-transformed,
quantized, dequantized and inverse-transformed as:(10)
andare the transform kernels of the DCT;
is the quantization method in the H.264/AVC;
indicates that each element ofis processed by
H.264/AVC quantization tool, including scaling and rounding
operations.
Based on the block, the separable 2D-KLT is thenused to derive the adaptive transform kernels
and
. For
example, as shown in top-left corner of Fig. 3, the current
input block is the 227th macroblock in the “Foreman (CIF)” sequence, and the residual blockis predicted by intra direction. Transform kernels
andwill be updated as shown in(11) and (12) at the bottom of the next page, where the integers
in the matrix are the approximated coefficients of the integertransform, and the scaling factor
is integrated
into the quantization scheme in the KTA platform. In thiswhere

WANG et al.: EFFICIENT H.264/AVC VIDEO CODING WITH ADAPTIVE TRANSFORMS

case, the proposed adaptive transform avoids the floating-point
arithmetic computation, and hence will not result in the drift
problem [6].
After obtaining the real-time transform kernels
and,the other blocks will be transformed as:

937

The detail of the proposed CAT method is presented in Algois first rerithm 1. In the decoder, the important block
constructed. Then, the other blocks can be reconstructed by repeating the inverse step (13).
Algorithm 1. The Proposed CAT Algorithm(13)
is quantizedand then the transform coefficient blockfor entropy coding.
For the quantization, different
values are designed for thetwo types of blocks, where theis considered as an important block while the other blocks
are considered as ordinary blocks. The reason is that down-sampling
may result in low correlations and require more bitrate to reduce the quantization distortion. As a result, to obtain a highquality, a lowshould be set for the block. Inorder to maintain a macroblock level rate distortion cost [31],a highis set for the blocks. Based onMonte Carlo simulations, we select the following simple but efficient
scheme:Input: The input blockand frame level.

Output: The quantized transform coefficient block.
Begin
1. The traditional DCT part.
1.1 Compute the coefficients of DCT:

1.2 Apply

and

for

to get;1.3 Collect the RD cost. Note that zigzag pattern is usedas scanning table.

(14)
2. The proposed CAT part.
is the macroblock quantization parameter.
where
Finally, the other blocks
are reconstructed by:

2.1 Apply a downsampling operator to the block;

2.2 Compute the coefficients of DCT:
(15)

(11)

(12)

938

IEEE TRANSACTIONS ON MULTIMEDIA, VOL. 16, NO. 4, JUNE 2014

to get

2.3 Apply;,and inverse transform for

2.4 Collect the RD cost. Note that the spiral method is
used.

2.5 Compute the 2D separable KLT transform kernels:

Fig. 5. The first frame of “BQMall” () sequence and its intra prediction residual. The grey color indicates zero residual, the black indicates negative
residual, and the white indicates positive residual. (a) “BQMall”original frame.
(b) “BQMall” intra residue.

2.6 Call proposed transform coding.
For

to getApply;,

and the inverse transform forCollect the RD cost:
Fig. 6. Plot of the Pearson correlations among subsamples of anblock
block is downsampled and correlations are obtained among its(Everyblocks,. (b) Residual
subsamples.) (a) Original
blocks,.

End For2.7 Compute the overall RD cost:

3. The RDO part.
If;

its intra-coding residuals are used in this experiment. Correlation among the subsampled blocks
isvery crucial to the proposed CAT method, which determines theenergy compaction efficiency of the adaptive transform kernels.
Thus, Pearson correlation coefficient (PCC) is used to measure
the strength and the direction of a linear relationship between
two subsampled blocks:
(16)

else
;
End IfEnd
IV. ANALYSIS OF THE CAT FRAMEWORKThis section presents the experimental analysis of the CAT
framework from various aspects. First, we study the correlations among the subsamples. Second, we discuss the proposed
spiral-scanning method for better reordering of the transform
coefficients. Third, experiments are carried out to investigate
the performance of a transform size and transform coding gain.
Finally, we discuss the difference between the proposed method
and the training-based directional transform methods.
A. Correlation Analysis
In this subsection, we analyze the correlations among the subsamples from various block sizes in both the original frame andits intra prediction residual. As shown in Fig. 5, “BQMall” and

where
and
are paired samples. In the statistical perspective, a correlation greater than 0.8 is generally considered to bestrong, whereas a correlation less than 0.5 is generally describedas weak.
Fig. 6 shows the PCCs among theblocks extracted
from anblock by pixel rearrangement (Fig. 4(a)) for boththe original “BQMall” frame and its intra prediction residualas shown in Figs. 5(a) and 5(b) (), respectively. From
Fig. 6, it is easily observed that most of the blocks are on theupper side of the plane with the, which indicatesthat the high correlations indeed exist among the subsampled
pixels in anblock. In addition, the original “BQMall”
frame has stronger correlation compared to its intra prediction
residual. However, the prediction residual blocks with strong
correlations account for 66% of the total. It indicates that for
those subsampled blocks with high correlations, the proposed
separable 2D-KLT kernels can achieve better energy compaction as formulated by (13).
Fig. 7 further shows the PCCs among subsampled blocks ofandblocks, respectively. It can be seen that theWANG et al.: EFFICIENT H.264/AVC VIDEO CODING WITH ADAPTIVE TRANSFORMS

Fig. 7. Plot of the Pearson correlations among subsamples of theblocks, respectively. (a) Original
blocks,, (b) Residual
blocks,, (c) Original
blocks,, (d) Residual
blocks,
.

939

and

Fig. 8. Distributions of the DCT coefficients and the proposed method in a
blocks (only AC coefficients). (a) and (b) are obtained from the original“BQMall” frame. (c) and (d) are obtained from its intra residual.

correlation among the subsamples increases with the transform
block sizes. For example, the PCC results of the original “BQMall” areblock,,
block,
andblock,.
The PCC results of the “BQMall” residual areblock,,
block,
andblock,. In addition, Table IIshows more PCC results of different sequences, where the firstten frames of intra residuals are used in the experiments. One
can see that the larger the transform block size, the higher isthe correlation among the subsamples, hence the higher efficiency of the proposed transform kernels, which can be demonstrated by the experimental results of block selection ratios in
Section IV-C.

Fig. 9. Illustration of the spiral-scanning table. (a) spiral; (b) performance ofthe proposed CAT with/without the spiral-scanning method.

TABLE II
CORRELATIONS OF THE INTRA RESIDUAL BLOCKS (PCC)

are distributed along the diagonal line. Therefore, we propose
a new spiral-scanning method for the CAT algorithm to efficiently reorder the quantized coefficients as shown in Fig. 9(a).
Fig. 9(b) illustrates the simulation results of “BQMall” under
all-intra coding configuration at, where a total 99
frames are used in the experiments and both the PSNR results
are about 41.6 dB. It can be seen that the proposed spiral-scanning method achieves a lower bitrate than the zigzag scanning
method since it is able to extend the zero run-length, thus improving the entropy coding efficiency.

B. Spiral-Scanning Table

C. Transform Block Size and Block Selection Ratio

In this subsection, we study the distributions of transform coefficients produced by (13). The original “BQMall” frame andits residuals are encoded by the proposed CAT algorithm, andexperimental results for the AC coefficients of the first macroblock are shown in Fig. 8. As shown in Figs. 8(b) and (d), it
can be seen that the proposed method has a better energy compaction performance than that of the DCT. Furthermore, we observed that transform coefficients of the proposed method (13)To show the effectiveness of the proposed CAT framework,
we investigate the selection ratio of a transform block size under
all-intra coding configuration in this subsection. The experimental conditions are the same as in Section V, and the selection
ratio is computed as:
(17)

940

IEEE TRANSACTIONS ON MULTIMEDIA, VOL. 16, NO. 4, JUNE 2014

TABLE IIICOMPARISON RESULTS OF DIFFERENT TRANSFORM BLOCK SIZE UNDER ALL-INTRA CODING CONFIGURATION (Fig. 10. The selection ratio for a transform block size. (a)whereis the number ofblocks codedby proposed method;is the total number ofblocks.
As shown in Fig. 3, the proposed CAT framework is implemented in the KTA intra encoder. According to the quad-tree
based parsing process, the proposed method involves two transform block sizes, i.e.,and. The reason is that thesmall blocks (i.e.,) may cost too many overhead bits. Furthermore, the correlations among the subsamples of theblocks make it not worthwhile to compute the adaptive transform kernels.
Table III shows the performance of the proposed method for
two transform block sizes. It can be seen that good coding performance is achieved for all test sequences. For example, anaverage 0.67 dB Bjontegaard-Delta PSNR (BD-PSNR) for theblocks and 0.40 dB BD-PSNR for theblocksare achieved, respectively. BD-PSNR is derived from simulation results with various. For sequenceswith rich textures, like “Coastguard” and “Mobile”, the proposed method is able to achieve very high coding gain.
In Fig. 10, four sequences with different resolutions are used
to evaluate the usage of our method for various block sizes. It
should be pointed out that the proposed method is evaluated at
the optimal rate distortion (RD) condition. As shown in Fig. 10,high selection ratio is achieved at higher bitrate. The results support ourscheme (14) in Section III-B, where high quality
can be used to derive better transform kernels. In addition,high selection ratio for the big transform blocks can also be observed in Fig. 10(a) and 10(b). It can be seen that the selection
ratio ofis higher than that ofin most cases (e.g.,; (b), 27, 32, 37).

Fig. 11. Coding gain comparison of the DCT and the proposed method.

13/16). The reason is that the correlation among subsamples ofis higher than that of, which indicates better transform kernels can be derived.
D. Coding Gain Analysis
The transform coding gain is considered as a benchmark tomeasure the transform performance. It is usually defined as theratio of the arithmetic mean of variances of the transform coefficients and the geometric mean of the variances:(18)

WANG et al.: EFFICIENT H.264/AVC VIDEO CODING WITH ADAPTIVE TRANSFORMS

941

Fig. 12. Comparison of the transform coefficients between the DCT (H.264/AVC) and the proposed method. The most left encoding block is the 29th Macroblock(MB) in the first frame of the “Foreman (CIF)” sequence, and the current predictive residual block are shown in the right-hand side; (a) is the result of the DCT); (b) is the results of the proposed CAT (
).
(

where
is the variance of the th transform coefficient; andis the total number of the transform coefficients.
In the 2D case, the variances of each transform coefficient are
defined as:

Fig. 13. Comparison of the proposed method and training based methods.

(19)
is the expectation operator. Furthermore, for diswhere
crete-time stationary Markov-1 signals, a separable 2D auto-covariance model is given by:(20)
Using this separable model, the 2D-DCT can be derived as theandapproaches 1,
vertical and horizontal correlations
respectively.
In Fig. 11, we show the average transform coding gain of the
proposed method under all-intra configuration. It can be seenthat the proposed CAT outperforms the H.264/AVC. In addition, it is observed that the average transform coding gains of
the proposed method decreases as the frame resolution changes
from
to
.
Fig. 12 shows a further coding gain comparison between the
H.264/AVC and the proposed method in an intra coding experiment. The input residual block is from the 29th macroblockof the “Foreman(CIF)” sequence with the intra direction. As shown in Fig. 12(a), it is observed thatthe DCT coefficients are sparsely distributed from the low
frequencies to the high frequencies. In comparison with the
H.264/AVC, the proposed method is shown in Fig. 12(b), where
blocks with four different colors denote the quantizedtransform coefficients of, respectively. One can see that the proposed method outperforms the
H.264/AVC in terms of less coefficients and hence distortion.

E. Comparison of the Proposed Method and the Directional
Transform Methods
Fig. 13 shows the comparison between the proposed method
and training-based directional transforms [16], [24], [29]. For
the directional transform methods, the transform kernels are
off-line trained on a large residual data set. In this situation, directional transforms can be considered as a separable 2D-KLTwith a super-largein (7). Bear in mind that all of theseprocesses are completed off-line and the transform kernels
are used for different video sequences. In comparison withthe directional transforms, the proposed CAT method obtains
the transform kernels adaptively from the reconstructed block.
As shown in Fig. 13, the CAT method derives the transformkernelsfrom the block. Due to a relatively highcorrelation between blockand the other three blocks(,
and), the transform kernels
havesuperior energy compaction capability when applied to theother three blocks.
F. Additional Syntax
For eachblock, aflag is used to notify
whether the proposed method is used. In addition, code block
pattern (CBP) is used to indicate whether non-zero coefficientsare sent, and CABAC entropy coding method is used to collect
the total bitrate consumption. For example, the overhead bitrateis about 0.2% for “BQMall” and 0.19% for “Container” (seeFig. 14).

942

IEEE TRANSACTIONS ON MULTIMEDIA, VOL. 16, NO. 4, JUNE 2014

B. Comparison of Block Selections
Fig. 14 shows two examples of the distributions of blocks encoded by the proposed CAT method. Figs. 14(a) and 14(b) are
the original frames of the “BQMall” () and “Container” (), respectively. Figs. 14(c) and 14(d) show
the blocks encoded by the proposed method, where the green
blocks are encoded by the CAT method and the grey blocks are
encoded by the H.264/AVC at. One can see that theblocks with rich textures are frequently encoded using the proposed method.
C. Bjontegaard-Delta Metric Results in the All-Intra
Configuration

Fig. 14. Illustration of block selections under the all-intra configuration.
; (b) “Container”; (c) “BQMall” coded by(a) “BQMall”
the proposed method; (d) “Container” coded by the proposed method; Green
blocks are coded by our method and grey blocks are coded the H.264/AVC.

TABLE IVTEST CONDITIONS

V. EXPERIMENTAL RESULTS
A. Test Conditions
In this section, we evaluate the performance of the proposed
method against the state-of-the-art methods in the H.264/AVC
framework. The proposed method is implemented on the KTA
reference software (JM 11.0 KTA2.6r1) [7] and Table IV gives
the general test conditions. In the experiments, the transform
block sizes are set as
and. There are a totalof 41 standard sequences of different resolutions, including
CIF, W/WQ-VGA, 720p and 1080p. The experiments are
conducted on a dual-core (i3-2100@3.10 GHz) workstation
with RAM 4 GB that is also used to measure the computational complexity of the proposed method. We measure theperformance by the Bjontegaard-Delta Bit Rate (BD-BR) andthe Bjontegaard-Delta PSNR (BD-PSNR) metrics [32]. These
metrics give the average performance differences between
the H.264/AVC and proposed methods. Note that positive
BD-PSNR indicates PSNR improvement while negative
BD-BR indicates bit rate reduction. The proposed method iscompared with several state-of-the-art methods, including Ye’s
method [16], Lim’s [17], Yeo’s method [19], Biswas’s [23],Zhao’s [24] and Dong’s [29] in terms of the above metrics.

Table V shows the coding performance of the proposed
method and other state-of-the-art methods under all-intra configuration. Bold number indicates the best method and if there
is no bold number in a row, it means the H.264/AVC is thebest one. From Table V, it can be observed that the proposed
method achieves 38 best results from 41 cases. In addition,
it can be seen that our method can achieve significant coding
gains ranging from 0.76% to 13.61%. This means that to get
the same PSNR, our method can save up to 13.61% bitratecompared to the H.264/AVC high profile.
From Table V, comparing to H.264/AVC, Ye’s method [16]achieves about 0.22 dB gain of BD-PSNR or 3.72% reduction of
BD-BR on average, Yeo’s method [19] achieves about 0.15 dB
gain of BD-PSNR or 2.79% reduction of BD-BR on average,
while our method achieves about 0.55 dB gain of BD-PSNR
or 7.95% reduction of BD-BR on average. Based on the above
analysis, it can be concluded that the proposed CAT method
outperforms the best currently available methods under the allintra configuration.
D. Bjontegaard-Delta Metric Results in the Low-Delay
Configuration
In this subsection, we extended the proposed content adaptive transform framework to the motion compensation (MC)residual coding. In the low-delay configuration, we compare theproposed method with Lim’s [17] and Dong’s [29] method. In
the experimental results, the test condition is set as in [29] forfair comparison.
Table VI shows the comparison results between the
H.264/AVC and the best currently available methods under
the low-delay configuration. Compared to the H.264/AVC,
Dong’s method [29] achieves about 0.17 dB gain of BD-PSNR
or 5.62% reduction of BD-BR on average, while the proposed
method achieves an average 0.34 dB gain of BD-PSNR or
7.0% reduction of BD-BR. On the other hand, Lim’s method[17] shows little coding gain.
Finally, the computational complexities of the three methods
are summarized as follows. The complexity of Lim’s method[17], the proposed method and Dong’s method [29] are about
105%, 110% and 123% respectively, as compared to the H.264/
AVC. From Table VI, one can see that the proposed CAT method
is able to achieve slightly better or comparable performancecomparing with state-of-the-art methods under the low-delay
configuration.

WANG et al.: EFFICIENT H.264/AVC VIDEO CODING WITH ADAPTIVE TRANSFORMS

943

TABLE VPERFORMANCE COMPARISON BETWEEN THE PROPOSED METHOD AND STATE-OF-THE-ART METHODS UNDER THE ALL-INTRA CONFIGURATIONTABLE VIPERFORMANCE COMPARISON BETWEEN THE PROPOSED METHOD AND STATE-OF-THE-ART METHODS UNDER THE LOW-DELAY CONFIGURATION

E. Rate Distortion Plot and Visual Quality
Fig. 15 and Fig. 16 show the rate distortion (RD) curves
under the all-intra and low-delay configurations, respectively.
The x-axis is the average bitrate of each method at. Correspondingly, y-axis is the average PSNR
at each. Since RD curves directly show the coding performance over the entire
range, several best available methods
are evaluated, such as Ye’s method [16], Lim’s [17], Yeo’s [19],Biswas’s [23], Zhao’s [24] and Dong’s [29]. From Fig. 15 andFig. 16, it can be observed that the H.264/AVC gives the lowest
coding gain whereas the CAT method achieves better or comparable results as compared to the others. By taking the RD curvesof the H.264/AVC as the benchmark, it can be seen that the proposed method can significantly improve the coding efficiency
under the all-intra and low-delay configurations.
Fig. 17 shows the visual quality results of the “Foreman(CIF)” sequence under the all-intra coding configuration on

944IEEE TRANSACTIONS ON MULTIMEDIA, VOL. 16, NO. 4, JUNE 2014

TABLE VIICOMPUTATIONAL COMPLEXITY OF THE ENCODERTABLE VIIICOMPUTATIONAL COMPLEXITY OF THE DECODER

Fig. 15. Rate distortion curves under the all-intra configuration.

F. Computational Complexity

Fig. 16. Rate distortion curves under the low-delay configuration.

the KTA platform. The first column shows the result of the
H.264/AVC and its cropped region of about
zoom forreference, respectively. Correspondingly, the second and thirdcolumns show the results of Ye’s method [16] and Yeo’s [19],respectively. For comparison, the subjective performance ofour method is shown in the fourth column. As shown in Fig. 17,
there are visible differences in some regions of the decodedframe although the improvements are not obvious. For example,
in Fig. 17(d), the texture in the red rectangle is visually more
pleasing than those of Figs. 17(a), 17(b) and 17(c). Zoom-in
parts are shown in Figs. 17(e), 17(f), 17(g) and 17(h).

In H.264/AVC, the complexity is mainly from rate distortion optimization (RDO) process that is used to choose the bestcoding modes. Since the proposed method is implemented in
the quad-tree structures of the KTA encoder, the additional complexity is increased in the encoder. The additional complexity ismainly from deriving the separable 2D-KLT transform kernels,
and we define that one KLT operation denotes the operations ofaddition, subtraction, multiplication or division for calculatingtransform kernels [30] once. When the RDO tool is on, the additional complexity is relatively high in the encoder. However, it
is worth noting that we only need to calculate transform kernels
for anblock when an input block is, and thedecoder complexity will only be one operation because mode
selection is only carried out in the encoder.
The complexity of the proposed method consists of two parts:(1) calculating the transform kernels and (2) calculating thetransform coefficients of the separable 2D-KLT (13). In general, when the input block is(), the operations
are: (1) calculating the transform kernels =, and (2) calculating the transform coefficients =. Thus, the total operation for the proposed method
is.
Table VII summarizes the average encoding time. It can beseen that the encoding complexity of the proposed method isabout twice that of the H.264/AVC. It is also observed that the
proposed method is more complex than Ye’s [16] and Yeo’s[19]. It is clear that the additional complexity is from the operations of updating the adaptive transform kernels. In addition,
Table VIII shows the complexity of the proposed method in
the decoder side. The average decoding complexity of the proposed method compared to the KTA decoder is 108% under the
all-intra configuration. One can see that the proposed method
can be efficiently used in video coding because the increased
execution time is acceptable (e.g., 120% in the encoder and 8%
in the decoder).

WANG et al.: EFFICIENT H.264/AVC VIDEO CODING WITH ADAPTIVE TRANSFORMS

945

Fig. 17. Subjective coding performance comparison of the first frame in “Foreman (CIF)”. (a) is the result of the H.264/AVC and the red rectangle part is amplified
in (e); (b) is the result of Ye’s [16] and the red rectangle part is amplified in (f); (c) is the result of Yeo’s [19] and the red rectangle part is amplified in (g); (d) is theresult of the proposed CAT and the red rectangle part is amplified in (h).

VI. CONCLUSIONSIn this paper, we introduce a content adaptive transform
method for the H.264/AVC-based video coding. Based on pixel
rearrangement, we construct a novel transform coding framework that utilizes adaptive transform kernels to decorrelate theprediction residuals. Unlike the traditional adaptive transforms,
the proposed method does not need to transmit the transformkernels to the decoder, which greatly saves the overhead bitrate.
In addition, to improve the coding performance, we proposea spiral-scanning method to reorder the quantized coefficients
before the RLC and entropy coding. Experimental results showthat the proposed method achieves an average bitrate reductionof 7.95% and 7.0% under all-intra and low-delay configurations, respectively, as compared to the H.264/AVC high profile.
We believe that the proposed method can be further extended
in a number of directions. For example, the proposed encoding
framework can be extended to the large transform block sizes,
such asand. In addition, the proposed method
can be used in the rectangular blocks, which will benefit therectangular quad-tree structure, and early mode decision algorithms will be designed to avoid the redundant computation ofadaptive transform kernels. Also, the proposed method can bedirectly used in image compression, where high correlation isable to improve its performance.
REFERENCES[1] T. Smith and J. Guild, “The CIE colorimetric standards and their use,”
Trans. Opt. Soc., vol. 33, no. 3, p. 73, 2002.
[2] C. Kim and C. C. J. Kuo, “Feature-based intra-/intercoding mode selection for H.264/AVC,” IEEE Trans. Circuits Syst. Video Technol., vol.
17, no. 4, pp. 441–453, 2007.
[3] A. C. Tsai, A. Paul, J. C. Wang, and J. F. Wang, “Intensity gradienttechnique for efficient intra-prediction in H.264/AVC,” IEEE Trans.
Circuits Syst. Video Technol., vol. 18, no. 5, pp. 694–698, 2008.
[4] Y. Piao and H. W. Park, “Adaptive interpolation-based divide-and-predict intra coding for H.264/AVC,” IEEE Trans. Circuits Syst. Video
Technol., vol. 20, no. 12, pp. 1915–1921, 2010.
[5] A. K. Jain, “A sinusoidal family of unitary transforms,” IEEE Trans.
Pattern Anal. Mach. Intell., no. 4, pp. 356–365, 1979.

[6] H. S. Malvar, M. Hallapuro, A. Karczewicz, and L. Kerofsky, “Lowcomplexity transform and quantization in H.264/AVC,” IEEE Trans.
Circuits Syst. Video Technol., vol. 13, no. 7, pp. 598–603, 2003.
[7] K. Sühring, G. Heising, and D. Marpe et al., KTA(2.6r1) Reference
Software, 2009 [Online]. Available: http://iphome.hhi.de/suehring/tml/
down load[8] G. J. Sullivan, J. Ohm, W.-J. Han, and T. Wiegand, “Overview of thehigh efficiency video coding (HEVC) standard,” IEEE Trans. Circuits
Syst. Video Technol., vol. 22, no. 12, pp. 1649–1668, 2012.
[9] 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., vol. 13, no. 7, pp. 560–576, 2003.
[10] L. Yu, S. J. Chen, and J. P. Wang, “Overview of AVS-video coding standards,” Signal Process.: Image Commun., vol. 24, no. 4, pp. 247–262,
2009.
[11] K. R. Rao and P. Yip, The Transform and Data Compression Handbook. Boca Raton, FL, USA: CRC, 2000.
[12] M. H. Wang and K. N. Ngan, “An efficient content adaptive transformfor video coding,” in Proc. IEEE China Summit and Int. Conf. Signal
and Information Processing (ChinaSIP), 2013, pp. 547–550.
[13] M. H. Wang, K. N. Ngan, and H. Q. Zeng, “A rate distortion optimized
transform for motion compensation residual,” in Proc. Picture Coding
Symp. (PCS2013), 2013, pp. 13–16.
[14] B. Zeng and J. Fu, “Directional discrete cosine transforms–a newframework for image coding,” IEEE Trans. Circuits Syst. Video
Technol., vol. 18, no. 3, pp. 305–313, 2008.
[15] C. L. Chang, M. Makar, S. S. Tsai, and B. Girod, “Direction-adaptive partitioned block transform for color image coding,” IEEE Trans.
Image Process., vol. 19, no. 7, pp. 1740–1755, 2010.
[16] Y. Ye and M. Karczewicz, “Improved H.264 intra coding based on
bi-directional intra prediction, directional transform, and adaptive coefficient scanning,” in Proc. IEEE Int. Conf. Image Processing, (ICIP),
2008, pp. 2116–2119.
[17] S. C. Lim, D. Y. Kim, and Y. L. Lee, “Alternative transform based on
the correlation of the residual signal,” in Proc. IEEE Congr. Image andSignal Processing, 2008 CISP’08, 2008, vol. 1, pp. 389–394.
[18] J. N. Han, A. Saxena, V. Melkote, and K. Rose, “Jointly optimized
spatial prediction and block transform for video and image coding,”
IEEE Trans. Image Process., vol. 21, no. 4, pp. 1874–1884, 2012.
[19] C. Yeo, Y. H. Tan, Z. Li, and S. Rahardja, “Mode-dependent transforms
for coding directional intra prediction residuals,” IEEE Trans. Circuits
Syst. Video Technol., vol. 22, no. 4, pp. 545–554, 2012.
[20] A. Dapena and S. Ahalt, “A hybrid DCT-SVD image-coding algorithm,” IEEE Trans. Circuits Syst. Video Technol., vol. 12, no. 2, pp.
114–121, 2002.
[21] Z. Gu, W. Lin, B. Lee, and C. T. Lau, “Low-complexity video coding
based on two-dimensional singular value decomposition,” IEEE Trans.
Image Process., vol. 21, no. 2, pp. 674–687, 2012.

946

IEEE TRANSACTIONS ON MULTIMEDIA, VOL. 16, NO. 4, JUNE 2014[22] C. Ding and J. Ye, “2-dimensional singular value decomposition for
2D maps, and images,” in Proc. SIAM Int. Conf. Data Mining, 2005,
pp. 32–43.
[23] M. Biswas, M. R. Pickering, and M. R. Frater, “Improved H.264-based
video coding using an adaptive transform,” in Proc. IEEE Int. Conf.
Image Processing (ICIP), 2010, 2010, pp. 165–168.
[24] X. Zhao, L. Zhang, S. Ma, and W. Gao, “Video coding with rate-distortion optimized transform,” IEEE Trans. Circuits Syst. Video Technol.,vol. 22, no. 1, pp. 138–151, 2012.
[25] R. A. Cohen, S. Klomp, A. Vetro, and H. F. Sun, “Direction-adaptive
transforms for coding prediction residuals,” in Proc. IEEE Int. Conf.
Image Processing (ICIP), 2010, pp. 185–188.
[26] O. G. Sezer, R. Cohen, and A. Vetro, “Robust learning of 2-d separable transforms for next-generation video coding,” in Proc. IEEE Data
Compression Conf. (DCC), 2011, 2011, pp. 63–72.
[27] A. Saxena and F. C. Fernandes, “Mode dependent DCT/DST for intra
prediction in block-based image/video coding,” in Proc. IEEE Int.
Conf. Image Processing (ICIP), 2011, pp. 1685–1688.
[28] E. Alshina, A. Alshin, and F. C. Fernandes, “Rotational transform forimage, and video compression,” in Proc. IEEE Int. Conf. Image Processing (ICIP), 2011, pp. 3689–3692.
[29] J. Dong and K. N. Ngan, “Two-layer directional transform for highperformance video coding,” IEEE Trans. Circuits Syst. Video Technol.,vol. 22, no. 4, pp. 619–625, 2012.
[30] G. H. Golub and C. Reinsch, “Singular value decomposition and leastsquares solutions,” Numer. Math., vol. 14, no. 5, pp. 403–420, 1970.
[31] M. H. Wang and B. Yan, “Lagrangian multiplier based joint three-layer
rate control for H.264/AVC,” IEEE Signal Process. Lett., vol. 16, no.
8, pp. 679–682, 2009.
[32] G. Bjontegard, “Calculation of average PSNR differences between
RD-curves,” ITU-T VCEG-M33, 2001.
Miaohui Wang (S’13) is currently pursuing the
Ph.D. degree in the Department of Electronic Engineering, the Chinese University of Hong Kong
(CUHK). Before that he received his B.S. degree inApplied Mathematics from Xi’an University of Posts
and Telecommunications (XUPT) and M.A. degreefrom School of Computer Science, Fudan University
in 2007 and 2010 respectively. His current researchinterests cover a wide range of topics related withvideo coding, computer vision and code optimization, including rate control, transform coding, error
concealment and image inpainting.
Mr. Wang received the Best Thesis Award in Shanghai city (2011) and Fudan
University (2012), respectively.

King Ngi Ngan (M’79–SM’91–F’00) received
the Ph.D. degree in electrical engineering fromLoughborough University, Loughborough, U.K. He
is currently a Chair Professor with the Department ofElectronic Engineering, Chinese University of Hong
Kong, Shatin, Hong Kong. He was previously a Full
Professor with Nanyang Technological University,
Singapore, and with the University of Western
Australia, Perth, Australia. He holds honorary andvisiting professorships with numerous universities
in China, Australia, and South East Asia. He has
published extensively, including three authored books, six edited volumes, over
300 refereed technical papers, and has edited nine special issues in journals. He
holds ten patents in image or video coding and communications.
Dr. Ngan has served as an Associate Editor of the IEEE TRANSACTIONS ON
CIRCUITS AND SYSTEMS FOR VIDEO TECHNOLOGY, the Journal on Visual Communications and Image Representation, the EURASIP Journal of Signal Processing: Image Communication, and the Journal of Applied Signal Processing.
He has chaired a number of prestigious international conferences on video signal
processing and communications, and has served on the advisory and technicalcommittees of numerous professional organizations. He co-chaired the IEEE International Conference on Image Processing, Hong Kong, in September 2010.
He is a fellow of IET, U.K., and IEAust, Australia, and was an IEEE Distinguished Lecturer from 2006 to 2007.

Long Xu received his M.S. degree in Applied Mathematics from Xidian University, China, in 2002, and
his Ph.D. degree from the Institute of Computing
Technology, Chinese Academy of Sciences in 2009.
He was a Postdoc researcher at the Department ofComputer Science of City University of Hong Kong,and the Department of Electronic Engineering ofChinese University of Hong Kong from August
2009 to December 2012. Now, he is with both
the Rapid-Rich Object Search Lab and School ofComputer Engineering, Nanyang Technological
University, Singapore. His research interests include image/video coding,wavelet-based image/video coding and computer vision.