Real-time texture synthesis by patch-based samplin

Real-TimeTextureSynthesisByPatch-BasedSamplingLinLiang,CeLiu,YingqingXu,BainingGuo,[e-mail]2001TechnicalReportMSR-TR-2001-40Wepresentapatch-basedsamplingalgorithmforsynthesizingtex-turesfromaninputsampletexture.Thepatch-basedsamplingalgo-rithmisfast.Usingpatchesofthesampletextureasbuildingblocksfortexturesynthesis,thisalgorithmmakeshigh-qualitytexturesyn-thesisareal-timeprocess.Forgeneratingtexturesofthesamesizeandcomparable(orbetter)quality,patch-basedsamplingisordersofmagnitudefasterthanexistingtexturesynthesisalgorithms.Thepatch-basedsamplingalgorithmsynthesizeshigh-qualitytexturesforawidevarietyoftexturesrangingfromregulartostochastic.Bysamplingpatchesaccordingtoanon-parametricestimationofthelo-calconditionalMRFdensity,weavoidmismatchingfeaturesacrosspatchboundaries.Moreover,thepatch-basedsamplingalgorithmre-mainseffectivewhenpixel-basednon-parametricsamplingalgorithmsfailtoproducegoodresults.Fornaturaltextures,theresultsofthepatch-basedsamplinglooksubjectivelybetter.MicrosoftResearchMicrosoftCorporationOneMicrosoftWayRedmond,WA98052fill-inandimage/videocompression.Thetexturesynthesisproblemmaybestatedasfollows:GivenaninputsampletextureIin,synthesizeatextureIoutthatissufficientlydifferentfromthegivensampletexture,yetappearsperceptuallytobegeneratedbythesameunderlyingstochasticprocess.Inthiswork,weusetheMarkovRandomField(MRF)asourtexturemodelandassumethattheunderlyingstochasticprocessisbothlocalandstationary.WechooseMRFbecauseitisknowntoaccuratelymodelawiderangeoftextures.Othersuccessfulbutmorespecializedmodelsincludereaction-diffusion[17,19],frequencydomain[10],andfractals[5,20].Inrecentyears,anumberofsuccessfultexturesynthesisalgorithmshavebeenproposedingraphicsandvision.Motivatedbypsychologystudies,HeegerandBergendevelopedapyramid-basedtexturesynthesisalgorithmthatapproximatelymatchesmarginalhistogramsoffilterresponses[7].Zhuetal.introducedamath-ematicalmodelcalledFRAME,whichintegratesfiltersandhistogramsintoMRFmodelsandusesaminimaxentropyprincipletoselectfeaturestatistics[24,25].Severaltexturesynthesisalgorithmsarebasedonmatchingjointstatisticsoffilterresponses.DeBonet’salgorithmmatchesthejointhistogramofalongvectoroffil-terresponses[3].PortillaandSimoncellidevelopedaniterativeprojectionmethodformatchingthecorrelationsofcertainfilterresponses[14].Thesemethods,alongwithmanyothersintheliterature[8,21],representtwodifferentapproachestotex-turesynthesis.Thefirstistocomputeglobalstatisticsinfeaturespaceandsampleimagesfromthetextureensemble[23]directly[7,3,14,23].Thesecondapproachistoestimatethelocalconditionalprobabilitydensityfunction(PDF)andsynthe-sizepixelsincrementally[24].Thetexturesynthesisalgorithmweproposefollowsthesecondapproach.Insomeearlierwork,Zhuetal.exploredthisapproachusingtheanalyticalFRAMEmodelandanaccuratebutexpensiveMarkovchainMonteCarlomethod[24].Morerecently,EfrosandLeungdemonstratedthepowerofsamplingfromalo-calPDFbypresentinganon-parametricsamplingalgorithmthatsynthesizeshigh-qualitytexturesforawidevarietyoftexturesrangingfromregulartostochastic[4].EfrosandLeung’salgorithm,whilemuchfasterthan[24],isstilltooslow.In-1Figure1:Texturesynthesisexample.Left:192192inputsampletexture.Right:256256texturesynthesizedbypatch-basedsampling.Thesynthesistakes0.02secondsona667MHzPC.spiredbyacluster-basedtexturemodel[13],WeiandLevoysignificantlyacceler-atedEfrosandLeung’salgorithmusingtree-structuredvectorquantization(TSVQ)[18].However,thisTSVQ-acceleratednon-parametricsamplingalgorithmisstillnotreal-time.Anotherproblemwith[4]and[18]isthat,forsometextures,[4]isagreedyalgorithmthathasatendencyto“slip”intoawrongpartofthesearchspaceandstarttogrowgarbage.TheTSVQacceleration[18]furtheraggravatesthisproblem.Inthispaperweshowthathigh-qualitytexturecanbesynthesizedinreal-time.Akeyingredientofthealgorithmweproposeisapatch-basedsamplingschemethatusestexturepatchesofthesampletextureasbuildingblocksfortexturesynthesis.Theadvantagesofpatch-basedsamplingincludespeedForsynthesizingtexturesofthesamesizeandcomparable(orbetter)qual-ity,ouralgorithmisordersofmagnitudefasterthanexistingtexturesynthesisalgorithms,includingTSVQ-acceleratednon-parametricsampling[18].Asaresult,high-qualitytexturesynthesisisnowareal-timeprocessonamid-levelPC.qualityThepatch-basedsamplingalgorithmsynthesizeshigh-qualitytexturesforawidevarietyoftexturesrangingfromregulartostochastic.Like[4,18],oursisalsoagreedyalgorithmfornon-parametricsampling.However,thep