Robust perceptual image hashing using feature points

Perceptual image hashing maps an image to a fixed length binary string based on the image’s appearance to the human eye, and has applications in image indexing, authentication, and watermarking. In this paper, we present a general framework for perceptual

ROBUSTPERCEPTUALIMAGEHASHINGUSINGFEATUREPOINTS

VishalMongaandBrianL.Evans

EmbeddedSignalProcessingLaboratory,CenterforPerceptualSystems

TheUniversityofTexasatAustin,Austin,TX78712

{vishal,bevans}@ece.utexas.edu

ABSTRACT

Perceptualimagehashingmapsanimagetoa xedlengthbinarystringbasedontheimage’sappearancetothehu-maneye,andhasapplicationsinimageindexing,authenti-cation,andwatermarking.Inthispaper,wepresentagen-eralframeworkforperceptualimagehashingusingfeaturepoints.Thefeaturepointsshouldbelargelyinvariantun-derperceptuallyinsigni cantdistortions.Tosatisfythis,weproposeaniterativefeaturedetectortoextractsigni cantgeometrypreservingfeaturepoints.Weapplyprobabilis-ticquantizationonthederivedfeaturestofurtherenhanceperceptualrobustness.Theproposedhashalgorithmwith-standsstandardbenchmark(e.g.Stirmark)attacksinclud-ingcompression,geometricdistortionsofscalingandsmallanglerotation,andcommonsignalprocessingoperations.Contentchanging(malicious)manipulationsofimagedataarealsoaccuratelydetected.

1.INTRODUCTION

Incryptography,hashfunctionsaretypicallyusedfordig-italsignaturestoauthenticatethemessagebeingsentsothattherecipientcanverifyitssource.AkeyfeatureofconventionalhashingalgorithmssuchasMD5andSHA-1isthattheyareextremelysensitivetothemessage[1];i.e.,aonebitchangeintheinputchangestheoutputdramati-cally.Datasuchasdigitalimages,however,undergovariousmanipulationssuchascompressionandenhancement.

Animagehashfunctiontakesintoaccountchangesinthevisualdomain.Inparticular,aperceptualimagehashisrequiredtobeinvariantunderimagemanipulationsthatdonotaltertheimageappearancesigni cantly.Suchafunctioncouldbeusefulforidenti cation/searchofimagesinlargedatabases.Otherapplicationsofimagehashinglieintheareaofauthenticationandwatermarking[2].

Signi cantattentionhasbeengiventogeneratingdig-italsignaturesforimageauthenticationundercertainat-tacks.Thisincludesmethodsbasedonstatisticsoftheim-age(oritstransformedversion)[3,4],relation-basedmeth-odsthatuseinformationabouttheDCT/Waveletcoe -cientsoftheimage[5,6],andmethodsbasedonextractionoflow-levelimagefeaturessuchasedgesandcorners[7,8].

Acommoncharacteristicofthemethodsin[3]–[8]isthatwhiletheyauthenticatetheimageunderspecialformsofmanipulation,e.g.JPEGcompression,theyarestillvulner-abletoseveralincidentalmodi cationsthatdonotcauseperceptuallysigni cantchanges.

Robustimagehashingmethodsthattolerateawiderrangeofperceptuallyinsigni cantdistortionshavebeenproposedrecently[9–12].Themethodsinin[9]and[10]arerelationbased.In[11]Venkatesanetal.formahashbasedonanimagestatisticsvectorextractedfromsubbandsinawaveletdecompositionoftheimage.Mihcaketal.[12]developanotherhashbyusinganiterativeapproachtobi-narizetheDCsubband.

Wepresentaframeworkforperceptualimagehashingusingfeature-points.Currentapproachesbasedonfeaturepointshavelimitedutilityastheyhavepoorrobustnessproperties.Weextractsigni cantimagefeaturesbyus-ingawaveletbasedfeaturedetectionalgorithmbasedonthecharacteristicsofthevisualsystem[13].Further,aniterativeprocedurebasedonobservationsin[12]isusedtolockontoasetofimagefeature-pointswithexcellentinvariancepropertiestoperceptuallyinsigni cantpertur-bations.Unlike,theuseofpublic-keyencryptionschemesin[7],[8]probabilisticquantizationisusedtobinarizetheextractedfeaturevector.Previousworkonimagehashinghasfocussedextensivelyontheproblemofcapturingimagecharacteristicsbutperformancetrade-o ssuchasthosebe-tweenperceptualrobustness,fragilityandrandomizationofthehasharenotexplicitlyanalyzed.Thesetrade-o saredirectlyaddressedviaparametersinourhashalgorithm.

2.FEATUREEXTRACTION

2.1.End-StoppedWavelets

Psychovisualstudieshaveidenti edthepresenceofcertaincells,calledhypercomplexorend-stoppedcells,inthepri-maryvisualcortex[13].Forreal-worldscenes,thesecellsrespondstronglytoextremelyrobustimagefeaturessuchascornerlikestimuliandpointsofhighcurvatureingen-eral[14],[15].Bhattacherjeeetal.[15]constructed“end-stopped”waveletstocapturethisbehavior.Morletwaveletscanbeusedtodetectlinearstructureshavingaspeci corientation.Inspatialdomain,thetwodimensional(2-D)

Perceptual image hashing maps an image to a fixed length binary string based on the image’s appearance to the human eye, and has applications in image indexing, authentication, and watermarking. In this paper, we present a general framework for perceptual

Morletwaveletisgivenby[16]

ψM(x)=(e

jk0.x

e 1|k0|2)(e

1|x|2)(1)

wherex=(x,y)represents2-Dspatialco-ordinates,andk0=(k0,k1)isthewave-vectorofthemotherwavelet,whichdeterminesscale-resolvingpower(SRP)andangular-resolvingpower(ARP)ofthewavelet[16].Thefrequencydomainrepresentation,ψM(k),ofaMorletwaveletis

ψ

)=(e 1M(k|k k0|2 e 121

2|k0|)(e |x|)(2)

Here,krepresentsthe2-Dfrequencyvariable(u,v).Intwodimensions,theendpointsoflinearstructurescanbede-tectedbyapplyingthe rst-derivativeofGaussian(FDoG) lterparalleltotheorientationofstructuresinquestion.Thetwo lteringstages,the rsttodetectlineshavingaspeci corientationandthesecondtodetecttheend-pointsofsuchlines,canbecombinedintoasingle lter.Thisre-sultsinan“end-stopped”wavelet[15].Anexampleofanend-stoppedwaveletandits2-DFouriertransformfollow:

x2+y2

ψ(x,y)=1

+k0(k0 2jx)

E4

ye

(3)

ψ

E(u,v)=2πe

(u k0)2+(v)2 ( (u2+

)

)

jve

v2

(4)

Equation(4)showsthatψ

Eisaproductoftwocomponents.The rstisaMorletwaveletorientedalongtheu axis.ThesecondfactorisaFDoGoperatorappliedalongthefrequency-axisv,thatisinthedirectionperpendiculartotheMorletwavelet.Hence,thiswaveletdetectslineendsandhighcurvaturepointsintheverticaldirection.2.2.Proposedfeaturedetectionmethod

Ourapproachtofeaturedetectioncomputesawavelettrans-formbasedonanend-stoppedwaveletobtainedbyapplyingtheFDoGoperatortotheMorletwavelet:

ψE(x,y,θ)=(FDoG)o(ψM(x,y,θ))

(5)

Orientationtuningisgivenbyθ=tan 1(k).Lettheorientationrange[0,π]bediscretizedintoMintervals0

andthescaleparameterαbesampledexponentiallyasαi,i∈Z.Thisresultsinthewaveletfamily

ψE(αi(x,y,θk)

,α∈R,i∈Z

(6)

whereθk=(kπ)/M,k=0,...,M-1.Thetransformis

Wi(x,y,θ)=

f(x1,y1)ψE αi(x x1,y y1),θ

dx1dy1

(7)

Thesamplingparameterαischosentobe2.

Fig.1describestheproposedfeaturedetectionmethod.Themethodhastwofreeparameters:integerscaleiandrealthresholdT.WeadaptthethresholdTtoselecta xednumber(P)offeaturepointsfromtheimage.ThelengthPfeaturevectorislabeledasf.

————————————–

http://www.77cn.com.cnputethewavelettransformin(7)atasuitably

chosenscaleiforseveraldi erentorientations.Thecoarsestscale(i=1)isnotselectedasitistoosensitivetoglobalvariations.Finerthescale,themoresensitiveitistodistortionssuchasquantiza-tionnoise.Wechoosei=3.2.Locations(x,y)intheimagethatareidenti edascandidatefeaturepointssatisfy

Wi(x,y,θ)=

(x ,y max

)∈N

|Wi(x ,y,θ)|

(8)

(x,y)

whereN(x,y)representsthelocalneighborhoodof

(x,y)withinwhichthesearchisconducted.3.Fromthecandidatepointsselectedinstep2,qualifyalocationas nalfeaturepointif

maxθ

Wi(x,y,θ)>T

(9)

whereTisauser-de nedthreshold.

————————————–

Figure1:Featuredetectionmethodthatpreservessigni -cantimagegeometryfeaturepointsofanimage.

Previousapproaches[3,7,8]haveusedpublic-keyen-cryptionmethodsonimagefeaturestoarriveatadigitalsignature.Suchasignaturewouldbeverysensitivetosmallperturbationsinthefeaturepoints.Thefeaturepointsde-tectedforperceptuallysimilarimagesmaynotalwaysbeidenticalbut“close”.Forexample,asmallanglerotationwouldresultintheoriginalfeaturepointsshiftedslightlybasedontherotation.Moregenerally,weobservethatunderperceptuallyinsigni cantdistortionstotheimage,thefeaturepointsarepreservedina“probabilistic”sense.Tomaintainperceptualrobustness,wequantizethefea-turevectorbasedontheprobabilitydistributionoffeaturepointsextractedfromtheimage.Inparticular,weusethenormalizedhistogramoffasanestimateofitsdistribution.Thenormalizedhistogramappearstobelargelyinsensitivetoattacksthatdonotcausesigni cantperceptualchanges.

3.HASHALGORITHMS

ThehashfunctionforimageIisrepresentedasH(I)andletDH(·,·)denotethenormalizedHammingdistancebetweenitsarguments(binarystrings).3.1.Algorithm1–Deterministic

Mihcaketal.[12]observethatprimarygeometricfeaturesoftheimagearelargelyinvariantundersmallperturbationstotheimage.Theyproposeaniterative lteringschemethatminimizesthepresenceof“geometricallyweakcompo-nents”andenhances“geometricallystrongcomponents”by

Perceptual image hashing maps an image to a fixed length binary string based on the image’s appearance to the human eye, and has applications in image indexing, authentication, and watermarking. In this paper, we present a general framework for perceptual

meansofregiongrowing.Weadaptthealgorithmin[12]tolockontoasetoffeature-pointsthatarelargelypreservedinperceptuallysimilarversionsoftheimage.Thestoppingcriterionforourproposediterativealgorithmisachievinga xedpointforthebinarystringobtainedonquantizingthevectoroffeaturepointsf.Thealgorithmfollows:1.GetparametersMaxIter, andP,setcount=http://www.77cn.com.cnethefeaturedetectorinFig.1toextractthelengthPvectoroffeaturepointsf3.Quantizefinaprobabilisticsensetoobtainabinarystringb1f4.Performorder-statistics ltering.LetIos=OS(I;p,q,r)whichisthe2-Dorderstatistics lteringoftheinputI.Fora2-DinputX,Y=OS(X;p,q,r)where i,j,Y(i,j)isequaltotherthelementofthesortedsetofX(i ,j ),wherei ∈{i p,i p+1,...,i+p}andj ∈{j q,j q+1,...,j+q}.5.Performlow-passlinearshiftinvariant lteringonIos

toobtainIlp.6.Repeatsteps(2)and(3)withIlptoobtainb2f7.If(count=maxIter)gotostep8.

elseifDH(b1f,b2

f)< gotostep8.elsesetI=Ilpandgotostep2.8.SetH(I)=b2f

Step4eliminatesisolatedsigni cantcomponents.Step5preservesthe“geometricallystrong”componentsbylow-pass ltering(whichintroducesblurredregions).Thesuc-cessofthedeterministicalgorithmreliesupontheself-correctingnatureoftheiterativealgorithmaswellastherobustnessofthefeaturedetector.Theaboveiterativeal-gorithmisfairlygeneralinthatanyfeaturedetectorthatextractsvisuallyrobustimagefeaturesmaybeused.3.2.Algorithm2–Randomized

Randomizingthehashoutputisdesirablenotonlyforse-curityagainstinputsdesignedbyanadversary(maliciousattacks)butalsoforscalability,i.e.theabilitytoworkwithlargedatasetswhilekeepingthecollisionprobabilityfordistinctinputsincheck.RandomnessresultsfromusingthesecretkeyKtogenerateNrandomlocations(row-columnpairs)intheimage.ApartitioningofanimageintoNregions{Ri}Ni=1isthenobtainedusingk meansclus-tering[17].Therandomlocationsserveasinitialguessesfortheclustercenters.Finally,featurepointsareextractedfromeachrandomlyselectedregion(sub-image)andcom-binedtoformthecompletefeaturevector.

Weemployk-meansclusteringtopartitiontheimagefortwomajorreasons.First,theclusteringachievedbyk-meansdependsheavilyontheinitialchoiceofclustercen-ters[18].Sincetheinitialcentersaregeneratedrandomlybythesecretkey,thismakesthepartioningalsorandomandingeneralthesamepartioningcannotbeachieved(withahighprobability)unlessthesecretkeyisavailable.Second,theresultingclustershavefewornoregionsthatareverysmall.Itisimportanttoavoidverysmallregionssincethey

Table1:NormalizedHammingdistancebetweenhashval-uesoforiginalandattacked(similar)images.

wouldnotyieldinterestingandrobustimagefeatures.AslongasmostoftheRiarebigenoughthegeometricrobust-nesspropertiesofAlgorithm1areretainedinAlgorithm2.

4.RESULTS

Wecomparethehashvaluesobtainedfromtwodi erentim-agesforcloseness(butnotequality)inHammingdistance.LetIsimrepresentstheclassofimagessuchthatIsimisperceptuallysimilartoI.Likewise,aperceptuallydistinctimagewillbedenotedbyIdiff.Then,werequire

DH(H(I),H(Isim))<0.2(10)DH(H(I),H(Idiff))>0.3

(11)

Thisisareasonableapproachasperceptualsimilarityisnottransitive.PerceptualsimilarityofapairofobjectsAandBandofanotherpairBandCdoesnotimplythesimilar-ityofAandC.However,modelingofperceptualsimilaritybyequalityofhashvalueswouldleadtoatransitiverela-tionship.Asimilarapproachwastakenin[12].

Fig.2showsthreeperceptuallysimilarimagesandtheextractedfeaturepointsatalgorithmconvergence.TheoriginalbridgeimageisshowninFig.2(a).Figs.2(c)and(e),respectively,aretheimagein(a)attackedbyJPEGcompressionwithqualityfactor(QF)of10andadditivewhiteGaussiannoise(AWGN)withσ=20.The nalfea-turepointsforthethreeimages(Figs.2(b),(d)and(f))arelargelythesame(orclose).Table1tabulatesthequantita-tivedeviationasthenormalizedHammingdistancebetweenthehashvaluesoftheoriginalandmanipulatedimagesforvariousattacks.Theattackedimagesweregeneratedus-ingtheStirmarkbenchmarksoftware[19].Thedeviationislessthan0.2exceptforlargerotation(greaterthan5o)andcropping(morethan20%).Wealsotestedunderseveralcontentchangingattacksincludingobjectinsertionandremoval,additionofexcessivenoise,alterationofthepositionofimageelements,andalterationofasigni cantimagecharacteristicsuchastextureandstructure.Inallcases,thedetectionwasaccurate.Thatis,thenormal-izedHammingdistancebetweentheimageanditsattacked

Perceptual image hashing maps an image to a fixed length binary string based on the image’s appearance to the human eye, and has applications in image indexing, authentication, and watermarking. In this paper, we present a general framework for perceptual

(a)Original

Image

(b)Feature

Points

(c)

JPEG,QF=10(d)Feature

Points

(e)AWGN,σ=

20(f)FeaturePoints

Figure2:Original/attackedimageswithfeaturepointsatalgorithmconvergence.Featurepointsoverlaidonimagesversionwasfoundtobegreaterthan0.3.Theperceptualsigni canceofthehashishencevalidated.

5.PERFORMANCETRADE-OFFS

AsthenumberoffeaturepointsPincreases,thespeci ca-tionofimagecharacteristicsbecomesmorepreciseandthefragilitytoperceptuallydistinctinputsimprovesaswell.However,theclassofperceptuallysimilarinputsbecomessmaller.TheparameterPfacilitatesaperceptualrobust-nessvs.fragilitytrade-o .Pisinturndeterminedbythesizeofthesearchneighborhoodandthethresholdparame-terT(e.g.asmallTimpliesmorefeaturepoints).

WhenthenumberofrandompartitionsNisone,norandomnessisinvolvedandalgorithms1and2arethesame.IfNisverylarge,thentherandomregionsshrinktoanex-tentthattheydonotcontainsigni cantchunksofgeomet-ricallystrongcomponentsandhencetheresultingfeaturesarenotrobust.TheparameterNfacilitatesarandomnessvs.perceptualrobustnesstrade-o .

Thechoiceofalgorithmparametersisgovernedlargely

bytheapplication.Forimageindexing,thereisnomoti-vationtorandomize(N=1).Alsoinindexing,thehashcomputationshouldbefast,whereasrandomizationasinAlgorithm2comesatthecostofpartitioningtheimagepriortofeatureextraction.Forsecurityapplications,itmaybedesirabletorandomizeasmuchaspossibletominimizethevulnerabilityagainstmaliciousattacks.

6.REFERENCES

[1]A.Menezes,V.Oorschot,andS.Vanstone,Handbookof

AppliedCryptography,CRCPress,1998.

[2]G.L.Friedman,“Thetrustworthydigitalcamera:restor-ingcredibilitytothephotographicimage,”IEEETrans.ConsumerElectronics,vol.39,pp.905–910,Nov.1993.[3]M.SchneiderandS.F.Chang,“Arobustcontentbased

digitalsignatureforimageauthentication,”Proc.IEEEConf.ImageProc.,Sept.1996.

[4]C.KailasanathanandR.SafaviNaini,“Imageauthen-ticationsurvivingacceptablemodi cationsusingstatisti-calmeasuresandk-meansegmentation,”IEEE-EURASIPWork.NonlinearSig.andImageProc.,June2001.

[5]C.Y.LinandS.F.Chang,“Generatingrobustdigitalsig-natureforimage/videoauthentication,”Proc.ACMWork.onMultimediaandSecurity,Sept.1998.

[6]C.Y.LinandS.F.Chang,“Arobustimageauthenti-cationsystemdistingushingJPEGcompressionfromma-liciousmanipulation,”IEEETrans.CircuitsandSystemsforVideoTechnology,pp.153–168,Feb.2001.

[7]S.BhatacherjeeandM.Kutter,“Compressiontolerantim-ageauthentication,”Proc.IEEEConf.ImageProc.,1998.[8]J.Dittman,A.Steinmetz,andR.Steinmetz,“Content

baseddigitalsignatureformotionpictureauthenticationandcontent-fragilewatermarking,”Proc.IEEEInt.Conf.MultimediaComp.andSys.,pp.209–213,1999.

[9]J.FridrichandM.Goljan,“Robusthashfunctionsfordig-italwatermarking,”http://www.77cn.com.cn.Tech.:CodingandComp.,Mar.2000.

[10]C.-S.LuandH.-Y.M.Liao,“Structuraldigitalsignature

forimageauthentication,”IEEETrans.Multimedia,pp.161–173,June2003.

[11]R.Venkatesan,S.M.Koon,M.H.Jakubowski,and

P.Moulin,“Robustimagehashing,”Proc.IEEEConf.ImageProc.,Sept.2000.

[12]K.MihcakandR.Venkatesan,“Newiterativegeometric

techniquesforrobustimagehashing,”Proc.ACMWork.SecurityandPrivacyinDig.RightsMan.,Nov.2001.

[13]D.H.HubelandT.N.Wiesel,“Receptive eldsandfunc-tionalarchitectureintwononstriatevisualareasofthecat,”J.Neurophysiology,pp.229–289,1965.

[14]A.Dobbins,S.W.Zucker,andM.S.Cynader,“End-stoppingandcurvature,”VisionResearch,1989.[15]S.BhatacherjeeandP.Vandergheynst,“End-stopped

waveletsfordetectinglow-levelfeatures,”Proc.SPIEWaveletAppl.inSig.&ImageProc.,pp.732–741,1999.[16]J.-P.AntoineandR.Murenzi,“Two-dimensionaldirec-tionalwaveletsandthescale-anglerepresentation,”Sig.Proc.,pp.259–281,1996.

[17]J.B.MacQueen,“Somemethodsforclassi cationandanal-ysisofmultivariateobservations,”Proc.Sym.Math,Statis-ticsandProbability,pp.281–297,1967.

[18]A.GershoandR.M.Gray,VectorQuantizationandSig.

Compression,KluwerAcademic,1991.

[19]“Fairevaluationproceduresforwatermarkingsystems,”

http://www.77cn.com.cn/fabien/watermarking/stirmark,2000.

本文来源：https://www.bwwdw.com/article/8ooi.html