Proceedings of 2010 IEEE 17th International Conference on Image Processing

September 26-29, 2010, Hong Kong

REALIZATION OF LOSSLESS-TO-LOSSY IMAGE CODING
COMPATIBLE WITH JPEG STANDARD BY DIRECT-LIFTING OF DCT-IDCT
Taizo Suzuki and Masaaki Ikehara
Department of Electronics and Electrical Engineering, Keio University
Yokohama, Kanagawa 223-8522, Japan
Email: {suzuki, ikehara}@tkhm.elec.keio.ac.jp
ABSTRACTA discrete cosine transform (DCT) can be easily implemented insoftware and hardware for the JPEG and MPEG formats. Recently,
some integer DCTs (IntDCTs) for lossless-to-lossy image coding
have been proposed, but they do not satisfy enough compatibility
with JPEG standard. This paper proposes a realization of losslessto-lossy image coding which has higher compatibility with it thanthe conventional IntDCTs. Our IntDCT is implemented by directlifting of DCT and inverse DCT (IDCT) and has high performancein lossless image coding compared with any IntDCT while keeping
high compatibility with JPEG standard. Finally, our method is validated by its application to lossless-to-lossy image coding.
Index Terms— integer discrete cosine transform (IntDCT),
direct-lifting, lossless-to-lossy image coding, JPEG standard
1. INTRODUCTION
JPEG [1] is an international standard in image coding. Discretecosine transform (DCT) [2] and differential pulse code modulation(DPCM) are separately applied to lossy and lossless image coding,respectively. DCT can be classified into types I to VIII and has excellent energy compaction capability, numerous fast implementations
and numerous applications on JPEG devices. DCT type-II (DCTII) and -III (DCT-III) are commonly called DCT and inverse DCT(IDCT). Since DCT and IDCT are compatible with the lossy JPEG,
they are especially promising.
Recently, with the rapid development of hardware such as PCs
and mobile phones, and the continual expansion of broadband,
lossless-to-lossy image coding, which is the unification of lossy andlossless image coding, is demanded to obtain higher quality andcompression ratio. Such lossless-to-lossy image coding has alreadybeen achieved by JPEG2000 [3] and HD Photo (JPEG-XR) [4].
These next-generation standards are based on discrete wavelet transform (DWT) and the hierarchical lapped biorthogonal transform(HLBT), respectively. However, the existing state-of-the-art technologies such as JPEG2000 and JPEG-XR cannot be substituted for
the JPEG standard because JPEG is most frequently used and its
compressed data is spread far over the world. This means that thetransform for lossless-to-lossy image coding should have compatibility with JPEG. Additionally, an image encoded by such transform
can also be decoded by the existing JPEG decoder if lossless data is
not demanded.
This work is supported in part by a Grant-in-Aid for the Global Centerof Excellence for High-Level Global Cooperation for Leading-Edge Platformon Access Spaces from the Ministry of Education, Culture, Sport, Science,
and Technology in Japan.

978-1-4244-7993-1/10/$26.00 ©2010 IEEE

389

Up to now, many integer DCTs (IntDCTs) [5–8], which is constructed by integer coefficients, lifting structures [9] and rounding
operations, have been proposed for lossless-to-lossy image coding.
In this regard, however, high compatibility with JPEG standard isdesired, but the conventional IntDCTs do not satisfy enough compatibility with it.
This paper proposes a simple lifting structure, which is called
direct-lifting, using only DCT and IDCT matrices for every lifting
block. Also, two-dimensional block transform (2DBT) applied toevery lifting block achieves better coding performance because thetotal number of rounding operations are reduced. As a result, our IntDCT has high performance in lossless image coding compared withany IntDCT while keeping high compatibility with JPEG standard.
Although our method requires a small side information block (SIB),
it is validated by its application to lossless-to-lossy image coding.
Notations: I, MT and diag{.} are the identity matrix, transposeof a matrix M and block diagonal matrix, respectively. For simplicity, we omit matrix sizes when they are obvious.
2. REVIEW
2.1. Block-Lifting Structure
Lifting, also known as a ladder structure, is an implementation
method of wavelet transforms originally proposed by Sweldens [9].
It is a special type of lattice structure: a cascading construction using only elementary matrices, that is, identity matrices with a single
nonzero off-diagonal element. Also, the block-lifting structure [10],shown in Fig. 1, is known as an efficient lifting structure for losslessto-lossy coding. It achieves a higher compression ratio because it
can merge many rounding operations. The left part in Fig. 1 showsa block-lifting structure before rounding operations are merged, andthe right part in Fig. 1 shows the structure after rounding operations
are merged. It is clear that the number of rounding operations is reduced from N 2 to N when the size of the lifting block T is N × N .
In the right part in Fig. 1, the analysis input signal vectors xi andxj , the analysis output and synthesis input signal vectors yi and yj ,the synthesis output signal vectors zi and zj , and lifting block T are
presented byyi = xi + round[Txj ],yj = xj ,zi = yi − round[Tyj ] = xi ,z j = yj = xj .

andICIP 2010

Fig. 1. Block-lifting structure (white circles: rounding operations): (left) before rounding operations are merged, (right) after they are merged.

In this case, the block-lifting matrix and its inverse matrix are as
follows:


I T
0 I





I T
0 I

and

−1


=


I −T
.
0 I

2.2. Discrete Cosine Transform (DCT) and Integer Discrete Cosine Transform (IntDCT)This paper describes only types DCT-II and -III which are commonly
called DCT and IDCT [2], respectively. These are often used forimage and video coding such as JPEG and MPEG. The m-column
and n-row elements of M -channel DCT and IDCT matrices C and
D are defined as






2
m (n + 1/2) π
cm cosMM(m + 1/2) nπ2[D]m,n =cn cosM
M[C]m,n =



√1
2

1



(m = 0)(m = 0)

and

cn =

√1
2

1

(n = 0),(n = 0)nrespectively. For simplicity, let us define M = 2 (n ∈ N). Also,
many fast implementations of DCT and IDCT have been widely researched. Note that the coding system by DCT is limited to operationin only lossy image coding because distortion of the decoded image
is unavoidable with these lossy algorithms.
On the other hand, many IntDCTs have been proposed forlossless-to-lossy image coding [5–8]. These IntDCTs are constructed by lifting structures [9] with rounding operations. Because
fast implementation of DCT is achieved by cascading Givens rotation matrices

Rθ =


cos θ − sin θ,
sin θ cos θ10

cos θ−1
sin θ

1



1 0
sin θ 1

1
0

3.1. Direct-Lifting of DCT-IDCT
We process the two individual signals by DCT and IDCT, as shownon the left part in Fig. 2. The output signals are transformed by
 
  
C 0 xi
yi
=
.
(1)
ti
0 D siAlso, its inverse transform is expressed by
 





−1 
D 0
I 0 I DI 0 0 −I
C 0
=
=
.
0 C
−C I 0 I −C I I 0
0 D(3)Thus, the block parallel system of DCT-IDCT can be efficiently
implemented by the block-lifting structure, as shown in the right partin Fig. 2. However, the systems in (2) and (3) have the problem thatthe transformed signals by IDCT are not suitable for image compression because IDCT includes a lot of DC leakages.
3.2. Efficient Realization by Side Information Block (SIB)
We can easily come up with a simple realization for lossless-to-lossy
image coding which is applied after an N ×N image X is segmented
to M ×M block xk (0 ≤ k ≤ n−1, n = (N/M )2 ). The segmented
block xk is sequentially transformed by DCT as

most IntDCTs are redesigned by lifting factorization asRθ =3. EFFICIENT REALIZATION OF INTDCT

Here, diag{C, D} in (1) can be factorized into complete blocklifting structures such as

 




C 0
0 I
I 0 I −D I 0
=
.
(2)
0 D
−I 0 C I 0 I
C I

where D = C−1 = CT , 0 ≤ m, n ≤ M − 1,cm =Fig. 2. Direct-lifting of DCT-IDCT (white circles: rounding operations).

cos θ−1
sin θ

1



yk = Cxk.

Hence, note that most IntDCTs are constructed by many rounding
operations, so that rounding error is generated much more.

390

for k = 1, 2, · · · , n

where yk is an output signal of xk . In parallel, M × M block sk
has to be transformed by IDCT, however, the transform by IDCT is
undesirable for the image compression as described in the previous

Fig. 3. IntDCT by direct-lifting of DCT-IDCT (white circles: rounding operations): (left) cascading of block parallel systems of DCT-IDCT,(right) lifting factorizations of it.

subsection. Then we prepare an M × M side information block(SIB) s0 as a null matrix and sk is iteratively transformed from s0bysk = Dsk−1

for k = 1, 2, · · · , n.

Table 1. The comparisons of the number of rounding operations per
an 1D transform of 8 × 1 signals.
K’s H’s L’s C’s
Prop.
[5]
[6] [7] [8] IntDCT
29
9
15
8
1.5

As a result, the proposed realization for lossless-to-lossy image coding is presented by⎤ ⎡Cy0⎢ y1 ⎥ ⎢C⎥ ⎢⎢⎢ .. ⎥ ⎢..
=⎢ . ⎥ ⎢.
⎥ ⎢⎢⎣yn−1 ⎦ ⎣C
sn
0⎡

3.3. More Efficient Improvement by Two-Dimensional Block
Transform (2DBT)

⎤⎡

⎤
x0
⎥ ⎢ x1 ⎥⎥⎢⎥0 ⎥⎢ . ⎥⎥ ⎢ .. ⎥⎥⎢⎥⎦ ⎣xn−1 ⎦
Dn
s0

(4)

and sn is also encoded with all of yk . The left part in Fig. 3 shows
the system in (4). Note sn = 0 due to rounding error in each lifting
structure. Moreover, it is clear that the combination of C and D canbe factorized to lifting structures by (2), as shown in dashed line areain Fig. 3. As expected, the inverse transform of (4) is expressed by⎤ ⎡Dx0⎢ x1 ⎥ ⎢D⎥ ⎢⎢⎢ .. ⎥ ⎢..
⎢ . ⎥=⎢.
⎥ ⎢⎢⎣xn−1 ⎦ ⎣
D
s0
0
⎡

⎤⎡

⎤
y0
⎥ ⎢ y1 ⎥⎥⎢⎥0 ⎥⎢ . ⎥⎥ ⎢ .. ⎥⎥⎢⎥⎦ ⎣yn−1 ⎦Cnsn

and the combination of D and C can be factorized to lifting structures by (3).
The proposed lossless-to-lossy image coding is summarized asfollows:
1. Lossless bitstream with block sn can be obtained by using (4)and an encoder.
2. In lossless mode, the image is reconstructed from all lossless
bitstreams and sn . Each block sk is successively inverselytransformed by sk = Csk+1 without any loss.
3. In lossy mode, the image is reconstructed by interrupting thelossless bitstream without using sn and decoding it by JPEG
standard.

391

DCT applied to M × M input signal x separately by column androw is expressed by
T
= CxCT  C2D (x)y = C (Cx)Twhere y is an output signal of x. Similar to C2D (x), let us define
D2D (x)  DxDT . Then, we find that each lifting block is also
defined as an M × M two-dimensional block transform (2DBT).
Consequently, (2) is represented by
 



0 I
I
0
0
C2D (x)=−I 0 C2D (x) I
0
D2D (x)
I −D2D (x)
I
0
. (5)
×
0
I
C2D (x) I
Such lifting matrices by 2DBT in (5) are a more efficient for losslessto-lossy image coding because the number of rounding operations
per an one-dimensional (1D) transform of M × 1 signals is reduced
from 3M to 3M/16 and rounding error is also reduced much more.
The comparisons of the number of rounding operations when theblock size is 8 are shown in Table 1.
4. RESULTS
In this section, the proposed 8-channel IntDCT is validated inlossless-to-lossy image coding by the lossless bitrate (LBR) [bpp] inlossless image coding and peak signal-to-noise ratio (PSNR) [dB]in lossy image coding. We chose [5–8] as the conventional IntDCTs
and twenty 512 × 512 grayscale test images, for example, “Barbara”, “Lena” and “Pepper”. The set partitioning in hierarchicaltrees (SPIHT) progressive image transmission algorithm [11] wasused to encode the transformed images.

where MSE is the mean squared error, with other lossy image coding
methods are shown in Table 3. As lossless image coding, in Table 3,
we see that the proposed IntDCT shows better coding performance
than do the conventional methods and has performance comparable
to the JPEG coder even in lossy image coding with low bitrates.

Table 2. Lossless image coding results (LBR [bpp]).
Test
DCT
K’s
H’s
L’s
C’s
Prop.
[2]
[5]
[6]
[7]
[8]
IntDCT
image
Airplane
4.51 4.41 4.90 4.40
4.36
5.02 4.96 5.51 4.97
4.95
Barbara5.22 5.19 5.73 5.19
5.18
Boat
Goldhill
5.19 5.16 5.71 5.16
5.15
4.69 4.63 5.22 4.64
4.62
Lena
Pepper
4.98 4.95 5.52 4.96
4.94
4.35 4.15 4.55 4.18
4.06
Watch
Avg.
5.44 5.39 5.91 5.40
5.38

5. CONCLUSION
This paper presents a realization of lossless-to-lossy image coding
which has higher compatibility with JPEG standard than the conventional integer discrete cosine transforms (IntDCTs). Our IntDCT
is implemented by direct-lifting of DCT and inverse DCT (IDCT)
and two-dimensional block transform (2DBT) is applied to every
lifting block to reduce the total number of rounding operations andshows better coding performance. On the other hand, although a sideinformation block (SIB) is required, its size is the same as that of
DCT and the amount of information for coding is small. As a result,
our IntDCT has high performance in lossless image coding compared with any IntDCT while keeping high compatibility with JPEG
standard. Our IntDCT also shows better coding performance thanthe conventional methods in lossless-to-lossy image coding. Thismethod can be applied into not only DCT but any orthogonal transform. Our future work will be deleting the side information andreducing the computational cost.

Table 3. Lossy image coding results (PSNR [dB]).
Test
DCT
K’s
H’s
L’s
C’s
Prop.
[2]
[5]
[6]
[7]
[8]
IntDCT
image
bitrate: 0.25 [bpp]Barbara 26.95 26.93 26.94 23.70 26.73
26.95
31.88 31.83 31.84 29.03 31.85
31.86
Lena
Pepper
31.43 31.38 31.41 28.49 31.42
31.42
bitrate: 0.50 [bpp]Barbara 30.70 30.65 30.67 27.14 30.40
30.68
35.60 35.45 35.51 32.25 35.48
35.55
Lena
34.49 34.38 34.43 31.52 34.33
34.46
Pepperbitrate: 1.00 [bpp]Barbara 36.08 35.88 35.96 31.18 35.84
36.03
39.23 38.70 38.97 35.52 38.93
39.12
Lena
37.04 36.68 36.85 34.16 36.71
36.97
Pepper

6. REFERENCES[1] ISO/IEC 10918-1, Information technology - Digital compression and coding of continuous-tone still images Requirements
and Guidelines.
[2] K. R. Rao and P. Yip, Discrete Cosine Transform Algorithms,
Academic Press, 1990.

4.1. Application to Lossless Image Coding
First, the proposed IntDCTs are applied to lossless image coding.
SIB sn is encoded without compression because the data consist ofvery few bits:
log2 (|sn |max ) + 1M 2 [bit]
SIB bitrate [bpp] =Total number of pixels [pixel]
where . is the ceiling of (.). For example, the size is only 512 [bits](0.01953125 [bpp]) in the 512×512 image “Barbara” transformedby the proposed IntDCT. The comparisons of
LBR [bpp] =Total number of bits [bit]+ SIB bitrate
Total number of pixels [pixel]

in lossless image coding are shown in Table 2. The coding performance of the proposed IntDCTs is better than the performance of allof the conventional methods.
4.2. Application to Lossy Image Coding
If lossy compressed data is required, it can be achieved by interrupting the obtained lossless bitstream without SIB sn . Therefore,
we can use the existing JPEG decoder to reconstruct an image. The
comparisons of


2552
,
PSNR [dB] = 10 log10
MSE

392

[3] ISO/IEC 15444-1, Information technology - JPEG 2000 image
coding system: Core coding system.
[4] ISO/IEC 29199-2, JPEG XR image coding system - Part 2:
Image coding specification.
[5] K. Komatsu and K. Sezaki, “Reversible discrete cosine transform,” in Proc. of ICASSP’98, Seattle, WA, May 1998.
[6] P. Hao and Q. Shi, “Matrix factorizations for reversible integer
mapping,” IEEE Trans. Signal Process., vol. 49, no. 10, pp.
2314–2324, Oct. 2001.
[7] J. Liang and T. D. Tran, “Fast multiplierless approximations of
the DCT with the lifting scheme,” IEEE Trans. Signal Process.,
vol. 49, no. 12, pp. 3032–3044, Dec. 2001.
[8] 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.
[9] W. Sweldens, “The lifting scheme: A new philosophy inbiorthogonal wavelet constructions,” in Proc. of SPIE 2569,
1995.
[10] S. Iwamura, Y. Tanaka, and M. Ikehara, “An efficient lifting
structure of biorthogonal filter banks for lossless image coding,” in Proc. of ICIP’07, San Antonio, TX, Sep. 2007.
[11] 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.