Integer Time-Domain Pre- and Post-Filters for
Low-Complexity Extension of JPEG StandardShohei Kubo∗ , Taizo Suzuki† , and Hiroyuki Kudo†∗ Department of Computer Science, University of Tsukuba, Japan,

E-mail: kubo@imagelab.cs.tsukuba.ac.jp† Faculty of Engineering, Information and Systems, University of Tsukuba, Japan,

E-mail: {taizo, kudo}@cs.tsukuba.ac.jp
Abstract—Time-domain lapped transform (TDLT) is a familyof lapped transforms (LTs) which reduce blocking artifacts
occurred by the DCT algorithm. Also, we can directly apply
it to the existing JPEG framework because it is constructed bythe DCT with time-domain pre- and post-filters. It obviously has
higher complexity than an ordinary DCT. We present an integer
approximated TDLT (IntTDLT) which can be easily implemented
with only adders/shifters, i.e., no floating-point multipliers, andfewer step processing, while preserving the characteristics suchas allowing the use of symmetric extension and structural one
degree of regularity (1-regularity). As a result, it performs goodcoding, especially at a low bitrate, in spite of the low-complexity.

I. INTRODUCTION
The well-known JPEG image compression (coding) standard [1] has been widely used for 20 years. However, itgenerates annoying error, i.e, blocking artifacts, at a low
bitrate image coding. The problem is caused due to theblock-based DCT [2] which excludes the neighboring block
correlation. As for video coding such as H.26x series [3][4],integer approximated DCTs [5][6] are commonly used. The
transforms not only have simple implementation but also avoid
the mismatch problems in the decoder.
JPEG XR [7] has been developed as the next generation
standard which provides high image quality even in a low
bitrate coding. However, JPEG is still used as a de facto
standard because of two factors: i) JPEG coder has alreadybeen used in the widespread application, ii) JPEG XR requires
higher complexity than JPEG. JPEG XR adopts a class oftime-domain lapped transform (TDLT) [8]. TDLT is a familyof lapped transforms (LTs), which reduce blocking artifacts,
and can be directly applied to the existing JPEG frameworkin case of block size 8 because it is constructed by the DCTwith time-domain pre- and post-filters. Although the traditional
TDLT consisting of lifting structure [9], which is called liftingbased TDLT (LiftTDLT) in this paper, cannot achieve effective
butterfly-style processing which has fewer step processing.
We propose an integer approximated TDLT (IntTDLT) with
only adders/shifters, i.e., no floating-point multipliers, andfewer step processing for image coding. The IntTDLT canadopt symmetric extension [10] to avoid boundary error even
if the coefficients are approximated by integers. Similarly, itsatisfies one degree of regularity (1-regularity) [11] which
is an important property for image coding in filter bank978-616-361-823-8 © 2014 APSIPAFig. 1. Processing flow of TDLT.

theory. In addition, since all coefficients in our transformconsist of only integers, we can always obtain the identicalreconstructed data even under any circumstance of decoder.
Moreover, it can achieve effective butterfly-style processing
for low-complexity unlike LiftTDLT. We show the validity ofthe proposed IntTDLT in its application to JPEG standard as
an example.
Notations: We use bold-faced lowercase and uppercase
characters to denote vectors and matrices, respectively. I, J,·−1 , and |·| indicate an identity matrix, a reversal identity
matrix, an inverse matrix, and the determinant of a matrix,
respectively.
II. REVIEW
A. Time-Domain Lapped Transform (TDLT)
TDLT [8] is a family of LTs and uses the time-domain
pre-filter of DCT inputs and the post-filter of IDCT outputs.
The pre- and post-filters are outside the existing framework
as shown in Fig. 1. The TDLT improves coding performance while achieving standard-compliance with minimal
software/hardware modifications. The analysis polyphase matrix is written as
[][]
I00 I
E(z) = CIIP,(1)M 0 z −1 II 0where
P=[][1 I JI
2 J −I 00V][IJ]J−I(2)and CII
M is an M × M type-II DCT matrix. The M/2 × M/2
nonsingular matrix V holds all of the degrees of freedom
in this structure which controls the properties of pre-/postfiltering.1 The coefficients are determined by using cost function such as coding gain and stopband attenuation. Also, the1 If V is a paraunitary matrix, it is decomposed into M (M − 1)/2 rotation
matrices Qk (k = 1, 2, · · · , M (M − 1)/2).

APSIPA 2014

TDLT in Eq. (1) is represented by lifting structures to obtaina transform with higher energy compaction capability andfaster implementation. In this paper, let LiftTDLT be TDLT-III
whose pre-filter P is shown in Fig. 2.
B. Integer Transform
By approximating the floating-point multipliers of a transform by integers, the multipliers can be replaced by several
different shifters and sum of them (adders) [12]. The total
number of adders and shifters is evaluated by using thebinary representation of the integer multiplier. For example,
the multiplier by 5 = (101)2 can be implemented by one adderand one shifter. Thus, the arithmetic complexity and dynamic
range of the data are significantly reduced compared withfloating-point multipliers. As a result, it achieves the simpler
circuit and the faster implementation.

Fig. 2. Lattice structure of LiftTDLT.

Fig. 3. Pre-filter of forward IntTDLT.

III. I NTEGER A PPROXIMATED TDLT (I NT TDLT)The purpose of this paper is to reduce blocking artifacts
with low-complexity as much as possible under the integer
approximation. If the transform coefficients are not integers but
floating-point values, we cannot obtain the lossless image dueto the quantization. Also, if the floating-point representationsof coefficients are different between decoders, we cannot
obtain same decoded images. With this in mind, the proposed
IntTDLT is designed such that all the coefficients consist ofonly integers.
A. Integer Approximation of V for Forward Transform
We derive an integer approximation of V and explain its
characteristics in this section. We define the approximation as(Fig. 3)Q̂k = round{αk Qk }for k = 1, 2, ..., (M − 2)/2

(3)

to convert the floating-point coefficients of a 2 × 2 arbitrary
matrix Qk into integers by a scaling factor αk . Additionally,we eliminate the redundancy using easy matrix manipulationsas[] [][]
ak1 bk2
a b k1 0=(4)ck1 dk2
c d 0 k2[] [][]
ak1 bk1
k0 a b= 1(5)ck2 dk2
0 k2 c dwhere a, b, c, d, k1 , and k2 are arbitrary integers. If scaling
factors in common appear in all passes, they are removed forlow-complexity.
As an example, we refer to Table V in [8] and set P0 = 0,P1 = −1/4, P2 = −1/2, U0 = 1/4, U1 = 1/2, U2 = 3/4,S0 = S1 = S2 = S3 = 1 in Fig. 2. The parameters achieve
so low-complexity. The 2 × 2 matrix Qk (k = 0, 1, 2) of thepre-filter is rewritten as[][1 U01Q0 =0 1
P0[][1 U11Q1 =0 1
P1[][1 U21Q2 =0 1P2] []0
1 1/4=
101] []
0
7/8 1/2=
1−1/41] []0
5/8 3/4=.
1−1/2
1(6)

To achieve our purpose discussed in the beginning of thissection, we set αk = 2, which is a simple scaling factor, in
Eq. (3). This approach leads Qk to the new matrix Q̂k as[]
[][]
2 1
2 1
1 2Q̂0 =, Q̂1 =, Q̂2 =.
(7)0 2−1 2−1 2Next, we eliminate the redundancy of the structure by using
easy matrix manipulations as shown in Eq. (4) and (5). Thescaling factor 2 is extracted from Q̂2 as[] [][]
e2 1 0 = 1 1 1 0 .
Q̂2 = Q(8)
0 2−1 1 0 2
Similarly, the scaling factor 2 extracted in Eq. (8) is moved
into the next matrix Q̂1 as[][]
2 04 2Q̂1 =.
(9)
0 1−1 2The same processing as Eq. (8) and (9) is repeatedly performed
until Q̂0 . Finally, the scaling factors in common appeared inall passes are removed. This approach leads Q̂k to the newmatrix Q̃k as[][][]1 14 1
1 1eeeQ0 =, Q1 =, Q2 =. (10)0 1−1 1−1 1
The structure allows a simple design and has low-complexity.
The overall view of the final structure is shown in Fig. 4.
The transform scaling factor 1/8 to normalize the transformed
signals is implemented on the phase before DCT.

B. Integer Approximation of V−1 for Inverse TransformIn the decoder, we should use just integer coefficients
because we have the problem that reconstructed images vary
due to the differences of decoders. If all coefficients of theinverse transform are integers, it is a complete system whiche −1 asdoes not depend on the decoder. Thus, we define Q
k[]−1 []d −be −1 ≜ |Q
e k| · a b
Q=,(11)
kc d−c aFig. 4. Pre-filter of forward IntTDLT (αk = 2).

e k | ̸= 0.
where a, b, c, and d are arbitrary integers and |Q
For an example in Eq. (10), the matrices are defined as[][][]e −1 = 1 −1 , Q
e −1 = 1 −1 , Q
e −1 = 1 −1 .
Q0120 11 4
1 1(12)e k for Low-Complexity
C. Adjustment of Q
e k | is an odd number, we must introduce new scaling
If |Q
factors to all passes in the post-filter to satisfy complete integer
approximation. This means that high-complexity is yielded inek
the decoder. By adjusting the determinant of 2 × 2 matrix Q
in the forward transform to the power-of-two, the IntTDLT
can achieve lower complexity.
e 1 | = 5 which is an odd number,
As an example, since |Qe
Q1 and the inverse are replaced by[]
[]
3 1
1 −1
−1ee
Q1 =, Q1 =.
(13)
−1 1
1 3
The new post-filter is shown in Fig. 5.
D. Application of Symmetric Extension and Structural 1Regularity
TDLT needs no extra signals at the signal boundaries byapplying the symmetric extension [10]. Let xM/2 and JxM/2
be the M/2 × 1 input vector signal and the reflected vector
signal of xM/2 , respectively. The pre-filter P implements thesignals as follows:][][][[][]1 I J
I 0 I J
JxM/2
JxM/2
P=xM/2xM/2
2 J −I 0 V J −I[][] []
1 I J
2xM/2
JxM/2
==.
(14)
0xM/2
2 J −IThis means that pre- and post-processing at the signal boundaries can be skipped even if the matrix V is any matrix.
On the other hand, DCT satisfies 1-regularity condition [11]as  √ 1M
1  0 II  (15)CIIM 1M = CM  ..  =  ..  .
.  . 
10Since the pre-filter P in TDLT is a mirror mapping operator
as in Eq. (14), it can just output 1M when the signal 1M isinput. Thus, it satisfies structural 1-regularity condition even
if the matrix V is any matrix.

Fig. 5. Post-filter of inverse IntTDLT (αk = 2).

IV. E XPERIMENTAL R ESULTS
In this section, we compare the complexity and image
coding performance of DCT in JPEG, LiftTDLT, and IntTDLT.
A. Complexity
Table I shows the comparison of the arithmetic complexity
for pre-/post-filters of LiftTDLT and IntTDLT. The IntTDLThas the same number of adders and the fewer number ofshifters than them of LiftTDLT. Moreover, the numbers ofprocessing steps are shown in Table I. The pre-filter of
LiftTDLT needs nine step processing, whereas that of IntTDLT
needs only five step processing because the proposed method
can be implemented with butterfly-style operation. This meansthat IntTDLT can be implemented faster than LiftTDLT.
B. Image Coding Performance
To evaluate coding performance fairly, we used structuralsimilarity (SSIM) [13]. Peak signal-to-noise ratio (PSNR)
is well-known as an objective assessment, which is usedmost widely, but it is unsuitable for perceptual visual quality,
especially concerning blocking artifacts [14]. SSIM is analternative complementary framework for quality assessment
based on the degradation of structural information and is closer
to human subjective evaluation than PSNR. The dynamic rangeof SSIM is [0,1] and the lager SSIM values signify the better
visual quality. We used the MATLAB code at [15]. To considera fair and practical situation, we used a JPEG framework afteradjusting the transformed coefficients to the 8-bit range [0,255]. In Fig. 6, IntTDLT and LiftTDLT showed better coding
performance compared with DCT in JPEG. And IntTDLT wascomparable to LiftTDLT though the coefficients are forcibly
approximated by integers. Also, as demonstrated in Fig. 7,
blocking artifacts were reduced and edges and textures werepreserved better than those of the DCT.

bb0.9

0.9

0.85

0.85

0.8

0.8

0.75

0.75

0.7

0.7

0.65

0.65

b0.9

0.85

0.8

0.75

b0.1

0.15

0.2

0.25

0.3

0.35

0.4

0.45

0.7

b0.10.150.2

0.25

0.3

0.35

b0.1

0.12 0.14 0.16 0.18

0.20.22 0.24 0.26 0.28

0.3Fig. 6. Comparison of SSIM with low bitrate : (left) Barbara, (middle) Goldhill, (right) Lena.

TABLE IC OMPARISON OF NUMBERS OF ADDERS , SHIFTERS , AND STEPS AMONG
L IFT TDLT AND I NT TDLTadders
multipliers
shifters
steps

Forward Transform
LiftTDLT IntTDLT
22220013995Inverse Transform
LiftTDLT IntTDLT
22220013995V. CONCLUSIONS
We have presented the theory, design, and implementationof the IntTDLT. It achieved faster implementations with only
adders/shifters and fewer step processing while preserving thenice characteristics such as allowing the use of symmetricextension and structural 1-regularity. As a result, we showed
good performance as an extension of JPEG standard. Especially, it reduced blocking artifacts occurred by JPEG in a
low bitrate situation.
ACKNOWLEDGMENT
This work was supported by a JSPS Grant-in-Aid for Young
Scientists (B), Grant Number 25820152.
R EFERENCES[1] W. Pennebaker and J. Mitchell, JPEG, Still Image Data Compression
Standard, NY: Van Nostrand, 1993.
[2] K. R. Rao and P. Yip, Discrete Cosine Transform Algorithms, AcademicPress, 1990.
[3] T. Wiegand, G. J. Sullivan, S. Member, G. Bjøntegaardntegaard, andA. Luthra, “Overview of the H.264/AVC video coding standard,” IEEETrans. Circuits Syst. Video Technol., vol. 13, no. 7, pp. 560–576, July
2003.
[4] G. J. Sullivan, J.-R. Ohm, W.-J. Han, and T. Wiegand, “Overview ofthe high efficiency video coding HEVC standard,” IEEE Trans. Circuits
Syst. Video Technol., vol. 22, no. 12, pp. 1649–1668, Dec. 2012.
[5] H. S. Malvar, A. Hallapuro, M. Karczewicz, and L. Kerofsky, “Lowcomplexity transform and quantization in H.264/AVC,” IEEE Trans.
Circuits Syst. Video Technol., vol. 13, no. 7, pp. 598–603, July 2003.
[6] B.K. Mohanty P.K. Meher, S. Y. Park and K. S. Lim, “Efficientinteger DCT architectures for HEVC,” IEEE Trans. Circuits Syst. VideoTechnol., vol. 24, no. 1, pp. 168–178, Jan. 2014.
[7] 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.

[8] T. D. Tran, J. Liang, and C. Tu, “Lapped transform via time-domainpre- and post-filtering,” IEEE Trans. Signal Process., vol. 6, no. 6, pp.
1557–1571, June 2003.
[9] W. Sweldens, “The lifting scheme: A new philosophy in biorthogonal
wavelet constructions,” in Proc. of SPIE San Diego. CA, July 1995, vol.
2569, pp. 1–12.
[10] M. Vetterli and J. Kovacevic, Wavelets and Subband Coding, Englewood
Cliffs, NJ: Prentice-Hall, 1995.
[11] W. Dai and T. D. Tran, “Regularity-constrained pre- and post-filteringfor block DCT-based systems,” IEEE Trans. Image Process., vol. 51,
no. 10, pp. 2568–2581, Oct. 2003.
[12] Y. J. Chen, S. Oraintara, T. D. Tran, K. Amaratunga, and T. Q. Nguyen,“Multiplierless approximation of transforms with adder constraint,”
IEEE Trans. Signal Process., vol. 9, no. 11, pp. 344–347, Nov. 2002.
[13] Z. Wang, A. C. Bovik, H. R. Sheikh, and E. P. Simoncelli, “Imagequality assessment: From error visibility to structural similarity,” IEEETrans. Image Process., vol. 13, no. 4, pp. 600–612, Apr. 2004.
[14] B. Girod, What’s wrong with mean squared error, Digital Images andHuman Vision, A. B. Watson, Ed. Cambridge, MA: MIT Press, 1993,
pp. 207-220.
[15] “The SSIM index for image quality assessment,” [Online]. Available:
https://ece.uwaterloo.ca/ z70wang/research/ssim/.

Fig. 7. Comparison of a particular area of decoded images: (top) Barbara: DCT (0.252[bpp]), LiftTDLT (0.245[bpp]), IntTDLT (0.251[bpp]), (middle) Goldhill:
DCT (0.247[bpp]), LiftTDLT (0.244[bpp]), IntTDLT (0.244[bpp]), (bottom) Lena: DCT (0.203[bpp]), LiftTDLT (0.204[bpp]), IntTDLT (0.202[bpp]).