Robust Detection of Region-Duplication Forgery in Digital Image

WeiqiLuo,JiwuHuang

GuangDongKeyLab.ofInformationSecuritySunYat-SenUniversity,Guangzhou,China,510275

GuopingQiu

SchoolofComputerScience

UniversityofNottingham,NG81BB,UK

isshjw@mail.sysu.edu.cn

Abstract

Regionduplicationforgery,inwhichapartofadigitalimageiscopiedandthenpastedtoanotherportionofthesameimageinordertoconcealanimportantobjectinthescene,isoneofthecommonimageforgerytechniques.Inthispaper,wedescribeanefficientandrobustalgorithmfordetectingandlocalizingthistypeofmalicioustamper-ing.Wepresentexperimentalresultswhichshowthatourmethodisrobustandcansuccessfullydetectthistypeoftamperingforimagesthathavebeensubjectedtovariousformsofpostregionduplicationimageprocessing,includ-ingblurring,noisecontamination,severelossycompres-sion,andamixtureoftheseprocessingoperations.

1.Introduction

Rapidadvancementinimagingtechnologyhasmadeitremarkablyeasytomanipulatedigitalimagecontents.Withtheproliferationofdigitalcamerasandcomputers,aswellassoftwareforimageediting,theproblemofdigitalim-ageforgeryispotentiallyveryserious.Digitalimagecoun-terfeitinghasalreadyappearedinmanydisturbingforms.Forexample,inthe2004Americapresidentialelection,awidelycirculatedphotographshowingtheDemocraticcan-didateandafamousHollywoodactresssharedademonstra-tionpodiuminthe1970swasafakeinfact[1].ApopularBritishnewspaperwasforcedtoapologizeforpublishingphotographsshowingBritishsoldiersabusinganIraqipris-oner,whichwereprovedtobefakes[2].Theseexamplesarejustatipoftheiceberganditwillgetworse.

Recently,severalresearchershavestartedtodeveloptechniquesfordetectingvariousformsofimageforgery.FaridandPopescudevelopedseveralstatisticalmethodsfordetectingforgeriesbasedonregionduplication,colorfilterinterpolation,andre-sampling[3-6].Fridrichpresentedamethodfordetectingcopy-movetypeofforgery[7].NgandChangproposedmodelsofimagespicingfordetect-ingphotomontage[8].Theyhavealsorecentlydeveloped

The 18th International Conference on Pattern Recognition (ICPR'06)0-7695-2521-0/06 $20.00 © 2006

qiu@cs.nott.ac.uk

physics-basedmodelfordistinguishingComputerGraphicsfromnaturalphotographs[9].

Acommonformofdigitalimagetamperingisobjectre-moval,whereregionsofunwantedobjectsinsideanimagearereplacedbypixelsfromotherpartoftheimage.Sev-eralresearchershavedevelopedmethodsfordetectingthisformofforgery.In[7],theauthorsanalyzedtheDCTcoef-ficientsforeachblock,whilemethod[4]employsprincipalcomponentanalysistocapturetheimageblocks’features.Inthispaper,weproposeanefficientandrobustalgo-rithmfordetectingandlocatingduplicatedregionswithinanimagethusexposingpossibletamperingoftheimage.Comparedwiththemethodsin[4]and[7],ouralgorithmhaslowercomputationalcomplexityandismorerobustagainststrongerattacksandvarioustypesofafter-copyingmanipulations,suchaslossycompressing,noisecontami-nation,blurringandacombinationoftheseoperations.

2.ModelofRegion-DuplicationForgery

DuetothenatureofRegion-Duplication,therewillbeatleasttwosimilarregionsinthetamperedimage.However,inmostnaturalimages(exceptforimageswithlargesmoothregions),itisunusualtohavetwolargesimilarregionsinanimage.Ouranalysisonover100naturalimagesshowsthat,insideasingleimage,itisunlikelytohavetwoverysimilarregionsthatarelargerthan0.85%oftheimagesize.Thetaskoffindingregionduplicationforgeryisthatoffindingtwolargesimilarregions.SeetheFig.1.

Figure1.Region-DuplicationForgery

Givenanimagef(x,y),thetamperedimagef󰀁(x,y),mustsubjectto:∃regionsD1andD2aresubsetsofDandashiftvectord=(dx,dy),(weassumethat|D1|=|D2|>

|D|∗0andf󰀁

.(85%x,y)and=|fd(|x>−Ldx,),f󰀁y(x,−ydy))=iff((x,x,yy))if∈(Dx,y)∈/D2

2,whereD1isthesourceandD2isthetargetregion,D2=D1+d.Itwouldbeeasytodetectaboveforgeryviaexactmatch.However,tomakethetamperedimagehardertodetect,theattackermayperformvariousprocessingonf󰀁(x,y)=Θ(f󰀁((x,x,yy))).Thenthetamperedimagebecomesf󰀁󰀁,whereΘistheprocessingoperator,suchasJPEGcompres-sionandaddingnoise.Thepostprocessingattackmakesthetaskofdetectingforgerysignificantlyharder.Inthenextsection,wepresentanefficientmethodfordetectingregionduplicationforgerywhichisalsorobustagainstvar-iousformsofpostregionduplicationprocessing.

3.ProposedAlgorithm

Ouralgorithmfirstdividesanimageintosmallover-lappedblocksanditthencomparesthesimilarityoftheseblocksandfinallyidentifiespossibleduplicatedregions.Detailprocedureisasfollows:

1)ExtractingblockCharacteristicsVector.Theinputim-ageissplitintooverlappingblocksofb×bpixels.Assum-ingthattheimageisanMxNcolorimage,thereareS=(M-b+1)x(N-b+1)blocks.ForeachblockBi(i=1,2...S),sevencharacteristicsfeaturescj(j=1,2...7)arecomputed.

i)c1,c2,c3aretheaverageofred,green,andbluecom-ponentsrespectively.

ii)IntheYchannel(Y=0.299R+0.587G+0.114B),wedi-videtheblockinto2equalpartsin4directionsasshowninFig.2andcomputec4,c5,c6,c7accordingto

ci=sum(part(1))/sum(part(1)+part(2))

i=4,5,6,7Figure2.FourDirections

Thesecharacteristicsfeatureswillnotchangesignifi-cantlyaftersomecommonprocessingoperations.TakingadditivewhiteGaussiannoise(AWGN)operationforexam-ple,weassumethatthenoiseforeachpixelεisani.i.d.withmean0andvariancev.ThenoisyblockisB󰀁󰀁i=Bthenc1=c1+ε󰀁(whereE(ε󰀁)=0,D(ε󰀁)=v/(b2

i+ε

)),when,

b≥16,wehavec󰀁1≈c1.Similarly,wehavec󰀁

󰀁ε2≈c2and

c3≈c3.c󰀁

4=(sum(part(1))+1)/(sum(part(1)+part(2))+ε2),whereE(ε1)=0,E(ε2)=0,D(ε1)=b2v/2,D(ε2)=b2v.Usuallysum(part(1))󰀈ε1,sum(part(1)+part(2))󰀈ε󰀁2whenvissmall(SNR≥18db),thereforecFor4≈c4.andc5,c6andc7havesimilarproperties.JPEGcompres-sionandGaussianblurring,theseoperationswilldiscardsomehighfrequencycomponentsbutchangethelowfre-quencycomponentsslightly.Socj(j=1...7)arerobust

The 18th International Conference on Pattern Recognition (ICPR'06)0-7695-2521-0/06 $20.00 © 2006

totheseoperations.ForeachblockBi,ablockcharacter-isticsvectorV(i)=(c1(i),c2(i),c3(i),c4(i),c5(i),c6(i),c7(i))is

computedandsavedinanarrayA.

2)Searchingsimilarblockpairs.ThearrayAislexi-cographicallysorted.ForeverypairBiandBj,wecom-putetheirsimilarityusingtheirrespectivecharacteristicsfeaturevectorV(i)andV(j)inAasfollows:LetDiff(k)=|ck(i)-ck(j)|,ifthefollowingconditionsaresatisfied(whereP(k)’s,t1andt2arepresetthresholds):(i)Diff(k)(ii)Diff(1)+Diff(2)+Diff(3)(iii)Diff(4)+Diff(5)+Diff(6)+Diff(7)3)Findingcorrectmatchingblockpairs.Notallsimilarblockpairsin2)areequallylikelytocomefromtwodupli-catedregions.Therefore,weneedtoidentifythosesimilarblocksthatcomefromtwoduplicatedregionsandremovethosethatarenot.Assumingthatthesourceandthetargetregionsarelargerthantheblocksize,thenallcorrespond-ingblocksinthesourceandthetargetregionswillhavethesameshiftvectors.AssumingthatblockB1(i)isablockinthesourceregionandB2(i)isitscorrespondingblockinthetargetregion,thenwehaveShift(B1(i),B2(i))=Shift(B1(j),B2(j)),asillustratedinFig.3.

Figure3.TheSameShiftVector

Basedonthisobservation,weusetheshiftvectorsofthesimilarblockpairstocompileahistogram,H(d󰀁)=H(dx󰀁,dy󰀁),whichrecordsthefrequencyofoccurrenceoftheshiftvectorbetweentwosimilarblocks.Wethenidentifytheshiftvectorhavingthehighestfrequencyofoccurrenceasthemainshiftvector,d=arg(max(H(d󰀁)).Weregardasim-ilarblockpairasincorrectmatchingpairwhenitsshiftvec-torismuchdifferentfromd.Letd=(dx,dy),wediscardallpairswhoseshiftvectord󰀁=(dx󰀁,dy󰀁)satisfy|dx󰀁-dx|>2or|dy󰀁-dy|>2.Allremainingsimilarblocksarethenputinabinaryimagethesamesizeastheoriginalimagewiththeareascoveredbytheblockssettoawhitevalueandtherestsettoablackvalue.Wethenperformtheopeningop-erationtoeliminatesmallislandsandthenfillholesforallconnectedcomponentsonbinaryimage[10].Thisisarea-sonableapproachbecauseiftwoblocksaresimilarandnot

causedbyaregionduplication,then,itisunlikelytherewillbemanyofsuchblockshavingthesameshiftvector.

4)Determiningforgery.Afterfindingtwolargecon-nectedregions,ouralgorithmdetermineswhetherare-gionduplicationtamperinghasoccurredbasedonfollow-ingrules.LetR1andR2aretworegionsobtainedfromaboveprocedure,ifmin(|R||RR1|,|R2|)>r,whereαM*N*0.85%,αandTrand1|−|2||/max(|R1|,|R2|)4.ExperimentalResults

Inourexperiments,allimagesareof300x400pixels.Theparametersaresetasfollow:P(1)=P(2)=P(3)=1.80,P(4)=P(5)=P(6)=P(7)=0.0125,t1=2.80,t2=0.02,b=16,L=50.

Iftag=0buttheinputimageistampered(failtode-tectforgery),ortag=1buttheimageisauthentic(wrongdetection),wesetJ=1.OtherwiseJ=0.

Iftheinputimageisaforgeryandtag=1,wedefinetheaccuracyr,andthefalsenegativew:

r=

|R1∩D1|+|R2∩D2||R1∪D1|+||D1|+|D2|,w=R2∪D2|

|D1|+|D2|

−r

ThefirstexampleisshowninFig.4.Thetamperedimage

isdetectedwithr=0.9888,w=0.1266.

Figure4.Left:Originalimage,Middle:Tam-peredimage,Right:DetectedRegion

ThetamperedimageisthendistortedbylossyJPEGcompressionandadditivewhiteGaussiannoise.Fig.5showthedetectionresultscomparingwiththatof[4](us-ingdefaultparametersandprocessgreenchanneltoyieldduplicationmaps).

Wecanseethatouralgorithmachievesbetteraccuracy,andismorerobusttoattacks.EvenwiththeJPEGqual-ityfactordecreasingtoaslowas30,ouralgorithmcanstillachiever=0.8474andw=0.2170.Forthenoisyim-agewithSNR=16db,ouralgorithmstillmanagetoachieve

The 18th International Conference on Pattern Recognition (ICPR'06)0-7695-2521-0/06 $20.00 © 2006

Figure5.RobusttoJPEG(Left),AWGN(Right)r=0.8479andw=0.1956.Thealgorithmin[4]failedwhentheJPEGqualityfactorwassmallerthan50orSNRwaslowerthan24db.OuralgorithmisalsorobustagainstGaussianblurring(5x5window,δ=1)andacombinationofGaussianblurring,AWGNwithSNR24db,andJPEGlossycompressionatqualityfactorof60.Thedetectionresultsare:Gaussianblurring:(r,w)=(0.9920,0.1291).Mixedoperations:(r,w)=(0.9176,0.1751).Similarde-tectionresultsareobtainedinanotherexample(downloadedfrom[4],seeFig.6).Thetamperedimagewithoutprocess-ingoperationsisdetectedwithr=0.9953,w=0.0878.Fig.7showthedetectionresultsforvariouspostregionduplicationcompressionandnoisecontaminationcompar-ingwith[4].ForGaussianblurringandMixedopera-tions,ouralgorithmachievesfollowingresults:GaussianBlurring:(r,w)=(0.9931,0.0905).Mixedoperations:(r,w)=(0.9631,0.0966).

Figure6.Example2

Figure7.RobusttoJPEG,AWGN

Inordertotesttheefficiencyandrobustnessofoural-gorithmfurther,wecollected100images.Foreachim-age,arandomsquareregionwascopiedthenpastedontoanon-overlappingposition.Thetamperedimagesarethendistortedbydifferentprocessingoperations.Inourtest,thesquareregions’sizesareof32x32,48x48,xand80x80.Theaverager,wandJover100imagesareshowninFig.8,andthetables1-5.

Figure8.RobusttoJPEG,AWGNTable1.Withoutanyprocessing

32*3248*48*80*80¯r1.00001.00001.00001.0000w¯0.06790.040.03750.0328¯J0.060.0100Table2.GaussianBlurring

32*3248*48*80*80¯r0.94780.97900.98460.9870w¯0.12610.07220.05130.0433¯J0.050.0100Table3.FalseJudgmentforJPEG

¯J40506070809032*320.300.120.100.050.050.08*480.080.020.020.010.010.01*0.040000080*800.0100000Table4.FalseJudgmentforNoisyimages

¯J20db24db28db32db36db40db32*320.200.060.070.090.100.0848*480.050.020.010.010.010.01*0.010000080*800.0100000Table5.MixtureOperations

32*3248*48*80*80¯r0.72750.86350.88490.9027w¯0.46690.16120.13480.1131¯J0.080.0100Allthetablesandfiguresaboveshowthatthebiggertheblocksizescopiedandthehigherthequalities,thebetterarethedetectionresults.Ingeneral,ifthecopiedblockisbiggerthan1.9%ofthetamperedimage,thedetectionre-sultsaregood.Inevitablythereareafewimageswronglyjudged,especiallyfortheimageswithsimilarregionsorwithlargesmoothregionsortheimagehadbeendistortedbadly.Webelievethathumaninterpretationisnecessaryinthesespecialcases.Wemaychangetheparametersaccord-ingtodifferentimages,orspecifyasuspiciousregiontomatchoreliminatesomeauthenticregionsbeforeapplying

The 18th International Conference on Pattern Recognition (ICPR'06)0-7695-2521-0/06 $20.00 © 2006

thealgorithm.Inourexperience,suchhumaninterventioncanalwaysfindthetamperedregions.

5.ConcludingRemarks

Region-duplicationforgeryisaneffectivetechniquetoremoveanobjectindigitalimage.Inthispaper,wehaveproposedanovelalgorithmtodetecttamperedimagesau-tomaticallyandeffectively.Comparedwith[4]and[7],ouralgorithmhaslowercomputationalcomplexityandismorerobustagainstvariouspostregionduplicationimagepro-cessingoperations.Advancesincomputervisionandcom-putergraphicshavemadeimagemanipulationmoreandmoresophisticated(seeforexample[11],[12]),Howtode-tectforgeriesusingtheseadvancedcomputergraphicstech-nologiesremainsanopenquestion.

Acknowledgement:Wethanktheauthorsof[4]forpro-vidingthecodeoftheiralgorithm,andthesupportre-ceivedfromNSFC(60325208,90604008),NSFofGuang-dong(042007).

References

[1]K.Light.Fonda,KerryandPhotoFakery.TheWashington

Post,Saturday,Feb.28,2004,PageA21.

[2]VoiceoftheMirror.Sorry..wewerehoaxed:IraqiPoWabuse

pictureshandedtousWEREfake.DailyMirrorNewspaper,15May2004

[3]H.Farid.Apicturetellsathousandlies.NewScientist,6Sep.

2003

[4]A.C.PopescuandH.Farid.Exposingdigitalforgeriesbyde-tectingduplicatedimageregions.TechnicalReportTR2004-515,DartmouthCollege,Aug.2004.

[5]AC.PopescuandH.Farid.ExposingDigitalForgeriesin

ColorFilterArrayInterpolatedImages.IEEETrans.onsignalprocessing,53(10):3948-3959,Oct.2005.

[6]A.C.PopescuandH.Farid.ExposingDigitalForgeriesbyDe-tectingTracesofResampling.IEEETrans.onSignalProcess-ing,53(2):758-767,Feb.2005

[7]J.Fridrich,D.Soukal,andJ.Lukas.DetectionofCopy-Move

ForgeryindigitalImages.Proc.ofDigitalForensicResearchWorkshop,Aug.2003.

[8]T-TNg,S-FChang.AModelforImageSplicing.ICIP,1169-1172Vol.2,Oct.2004

[9]T-TNg,etal.Physics-MotivatedFeaturesforDistinguishing

PhotographicImagesandComputerGraphics.InACMMul-timedia,239-248,Nov.2005

[10]R.C.GonzalezandRichardE.woods.DigitalImagePro-cessing.PearsonEducation,2002.

[11]A.Criminisi,P.P’erezandK.Toyama.RegionFillingand

ObjectRemovalbyExemplar-BasedImageInpainting.IEEETrans.onimageprocessing,13(9):1200-1212,Sept.2004.[12]L-YWei.TextureSynthesisbyFixedNeighborhoodSearch-ing.Ph.D.dissertation,StanfordUniversity,Nov.2001.