【正文】 類區(qū)域組合，然后選取一個合適的閾值，判斷圖像中每一個像素點是屬于目標區(qū)域還是屬于背景區(qū)域。分割的閾值通常根據(jù)圖像的一維灰度直方圖來選擇。該算法適合目標區(qū)域與背景區(qū)域灰度值有較大差異的情況，但是該算法并沒有考慮圖像空間信息?；趨^(qū)域的圖像分割方法，基于區(qū)域的圖像分割方法是根據(jù)圖像的顏色、紋理等圖像特征，把圖像的像素劃分到各個區(qū)域中，進而將圖像分割成為不同區(qū)域的一種分割方法。如區(qū)域增長算法，其基本思想是根據(jù)一定的相似準則，將圖像中相似區(qū)域或者像素合并成一個更大的區(qū)域。分割效果依賴于種子的選取及生長的順序。圖 32 區(qū)域增長分割算法分水嶺分割算法，該算法實際上一種基于數(shù)學形態(tài)學的分割算法，對圖像的梯度圖進行分割。合并分裂算法，其根本思想是根據(jù)圖像各個區(qū)域的不均勻性將圖像分割成不同的子區(qū)域，然后根據(jù)臨近區(qū)域的均勻性將相鄰的子區(qū)域合并成較大的區(qū)域。圖 33 合并分裂算法基于邊緣的圖像分割方法如邊緣檢測算子（Robert 算子精度高但對噪聲比較敏感 Sobel 算子在獲得較好的邊緣效果的同時，對噪聲具有一定的平滑作用，但是精度較低，Prewitt 算子相對較為簡單） 、邊緣松弛法、邊界跟蹤法等。除第 3 章 基于 CMRM 的圖像標注改進算法 19 此以外，近年來新出現(xiàn)的結合特定理論、方法的圖像分割方法如基于模糊理論的圖像分割方法、基于支持向量機的圖像分割方法、基于神經(jīng)網(wǎng)絡的圖像分割方法、基于圖論的圖像分割方法、基于粒度計算理論的圖像分割算法、基于免疫算法的圖像分割技術等。在 CMRM 圖像標注方法中采用歸一化分割算法 (Normalized Cut)[42]。圖像分割是圖像自動標注算法的基礎，它將圖像分割成一些有意義的視覺對象區(qū)域，為 CMRM 方法下一步的訓練標注模型操作提供素材。因此，作為圖像自動標注算法的關鍵步驟之一，圖像分割結果的好壞直接影響對圖像內容的理解以及標注結果的準確性。在 CMRM 圖像標注方法中采用歸一化分割算法。該算法屬于基于圖論的圖像分割方法。對簡單圖像分割效果較好，但是對于背景較為復雜的圖像，不僅分割效果差而且會產(chǎn)生許多沒有意義的圖像區(qū)域，而且當圖像中像素點較多時，生成圖的節(jié)點數(shù)目也會隨之增多，從而給計算求解帶來了很大困難，影響分割效率。因此，本文采用了基于普擴散理論的圖像分割算法，該算法在圖像自動分割的同時提供人工輔助分割方法，根據(jù)用戶輸入的感興趣區(qū)域，實現(xiàn)對圖像的精確分割，此算法對于背景復雜的圖像是一種很有效的圖像分割算法。下面將分別介紹這兩種分割算法并給出實驗結果對比。 基于 Normalized Cut 的圖像分割算法歸一化分割算法(Normalized Cut)是一種基于圖論的圖像分割算法。在圖論中所謂分割，就是對于圖 ，其中 V 代表節(jié)點的集合，在圖像中表示為像(,)GE?素集，E 代表了連接兩兩節(jié)點的邊集。通過移除 A，B 兩部分之間的邊，可以把圖分割成不想交的兩個子集 A 和 B，且有 ， ，節(jié)點之間????的邊連接權為 ，我們所移除的邊的總的權重可以用來表示這兩個部分之(,)wuv間的不相似度： (31)(,)(,),ctwuv???Wu 和 Leahy[43]曾提出一種基于最小分割標準的圖像分割算法，該算法是將圖分割成 k 個子圖，并且保證這些子圖之間的最小分割值。這個問題可以通過二分迭代法來找到最小分割值。但是正是由于只考慮了子圖之間的分割值最小，在兩個子集之間任意增加一條邊都會增加子集之間的分割值，而單個頂點與其補圖之間的邊往往最少，因此該方法會趨向于分割單個頂點，而真正的最佳分割反而無法得到。為了避免這種分割出小部分點的不正常情況，Shi 和 Malik 提出了一種新的子集之間不相似度的測量標準歸一化最小分割(Normalized Cut) 。北京工業(yè)大學工學碩士學位論文 20 Normalized Cut 方法將該不相似度歸一化并表示為如下公式： (32)(,)(,)(,)cutABcutNctasoVaso??其中 同理可得 。,(,),asoAVwtt??(,)(,),BVwutt???對于一幅圖像，求得 A 與 B 之間 值最小的劃分即為圖像的最佳分割。,cuA我們定義 表示從節(jié)點 i 到其他節(jié)點的連接權值和。()(,)diij?， ， 其中 x 為 維指示向量，如果0iixk???1kb?(1)yxb??V，表示節(jié)點 i 屬于 A，如果 ，表示節(jié)點 i 屬于 中。將求 Ncut 最小1i ?i A值問題轉化為如下形式： (33)()min()inTyDWNcutx?其中 且 ， ，以上表達式形(){1,}yib??0TyDl?20i iiiYdbxx????式是瑞利商數(shù)。為了求解 的值，Normalized Cut 方法將計算最小值問(,)tAB題轉換為對矩陣特征值和特征向量的求解問題。如果把 y 的取值放寬到實數(shù)，那么最小化 Normalized Cut 相當于求廣義特征值系統(tǒng)下的方程： (34)()DWy???我們令 ，且因為 ，所以滿足 ，將上12zy?0i iTiildbx???0TyDl?式轉化為標準特征值系統(tǒng)方程為： (35)1122()Dz????求解特征值 0 所對應的特征向量為 ，由于 拉普拉斯矩陣，12l0()DW?可以得到 為對稱半正定矩陣，因此 為正交特征向量中最小的1122()DW?? 0z特征向量，我們用 表示第二小特征向量并且與 正交。我們再回到廣義特征1z值系統(tǒng)，其中 為廣義系統(tǒng)中的最小特征值 0 對應的特征向量，又因為0yl?與 正交且 ，所以建立如下等式：0z100iiTxxdb????? (36)1TzyDl第 3 章 基于 CMRM 的圖像標注改進算法 21 其中 則為廣義特征值系統(tǒng)中第二小特征向量?，F(xiàn)在引入瑞利商數(shù)的定義：1y設 A 為實對稱矩陣，如果 x 正交于最小的 個特征向量 ，那么商數(shù)1j?1,jx??將在第二小特征值所對應的特征向量處取得最小值。因此我們可以得到：Tx (37)011221 ()?? (38)?廣義特征值系統(tǒng)的第二小特征向量便是我們所要求得的最小歸一化分割值。因此，實現(xiàn) Normalized Cut 圖像分割算法可總結為如下四個步驟：(1) 給定一幅圖像 I，建立一個加權圖 ，圖像的每一個像素映射為(,)GVE?一個節(jié)點，N 為節(jié)點的個數(shù)。并構建一個對稱相似矩陣 W，設定邊的權值函數(shù) ，用來度量像素間的相似度()Fi (39)2 22|j||()|expexp)xIij Xijw??????(2) 是節(jié)點 的空間分布，也就是圖像 像素的坐標， 是特征矢量；()i I()Fi(3) 是從節(jié)點 i 到其他所有節(jié)點的連接權值。構建一個 對1,nijjdi???N?角矩陣 ；D(4) 求解特征方程 的第二小特征向量；()WyD???(5) 利用具有第二最小特征值的特征向量將圖像一分為二；對所分割的部分判斷是否需要再細分，如有需要則遞歸的調用 Normalized Cut 方法對圖像進行再分割。Normalized Cut 圖像分割算法能夠取得不錯的圖像分割效果。但同時該分割算法是一個 NPhard 問題 [44][45]。一方面，當圖像中像素較多時，矩陣的規(guī)模將會很大，求解大規(guī)模矩陣特征向量的計算復雜度將會大大增加，圖像的分割速度將會很慢；另一方面對于背景復雜的圖像分割效果不夠理想。所以，本文提出基于普擴散理論的圖像分割算法來輔助 CMRM 標注方法中采用的Normalized Cut 分割算法。 基于普擴散理論的圖像分割改進算法目前針對 Normalized Cuts 算法所存在的問題進行的改進主要包括以下兩個方面：一方面是針對映射成圖的節(jié)點個數(shù)較多的情況，可以不按照每個像素點映北京工業(yè)大學工學碩士學位論文 22 射成為圖的節(jié)點的規(guī)則。而是先將原圖像中的像素按照一定大小進行劃分，然后將劃分后的區(qū)域映射為節(jié)點，這樣好處是可以大大減少生成的映射節(jié)點的個數(shù)。實現(xiàn)簡單，但是限制比較大，區(qū)域分割多大影響分割準確性。以 256*256大小的圖像為例，計算規(guī)模如表 31 所示：表 31 Normalized Cuts 和基于區(qū)域劃分的分割方法計算規(guī)模另一方面是將 Normalized Cuts 方法與其他圖像分割方法相結合：先用一些圖像分割方法對圖像進行預處理，再用 Normalized Cuts 方法對結果進行進一步分割，其實這種方法也是使得 Normalizd Cuts 分割方法給予區(qū)域而不是基于單個像素點，從而降低問題的求解規(guī)模。例如有人提出把分水嶺算法與Normalized Cuts 相結合，利用分水嶺算飯對局部信息的搜索，以及 Normalized Cuts 對全局信息的把握。分水嶺算法本質上是將一張圖像看做為一個地形，假設雨水順著地形下流，最終形成分割開的區(qū)域，其分割界限界限即為分水嶺線。圖 34 分水嶺分割算法模擬演示首先，通過一個類似于淹沒的處理方式取出梯度圖像的弱邊界，這樣有利于減少過度分割。其次模擬雨滴在地表下落的過程，使得每一個像素與其梯度下降最快方向上的像素結合。然后，給保留下來的每一個邊緣標記不同標記，于是就形成被邊緣包圍的區(qū)域。最后將前面生成的圖像區(qū)域作為輸入，利用Normalized Cuts 的求解步驟對區(qū)域區(qū)域進行分割。還比如雙閾值分割法與Normalized Cuts 相結合，先求出圖像的兩個閾值，將灰度值小于低閾值的像素視為一個節(jié)點，將灰度值大于高閾值的像素視為一個節(jié)點，然后再建立相似度Normalized Cuts 區(qū)域劃分（4*4）圖像節(jié)點數(shù) 65536 4096相似度矩陣 4294967296 16777216第 3 章 基于 CMRM 的圖像標注改進算法 23 矩陣。當我們分割復雜圖像的時候，單單依靠歸一化分割算法去尋找最小分割值不僅效率很低，而且由于分割區(qū)域數(shù)量是固定的，所以容易產(chǎn)生很多沒有意義的分割區(qū)域，影響后續(xù)的圖像標注精度。我們希望在分割圖像的時候，能夠更有針對性地趨向于分割我們感興趣的區(qū)域。在 Normalized Cut 分割算法中通過尋找一幅圖像的最小分割值將圖像分割成兩部分。而在改進算法中，我們通過人工輸入標記點的方法引入先驗概率信息，感興趣區(qū)域通過標記點集合 T 來構造，然后在標記點構造出的感興趣區(qū)域附近尋找最小分割值 。這樣我(,)cutsS們所求的 不僅僅是歸一化局部最小分割值，而且還要通過 與感(,)cutsS V?興趣區(qū)域建立相關性。我引入譜擴散理論來求得這樣一個分割值，首先我們對 Normalized Cut 特征值系統(tǒng)方程為 進行一下變形，其中 為歸1122()DWz????1122()DW??一化拉普拉斯矩陣，我們用 表示，同時設 為 的特征向量。 為權G?iuG?G?重對角矩陣， 為權重對稱矩陣， 為拉普拉斯矩陣，我們用 表GA?()?L示。那么根據(jù)特征值與特征向量之間的關系可以求出 的的對應特征向量為L，那么原方程轉化為12iGivDu?? (310)GiiiLvD??譜擴散理論：如果存在一個連通圖并且 滿足 ，相關系TV?2()0TiSivd?數(shù) 。那么根據(jù)普擴散理論可以知道，在 T 附近存在一個最小歸一化分10??割的最優(yōu)解 ， ，其中 。其中 是節(jié)x?21nTiGicuS?????2(,)G?????TS點子集合 T 一個指示向量，如果 ， ，如果i 1()()()Tvolivol??， ，把兩種情況進行合并為 。i?GAW?() )()()(TTT llSiGl??我們可以從中看出該理論是將特征矢量和特征矢量的權值相結合，而且與 成反比。這就使得與我們輸入的標注節(jié)點子集合 T 相關性大的TiuDSi???特征向量權值也增加,其中 ?；谧V擴散圖像分割具體步驟：avg??????1 給定一幅圖像 ，建立一個加權圖 ，圖像的每一個像素映射I(,)VE?為一個節(jié)點， 為節(jié)點的個數(shù)。設定邊的權值函數(shù) ；Nw2 構建權重對稱相似矩陣 以及對角矩陣 ；(,)(,)GAijwij?(,)(,)jGDii??北京工業(yè)大學工學碩士學位論文 24 3 構建拉普拉斯矩陣 ，對其進行歸一化 ；GGLDA??12GGDL???4 計算 的 k 個最小特征值 所對應的特征向量 ；G?12,ku? 1,k??5 計算最小歸一化分割值 。*iTnixcuS???? 圖像分割實驗結果對比在實驗中，我們使用 Corel 圖像庫中的六幅圖像分別對 Normalized Cut 圖像分割算法、基于譜擴散理論的 Normalized Cut 算法進行測試，并給出兩種方法得到的圖像分割效果及分割效率實驗結果： 原始圖像第 3 章 基于 CMRM 的圖像標注改進算法 25 NCut 圖像分割結果 參考標注點 基于普擴散理論分割結果圖 35 兩種分割方法效果對比從上述結果可以看出，對一