数字图像处理 图像分割

数字图像处理

（DigitalImageProcessing）图像分割Imagesegmentationdividesanimageintoregionsthatareconnectedandhavesomesimilaritywithintheregionandsomedifferencebetweenadjacentregions.

Thegoalisusuallytofindindividualobjectsinanimage.Forthemostparttherearefundamentallytwokindsofapproachestosegmentation:discontinuityandsimilarity.Similaritymaybeduetopixelintensity,colorortexture.Differencesaresuddenchanges(discontinuities)inanyofthese,butespeciallysuddenchangesinintensityalongaboundaryline,whichiscalledanedge.ConceptsandApproachesWhatisImageSegmentation?ImageSegmentationMethodsThresholdingBoundary-basedRegion-based:regiongrowing,splittingandmergingConceptsandApproachesPartitionanimageintoregions,eachassociatedwithanobjectbutwhatdefinesanobject?Howtodefinethesimilaritybetweenregions?FromProf.XinLiAssumption:therangeofintensitylevelscoveredbyobjectsofinterestisdifferentfromthebackground.ThresholdingMethodThresholdingMethodthresholdinghistogramsinglethresholdmultiplethresholdsFrom[Gonzalez&Woods]GlobalThresholdingThresholdingMethod:BasicGlobalThresholding选取一个全局阈值T的初始估计用T分割图像为两部分：G1和G2计算区域G1和G2中的灰度均值m1和m2计算新的阈值：T=0.5(m1+m2)重复步骤2-4，直至T值收敛全局阈值估计基本算法GlobalThresholdingThresholdingMethod:BasicGlobalThresholdingThismethodtreatspixelvaluesasprobabilitydensityfunctions.Thegoalofthismethodistominimizetheprobabilityofmisclassifyingpixelsaseitherobjectorbackground.Therearetwokindsoferror:mislabelinganobjectpixelasbackground,andmislabelingabackgroundpixelasobject.OptimalGlobalThresholding计算图像归一化直方图，pi(i=0,1,2,…,L-1)计算累积直方图P1，令P2=1-P1计算累积灰度均值m1和m2计算全局灰度mG计算类间方差var(k)取使得var(k)最大的k值，即为Otsu阈值k*Otsu最佳全局阈值估计算法Otsu’sThresholdingThresholdingTheRoleofIlluminationThresholdingTheRoleofNoiseThresholdingTheRoleofNoise---DenosingThresholdingMethod:BasicGlobalThresholdingGlobalThresholding:WhendoesItNOTWork?AmeaningfulglobalthresholdmaynotexistImage-dependentglobalthresholdingBasicAdaptiveThresholdingBasicAdaptiveThresholdingThresholdingT=4.5ThresholdingT=5.5trueobjectboundaryBasicAdaptiveThresholdingThresholdingT=4.5ThresholdingT=5.5trueobjectboundarySplitSolutionSpatiallyadaptivethresholdingLocalizedprocessingBasicAdaptiveThresholdingThresholdingT=4ThresholdingT=7ThresholdingT=4ThresholdingT=7spatiallyadaptivethresholdselectionBasicAdaptiveThresholdingmergemergemergemergemergelocalsegmentationresultsBasicAdaptiveThresholdingAdaptiveThresholdingMultipleThresholdsColorimagesegmentationandclusteringColorimagesegmentationandclusteringRegion-BasedMethod:RegionGrowingFrom[Gonzalez&Woods]Key:similaritymeasureRegionGrowingStartfromaseed,andletitgrow(includesimilarneighborhood)Region-BasedMethod:SplitandMergeSplitandMergeIterativelysplit(non-similarregion)andmerge(similarregions)Example:quadtreeapproachFrom[Gonzalez&Woods]Region-BasedMethod:SplitandMergeoriginalimage4regions4regions(nothingtomerge)splitmergeExample:QuadtreeSplitandMergeProcedureIteration1SplitStep

spliteverynon-uniformregionto4Merge

Step

mergealluniformadjacentregionsRegion-BasedMethod:SplitandMergefromIteration113regions4regionssplitmergeExample:QuadtreeSplitandMergeProcedureIteration2SplitStep

spliteverynon-uniformregionto4Merge

Step

mergealluniformadjacentregionsRegion-BasedMethod:SplitandMergefromIteration210regionssplitmergeExample:QuadtreeSplitandMergeProcedureIteration3finalsegmentationresult2regionsSplitStep

spliteverynon-uniformregionto4Merge

Step

mergealluniformadjacentregionsRegion-BasedMethod:SplitandMergeHardProblem:TexturesSimilaritymeasuremakesthedifferenceFromProf.XinLiedgedetectionboundarydetectionclassificationandlabelingimagesegmentationBoundary-BasedMethodDetectionofDiscontinuitiesTherearethreekindsofdiscontinuitiesofintensity:points,linesandedges.Themostcommonwaytolookfordiscontinuitiesistoscanasmallmaskovertheimage.Themaskdetermineswhichkindofdiscontinuitytolookfor.

PointDetection点检测（拉普拉斯）模板LineDetectionOnlyslightlymorecommonthanpointdetectionistofindaonepixelwidelineinanimage.Fordigitalimagestheonlythreepointstraightlinesareonlyhorizontal,vertical,ordiagonal(+or–45

).LineDetectionEdgeDetectionEdgeDetectionEdgeDetectionEdgeDetection:GradientOperatorsFirst-orderderivatives:Thegradientofanimagef(x,y)atlocation(x,y)isdefinedasthevector:Themagnitudeofthisvector:Thedirectionofthisvector:EdgeDetection:GradientOperatorsEdgeDetection:GradientOperatorsEdgeDetection:GradientOperatorsRobertscross-gradientoperatorsPrewittoperatorsSobeloperatorsGradientOperators:ExampleGradientOperators:ExampleGradientOperators:ExampleEdgeDetection:GradientOperatorsSecond-orderderivatives:(TheLaplacian)TheLaplacianofan2Dfunctionf(x,y)isdefinedasTwoformsinpractice:EdgeDetection:Marr-HildrethEdgeDetectorConsiderthefunction:TheLaplacianofhisTheLaplacianofaGaussiansometimesiscalledtheMexicanhatfunction.Italsocanbecomputedby

smoothingtheimagewiththeGaussiansmoothingmask,followedbyapplicationoftheLaplacianmask.TheLaplacianofaGaussian(LoG)AGaussianfunctionEdgeDetection:Marr-HildrethEdgeDetectorEdgeDetection:Marr-HildrethEdgeDetectorZerocrossingofthesecondderivativeofafunctionindicatesthepresenceofamaximaEdgeDetection:Marr-HildrethEdgeDetectorStepsSmooththeimageusingGaussianfilterEnhancetheedgesusingLaplacianoperatorZerocrossingsdenotetheedgelocationUselinearinterpolationtodeterminethesub-pixellocationoftheedgeMarr-HildrethEdgeDetector:ExampleZeroCrossingsDetectionEdgeImageZeroCrossingsMarr-HildrethEdgeDetector:ExampleSobelgradientLaplacianmaskGaussiansmoothfunctionMarr-HildrethEdgeDetector:ExampleEdgeDetection:CannyEdgeDetectorOptimaledgedetectordependingonLowerrorrate–edgesshouldnotbemissedandtheremustnotbespuriousresponsesLocalization–distancebetweenpointsmarkedbythedetectorandtheactualcenteroftheedgeshouldbeminimumResponse–OnlyoneresponsetoasingleedgeOnedimensionalformulationAssumethat2DimageshaveconstantcrosssectioninsomedirectionEdgeDetection:CannyEdgeDetectorDependingontheaboveprinciples,severaloptimaledgedetectorsarecalculatedBestapproximationtotheabovedetectorsistheFirstDerivativeofGaussianItischosenbecauseoftheeaseofcomputationin2dimensionsImplementationofCannyEdgeDetectorStep1Noiseisfilteredout–usuallyaGaussianfilterisusedWidthischosencarefullyStep2EdgestrengthisfoundoutbytakingthegradientoftheimageARobertsmaskoraSobelmaskcanbeusedImplementationofCannyEdgeDetectorStep3FindtheedgedirectionStep4ResolveedgedirectionImplementationofCannyEdgeDetectorStep5Non-maximasuppression–tracealongtheedgedirectionandsuppressanypixelvaluenotconsideredtobeanedge.GivesathinlineforedgeStep6Usedouble/hysterisisthresholdingtoeliminatestreakingCannyEdgeDetectorWewishtomarkpointsalongthecurvewherethemagnitudeisbiggest.Wecandothisbylookingforamaximumalongaslicenormaltothecurve(non-maximumsuppression).Thesepointsshouldformacurve.Therearethentwoalgorithmicissues:atwhichpointisthemaximum,andwhereisthenextone?Non-MaximumSuppressionNon-MaximumSuppressionSuppressthepixelsin‘GradientMagnitudeImage’whicharenotlocalmaximumNon-MaximumSuppressionNon-MaximumSuppressionHysteresisThresholdingHysteresisThresholdingIfthegradientatapixelisabove‘High’,declareitan‘edgepixel’Ifthegradientatapixelisbelow‘Low’,declareita‘non-edge-pixel’Ifthegradientatapixelisbetween‘Low’and‘High’thendeclareitan‘edgepixel’ifandonlyifitisconnectedtoan‘edgepixel’directlyorviapixelsbetween‘Low’and‘High’HysteresisThresholdingCannyEdgeDetector:ExampleCannySobelEdgeDetection:CannyAlgorithmEdgeLinkingandBoundaryDetection:LocalProcessingTwopropertiesofedgepointsareusefulforedgelinking:thestrength(ormagnitude)ofthedetectededgepointstheirdirections(determinedfromgradientdirections)Thisisusuallydoneinlocalneighborhoods.Adjacentedgepointswithsimilar

magnitudeanddirectionarelinked.Forexample,anedgepixelwithcoordinates(x0,y0)inapredefinedneighborhoodof(x,y)issimilartothepixelat(x,y)ifEdgeLinkingandBoundaryDetection:LocalProcessingInthisexample,wecanfindthelicenseplatecandidateafteredgelinkingprocess.HoughTransformMethodtoisolatetheshapesfromanimagePerformedafteredgedetectionNotaffectedbynoiseorgapsintheedgesTechniqueThresholdingisusedtoisolatepixelswithstrongedgegradientParametricequationofstraightlineisusedtomaptheedgepointstotheHoughparameterspacePointsofintersectionintheHoughparameterspacegivestheequationoflineonactualimageEdgeLinkingandB