INTEGER FAST LAPPED BIORTHOGONAL TRANSFORM VIA APPLICATIONS OF
DCT MATRICES AND DYADIC-VALUED FACTORS FOR LIFTING COEFFICIENT BLOCKSTaizo Suzuki and Hiroyuki Kudo
Faculty of Engineering, Information and Systems, University of Tsukuba
Tsukuba, Ibaraki, 305-8573 Japan
Email: {taizo, kudo}@cs.tsukuba.ac.jp
ABSTRACTThis paper presents a realization of integer fast lapped biorthogonal transform (FLBT) via applications of discrete cosine transform(DCT) matrices and dyadic-valued factors for lifting coefficient
blocks. It is obtained by using the block-lifting factorization as ourprevious work and easy matrix manipulations. The proposed FLBT
has higher coding performance and fewer rounding operations thanthe conventional methods. The practicality of the proposed FLBT
is validated through lossy-to-lossless image compression (coding)simulation which unifies lossy and lossless image coding.
Index Terms— Block-lifting structure, discrete cosine transform (DCT), dyadic-valued factor, fast lapped biorthogonal transform (FLBT), lossy-to-lossless image coding
1. INTRODUCTION
The discrete cosine transform (DCT) and discrete sine transform(DST) [1] have found wide signal processing applications, especially image/video compression (coding) standards such as JPEG
and H.26x series [2, 3]. Both of DCT and DST are classified into
several different types. The type-II DCT (DCT-II) and its inverse
transform, type-III DCT (DCT-III), are usually adopted to the transform and inverse transform part in image/video coding standard, respectively, because the DCT-II has high energy compaction capability and DCTs have many fast implementations. However, theDCT-II generates an unpleasant artifact, i.e., blocking artifact, fora reconstructed image in low-bitrate compression. The M -channel(M = 2k , k ∈ N, k ≥ 2) lapped transform (LT) [4] has been
proposed to overcome the problem. In particular, an M -channel
fast lapped orthogonal transform (FLOT) reduces the blocking artifacts while keeping comparatively fast implementation, because
it is composed of only the postprocessing part, which is also constructed by the M/2-channel DCT-III, M/2-channel type-IV DST(DST-IV) and some 2-channel Hadamard transforms, after the M channel DCT-II implementation.
On another front, several integer LTs [5, 6] based on lifting
structure [7] have been researched for lossy-to-lossless image coding which unifies lossy and lossless image coding. As part ofthis trend, a 4-channel hierarchical lapped biorthogonal transform(HLBT) [8], which was developed FLOT to achieve higher coding
performance and composed of lifting structures, was adopted to thenewest image coding standard JPEG XR [9]. However, the HLBT isa transform researched to seek faster implementation while keeping
coding performance moderately. And then [10] has proposed an integer FLOT with bigger block size, e.g., M = 8 and 16, and higher
coding performance than the HLBT. But, since the FLOT must be

978-1-4799-2341-0/13/$31.00 ©2013 IEEE

800

implemented by two parallel systems, it increases the complexity.
Thereby a transform with more higher coding performance than theconventional methods and as little complexity as possible should be
innovated for the further future in image/video coding.
This paper designs an integer fast lapped biorthogonal transform (FLBT) with big block size and higher coding performance/lesscomplexity than the conventional methods. In this regard, the operations such as multipliers and adders are increased if the block size
is just simply extended, and it is undesired. The proposed FLBT
focuses on the block-lifting structure in our previous work [11, 12].
By using the structures and easy matrix manipulations, the FLBT
can be fast implemented because its most of lifting coefficients arecomposed of DCT matrices and dyadic-valued factors.
Notations: I, J, D and MT are an identity matrix, a reversal
identity matrix, a diagonal matrix with (−1)k (k ∈ N) in the (k, k)element and a transpose of the matrix M, respectively.
2. REVIEW
2.1. M -Channel FLOT and FLBTAn M -channel FLOT can be constructed in polyphase structure fromcomponents with well-known fast-computable algorithms such as
DCT and DST. One of the most elegant solutions is the FLOT whose
polyphase matrix is [4][][]I
0C0E(z) =WΛ(z)W IIWĨ
0 SIV CIII0 CIV
where[1 I
W= √2 I]
[II, Λ(z) =−I
00z−1]
I, Ĩ =[0I]J,0and CII , CIII , CIV and SIV are DCT-II, DCT-III, type-IV DCT(DCT-IV) and type-IV DST (DST-IV) matrices with (M/2) ×(M/2) size, respectively. The (m, n)-element of N -channel(N = 2k , k ∈ N, k ≥ 1) DCT-II and DCT-IV matrices aredefined as√()m (n + 1/2) π2[CII ]m,n =cm cos
NN√()(m + 1/2) (n + 1/2) π2[CIV ]m,n =cos
NN
√
−1
T
where cm = 1/ 2 (m = 0) or 1 (m ̸= 0), CIII = CII= CII,−1T
CIV = CIV = CIV and SIV = D CIV J are established, respectively. Also, the HLBT [8] adopts the scaling factor s. In this paper,ICIP 2013

Fig. 1. Lattice structure of the FLBT and its block-lifting structure (white and black circles mean rounding operations and adders, respectively): (top) lattice structure, (bottom) block-lifting structure.

[[IL

I0]
0,
I]
U,
I

[[IL
I0]
I
0−L I]−1 []UI −U=,I0I
0I]−1[=respectively.
3. THE PROPOSED FLBTFig. 2. Block-lifting structures.

the FLBT inspired by the HLBT as[E(z) =I0]
[sCII0WΛ(z)W
SIV CIII001Cs IV]
WĨ(1)

is used and shown in the top of Fig. 1.
2.2. Block-Lifting Structure
The block-lifting structure [12], shown in Fig. 2, is to improve thebasic lifting structure [7] for an effective implementation of lossy-tolossless image coding. The structure achieves a higher compression
ratio due to fewer rounding operations. In Fig. 2, the analysis input
signal vectors xi and xj , the analysis output and synthesis input
signal vectors yi and yj , the synthesis output signal vectors zi andzj , and the lifting coefficient blocks L and U are presented by
yj = xj + round{Lxi },zi = yi − round{Uyj } = xi ,yi = xi + round{Uyj }zj = yj − round{Lyi } = xj .

In this case, the matrices and its inverse matrices are expressed by801

In this section, we introduce an integer FLBT composed of DCT
matrices and dyadic-valued factors for lifting coefficient blocks.
Theorem: The resulting structure is presented as[][][]−1−z −1I 0I0CII JCIV
2E(z) =
Λ(z) I0 D CIV JCIII I0I[][][]
I0 I CIVI0×
CIV JCIII − CIV I 0Is2 J − CIV I[][][]
I s1 JI00I×0Is0 J I −I 0√√√
where s0 = ( 2 − s)/s, s1 = −s/ 2 and s2 = ( 2s − 1)/s2 ,respectively, as shown in the bottom of Fig. 1. Since s0 , s1 ands2 , however, are non-dyadic-valued (floating-point) factors, they areapproximated to dyadic-values as α/2β (α, β ∈ N) for faster implementation as shown in Table 1.
Proof: As the preparation for lifting factorization, (1) is factorized into several matrices as[]I 0E(z) =ΦΓ(z)ΞΦSW̃J(2)0 D
where][][]I0I
0I0, Γ(z) =WΛ(z)W0 CIV J0 CIII0 CII[][][]
1 IsI 0C0J√
Ξ = II, S=andW̃
=,0 CIII
0 1s I
2 J −I

Φ=[Table 1. Lifting coefficients of the scaling part.
ChannelLifting Coefficients
MFloat.
Dyad.
s00.5747
147/256
8s1 -0.6351 -163/256
s20.3349
43/128s00.5109
33/64
16
s1 -0.6619-85/128s20.3695
47/128

Table 2. Coding gain (CG [dB]).
Channel Conv. FLOTs [10]Prop. FLBTs
M
Float.
Dyad.
Float. Dyad.
8
9.219
9.219
9.447 9.447
16
9.759
9.759
9.845 9.845

respectively. Also, the following equations are used to factorize into
lifting structures.
[][] []I 0I 0I
0=(3)L0 I L1 I
L0 + L1 I[][] []I U0 I U1
I U 0 + U1=(4)
0I0I0I[][] [][]I 0I 0I
0 I 0=(5)
0 N L2 I
NL2 I 0 N[][] [][]
I 0 I U2I U2 N−1 I 0=
(6)
0 N 0I0 N0I
where N is an arbitrary nonsingular matrix, and Lk and Uk (k =0, 1, 2) are arbitrary matrices, respectively. According to [11, 12],the block-lifting factorizations of Γ(z) and Ξ in (2) are produced,
respectively, as[][][]
1−z −1I0I0CII2
Γ(z) =
Λ(z) ICIII I−CIII I0I[][][][]
I
0 I −CIII00I
Ξ=CIII I 0I
CIII I −I 0
and the merged structure of Γ(z) and Ξ is simplified as[][][][]−1−z −1
I 0
I 00 ICII2
Γ(z)Ξ =
Λ(z) I.
CIII ICIII I −I 00I
By using (3)-(6) and the block-lifting factorization in [11], (2) isrepresented by[][]
I 0
J 0E(z) =Γ̃(z)Φ̃SW̃J(7)0 D0 J
where[][]−1−z −1I0CII JCIV2
Λ(z) ICIV JCIII I0I[][]
I00I×
CIV JCIII I −I 0[]C0Φ̃ = IV0CIV[][][][]0 −I
I0 I CIV
I0=.
I0−CIV I 0I−CIV IΓ̃(z) =by using (3)-(6) again. Also, it is clear that[][][][J 0I0 I s1 JISW̃J =0 J
s2 J I 0Is0 J0I][0−I]I.
0(9)Consequently, the block-lifting factorization of FLBT in (1) isachieved by substituting (8) and (9) to (7). □4. EXPERIMENTAL RESULTS
This paper designed the 8 × 16 and 16 × 32 FLBTs.1 In this section,
the proposed FLBTs are compared with the HLBT for JPEG XR [8]and the conventional FLOTs [10] by the coding gain, the number ofrounding operations and the lossy-to-lossless simulation results.
4.1. Coding Gain and Number of Rounding Operations
The coding gain is one of the most important and popular factors fora transform in compression applications. A transform with higher
coding gain compacts more energy into a fewer number of coefficients. As a result, higher objective performance such as PSNR
would be achieved after quantization. The coding gain (CG) is defined as [13]σx222k=0 σxk ∥ fk ∥CG [dB] = 10 log10 ∏M −1

where σx2 is the variance of the input signal, σx2k is the variance of
the k-th subbands and ∥ fk ∥2 is the norm of the k-th synthesis
filter. Table 2 shows the comparisons of coding gain of the conventional FLOTs [10] and the proposed FLBTs with floating-point anddyadic-valued factors for the lifting coefficients in the scaling part.2
It is clear that the most of coding gain are not lost even if the lifting
coefficients are approximated to dyadic-valued factors. Moreover,the proposed FLBTs have higher coding gains than the conventional
FLOTs.
We also compare the number of rounding operations because
a transform with fewer rounding operations achieves more effective lossy-to-lossless coding due to reducing rounding error. Actually, the number is reduced from 9M/2 to 5M/2, i.e., the proposed FLBTs have fewer rounding operations than the conventional
FLOTs [10].
4.2. Lossy-to-Lossless Image Coding

The merged structure of Γ̃(z) and Φ̃ are simplified as[][]−1−z −1I0CII JCIV2Γ̃(z)Φ̃ =Λ(z) I
CIV JCIII I0I[][][]
I0 I CIVI0×(8)CIV JCIII − CIV I 0I−CIV I

802

Finally, the proposed FLBTs are validated in lossy-to-lossless image
coding. To evaluate transform performance fairly, a very common
1 Of course, the FLBTs with bigger block size can be easily designed.

2 The coding gain of the proposed method cannot be accurately comparedwith one of the HLBT for JPEG XR because the dyadic-valued HLBT is implemented by non-separable transform. In the floating-point case, its coding
gain is 8.447[dB].

Table 3. Comparison of lossless image coding (LBR [bpp]).
Test
HLBT Conv. FLOTs [10]Prop. FLBTs
Images[8]8 × 16 16 × 32 8 × 16 16 × 32
Barbara
4.96
4.95
4.85
4.86
4.80
Boat
5.20
5.19
5.16
5.14
5.13
Finger
5.89
5.89
5.75
5.82
5.73
Goldhill
5.12
5.18
5.15
5.12
5.12
Lena
4.64
4.71
4.69
4.62
4.64
Pepper
5.00
4.99
5.00
4.93
4.97

Table 4. Comparison of lossy image coding (PSNR [dB]).
Bitrate HLBT Conv. FLOTs [10]Prop. FLBTs
[bpp]
[8]
8 × 16 16 × 32 8 × 16 16 × 32
Barbara
1.00
36.00
36.59
37.13
37.13
37.43
0.50
30.85
31.76
32.67
32.14
32.87
0.25
27.01
27.83
28.77
28.05
28.90
Boat
1.00
35.21
35.44
35.43
35.63
35.55
0.50
32.02
32.13
32.13
32.39
32.20
0.25
28.80
28.97
29.04
29.21
29.08
Finger
1.00
30.12
30.64
31.44
30.92
31.52
0.50
26.31
26.79
27.32
27.00
27.36
0.25
22.95
23.57
23.97
23.77
24.01
Goldhill
1.00
35.17
35.26
35.36
35.50
35.53
0.50
32.02
32.05
32.20
32.36
32.41
0.25
29.62
29.43
29.59
29.80
29.81
Lena
1.00
38.62
38.47
38.53
39.01
38.90
0.50
35.90
35.59
35.71
36.30
36.25
0.25
32.76
32.37
32.55
33.08
33.00
Pepper
1.00
36.39
36.50
36.44
36.77
36.68
0.50
34.71
34.29
34.02
34.88
34.48
0.25
32.52
31.68
31.84
32.52
32.29

Fig. 3. Comparison of a particular area of the reconstructed image
Barbara (bitrate is 0.25[bpp]): (top) original image and the HLBTfor JPEG XR [8], (middle) the conventional 8 × 16 and 16 × 32
FLOTs [10], (bottom) the proposed 8 × 16 and 16 × 32 FLBTs.

wavelet-based coder SPIHT [14] was adopted for all after the transformed coefficients were rearranged from subband mode to multiresolution mode similar to wavelet transform. Also, the periodic extension was used for image boundaries. Moreover, we used 8-bit grayscale test images with 512×512 size such as Barbara. After the proposed FLBTs, the HLBT and the conventional FLOTs are applied tolossless image coding, the lossy compressed data can be achievedby interrupting the obtained lossless bitstream if it is required. The
lossy-to-lossless image coding results are compared by lossless bit
rate (LBR) and peak signal-to-noise ratio (PSNR) asLBR [bpp] =Total number of bits [bit]Total number of pixels [pixel]

PSNR [dB] = 10 log102552
MSE

where MSE is the mean squared error, respectively. The comparisons of LBR, PSNR and a particular area of the reconstructed im-803

age Barbara (bitrate is 0.25[bpp]) are shown in Table 3, 4 and Fig.
3, respectively.
The proposed FLBTs show better coding performance than theconventional methods. It is considered that the reduction of rounding
operations is one of the most feasible reasons for achieving suchperformance. On the other hand, note that the proposed FLBTs havea simple and fast implementation due to the construction with DCT
matrices and dyadic-valued factors for lifting coefficient blocks.
5. CONCLUSION
In this paper, we have introduced a realization of integer fast lappedbiorthogonal transform (FLBT) via applications of discrete cosine
transform (DCT) matrices and dyadic-valued factors for lifting coefficient blocks. The proposed FLBTs have higher coding gain andfewer rounding operations than the conventional fast lapped orthogonal transforms (FLOTs). They could achieve more effective coding performance for lossy-to-lossless image coding than the conventional methods including a hierarchical lapped biorthogonal transform (HLBT) for the newest image coding standard JPEG XR.

6. REFERENCES[1] K. R. Rao and P. Yip, Discrete Cosine Transform Algorithms,
Academic Press, 1990.
[2] G. K. Wallace, “The JPEG still picture compression standard,”
IEEE Trans. Consum. Electr., vol. 38, no. 1, pp. xviii–xxxiv,Feb. 1992.
[3] T. Wiegand, G. J. Sullivan, G. Bjøntegaard, 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, July 2003.
[4] H. S. Malvar, Signal Processing with Lapped Transforms, Norwood, MA: Artech House, 1992.
[5] T. D. Tran, “The LiftLT: fast lapped transforms via liftingsteps,” IEEE Signal Process. Lett., vol. 7, no. 6, pp. 145–148,
June 2000.
[6] W. C. Fong, S. C. Chan, A. Nallanathan, and K. L. Ho, “Integer lapped transforms and their applications to image coding,”
IEEE Trans. Image Process., vol. 11, no. 10, pp. 1152–1159,
Oct. 2002.
[7] W. Sweldens, “The lifting scheme: A new philosophy inbiorthogonal wavelet constructions,” in Proc. of SPIE 2569,San Diego, CA, July 1995.
[8] C. Tu, S. Srinivasan, G. J. Sullivan, S. Regunathan, and H. S.
Malvar, “Low-complexity hierarchical lapped transform forlossy-to-lossless image coding in JPEG XR/HD Photo,” inProc. of SPIE 7073, San Diego, CA, Aug. 2008.
[9] F. Dufaux, G. J. Sullivan, and T. Ebrahimi, “The JPEG XR
image coding standard,” IEEE Signal Process. Mag., vol. 26,no. 6, pp. 195–199, 204, Nov. 2009.
[10] T. Suzuki and M. Ikehara, “Integer fast lapped orthogonaltransform based on direct-lifting of DCTs for lossless-to-lossy
image coding,” in Proc. of ICASSP’11, Prague, Czech Republic, May 2011, pp. 1525–1528.
[11] T. Suzuki and M. Ikehara, “Integer DCT based on directlifting of DCT-IDCT for lossless-to-lossy image coding,” IEEE
Trans. Image Process., vol. 19, no. 11, pp. 2958–2965, Nov.
2010.
[12] T. Suzuki, M. Ikehara, and T. Q. Nguyen, “Generalized blocklifting factorization of M -channel biorthogonal filter banks forlossy-to-lossless image coding,” IEEE Trans. Image Process.,
vol. 21, no. 7, pp. 3220–3228, July 2012.
[13] G. Strang and T. Nguyen,
Wavelets and Filter Banks,
Wellesley-Cambridge Press, 1996.
[14] A. Said and W. A. Pearlman, “A new, fast, and efficient image
codec based on set partitioning in hierarchical trees,” IEEE
Trans. Circuits Syst. Video Technol., vol. 6, no. 3, pp. 243–250,
June 1996.

804