四队和一队基于分水岭算法图像分割研究

中图像分割是指把图像分成各具特性的区域并提取出感目标的技术和过后结合V-S分水岭算法的排序和浸没过程进一步分析处理图像。针对传统的分水岭算法在彩像分割时常常会产生过分割现象，利用基于彩像的区域合成解决分水岭的过分割问题，在去除图像噪声的同时最后，利用visualC++语言实现了该算法，并进行了试验，实验结果表明程序能较好的实现对彩像的分割效果。：图像分割，梯度，V-S分水岭算法，区域合Imagesegmentationreferstotheimageintoregionswithspecificcharacteristics,andextracttheobjectofinterestandprocesstechnology,itisacrucialstepfurtherbyimageprocessingtoimageysisisabasiccomputervisiontechniques.Onthebasisofimagesegmentation,thetargetcanbemoreconvenientforthefeatureextractionandmeasurementparameters,suchhigherlevelimageysisandunderstandingpossible.Therefore,thestudyofimagesegmentationhasimportantsignificanceinthefieldofimageprocessing.Inthispaper,amethodforimagesegmentationusingwatershedalgorithmismainlybecauseoftheprincipleofwatershedalgorithmintuitive,highefficiencyofthealgorithmtodetectcontinuousedgelineclosed,canrespondtotheadvantagesofweakedges,etc.,inthefieldofimagesegmentationplaysaveryimportantrole.Studiesincludingthefollowing:(1)Collectedtherelevantinformationaboutthethreetypesofimagesegmentation:segmentationalgorithmbasedontheedgeofthesegmentationalgorithmbasedonregion-basedthresholdsegmentationalgorithm.Andintroducedthecalculationbasedondifferentimagegradientoperator.(2)Detailsofthewatershedalgorithmbasedonmorphology.Gradient-basedimagesegmentation,andthencombinetheprocessofsortingandimmersionVSwatershedalgorithmfurtherysisandprocessingimages.(3)Forthetraditionalwatershedinthecolorimagesegmentationalgorithmoftenproducesover-segmentationphenomenon,basedontheuseofsyntheticsolvewatershedareaoverthecolorimagesegmentationproblem,removingimagenoisewhilekeetheimageedgeinformation,therebyimprovingtheover-segmentation.Finally,theuseofvisualC++languageimplementationofthealgorithm,andtested,experimentalresultsshowthattheprogramcanachievebetterresultsforcolorimagesegmentation.中 第一章引言1-研究的背景及意义1-图像分割技术发展现状.......................................................................................-1-本文研究内容2-第二章图像梯度计算3-图像分割定义3-图像分割的方法4-图像梯度算子4-4-一阶导数算子6-二阶导数算子7-8-分水岭算法的原理8-分水岭算法的数学描述........................................................................................-9-分水岭算法的优缺点11-V-S分水岭算法12-V-S算法的排序过程12-V-S算法的浸没过程13-第四章基于彩像的区域合并..................................................................................-14颜色空间模型14-彩像颜色空间..............................................................................................-15相似区域合并15-第五章基于visualC++16-16-16-第六章总结21-参考文献22-研究的背景及图像、图形（动画、、文本、数据等，这也是人类最有效和最重要的信息哪种目的,图像处理中最关键的一步就是对包信息的图像进行分割。图像分割技术发展现阈值分割法是一种并行分割法[4]。早期的阈值分割法如Otsu等类别方差法[5]T.Pun引入的最大熵法[6]等均未考虑像素点的空间信息，对含噪声和不均匀的图像较敏感，容易在分割区域中产生空洞。Nakagawa等变化阈噪声干扰。其他的边缘检测法有Vishvjit等基于曲面拟合的方法[10]，Kass等变形模型算法[11]等。变形模型算法[10]的分割结果均为闭合连续的曲线WanShu-Yen等对称区域生长法[12],克服了区域分割法过分依赖区域的最低梯度值像素点，因此无须人工或计算选取点。维图像，从灰度图像到彩像[14]、多光谱图像，从静态分析到动态[15]等除了传统的三类方法外图像分割的方法还包括基于理论的分割方法、基于形态学的分水岭算法[16]是最近发展起来的一种图像分割方法,它基于测地学上的测线重构，由Beucher等人最早提出。该方法的主要目标是找出分水岭。具有代表性的一种分水岭算法是LucVincent和PierreSoille于彩像的区域合并技术来解决该问题，并取得良好的效果。本文研究内1计算，包括一阶导数算子如Roberts算子、Sobel算子、Prewitt算子、Canny算子等，二阶导数算子如Laplacian算子、LoG（Laplacian-Gauss）算子。V‐S3．基于彩像的区域合由于分水岭算出现严重的过分割分水岭变换的结果容易产生过量非必彩像颜色空间，包括RGB模型、CMY和CMYK模型、YIQYUV4．基于vc++在Visual图像分割定出感的目标或前景的过程称为图像分割技术[17]。RRRN个满足以下五个条件的非空子集[19]（子区域）P(Ri)FALSER1R2RN：NRNRi；所有的iji

j，有RiRji=1，2，…，NP(RiTRUE ijP(RR)FALSE i=1，2，…，NRiP(Ri是对所有在集合Ri中元素的逻辑谓词，φ上述这些条件[19]不仅定义了分割，也对如何进行分割有指导作用。对图图像分割的方分割问题的在于图像数据的模糊和噪声的干扰。到目前为止，还没有一概念,它在本质上是一种区域增长的算法,不过与传统区域增长算法不同的是,图像梯度算图像边缘号为例如图2-1a是一种阶跃信号当然认为点A处是边缘点在实际情况中，2-1b是一种逐渐增大的信号，对图中所示A、B、CA2-1a2-1b的特例。因为当B→A，C→A时，图2-1b将趋2-1a。在图2-1c和图2-1d中，如果“台阶”比较窄，可以认为B为边缘点，也可以认为有两个边缘点A和C。2-1图像的梯度及其计算f(x,y在点(x,ygradf(x,y)fi

jf,f xy fxyf gradf(x,y)2-2f(x0f(x0x)f(x0xf'(x)x1，所以f'(x0)f(x01)f(x0)f(x0)f(x0f(x0h)f(x0)（2-f''(xf''(x)

f(x0x)f(x0x)2f(x0

(x)f(x)f(xx)（2-f(x0xf(x0x2f(x0)(x0x(x0（2-7）(x0x)(x0)'(x0x)x(06(x0x)(x0)f'(x0x)f'(x0x由二阶导函数f''(x)的连续性，再次应用日中值定理，得f'(x0x)f'(x0xx)f''(x0x'x)x(0,'合并上述结果，并代入（2-5）f''(xf(x0x)f(x0x)2f(x0)f

x'x)f''(x)(x 这就证明了（2-5x1时，即得在计算机编程时，二阶f''(x0)f(x01)f(x01)2f(x0)（2-8-2计算图像的梯度，Roberts算子Roberts算子的公式和模板分别为G(x,y)g(i,j)g(i1,j1)g(i1,j)g(i,j1)（2-2-4Roberts公式中G(x,yg(x,y)通过RobertsRoberts算子具有的优点[9]是定位边缘能力比较高，精确读高，偏移小，垂糙，不够平滑细腻，对噪声也较敏感，容易受到噪声的干扰。Roberts算子适用Sobel算子点就是边缘点。Sobel3×3的模板为[18]：2-5SobelSobel算子具有的优点[9]是能通过梯度方向信息获取精确的边缘方向信息。RobertsSobel算子虽有一定的去噪功能，Prewitt算子原理：与Sobel算子一样，但Prewitt算子没有用值，将g像素点周围Canny算子

2-6Prewitt图像中的一阶导数最大值，定位到的点即为边缘点。Canny3个准边缘定位精确度准则，边缘定位精确度L定义如下WW h2公式(2-9)中，G'(x是边缘定位函数G(x的导函数，h'(xW的滤波器的脉冲响应函数h(x)的导函数[18]。信噪比准则，信噪比SNR定义为WWh2公式(2-10)中，h(x)是宽度为W

滤波器的脉冲响应函数，G(x)边缘定位函数，σ为滤波器的均方差值[18]单边缘准则，确保检测到的边缘是单像素点D(f)

1h'2h''(x)dx公式(2-11)h''(xh(x)的二阶导函数[18]Canny检测算子，从而获得效果最佳的边缘结果。Canny算子的边缘检测效果较前面的几个一阶导数算子都要好，Canny算子具备抑制噪声的能力和精确的边缘定位能力，缺点是去[9]。已知一阶导数的最大值处对应二阶导数的过零点，因此可通过查找二阶导Laplacian算子原理：像素点的二阶导数的零交叉点即为边缘点。Laplacian算子求取二阶 2 2gx2

2 Laplacian算子的优点[16]是边缘定位精度很高。缺点是对噪声过于敏感，无法获得边缘的方向信息。为了缓解对噪声的敏感，Laplacian算子边缘检测前一LoG（Laplacian-Gauss）算子检测算子之前，一般都要经滤波器滤除掉图像中的噪声。LoG[9算子是将Laplacian算子和滤波器相结合得到的一种边缘检测算子。首先用滤波g(x,y用LoG算子检测边缘的公式如下x2y22

x2y2G(x,y) )e2

*g(x,

公式(2-14)中，*表示求卷积，σ为滤波器的均方差值[18]分水岭算法的原上述方法是分水岭算法基于模拟浸没的过程,分水岭的另一种描述方法是基于模拟降水的过程[2]。同样将图像视为高低起伏的地形图，梯度值仍然代表每分水岭算法的数学IDZ2I设定为0NI0N255,则I的定义如下

Z2IpI(

1[22]IpqL是由(l+1)个点组成，这些点为p0

pl1plp0

,plq于任意点i满足：i1,l,(pi1,pi)G（G表示数字网格表示 定义2[22]：图像I中高度为h的极小区M是由一个或多个梯度值为的像素点构成的连通区域，极小区M中的任一点若要与梯度值小于h点之间形成连通路径L，L路径中必然有一点梯度值大于hpLqL,pI(qIpLp0 pl1plp0pplq（3-（climb3-2中若要从极小区M中任一像素点连通道h-1的像素点时必须经过图中向上的红色箭头所指路径，而此路径中必然存在梯度值>h的像素点。（climb）对于图I，梯度值范围D(i,jC(i,jE(i,j)DI的下限值即梯度最小值hmin，上限值即梯度最大值hmax，当梯度值为h时，用Th(I表示梯度值h的所有像Th(I){pDI,I(p)h}（3-假设极小区M所在的积水盆地为C(M)，对于h层以下的所有像素点Th(I所在的积水盆地Ch(M必然满足下式Ch(M){pC(M),I(p)h}C(M)Th(I)（3-3[22]：测地距离（GeodesicInfluenceZoneab都属于a,bA内并且是所有可取路径中的最短路径，如图3-3所示，测地距离用公式定义如下：)3-3Bk集合集合B由B1,B2 k个互不相连的区域组成定义连通区域Bk(BiBiBj的距离，其中ijA，如图3-4所示，测地影响区域的公式定义如下[22]:izA(Bi{pA,j1k且jidApBidApBj)}（3-A区域内所有的点计算测地距离并确定测地影响区域后，只剩下不属于SKIZA(B)AIZA(B),其中

(B) iz(B

3-4分水岭算法的优缺（b严重的过分割，分水岭变换的结果容易产生过量非必要的小区域（a）原 图3-5各种图像分割算法对比图纳总结，实际应用中通常采用的消除过分割的方法分为以下三种由Vincent和Soille分水岭算法使分水岭图像分割方法得到推（以V-S算法。相对于传统的分水岭算法，V-S排序[22]：顺序扫描梯度图像中的像素点，按梯度值升序的顺序排列过队列queue结构的先进先出方式处理每个像素点。g[h]来表示，其中hg[h]表示梯度级h所包含的像素点个数。级hg[h]即自增1。梯度级累加概率是指：当梯度级为h时，所有小于或等于梯度级h所包中，像素点的顺序为：上、左、右、下。排序结果如图3-6所示。由以上步骤可知，排序过程总共对图像扫描了23-6V-S浸没过程的算法步骤描述如下处理每一梯度级：排序后梯度图中的最低梯度级记为hmin，最高梯度级记为hmax。按梯度级从低到高的顺序扫描hmin到hmax的每一个梯度级，假设当前h（h为h层。然后按照下面（2）至（4）h层由图3-6可知，排序后像素点包含了在图中所处的坐标信息和自身的梯度值信息，则查找h层的像素点时，每个像素点的坐标信息均可获得。假设当前像素点为点Pcur，扫描点Pcur邻域点，若邻域中有点已经被标方法PcurFIFO队列中，如果邻域点被标记，那么当前像素点就顺序处理第（2）步中压入FIFO队列中的点。FIFO队列中的点按先进先出的顺序处理，每标记一个点后将此点移出FIFO队列，然后处理队列中hFIFO队列，再执行当前步骤。循环查找邻域点的邻域内是否同属于h层，若有，继续执行当Pcur的连通区域内查找不到h层像素点。Pcurh层的像素点FIFO队列，直到确定点Pcur的连通区域周围均无被标记积水盆地，则标记Pcur所在连同区域为新的极小区（h的像素点。标记顺序为FIFO中的顺序。Pcurh素点都要进出FIFO队列，这是非常耗时的操作。下一章介绍的快速分水岭算法，剔除了耗时的FIFO队列，节省了进出队列的时间。颜色空间模RGB模型RGBRGB三色光互相叠加来实现混色的F（物体颜色）=R（红色的百分比）+G（绿色的百分比）+B（蓝色的百比由于图像和显示设备使用的是RGB彩色模型，所以RGB彩色模型彩像处理中最基础的彩色模型CMYCMYK模型（Cyan（MagentaCMY模型中，线完全被反射时显示为白色（加色法从理论上来说，只需要CMY三种油墨等比例混合在一起就会得到黑色，但会加入黑色油墨，这就是CMYK色彩混合模式的由来。所以CMYK又称为印刷YIQYUV模型YIQ与YUVYIQ，是NTSC(NationalevisionStandardsCommittee)电视系统标准，适用于彩色电视广播中，Y是提供黑白电视及彩色电视的亮度信号（Lumminance）,即亮度（Brightness）,I代表In-phase,色彩从橙色到青色，QQuadrature-phase,色彩从紫色到黄绿色，是RGB表示的一个简单线性变化。YUVYIQ彩色模型类似，不同在于空间多了一个33的旋转，是为了能与黑白电视兼容，YUV中亮度信号（Y）和色度信号（U、V）是相互独立的，即Y信号分量构成的黑白灰度图与U、V的另外两个单是相互独彩像颜色空RGB颜色空间[28]能有效显示图像，目前的显示器、电视机、数码相机、摄像机等大都采用RGB颜色标准。但图像处理领域一般不直接用RGB颜色空间，是由于RGB空间的以下三个特性[29]：RGB空间基于底层硬件，与人眼视觉感触有一定差距，图像处理是为RGBRGBLUV颜色空间[30]各分量相关性小，LUV色度图中点距正比于人眼所感知LUV颜色空间更适合于图像处理。LUV颜色空间[30]中，L代表亮度，U和V代表色度坐标，U、V的取值范围为-100到+100，L的取值范围为0到100。RGB到XYZ颜色空间的转换[30]：一幅彩像中，将像素点的（R，G，B）转化为（X，Y，ZXvar_R*0.4124var_G*0.3576var_BYvar_R*0.2126var_G*0.7152var_B Zvar_R*0.0193var_G*0.1192 公式(4-1)中，var_RR((R/2550.055)/1.055)24*100,R12.92*R/255*100,Rvar_Gvar_BXYZLUV颜色空间的转换

L (29/3)3*(Y/Y),(Y/Y)(6/ nU13*L*(u'unnV13*L*(v'vn

公式(4-4)中uv'分别为u'(4*X)/(X15*Y3*v'(9*Y)/(X15*Y3*

Yuv Y100u'0.2009v'0.4610 相似区域合D(i,j)C(i,j)E(i,j)（4-公式(4-5)C(i,j为两个区域的色度相似度，定义如下(LL)2(LL)2(UU)2(VV 为区域j中所有像素点的的 U,V三分量的均值[30]公式(4-6)E(ij为两个区域间的分水岭两侧像素点的梯度均值的相似度，定E(i,j)i

公式(4-7)中，i，j表示两相邻区域间分水岭两侧像素点的梯度均值[32]。若分水岭为越明显的边缘，i，jE(i,j就越大。开发环境和系统操作系统：Windows7（CPU：In内存：4GBVisualC程序代VoidCWaterShedDoc::GetGradient(BYTE*image,INTwidth,INTheight,{INT*deltaxarr;INT*INTgrawidth=width;INTgraheight=INTdeltacount=grawidth*graheight;deltaxarr=newINT[deltacount];deltayarr=newINT[deltacount];//for(INTy=1;y<graheight-1;{for(INTx=1;x<grawidth-1;{INTinarrposy)*widthx))*31;//在输入块中的位置；INTdeltaarrpos=y*grawidth+x;//在梯度数组中的位置；deltaxarr[deltaarrposINTimage[((y-1)*width+(x+1))*3+1]//右上,+1+image[((y)*widthx+1))*31]//+image[((y+1)*widthx+1))*31]//image[((y-1)*widthx-1))*31]左image[((y)*widthx-1))*31image[((y+1)*widthx-1))*31]3左下deltayarr[deltaarrpos]=(INT)((image[((y-1)*widthx+1))*31]//image[((y-1)*widthx))*31]//image[((y-1)*width(x-1))*31]//image[((y+1)*widthx-1))*31]左image[((y+1)*widthx))*31]image[((y+1)*widthx+1))*313右}}////////}voidCWaterShedDoc::MergeRgs(MyRgnInfo*rginfoarr,INTrgnumber,INT*flag,INTwidth,INTheight,INT*outmerge,INT&rgnum){CString*neiarrnewCString[rgnumber+1];//第一个不用；INT*mergearr=outmerge;//记录合并情况数组；//for(INTy=0;y<height;{INTlstart=y*for(INTx=0;x<width;{INTpos=lstart+INTleft=-1,right=-1,up=-1,down=-1;myMath.GetNeiInt(x,y,pos,width,height,leftright,up,down);//找posINTcurid=flag[pos];AddNeiOfCur(curid,leftright,up,down,flag,}}////1iifor(INTrgi=1;rgi<=rgnumber;{//LONGallpoints=imageWidth*imageHeight;LONGnmin=(LONG)(allpoints/400);INTcurid=//rginfoarr[rgi].isflag初始为FALSE，在被合并到其它区后改为TRUE；while(((rginfoarr[rgi].ptcount)<nmin)&&!rginfoarr[rgi].isflag{CStringneistr=neiarr[curid];INTnearid=FindNearestNei(curid,neistr,rginfoarr,//合并curid与nearid；MergeTwoRgn(curid,nearid,neiarr,rginfoarr,}}INTcountjjj=//1iifor(INTii=1;ii<=rgnumber;{if{INTcurid=}}INTcounttemp=for(INTi=0;i<rgnumber;{if{counttemp}}rgnum=delete[]neiarr;neiarr=}5-15-2第六章总结算法，包括了分水岭算法的基本原理、数学描述和优缺点，并重点研究了V-着重研究了基于彩像的区域合成，介绍了几种常用彩色模型，而后研究了彩最后，在visualC++上实现了该算法，并且对比了区域合并前后效果。[1]R.CGonzalez,R.EWoods.DigitalImageProcessing.SecondEdition.PearsonEducationAsiaLimited.China:PublishingHouseofElectronicsIndustry,2002.567-642.[2].基于分水岭与区域生长的彩像分割算法研究:[湖南师范大学：湖南师范大学馆[3].图像分割方法及其应用研究综述.,2007,11- P.K.Sahoo,S.Soltani,A.K.C.Wong,etal.ASurveyofThresholding41(2):233-260. N.Otsu.AThresholdSelectionMethodfromGray-levelHistograms[J].IEEETransactionsonSystems,ManandCybernetics,1979,9(1):62-66. T.Pun.ANewMethodforGray-levelPictureThresholdingUsingtheEntropyoftheHistogram[J].SignalProcessing,1980,2(3):223- YasuoNakagawa,AzrielRosenfield.SomeExperimentsonVariableThresholding.PatternRecognition,1979,11:191-204..改进后的分水岭算法在图像分割中的应用研究:[山东大学:山东大学馆, Vishvjit,S.Nalwa,ThomasO.Binford.OnDetectingEdges.IEEETransactionsonPatternysisandMachineInligence,1986,8(6):Vishvjit,S.Nalwa,ThomasO.Binford.OnDetectingEdges.IEEETransactionsonPatternysisandMachineIn WangShu-Yen,Higgins,WilliamE.Symmetricregiongrowing.IEEETransactionsonImageProcessing,2003,12(9):RenMingyi,LiXiaofeng,LiZaiming.AnImprovedTransformationforImageSegment