DCT APPROXIMATION FOR LOW BIT RATE CODING USING A CONDITIONAL
TRANSFORM
Ricardo L.de Queiroz
Xerox Corporation,800Phillips Rd.,128-27E,Webster,NY,14580
queiroz@ieee
ABSTRACT
A transform approximation is explored for speeding up the software compression of images and video.It is ud to re-place the regular DCT whenever only few DCT coefficients are actually encoded.A conditional transform is propod to only transform the data that it determines to be relevant. The approximation is applicable to environments combining the requirements of high compression and low complexity.
1.INTRODUCTION
Image transmission is commonplace.Among numerous ap-plications,the ITU has recently standardized a system for color fax[1].In its baline mode,color fax operates with a handshaking procedure similar to that of black and white fax.After connection is established,the scanned image is JPEG[2]compresd and transmitted.Often,the compres-sion ratios are quite large.Other facsimile systems such as Internet Fax are being devid[1].Video is also pervasive on the internet and MPEG compression[3]is a popular video reprentation format.
We are concerned with systems where the image is input or generated on-the-fly and transmitted immediately.This is the ca in live transmission of video and stills.In color fax,image parameters are only determined after handshak-ing.Hence,as is the ca of live production of stills and video,compression has also to be performed in real time. Compression standards such as JPEG[2]or MPEG[3]rely on quential transform,quantization,and entropy coding. Typically,all image data is transformed and quantization is applied to every transformed coefficient.The two steps typically drain a significant fraction of the compression com-putation and are independent of the image data or of the compression target.
In summary,we are concerned with systems in which software-bad compression is performed on-the-fly and where it is desirable to reduce computational complexity. Our goal is to speed up the com
pression by replacing the real transformation by a low cost approximation.We examine the ca of the discrete cosine transform(DCT)and concentrate on the JPEG image coding standard,although results would also apply to MPEG,or,effectively,to any block transform bad compression system.A companion paper discuss re-duced transforms and fast image analyzers[4].
2.CONDITIONAL REFINEMENT
If we can determine if there are no non-zero high frequency coefficients in certain blocks,we can approximated a reduced DCT,which just implements the DCT for the low frequency coefficients.This concept has been applied in[5]–[9].
In-
00
11
22
33
brusls44
55
66
77
Figure1.Approximation of an8-point DCT. variably,one us a reduced-complexity DCT approximation, which is suppod to be only ud when it is estimated that there is no high frequency content on the block.The prob-lem is the estimation step.It must be reliable enough not to
cau artifacts and fast enough not to offt the savings of a fast DCT approximation.As a starting point,we have devel-oped an approximation to the DCT,depicted in Fig.1for an 8-channel transform,which is similar to the“subband-DCT”scheme[7].It is also similar to the approximation in[6],ex-cept for one small but important change to the last stage. The8-point DCT is approximated by4simple Haar trans-forms(sum and difference)followed by DCTs.The output of the sum is a simple low-pass version of the block samples, while the output of the difference is like a high pass signal. Now,each resulting4-point signal(low-and high-pass)is transformed by a4-point DCT to get an8-point transformed quence.DCT bas are compared to the bas of the ap-proximation in Fig.2.
The advantage of using such an approach is becau af-ter the Haar transforms,the low-and the high-frequency coefficients have already been parated.Since the DCT is orthogonal,the signal power before and after the DCT-4is the same,so that we can estimate the signal power of the transformed coefficients just by estimating the power of the Haar-transformed samples.
The propod system is illustrated in Fig.3.Using the Haar transform the image is divided into4quadrants:sum or difference in both directions,and the other two combina-tions.The low-pass quadrant is transformed by the4×4 DCT.Each of the3other quadrants is checked for activity. This is done by comparing each sample to a threshold.If any sample is above the threshold,the DCT for that 自考什么时候出成绩
ction is computed,otherwi the DCT coefficients in that region are
DCT Approximation
12345670
123456700.10.20.30.40.50.60.70.80.91
-20-15-10-500
0.10.20.30.40.50.60.70.80.91
-20-15-10-50DCT
Approximation
Figure 2.Comparison of bas of the DCT and of its approximation.Top:spatial domain;bottom:fre-quency respon of the bas when viewed as filters.
-/-
-/-
+/-超能陆战队字幕
+/--/+-/++/++/+DCT Test/DCT Test/DCT
Test/DCT LL LL LH LH
HL HL HH
HH
}
{
Haar
Figure 3.Conditional transform propod here.High-pass gments of the DCT coefficients are only computed if samples before the DCT-4are deemed relevant.
directly t to zero.The threshold can be t as the aver-age of the quantizer steps in the respective DCT region as in the example in Fig.4.This average can be divided by 2to dispen applying the sca
ling step (×1/4)in the Haar aver-aging.When a quadrant is considered active (some sample above threshold)it is transformed using a 2D 4×4DCT,which incorporates the normalization factor from the Haar transform along with its own.
Counting additions,multiplications,compares (to zero),shifts,etc.as one operation (op),the total complexity for the 8×82D DCT is 768ops assuming a standard parable algorithm [10].Using the same algorithm for the 4×42D DCT the complexity is 112ops.Other algorithms can im-plement the 8×82D DCT with 672ops [11]or 572ops [12](discarding scalings),but we will stick to the first method since the performance improvement we propo is relative.The average complexity per block for the propod trans-form is 336+112νops,where νis the average number of active high-frequency bands above the thresh-old.The relative complexity compared to the DCT ca is
X 4444108
Associated Thresholds
68101321356211789121728478413510121625406910216513172538648913421921
28406486123189255354769891231812552556284102134189255255255117135165219255255255255
Q-table
Figure 4.An example quantizer table and associated thresholds to test relevance of subbands in the con-ditional transform.Thresholds are half the averages of the quantizer step entries in each quadrant.
Figure 5.Transform mismatch example.Image cam-eraman (256×256pixels)transformed using the con-ditional approximation but reconstructed using the DCT.
φ=0.4375+0.1458ν.Hence,in the best ca,the complexity is less than half of that of the DCT,while in the worst ca it is at least 12.5%less that the DCT.The following table summarizes the behavior of νand φfor image “Lena”,at different compression ratios (CR),where it should be appre-ciated how quickly the complexity φapproaches its minimum value.
CR 4.57.711.71826ν 1.800.840.360.150.02φ0.700.560.490.460.44
As in the other approximations in this paper,there is a quality reduction price one pays for the increa in speed.Let us consider two decoder scenarios.In the first,the de-coder us the inver of the approximated transform (inver 4×4DCTs,and inver Haar transforms).The compression performance is a bit below that of the DCT becau the trans-form itlf is not as clo to the optimal as the DCT is for a Markov image model.The rate-distortion curves for the approximation and for the DCT are comparable,with the DCT being consistently superior (typically by 1dB or so).In the cond scenario,a regular inver DCT is ud in the de-coder causing a transform mismatch as exemplified in Fig.5.There are jagged ringing artifacts near sharp edges.The artifacts may or may not be noticeable in a high-resolution low-bit-depth printing.In any ca,if there is a potential transform mismatch it is advisable to u the conditional transform for low-bit-rate cas only.
aprilfool
Figure6.Image cameraman compresd at moder-ate bit rates using JPEG.Top left:regular DCT (0.63bpp,PSNR=27.7dB).Top right:approxi-mated compression but using regular inver DCT (0.62bpp,PSNR=25.4dB).Bottom left:approxi-mated transform(0.62bpp,PSNR=26.4dB).Bot-tom right:傅雷翻译
map with number of active bands.
3.PERFORMANCE
Figure6compares decompresd images after a compression to bit rates around0.63bpp.It is shown the image camera-man after compression using the propod conditional trans-form and decompression using both an approximated trans-form and using the regular inver DCT.The image after compression using regular JPEG at a similar rate is also shown in Fig.6,along with the map with the number of active bands in each block(black=0;white=3).Note the ringing artifacts around the edges of the image where the mismatch between transforms occurred.The image which ud the ap-proximation in both compression and decompression stages is comparable to the straight JPEG ca.Figure7repeats the results from Fig.6for a higher compression bit rates around0.27bpp.In this ca,all the images prent similar visual reconstruction quality,despite the differences in PSNR.PSNR curves for this image are shown in Fig.8. The best performing curve is for the regular JPEG approach, followed by the ca where the approximated transform was ud in both compression and decompression,while the ca where there was mismatch is the one where the worst per-formance is recorded,as expected.For low bit rates,the difference is about1dB,which is a good sign that the ap-proximation even in objective terms is not too far offthe DCT.
In summary,the conditional transform should be ud for higher compression ratios where it makes little difference whether there is a mismatch in the inver transform.At the same time the transform complexity is nearly halved at only a small decrea in performance,which is typically a few dB loss in PSNR.Subjectively,the differences among methods are less evident for lower rates.
4.CONCLUSIONS
An approximation to the DCT was propod for u in image compression in order to save computation.They are suit-able to JPEG and MPEG in high compression ratio modes, since quantization artifacts might help mask the artifacts caud by the transform approximation.The approximation can typically half the overall computation for low bit rates and where JPEG/MPEG compression of the data blocks is already discarding too much visible information.In other words,savings come from not computing information that is not encoded.The method was shown to be efficient to sub-stitute the DCT in JPEG/MPEG environments for low bit rate targets.The method in many parts can be extended to encompass other transforms such as the wavelet transform ud in JPEG2000[13],which is a direction for further ex-ploration.
REFERENCES
[1]R.Buckley,D.Venable and L.McIntyre,“New develop-bta
ments in color facsimile and internet fax,”Proc.of IS&T’s Fifth Color Imaging Conference,pp.296–300,Scottsdale, AZ,Nov.1997.
[2]W.P.Pennebaker and J.L.Mitchell,JPEG:Still Image
Compression Standard,Van Nostrand-Reinhold,1993. [3]A.M.Tekalp,Digital Video Processing,Upper Saddle
River,NJ,Prentice-Hall,1995.
[4]R.de Queiroz,“Reduced DCT approximations for low bit
rate coding,”in this Proceedings.
[5]B.Girod and K.W.Stuhlmuller,“A content dependent
fast DCT algorithm for low bit-rate video coding,”Proc.
ICIP,Chicago,IL,Oct.1998.
Figure7.Image cameraman compresd at low bit rates using JPEG.Top left:regular DCT(0.28 bpp,PSNR=24.63dB).Top right:approximated compression but using regular inver DCT(0.27 bpp,PSNR=23.86dB).Bottom left:approximated transform(0.27bpp,PSNR=23.76dB).Bottom right:ma
p with number of active bands.trace是什么意思
0.20.40.60.81
Bit-rate(bpp)
P
S
N
R
(
d
B
)
大括号Figure8.PSNR plots for the conditional transform approach.A(I)T refers to the approximated(in-ver)transform.
[6]K.Lengwehasatit and A.Ortega,“DCT computation
bad on variable complexity fast approximations,”Proc.
ICIP,Chicago,IL,Oct.1998.
[7]S.-H.Jung,S.K.Mitra and D.Mukherjee,“Subband
DCT:definition,analysis and applications,”IEEE Trans.
on Circuits and Systems for Video Tech.,vol.6,pp.273-286,June1996.
[8]I.Richardson and Y.Zhao,“Adaptive algorithms
for variable-complexity video coding,”Proc.of ICIP, Greece,Oct.2001.
[9]I-M.Pao and M.T.Sun,“Modelling DCT coefficients
for fast video encoding,” Circuits and Systems for Video Tech.,Vol.9,pp.608–616,June1999.
[10]K.R.Rao and P.Yip Discrete Cosine Transform:Algo-
rithms,Advantages,Applications,San Diego,CA:Aca-demic Press,1990.
[11]C.Loeffler,A.Ligtenberger,and G.Moschytz,“Prac-
tical fast1-D DCT algorithms with11multiplications,”
Proc.ICASSP,pp.988–991,1989.
insomnia[12]N.Cho and S.Lee,“Fast algorithm and implementation
monitored
of the2D DCT,” Circuits and Systems, Vol.38,pp.297–305,Mar.1991.
[13]ISO/IEC JTC1/SC29WG1,JPEG2000Committee,Fi-
nal Draft Intl.Standard,Sep.25,2000.
