四隊和一隊基于分水嶺算法圖像分割研究

中圖像分割是指把圖像分成各具特性的區(qū)域并提取出感目標的技術(shù)和過后結(jié)合V-S分水嶺算法的排序和浸沒過程進一步分析處理圖像。針對傳統(tǒng)的分水嶺算法在彩像分割時常常會產(chǎn)生過分割現(xiàn)象，利用基于彩像的區(qū)域合成解決分水嶺的過分割問題，在去除圖像噪聲的同時最后，利用visualC++語言實現(xiàn)了該算法，并進行了試驗，實驗結(jié)果表明程序能較好的實現(xiàn)對彩像的分割效果。：圖像分割，梯度，V-S分水嶺算法，區(qū)域合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-圖像分割技術(shù)發(fā)展現(xiàn)狀.......................................................................................-1-本文研究內(nèi)容2-第二章圖像梯度計算3-圖像分割定義3-圖像分割的方法4-圖像梯度算子4-4-一階導(dǎo)數(shù)算子6-二階導(dǎo)數(shù)算子7-8-分水嶺算法的原理8-分水嶺算法的數(shù)學(xué)描述........................................................................................-9-分水嶺算法的優(yōu)缺點11-V-S分水嶺算法12-V-S算法的排序過程12-V-S算法的浸沒過程13-第四章基于彩像的區(qū)域合并..................................................................................-14顏色空間模型14-彩像顏色空間..............................................................................................-15相似區(qū)域合并15-第五章基于visualC++16-16-16-第六章總結(jié)21-參考文獻22-研究的背景及圖像、圖形（動畫、、文本、數(shù)據(jù)等，這也是人類最有效和最重要的信息哪種目的,圖像處理中最關(guān)鍵的一步就是對包信息的圖像進行分割。圖像分割技術(shù)發(fā)展現(xiàn)閾值分割法是一種并行分割法[4]。早期的閾值分割法如Otsu等類別方差法[5]T.Pun引入的最大熵法[6]等均未考慮像素點的空間信息，對含噪聲和不均勻的圖像較敏感，容易在分割區(qū)域中產(chǎn)生空洞。Nakagawa等變化閾噪聲干擾。其他的邊緣檢測法有Vishvjit等基于曲面擬合的方法[10]，Kass等變形模型算法[11]等。變形模型算法[10]的分割結(jié)果均為閉合連續(xù)的曲線WanShu-Yen等對稱區(qū)域生長法[12],克服了區(qū)域分割法過分依賴區(qū)域的最低梯度值像素點，因此無須人工或計算選取點。維圖像，從灰度圖像到彩像[14]、多光譜圖像，從靜態(tài)分析到動態(tài)[15]等除了傳統(tǒng)的三類方法外圖像分割的方法還包括基于理論的分割方法、基于形態(tài)學(xué)的分水嶺算法[16]是最近發(fā)展起來的一種圖像分割方法,它基于測地學(xué)上的測線重構(gòu)，由Beucher等人最早提出。該方法的主要目標是找出分水嶺。具有代表性的一種分水嶺算法是LucVincent和PierreSoille于彩像的區(qū)域合并技術(shù)來解決該問題，并取得良好的效果。本文研究內(nèi)1計算，包括一階導(dǎo)數(shù)算子如Roberts算子、Sobel算子、Prewitt算子、Canny算子等，二階導(dǎo)數(shù)算子如Laplacian算子、LoG（Laplacian-Gauss）算子。V‐S3．基于彩像的區(qū)域合由于分水嶺算出現(xiàn)嚴重的過分割分水嶺變換的結(jié)果容易產(chǎn)生過量非必彩像顏色空間，包括RGB模型、CMY和CMYK模型、YIQYUV4．基于vc++在Visual圖像分割定出感的目標或前景的過程稱為圖像分割技術(shù)[17]。RRRN個滿足以下五個條件的非空子集[19]（子區(qū)域）P(Ri)FALSER1R2RN：NRNRi；所有的iji

j，有RiRji=1，2，…，NP(RiTRUE ijP(RR)FALSE i=1，2，…，NRiP(Ri是對所有在集合Ri中元素的邏輯謂詞，φ上述這些條件[19]不僅定義了分割，也對如何進行分割有指導(dǎo)作用。對圖圖像分割的方分割問題的在于圖像數(shù)據(jù)的模糊和噪聲的干擾。到目前為止，還沒有一概念,它在本質(zhì)上是一種區(qū)域增長的算法,不過與傳統(tǒng)區(qū)域增長算法不同的是,圖像梯度算圖像邊緣號為例如圖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由二階導(dǎo)函數(shù)f''(x)的連續(xù)性，再次應(yīng)用日中值定理，得f'(x0x)f'(x0xx)f''(x0x'x)x(0,'合并上述結(jié)果，并代入（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算子具有的優(yōu)點[9]是定位邊緣能力比較高，精確讀高，偏移小，垂糙，不夠平滑細膩，對噪聲也較敏感，容易受到噪聲的干擾。Roberts算子適用Sobel算子點就是邊緣點。Sobel3×3的模板為[18]：2-5SobelSobel算子具有的優(yōu)點[9]是能通過梯度方向信息獲取精確的邊緣方向信息。RobertsSobel算子雖有一定的去噪功能，Prewitt算子原理：與Sobel算子一樣，但Prewitt算子沒有用值，將g像素點周圍Canny算子

2-6Prewitt圖像中的一階導(dǎo)數(shù)最大值，定位到的點即為邊緣點。Canny3個準邊緣定位精確度準則，邊緣定位精確度L定義如下WW h2公式(2-9)中，G'(x是邊緣定位函數(shù)G(x的導(dǎo)函數(shù)，h'(xW的濾波器的脈沖響應(yīng)函數(shù)h(x)的導(dǎo)函數(shù)[18]。信噪比準則，信噪比SNR定義為WWh2公式(2-10)中，h(x)是寬度為W

濾波器的脈沖響應(yīng)函數(shù)，G(x)邊緣定位函數(shù)，σ為濾波器的均方差值[18]單邊緣準則，確保檢測到的邊緣是單像素點D(f)

1h'2h''(x)dx公式(2-11)h''(xh(x)的二階導(dǎo)函數(shù)[18]Canny檢測算子，從而獲得效果最佳的邊緣結(jié)果。Canny算子的邊緣檢測效果較前面的幾個一階導(dǎo)數(shù)算子都要好，Canny算子具備抑制噪聲的能力和精確的邊緣定位能力，缺點是去[9]。已知一階導(dǎo)數(shù)的最大值處對應(yīng)二階導(dǎo)數(shù)的過零點，因此可通過查找二階導(dǎo)Laplacian算子原理：像素點的二階導(dǎo)數(shù)的零交叉點即為邊緣點。Laplacian算子求取二階 2 2gx2

2 Laplacian算子的優(yōu)點[16]是邊緣定位精度很高。缺點是對噪聲過于敏感，無法獲得邊緣的方向信息。為了緩解對噪聲的敏感，Laplacian算子邊緣檢測前一LoG（Laplacian-Gauss）算子檢測算子之前，一般都要經(jīng)濾波器濾除掉圖像中的噪聲。LoG[9算子是將Laplacian算子和濾波器相結(jié)合得到的一種邊緣檢測算子。首先用濾波g(x,y用LoG算子檢測邊緣的公式如下x2y22

x2y2G(x,y) )e2

*g(x,

公式(2-14)中，*表示求卷積，σ為濾波器的均方差值[18]分水嶺算法的原上述方法是分水嶺算法基于模擬浸沒的過程,分水嶺的另一種描述方法是基于模擬降水的過程[2]。同樣將圖像視為高低起伏的地形圖，梯度值仍然代表每分水嶺算法的數(shù)學(xué)IDZ2I設(shè)定為0NI0N255,則I的定義如下

Z2IpI(

1[22]IpqL是由(l+1)個點組成，這些點為p0

pl1plp0

,plq于任意點i滿足：i1,l,(pi1,pi)G（G表示數(shù)字網(wǎng)格表示 定義2[22]：圖像I中高度為h的極小區(qū)M是由一個或多個梯度值為的像素點構(gòu)成的連通區(qū)域，極小區(qū)M中的任一點若要與梯度值小于h點之間形成連通路徑L，L路徑中必然有一點梯度值大于hpLqL,pI(qIpLp0 pl1plp0pplq（3-（climb3-2中若要從極小區(qū)M中任一像素點連通道h-1的像素點時必須經(jīng)過圖中向上的紅色箭頭所指路徑，而此路徑中必然存在梯度值>h的像素點。（climb）對于圖I，梯度值范圍D(i,jC(i,jE(i,j)DI的下限值即梯度最小值hmin，上限值即梯度最大值hmax，當梯度值為h時，用Th(I表示梯度值h的所有像Th(I){pDI,I(p)h}（3-假設(shè)極小區(qū)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內(nèi)并且是所有可取路徑中的最短路徑，如圖3-3所示，測地距離用公式定義如下：)3-3Bk集合集合B由B1,B2 k個互不相連的區(qū)域組成定義連通區(qū)域Bk(BiBiBj的距離，其中ijA，如圖3-4所示，測地影響區(qū)域的公式定義如下[22]:izA(Bi{pA,j1k且jidApBidApBj)}（3-A區(qū)域內(nèi)所有的點計算測地距離并確定測地影響區(qū)域后，只剩下不屬于SKIZA(B)AIZA(B),其中

(B) iz(B

3-4分水嶺算法的優(yōu)缺（b嚴重的過分割，分水嶺變換的結(jié)果容易產(chǎn)生過量非必要的小區(qū)域（a）原 圖3-5各種圖像分割算法對比圖納總結(jié)，實際應(yīng)用中通常采用的消除過分割的方法分為以下三種由Vincent和Soille分水嶺算法使分水嶺圖像分割方法得到推（以V-S算法。相對于傳統(tǒng)的分水嶺算法，V-S排序[22]：順序掃描梯度圖像中的像素點，按梯度值升序的順序排列過隊列queue結(jié)構(gòu)的先進先出方式處理每個像素點。g[h]來表示，其中hg[h]表示梯度級h所包含的像素點個數(shù)。級hg[h]即自增1。梯度級累加概率是指：當梯度級為h時，所有小于或等于梯度級h所包中，像素點的順序為：上、左、右、下。排序結(jié)果如圖3-6所示。由以上步驟可知，排序過程總共對圖像掃描了23-6V-S浸沒過程的算法步驟描述如下處理每一梯度級：排序后梯度圖中的最低梯度級記為hmin，最高梯度級記為hmax。按梯度級從低到高的順序掃描hmin到hmax的每一個梯度級，假設(shè)當前h（h為h層。然后按照下面（2）至（4）h層由圖3-6可知，排序后像素點包含了在圖中所處的坐標信息和自身的梯度值信息，則查找h層的像素點時，每個像素點的坐標信息均可獲得。假設(shè)當前像素點為點Pcur，掃描點Pcur鄰域點，若鄰域中有點已經(jīng)被標方法PcurFIFO隊列中，如果鄰域點被標記，那么當前像素點就順序處理第（2）步中壓入FIFO隊列中的點。FIFO隊列中的點按先進先出的順序處理，每標記一個點后將此點移出FIFO隊列，然后處理隊列中hFIFO隊列，再執(zhí)行當前步驟。循環(huán)查找鄰域點的鄰域內(nèi)是否同屬于h層，若有，繼續(xù)執(zhí)行當Pcur的連通區(qū)域內(nèi)查找不到h層像素點。Pcurh層的像素點FIFO隊列，直到確定點Pcur的連通區(qū)域周圍均無被標記積水盆地，則標記Pcur所在連同區(qū)域為新的極小區(qū)（h的像素點。標記順序為FIFO中的順序。Pcurh素點都要進出FIFO隊列，這是非常耗時的操作。下一章介紹的快速分水嶺算法，剔除了耗時的FIFO隊列，節(jié)省了進出隊列的時間。顏色空間模RGB模型RGBRGB三色光互相疊加來實現(xiàn)混色的F（物體顏色）=R（紅色的百分比）+G（綠色的百分比）+B（藍色的百比由于圖像和顯示設(shè)備使用的是RGB彩色模型，所以RGB彩色模型彩像處理中最基礎(chǔ)的彩色模型CMYCMYK模型（Cyan（MagentaCMY模型中，線完全被反射時顯示為白色（加色法從理論上來說，只需要CMY三種油墨等比例混合在一起就會得到黑色，但會加入黑色油墨，這就是CMYK色彩混合模式的由來。所以CMYK又稱為印刷YIQYUV模型YIQ與YUVYIQ，是NTSC(NationalevisionStandardsCommittee)電視系統(tǒng)標準，適用于彩色電視廣播中，Y是提供黑白電視及彩色電視的亮度信號（Lumminance）,即亮度（Brightness）,I代表In-phase,色彩從橙色到青色，QQuadrature-phase,色彩從紫色到黃綠色，是RGB表示的一個簡單線性變化。YUVYIQ彩色模型類似，不同在于空間多了一個33的旋轉(zhuǎn)，是為了能與黑白電視兼容，YUV中亮度信號（Y）和色度信號（U、V）是相互獨立的，即Y信號分量構(gòu)成的黑白灰度圖與U、V的另外兩個單是相互獨彩像顏色空RGB顏色空間[28]能有效顯示圖像，目前的顯示器、電視機、數(shù)碼相機、攝像機等大都采用RGB顏色標準。但圖像處理領(lǐng)域一般不直接用RGB顏色空間，是由于RGB空間的以下三個特性[29]：RGB空間基于底層硬件，與人眼視覺感觸有一定差距，圖像處理是為RGBRGBLUV顏色空間[30]各分量相關(guān)性小，LUV色度圖中點距正比于人眼所感知LUV顏色空間更適合于圖像處理。LUV顏色空間[30]中，L代表亮度，U和V代表色度坐標，U、V的取值范圍為-100到+100，L的取值范圍為0到100。RGB到XYZ顏色空間的轉(zhuǎn)換[30]：一幅彩像中，將像素點的（R，G，B）轉(zhuǎn)化為（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顏色空間的轉(zhuǎn)換

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 相似區(qū)域合D(i,j)C(i,j)E(i,j)（4-公式(4-5)C(i,j為兩個區(qū)域的色度相似度，定義如下(LL)2(LL)2(UU)2(VV 為區(qū)域j中所有像素點的的 U,V三分量的均值[30]公式(4-6)E(ij為兩個區(qū)域間的分水嶺兩側(cè)像素點的梯度均值的相似度，定E(i,j)i

公式(4-7)中，i，j表示兩相鄰區(qū)域間分水嶺兩側(cè)像素點的梯度均值[32]。若分水嶺為越明顯的邊緣，i，jE(i,j就越大。開發(fā)環(huán)境和系統(tǒng)操作系統(tǒng)：Windows7（CPU：In內(nèi)存：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;//在梯度數(shù)組中的位置；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;//記錄合并情況數(shù)組；//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，在被合并到其它區(qū)后改為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第六章總結(jié)算法，包括了分水嶺算法的基本原理、數(shù)學(xué)描述和優(yōu)缺點，并重點研究了V-著重研究了基于彩像的區(qū)域合成，介紹了幾種常用彩色模型，而后研究了彩最后，在visualC++上實現(xiàn)了該算法，并且對比了區(qū)域合并前后效果。[1]R.CGonzalez,R.EWoods.DigitalImageProcessing.SecondEdition.PearsonEducationAsiaLimited.China:PublishingHouseofElectronicsIndustry,2002.567-642.[2].基于分水嶺與區(qū)域生長的彩像分割算法研究:[湖南師范大學(xué)：湖南師范大學(xué)館[3].圖像分割方法及其應(yīng)用研究綜述.,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..改進后的分水嶺算法在圖像分割中的應(yīng)用研究:[山東大學(xué):山東大學(xué)館, 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