Block-matching-and-3D-filtering-算法详解

Imageandvideodenoisingbysparse3Dtransform-domaincollaborativefilteringBlock-matchingand3Dfiltering(BM3D)algorithm块匹配三维协同滤波算法Anovelimagedenoisingstrategy•Anenhancedsparserepresentationintransformdomain.•Theenhancementofthesparsityisachievedbysimilar2-Dimagefragments(e.g.,blocks)into3-Ddataarrayswhichwecall“groups.”•Collaborativefilteringisaspecialproceduredevelopedtodealwiththese3-Dgroups.•Usingthethreesuccessivesteps:•1.3-Dtransformationofagroup.•2.shrinkageofthetransfomspectrum.•3.inverse3-Dtransformation.•Aggregationisaparticularaveragingprocedurewhichisexploitedtotakeadvantageoftheredundancy.sparserepresentation（稀疏表示）•稀疏编码是从人的生理特性出发，从而发展起来的。人的视网膜细胞很多，但是对事物敏感的细胞单元却很少，从这点出发，我们可以对输入图像进行稀疏表示，用一组稀疏系数表示，从而达到了对图像信息的压缩。•比如把一个句子中的字母比作像素，单词比作经过稀疏表示过后的稀疏元素，那么字典就表示单词和字母的映射关系。单词和字母都可以表示这个句子，但是单词的个数是要远远小于字母的个数，这样字母到单词的转换，就是对这个句子信息的压缩。Grouping•Groupingistheconceptofcollectingsimilard-dimensionalfragmentsofagivensignalintoagivensignalintoad+1-dimentisonaldatastructurethatweterm“group.”•Groupingcanberealizedbyvarioustechniques.•Theimportanceofgroupingistoenabletheuseofahigherdimensionalfilteringofeachgroup,whichexploitsthepotentialsimilarity(correlation,affinity,e.t.c.)betweengroupedfragmentsinordertoestimatethetruesignalineachofthem.•Theapproachwedenominatecollaborativefiltering.Groupingbymatching•Matchingisamethodforfindingsignalfragmentssimilartoagivenreferenceone.•Achievingbypairwisetesting•Distanceissmallerthanthreshold•Block-matching(BM)（块匹配）isaparticularmatchingapproachthathasbeenextensivelyusedformotionestimationinvideocompression(MPEG1,2,and4,andH.26x).Asaparticularwayofgrouping,itisusedtofindsimilarblocks,whicharethenstackedtogetherina3-Darray(i.e.,agroup).CollaborativeFiltering（协同滤波）•Nfragment-Nestimates•Collaborativemeanseachgroupedfragmentcollaboratesforthefilteringofallothers,andviceversa.•Thegroupedblocksexhibitperfectmutualsimilarity,whichmakestheelementwiseaveraging(i.e.,averagingbetweenpixelsatthesamerelativepositions)asuitableestimator.•However,perfectlyidenticalblocksareunlikelyinnaturalimages.Ifnonidenticalfragmentsareallowedwithinthesamegroup,theestimatesobtainedbyelementwiseaveragingbecomebiased（有偏差）CollaborativeFilteringbyShrinkageinTransformDomain•Assuming–dimensionalgroupsofsimilarsignalfragmentsarealreadyformed,thecollaborativeshrinkagecomprisesofthefollowingsteps.•Applyad+1-dimensionallineartransformtothegroup.•Shrink(e.g.,bysoft-andhard-thresholdingorWienerfiltering)thetransformcoefficientstoattenuatethenoise.•Invertthelineartransformtoproduceestimatesofallgroupedfragments•Thesegroupsarecharacterizedbyboth:•interfragmentcorrelationwhichappearsbetweenthepixelsofeachgroupedfragment—apeculiarityofnaturalimages;（同组内的像素）•interfragmentcorrelationwhichappearsbetweenthecorrespondingpixelsofdifferentfragments—aresultofthesimilaritybetweengroupedfragments.（不同组但相同位置的像素）Thebenefitofthecollaborativeshrinkage•A2-Dtransformisappliedseparatelytoeachindividualblockinagivengroupofn（个）fragments.•Sincethesegroupedblocksareverysimilar,foranyofthemweshouldgetapproximatelythesamenumber,a（个）significanttransformcoefficients.•Itmeansthatthewholegroupoffragmentsisrepresentedbyna（个）coefficients.•If1-DtransformthatacrossthegroupedblockshasaDC-basiselement,thenbecauseofthehighsimilaritybetweentheblocks,thereareapproximatelyonlya（个）significantcoefficientsthatrepresentthewholegroupinsteadofna;Algorithm•Theinputnoisyimageisprocessedbysuccessivelyextractingreferenceblocksfromitandforeachsuchblock:•findblocksthataresimilartothereferenceone(blockmatching)andstackthemtogethertoforma3-Darray(group);•performcollaborativefilteringofthegroupandreturntheobtained2-Destimatesofallgroupedblockstotheiroriginallocations.•Afterprocessingallreferenceblocks,theobtainedblockestimatescanoverlap,and,thus,therearemultipleestimatesforeachpixel.Weaggregatetheseestimatestoformanestimateofthewholeimage.hard-thresholding硬阈值滤波basicestimateempiricalWienershrinkagecoefficients经验维纳滤波系数CollaborativeWienerFiltering•AggregationWeights•AggregationbyWeightedAverageFASTANDEFFICIENTREALIZATION•Reducethenumberofprocessedblocks.•Reducethecomplexityofgrouping.•Reducethecomplexityofapplyingtransforms.•Realizeefficientlytheaggregation.•Reducethebordereffects.