1、清華大學(xué)本科生畢業(yè)設(shè)計(jì)題目: 基于MATLAB的圖像分割算法研究作者姓名 XXX 學(xué)號(hào) 指導(dǎo)教師 XX教授 學(xué)科專(zhuān)業(yè) 計(jì)算機(jī)科學(xué)與技術(shù) 所在學(xué)院 計(jì)算機(jī)學(xué)院 提交日期 目錄：1 引言2 圖像目標(biāo)分割與提取技術(shù)綜述3 最優(yōu)割集準(zhǔn)則的設(shè)計(jì)4 基于等周圖割的圖像分割5 編程語(yǔ)言的選擇6 程序運(yùn)行結(jié)果1. 引言數(shù)字圖像處理技術(shù)是一個(gè)跨學(xué)科的領(lǐng)域。隨著計(jì)算機(jī)科學(xué)技術(shù)的不斷發(fā)展，圖像處理和分析逐漸形成了自己的科學(xué)體系，新的處理方法層出不窮，盡管其發(fā)展歷史不長(zhǎng)，但卻引起各方面人士的廣泛關(guān)注。首先，視覺(jué)是人類(lèi)最重要的感知手段，圖像又是視覺(jué)的基礎(chǔ)，因此，數(shù)字圖像成為心理學(xué)、生理學(xué)、計(jì)算機(jī)科學(xué)等諸多領(lǐng)域內(nèi)的學(xué)者們

2、研究視覺(jué)感知的有效工具。其次，圖像處理在軍事、遙感、氣象等大型應(yīng)用中有不斷增長(zhǎng)的需求?；趫D論的圖像分割技術(shù)是近年來(lái)國(guó)際上圖像分割領(lǐng)域的一個(gè)新的研究熱點(diǎn)。該方法將圖像映射為帶權(quán)無(wú)向圖，把像素視作節(jié)點(diǎn)。利用最小剪切準(zhǔn)則得到圖像的最佳分割 該方法本質(zhì)上將圖像分割問(wèn)題轉(zhuǎn)化為最優(yōu)化問(wèn)題。是一種點(diǎn)對(duì)聚類(lèi)方法。對(duì)數(shù)據(jù)聚類(lèi)也具有很好的應(yīng)用前景。但由于其涉及的理論知識(shí)較多，應(yīng)用也還處在初級(jí)階段。因此國(guó)內(nèi)這方面的研究報(bào)道并不多見(jiàn)，本文將對(duì)圖論方法用于圖像分割的基本理論進(jìn)行簡(jiǎn)要介紹，并對(duì)當(dāng)前圖論方法用于圖像分割的最新研究進(jìn)展進(jìn)行綜述，并著重介紹基于等周圖割的圖像分割的方法。2. 圖像目標(biāo)分割與提取技術(shù)綜述圖像分割

3、是一種重要的圖像技術(shù)，在理論研究和實(shí)際應(yīng)用中都得到了人們的廣泛重視。圖像分割的方法和種類(lèi)有很多，有些分割運(yùn)算可直接應(yīng)用于任何圖像，而另一些只能適用于特殊類(lèi)別的圖像。有些算法需要先對(duì)圖像進(jìn)行粗分割，因?yàn)樗麄冃枰獜膱D像中提取出來(lái)的信息。例如，可以對(duì)圖像的灰度級(jí)設(shè)置門(mén)限的方法分割。值得提出的是，沒(méi)有唯一的標(biāo)準(zhǔn)的分割方法。許多不同種類(lèi)的圖像或景物都可作為待分割的圖像數(shù)據(jù)，不同類(lèi)型的圖像，已經(jīng)有相對(duì)應(yīng)的分割方法對(duì)其分割，同時(shí)，某些分割方法也只是適合于某些特殊類(lèi)型的圖像分割。分割結(jié)果的好壞需要根據(jù)具體的場(chǎng)合及要求衡量。圖像分割是從圖像處理到圖像分析的關(guān)鍵步驟，可以說(shuō)，圖像分割結(jié)果的好壞直接影響對(duì)圖像的理解

4、。2.1 圖像分割方法的發(fā)展和現(xiàn)狀分割問(wèn)題的困難在于圖像數(shù)據(jù)的模糊和噪聲的干擾。前面已經(jīng)提到，到目前為止，還沒(méi)有一種或者幾種完善的分割方法，可以按照人們的意愿準(zhǔn)確的分割任何一種圖像。實(shí)際圖像中景物情況各異，具體問(wèn)題具體分析，需要根據(jù)實(shí)際情況選擇適合的方法。分割結(jié)果的好壞或者正確與否，目前還沒(méi)有一個(gè)統(tǒng)一的評(píng)價(jià)判斷準(zhǔn)則，分割的好壞必須從分割的效果和實(shí)際應(yīng)用場(chǎng)景來(lái)判斷。不過(guò)在人類(lèi)研究圖像的歷史中，還是積累了許多經(jīng)典的圖像分割方法。雖然這些分割方法不適合所有類(lèi)型的圖像分割，但是這些方法卻是圖像分割方法進(jìn)一步發(fā)展的基礎(chǔ)。事實(shí)上，現(xiàn)代一些分割算法恰恰是從經(jīng)典的分割方法衍生出來(lái)的。早期的圖像研究中，圖像的分

5、割方法主要可以分為兩大類(lèi)。一類(lèi)是邊界方法，這種方法的假設(shè)是圖像分割結(jié)果的某個(gè)子區(qū)域在原來(lái)的圖像中一定會(huì)有邊緣存在；一類(lèi)是區(qū)域方法，這種方法的假設(shè)是圖像分割結(jié)果的子區(qū)域一定會(huì)有相同的性質(zhì)，而不同區(qū)域的像素沒(méi)有共同的性質(zhì)。這兩種方法都有缺點(diǎn)和優(yōu)點(diǎn)，有的學(xué)者也試圖把兩者結(jié)合起來(lái)進(jìn)行圖像分割，隨著計(jì)算機(jī)處理能力的提高，很多方法不斷涌現(xiàn)，如基于彩色分量分割、紋理圖像分割。所使用的教學(xué)工具和實(shí)驗(yàn)手段也是不斷的擴(kuò)展，從時(shí)域信號(hào)到頻域信號(hào)處理，近來(lái)小波變換也應(yīng)用在圖像分割當(dāng)中。2.1.1 研究背景與意義數(shù)字圖像目標(biāo)分割與提取是數(shù)字圖像處理和計(jì)算機(jī)視覺(jué)領(lǐng)域中一個(gè)備受關(guān)注的研究分支。因?yàn)樵谀繕?biāo)分割與提取過(guò)程中可以

6、利用大量的數(shù)字圖像處理的方法，加上其在計(jì)算機(jī)視覺(jué)、模式識(shí)別等領(lǐng)域中的廣泛應(yīng)用，都吸引了眾多研究者的注意。相信對(duì)這一問(wèn)題的深入研究不僅會(huì)不斷完善對(duì)這一問(wèn)題的解決，而且必將推動(dòng)模式識(shí)別、計(jì)算機(jī)視覺(jué)、人工智能等計(jì)算機(jī)科學(xué)分支的發(fā)展。圖像分割和邊緣檢測(cè)的問(wèn)題在近二十年中得到了廣泛的關(guān)注和長(zhǎng)足的發(fā)展，國(guó)內(nèi)外很多研究人士提出了很多方法，在不同的領(lǐng)域取得了一定的成果。但是對(duì)于尋找一種能夠普遍適用于各種復(fù)雜情況的準(zhǔn)確率很高的分割和檢測(cè)算法，還有很大的探索空間。邊緣提取和分割是圖像分析的經(jīng)典研究課題之一，目前的理論和方法仍存在許多不足之處，仍在不斷改進(jìn)和發(fā)展。需要說(shuō)明的是：邊緣與物體間的邊界并不等同，邊緣指的是

7、圖像中像素的值有突變的地方，而物體間的邊界指的是現(xiàn)實(shí)場(chǎng)景中的存在與物體之間的邊界。有可能有邊緣的地方并非邊界，也有可能邊界的地方并無(wú)邊緣，因?yàn)楝F(xiàn)實(shí)中的物體是三維的，而圖像只具有二維信息，從三維到二維的投影成像不可避免的會(huì)丟失一部分信息；另外成像的過(guò)程中的光照和噪聲也是不可避免的重要因素。正是因?yàn)檫@些原因，基于邊緣的圖像分割仍然是當(dāng)前圖像研究中的世界級(jí)難題，目前研究者們正在試圖在邊緣提取中加入高層的語(yǔ)義信息。由于圖像的多義性和復(fù)雜性，許多分割的工作無(wú)法依靠計(jì)算機(jī)自動(dòng)完成，而手工分割又存在工作量大，定位不準(zhǔn)確的難題，因此，人們提出了一些人工交互和計(jì)算機(jī)自動(dòng)定位相結(jié)合的方法，利用各自的優(yōu)勢(shì)，實(shí)現(xiàn)目標(biāo)

8、輪廓的快速定位。相信這些交互式方法的應(yīng)用，必將推動(dòng)圖像目標(biāo)分割與提取這一既具有廣闊的應(yīng)用前景又具有重要的學(xué)術(shù)價(jià)值的課題的進(jìn)一步研究，也必將成為一個(gè)更為獨(dú)立和活躍的研究領(lǐng)域。2.2 基于圖論的圖像分割基于圖論的圖像分割技術(shù)是近年來(lái)國(guó)際上圖像分割領(lǐng)域的一個(gè)新的研究熱點(diǎn)，在此，有必要先介紹一下基于圖論分割的一些基本知識(shí)。2.2.1 基本知識(shí)(1)圖的最優(yōu)劃分準(zhǔn)則令圖G=(V，E)，圖G被劃分為兩部分A、B，且有AB=V，AB=，節(jié)點(diǎn)之間的邊的連接權(quán)為(W(M，V)，則將圖G劃分為A，B兩部分的代價(jià)函數(shù)為：cut(A，B)= (1)使得上述剪切值最小的劃分(A，B)即為圖G的最優(yōu)二元?jiǎng)澐诌@一劃分準(zhǔn)則稱(chēng)

9、為最小割集(Minimum cut)準(zhǔn)則。(2)圖像的最佳分割將一幅圖像視為一個(gè)帶權(quán)的無(wú)向圖G=( V，E)，像素集被看作節(jié)點(diǎn)集.邊緣集被看作邊集E，像素之間的連接權(quán)為W（i,j），則將圖像二值劃分為兩個(gè)集合(區(qū)域)A，B的代價(jià)函數(shù)為：cut(A, B)= (2)對(duì)于一幅圖像，使得上述代價(jià)函數(shù)最小的劃分即為圖像的最佳分割。(3)權(quán)函數(shù)權(quán)函數(shù)一般定義為兩個(gè)節(jié)點(diǎn)之間的相似度。在基于圖論的圖像分割方法中常見(jiàn)的權(quán)函數(shù)有如下形式：上式權(quán)函數(shù)中，對(duì)于灰度圖像，F(xiàn)i的值為像素的灰度值，Xi為像素的空間坐標(biāo)，為灰度高斯函數(shù)的標(biāo)準(zhǔn)方差，為空間距離高斯函數(shù)的標(biāo)準(zhǔn)方差。r為兩像素之間的有效距離。若超過(guò)這一距離，則認(rèn)

10、為兩像素之間的相似度為0。此相似度函數(shù)認(rèn)為，兩像素之間的灰度值越接近，則兩像素之間的相似度越大，兩像素之間的距離越近則其相似度也越大。另外，文獻(xiàn)16定義了如下兩個(gè)權(quán)函數(shù)為：=exp(-) (4)= (5)上述權(quán)函數(shù)僅考慮了像素之間的灰度關(guān)系，沒(méi)有考慮其空間關(guān)系。(4)相似度矩陣、度矩陣及拉普拉斯矩陣圖論分割算法常把所定義的最優(yōu)割集準(zhǔn)則轉(zhuǎn)化為求解相似度矩陣或拉普拉斯矩陣的特征值及特征矢量問(wèn)題。相似度常用W或A表示，有時(shí)也稱(chēng)親和力(affinity)矩陣。將原圖像中的像素從左到有單行排列并作為相似度矩陣的行序列及列序列,相似度矩陣中每一個(gè)元素的值為使用相似度函數(shù)計(jì)算所得到的值,因此若一幅圖像尺寸為

11、，則其相似度矩陣元素個(gè)數(shù)將。將相似度矩陣的每行元素相加。即得到該節(jié)點(diǎn)的度，以所有度值為對(duì)角元素構(gòu)成的對(duì)角矩陣即為度矩陣，度矩陣常用D表示。拉普拉斯矩陣為L(zhǎng)=DW，在圖論分割算法中拉普拉斯為常用的標(biāo)準(zhǔn)矩陣。(5)勢(shì)函數(shù)、Fiedler矢量及譜勢(shì)函數(shù)為代表某像素劃分歸屬的指示矢量(indicator vector)。其定義為：若最終勢(shì)函數(shù)中某像素對(duì)應(yīng)的值為1則該像素屬于集合A，若為0則屬于集合B。但實(shí)際劃分求解得到的結(jié)果常為0到1之間的實(shí)數(shù)值，此時(shí)可用k均值聚類(lèi)等方法進(jìn)一步?jīng)Q定像素的歸屬。許多圖論分割算法將圖劃分問(wèn)題轉(zhuǎn)化為求解下述方程的第二小特征矢量問(wèn)題： x=x (7)這里的第二小特征矢量為第二

12、個(gè)最小特征值對(duì)應(yīng)的特征矢量，它代表了最佳圖劃分的一個(gè)解(即勢(shì)函數(shù))，把這一特征矢量稱(chēng)為Fiedler矢量。與特征矢量(不一定是Fiedler矢量)對(duì)應(yīng)的特征值稱(chēng)為譜。3 最優(yōu)割集準(zhǔn)則的設(shè)計(jì)目前，基于圖論的圖像分割方法的研究主要集中在以下幾個(gè)方面：(1)最優(yōu)剪切準(zhǔn)則的設(shè)計(jì)；(2)譜方法用于分割；(3)快速算法的設(shè)計(jì)；(4)其他圖論分割方法。通過(guò)對(duì)以上圖論的研究與比較，我們現(xiàn)在應(yīng)該找出一種較好的圖像分割的方法，或是得到這種方法的途徑。3.1 割集準(zhǔn)則 由式(2)的最優(yōu)分割準(zhǔn)則及式(3)的相似度函數(shù)可知，基于圖論的最優(yōu)分割基本原則就是使劃分成的兩個(gè)子圖(區(qū)域)內(nèi)部相似度最大子圖之間的相似度最小同時(shí)應(yīng)

13、使得劃分的區(qū)域盡量避免出現(xiàn)歪斜(即偏向小區(qū)域)分割。割集準(zhǔn)則的好壞直接影響到分割結(jié)果的優(yōu)劣。常見(jiàn)的割集準(zhǔn)則有Minimum cut，Average cut，Normalize cut，Min-maxCut，Ratio cut，F(xiàn)oreground-cut，Bcut，Isoperimetric ratio，Nested cut。表1列出了幾種常見(jiàn)的割集準(zhǔn)則。其中Norma1ize cut是一種較規(guī)范的形式，可以將準(zhǔn)則轉(zhuǎn)化為求解矩陣的特征矢量問(wèn)題 Isoperimetric ratio是一種較新穎的圖論分割算法，且運(yùn)算速度較快，不需要對(duì)相似度矩陣進(jìn)行重構(gòu)。最優(yōu)準(zhǔn)則的實(shí)現(xiàn)有兩種方式：一種是將最優(yōu)準(zhǔn)則

14、轉(zhuǎn)化為求解矩陣方程 ，另一種方法是使用所定義的準(zhǔn)則直接進(jìn)行圖縮減。前三種準(zhǔn)則的較詳細(xì)的性能對(duì)比參見(jiàn)文獻(xiàn)17。表1 幾種常見(jiàn)準(zhǔn)則的比較準(zhǔn)則準(zhǔn)則形式準(zhǔn)則實(shí)現(xiàn)方式特點(diǎn)Minimum CutCut(A,B)=樹(shù)圖縮減易傾向于較小的分割A(yù)verage CutAvcut(A,B)= +求方程(D-W)x=x易傾向于較大的分割Normalize CutNcut=Assoc(A,V)=求方程(D-W)x=Dx當(dāng)類(lèi)間重疊較大時(shí)易出現(xiàn)歪斜劃分Min-Max CutMcut=求方程(D-W)x=Dx后置處理需要花費(fèi)大量時(shí)間Ratio CutRcut(A,B)=樹(shù)圖縮減速度較慢，可避免劃分向短邊偏移Isoperime

15、tric Ratioh=表示區(qū)域S的體積,| 為區(qū)域S的邊界所包含的面積求方程= 速度較快3.2 譜方法譜方法在本質(zhì)上與圖論方法相一致此類(lèi)算法直接對(duì)原圖像構(gòu)造親和力矩陣(即相似度矩陣)W或拉普拉斯矩陣L，然后求解矩陣的特征矢量并以此為基礎(chǔ)直接或進(jìn)一步構(gòu)造特征矢量指導(dǎo)分割目前常見(jiàn)的幾種譜分割方法見(jiàn)表2。其中文獻(xiàn)l8是一種較規(guī)范、較常用的譜分割方法。表2 幾種常見(jiàn)的譜分割方法所用方程主要求解步驟Wx=求解最大特征值對(duì)應(yīng)的特征矢量用于指導(dǎo)分割，遞歸運(yùn)算(D-W)x=求解方程的Fiedler矢量指導(dǎo)分割，遞歸運(yùn)算Wx=求解前k個(gè)特征值對(duì)應(yīng)的特征矢量并合并成矢量V，將V按行歸一化等到矢量X，計(jì)算，通過(guò)Q

16、矩陣指導(dǎo)分割，即=1的象素將被分為一類(lèi)Nx=,其中特征矢量合并成矩陣V，將V按行矢量歸一化得到X，然后使用k均值方法將X的行矢量聚類(lèi)得到分割結(jié)果3.3 快速算法的設(shè)計(jì)從前面的介紹可以看到，圖論分割算法用于求解特征向量的實(shí)現(xiàn)方法其運(yùn)算耗費(fèi)主要在于相似度矩陣的構(gòu)造，相似度矩陣的元素個(gè)數(shù)與像素尺寸有著直接的關(guān)系，因此快速算法的設(shè)計(jì)主要集中在對(duì)相似度矩陣的采樣構(gòu)造與稀疏處理。另外，還可以通過(guò)改變搜索策略直接進(jìn)行圖縮減以提高算法速度。(1) Nystrom 采樣構(gòu)造相似度矩陣該方法的思想是對(duì)原圖像進(jìn)行采樣,計(jì)算n個(gè)采樣像素之間的相似度矩陣A,以及n個(gè)采樣像素與其余N一n個(gè)像素之間的相似度矩陣B,并使用A

17、，B對(duì)總相似度矩陣W 以及k個(gè)特征矢量進(jìn)行估計(jì)。由此原相似度矩陣寫(xiě)為：其中, 分別為前述矩陣,N為圖像的總像素個(gè)數(shù)， 為其余(N-n)個(gè)像素之間的相似度矩陣。令A(yù)可對(duì)角化為，表示W(wǎng)的特征矢量的估計(jì)，則有：W的估計(jì)為：式(10)中的特征矢量還需進(jìn)一步正交化才能使用。實(shí)驗(yàn)證明，只需對(duì)原數(shù)據(jù)采樣1%即可得到較高的估計(jì)質(zhì)量與較好的分割效果。(2)概率采樣與SVD估計(jì)文獻(xiàn)19的方法類(lèi)似于文獻(xiàn)20，但采樣方法與該文不同，在計(jì)算效率提高了10%的情況下仍得到了較好的分割結(jié)果。(3)使相似度矩陣W稀疏這種方法將W 矩陣中大部分元素值賦0，或?qū) 矩陣中的元素隨機(jī)賦0。文獻(xiàn)21使用4連通圖，并將矩陣中的元素進(jìn)行

18、編碼，使相似度矩陣的計(jì)算速度大為提高。(4)改變搜索策略前面幾種方法都是基于對(duì)相似度矩陣的變換。文獻(xiàn)22并不對(duì)相似度矩陣進(jìn)行操作，而是直接進(jìn)行圖縮減。傳統(tǒng)的MinCutMaxFlow算法當(dāng)給定的路徑長(zhǎng)度耗盡時(shí)開(kāi)始一個(gè)新的寬度優(yōu)先搜索構(gòu)建圖像的寬度優(yōu)先搜索樹(shù)要耗費(fèi)大量時(shí)間。文獻(xiàn)22提出一種遞歸的三步搜索策略：“生長(zhǎng)(growth)”、“增加(augmentation)”、“收養(yǎng)(adoption)”。通過(guò)在“增加” 階段將“tree"轉(zhuǎn)化為“forest”等，使得算法運(yùn)算時(shí)間比傳統(tǒng)方法大為縮減，甚至可以達(dá)到實(shí)時(shí)運(yùn)算。4. 基于等周圖割的圖像分割基于圖論的圖像分割方法是近年來(lái)國(guó)際上圖像分

19、割領(lǐng)域的一個(gè)新的研究熱點(diǎn)。該類(lèi)方法將圖像映射為帶權(quán)無(wú)向圖，把像素視作節(jié)點(diǎn),利用最小剪切準(zhǔn)則得到圖像的最佳分割。有學(xué)者首先將最小割集準(zhǔn)則用于圖像分割，很快這個(gè)方法就被轉(zhuǎn)化為求Laplacian矩陣的Fieldler矢量問(wèn)題。此后許多學(xué)者提出了不同的最優(yōu)圖劃分準(zhǔn)則用于圖像分割,較典型的有ratio cut準(zhǔn)則,等周割集(Isoperimetric cut)準(zhǔn)則等。譜圖分割提供了一種良好的圖像分割方法。我們借助小等周常數(shù)劃分的思想，將圖像分割問(wèn)題轉(zhuǎn)化為線(xiàn)性系統(tǒng)問(wèn)題，而不是特征向量問(wèn)題。利用這種方法旨在獲得高質(zhì)量的圖像分割效果，并提高速度和改進(jìn)穩(wěn)定性。4.1 等周問(wèn)題 等周割集準(zhǔn)則的提出源自典型的等周

20、問(wèn)題,即找出一個(gè)包含最大面積的最小周長(zhǎng)的邊界。定義一個(gè)集合U的等周常數(shù)為: h= (8)S U為集合U中的一個(gè)區(qū)域,表示區(qū)域S的體積,| 為區(qū)域S的邊界所包含的面積。由上述定義,等周常數(shù)h為所有可能的集合S的面積與體積之比的下確界。對(duì)一個(gè)緊致集合,其體積存在, ,而對(duì)非緊致集合有 <。我們?cè)谶@里指出找到一個(gè)同時(shí)具有最大面積（也就是說(shuō)，上確值）和最小周長(zhǎng)(也就是說(shuō), 下確值)的區(qū)域，直觀的說(shuō)，就是一個(gè)好的圖像分割了。早先應(yīng)用到圖像分割上的譜圖分割已經(jīng)產(chǎn)生了成功的算法。一般來(lái)說(shuō),以前的方法都是依據(jù)譜圖理論上的最大切/最小割算法。雖然等周準(zhǔn)則在直觀上是類(lèi)似于以前的譜圖理論，但表面算法上細(xì)小的差

21、別還是將圖像分割問(wèn)題轉(zhuǎn)化為線(xiàn)性系統(tǒng)問(wèn)題，而不是特征向量問(wèn)題。線(xiàn)性系統(tǒng)問(wèn)題是合乎需要的， 因?yàn)樗倪M(jìn)了速度和穩(wěn)定性。此外，譜圖分割還會(huì)出現(xiàn)一些“意外情況”。最小割算法易傾向與較小的分割，從而帶來(lái)問(wèn)題。而等周算法傾向與大量的分割，從而可以很好的避免這個(gè)問(wèn)題。4.2 等周算法(1)定義一個(gè)帶權(quán)無(wú)向圖G = (V, E) ,其節(jié)點(diǎn)v V,邊e E V ×V,分割節(jié)點(diǎn)與的邊定義為 ,權(quán)值為w ( ) ,節(jié)點(diǎn)的度為: = ， E (9)對(duì)于一個(gè)有限節(jié)點(diǎn)的圖來(lái)講,等周常數(shù)變?yōu)?= (10)其中S V, 。集合S的邊定義為, = | i S, j , 為S的補(bǔ)集。則集合S的面積為:|= (11)集合

22、S的體積為：=， (12)對(duì)有限節(jié)點(diǎn)式(10)的下確界應(yīng)為最小值。定義勢(shì)函數(shù)矢量X (13)以及一個(gè)矩陣L (Lap lacian矩陣) ,其元素為： | =LX (15) =d (16)d為節(jié)點(diǎn)度矢量。用r表示元素值全為1的列矢量,則在滿(mǎn)足約束=d下最大化S的體積可以通過(guò)令:d =d (17)來(lái)實(shí)現(xiàn)。由此式(10)的等周常數(shù)可寫(xiě)為:= (18)上式約束最優(yōu)化可以引入Lagrange乘子并將X松弛到實(shí)數(shù),然后最小化如下代價(jià)函數(shù)實(shí)現(xiàn):Q (X) = LX -(d -d) (19)=2LX-d (20)2LX=d (21)求解X時(shí)標(biāo)量2及可以省去。但由矩陣L的定義看出,L 的行和與列和都是0, 使

23、得(21) 式的求解需要引入新的約束。注意到圖G中c個(gè)不相連的子圖實(shí)際上對(duì)應(yīng)于矩陣L的秩為n - c。因此可將某先驗(yàn)節(jié)點(diǎn)放入?yún)^(qū)域,此操作對(duì)應(yīng)于從L中移除第g行第g列得到剩余矩陣,且對(duì)應(yīng)于移除X, d的第g行,得到,。因此求解勢(shì)函數(shù)X可轉(zhuǎn)化為求解:= (22)得到X0 即為指導(dǎo)分割的勢(shì)函數(shù)矢量。得到勢(shì)函數(shù)后,可通過(guò)設(shè)定閾值或k均值聚類(lèi)得到最終二值分割結(jié)果。(2)物理分析：等式(21)最早出現(xiàn)在電路理論中，當(dāng)時(shí)在確定電流源的無(wú)規(guī)則電路中解決電勢(shì)問(wèn)題。在電路中將一個(gè)節(jié)點(diǎn)接地（例如，使該節(jié)點(diǎn)電勢(shì)為0），決定保持電勢(shì)就需要等式13這個(gè)解決方案。因此，我們提到節(jié)點(diǎn)，我們先設(shè)定作為接地點(diǎn)。同樣的對(duì)于的解決方

24、案來(lái)自(22)。在節(jié)點(diǎn)，我們可能提到如的電壓。有了上面所闡述的符號(hào)，3個(gè)對(duì)接地的基本電路方程式就可以給出了：y=f (23)=y (24)p= (25)對(duì)一個(gè)電流分支向量y，電流源f和電勢(shì)差(電壓)p。注意在當(dāng)前公式中沒(méi)有電壓源。以上3個(gè)方程可以組合成一個(gè)線(xiàn)形系統(tǒng)：C=X=f， (26)即 =L18。我們發(fā)現(xiàn)電路和圖在這方面有很深的聯(lián)系。這一事實(shí)暗示了在圖上對(duì)這種算法的分析。電壓降計(jì)算出的每一個(gè)節(jié)點(diǎn)都存在這樣一種現(xiàn)象：很多可預(yù)料的自由電子從節(jié)點(diǎn)向地移動(dòng)。比如說(shuō)它可能從節(jié)點(diǎn)出發(fā)去。基于這種理論，等周分割就是將圖分割成擁有最小等周比率的圖。(3)算法細(xì)節(jié)1)算法摘要:基于等周圖割的圖像分割可以用以

25、下步驟來(lái)描述：1利用(27)式求所有邊的權(quán)并構(gòu)造L矩陣2選擇最大度的節(jié)點(diǎn)作為領(lǐng)域節(jié)點(diǎn)，并通過(guò)刪除對(duì)應(yīng)的列/行來(lái)確定L0和d0。3根據(jù)公式=求解出。4在對(duì)應(yīng)最低等周率所確定分割的值的地方設(shè)置勢(shì)能x的閾值5在每個(gè)分割上連續(xù)迭代，直到子分割的等周率比停止參數(shù)大2)找出每條邊的權(quán)：為了應(yīng)用等周算法來(lái)分割一張圖，這幅圖的值必須經(jīng)由每條邊的權(quán)來(lái)編碼。 我們使用標(biāo)準(zhǔn)的求權(quán)公式： (27)其中代表一個(gè)自由參數(shù)且代表了節(jié)點(diǎn)的參數(shù)。注意到可以用這兩點(diǎn)之間的幾何距離的矢量值表示。4.3 等周割集應(yīng)用舉例(1)等周割集準(zhǔn)則用于直方圖聚類(lèi)等周割集準(zhǔn)則用于直方圖聚類(lèi)實(shí)際上是使用該準(zhǔn)則對(duì)一維直方圖數(shù)據(jù)進(jìn)行聚類(lèi)。由直方圖進(jìn)行

26、二值分割實(shí)際上是對(duì)直方圖數(shù)據(jù)進(jìn)行二值聚類(lèi),直方圖的二值劃分灰度即為分割閾值。使用等周割集準(zhǔn)則進(jìn)行直方圖聚類(lèi)的算法步驟如下:1) 由式計(jì)算直方圖數(shù)據(jù)的相似度。2) 由式(9)及(14)計(jì)算度矩陣d及Laplacian矩陣L 。3) 選擇最大的節(jié)點(diǎn),將d及L中與該節(jié)點(diǎn)對(duì)應(yīng)的行和列刪除,得到新矩陣, 。4) 由式=求解勢(shì)函數(shù)。5) 對(duì) 進(jìn)行二值劃分,由式(18) 計(jì)算等周比值h ,并判斷是否大于給定的終止條件。6) 對(duì)直方圖數(shù)據(jù)進(jìn)一步迭代劃分,直到滿(mǎn)足終止條件。此時(shí)的二值劃分點(diǎn)即為分割閾值。其中,對(duì)的二值劃分通過(guò)k均值聚類(lèi)進(jìn)行,相似度函數(shù)的計(jì)算可以使用全連通圖(所有直方圖數(shù)據(jù)兩兩計(jì)算相似度) ,也可

27、以使用如4連通、8連通圖來(lái)進(jìn)行計(jì)算。5. 編程語(yǔ)言的選擇 題目的要求是用C+或者是MATLAB來(lái)實(shí)現(xiàn)這個(gè)算法，經(jīng)過(guò)比較，雖然對(duì)C+可能要更熟悉一點(diǎn)，但是在對(duì)題目的把握上，尤其是考慮到程序的編寫(xiě)上，經(jīng)過(guò)分析與老師的指導(dǎo)，認(rèn)識(shí)到使用MATLAB與C+各自的優(yōu)缺點(diǎn)后，決定使用MATLAB。5.1 MATLAB簡(jiǎn)介 MATLAB是一種功能十分強(qiáng)大，運(yùn)算效率很高的數(shù)字工具軟件，全稱(chēng)是Matrix Laboratory。起初它是一種專(zhuān)門(mén)用于矩陣運(yùn)算的軟件，經(jīng)過(guò)多年的發(fā)展，MATLAB已經(jīng)發(fā)展成為一種功能強(qiáng)大的軟件，幾乎可以解決科學(xué)計(jì)算中的任何問(wèn)題?？傊?，矩陣和數(shù)組是MATLAB的核心，因?yàn)镸ATLAB中的

28、所有數(shù)據(jù)都是以數(shù)組的表示和儲(chǔ)存的。除了常用的矩陣代數(shù)運(yùn)算值外，MATLAB還提供了非常廣泛和靈活的方式處理數(shù)據(jù)集的數(shù)組運(yùn)算功能。另外，MATLAB除了對(duì)矩陣提供了強(qiáng)大的處理能力之外，還具有一種與其他高級(jí)語(yǔ)言相似的編程特性。同時(shí)它還可以與Fortran和C語(yǔ)言混合編程，進(jìn)一步擴(kuò)展了其功能。在圖形可視化方面，MATLAB提供了圖形用戶(hù)界面（GUI），使得用戶(hù)可以進(jìn)行可視化編程。因此，MATLAB就把數(shù)據(jù)結(jié)構(gòu)、編程特性以及圖形用戶(hù)界面完美地結(jié)合到一起。5.2 MATLAB的主要應(yīng)用 1數(shù)學(xué)和計(jì)算 2算法開(kāi)發(fā) 3數(shù)據(jù)獲取 4建模、模擬和原型設(shè)計(jì) 5數(shù)據(jù)分析、研究和可視化 6科學(xué)和工程圖形 7應(yīng)用開(kāi)發(fā)，

29、包括圖像用戶(hù)界面構(gòu)建基于此，選用MATLAB已經(jīng)是很明顯的了。5.3 MATLAB的優(yōu)點(diǎn)(1)MATLAB使用方便MATLAB允許用戶(hù)以數(shù)學(xué)形式的語(yǔ)言編寫(xiě)程序，用戶(hù)在命令窗口中輸入命令即可直接得出結(jié)果，這比C+、Fortran和Basic等等該機(jī)語(yǔ)言都要方便的多。而且它是用C語(yǔ)言開(kāi)發(fā)的，其流程控制語(yǔ)句與C語(yǔ)言中的相應(yīng)語(yǔ)句幾乎一致。這給使用上帶來(lái)了方便，使我能較快的適應(yīng)與使用MATLAB這門(mén)語(yǔ)言。(2)內(nèi)部函數(shù)非常豐富MATLAB的內(nèi)部函數(shù)提供了相當(dāng)豐富的函數(shù)，這些函數(shù)解決許多基本問(wèn)題，如矩陣的輸入。在其它語(yǔ)言中(比如C語(yǔ)言中)，要輸入一個(gè)矩陣，先要編寫(xiě)一個(gè)矩陣的子函數(shù)，而MATLAB語(yǔ)言則提供

30、了一個(gè)人機(jī)交互的數(shù)學(xué)系統(tǒng)環(huán)境，該系統(tǒng)的基本數(shù)據(jù)結(jié)構(gòu)是矩陣，在生成矩陣對(duì)象時(shí)，不要求做明確的維數(shù)說(shuō)明。與利用C語(yǔ)言或 Fortran等等高級(jí)語(yǔ)言編寫(xiě)數(shù)值計(jì)算的程序相比，利用MATLAB可以節(jié)省大量的編程時(shí)間。這就給用戶(hù)節(jié)省了很多的時(shí)間，使用戶(hù)可以把自己的精力放到創(chuàng)造方面，而把繁瑣的問(wèn)題交給內(nèi)部函數(shù)來(lái)解決。除了這些數(shù)量巨大的基本內(nèi)部函數(shù)外，MATLAB還有為數(shù)不少的工具箱。這些工具箱用于解決某些領(lǐng)域的復(fù)雜問(wèn)題。(3)強(qiáng)大的圖形和符號(hào)功能MATLAB具有強(qiáng)大的圖形處理功能，它本身帶有許多繪圖的庫(kù)函數(shù)，可以很輕松地畫(huà)出各種復(fù)雜的二維和多維圖形。這些圖形可以在與運(yùn)行該程序的計(jì)算機(jī)連接的任何打印機(jī)設(shè)備上打

31、印出來(lái)，這使得MATLAB成為技術(shù)數(shù)據(jù)可視化的杰出代表。MATLAB也開(kāi)發(fā)了自己的符號(hào)運(yùn)算功能，特別是MATLAB7.0在這方面的功能絲毫不遜色于其他的相關(guān)軟件，如Mathematic等等。因此，用戶(hù)只需要掌握MATLAB一門(mén)語(yǔ)言，就幾乎可以解決學(xué)習(xí)和科研中的所有問(wèn)題，不必再專(zhuān)門(mén)學(xué)習(xí)一門(mén)符號(hào)運(yùn)算語(yǔ)言。(4)可以自動(dòng)選擇算法在使用其他語(yǔ)言編制程序時(shí)，往往會(huì)在算法選擇上費(fèi)一番周折，但是在MATLAB里，這個(gè)問(wèn)題將不復(fù)存在。MATLAB的許多功能函數(shù)都帶有算法自適應(yīng)能力，它會(huì)根據(jù)情況自行選擇最合適的算法，這樣，當(dāng)使用其他程序時(shí)，因算法選擇不當(dāng)而引起的譬如死循環(huán)等錯(cuò)誤，在使用MATLAB時(shí)可很大程度避

32、免。6 程序運(yùn)行結(jié)果 程序經(jīng)過(guò)運(yùn)行輸入圖片后，可得出結(jié)果，下面將待處理的圖片與處理后的圖片進(jìn)行對(duì)比，以清楚的表現(xiàn)出圖像分割：圖3 待分割的原圖圖4 分割后的圖為進(jìn)行比較，以下是另外圖的結(jié)果：圖5 基于等周圖割的圖像分割實(shí)驗(yàn)結(jié)果良好，達(dá)到了預(yù)期的效果。結(jié) 論數(shù)字圖像目標(biāo)分割與提取是數(shù)字圖像處理和計(jì)算機(jī)視覺(jué)領(lǐng)域中一個(gè)備受關(guān)注的研究分支，也是圖像處理領(lǐng)域的一個(gè)經(jīng)典難題。經(jīng)過(guò)近二十年的不斷研究和探討，數(shù)字圖像目標(biāo)分割與提取在不同領(lǐng)域取得了很大發(fā)展，但是目前還沒(méi)有一個(gè)通用的算法或標(biāo)準(zhǔn)能夠勝任所有不同的應(yīng)用，該問(wèn)題也沒(méi)有形成一個(gè)通用的自身理論。我通過(guò)學(xué)習(xí)和實(shí)踐經(jīng)典的圖像目標(biāo)分割與提取的算法，對(duì)這一領(lǐng)域的歷

33、史和發(fā)展現(xiàn)狀有了較為清楚的認(rèn)識(shí)。在現(xiàn)在的研究水平下，想找出一種通用的技術(shù)或方法是很困難的。每一種算法都有其自身的優(yōu)點(diǎn)和缺點(diǎn)，有其特定的適用范圍，因此首先明確研究對(duì)象的性質(zhì)是至關(guān)重要的，這樣在使用算法時(shí)才可以有的放矢。經(jīng)典的算法雖然在應(yīng)用上已被新的算法所取代，但經(jīng)典算法中的很多思想都具有相當(dāng)重要的價(jià)值，它們是新算法研究和提出的基礎(chǔ)?；诘戎軋D割的圖像分割中的等周算法，是基于圖論的圖像分割方法研究的產(chǎn)物，它是圖像分割算法研究上的一大進(jìn)步。傳統(tǒng)的圖像分割方法已經(jīng)不能適用于現(xiàn)在的實(shí)際要求，需要與先進(jìn)的技術(shù)結(jié)合才能有所突破。但是在同時(shí)，這種算法也有著固有的缺點(diǎn)，他們都是針對(duì)圖像灰度數(shù)據(jù)進(jìn)行聚類(lèi)分割，運(yùn)算

34、量隨圖像尺寸增大而增大。通過(guò)本次畢業(yè)設(shè)計(jì)，我得到了許多收獲。不但對(duì)數(shù)字圖像目標(biāo)分割與提取鄰域的基本理論和基本知識(shí)有了較為全面的了解，在對(duì)新知識(shí)學(xué)習(xí)的過(guò)程中，自己原有的知識(shí)和理論也得到了進(jìn)一步的鞏固，同時(shí)自己的編程能力也得到了一定程度的提高。另外，在畢業(yè)設(shè)計(jì)過(guò)程中，我所學(xué)的知識(shí)得到了系統(tǒng)地整理和運(yùn)用，這既是對(duì)我四年學(xué)習(xí)的檢查，也為我今后在工作上的學(xué)習(xí)打下了堅(jiān)實(shí)的基礎(chǔ)。因?yàn)闀r(shí)間倉(cāng)促，再加上本人水平有限，在畢業(yè)設(shè)計(jì)過(guò)程中存在不少不足之處。我將以此為鑒，在今后的學(xué)習(xí)和生活過(guò)程中不斷改進(jìn)。致 謝正值論文完成之際，謹(jǐn)向所有曾給予我鼓勵(lì)、關(guān)心和幫助的老師、同學(xué)、朋友表示深深的謝意！我還要感謝我們班以及我們系

35、我所認(rèn)識(shí)的同學(xué)，是你們給了我好的環(huán)境和鼓勵(lì)幫助，讓我順利的完成了這次的設(shè)計(jì)。感謝在我成長(zhǎng)過(guò)程中所有關(guān)心我、幫助我的人們。參 考 文 獻(xiàn)1 夏得深，傅德勝.現(xiàn)代圖像處理技術(shù)與應(yīng)用.東南大學(xué)出版,20012 K.R.Castleman. 數(shù)字圖像處理.電子工業(yè)出版社,19983 岡薩雷斯.數(shù)字圖像處理（MATLAB版）.電子工業(yè)出版社,20054 劉直芳,游勝志等.基于多尺度彩色形態(tài)矢量算子的邊緣檢測(cè).中國(guó)圖像圖形學(xué)報(bào) 2002 (9) 888-8935 潘晨,顧峰.基于3D直方圖的彩色圖像分割方法.中國(guó)圖像圖形學(xué)報(bào) 2002 (8) 800-8056 李宏貴,李興國(guó).一種基于函數(shù)的圖像邊緣檢測(cè)算

36、法.中國(guó)圖像圖形學(xué)報(bào) 2003(2) 188-1927 J. Shi and J. Malik.“Normalized cuts and image egmentation”.Proc. of CVPR, p. 731-37, 19978 W.Y. Ma and B.S. Manjunath.“Edge flow: a framework of boundary detection and image segmentation”.Proc. of CVPR, pp 744-49, 19979 S. Belongie, et. al.“Color- and texture-based image

37、 segmentation using EM and its application to content-based image retrieval”. Proc. of ICCV,p. 675-82, 199810 .“Perfect ImageSegmentation Using Pulse Coupled NeuralNetworks”.IEEE trans. on NeuralNetworks,Vol.10,No.3, 199911 孫祥，徐流美，吳清.MATLAB 7.0 基礎(chǔ)教程.清華大學(xué)出版社，200512 WU Z , LEAHY R .An op timal graph t

38、heoretic app roach to data clustering: theory and its app lication to image segmentation J .IEEE Transactions on Pattern Analysis and Machine Intelligence,1993, 15 (11) : 1101 111313 SH I J, Malik J. Normalized Cuts and Image SegmentationA . Pro2ceedings of IEEE Conference on ComputerVision and Pattern Recog2 nitionC , 1997