基于圖譜理論的圖像分割

翟永磊 田道坤

（中國人民解放軍91604 部隊，山東 龍口265700）

0 引言

圖像分割就是將圖像表示為物理上有意義的連通區(qū)域的集合。人們一般是通過對圖像的不同特征如邊緣、紋理、顏色、亮度等的分析達到圖像分割的目的。 圖像分割通常是為了進一步對圖像進行分析、識別、跟蹤、理解、壓縮編碼等，分割的準確性直接影響后續(xù)任務的有效性，因此具有十分重要的意義。

1 圖像分割

1.1 圖像分割的一般模型

圖像分割是依據(jù)圖像的灰度、顏色或幾何性質將圖像中具有的特殊含義的不同區(qū)域區(qū)分開來，這些區(qū)域是互不相交的，每一個區(qū)域都滿足特定區(qū)域的一致性。 比如對同一物體的圖像，一般需要將圖像中屬于該物體的像素（或物體的特征像素點）從背景中分割出來，將屬于不同物體的像素點分離開。 分割出來的區(qū)域應該同時滿足：

1.1.1 分割出來的圖像區(qū)域的均勻性和連通性。 其中，均勻性指的是該區(qū)域中的所有像素點都滿足基于灰度、紋理、彩色等特征的某種相似性準則，連通性是指該區(qū)域內存在連接任意兩點的路徑。

1.1.2 相鄰分割區(qū)域之間針對選定的某種差異顯著性。

1.1.3 分割區(qū)域邊界應該規(guī)整，同時保證邊緣的空間定位精度。

1.2 基于閾值選取的圖像分割方法

基于閾值選取的圖像分割方法是提取目標物體與背景在灰度上的差異， 把圖像分為具有不同灰度級的目標區(qū)域和背景區(qū)域的組合。閾值法對物體和背景對比較強的景物分割有著很強的優(yōu)勢，計算較為簡單，并且可以用封閉和連通的邊界定義不交疊的區(qū)域，是圖像分割中最有效且實用的技術之一。根據(jù)獲取最優(yōu)分割閾值的途徑可以把閾值法分為全局閾值法、動態(tài)閾值法、模糊閾值法和隨機閾值法等。盡管閾值選取的方法很多，但至今還沒有找到一種對所有圖像都可以有效分割的方法，一種閾值方法只能適用于某一類或某幾類圖像，因此一些學者在研究新的閾值選取方法之外，同時將新的數(shù)學工具融合到原有的閾值方法中，并取得了較好的分割效果。

2 一種新的基于圖譜理論的圖像閾值分割方法

基于圖譜劃分的圖像分割方法通常具有較高的復雜性，實時性較差，因而在很多實時視覺處理場合無法采用。 采用一種基于圖譜劃分的閾值分割方法，采用圖譜劃分測度作為閾值分割的準則來區(qū)分目標和背景。 與現(xiàn)有的基于圖譜劃分的圖像分割方法類似，我們仍將圖像中的每個像素看作一個節(jié)點，而連接每兩個節(jié)點的權值反映了這兩個像素屬于同一類的可能性。不同之處在于我們采用基于圖像灰度級的對稱矩M（其大小為256×256）來描述圖像中各部分之間的關系，而不是采用一般的N×N （其中N 為圖中節(jié)點的個數(shù)） 的對稱的相似矩陣W。 算法的基本思想是：對每一個可能門限t，利用矩陣M 可快速地計算其對應的圖譜劃分值，其最小的圖譜劃分值對應的門限即為分割圖像的最佳閾值。采用這種方法的一個最大的優(yōu)點是避免了復雜的特征系統(tǒng)求解問題，因而極大減少了算法所需的存儲空間以及計算的復雜度，大大提高了算法的實時性能。比較實驗還表明，這種基于圖譜劃分的閾值分割方法的性能優(yōu)于其他類型的閾值分割方法；同時針對一些適合于閾值分割的具有明顯目標和背景的實際圖像，這種方法較之通常用特征系統(tǒng)求閾值的方法更為有效。

3 實現(xiàn)過程

基于圖譜理論新的閾值分割算法我采用matlab 語言加以實現(xiàn)，同樣是采用Ncut 算法。 這種基于圖譜理論新的閾值分割算法的實現(xiàn)流程圖如圖3-1。

首先讀取圖像，把圖像轉化成灰度值矩陣。 然后檢測圖像是否是彩色圖像，如果是彩色圖像就把它轉化成灰度圖像處理，如果是灰度圖像就直接繼續(xù)下一步。

在這里如果圖像尺度很大時，將會嚴重影響程序運行速度，所以我在這里加入了調整圖像大小的語句， 主要目的在于減少運算量，提高運算速度。 如果圖像較小時這條語句就可以省略了。 顯示原始圖像如圖3-2。

轉化數(shù)據(jù)類型，接著就是對以下公式：

中的參數(shù)加以設置，這里dI設置為625，dX設置為4，r 設置為2。

圖3-1 算法流程圖

下一步是通過計算圖中所有節(jié)點間的權值就可以構建基于灰度級的權值矩陣M。 運用M 矩陣的上三角形部分，分區(qū)求出每一個門限t 對應的cut（A，B），asso（A，A）和asso（B，B）的值，進而求出這個門限對應的Ncut（A，B）值。 畫出Ncut（A，B）的曲線變化圖，如圖3-3。

圖3-2 原始圖像

圖3-3 Ncut（A，B）的曲線變化圖

根據(jù)Ncut（A，B）的曲線變化圖，計算出最小Ncut（A，B）值對應的門限t 的值，此值即為我們要找的最佳分割閾值T，本文所采用的圖像的分割閾值為77。

然后用求得的閾值T 對圖像進行分割，將原圖像中灰度值大于T的都賦值為0,顯示分割的結果；將灰度值小于T 的都賦值為0，顯示分割結果。

以下就是分割結果，把人物和背景成功地分離開來，如圖3-4。

圖3-4 圖像分割結果

4 結論

基于圖譜分組理論的圖像分割方法通過將圖像看作一個無向帶權圖，圖像中的像素看作圖的節(jié)點，構建節(jié)點鄰接權值矩陣，進而采用求解特征系統(tǒng)的方法來尋求圖譜劃分測度的最優(yōu)解， 并利用其相應的特征矢量對圖中節(jié)點進行分類。 這類方法雖然效果較好，但是其巨大的計算復雜度使得該方法很難在很多實時應用場合使用， 如自動目標識別(ATR)等。 本文采用的基于圖譜劃分測度的閾值分割方法則有效克服了這一計算瓶頸問題。 選用圖譜劃分測度作為閾值分割的準則，構建基于灰度級的鄰接權值矩陣， 通過查詢權值矩陣即可快速得到每個閾值t（0≤t≤255）對應的Ncut 值，進而采用最小Ncut 值對應的門限對圖像進行閾值分割。 理論分析及實驗結果均表明，本方法極大地縮減了算法所需的存儲空間及運算時間，能夠有效地應用于實時視覺場合。 對比實驗結果還表明：與文獻中其他典型的圖像分割方法相比，本文提出的基于圖譜劃分的閾值分割方法具有更好的分割性能，且魯棒性較好。

［1］李弼程，彭天強，彭波.智能圖像處理技術[M].北京：電子工業(yè)出版社，2004:589-651.

［2］Z Wu,R Leahy.An optimal graph theoretic approach to data clustering:Theory and its application to image segmentation[J].IEEE.Trans on PAMI,1993:1101-1113.

［3］卜月華.圖論及其應用[M].南京：東南大學出版社，2002:1-28.

［4］王樹禾.圖論[M].北京：科學出版社，2004:1-5.