IEICE TRANS. FUNDAMENTALS, VOL.E96–A, NO.4 APRIL 2013

762

PAPER

M-Channel Fast Hartley Transform Based Integer DCT for
Lossy-to-Lossless Image Coding
Taizo SUZUKI†a) , Member and Hirotomo ASO†† , Fellow

SUMMARY
This paper presents an M-channel (M = 2n (n ∈ N)) integer discrete cosine transforms (IntDCTs) based on fast Hartley transform(FHT) for lossy-to-lossless image coding which has image quality scalability from lossy data to lossless data. Many IntDCTs with lifting structures
have already been presented to achieve lossy-to-lossless image coding. Recently, an IntDCT based on direct-lifting of DCT/IDCT, which means direct
use of DCT and inverse DCT (IDCT) to lifting blocks, has been proposed.
Although the IntDCT shows more eﬃcient coding performance than any
conventional IntDCT, it entails many computational costs due to an extra
information that is a key point to realize its direct-lifting structure. On theother hand, the almost conventional IntDCTs without an extra information
cannot be easily expanded to a larger size than the standard size M = 8,or the conventional IntDCT should be improved for eﬃcient coding performance even if it realizes an arbitrary size. The proposed IntDCT does notneed any extra information, can be applied to size M = 2n for arbitrary n,
and shows better coding performance than the conventional IntDCTs without any extra information by applying the direct-lifting to the pre- and postprocessing block of DCT. Moreover, the proposed IntDCT is implemented
with a half of the computational cost of the IntDCT based on direct-liftingof DCT/IDCT even though it shows the best coding performance.
key words: direct-lifting, fast Hartley transform (FHT), integer discretecosine transform (IntDCT), lossy-to-lossless image coding

1.

Introduction

Discrete cosine transform (DCT) [1] has several types, and
DCT type-II (DCT-II) and -III (DCT-III) are commonly
called DCT and inverse DCT (IDCT). They are applied tolossy image/video compression (coding) such as the international standard JPEG [2] and H.26x family [3], because
DCT has excellent energy compaction capability, many
fast implementations [4]–[7] and numerous applications on
JPEG devices. Since it is compatible with the lossy JPEG,
DCT is especially promising.
Recently, with the rapid development of multimedia
devices such as media tablets and smartphones, and the continual expansion of broadband, lossy-to-lossless image coding, which has image quality scalability from lossy data tolossless data, is demanded to respond to the various needs.
To achieve it, many integer DCTs (IntDCTs) based on lifting
structures [8]–[10] have been proposed [11]–[13]. We also
Manuscript received July 4, 2012.
Manuscript revised October 19, 2012.
†
The author is with the Faculty of Engineering, Information and Systems, University of Tsukuba, Tsukuba-shi, 305-8573
Japan.
††
The author is with the Department of Electrical and Electronic Engineering, College of Engineering, Nihon University,
Koriyama-shi, 963-8642 Japan.
a) E-mail: taizo@cs.tsukuba.ac.jp
DOI: 10.1587/transfun.E96.A.762

have proposed a direct-lifting which is a so eﬀective structure for lossy-to-lossless image coding [14]. The IntDCT,
however, requires an extra information because both of atransform and its inverse transform are required, i.e., bothof DCT and IDCT must be simultaneously implemented.
As its solution, DCT is separated to the pre- and postprocessing block as the first stage. If at least one of the pre/post-processing blocks is a symmetric orthogonal matrix,
the DCT may perform eﬃcient lossy-to-lossless image coding due to application of a direct-lifting. Although our previous work in [15] has such structure using a direct-liftingof Walsh-Hadamard transform (WHT) as the pre-processing
block, it should be improved for more eﬃcient coding performance because there are many rounding operations in the
post-processing block. Also, the conventional IntDCTs except for [13], [14] cannot be easily expanded to a larger size
M = 2n (n ∈ N) than the standard size M = 8. Sucharbitrary size is needed for the super high resolution standards as 4K Digital Cinema (4096 × 2160) and 8K Super
Hi-Vision (7680 × 4320). Nevertheless, many rounding operations newly generated cause worse coding performancedue to their rounding error when the IntDCT has a larger
size than M = 8.
On the other hand, faster DCT algorithms without multipliers are widely researched for real time encode/decode
implementations [15]–[17]. We also have proposed a multiplierless fast DCT based on fast Hartley transform (FHT)[18]. The structure has an FHT and the residue orthogonal matrix with (M − 2)/2 rotation matrices as the pre- andpost-processing blocks, respectively. It is easy that the DCT
obtains an arbitrary size M = 2n .
In this paper, we adopt direct-liftings for both of thepre- and post-processing blocks of DCT based on FHT
to achieve eﬀective lossy-to-lossless image coding. We
can implement it without any complex calculation because
direct-lifting can be easily adopted for a combination of
two symmetric orthogonal matrices. Both FHT as the preprocessing block and the residue orthogonal matrix as thepost-processing block are symmetric orthogonal matrices.
Also, two-dimensional (2-D) separable block transform isconsidered to achieve a more eﬀective implementing. The
resulting simple structure avoids a propagation of rounding
error generated by cascading rounding operations. As a result, the proposed IntDCT does not need any extra information, can be applied to size M = 2n for arbitrary n, and shows
better coding performance than the conventional IntDCT
without any extra information. Moreover, the proposed Int-

c 2013 The Institute of Electronics, Information and Communication Engineers
Copyright SUZUKI and ASO: M-CHANNEL FHT BASED INTDCT FOR LOSSY-TO-LOSSLESS IMAGE CODING

763
Table 1

The comparison of IntDCTs.

Eﬃcient coding
performance
[11]
[12]
[13]
[14]
[15]
Prop.

Arbitrary size
M = 2n(Best)(2nd best)No sideinformation






DCT is implemented with a half of the computational cost of
the IntDCT based on direct-lifting of DCT/IDCT [14] eventhough it shows the best coding performance. Table 1 summarizes the comparison of IntDCTs.
Notations: I, J, {·}[N] , {·}T and diag{M, N} are an identity matrix, a reversal identity matrix, N × N matrix, transpose of a matrix and a block diagonal matrix, respectively.
2.

Review

2.1 Discrete Cosine Transform (DCT)
Not only is DCT [1] often used for the international standard
JPEG [2] and H.26x family [3], but also numerous devices
for DCT have been developed. The (m, n)-element of Mchannel DCT-II matrix C, DCT-III matrix D and DCT-IV
matrix E are defined asm (n + 1/2) π
2cm cos[C]m,n =MM(m + 1/2) nπ2[D]m,n =cn cosMM(m + 1/2) (n + 1/2) π2[E]m,n =cos
MM
where D√= C−1 = CT , E−1 = ET = E, 0 ≤ m, n ≤ M − 1,
ck = 1/ 2 (k = 0) or 1 (k  0), respectively. For simplicity, let M be defined as M = 2n (n ∈ N). Also, many fast
implementations of DCT have been widely researched [4]–[7]. For example, Chen’s fast implementation of M-channel
DCT C[M] in [4] is the most popular structure as



1
0
C
I J
C[M] = √ PChen [M/2](1)0E[M/2] J −I
2where PChen is an M × M permutation matrix. In case of
M = 8, it is simplified by 4 rotation matrices with π/4 angles
and 4-channel DCT-II/-IV as shown in Fig. 1(a). Note thatany coding system by DCT is limited to operation in only
lossy image coding because distortion of the decoded image
is unavoidable with these lossy algorithms.
2.2 Fast Hartley Transform (FHT)The FHT is a tool for the frequency analysis, design andimplementation of digital signal processing algorithms andsystems like DCT. It is strictly symmetrical concerning the

Fig. 1[18].

8-channel DCT C: (a) Chen’s DCT in [4], (b) FHT based DCT in

Fig. 28-channel FHT PH.

transformation and its inverse, i.e., a symmetric orthogonal
matrix. The (m, n)-element of M-channel FHT matrix H isdefined as [19]


 
2mnπ
1
H m,n = √ cas
M
M
where cas θ = cos θ + sin θ and H −1 = H T = H. Since
H is not according to the frequency band order, let H withthe correct order be PH where P is a permutation matrix. In
case of M = 8, it is simplified by 13 rotation matrices with
π/4 angles as shown in Fig. 2.
2.3 Direct-Lifting Structure
Lifting structure, also known as a ladder structure, is an implementation method of wavelet transforms originally proposed [8]–[10] by Sweldens. It is a special type of lattice
structure: a cascading construction using only elementary
matrices, that is, identity matrices with a single nonzero oﬀdiagonal element. Figure 3(a) shows a standard lifting struc-IEICE TRANS. FUNDAMENTALS, VOL.E96–A, NO.4 APRIL 2013

764

Fig. 4 A direct-lifting structure (white circles mean rounding
operations).

where MN = NM = I, and yi and ti are the output signals of xi and si , respectively, as shown on the left side ofFig. 4. Then, the matrix diag{M, N} can be redefined to lifting structures as

 




M 0
0 I I 0 I −N I 0=.
0 N−I 0 M I 0 I M I
Fig. 3 A lifting structure (white circles mean rounding operations): (a) astandard lifting, (b) a block-lifting.

ture. In this case, the lifting matrix and its inverse matrix are
as follows:




−1 
1 −T
1 T
1 T
=
.
,
0 1
0 1
0 1
Then, they are represented byyi = xi + round{T x j }z = yi − round{T y j } = xi
→ izj = yj = xj
yj = xj
where T and round{.} are a lifting coeﬃcient and a rounding
operation, respectively. The lifting structures with rounding
operation can achieve integer-to-integer transform for lossyto-lossless image coding.
To obtain more eﬃcient transform performance than atransform by standard lifting, block-lifting as a class of lifting structure has been proposed [20]. Instead of a lifting
coeﬃcient T , we adopt a lifting matrix (block) T. Suchblock-lifting can be expressed as follows:




−1 
I −T
I T
I T
=
,
0 I
0 I
0 I

This is called direct-lifting because two matrices M and N
are directly used to lifting blocks. To obtain lossless data, arounding operation is applied to each lifting step because it
achieves an integer-to-integer transform without any distortion in the quantization part in image coding flow. Commonly, an extra information is used to implement directlifting because both of a transform M and its inverse transform N must be implemented simultaneously [14]. But theextra information is not required if M and N have the symmetric orthogonality, i.e., N = M−1 = MT =M.
3.

M-Channel FHT Based Integer DCT (IntDCT)

3.1 FHT Based DCT
A fast FHT based DCT [18] is definitely diﬀerent fromthe most popular Chen’s structure in (1). The structure isseparated to a permutation matrix PT , FHT H as the preprocessing block, the residue orthogonal matrix Q as thepost-processing block and a diagonal matrix D with eitherof +1 or −1 values as follows:
C = DQHPT
where
I[M/2+1]0⎡0⎢⎢⎢1⎢⎢⎢0 JCJ⎢
Q = ⎢⎢⎢
0
⎢⎢⎣0
0 SJ
D=

and
z = yi − round{Ty j } = xi
yi = xi + round{Tx j }→ i,zj = yj = xj
yj = xj
where xi , x j , yi , y j , zi and z j are the input and output signal
matrices, as shown in Fig. 3(b). Similar to standard lifting,it is clear that the reconstructed signals zi and z j are exactly
the same value as xi and x j . The block-lifting would be eﬃcient for lossy-to-lossless image coding due to having fewer
number of rounding operations† .
Moreover, we have proposed direct-lifting as a classof block-lifting [14]. First, we process the two individual
signals xi and si by a matrix M and its inverse matrix N, i.e.,
  
 
yi
M 0 xi=ti
0 N si(2)0−I[M/2−1]⎤
0 0 ⎥⎥⎥
0 JS ⎥⎥⎥⎥⎥
1 0 ⎥⎥⎥⎥
⎦
0 −C


⎧
 (k+1)π ⎪⎪⎨ [C]k,k = cos 2M ⎪⎪
⎩ [S]k,k = sin (k+1)π2M

for 0 ≤ k ≤ M/2 − 2 as shown in Fig. 1(b). Note that thisstructure can be easily expanded to a larger size than M =8. However, if this DCT is factorized into the lifting partand the scaling part according to [18], it is inapplicable tolossy-to-lossless image coding due to M multipliers as thegenerated scaling part.
†
When the number of rounding operations increases, the quantization error simultaneously increased aﬀects the subband energy
compaction [13].

SUZUKI and ASO: M-CHANNEL FHT BASED INTDCT FOR LOSSY-TO-LOSSLESS IMAGE CODING

765

Fig. 5 M-channel FHT based IntDCT (white circles mean rounding operations): (a) by using 1-D
transform in each of vertical and horizontal directions, (b) by making full use of 2-D separable blocktransform.

3.2 Direct-Lifting of Pre-/Post-Processing Blocks of DCT
To achieve lossy-to-lossless image coding without any extra information, we apply direct-lifting factorization to FHT
and the residue orthogonal matrix as the pre- and postprocessing blocks of DCT, respectively.
Generally, it is careful that the direct-lifting requires anextra information because both transform M and its inverse
transform N (N  M) must be implemented. However, we
can easily come up with a simple realization for lossy-tolossless image coding without any extra information. First,
an hM × wM (h, w ∈ N) image X is segmented to M × M
block xk (0 ≤ k ≤ hw − 1). The segmented block xk issequentially transformed by hw DCTs as follows:T
yT0 , yT1 , · · · , yThw−1 =Tdiag {C, C, · · · , C} · xT0 , xT1 , · · · , xThw−1
We process each combination of the two adjacent signal
blocks xe and xo (e and o are an even and an odd value,
respectively) by DCT, i.e.,
  
 
ye
C 0 xe=yo
0 C xo




 
D 0 Q 0 H 0 PT 0 xe=
(3)
0 D 0 Q 0 H 0 PT xo
where ye and yo are the output signals of xe and xo , respectively. Then, a combination of the pre- and post-processing
blocks in (3) is factorized into five step direct-liftings as follows:



Q 0 H
0 Q 0

 


0
I
0 I Q
=
H
−Q I 0 I
I
0 I −H I×
HI
H −Q I 0


0
I
(4)

(4) is shown in Fig. 5(a). Consequently, the two adjacent
blocks separated from an image can be simultaneously implemented by (4), and it does not require any extra information. Since PT and D have no necessity to be factorized
into lifting structures, we have just realized a novel IntDCTby (3) and (4). As mentioned in Sect. 2.3, although an extra information is often used to implement direct-lifting, theproposed structure does not require it due to the symmetricorthogonalities of H and Q. The proof of (4) is presented in
the Appendix.
3.3 Making Full Use of Two-Dimensional (2-D) Separable
Block Transform
A DCT matrix C is commonly applied into an M × M input
signal x in column- and row-wise (vertical and horizontal
direction) separately. The output signal y is expressed byT
y = C (Cx)T = CxCT .
(5)
We call it a 2-D separable block transform [14]. Since the
DCT can be factorized as C = DQHPT in (2), (5) is represented by
y = DQHPT x(DQHPT )T = DQHPT xPH T QT DT .
This equation means the 2-D separable block transforms are
implemented according to the following order as shown inIEICE TRANS. FUNDAMENTALS, VOL.E96–A, NO.4 APRIL 2013

766

Fig. 6block.

A 2-D separable block transform: (a) a standard transform, (b) an ordered transform to eachFig. 6(b).
(a) A 2-D separable block transform by PT is implemented.
(b) A 2-D separable block transform by H is implemented
after (a) is implemented.
(c) A 2-D separable block transform by Q is implemented
after (b) is implemented.
(d) A 2-D separable block transform by D is implemented
after (c) is implemented.
Also, let the 2-D separable block transforms of x by PT , H,
Q and D be defined as
PT xP  PT2D (x),HxH T  H2D (x),QxQT  Q2D (x) and DxDT  D2D (x),respectively. Therefore, (4) are represented by
Q2D (x)
H2D (x)00=0
Q2D (x)
0
H2D (x)




I
0
I
0 I Q2D (x)I
H2D (x) − Q2D (x) I−Q2D (x) I 0I −H2D (x)
I
0
×
0
I
H2D (x) I
as shown in Fig. 5(b). Such lifting matrices are more effective for lossy-to-lossless image coding than lifting matrices without considering the 2-D separable block transform, because the number of rounding operations per an
one-dimensional (1-D) transform of M ×1 signals is reduced
from (5M − 4)/2 to (5M − 4)/4 in each block and rounding
error is also reduced much more. Table 2 shows the numberof rounding operations in each IntDCT. It is clear that the
number of rounding operations of the proposed structure isless than the previous works except for [12].
4.

Experimental Results

The resulting FHT based IntDCT and the conventional IntDCTs in [11]–[15] (M = 8) are applied to lossy-to-losslessTable 2 The number of rounding operations in each M-channel IntDCT.
(N[M/2] indicates the number of rounding operations in M/2-channel IntDCT in [13].)
Size
M

[11]

[12]

Conv. IntDCT
[13]

[14]

[15]

Prop.
IntDCT

8
M

21
–

8
–

23

12

9
4 M + N[M/2]

3
2M

21
–

5
4M −1

9

image coding. Also, since the conventional methods in [11],[12], [15] are inapplicable to a larger size DCT than M = 8,
only the proposed IntDCT and the conventional IntDCTs in[13], [14] (M = 16) are applied to lossy-to-lossless image
coding as an example of larger sizes. An integer-to-integertransform can be obtained by using a rounding operation
at each lifting step. As described above, only the conventional IntDCT in [14] requires a side information, and theothers do not require one. To evaluate transform performance fairly, after the images were transformed, they wereencoded by the set partitioning in hierarchical trees (SPIHT)
progressive image transmission algorithm with PSNR scalability [21]. Test images are several 512 × 512 grayscale
standard images such as Barbara and Lena, respectively. In
lossy image coding, we compare their peak signal-to-noise
ratios (PSNRs):


2552
,
PSNR [dB] = 10 log10
MSE
where MSE is the mean squared error, for three standard
images as shown in Table 3. In lossless image coding, we
compare their lossless bit rates (LBRs) [bpp]:
LBR [bpp] =Total number of bits [bit]Total number of pixels [pixel]

as shown in Table 4.
Although our previous work in [14] shows the best performance with an extra information, the proposed IntDCT is
implemented with a half of the computational cost of [14],since the proposed one does not require any extra information. It is, however, clear that the proposed IntDCT is better

SUZUKI and ASO: M-CHANNEL FHT BASED INTDCT FOR LOSSY-TO-LOSSLESS IMAGE CODING

767

Test
image
BarbaraFingerGoldhill

Lena

PepperTable 3Lossy image coding results (PSNR [dB]).

Bit rate
[bpp]

DCT
[1]

[11]

M=8
Conv. IntDCT
[12]
[13]
[14]

0.25
0.50
1.00
0.25
0.50
1.00
0.25
0.50
1.00
0.25
0.50
1.00
0.25
0.50
1.00

26.95
30.70
36.08
22.55
25.57
29.70
29.38
31.99
35.40
31.88
35.60
39.23
31.43
34.49
37.04

26.94
30.67
35.97
22.54
25.55
29.66
29.36
31.94
35.27
31.87
35.53
38.95
31.40
34.41
36.83

26.73
30.40
35.84
22.21
25.36
29.47
29.13
31.80
35.19
31.86
35.49
38.93
31.43
34.33
36.71

Table 4

Lossless image coding results (LBR [bpp]).

Test
image
Airplane
BaboonBarbaraBoat
BridgeElaineFingerGoldhill
Grass
Lena
Pepper
Tank

26.94
30.67
35.96
22.55
25.55
29.67
29.36
31.96
35.28
31.87
35.55
38.94
31.41
34.42
36.82

[11]

M=8
Conv. IntDCT
[12]
[13]
[14]

4.44
6.27
4.98
5.20
6.00
5.23
6.07
5.17
6.17
4.65
4.96
5.20

4.40
6.28
4.97
5.19
6.00
5.25
6.06
5.16
6.18
4.63
4.96
5.20

4.43
6.27
4.98
5.20
6.00
5.23
6.06
5.16
6.17
4.65
4.96
5.20

4.36
6.27
4.94
5.18
5.99
5.22
6.06
5.14
6.17
4.61
4.94
5.19

than the conventional methods without any extra information in both lossy and lossless image coding, because theproposed IntDCT has a few number of rounding operations
as shown in Table 2 and the simple structure avoids a propagation of rounding error generated by cascading rounding
operations. Note that Chokchaitam’s IntDCT in [12] withthe fewest rounding operations in case of M = 8 cannot be
performed enough due to several removed scaling factors.
5.

Conclusion

This paper presented an M-channel (M = 2n (n ∈ N)) fast
Hartley transform (FHT) based integer discrete cosine transforms (IntDCTs) for lossy-to-lossless image coding. It was
obtained by applying direct-lifting factorization to each of
FHT and the residue orthogonal matrix as the pre- and postprocessing blocks of DCT, respectively, and considering a
two-dimensional (2-D) separable block transform. The resulting IntDCT shows better coding performance than theconventional IntDCT without any extra information, whichcauses its handling trouble, due to a few rounding operations. Moreover, the proposed IntDCT can easily achieve an
arbitrary size M = 2n , which is required for the super highresolution standards as 4K Digital Cinema (4096 × 2160)

26.95
30.68
36.03
22.55
25.56
29.70
29.37
31.97
35.36
31.89
35.59
39.13
31.42
34.46
36.97

[15]

Prop.
IntDCTM = 16
Conv. IntDCT
Prop.
[13]
[14]
IntDCT

26.94
30.68
35.98
22.55
25.56
29.68
29.38
31.96
35.31
31.88
35.57
38.99
31.41
34.41
36.85

26.94
30.67
36.00
22.54
25.56
29.69
29.37
31.96
35.33
31.88
35.58
39.07
31.41
34.45
36.92

27.95
31.79
36.88
23.24
26.57
30.79
29.71
32.33
35.51
32.67
36.10
39.04
32.06
34.56
36.77

27.96
31.84
37.08
23.24
26.58
30.85
29.73
32.38
35.69
32.70
36.21
39.44
32.09
34.65
37.03

[15]

Prop.
IntDCTM = 16
Conv. IntDCT
Prop.
[13]
[14]
IntDCT

4.40
6.27
4.97
5.20
6.00
5.23
6.06
5.16
6.17
4.63
4.96
5.20

4.39
6.27
4.96
5.18
5.99
5.23
6.06
5.15
6.17
4.62
4.94
5.19

4.44
6.22
4.85
5.14
6.00
5.18
5.84
5.11
6.11
4.61
4.94
5.20

4.33
6.21
4.79
5.10
5.99
5.16
5.83
5.08
6.11
4.56
4.91
5.19

27.96
31.83
37.04
23.24
26.58
30.84
29.72
32.38
35.66
32.70
36.19
39.37
32.09
34.64
37.00

4.36
6.21
4.80
5.11
5.99
5.17
5.83
5.08
6.11
4.57
4.91
5.19

and 8K Super Hi-Vision (7680 × 4320), than M = 8.
References[1] K.R. Rao and P. Yip, Discrete Cosine Transform Algorithms, Academic Press, 1990.
[2] ISO/IEC 10918-1, Information technology — Digital compression
and coding of continuous-tone still images: Requirements andGuidelines.
[3] ISO/IEC 14496-10, Information technology — Coding of audiovisual objects — Part 10: Advanced Video Coding.
[4] W.H. Chen, C.H. Smith, and S.C. Fralick, “A fast computationalalgorithm for the discrete cosine transform,” IEEE Trans. Commun.,vol.CON-25, no.9, pp.1004–1009, Sept. 1977.
[5] Z. Wang, “Fast algorithms for the discrete W transform and for thediscrete Fourier transform,” IEEE Trans. Acoust. Speech Signal Process., vol.ASSP-32, no.4, pp.803–816, April 1984.
[6] B.G. Lee, “A new algorithm to compute the discrete cosine transform,” IEEE Trans. Acoust. Speech Signal Process., vol.ASSP-32,
no.6, pp.1243–1245, June 1984.
[7] Z. Wang, “On computing the discrete Fourier and cosine transforms,” IEEE Trans. Acoust. Speech Signal Process., vol.ASSP-33,
no.4, pp.1341–1344, April 1985.
[8] W. Sweldens, “The lifting scheme: A new philosophy in biorthogonal wavelet constructions,” Proc. SPIE 2569, 1995.
[9] W. Sweldens, “The lifting scheme: A custom-design construction ofbiorthogonal wavelets,” Appl. Comput. Harmon. Anal., vol.3, no.2,
pp.186–200, April 1996.

IEICE TRANS. FUNDAMENTALS, VOL.E96–A, NO.4 APRIL 2013768

[10] W. Sweldens, “The lifting scheme: A construction of second generation wavelets,” SIAM J. Math. Anal., vol.29, no.2, pp.511–546,
1997.
[11] S. Fukuma, K. Ohyama, M. Iwahashi, and N. Kambayashi, “Lossless 8-point fast discrete cosine transform using lossless Hadamardtransform,” IEICE Technical Report, DSP99-103, Oct. 1999.
[12] S. Chokchaitam, M. Iwahashi, and S. Jitapunkul, “A new unified
lossless/lossy image compression based on a new Integer DCT,”
IEICE Trans. Inf. & Syst., vol.E88-D, no.2, pp.403–413, Feb. 2005.
[13] T. Suzuki and M. Ikehara, “M-channel integer discrete cosine transform using block lifting factorization,” IEICE Trans. Fundamentals(Japanese Edition), vol.J92-A, no.11, pp.888–900, Nov. 2009.
[14] T. Suzuki and M. Ikehara, “Integer DCT based on direct-lifting of
DCT-IDCT for lossless-to-lossy image coding,” IEEE Trans. Image
Process., vol.19, no.11, pp.2958–2965, Nov. 2010.
[15] T. Suzuki and M. Ikehara, “Integer discrete cosine transform via
lossless Walsh-Hadamard transform with structural regularity forlow-bit-word-length,” IEICE Trans. Fundamentals, vol.E93-A, no.4,
pp.734–741, April 2010.
[16] Y.J. Chen, S. Oraintara, T.D. Tran, K. Amaratunga, and T.Q.
Nguyen, “Multiplierless approximation of transforms with adderconstraint,” IEEE Signal Process. Lett., vol.9, no.11, pp.344–347,
Nov. 2002.
[17] O. Nishida, M. Iwahashi, and N. Kambayashi, “A word length allocation method for multipliers of the lossless DCT,” IEICE Trans.
Fundamentals (Japanese Edition), vol.J86-A, no.6, pp.694–702,
June 2003.
[18] T. Suzuki, Y. Tanaka, M. Ikehara, and H. Aso, “Multiplierless fastalgorithm for DCT via fast Hartley transform,” Proc. ICASSP’12,
pp.3469–3472, Kyoto, Japan, March 2012.
[19] H.J. Meckelburg and D. Lipka, “Fast Hartley transform algorithm,”
IET Electron. Lett., vol.21, no.8, pp.311–313, April 1985.
[20] T. Suzuki, M. Ikehara, and T.Q. Nguyen, “Generalized block-lifting
factorization of M-channel biorthogonal filter banks for lossy-tolossless image coding,” IEEE Trans. Image Process., vol.21, no.6,
pp.3220–3228, 2012.
[21] A. Said and W.A. Pearlman, “A new, fast, and eﬃcient image codec
based on set partitioning in hierarchical trees,” IEEE Trans. Circuits
Syst. Video Technol., vol.6, no.3, pp.243–250, June 1996.

Appendix:

Direct-Lifting Factorization of Pre-/PostProcessing of DCT

The proof of this derivation can be accomplished by using
a direct-lifting and a simple matrix manipulation. First, thedirect-lifting factorization can be easily applied to each of
FHT and the residue orthogonal matrix, respectively, because FHT H and the residue orthogonal matrix Q are symmetric orthogonal matrices, i.e., their inverses are themselves. However, to achieve a more eﬀective implementation than a simple application of direct-lifting factorization
to them, the only pre-processing block diag{H, H} is factorized into direct-liftings at the first step as follows:





 
H 0
0 I I 0 I −H I 0(A· 1)=
I H I−I 0 H I 0
0 H
where HH = I. Next, if the first matrix in (A· 1) ismultiplied by the right side of the post-processing block
diag{Q, Q} as


 

0 Q
Q 0 0 I=,−Q 0
0 Q −I 0

this matrix is factorized into the following direct-liftings.



 

0
0 Q
I
0 I Q I(A· 2)=−Q 0−Q I 0 I −Q I
Finally, (4) is obtained by connecting (A· 1) and (A· 2). This
completes the proof.

Taizo Suzuki
received the B.E., M.E.
and Ph.D. degrees in electrical engineering from
Keio University, Japan, in 2004, 2006 and 2010,
respectively. He joined Toppan Printing Co.,
Ltd., Tokyo, Japan, from 2006 to 2008. After
that, he was a RA of Global COE (C-12) from2008 to 2011, a Research Fellow of the JSPS
from 2010 to 2011, and a Visiting Scholar in the
ECE Dept., UCSD, La Jolla, CA from 2010 to2011, respectively. Then, he was an AssistantProfessor in the EEE Dept., College of Eng.,
Nihon University, Koriyama, Japan from 2011 to 2012. He is currently an
Assistant Professor in the Faculty of EIS, University of Tsukuba, Tsukuba,
Japan. His current research interests are filter bank design and its application for image/video.

Hirotomo Aso
received the B.E., M.E.,
and Ph.D. degrees in electrical engineering fromTohoku University, Japan, in 1968, 1970, and1974, respectively. He was with the Department
of Information Engineering, Tohoku University
in 1973, and later joined the Faculty of Engineering, Nagoya University from 1979 to 1986.
He was a professor in the Faculty of Engineering, Tohoku University till 2009. He is now
a Professor in College of Engineering, Nihon
University. He is presently engaged in researchof character pattern recognition, cellular automata, concurrent program
schema, parallel processing, and theory of systolic algorithms. He has received the Achievement Award (Gyoseki-sho) of IEICE in 1992. Dr. Asois a member of IEEE, ACM, IPSJ, and JSAI.