Enhancement of JPEG-compressed images by re-application of JPEG

AriaNosratinia(aria@utdallas.edu)

DepartmentofElectricalEngineering,UniversityofTexasatDallas,Richardson,TX75083

Abstract.Anovelmethodisproposedforpost-processingofJPEG-encodedim-ages,inordertoreducecodingartifactsandenhancevisualquality.Ourmethodsimplyre-appliesJPEGtotheshiftedversionsofthealready-compressedimage,andformsanaverage.Thisapproach,despiteitssimplicity,offersbetterperformancethanotherknownmethods,includingthosebasedonnonlinearfiltering,POCS,andredundantwavelets.

Keywords:JPEG,imagecompression,enhancement,postprocessing

1.Introduction

Blocktransformcodingofimages,viatheDiscreteCosineTransform(DCT),hasprovedtobeasimpleyeteffectivemethodofimagecom-pression.Differentimplementationsofthismethodhavefoundwidespreadacceptanceviainternationalstandardsforimageandvideocompres-sion,suchasJPEGandMPEGstandards.

Thebasicapproachforblock-transformcompressionisfairlysimple.Theencodingprocessconsistsofdividingtheimageintoblocks,typi-callyofsize8×8.Ablocktransform,typicallytheDCT,isappliedtotheseblocks,andthetransformcoefficientsareindividuallyquantized(scalarquantization).Toefficientlyrepresenttheresultingdata,certainlosslesscompressionoperationsareperformedonthequantizeddata,typicallyconsistingofazig-zagscanofcoefficientsandentropycoding.AsimplifieddiagramofthisoverallprocessisshowninFigure1.

Theblockencodingprocess,whilesimpleandefficient,alsointro-ducesanumberofundesirableartifactsintotheimage;themostnotableareblockingartifacts(discontinuitiesattheblockboundaries)andringingartifacts(oscillationsduetotheGibbsphenomenon).Theseartifactsbecomemorepronouncedwithincreasingcompressionratio.AsignificantbodyofworkhasevolvedtoaddresstheenhancementofDCT-compressedimages.TheproblemofJPEGimageenhancement,inparticular,isofgreatinterestduetothefactthatthenumberofJPEGencodedimagesiscurrentlyinthemillions,andwillcontinuetoriseforatleastthenextfewyears,wellbeyondtheimpendingintroductionofJPEG2000.Aprimeexampleofthisproliferationis

c2002KluwerAcademicPublishers.PrintedintheNetherlands.󰀂

final.tex;21/10/2002;13:01;p.1

2

DC Coefficients

DPCMSource/Image

DCTQAC CoefficientsEntropyCodingHeaders/SyntaxJPEGCode

QuantizationTablesDesignHuffmanTablesHuffmanTablesFigure1.TheJPEGencodingsystem

ontheInternet,wherenumerouswebpagesuseJPEGencodedimages.Anotherexamplearetheimagesproducedbydigitalcameras.

InthispaperwepresentanovelpostprocessingtechniqueforthereductionofcompressionartifactsinJPEG-encodedimages.Thisap-proachisasignificantdeparturefromtheprevioussignalprocessingmethods,inthatitdoesnotspecificallylookatthediscontinuitiesatblockboundaries,neitherdoesitmakedirectuseofsmoothnesscriteria.ItusestheJPEGprocessitselftoreducethecompressionartifactsoftheJPEG-encodedimage.Thisapproachisveryeasytoimplementand,despiteitssimplicity,hashighlycompetitiveperformance.

2.Background

PastworkontheenhancementofJPEG-encodedimageshaslargelyfocusedonenforcingvarioussmoothnesscriteriaonthecompressedimage.Themodelforsmoothnessorcontinuityoftheimagecanbedeterministicorstochastic,andtheenforcementofthemodelcanvary,fromregularization-basedoptimizationtoprojectiononconvexsets(POCS)toadaptiveandspace-varyingfilters.

Theearliestattemptsinenhancingblock-encodedimagesinvolvedspace-invariantfiltering[1].Itwasquicklydiscovered,however,thatspace-invariantfiltersaregenerallynotveryeffectiveforthisapplica-tion;theyeitherdonotremoveenoughoftheartifacts,oroversmooththeimage.

Space-varyingfiltersprovideamoreflexibleframeworkforthere-ductionofcompressionartifacts.Anearlyexampleoftheapplicationofspace-varyingoperationstoblock-encodedimagesappearedin[2].Spacevaryingmethodsusuallyinvolveaclassificationstep.Forex-ample,KuoandHsieh[3]classifyimageblocksaccordingtohight

final.tex;21/10/2002;13:01;p.2

3

orlowACactivity,andapplytheenhancementprocessonlyontheactiveblocks.Thealgorithmin[3]involvesedgedetection,andthespace-varyingfilterisdesignedsuchthatitdoesnotsmooththeedges.Inadifferentspace-varyingapproach,Chouetal.[4]andXiongetal.[5]classifytheblockboundariesaccordingtothelocalactivityintheimage:Ifthediscontinuityatablockboundaryissmallcomparedtothelocalenergyintheimage,thenitislikelythatthediscontinuityisentirelyduetoquantization,thereforeastrongfilteringoperationisperformedonit.However,verylargediscontinuitiesatblockbound-ariesarelesslikelytobeduetoquantizationalone,thereforeamildersmoothingoperationisperformedonthem,sothattheimageedgesarepreserved.

Anumberofotherrelatedmethodsalsodependonclassificationandspace-varyingoperations,e.g.[6,7,8].

AnotherclassofpostprocessorsutilizeareconstructionmethodknownasProjectiononConvexSets(POCS).UsageofPOCSforimagerecon-structiongoesbacktotheworkofYula[9],andYulaandWebb[10].Thismethodisbasedonthewell-knowntopologicalpropertythatthenonemptyintersectionofasetofclosedconvexsetsisitselfaclosedconvexset.Thisintersectioncanbereachedthroughrepeatedalternateprojectionsontotheoriginalsets.Inthepostprocessingapplication,oneconvexsetconsistsofalloriginalimagesthatarequantizedtothegivencompressedimage.Theotherconvexsetsaredefinedtoexpressthesmoothnessoftheoriginalimage.Theintersectionofallthesesets,asfoundbyPOCS,isabetterapproximationtotheoriginalimagethanthecompressedimageitself.POCSiselegantindesign,butitsconvergenceiscriticallydependentonthea-prioriassumptionthattherepresentativesetshavenonemptyintersection.

OneoftheearliestPOCSpostprocessorsforJPEGwasproposedbyZakhor[11],1wherethesmoothnessconvexsetconsistsoflowpassbandlimitedimages.ReevesandEddins[12]pointedoutthatanon-ideallowpassfilter,liketheoneusedin[11],isnotaprojectionoperatorandthereforethealgorithm,strictlyspeaking,cannotbeclassifiedasPOCS,butisratheraconstrainedoptimizationmethod.Yangetal.[15]proposedadifferentconvexsetconsistingofimageswithatotaldiscon-tinuityacrossblockboundarieslessthanagiventhreshold(Figure2);thisworkwasextendedin[16]viaaspatiallyadaptiveconvexset.OtherworkutilizingPOCSforJPEGpostprocessingincludes[17,18].

ConstrainedoptimizationisthebasisofanotherfamilyofJPEGpostprocessors.Asubsetofthisclassisknownasregularization,a

Thisworkhasbeensubjecttorepeatedinaccuratecitation,includingin[12,13,14,15,16]

1

final.tex;21/10/2002;13:01;p.3

4

Figure2.TraditionalJPEGdenoisingconcentratesonblockdiscontinuities.

methodtosolveill-posedinverseproblems.Yangetal.[15]proposedaregularizationschemeforaconstrainedleastsquaressolutiontothepostprocessingproblem.Theconstrainedleastsquaresapproacharisesfromthedesiretoremainwithinthequantizationconvexset(constraint)butatthesametimeminimizethehighpassenergyofthesignal(expressedasleastsquares).[15]usedaregularizationmethodtosolvethisproblem.Hongetal.[19]appliedregularizationmethodsinthesubbanddomaintoreduceDCTartifactsinimages.

Anotherfamilyofpostprocessorsarebasedonsophisticatedstochas-ticmodelingoftheimage.Allpost-processorsuseaprioriknowledgeoftheimageproperties.However,inthemodel-basedapproach,theaprioriassumptionsandtheirintroductionintothealgorithmaremoreexplicit.MarkovRandomFields(MRF)areamongthemoresuccessfulmodelsappliedtoimageenhancement.ThealgorithmofO’RourkeandStevenson[13]appliesmaximuma-posteriori(MAP)estimationunderaMarkovprior,whileconstrainingthesolutiontotheDCTquantizationhypercube.LiandKuo[20]developedamultiscaleMAPtechnique,againundertheMRFprior.BecauseoftheiterativeprocedurenecessaryforthegenerationofMarkovRandomFields,MRFtechniqueshaveahighcomputationalcomplexity.

Strictlyspeaking,compressiondistortionisnotarandomnoise,inthesensethattheadditivedistortioninducedbycompression,condi-tionedontheoriginal(input)image,iscompletelydeterministic.Undercertainconditions,however,compressionnoiseisuncorrelatedwiththequantized(output)image.Therefore,denoisingtechniquesoriginallyintendedforrandomnoisesituationscansometimesbeappliedtothe

final.tex;21/10/2002;13:01;p.4

5

enhancementofcompressedimages.Amongthemostsimpleandef-fectivedenoisingalgorithmsarethoseusingthewavelettransform.Gopinathetal.[21]proposedanenhancementmethodinvolvingtheoversampledwavelettransform,inconjunctionwithasoftthresholdingmotivatedbytheminimaxargumentsofDonoho[22].Gopinathetal.findthethresholdbasedonaMMSEestimationofthequantizationnoise.AnotherversionofoversampledwaveletdenoisingwasemployedbyXiongetal.[5].Wenotethattheoversampledwaveletdenois-ingofGopinathaswellasthatofXiongarebothvariationsontheso-calledtranslation-invariantdenoisingintroducedbyCoifmanandDonoho[23].

IntheabovewepresentedaquickoverviewofthemainapproachestopostprocessingJPEGencodedimages.Forthesakeofbrevity,someexistingalgorithmswerenotindividuallymentioned,amongthem[14,24,25,26,27,28,29].Thesealgorithmsusevariantsorcombinationsofthetechniquesalreadymentionedinthissection.

3.JPEGdenoisingthroughJPEG

3.1.Algorithm

WepresentasimpleandpowerfultechniquefortheenhancementofJPEG-compressedimages.Ouralgorithmisadramaticdeparturefromtheknownenhancementtechniques,andsimplyconsistsofapplyingshiftedversionsoftheJPEGcompressionoperatortotheJPEG-compressedimage.Thealgorithmissummarizedbelow:

1.Shiftthecompressedimagesinverticalandhorizontaldirectionsby(i,j).2.ApplyJPEGtoshiftedimage.

3.Shifttheresultback,i.e.verticallyandhorizontallyby(−i,−j).4.Repeatforallpossibleshiftsintherange[−3,4]×[−3,4]5.Averageallimages

ThequantizationparameterandthequantizationmatrixoftheJPEG,forthepostprocessingpurposes,issettothesamevaluesasthecompressedimage.Thisshouldpresentnodifficulties,sincetheheaderoftheoriginalJPEGimagecontainsallnecessaryinformation.TheblockdiagramofourpostprocessingalgorithmisshowninFigure3.

final.tex;21/10/2002;13:01;p.5

6

z1z2z1z2-3-3-3-2JPEGJPEGJPEGJPEG-1-1z1z2z1z23233Noisy Image-2-3z1z2JPEGJPEGJPEGJPEG-1-123z1z2Enhanced Imagez1z2-2-2z1z222z1z244JPEGJPEG-1z1z2-4-4Figure3.Systemdiagram

zzzz-32122412zzOriginal JPEGblock boundaries1-212Figure4.OurJPEGpostprocessingusesvariousshiftsofJPEG,threerepresentativeshiftsshowninthisfigure.

final.tex;21/10/2002;13:01;p.6

7

ThedualshiftingoftheimageineachbranchofFigure3essentiallyamountstoanetshiftoftheboundariesoftheblockencodingpro-cess,asillustratedinFigure4.Thisdemonstratesabasicmotivationbehindouralgorithm:TheJPEGencodingprocessisknowntoreducesthehigh-frequencycontentoftheimage.Inotherwords,thehigh-frequencycomponentsoftheimagearequantizedmorecoarselythanlowerfrequencies.Butatthesametime,highfrequencycomponentsareintroducedattheedgesoftheblocks,becausetheseedgeseffectivelyarenot“seen”intheDCTblock-spectrumofJPEG.BytakingvariousshiftsofJPEG,theoriginalblockboundarieswillbeexposedtothefrequencyshapingoftheJPEGencodingprocess,thusthemagnitudeoftheblockinesswillbereduced.

Thissecondaryencodingprocessitselfwillproducenewblockbound-aries,albeitsmallerthantheoriginalone.Onecanputthesenewblockboundariesatanygivenlocation,bycontrollingtheshiftofthesecondaryJPEGencoding.However,thereisnoreasontopreferanygivenlocationoveranother,thereforeweaverageallshiftssothatthesecondaryblockinessisdiffusedoverallpixels.Infact,withthisprocess,almostnoblockingeffectsarevisibleinthefinalpostprocessedimage.3.2.RelationtoKnownDenoisingTechniques

Thealgorithmproposedinthispaper,whileinappearanceandop-erationverydifferentfrompreviousapproaches,infactcombinestwopowerfulideasfromimagedenoising:redundantrepresentationsandthedualityofquantizationanddenoising.

Recently,waveletexpansionshaveemergedasarobustandpow-erfultoolformanysignalprocessingapplications,inparticularimagedenoising[22].Waveletbasesprovideefficientrepresentationsofsignals,whichisdesirableinmanyapplications,e.g.compression.However,inotherapplications,suchasdenoising,efficiencyofrepresentationisnotanobject.Ithasbeenknown,infact,thatredundantrepresentations(frames)performbetterthanbasesindenoisingapplications[30].

Asimpleexplanationfortheperformanceofredundantdenoisingalgorithmsisthattheinversetransformforaframe(asopposedtoabasis)isaMoore-Penrosepseudoinverse.Looselyspeaking,theframeinversetransformcontainsaveraging,whichhelpsreducetheeffectofnoise.Xiongetal.[5],forexample,harnessedthepowerofthistech-niqueandusedredundantwavelets,alongwithedgeclassificationandsoftthresholdingnonlinearitiesfortheirenhancementalgorithm.

Ourmethodiscloselyrelatedtotheoversampled(redundant)waveletdenoisingtechniques.ThediagraminFigure3showsthatJPEGencod-inganddecodingareperformedsuccessivelyineachbranch,therefore

final.tex;21/10/2002;13:01;p.7

8

z1z2z1z2-3-3-3-2DCTDCTQQDCTDCT-1-1z1z2z1z23233Noisy Image-2-3z1z2DCTDCTQQDCTDCT-1-123z1z2Enhanced Imagez1z2-2-2z1z222z1z244DCTQDCT-1z1z2-4-4Redundant ExpansionFigure5.JPEGenhancementalgorithmseenfromtheviewpointofredundantexpansions

thelosslesspartsofJPEGcanberemovedforourpurposes,leadingtothesimplifieddiagramofFigure5.ThisdiagramshowsthatourJPEGenhancementalgorithmcanbeviewedasaredundantdenoisingalgorithm,wherequantizationplaystheroleofdenoisingnonlinearities.Thisbringsustothesecondmainideaunderlyingtheproposedalgorithm:thedualityofquantizationanddenoising[31].Toexpressthisrelationshipanditsutilizationinouralgorithm,welookatoptimalquantization,optimalMMSEdenoising,andtheirrelationship.

AssumetheavailableobservationsxareasummationofaGaussiansignalsandamemorylessGaussiannoisen.

x=s+n

(1)

Bayesianquadraticmeanestimationrequiresthatthedecorrelatedcom-ponentsoftheobservedsignalbescaledaccordingto:

2σs

xxˆ=22σs+σn

(2)

Therefore,optimaldenoisingofGaussiansignalsrequirealinearoper-ationonthediagonalizedversionofthesignal.

Ontheotherhand,optimalquantization,againfortheGaussiansignals,isachievedviatheinversewater-fillingalgorithm[32].This

final.tex;21/10/2002;13:01;p.8

9

argument,whichisusedtojustifytransformcoding,statesthatoptimalquantizationisachievedviaadiagonalizingtransform.Toachieveop-timality,transformcomponentsbelowacertainenergyareeliminated,andothersarequantizedsoastoproduceequalerrorenergy.

Atfirstsight,thesetwoapproachesmayseemdifferent,butinap-plicationtheyareveryclose.Toseethispoint,notethatthelinearexpressionfortheoptimaldenoisingoperatorrequiresknowledgeofthepoweroftheoriginal(uncorrupted)signalandnoise.Butinprac-tice,estimatingthesequantitiescanbearatherdifficulttask.Onecanlookattheinversewater-fillingalgorithmasanapproximationoftheoptimalGaussiandenoisinginmanypracticalsituations,because:−Forcomponentswherethesignalisweakerthanthenoise,the

linearexpression(2)isapproximatedbyzero.Thiscorrespondstoacoarsequantizationthatmapssmallsignalstozero.−Forcomponentswherethesignalisgreaterthanthenoise,the

denoisingfraction(2)isclosetoone.Thisexpressioncanagainbeapproximatedbyquantization,becausewhenquantizeddistortionismuchsmallerthansignalpower,quantizationitselfisalmostequivalenttoanattenuation[33].Tosummarize,thisalgorithmeffectivelyusesaredundant(frame)expansionapproachtosignaldenoising,wheretheframeexpansionisanoversampledDCT.ThedenoisingnonlinearitiesareprovidedbythescalarquantizersinJPEG.3.3.QuantizationLevels

Thequestionremains:howtosetthequantizationlevelsinthesec-ondary(denoising)JPEG?ExperimentsshowthatthebestresultsareobtainedwhenthesecondaryJPEGquantizationisidenticaltothequantizationmatrixintheoriginalimage.Inourexperiments,weperturbedthequantizationmatrixbyamultiplyingconstantα.Wetestedvaluesofαbothgreaterthanandlessthanunity.Inallsuchexperiments,bothathighandlowbitrates,thequantizationmatrixbestsuitedfordenoisingwasthesameastheoneusedforcompression.Fromapracticalpointofview,thisshouldpresentnodifficulties,sincethequantizationmatrixisrepresentedintheJPEGheaderoftheoriginalimage,andcanbeextractedeasily.3.4.ImageBoundaries

Theshiftingoperationinouralgorithmneedstobemodifiedclosetotheimageboundaries.Weofferthreesolutionsattheimageboundaries:

final.tex;21/10/2002;13:01;p.9

10

−Symmetricextension−Rowandcolumnreplication−Zero-shiftreplacement

Thesymmetricextensionworksasfollows:whentheshiftrequiresthatpartoftheexistingblockgooutsideoftheimageboundaries,thedatais“thrownaway.”Whenitrequiresdatafromoutsidetheimageboundaries,theimageisextendedsymmetrically.Thesymmetricextensioncanbeeitheroddorevenattheboundary.

Thereplicationmethodissimilartothesymmetricextension,exceptthatthedatashiftedfromoutsideofimageboundariesissimplyareplicationoftheboundaryrow/column.Oursimulationresultswereobtainedusingthismethod.

Thezero-shiftreplacementtechniqueforaboundaryblockworksasfollows:anyshiftsthatcanbeperformedwithoutreferencetopixelsoutsideofimageboundaryareperformedasusual.IfinanybranchinFigure3aknowledgeofpixelsoutsidetheimageboundaryisrequired,thenthatbranchwillbereplacedwiththezero-shiftbranch.Thismeansthatboundaryblockswillreceivelesssmoothingthanotherblocks.

4.ComputationalIssues

AtfirstglancethesystemshowninFigure3seemsfairlyinvolved.Whileadirectimplementationofthissystemissimplerthanoptimization-basedandmodel-basedapproachesmentionedinSection2,itstillinvolves64timesJPEGcompressionanddecompression.

Adirectimplementationofthissystemhastheadvantagethatvir-tuallynoadditionalsoftwareorhardwareisrequired.ExistingJPEGcodeand/orhardwarecanbeappliedwiththeadditionofsomeshiftoperators.Whencomputationalcomplexitybecomesanissue,however,onecanimprovethespeedofthealgorithmbyanumberofverysimplemodifications:

−ThesimplestmodificationisinthebranchwithzeroshiftinFig-ure3.TheJPEGencodinganddecodinginthisbranchcanbere-moved.Thereason:JPEGisanidempotentoperator,inthesensethatreapplicationofJPEGwithidenticalparameterstoaJPEG-compressedimagewillresultinthesameJPEG-compressedimage.Thereforethebranchwithzeroshiftcanbereplacedwithaniden-tityoperator,savingthecomputationofoneJPEGcompressionanddecompression.

final.tex;21/10/2002;13:01;p.10

11

−Thesecondmodificationismuchmoresignificant,andinvolvesthe

removalofthelosslesspartsofJPEG(Figure1).SinceJPEGcom-pressionisdirectlyfollowedbydecompressioninouralgorithm,thelosslesspartsofJPEGplaynorole,andcanberemoved.ThisincludesDPCMonDCvalues,zig-zagscan,generationofHuffmantables,entropycoding,andthegenerationofsyntaxandheaders.TheonlypartsneededaretheDCTandthescalarquantiza-tion.Scalarquantizationisimplementedasatruncationoperation,thereforethebulkofthecomputationalcomplexityofourmethodwillresideintheDCTandinverseDCT.Thisisasignificantreductionincomputationalcomplexity.−Finally,wenotethatnotallshiftsinFigure3arenecessary.In

fact,weobservedthatremovinghalfoftheshifts(inaquincunxpattern)doesnotsignificantlychangetheoutputofthealgorithm.Wethereforerecommenditasacomputationalshortcut.TheoperationsofouralgorithmdependsonlittleelseexcepttheDCTandIDCT,sothecomplexitycanbeeasilydetermined.Theexactnumberofoperationsneededforthisalgorithmdependsontheimple-mentationchosenforDCTandIDCT.Forexample,weshowbelowacomplexityanalysisofouralgorithmwiththe2-DDCTimplementationofFeigandLinzer[34].Thisisa8×8DCTthattakesadvantageoftheredundanciesinthetwo-dimensionallatticeoftheDCTtodesignanimplementationwith60multiplicationsand262additionsperblock.Wesawabovethattheblockwithzeroshiftneednotberecalculatedduringpostprocessing.Fromamongtheothershifts,onlyone-halfneedbecomputed.Thereforeweneed31DCTandIDCToperationsover

×60≈58multiplicationsperpixeltheimage.Thisgivesatotalof2×3164×262≈254additionsperpixelforthisalgorithm.Toputand2×3164thesenumbersinperspective,thecomputationalcomplexityoftheproposedalgorithmisroughlysimilartothecomplexityreportedforthe“simplifiedalgorithm”in[16],butissubstantiallysmallerthanthatof[11].

Beforeleavingthesubjectofimplementationandcomputation,wenotethattheimplementationoftheproposedalgorithminvolvesonlyasmallengineeringeffort(hencecost),sinceitneedslittlebeyondtheDCTandIDCT,andthetransformalreadyexistsineachimplemen-tationofJPEG.

final.tex;21/10/2002;13:01;p.11

12

5.OptimalMMSEEstimation

Theproposedalgorithmcanbeviewedasalinearcombinationofanumberofestimatesoftheimage.Toillustrate,weusethefollowingnotation.Assumethattheoriginalimageisdenotedbyavectorx,theJPEG-encodedimagebyxˆ,andthedenoisedimagebyy.AssumethatthesuccessionofJPEGencodinganddecodingprocessisrepresentedbytheoperatorQ.UsingthedelayoperatornotationD,wecanwrite:

󰀁y=D(−i,−j)Q(D(i,j)xˆ)(3)

i,j

EachterminthesumrepresentsonebranchofthesysteminFigure3.

Asimpleanddirectextensionistoreplacethesumwithalinearcombination:󰀁

y=αi,jD(−i,−j)Q(D(i,j)xˆ)(4)

i,j

wherethecoefficientsαi,jcanbedetermined,viaatrainingset,to

makeyanoptimalMMSEestimatoroftheoriginalimage.

Weappliedthistechniquetoatrainingsetofimages,andtheresult-ingcoefficientsareshowninFigure6.Weseethat,withtheexceptionofzeroshift,allshiftshavealmostthesamecoefficient.Thezero-shiftcoefficientissignificantlylargerthanothers.

Whilethisisalargedeviationfromtheuniformcoefficientsother-wiseusedinthispaper,wefoundthattheoptimalcoefficientsresultinlittleifanyadditionalimprovementinthePSNRoftheenhancedimage.Thisleadsustobelievethat,inthespaceofcoefficients,thedistortioncostfunctionmustberatherflat.Wethereforerecommendthesimpleruniformcoefficientsetovertheoptimalone.

6.ExperimentalResults

TheresultsareveryencouragingbothintermsofPSNRandvisualquality.Infact,thePSNRimprovementsaresuperiortopreviouslyreportedresultsknowntous.TableIIcomparestheperformanceofthenewalgorithmwithsomeresultsintheliterature.Thetestimageisthegreencomponentofthe512×512pixel“Lenna.”Forcomparisonpurposes,weusethethreequantizationtablesoriginallyintroducedin[11],andalsousedin[5,16].Thesequantizationtablesarepre-sentedinTableI.TableIIIpresentstheresultsoftheapplicationofouralgorithmtoanumberof512×512-pixeltestimages.

WeobservedaslightlydifferentJPEGPSNRcomparedto[5,16](ontheorderofafewhundredthsofadB)whichweattributeto

final.tex;21/10/2002;13:01;p.12

13

10.80.60.40.208765432112345678Figure6.CoefficientsforoptimalcombiningofJPEGshiftssmalldifferencesinJPEGimplementation.Inordertomaintainfairnessdespitesmallimplementationdifferences,wereportnottheabsolutePSNR,buttheimprovementinPSNRineachcase.

Figure7showspartoftheJPEGandenhancedimageatthelowerPSNRrange.Notetheimprovementinde-blocking,aswellasperse-veranceofedges.

7.Conclusion

InthispaperwepresentedanovelapproachtotheenhancementofJPEGencodedimages.Mostpreviousapproachesinvolveasmooth-nesscriterion,andinonewayoranotherfocusonthediscontinuitiesgeneratedbytheblock-encodingprocess.Incontrast,ouralgorithmusestheJPEGencodingitselftoenhancetheJPEG-compressedimage.ThisisperformedthroughapplicationofvariousshiftsofJPEGtotheencodedimage.Theboundariesoftheimagecanbetreatedinanumberofways.Thecomputationalcomplexityofthealgorithmissmallerthantheoptimization-basedapproaches,andcanbefurtherreducedbyremovingthelosslesspartsofJPEG,aswellasdownsamplingtheshiftsatwhichitisapplied.Experimentalresultsdemonstrateexcellentperformance,andalarge-scalereductionofbothblockinessandringingartifacts.

final.tex;21/10/2002;13:01;p.13

14

TableI.Quantizationtablesusedinexperiments.

Q1

20242832368098144

242428345270128184

2828324874114156190

32344858112128174196

365274112136162206224

8070114128162208242200

98128156174206242240206

144184190196224200206208

Q2

5060707090120255255

60607096130255255255

707080120200255255255

7096120145255255255255

90130200255255255255255

120255255255255255255255

255255255255255255255255

255255255255255255255255

Q3

110130150192255255255255

130150192255255255255255

150192255255255255255255

192255255255255255255255

255255255255255255255255

255255255255255255255255

255255255255255255255255

255255255255255255255255

final.tex;21/10/2002;13:01;p.14

15

Figure7.Top:PartofJPEGencoded512×512Lennaat26.65dB.Bottom:Enhancedimagethroughre-applicationofJPEG.

final.tex;21/10/2002;13:01;p.15

16

Figure8.Top:JPEGencoded512×512Lennaat26.65dB.Bottom:Enhancedimage.

final.tex;21/10/2002;13:01;p.16

17

TableII.ImprovementsinPSNRonJPEG-encodedimagesviadifferentalgorithms,onimage“Lenna”(greencomponent).

ImprovementinPSNRWavelet[5]Adaptive[4]

1.140.790.10

1.060.790.45

JPEGPSNR

26.6529.7432.34

POCS[16]1.140.850.45

Ourmethod

1.161.030.66

TableIII.ImprovementsinPSNR,throughtheproposedalgorithm,onanumberoftestimagesatvariousbitrates.

Quantization

Q1Q2Q3

Lenna0.661.031.16

Mandrill0.190.230.40

Stream0.230.420.55

Goldhill0.520.740.91

Barbara1.040.891.04

References

1.2.

H.C.ReevesandJ.S.Lim,“Reductionofblockingartifactsinimagecoding,”OpticalEngineering,vol.23,pp.34–37,Jan./Feb.1984.

B.RamamurthiandA.Gersho,“Nonlinearspace-variantpostprocessingofblockcodedimages,”IEEETransactionsonAcoust.SpeechSignalProcess.,vol.34,pp.1258–1267,October1986.

C.J.KuoandR.J.Hsieh,“Adaptivepostprocessingforblockencodedimages,”IEEETransactionsonCircuitsandSystemsforVideoTechnology,vol.5,no.4,pp.298–304,1995.

J.Chou,M.Crouse,andK.Ramchandran,“Asimplealgorithmforremovingblockingartifactsinblock-transformcodedimages,”IEEESignalProcessingLetters,vol.5,pp.33–35,February1998.

Z.Xiong,M.Orchard,andY.Zhang,“AdeblockingalgorithmforJPEGcompressedimagesusingovercompletewaveletrepresentations,”IEEETrans-actionsonCircuitsandSystemsforVideoTechnology,vol.7,pp.433–437,April1997.

A.Kundu,“EnhancementofJPEGcodedimagesbyadaptivespatialfiltering,”inProc.IEEEICIP,vol.II,(Washington,D.C.),pp.187–191,October1995.W.E.Lynch,A.Reibman,andB.Liu,“Postprocessingtransformcodedimagesusingedges,”inProc.IEEEICASSP,vol.IV,(Detroit,MI),pp.2323–2326,May1995.

K.Sauer,“Enhancementoflowbit-rateencodedimagesusingedgedetectionandestimation,”ComputerVision,GraphicsandImageProcessing,pp.52–62,1991.

3.

4.

5.

6.7.

8.

final.tex;21/10/2002;13:01;p.17

18

9.

D.C.Yula,“Generalizedimagerestorationbythemethodofalternatingor-thogonalprojections,”IEEETransactionsonCircuitsandSystems,vol.25,pp.694–702,1978.

D.YulaandH.Webb,“Imagerestorationbythemethodofconvexprojections:PartI-theory,”IEEETransactionsonMedicalImaging,vol.1,pp.81–94,October1982.

A.Zakhor,“Iterativeproceduresforreductionofblockingartifactsintrans-formimagecoding,”IEEETransactionsonCircuitsandSystemsforVideoTechnology,vol.2,pp.91–95,March1992.

S.J.ReevesandS.I.Eddins,“Commentsoniterativeproceduresforreductionofblockingeffectsintransformcoding,”IEEETransactionsonCircuitsandSystemsforVideoTechnology,vol.3,pp.439–440,December1993.

T.P.O’RourkeandR.L.Stevenson,“Improvedimagedecompressionforre-ducedtransformcodingartifacts,”IEEETransactionsonCircuitsandSystemsforVideoTechnology,vol.5,pp.490–499,December1995.

M.-Y.ShenandC.-C.J.Kuo,“Reviewofpostprocessingtechniquesforcompressionartifactremoval,”JournalofVisualCommunicationandImageRepresentation,vol.9,pp.2–14,March1998.

Y.Yang,N.Galatsanos,andA.Katsaggelos,“Regularizedreconstructiontoreduceblockingartifactsofblockdiscretecosinetransformcompressedim-ages,”IEEETransactionsonCircuitsandSystemsforVideoTechnology,vol.3,pp.421–432,December1993.

Y.Yang,N.Galatsanos,andA.Katsaggelos,“Projection-basedspatiallyadap-tivereconstructionofblock-transformcompressedimages,”IEEETransactionsonImageProcessing,vol.4,pp.896–908,July1995.

J.K.SuandR.M.Mersereau,“Post-processingforartifactreductioninJPEG-compressedimages,”inProc.IEEEICASSP,vol.IV,(Detroit,MI),pp.2363–2366,May1995.

K.Y.KwakandR.A.Haddad,“Projection-basedeigenvectordecompositionforreductionofblockingartifactsofDCTcodedimage,”inProc.IEEEICIP,vol.II,(Washington,D.C.),pp.527–530,October1995.

S.-W.Hong,Y.-H.Lee,andW.-C.Siu,“Subbandadaptiveregulariza-tionmethodforremovingblockingartifacts,”inProc.IEEEICIP,vol.II,(Washington,D.C.),pp.523–527,October1995.

J.LiandC.-C.J.Kuo,“Codingaritactremovalwithmultiscalepostprocess-ing,”inProc.IEEEICIP,vol.I,(SantaBarbara,CA),pp.45–48,October1997.

R.A.Gopinath,M.Lang,H.Guo,andJ.E.Odegard,“Wavelet-basedpost-processingoflowbitratetransformcodedimages,”inProc.IEEEICIP,pp.913–917,1994.

D.Donoho,“Denoisingbysoftthresholding,”IEEETransactionsonInforma-tionTheory,vol.IT-41,pp.613–627,May1995.

R.R.CoifmanandD.L.Donoho,“Translation-invariantdenoising,”inWaveletsandStatistics,SpringerLectureNotesinStatistics103,(NewYork:SpringerVerlag),pp.125–150,1994.

S.MinamiandA.Zakhor,“Anoptimizationapproachforremovingblockingeffectsintransformcoding,”IEEETransactionsonCircuitsandSystemsforVideoTechnology,vol.5,pp.74–81,April1995.

N.C.Kim,I.H.Jang,D.H.Kim,andW.H.Hong,“Reductionofblockingartifactinblock-codedimagesusingwavelettransform,”IEEETransactionsonCircuitsandSystemsforVideoTechnology,vol.8,pp.253–257,June1998.

10.

11.

12.

13.

14.

15.

16.

17.

18.

19.

20.

21.

22.23.

24.

25.

final.tex;21/10/2002;13:01;p.18

19

26.

Y.-H.Chan,S.-W.Hong,andW.-C.Siu,“Apracticalpostprocessingtechniqueforreal-timeblock-basedcodingsystem,”IEEETransactionsonCircuitsandSystemsforVideoTechnology,vol.8,pp.4–8,February1998.

S.-C.Hsia,J.-F.Yang,andB.-D.Liu,“Efficientpostprocessorforblockyeffectremovalbasedontransformcharacteristics,”IEEETransactionsonCircuitsandSystemsforVideoTechnology,vol.7,pp.924–929,December1997.

G.Lakhani,“ImprovedequationsforJPEG’sblockingartifactsreductionap-proach,”IEEETransactionsonCircuitsandSystemsforVideoTechnology,vol.7,no.6,pp.930–934,1997.

Z.WangandD.Zhang,“Anovelapproachforreductionofblockingeffectsinlow-bit-rateimagecompression,”IEEETransactionsonCommunications,vol.46,pp.732–734,June1998.

M.Lang,H.Guo,J.E.Odegard,C.S.Burrus,andR.O.Wells,“Noisereduc-tionusinganundecimateddiscretewavelettransform,”IEEESignalProcessingLetters,vol.3,pp.10–12,January1996.

B.Natarajan,“Filteringrandomnoisefromdeterminicsignalsviadatacom-pression,”IEEETransactionsonSignalProcessing,vol.43,pp.2595–2605,November1995.

G.DavisandA.Nosratinia,“Wavelet-basedimagecoding:anoverview,”ApplidandComputationalControl,Signals,andCircuits,vol.1,no.1,1998.N.S.JayantandP.Noll,DigitalCodingofwaveforms.EnglewoodCliffs,NJ:Prentice-Hall,1984.

E.FeigandE.Linzer,“Discretecosinetransformalgorithmsforimagedatacompression,”inElectronicImaging’90East,(Boston,MA),pp.84–87,October1990.

27.

28.

29.

30.

31.

32.33.34.

Author’sVitae

AriaNosratiniareceivedhisB.S.inElectricalEngineeringfromUni-versityofTehran,M.A.Sc.fromUniversityofWindsor,andPh.D.inElectricalandComputerEngineeringfromtheUniversityofIllinoisatUrbana-Champaignin1996.Duringtheacademicyear1995-96,hewaswithPrincetonUniversity,Princeton,NewJersey.From1996to1999,hewasavisitingprofessorandfacultyfellowatRiceUniversity,Houston,Texas.InJuly1999hejoinedthefacultyoftheUniversityofTexasatDallasasAssistantProfessorofElectricalEngineering.

Dr.NosratiniahasreceivedtheNationalScienceFoundationCareeraward(2000)andtheTexasHigherEducationCoordinatingBoardAdvancedResearchProgramaward(1999).Hisresearchisintheareaofdigitalsignalprocessing,imageprocessing,andcodingofimagesandvideo.Hehascontributedtotwobooks,AppliedandComputa-tionalControl,SignalsandCircuitsandWavelets,Subbands,andBlockTransformsinCommunicationsandMultimedia.Hislatestinterestsareinwirelesscommunicationofmultimediasignals.

final.tex;21/10/2002;13:01;p.19

final.tex;21/10/2002;13:01;p.20