Fast I-slice encoding and down-scaling from H.264/AVC bit stream 1

Abstract

We present a new approach for generating thumbnail images from H.264/AVC coded bit streams. We have verified analytically that mismatch errors between the encoder and decoder prevent the direct generation of thumbnail images from H.264/AVC transform coefficients. Based on this analysis, we have devised a method that exploits both the spatial and transform domains. What distinguishes our algorithm from previous works is that it determines the thumbnail image pixels by summing the residual and estimate block averages. The residual block averages are directly acquired in the transform domain and the estimate block averages are calculated in the spatial domain. The proposed method produces thumbnail images that are indistinguishable to the ones produced by the method that decodes the H.264/AVC-I slice bit streams and then scales them down, while, for most of images, it executes almost 3 times faster than the down-scaling method at frequently used bandwidths.

Keywords

H.264/AVC Intra prediction Integer DCT

1 Introduction

The use of spatially reduced images, also known as thumbnail images, has become more prevalent as video browsing and retrieval have been more important. In order to generate thumbnail images, the encoded video stream must be decoded and then the decoded video sequence must be down-scaled. This could lead to significant amounts of computing and storage requirements as the demand for video browsing and retrieval expands to real time broadcasting and mobile terminals [1]. Therefore, efficient methods for the rapid generation of thumbnail images from coded video streams must be developed.

The efficient methods had been developed for generating thumbnail image directly from the MPEG-2 or 4 coded video streams. The current thumbnail image generating method used for MPEG-2 and 4 coded bit streams is to collect the DC values of image spectra in I-frames, since the DC values are the average values of image blocks [2, 3]. However, the conventional method is not readily applicable to the H.264/AVC coded bit stream for the following reasons. The H.264/AVC standard adopts the integer DCT (IntDCT). The kernel of the IntDCT is extracted from the kernel of the modified DCT (MDCT), which approximates the DCT kernel found in the MPEG-2 and 4 standards [4, 5]. It also performs intra prediction in the spatial domain and conducts transforms on the resultant spatial residual blocks [6]. So, the H.264/AVC transform coefficients are not directly associated with the image block spectra. In addition, the quantization parameters and the integer DCT coefficients are closely coupled. Therefore, it has become necessary to develop a method that efficiently generates thumbnail images from a H.264/AVC encoded video stream.

In order to produce image spectrum from H.264/AVC bit stream, Chen et al. developed matrix operations translating the intra prediction in spatial domain into the MDCT domain [7]. Using this work, Kim et al. generated thumbnail images by collecting DC values of MDCT coefficients [8]. Since the method in [7] considered neither the quantization process nor the procedure of separating the IntDCT kernels from the MDCT kernels, it induces mismatch errors between the encoder and decoder when applied to actual H.264/AVC coding system [9, 10]. For compensating the errors, Kim et al. adopted lookup tables (LUT). However, the mismatch errors can not be exactly analyzed in transform domain and so it is difficult for their lookup tables to compensate the errors. The method also requires real number operations due to the real values of MDCT.

In this work, we propose new algorithms exploiting spatial and transform domains. We analyze the intra prediction in the MDCT domain with consideration of the mismatch errors. Based on the analysis, the proposed method obtains thumbnail pixels by summing the averages of the residual and estimate blocks. The averages of the residual blocks are acquired from the DC values in the integer transform domain and those of the estimate blocks are computed in the spatial domain. The proposed method not only radically eliminates the source of the mismatch errors, but also performs integer operations only. The experiments verify that the proposed method produces the thumbnail images subjectively indistinguishable to the down-scaled image and reduces the complexity by more than 60% over the down-scaling method.

The outline of the paper is organized as follows. Section 2 introduces the transformation and intra prediction used in H.264/AVC. In Section 3, we prove the infeasibility of generating the thumbnail image directly from transform coefficients of H.264/AVC. Section 4 elaborates the dual domain method for generating thumbnail images from H.264/AVC bit-streams. The performances of the developed method are discussed in Section 5. Finally, Section 6 summarizes the conclusions.

2 Transform and Intra prediction in H.264/AVC

This section briefly addresses the transformation and the intra prediction of H.264/AVC.

2.1 Transformation of H.264

In H.264/AVC, a spectrum of an image block is obtained by the modified DCT(MDCT) that approximates the real DCT. However, for integer operations, H.264/AVC performs the integer DCT(IntDCT) of which kernels are derived from the MDCT kernel [4].

Let x be an image block. The size of x can be either 4×4 or 8×8. We also denote the MDCT block and the IntDCT block corresponding to x as X_MDCT and X_IntDCT, respectively. Then, the following relations are established. $\begin{matrix} X_{MDCT} & = & {C_{f} \cdot x \cdot {(C_{f})}^{T}} \otimes {PF}_{f} \\ \equiv & X_{IntDCT} \otimes {PF}_{f} \\ = {(C_{i})}^{T} \cdot {X_{MDCT} \otimes {PF}_{i}} \cdot C_{i} \end{matrix}$ (1) where ⊗ represents the element-by-element multiplication, and C_f and C_i denote the forward and backward integer DCT kernel matrices, and PF_f and PF_i are also the forward and backward post scaling factor matrices, respectively. For the 4×4 transform, these matrices are as follows [6]: $C_{f} = [\begin{matrix} 1 & 1 & 1 & 1 \\ 2 & 1 & - 1 & - 2 \\ 1 & - 1 & - 1 & 1 \\ 1 & - 2 & 2 & - 1 \end{matrix}], {PF}_{f} = [\begin{matrix} a^{2} & \frac{ab}{2} & a^{2} & \frac{ab}{2} \\ \frac{ab}{2} & \frac{b^{2}}{4} & \frac{ab}{2} & \frac{b^{2}}{4} \\ a^{2} & \frac{ab}{2} & a^{2} & \frac{ab}{2} \\ \frac{ab}{2} & \frac{b^{2}}{4} & \frac{ab}{2} & \frac{b^{2}}{4} \end{matrix}]$ $C_{i} = [\begin{matrix} 1 & 1 & 1 & 1 \\ 1 & \frac{1}{2} & - \frac{1}{2} & - 1 \\ 1 & - 1 & - 1 & 1 \\ \frac{1}{2} & - 1 & 1 & - \frac{1}{2} \end{matrix}], {PF}_{i} = [\begin{matrix} a^{2} & ab & a^{2} & ab \\ ab & b^{2} & ab & b^{2} \\ a^{2} & ab & a^{2} & ab \\ ab & b^{2} & ab & b^{2} \end{matrix}]$ where a = 1/2, $b = \sqrt{2 / 5}$ . For the 8×8 transform, the matrices can be found in [11].

2.2 Intra Prediction

Intra prediction of H.264/AVC encodes the residual between current blocks to be coded and blocks estimating the current blocks. Let xⁿ and ${\tilde{x}}^{n}$ be the n^th block to be coded and the reconstructed block of xⁿ, respectively. The estimate block EstBLⁿ for xⁿ is constructed by referring to the boundary of previously coded blocks in accordance with the prediction modes. Figure 1 illustrates the reference pixels for 4×4 and 16×16 intra predictions.

Fig.1

Reference pixels in accordance with block sizes. (a) The 13 reference pixels for the 4×4 intra predictions. (b) The 33 reference pixels associated with the 16×16 intra predictions.

It is possible to describe the procedures of reconstructing estimated block in matrix operations [7, 8]. We denote $r_{n}^{m, i}$ as the referencing matrix of the i^th reference pixel for n^th block with prediction m. We can also let sⁱ be the circular shift matrix for the i^th reference pixel. Details of $r_{n}^{m, i}$ and sⁱ can be found in [7]. Then, EstBLⁿ for prediction mode m is expressed as [8]. $\begin{matrix} {EstBL}^{n} = \sum_{i = 1}^{4} {r_{n - 1}^{m, i} \cdot {\tilde{x}}^{n - 1} \cdot {(s^{i})}^{T}} \\ + \sum_{j = 2}^{4} \sum_{i = 1}^{4} {s^{i} \cdot {\tilde{x}}^{n - j} \cdot r_{n - j}^{m, i}} \\ = the left bounary pixels \\ + Pixels estimated by the upper boundary pixels \end{matrix}$ (2)

The n^th residual block and its reconstructed residual block are denoted as resⁿ and ${\tilde{res}}^{n}$ . The intra prediction can be described as in the following recursive form [6]. $\begin{matrix} {res}^{n} & = & x^{n} - {EstBL}^{n} \\ {\tilde{x}}^{n} & = & {\tilde{res}}^{n} + {EstBL}^{n} \end{matrix}$ (3)

3 Intra prediction in transform domain

In this section, we analyze the intra prediction in the transform domain and then verify that it is infeasible to generate thumbnail images directly from H.264/AVC transform coefficients.

We use the subscripts “MDCT” and “IntDCT” to denote the modified DCT blocks and the integer DCT blocks. From (3), the intra prediction in MDCT domain can be described as $\begin{matrix} {Res}_{MDCT}^{n} & = & X_{MDCT}^{n} - {EstBL}_{MDCT}^{n} \\ {\tilde{X}}_{MDCT}^{n} & = & {\tilde{Res}}_{MDCT}^{n} + {EstBL}_{MDCT}^{n} \end{matrix}$ (4)

From (4), if Q_s is quantization scale, the spectrum of a reconstructed residual block is $\begin{matrix} {\tilde{Res}}_{MDCT}^{n} & = & \partial (\frac{{Res}_{MDCT}^{n}}{Q_{s}}) \cdot Q_{s} \\ = & \partial (\frac{{Res}_{IntDCT}^{n} \otimes {PF}_{i}}{Q_{s}}) \cdot Q_{s} \\ \equiv & Z_{n} \cdot Q_{s} \end{matrix}$ (5) where ∂ (X) is the matrix operation rounding each element of matrix X to the nearest integer and Z_n stands for the n^th quantized residual MDCT block.

In H.264/AVC, the inverse quantization procedure is implemented by multiplying Z_n with round approximations of the rescaling matrix V = ∂ (Q_s · PF_i · 64). In the matrix V, the quantization scale Q_s doubles for every increment of 6 in the quantization parameter QP with maintaining bit accuracy of 6 and so Q_s is obtained as below. $Q_{s} = Q_{0} (\mod (QP, 6)) \cdot 2^{⌊ QP / 6 ⌋}$ (6) where mod (· , ·) is the modulo operator and {Q₀ (i) | i = 0, …, 5} is the set of initial quantization steps.

The rescaling matrix V is defined as [12] $\underset{.}{V = \partial (Q_{0} (\mod (QP, 6)) \cdot {PF}_{i} \cdot 64) \cdot 2^{⌊ QP / 6 ⌋}}$ (7)

For integer operations, the inverse quantization of H.264/AVC produces the integer block ${\tilde{Res}}_{IntDCT}$ instead of the real block ${\tilde{Res}}_{MDCT}$ . Therefore, the quantization process for acquiring ${\tilde{Res}}_{IntDCT}$ from Z_n is obtained as follows: $\begin{matrix} {\tilde{Res}}_{IntDCT}^{n} = Z_{n} \otimes V \\ = Z_{n} \otimes {\partial (Q_{0} (\mod (QP, 6)) \cdot {PF}_{i} \cdot 2^{6}) \\ \cdot 2^{⌊ QP / 6 ⌋}} \\ = Z_{n} \otimes {(Q_{0} (\mod (QP, 6)) \cdot {PF}_{i} \cdot 2^{6}) \\ \cdot 2^{⌊ QP / 6 ⌋}} + \in_{V} \end{matrix}$ (8) where ∈ _V is the error matrix caused by the integer rounding of the rescaling matrix. From (5) and (8), the spectrum of a reconstructed residual block becomes $\begin{matrix} {\tilde{Res}}_{MDCT}^{n} & = & Z_{n} \cdot Q_{s} \\ = & (({\tilde{Res}}_{IntDCT}^{n} - \in_{V}) ø {PF}_{i}) / 64 \\ = & ({\tilde{Res}}_{IntDCT}^{n} ø {PF}_{i}) / 64 + \in_{res} \end{matrix}$ (9) where ø represents the element-by-element division and ∈_res is an integer approximation error matrix occurred while converting the IntDCT coefficients to the MDCT coefficients.∈_res is apparently caused from ∈ _V .

As shown from (4) and (9), the errors of the elements containing rounding error spread over entire elements of the reconstructed spectrum block ${\tilde{X}}_{MDCT}^{n}$ while the estimate spectrum block ${EstBL}_{MDCT}^{n}$ is constructed. Moreover, the errors accumulate as the intra prediction proceeds. This implies that the DC value of the reconstructed spectrum block ${\tilde{X}}_{MDCT}^{n} (0, 0)$ contains the approximation errors and cannot be a pixel value of a thumbnail image. The error accumulation by the intra prediction process is theoretically derived in Appendix. Consequently, it is impossible to generate a thumbnail image directly from H.264/AVC transform coefficients without enduring mismatch errors.

Figure 2 compares the thumbnail images produced by taking the average values of the 4×4 decoded image blocks and collecting the DC values of the reconstructed 4×4 MDCT blocks. As shown in Fig. 2(b), the integer approximation error embedded in the MDCT coefficients propagates and accumulates and so the quality of thumbnail image degrades rapidly as the intra prediction proceeds.

Fig.2

Comparison of thumbnail images. (a) Thumbnail image produced by the average values of 4x4 blocks. (b) Thumbnail image produced by collecting DC values of the 4x4 reconstructed MDCT blocks.

4 Dual domain method for generating thumbnail images

This section develops a method for fast generating thumbnail images from H.264/AVC coded bit streams, without any mismatch errors. A thumbnail pixel must be the average of the reconstructed block and the reconstructed block is sum of the residual block and estimated block. Therefore, a thumbnail pixel Avg_rec is obtained as $Avg_r ec = Avg_r es + Avg_E stBL$ (10) where Avg_res and Avg_EstBL are an average values of the reconstructed residual and the estimate blocks, respectively.

The proposed method obtains the residual block averages in the integer transform coefficients and calculates the estimate block averages in the spatial domain. So, the proposed method is carried out in dual domains.

4.1 Calculation of residual block average, Avg_res

At {(i, j)} = {(0, 0) , (2, 0) , (0, 2) , (2, 2)}, the elements of PF_i are 1/4 [12]. From (7), we obtain the rescaling elements such as: $\begin{matrix} V (i, j) & = \partial (Q_{0} (\mod (QP, 6)) \cdot \frac{1}{4} \cdot 64) \\ \cdot 2^{⌊ (QP / 6) ⌋} \\ = (Q_{0} (\mod (QP, 6)) \cdot 2^{4}) \cdot 2^{⌊ (QP / 6) ⌋} \end{matrix}$ (11) where { (i, j) } = { (0, 0) , (2, 0) , (0, 2) , (2, 2) } _. Eq. (11) indicates that the rescaling elements at { (i, j)} = { (0, 0) , (2, 0) , (0, 2) , (2, 2) } are free from any approximation errors.

From (9) and (11), the reconstructed MDCT coefficients at { (i, j)} = { (0, 0) , (2, 0) , (0, 2) , (2, 2) } are ${\tilde{Res}}_{MDCT}^{(i, j)} = \frac{{\tilde{Res}}_{IntDCT}^{(i, j)}}{64 \cdot {PF}_{i} (i, j)} = {\frac{{\tilde{Res}}_{IntDCT}^{(i, j)}}{16}}_{.}$ (12)

The DC coefficient of image spectrum, ${\tilde{Res}}_{MDCT}^{(0, 0)}$ , is equal to an average value of a block and so, Avg_res can be obtained such as $Avg_res = {\tilde{Res}}_{MDCT}^{(0, 0)} = {\tilde{Res}}_{IntDCT}^{(0, 0)} / 16_{.}$ (13)

From (13), we can obtain the residual block average directly from integer DCT coefficients without any mismatch errors.

Similarly, for the 8×8 transform, the elements of V at { (i, j)} = { (0, 0) , (4, 0) , (0, 4) , (4, 4) } do not hold the errors. So, Avg_res for the 8×8 transform can be also obtained by (13).

4.2 Calculation of estimate block average, Avg_EstBL

As shown in Section 3, the estimate block averages calculated from transform coefficients must contain the accumulated mismatch errors. Therefore, we need to calculate the estimate block averages in the spatial domain.

The estimate blocks are constructed through referring to the pixels at the boundaries of previously reconstructed blocks [6]. So, Avg_EstBL can be calculated from only the boundary pixels. Table 1 lists the formulas calculating Avg_EstBL for each of intra-prediction modes. In the table, calculations of the estimate block averages for vertical, horizontal and DC modes in 16×16 size are equivalent to those of same modes in 4×4 size.

Table 1

Block size Prediction mode Averaging formula

4×4 vertical (4A + 4B + 4C + 4D)/16

horizontal (4I + 4J + 4K + 4L)/16

DC (A + B + C + D + I + J + K + L)/8

diagonal down-left (A + 4B + 8 · C + 12D + 14E + 12 · F + 8G + 5H)/64

diagonal down-right (14 · M + 12A + 8B + D + 12I + 8J + 4K + L)/64

vertical-right (11 · M + 16A + 15B + 10C + 3D + 5I + 3J + K)/64

horizontal-down (11 · M + 5A + 3B + C + 16I + 15J + 10K + 3L)/64

vertical-left (3A + 10B + 15C + 16D + 13E + 6F + G)/64

horizontal-up (3I + 10J + 15K + 36L)/64

16×16 Plane $\begin{matrix} {avg}_{00} & = & 2 a - 11 b - 11 c + 32, & {avg}_{01} & = & 2 a - 3 b - 11 c + 32 \\ {avg}_{02} & = & 2 a + 5 b - 11 c + 32, & {avg}_{03} & = & 2 a + 13 b - 11 c + 32 \\ {avg}_{10} & = & 2 a - 11 b - 3 c + 32, & {avg}_{11} & = & 2 a - 3 b - 3 c + 32 \\ {avg}_{12} & = & 2 a + 5 b - 3 c + 32, & {avg}_{13} & = & 2 a - 13 b - 3 c + 32 \\ {avg}_{20} & = & 2 a - 11 b + 5 c + 32, & {avg}_{21} & = & 2 a - 3 b + 5 c + 32 \\ {avg}_{22} & = & 2 a + 5 b + 5 c + 32, & {avg}_{23} & = & 2 a + 13 b + 5 c + 32 \\ {avg}_{30} & = & 2 a - 11 b + 13 c + 32, & {avg}_{31} & = & 2 a - 3 b + 13 c + 32 \\ {avg}_{32} & = & 2 a + 5 b + 13 c + 32, & {avg}_{33} & = & 2 a + 13 b + 13 c + 32 \end{matrix}$

where avg_ij (i, j = 0, 1, 2, 3) is the average of block x_ij in Fig. 1(b),

a = 16 (D₃ + L₃), b = (5h + 32)/64, c = (5v + 32)/64,

$h = {\begin{matrix} (A_{2} + C_{1}) + 2 (B_{2} + B_{1}) + 3 (C_{2} + A_{1}) + 4 (D_{2} + D_{0}) \\ + 5 (A_{3} + C_{0}) + 6 (B_{3} + B_{0}) + 7 (C_{3} + A_{0}) + 8 (D_{3} + M) \end{matrix}}_{,}$

$v = {\begin{matrix} (I_{2} - K_{1}) + 2 (J_{2} - J_{1}) + 3 (K_{2} - I_{1}) + 4 (L_{2} - L_{0}) \\ + 5 (I_{3} - K_{0}) + 6 (J_{3} - J_{0}) + 7 (K_{3} - I_{0}) + 8 (L_{3} - M) \end{matrix}}_{.}$

It can be observed that the reference pixels are produced from the combinations of only the 7 boundary pixels located at bottom and right boundaries of previously reconstructed blocks. Figure 3 represents how combinations of the 7 boundary pixels construct a 4×4 estimate block. In Fig. 3(a), the block xⁿ is the current block to be intra-coded. A ∼ M are reference pixels for estimating xⁿ. After xⁿ is coded, the right boundary pixels of the reconstructed block ${\tilde{x}}^{n}$ are to be used as the I,J,K and L pixels for estimating the block x⁽ⁿ⁺¹⁾. The bottom boundary pixels of ${\tilde{x}}^{n}$ become the E,F,G and H pixels for estimating the block x^m and also become the A,B,C and D pixels for estimating the block x^(m+1). The pixel M for estimating the block x^(m+2) is the bottom right boundary pixel of ${\tilde{x}}^{n}$ . Figure 3(b) illustrates how the 7 boundary pixels of a reconstructed block ${\tilde{x}}^{n}$ organize the reference pixels for estimating consecutive blocks.

Fig.3

Reference pixels for constructing a 4×4 estimate block. (a) Constitution of 13 reference pixels used for estimating the block xⁿ. (b) The 7 boundary pixels at the reconstructed block ${\tilde{x}}^{n}$ for estimating next blocks.

As seen in (3), the reconstruction of the 7 boundary pixels requires the reconstruction of the corresponding pixels of the residual block and the estimate block. The 7 boundary pixels of a residual block are reconstructed by calculating the integer inverse DCT [13]. The boundary pixels of an estimate block are generated through combinations of the previously reconstructed boundary pixels, where the combinations are made up in accordance with each intra prediction mode [6].

Using that the 7 boundary pixels of a residual block are reconstructed, we develop a method that greatly reduces the complexity of integer inverse DCT(IntIDCT). From (1), the integer inverse DCT(IntIDCT) is computed such as $\tilde{res} = C_{i}^{T} \cdot {\tilde{Res}}_{IntDCT} \cdot C_{i} .$ (14)

Let ${\tilde{res}}^{ij}$ and ${\tilde{Res}}_{IntDCT}^{ij}$ denote the (i, j) element of $\tilde{res}$ and ${\tilde{Res}}_{IntDCT}$ , respectively. With extracting calculations required for computing the boundary pixels only, we can compute the boundary residual pixels as follows [13]: $\begin{matrix} [\begin{matrix} \tilde{r} e s^{03} \\ \tilde{r} e s^{13} \\ \tilde{r} e s^{23} \\ \tilde{r} e s^{33} \end{matrix}] & = C_{i}^{T} \cdot [\begin{matrix} H_{0} \\ H_{1} \\ H_{2} \\ H_{3} \end{matrix}] & = [\begin{matrix} H_{0} + H_{1} + H_{2} + H_{3} / 2 \\ H_{0} + H_{1} / 2 - H_{2} - H_{3} \\ H_{0} - H_{1} / 2 - H_{2} + H_{3} \\ H_{0} - H_{1} + H_{2} - H_{3} / 2 \end{matrix}] \\ [\begin{matrix} \tilde{r} e s^{30} \\ \tilde{r} e s^{31} \\ \tilde{r} e s^{32} \\ \tilde{r} e s^{33} \end{matrix}] & = {[\begin{matrix} V_{0} \\ V_{1} \\ V_{2} \\ V_{3} \end{matrix}]}^{t} \cdot C_{i} & = [\begin{matrix} V_{0} + V_{1} + V_{2} + V_{3} / 2 \\ V_{0} + V_{1} / 2 - V_{2} - V_{3} \\ V_{0} - V_{1} / 2 - V_{2} + V_{3} \\ V_{0} - V_{1} + V_{2} - V_{3} / 2 \end{matrix}] \end{matrix}$ (15) Since ${\tilde{res}}^{33}$ is overlapped in the horizontal and vertical components, we only calculated the overlapped components at once. So, we name (15) as the 7 integer IDCT (7-IntIDCT).

Similarly, Avg_EstBL for the 8×8 block size can be calculated by 25 reference pixels which are shown in Fig. 4. Table 2 lists the formulas calculating Avg_EstBL for each 8×8 intra prediction mode. As in the 4×4 block, only the 15 boundary pixels of the 8×8 block are reconstructed. The 15 integer IDCT (15-IntIDCT) is derived in the following manner.

\begin{array}{l} \begin{matrix}  \end{matrix} \\ n{\footnotesizen\begin{array}{llll}n\makebox [- 4 e x] [\begin{matrix} \tilde{r} e s^{07} \\ \tilde{r} e s^{17} \\ \tilde{r} e s^{27} \\ \tilde{r} e s^{37} \\ \tilde{r} e s^{47} \\ \tilde{r} e s^{57} \\ \tilde{r} e s^{67} \\ \tilde{r} e s^{77} \end{matrix}] = C_{i}^{T} \cdot {[\begin{matrix} H_{0} \\ H_{1} \\ H_{2} \\ H_{3} \\ H_{4} \\ H_{5} \\ H_{6} \\ H_{7} \end{matrix}]}_{,} \begin{array}{l} [\begin{matrix} \tilde{r} e s^{70} \\ \tilde{r} e s^{71} \\ \tilde{r} e s^{72} \\ \tilde{r} e s^{73} \\ \tilde{r} e s^{74} \\ \tilde{r} e s^{75} \\ \tilde{r} e s^{76} \\ \tilde{r} e s^{77} \end{matrix}] & {[\begin{matrix} V_{0} \\ V_{1} \\ V_{2} \\ V_{3} \\ V_{4} \\ V_{5} \\ V_{6} \\ V_{7} \end{matrix}]}^{T} \cdot C_{i} \end{array} \end{array}

(16)

Fig.4

Reference pixels for constructing a 8×8 estimate block.

Table 2

Block size	Prediction mode	Averaging formula
8 × 8	vertical	(8A₀ + 8B₀ + 8C₀ + 8D₀ + 8A₁ + 8B₁ + 8C₁ + 8D₁)/64
	horizontal	(8I₀ + 8J₀ + 8K₀ + 8L₀ + 8I₁ + 8J₁ + 8K₁ + 8L₁)/64
	DC	(A₀ + B₀ + C₀ + D₀ + A₁ + B₁ + C₁ + D₁ + I₀ + J₀ + K₀ + L₀ + I₁ + J₁ + K₁ + L₁)/16
	diagonal down-left	$(\begin{matrix} A_{0} / 4 + B_{0} + 2 C_{0} + 3 D_{0} + 4 A_{1} + 5 B_{1} + 6 C_{1} + 7 D_{1} \\ + 15 A_{2} / 2 + 7 B_{2} + 6 C_{2} + 5 D_{2} + 4 A_{3} + 3 B_{3} + 2 C_{3} + 5 D_{3} \end{matrix}) / 64$
	diagonal down-right	$(\begin{matrix} 7 A_{0} + 6 B_{0} + 5 C_{0} + 4 D_{0} + 3 A_{1} + 2 B_{1} + C_{1} + D_{1} / 4 \\ + 7 I_{0} + 6 J_{0} + 5 K_{0} + 4 L_{0} + 3 I_{1} + 2 J_{1} + K_{1} + L_{1} / 4 + 15 M / 2 \end{matrix}) / 64$
	vertical-right	$(\begin{matrix} 8 A_{0} + 8 B_{0} + 8 C_{0} + 31 D_{0} / 4 + 13 A_{1} / 2 + 9 B_{1} / 2 + 5 C_{1} / 2 + 3 D_{1} / 4 \\ + 13 I_{0} / 4 + 11 J_{0} / 4 + 9 K_{0} / 4 + 7 L_{0} / 4 + 5 I_{1} / 4 + 3 J_{1} / 4 + K_{1} / 4 + 23 M / 4 \end{matrix}) / 64$
	horizontal-down	$(\begin{matrix} 13 A_{0} / 4 + 11 B_{0} / 4 + 9 C_{0} / 4 + 7 D_{0} / 4 + 5 A_{1} / 4 + 3 B_{1} / 4 + C_{1} / 4 \\ + 8 I_{0} + 8 J_{0} + 8 K_{0} + 31 L_{0} / 4 + 13 I_{1} / 2 + 9 J_{1} / 2 + 5 K_{1} / 2 + 3 L_{1} / 4 + 23 M / 4 \end{matrix}) / 64$
	vertical-left	$(\begin{matrix} 3 A_{0} / 4 + 5 B_{0} / 2 + 9 C_{0} / 2 + 13 D_{0} / 2 + 31 A_{1} / 4 + 8 B_{1} + 8 C_{1} + 8 D_{0} \\ + 29 A_{2} / 4 + 11 B_{2} / 2 + 7 C_{2} / 2 + 3 D_{2} / 2 + M / 4 \end{matrix}) / 64$
	horizontal-up	(3I₀/4 +5J₀/2 +9K₀/2 +13L₀/2 +31I₁/4 +8J₁ + 8K₁ + 26L₁)/64

where the horizontal components are $\begin{array}{l} H_{i} = \tilde{R} e s_{I n t D C T}^{i 0} - 3 \tilde{R} e s_{I n t D C T}^{i 1} / 2 + \tilde{R} e s_{I n t D C T}^{i 2} \\ - 5 \tilde{R} e s_{I n t D C T}^{i 3} / 4 + \tilde{R} e s_{I n t D C T}^{i 4} - 3 \tilde{R} e s_{I n t D C T}^{i 5} / 4 \\ + \tilde{R} e s_{I n t D C T}^{i 6} / 2 - 3 \tilde{R} e s_{I n t D C T}^{i 7} / 8, \\ + (i = 0, 1, 2, 3, 4, 5, 6, 7) \end{array}$ and the vertical components are $\begin{array}{l} V_{j} = \tilde{R} e s_{I n t D C T}^{0 j} - 3 \tilde{R} e s_{I n t D C T}^{1 j} / 2 + \tilde{R} e s_{I n t D C T}^{2 j} \\ - 5 \tilde{R} e s_{I n t D C T}^{3 j} / 4 + \tilde{R} e s_{I n t D C T}^{4 j} - 3 \tilde{R} e s_{I n t D C T}^{5 j} / 4 \\ + \tilde{R} e s_{I n t D C T}^{6 j} / 2 - 3 \tilde{R} e s_{I n t D C T}^{7 j} / 8, \\ {(j = 0, 1, 2, 3, 4, 5, 6, 7)}_{.} \end{array}$

Tables 3 and 4 compare the complexities of the proposed integer IDCTs and the conventional integer IDCTs. Computational structure of the 7,15-IntIDCT contains neither the diagonal component computations nor any internal dependencies. Accordingly, the 7,15-IntIDCT not only greatly decrease the number of operations, but also avoid any recursive operations. By avoiding the recursive structure, the proposed integer IDCTs dramatically reduces memory access compared to the fast integer IDCT. In addition, they require fewer arithmetic operations over the direct IDCT since fewer components are computed.

With the method constructing the 7 or 15 boundary pixels only, we can greatly reduce the complexity of calculating the average of an estimate block, compared to the method reconstructing blocks.

Table 3

Complexities of the 7-IntIDCT and the 4×4 integer IDCTs

	Add.	Mult.	M/A	Structure
Fast Integer IDCT	96	48	176	Recursive
Direct Integer IDCT	240	112	64	Non-recursive
7-IntIDCT	56	22	28	Non-recursive

Table 4

Complexities of the 15-IntIDCT and the 8×8 integer IDCTs

	Add.	Mult.	M/A	Structure
Fast Integer IDCT	636	288	832	Recursive
Integer IDCT	896	768	512	Non-recursive
15-IntIDCT	392	170	135	Non-recursive

4.3 Analysis of the proposed dual domain method

Figure 5 illustrates the overall scheme of the proposed method. The quantized residual integer DCT block Z is obtained by variable length decoding from I-slice bit streams. The inverse quantization applied to Z produces the integer DCT residual coefficient block ${\tilde{Res}}_{IntDCT}$ . The average of residual block, Avg_res, is calculated directly from the DC value ${\tilde{Res}}_{IntDCT} (0, 0)$ . The 7 residual boundary pixels for 4×4 block and the 15 residual boundary pixels for 8×8 block are reconstructed by using the 7-IntIDCT and 15-IntIDCT, respectively. The 7 or 15 estimate boundary pixels for the current block are constructed from sets of the previously reconstructed 7 or 15 boundary pixels in accordance with the given intra prediction mode. The 7 or 15 boundary pixels of the current block is reconstructed by adding the 7 or 15 residual and estimate boundary pixels. The average of the estimate block, Avg_EstBL, is calculated by using the formulas of Table 1. The average of the current block, that becomes a pixel value of a thumbnail image, is the sum of Avg_res and Avg_EstBL.

Fig.5

The overall scheme for the proposed dual domain method.

Distinctions of the proposed method can be listed as follows. First, the proposed method uses multiple domains exploiting both the transform and spatial domain. Second, it performs the 7-IntIDCT or the 15-IntIDCT instead of the 4×4 or 8×8 integer IDCT. Finally, it recovers only the 7 or 15 estimate boundary pixels rather than the entire estimate blocks.

In chroma components, even if the block size for the intra prediction is 8×8, the size of integer DCT is 4×4. Thus, 7-IntIDCT can be directly applied except that the reference pixels are at boundaries of the 8×8 block.

5 Experiment and Discussion

We evaluate the performance of the proposed method in terms of thumbnail image quality, theoretical complexity and actual computation time. The proposed method was implemented on the H.264/AVC-JM17.2 at main and high profiles [14]. Test sequences are ‘table setting’, ‘playing cards’, and ‘rolling tomatoes’ of which the resolution is HD(1920×1080). The transform block size for the main profile is 4×4 and the resolution of the thumbnail images is 480×270. At the high profile, 4×4 and 8×8 block transforms are used and so the resolution of the thumbnail images is 240×136.

5.1 Evaluation of thumbnail image quality

The original thumbnail images are naturally regarded as the images obtained through fully decoding the intra-coded video stream and then down-scaling the resultant images. Average, bilinear and bicubic filters are used in down-scaling.

We used the Structural SIMilarity(SSIM) index to measure the similarities between the original thumbnail images and ones generated by the proposed method, and also between the original thumbnail images and the ones obtained through the DC extraction method [15]. For two images X, Y, the SSIM is calculated as $\begin{matrix} SSIM (X, Y) = \frac{(2 μ_{X} μ_{Y} + C_{1}) (2 σ_{XY} + C_{2})}{(μ_{X}^{2} + μ_{Y}^{2} + C_{1}) (2 σ_{X}^{2} σ_{Y}^{2} + C_{2})} \end{matrix}$ (17) where μ_x, μ_y, σ_x and σ_y are the mean and the standard deviations of each image, and σ_xy is the correlation coefficient, and C₁ and C₂ are constants for masking Human Visual System. C₁ and C₂ are generally set as C₁ = 6.5 and C₂ = 58.5.

The SSIM score of 1.0 implies that the compared images are identical. Table 5 shows the SSIM results. The SSIM values comparing the original images and the images made by the proposed method are very close to 1, which indicates that the differences between the compared images are indistinguishable. Conversely, the low SSIM values in regards to the DC extraction method indicate that the original images and the images produced by the DC extraction method are apparently distinguishable.

Table 5

The structural similarity(SSIM) index scores. The original images are measured against the images generated by the proposed method and the DC extraction method

Sequences	Method
	DC extraction	Proposed
Table Setting	0.52	0.99
Playing Cards	0.56	0.99
Rolling Tomatoes	0.56	0.99

Figure 6 shows the thumbnail images generated using each method and the differences between these images and the original images. We used an average filter to obtain the original image. The image resolution was reduced to 1/4 in each direction. As seen in the figure, the thumbnail image produced by the proposed method is identical to the original image, whereas the DC extraction method displays a degradation in quality caused by the mismatch errors.

Fig.6

Thumbnail images generated by the proposed method and the DC extraction method and differences against the original images. (a) Thumbnail images by the proposed method. (b) Thumbnail images by the DC extraction method.

According to both the SSIM and the subjective quality results, the proposed algorithm produces thumbnail images that are indistinguishable from the original ones.

5.2 Evaluation of complexities

In order to evaluate the complexity of the proposed method, we compared the complexities of the proposed method to the down-scaling method. The down-scaling method generally uses an average filter since the average filter has the lowest complexity and the thumbnail images generated by the average filter are almost identical to the ones generated by using the other down-scaling filters.

For calculating the complexities theoretically, we multiplied the frequencies of each mode and the theoretical complexities found in the corresponding modes. The frequencies of each mode were actually counted. The theoretical complexity of the proposed method includes the computation of the 7-IntIDCT and 15-IntIDCT, the construction of the 7 or 15 boundary pixels of estimate blocks, and the calculation of the formulas found in Tables 1 and 2 used to obtain the estimate block average. The complexity of the down-scaling method includes the computation of the fast 4×4 and 8×8 integer IDCTs, the construction of the 4×4 or 8×8 estimate blocks, and the calculation of the reconstructed block average [4, 6, 11].

Table 6 compares the theoretical complexities. Compared to down-scaling method, at the main profile, the proposed method reduces addition by 26.9%, multiplication by 45.5%, and memory access by 79.9%, and at the high profile, the proposed method reduces addition by 33.2%, multiplication by 38%, and memory access by 82.7%.

Table 6
Complexities for generating a pixel of thumbnail images from bit-stream coded with main and high profiles. ‘Scale’ and ‘Prop’ indicate ‘down-scaling method’ and ‘proposed method’, respectively

Sequence Profile Addition Multiplication Mem. Access

Scale Prop. Scale Prop. Scale Prop.

Table Main 146 56 200 734 310 910

Setting High 106 30 40 490 192 157

Playing Main 152 58 202 738 313 910

Cards High 112 32 41.3 494 195 159

Rolling Main 148 57 201 733 310 908

Tomatoes High 108 31 40 489 192 156

Sequence	Profile	Addition	Multiplication	Mem. Access
Table	Main	146	56	200	734	310	910
Setting	High	106	30	40	490	192	157
Playing	Main	152	58	202	738	313	910
Cards	High	112	32	41.3	494	195	159
Rolling	Main	148	57	201	733	310	908
Tomatoes	High	108	31	40	489	192	156

In order to evaluate the execution times at actual systems, we executed the proposed method and the down-scaling method on a 3 GHz 32-bit Pentium processor. Table 7 compares the average execution times for generating a thumbnail image. As the QP becomes larger, the more integer DCT coefficients become zeros. The zero coefficients do not need inverse quantization and inverse transformation so that the execution time should be more reduced for the lager QPs. At the QP values of around 25 that produces frequently used bandwidth for HD size, the proposed method executes almost 3 times faster than the averaging method.

Table 7

Comparison of the average execution time for generating a thumbnail image (msec)

Sequences	Method	Quantization Parameter (QP)
		10	16	25	33	45
Table	Down-scaling	412	316	194	142	116
setting	Proposed	364	220	86	41	20
Playing	Down-scaling	378	294	186	144	117
cards	Proposed	330	202	81	42	21
Rolling	Down-scaling	304	240	144	120	110
tomatoes	Proposed	257	138	41	23	17

6 Conclusion

We have presented a new method in generating thumbnail images from H.264/AVC coded bit streams. The proposed method produces pixel values of thumbnail images by summing the averages of the residual and estimate blocks. The averages of the residual blocks are obtained from the spectrum of residual blocks in the transform domain and those of the estimate blocks are calculated from combinations of reference pixels in the spatial domain. The proposed method not only eliminates the source of the mismatch errors, but also performs integer operations only.

When the proposed method was tested on actual systems, it executed more 3 times faster than the method that decodes the video stream and then down-scales the decoded images. The proposed method produces thumbnail images indistinguishable to the human eye from the ones by the down-scaling method.

Appendix

We derive how the error accumulates as the intra prediction proceeds. From (2), the MDCT domain version of the n^th estimate block EstBLⁿ is obtained as [8], $\begin{array}{l} E s t B L_{M D C T}^{n} \\ = E s t B L_{M D C T}^{h o r, n} + E s t B L_{M D C T}^{v e r, n} \\ = \sum_{i = 1}^{4} {R_{n - 1}^{m, i} \cdot {\tilde{X}}_{M D C T}^{n - 1} \cdot {(S^{i})}^{T}} \\ + \sum_{j = 2}^{4} \sum_{i = 1}^{4} {S^{i} \cdot {\tilde{X}}_{M D C T}^{n - j} \cdot R_{n - j}^{m, i}} \end{array}$ (18)

From (9), $\begin{array}{l} E s t B L_{M D C T}^{h o r, n} \\ = \sum_{i = 1}^{4} {R_{n - 1}^{m, i} \cdot {\tilde{X}}_{M D C T}^{n - 1} \cdot {(S^{i})}^{T}} \\ = \sum_{i = 1}^{4} {R_{n - 1}^{m, i} \cdot (α \cdot \tilde{R} e s_{I n t D C T}^{(n - 1)} ⊘ P F_{i} \\ + ϵ_{r e s}^{(n - 1)} + E s t B L_{M D C T}^{h o r, (n - 1)}) \cdot {(S^{i})}^{T}} \end{array}$ is as follows: $\begin{matrix} {EstBL}_{MDCT}^{hor, n} \\ = \sum_{i = 1}^{4} {R_{n - 1}^{m, i} \cdot {\tilde{X}}_{MDCT}^{n - 1} \cdot {(S^{i})}^{T}} \\ = \sum_{i = 1}^{4} {R_{n - 1}^{m, i} \cdot (α \cdot {\tilde{Res}}_{IntDCT}^{(n - 1)} ø {PF}_{i} \\ + \in_{res}^{(n - 1)} + {EstBL}_{MDCT}^{hor, (n - 1)}) \cdot {(S^{i})}^{T}} \end{matrix}$ (19) where α = 1/2⁶.

The solution of recursive equation (19) is determined as $\begin{array}{l} E s t B L_{M D C T}^{h o r, n} = \\ [\sum_{i_{n} = 1}^{4} {R_{n - 1}^{m, i} \cdot (α \tilde{R} e s_{I n t D C T}^{(n - 1)} ⊘ P F_{i}) \cdot {(S^{i})}^{T}} \\ + \dots + \sum_{i_{n} = 1}^{4} \sum_{i_{n - 1} = 1}^{4} \dots \sum_{i_{0} = 1}^{4} {\prod_{k = 0}^{n - 1} (R_{n - k}^{m, i}) \cdot \\ (α \tilde{R} e s_{I n t D C T}^{n - (k + 1)} ⊘ P F_{i}) \cdot \prod_{k = 0}^{n - 1} {(S^{i})}^{T}}] \\ + [\sum_{i_{n} = 1}^{4} {R_{n - 1}^{m, i} \cdot ϵ_{r e s}^{(n - 1)} \cdot {(S^{i})}^{T}} \\ + \dots + \sum_{i_{n} = 1}^{4} \sum_{i_{n - 1} = 1}^{4} \dots \sum_{i_{0} = 1}^{4} {\prod_{k = 0}^{n - 1} (R_{n - k}^{m, i}) \cdot \\ ϵ_{r e s}^{n - (k + 1)} \cdot \prod_{k = 0}^{n - 1} {(S^{i})}^{T}}] \end{array}$ (20)

$\begin{array}{l} \begin{array}{l} = [Accumulation of horizontal block spectrums] \\ + [Accumulation of horizontal approximation errors] \end{array} \\ E s t B L_{M D C T}^{v e r, n} can be also similarly derived . \\ E s t B L_{M D C T}^{v e r, n} \begin{array}{l} E s t B L_{M D C T}^{n} \\ = E s t B L_{M D C T}^{h o r, n} + E s t B L_{M D C T}^{v e r, n} \\ = Accumulation of estimated block spectrums \\ + Accumulation of approximation errors \end{array} \end{array}$

${EstBL}_{MDCT}^{ver, n}$ can be also similarly derived. $\begin{matrix} {EstBL}_{MDCT}^{n} \\ = {EstBL}_{MDCT}^{hor, n} + {EstBL}_{MDCT}^{ver, n} \\ = Accumulation of estimated block spectrums \\ + Accumulation of approximation errors \end{matrix}$ (21)

Thus, ${\tilde{X}}_{MDCT}^{n}$ becomes $\begin{array}{l} {\tilde{X}}_{M D C T}^{n} = \tilde{R} e s_{M D C T}^{n} + E s t B L_{M D C T}^{n} \\ = Accumulation of reconstructed spectrums \\ + Accumulation of approximation errors . \end{array}$ (22)

Consequently, the spectrum of the reconstructed block must contains the integer approximation errors which are accumulated as the intra prediction proceeds.

References

Taskiran

, Chen

, Albiol

, Torres

, Bouman

C.A.

and Delp

E.J.

, A compressed video database structured for active browsing and search, IEEE Trans on Multimedia6(1) (2004), 103–118.

Song

and Yeo

B.L.

, Fast extraction of spatially reduced image sequences from MPEG-2 compressed video, IEEE Trans Circ and Syst Video Tech9(7) (1999), 1100–1114.

Yeo

B.L.

and Liu

, On the extraction of DC sequence from MPEG compressed video, IEEE Int Conf on Image ProcessingII (1995), 260–263.

Malvar

H.S.

, Hallapuro

, Karczewicz

and Kerofsky

, Lowcomplexity transform and quantization in H.264/AVC, IEEE Trans Circ and Syst Video Tech13(7) (2003), 598–603.

Hallapuro

, Karczewicz

and Marvar

H.S.

, Low complexity transform and quantization, in Joint Video Team (JVT) of ISO/IEC MPEG and ITU-T VCEG, Docs., JVT-B038 and JVTB039, 2002.

Wiegand

and Sullivan

G.J.

, Draft ITU-T recommendation and final draft international standard of joint video specification (ITU-T rec. H.264 U ISO/IEC 14496-10 AVC), 2003.

Chen

and Wu

P.H.

, Transform-domain intra prediction for H.264, IEEE ISCAS2 (2005), 1497–1500.

Kim

E.S.

, Um

T.W.

and Oh

S.J.

, A fast thumbnail extraction method in H.264/AVC video streams, IEEE Trans Consum Electron55 (3) (2009), 1424–1430.

S.K.

and Park

H.W.

, Analysis of IDCT and motion-compensation mismatches between spatial-domain and transform-domain motioncompensated coders, IEEE Trans Circ and Syst Video Tech15(7) (2005), 835–843.

10.

Chen

, Wu

P.H.

and Chen

, Rounding mismatch between spatialdomain and transform-domain, IEEE Trans Circ and Syst Video Tech16(10) (2006), 1286–1293.

11.

Gorden

, Simplified use of 8č8 transforms, in Joint Video Team (JVT) of ISO/IEC MPEG and ITU-T VCEG, Docs., JVTI022, 2003.

12.

Iain

, Richardson

, H.264 and MPEG-4 Video Compression, Wiley, 2004.

13.

H.S.

and Kim

, A novel encoding method for the I-slice of H.264/AVC, IEEE Int Conf on Image Processing, 2010, pp. 4441–4444.

14.

H.264 Reference Software Version JM17.2, 2010. http://iphome.hhi.de/suehring/tml.

15.

Sheikh

H.R.

, Wang

, Bovik

A.C.

and Simoncelli

E.P.

, Image quality assessment: From error visibility to structural similarity, IEEE Trans Image Processing13(4) (2004), 600–612.