数字图像处理章分割

1第十章图像分割

ImageSegmentation张运楚信息与电气工程学院

2OutlineDetectionofgrayleveldiscontinuitiesEdgelinkingandboundarydetectionThresholdingRegion-BasedSegmentationSegmentationbyMorphologicalWatershedsTheUseofMotioninSegmentation3Revisit-GoalsofimageprocessingImageimprovement–lowlevelImageProcessingImprovementofpictorialinformationforhumaninterpretation(Improvingthevisualappearanceofimagestoahumanviewer)Imageanalysis–highlevelImageProcessingProcessingofscenedataforautonomousmachineperception(Preparingimagesformeasurementofthefeaturesandstructurespresent)ExtractinginformationfromanimageStep1:segmenttheimage

objectsorregions(Regionofinterest)Step2:describeandrepresentthesegmentedregionsinaformsuitableforcomputerprocessingStep3:imagerecognitionandinterpretation4Imageanalysis5Whatissegmentation?DefinitionSubdividesanimageintoitsconstituentregionsorobjects从图像中提取出所需的语义对象(semanticobject)将图像划分成若干有一定含义的区域Heavilyrelyononeoftwopropertiesofintensityvalues:Discontinuity----Partitionbasedonabruptchangesinintensity,e.g.edgesinanimagepoint/line/edge/cornerdetectionSimilarity----Partitionbasedonintensitysimilarity.thresholdingregiongrowing/splitting/merging67图像分割示例8Extractmotionobjectsfromasequenceofimages9图像分割难度分割依赖于低层视觉，同时又依赖于高层视觉。图象分割是计算视觉和图像理解中的最基本问题之一，也是该领域国际学术界公认的将会长期存在的最困难的问题之一。图象分割之所以困难的一个重要原因是其并不完全属于图像特征提取问题，它还涉及到各种图像特征的知觉组织(PerceptualGrouping)。从一般意义上来说，只有对图像内容的彻底理解，才能产生完美的分割。通过对环境进行适度控制和选择适当的传感器，可以降低图象分割的难度。101110.1基础知识LetRrepresenttheentireregion.WemayviewsegmentationasaprocessthatpartitionsRintonsubregions,R1,R2,…,Rn,suchthatHere,Q(Ri)isalogicalpredicatedefinedoverthepointsinregionsetRi.Condition(d)dealswiththepropertiesthatmustbesatisfiedbythepixelsinasegmentedregion.Segmentationmustbecomplete,thatis,Everypixelmustbeinaregion.Regionmustbedisjoint.12示例：基于不连续性和相似性的灰度图像分割44的子块基于区域特征-标准差1310.2DetectionofDiscontinuitiesWewanttoextract3basictypesofgray-leveldiscontinuityinadigitalimage:PointsLinesEdgesThemostcommonwaytolookfordiscontinuitiesistorunamaskthroughtheimage--spatialfiltering.Theresponseofthemaskatanypointintheimageisgivenby14突变检测（一阶微分）梯度定义对于图像函数f(x,y)，它在点(x,y)处的梯度是一个矢量，定义为：

梯度的两个重要性质是：

（1）梯度的方向在函数f(x,y)最大变化率的方向上。（2）梯度的模用由下式算出：15对数字图像来讲，f(x,y)的二阶偏微分可表示为：突变检测（二阶微分

拉普拉斯算子）16拉普拉斯算子实现模板

Whichgivesanisotropicresultforrotationsinincrementsof90°Whichgivesanisotropicresultforrotationsinincrementsof45°17181.PointDetection

Isolatedpoint(孤立点)–apointwhosegraylevelissignificantlydifferentfromitsbackgroundandwhichislocatedinahomogeneousornearlyhomogeneousarea.Anisolatedpointsdetectedatthelocationonwhichthemaskiscenteredif

|R(x,y)|≥TwhereTisanonnegativethresholdandRistheresponseofthemask.此处采用拉普拉斯模板。从而产生一个二值图像：19Exampleofpointdetection拉普拉斯模板20用拉普拉斯模板进行线检测2.Linedetection21Masksforlinesofdifferentdirections:Respondmorestronglytolinesofonepixelthickofthedesignateddirection.Ifinterestedinlinesofanydirections,runall4masksandselectthehighestresponse.Ifinterestedonlyinlinesofaspecificdirection(e.g.vertical),useonlythemaskassociatedwiththatdirection.Thresholdtheoutput.22Illustrationoflinedetection233.EdgeDetection物体的边缘是以图像的局部特征不连续的形式出现的，也就是指图像局部亮度变化最显著的部分，例如灰度值的突变、颜色的突变、纹理结构的突变等，同时物体的边缘也是不同区域的分界处。在Marr的视觉计算理论框架中，抽取二维图像上的边缘、角点、纹理等基本特征，是整个系统框架中的第一步。这些特征所组成的图称为基元图。Yuille等指出，在不同“尺度”意义下的边缘点，在一定条件下包含了原图像的全部信息。24边缘的形成与分类A类--空间曲面上的不连续点B类--由不同材料或相同材料不同颜色产生的C类--物体与背景的分界线，一般称为轮廓线D类--阴影引起的边缘右图画出了一幅图像中的边缘点，仅仅根据这些边缘点，就能识别出三维物体，可见边缘点确实包含了图像中的大量信息。图像中的边缘点

25在各边缘线的两边，图像的灰度值有明显的不同。26ModelofEdgeAsetofconnectedpixelsthatlieontheboundary

betweentworegions.Localconcept271stand2nd

DerivativeofgraylevelThemagnitudeofthefirstderivativecanbeusedtodetectthepresenceofanedgeatapointinanimage(i.e.,todetermineifapointisonaramp).Thesignofthesecondderivativecanbeusedtodeterminewhetheranedgepixelliesonthedarkorlightsideofanedge.Producing2valuesforeveryedgeinanimage(anundesirablefeature).Centerofathickedgeislocatedatthezerocrossing.28Example:Behaviorofthefirstandsecondderivatives

aroundanoisyedgeFairlylittlenoisecanhavesignificantimpactonthetwokeyderivatives.Andthesecondderivativeisevenmoresensitivetonoise.Imagesmoothingshouldbeaseriousconsiderationpriortotheuseofderivatives.Effectofnoise29边缘检测的基本步骤对图像进行平滑处理-降噪边缘点的检测，以提取图像中所有的边缘候选点边缘定位，从候选边缘点中确认真正的边缘点30FirstDerivative:GradientOperatorsThegradientofanimagef(x,y)atlocation(x,y)isdefinedasSomepropertiesaboutgradientvectorGradientvectordirection:Itpointsinthedirectionofmaximumrateofchangeofimageat(x,y).MagnitudeM(x,y):givesthemaximumrateofincreaseofperunitdistanceinthedirectionof

f.Thedirectionangleofthegradientvector

f,

(x,y).31Anedgeelementisassociatedwith2components:magnitudeofthegradientvector

f.edgedirection,thedirectionofanedgeat(x,y)isperpendiculartothedirectionofthegradientvectorat(x,y).32

水平垂直差分法RobertGradientSobel算子：Prewitt算子：SomebasicgradientoperatorsBetternoise-suppression(x,y)33Somebasicgradientoperators(cont’d)34Example:

IllustrationoftheSobelgradientanditscomponent35IllustrationoftheSobelgradient(cont’d)–smoothedtheimagepriortoedgedetection36IllustrationoftheSobelgradient(cont’d)-Diagonaledgedetection37IllustrationoftheSobelgradient(cont’d)-Thresholding38SecondDerivative:LaplacianOperatorTheLaplacianoperator(

2)isaverypopularoperatorapproximatingthesecondderivative.Laplacianoperatoratlocation(x,y)isdefinedasLaplacianoperatorisnon-directional(isotropic).39IssueswithLaplacianProblems:UnacceptablysensitivetonoiseMagnitudeofLaplacianresultsindoubleedgesDoesnotprovidegradient,socan’tdetectedgedirectionFixes:SmoothingUsingzero-crossingpropertyforedgelocationNotforgradientdirection,butforestablishingwhetherapixelisonthedarkorlightsideofandedge40Marr-HildrethEdgeDetection

Smoothing-LaplacianofGaussian(LoG)ConsiderthentheLaplacianofanimagef(x,y)smoothedbyaGaussian.ThisoperatorisabbreviatedasLoG,fromLaplacianofGaussian:Theorderofdifferentiationandconvolutioncanbeinterchangedduetolinearityoftheoperations:41LaplacianofGaussian(cont’d)42LaplacianofGaussian(cont’d)Becauseofitsshape,theLoGoperatoriscommonlycalledaMexicanhat.43Example:EdgefindingbyzerocrossingSmooththeimageusingGaussianlow-passfiltertoreducenoise.Thencalculatethe2ndderivativeusingLaplacianoperator.Finally,findthezero-crossing.Advantages:noisereductioncapability;edgesarethinner.Drawbacks:edgesformnumerousclosedloops(spaghettieffect);computationcomplex.44CannyEdgeDetector(坎尼边缘检测器)Canny在1986年写的一篇论文中给出了3个准则：（1）信噪比准则（2）定位精度准则（3）单边缘响应准则具体步骤：

首先用2D高斯滤波模板进行卷积以平滑图像；

利用微分算子，计算梯度的幅值和方向；Canny,J.AComputationalApproachtoEdgeDetection.IEEETrans.onPatternAnalysisandMachineIntelligence,1986,8(6):679-698.45

对梯度幅值进行非极大值抑制。即遍历梯度幅值图像，若某个像素的梯度幅值与其梯度方向上前后两个像素的梯度幅值相比不是最大，那么这个像素值置为0，即不是边缘；

使用双阈值算法检测和连接边缘。即使用累计直方图计算两个阈值，凡是梯度的幅值大于高阈值的一定是边缘；凡是梯度的幅值小于低阈值的一定不是边缘。如果检测结果大于低阈值但又小于高阈值，那就要看这个像素的邻接像素中有没有超过高阈值的边缘像素，如果有，则该像素就是边缘，否则就不是边缘。46Anedgeelementisassociatedwith2components:magnitudeofthegradientvector,

f.edgedirection,thedirectionofanedgeat(x,y)isperpendiculartothedirectionofthegradientvectorat(x,y).47Example:Cannyedgedetector48EdgelinkingandboundarydetectionDetectionofdiscontinuityusing1stderivativeProvidinggradientandmagnitudeZerocrossing(2ndderivativeusingLaplacian)ForedgelocationNogradientinformationSensitivetonoiseSmoothingusingGaussianfilter(LoG)Howtodealwithgapsinedges?Howtodealwithnoiseinedges?Linkingpointsbydeterminingwhethertheylieonacurveofaspecificshape.LocalProcessingGlobalProcessingviatheHoughTransform491.LocalProcessingAnalyzethecharacteristicsoftheedgepixelsinasmallneighborhoodItsmagnitudeItsdirectionAllpointsthataresimilaraccordingtoasetofpredefinedcriteriaarelinked,forminganedgeofpixelsthatsharethosecriteria.Asetofsimilaritycriteria,forexample:Anedgepixelat(s,t)inapredefinedneighborhoodof(x,y),issimilarinmagnitudeofgradienttothepixelat(x,y),ifandhasananglesimilartothepixelat(x,y),if,E-nonnegativethreshold,A-nonnegativeanglethreshold50边缘连接的简化步骤计算输入图像f(x,y)的梯度幅度阵列M(x,y)和梯度角度阵列

(x,y)。按下式形成一幅二值图像g：其中TM是梯度幅度阈值，A是选定的角度方向，TA是与A相关的可接受的梯度角度方向变化范围。扫描g的各行，并在每一行中填充不超过指定长度K的缝隙。如检测任何其他方向

的缝隙，以该角度旋转图像g，并应用步骤3中的水平扫描过程，然后再恢复g。51Example:

Edge-pointlinkingbasedonlocalprocessingTM=30%最大梯度值A=90

TA=45

52Matlabfunctionfilter2Imfilterfpecialedge53GlobalProcessingviatheHoughTransform

霍夫变换Resultsofedge-detectionmethodsmaycontainsparsepoints,insteadofstraightlinesorcurves.Therefore,needtofitalinetotheedgepoints.Efficientsolution:HoughTransformImagespace

parameterspaceOriginallyforfindinglinesEasilyvariedtofindothershapesReference:DudaRO,HartPE.UseoftheHoughTransformationtoDetectLinesandCurvesinPictures[J].CommunicationsoftheACM,1972,15(1):11–15.张运楚.基于存在概率图的圆检测方法.计算机工程与应用,2006,42(29),49-51.54HoughTransformConsiderapoint(xi,yi)andthegeneralequationofastraightlineinslope-interceptform:

yi=axi

+bQ:Howmanylinesmaypassthrough(xi,yi)?Re-writingtheequationin“ab-plane”—parameterspace:b=-xia+yiQ:Howmanylinesdowegetforafixed(xi,yi)in“ab-plane”?Nowgivenanotherpoint(xj,yj),Howtofindtheparameter(a’,b’)whichdefinesthelinethatcontainsbothpoints?55HoughTransform(cont’d)Allpointsonthelinepassingthrough(xi,yi)and(xj,yj),havelinesinparameterspacethatintersectat(a',b').56HoughTransform(con’t)PollingalledgepointsforlinesProblem:theslopeapproachesinfinityasthelineapproachesthehorizontal.57HoughTransform(cont’d)Needanotherparameterizationscheme.Nowconsider:

istheshortestdistancefromthelinetotheorigin,and

istheangle.58HoughTransform(cont’d)Choosingadiscretesetofvaluesof

and

.Constructanaccumulatorarray,initializedwith0foreachentry.Picturethisprocessasavotingprocess.59Example:detectlineviaHoughTransform60DetectingLinesUsingtheHoughTransform(Matlab)houghhoughpeakshoughlines61Example:detectcircleviaHoughTransform6210.3Thresholding阈值分割：利用图像中要提取的目标物与其背景在灰度特性上的差异，把图像视为具有不同灰度级的两类区域(目标和背景)的组合，选取一个合适的阈值，以确定图像中每个像素点应该属于目标还是背景区域，从而产生相应的二值图像，称单阈值分割。如果图像中有多个灰度值不同的区域，那么可以选择一系列的阈值以将每个像素分到合适的类别中去，这种用多个阈值分割的方法称为多阈值分割。63ExampleOriginalHistogramResultofsegmentationSinglethresholdDualthresholds64GeneralFormulationofThresholdingAthresholdedimageg(x,y)isdefinedasWhenTdependsonlyonf(x,y),thethresholdiscalledglobal.IfTdependsonbothf(x,y)andp(x,y),thethresholdislocal.IfTdependsonthespatialcoordinates(x,y),thethresholdiscalleddynamicoradaptive.SomelocalpropertyGrayscalevalue65双阈值分割：图像中含有三个支配模式的直方图，可以设置两个阈值实现多阈值分割：66Noiseeffect67TheRoleofIlluminationNon-uniformillumination68Thresholdingmethod:categoriesbySankurThresholdNumberBi-levelMulti-levelSpatialvarianceGlobalthreshold:thresholdstheentireimagewithasinglethresholdvalue.Localthreshold:partitionsagivenimageintosubimagesanddeterminesathresholdforeachofthesesubimages.PointdependentorregiondependentFixedoradaptivethresholdM.SezginandB.Sankur,ImageThresholdingTechniques:ASurveyOverCategories69Thresholdingmethod(cont’d)AccordingtheinformationexploitedHistogramshapebased:peaks,valleysandcurvatures.Clusteringbased:pixelsaremodeledasamixtureoftwoGaussians.EntropybasedObjectattributebasedThespatialmethodsusehigh-orderprobabilitydistributionorcorrelationbetweenpixelsLocalmethods70ThresholdingMethoddiscussedBasicGlobalThresholdingBasicAdaptiveThresholdingOtsu’sMethodUsedbythefunctiongraythreshinMatlab71BasicGlobalThresholdingSelectaninitialestimateforTSegmenttheimageusingTtogenerate2regions,G1&G2.G1consistingofallpixelswithgraylevelvalues>TG2consistingofallpixelswithgraylevelvalues

TComputetheaveragegraylevelvaluesm1andm2forthepixelsinregionsG1andG2,respectively.Computeanewthresholdvalue:T=(m

1+m

2)/2Repeatthesteps2through4untilthedifferenceinTinsuccessiveiterationsissmallerthanapredefinedparameterT0(i.e.Tconverges).72HowtoselecttheinitialTIfforegroundandbackgroundoccupycomparableareas,averagegraylevelmightbegood.Iftheareasnotcomparable,midwaybetweenmaxandmingraylevelmightbebetter.73ExampleInitialTistheaveragegraylevel,ThefinalTis125.4with3iterationsvalley74Otsu’sMethod

Otsu法（大津法）由大津于1979年提出的最优阈值方法是一种在判决分析或最小二乘法原理的基础上推导出来的最大类间方差法。令{0,1,2,…,L-1}表示一幅大小为M

N像素的L个不同的灰度级，ni

表示图像中灰度级为i的像素个数,M

N=n0+n2+…+nL-1表示图像的总像素数。图像的灰度直方图被归一化后视为灰度级的概率分布：75Otsu’sMethod(cont’d)选择T(k)=k为分割阈值，它把把图像中的所有像素按灰度级分成两类C1和C2，即：

那么C1和C2发生的概率可由下式给出：76Otsu’sMethod(cont’d)两类像素的灰度均值和方差分别为：式中mG为图像像素灰度总体平均值77Otsu’sMethod(cont’d)两类像素的灰度方差分别为：为了评估阈值k的优劣，Otsu使用类间方差和总体方差定义了两类像素的可分性测度：78Otsu’sMethod(cont’d)

两类像素的类间方差和总体方差分别为：

由于总体方差与阈值k

无关，因此，常通过最大化来获取最优阈值kopt，即：79Otsu’sMethod(cont’d)80ExampleofOtsu’sMethod81用图像平滑改善全局阈值处理

ExampleofOtsu’sMethod(Noisyimage)82ExampleofOtsu’sMethod(failed)酵母菌83利用边缘改进全局阈值处理利用边缘性质，将原来的直方图变换成具有更深波谷的直方图，或者使波谷变换成波峰，使得谷点或峰点更易检测到。由微分算子的性质可以推知，目标与背景内部像素的梯度小，而目标与背景之间的边界像素的梯度大。因此，可以根据像素的梯度值或作出一个加权直方图。84用梯度信息改进图像分割的步骤：计算图像f(x,y)的边缘图像g(x,y)

，梯度幅度或拉普拉斯的绝对值均可。选择阈值T。对g(x,y)

进行阈值处理，产生一幅二值图像gT(x,y)

。仅用f(x,y)中对应于gT(x,y)

中像素值为1的位置像素计算直方图。用上述直方图计算阈值（如Otsu方法），对图像f(x,y)

进行分割。85Example1:Gradientmagnitudebased86Example2:AbsoluteLaplacianbased87Matlabimplementationgraythresh

im2bw88BasicAdaptiveThresholdingGlobalthresholdingoftenfailsinthecaseofunevenillumination.globalthresholding89AnapproachforhandlingsuchasituationistoDividetheimageintosubimagesDetermineadifferentthresholdTtosegmenteachsubimage.Thekeyissues:Howtosubdividetheimage?Howtoestimatethethresholdforeachsubimage?90ExampleofBasicAdaptiveThresholdingAsimplepartition,obtainedbysubdividingtheimageintofourequalparts,andthensubdividingeachpartbyfouragain.subimages91ExampleofBasicAdaptiveThresholding

(cont’d)HowtodealwiththeSubimages?Observation:Type1:Forallsubimages,ifthegraylevelvarianceis<75donotcontainobjectboundaryType2:Forallsubimages,ifthegraylevelvarianceis>100containobjectboundaryAllsubimagesoftype1aremergedandthresholdedusingasinglethresholdvalueEachsubimageoftype2isthresholdedindependently.Allthresholdingisdoneusingbasicglobalmethod.92(cont’d)ResultofBasicAdaptiveThresholdingFailedsubimage93(cont’d)Furthersubdividing9410.4Region-BasedSegmentationFindregionsdirectlybymeansofregionsimilarity&connectivity.TherearefewsuchalgorithmsRegiongrowingRegionsplittingandmerging95RegiongrowingGroupspixelsorsubregionsintolargerregionsbasedonpredefinedcriteria(graytoneortexture).Basicmethod:

Startwithasetof“seed”pointsandfromthese,growregionsbyappendingtoeachseedthoseneighboringpixelsthathavepropertiessimilartotheseed,suchasspecificrangesofgraylevelorcolor.Problemsinregiongrowing:SelectionoftheseedsCriteriaofsimilarityGraylevel’ssimilarity/connectivity/texture/momentsFormulationofastoppingrule

Growingaregionshouldstopwhennomorepixelssatisfythecriteriaforinclusioninthatregion96Example:ApplicationofRegiongrowingseedregions97Example:ApplicationofRegiongrowing(cont’d)Step1:Determinetheinitialseedpoints.Allpixelshavinggray-levelvaluesof255.Step2:Choosecriteriaforregiongrowing.Theabsolutegray-leveldifferencebetweenanypixelandtheseedhadtobelessthan65.Tobeincludedinoneoftheregions,thepixelhadtobe8-connectedtoatleastonepixelinthatregion.Ifapixelwasfoundtobeconnectedtomorethanoneregion,theregionsweremerged.Step3:Formulationofastoppingrule.Inthiscase,itwasnotnecessarytospecifyanystoppingrule.Becausethecriteriaforregiongrowingweresufficient.98RegionsplittingandmergingSplitting:Startingwiththeentireregion.RrepresenttheentireregionandselectapredicateP.IfP(R)=FALSE,dividetheimageintoquadrantsIfPisstillFALSEforanyquadrant,subdividethatquadrantintosubquadrantsandsoon.Theresultisaquadtree.99Merging:Ifonlysplitting,itislikelythatadjacentregionshaveidenticalproperties.Somergingisallowed,aswellassplitting.TwoadjacentregionsRiandRjaremergedonlyifP(Ri∪Rj)=TRUE.AlgorithmSplittinginto4disjointquadrantsforanyregionRiforwhich

P(Ri)=FALSEMerginganyadjacentregionsRjandRkforwhichP(Rj∪Rk)=TRUE.Stopwhennofurthermergingandsplittingispossible.(a)(b)(c)(d)Regionsplittingandmerging(cont’d)100Example10110.5SegmentationbyMorphologicalWatershedsVisualizetheimagein3Dtopography(地形)spatialcoordinatesandgraylevels.Insuchatopographicinterpretation,thereare3typesofpoints:PointsbelongingtoaregionalminimumPointsatwhichadropofwaterwouldfalltoasingleminimum.(Thecatchmentbasin(汇水盆)orwatershed(分水岭)ofthatminimum.)Pointsatwhichadropofwaterwouldbeequallylikelytofalltomorethanoneminimum.(Thedividelinesorwatershedlines.)WatershedlinesCatchmentbasinsOriginalimageTopographicview102Visualizetheimagein3Dtopography(地形)103(Cont’d)Theobjectiveistofindwatershedlines.Theideaissimple:Supposethataholeispunchedineachregionalminimumandthattheentiretopographyisfloodedfrombelowbylettingwaterrisethroughtheholesatauniformrate.Whenrisingwaterindistinctcatchmentbasinsisaboutthemerge,adamisbuilttopreventmerging.Thesedamboundariescorrespondtothewatershedlines.104IllustrationofWatershedsSegmentationLongerdamconstructedWaterstartmerging,soshorterdamconstructedFinalresult105ApplicationofWatershedSegmentationWatershedalgorithmisoftenappliedtothegradientofanimage,ratherthantotheimageitself.RegionalminimaofcatchmentbasinscorrelatenicelywiththesmallvalueofthegradientcorrespondingtheobjectsofinterestBoundariesarehighlightedasthewatershedlines.Theimportantpropertyisthatthewatershedlinesformaconnectedpath,thusgivingcontinuousboundariesbetweenregions.Oneoftheprincipalapplication:extractionofnearlyuniform(bloblike)objectsfromthebackground.106Example_1ofWatershedSegmentationthegradientofanimage107Example_2ofWatershedSegmentationDuetonoiseandotherlocalirregularitiesofthegradient,oversegmentationmightoccur.108Example_2ofWatershedSegmentation(cont’d)Asolutionistolimitthenumberofregionalminima.Usemarkerstospecifytheonlyallowedregionalminima.Aregionthatissurroundedbypointsofhigher“altitude”;Suchthatthepointsintheregionformaconnectedcomponent;Andinwhichallthepointsintheconnectedcomponenthavethesamegray-levelvalue.internalmarkersexternalmarkers10910.6TheUseofMotioninSegmentationMotionisapowerfulcueusedbyhumansandmanyanimalstoextractobjectsofinterestfromabackgroundofirrelevantdetail.Motionarisesfromarelativedisplacementbetweenthesensingsystemandthescenebeingviewed.RoboticapplicationsAutonomousnavigation