基于圖論的圖像分割技術探討

湯龍

摘要：數字圖像處理技術的發展歷史并不算久，卻是一種極具挑戰性的跨學科技術，不但涉及美學和物理學的基礎知識，更需要計算機的算法作為技術支持。在信息化網絡時代，各行各業的管理運作都離不開計算機技術。其中，對圖像數據的處理和分析技術更是許多工作崗位上計算機實務操作的根本原理所在。其中，圖像分割技術歷來是圖像分割處理中的技術難點。該文將專門針對基于圖論的圖像分割技術來進行探討與研究。

關鍵詞：圖論；圖像分割；邊緣識別

中圖分類號：TP302 文獻標識碼：A 文章編號：1009-3044（2016）12-0197-02

圖像分割（Image Segmentation）是根據圖形的灰度、顏色、紋理和形狀等不同指標來進行信息分組，將同一指標中特征相似的歸為一類，繼而不同類別的較大差異來分割圖像。

1 圖像分割的傳統方法歸納

1）邊緣檢測分割法

邊緣檢測是最基本的圖像分割技術，顧名思義，即通過智能測算，來確定圖像的邊緣，并進行分割。首先識別出圖像中的邊緣點，然后以閉合曲線連結錨點，選出分割區域。

從色彩學的基本原理上看，圖像的邊緣，通常是灰度、色相或紋理等特性發生驟變的地方。因此，對于圖像邊緣的識別，主要是依賴算法對上述特征的界定。邊緣檢測算法種類繁多，且各有優缺點。其中，智能識別邏輯含義簡單，邊緣灰度變化明顯，且噪點不多的簡單圖像。而對一些題材超現實，或是色彩和明度變化微妙，又或者噪點過多的圖像，執行這一簡單的算法就無法正確地識別邊緣。即使反復操作，效果也不好：一來噪點過多，與圖像本身的邊緣區分不開，二來降低噪點又必然折損原圖的結構紋理，更容易誤導邊緣識別。

2）閾值分割法

閾值分割則也是傳統的分割技術之一，分割原理很容易理解，即利用圖像中目標區域與背景區域之間的最大灰度差來識別不同物體之間的邊界，此時便將相同物體上灰度的相對均勻作為分割依據。閾值分割通過一個或幾個閾值將圖像劃分出幾個不同區域。

閾值圖像分割法的基本原理是根據直方圖的像素分布來指定恰當的閾值，該方法也有局限性：只能對動態范圍廣，即像素分布均勻的圖像進行精確分割。如果圖像的直方圖向左或向右傾斜過多（即像素集中分布在高亮部或暗部），實際區域劃分就會出現嚴重的誤差。

3）聚類分析分割法

聚類分析法的誕生，是圖形分割由單一算法走向多元統計的標志。所謂的聚類分析，指的是根據圖形數據的內部結構來劃分類別，從而實現更智能化，成功率更高的邊緣識別。

聚類分析有兩種，一種是硬聚類，還有一種是模糊聚類分析法，一般前者比較常用，其基本工作原理是在非同一類別的函數中，將隸屬度取值為0或1，換言之單個樣本只可屬于單一類別。

模糊聚類則是在一種無監督的聚類方法，它是在樣本點的正態分布區間中根據隸屬度取值，如此一來，各個樣本點對聚類都呈現出一種隸屬關系。模糊聚類法是圖像邊緣不確定性的典型表征。因此在運用上硬聚類分割法更為繁瑣，目前多用于醫學圖像處理中。

而可能性聚類則不同于上述方法，它不僅要顧及到樣本與聚類中心的隸屬關系，還要兼顧樣本對分類結果的影響。傳統聚類算法不能覆蓋到圖像的空間性，所以對局部強噪點和灰度變化大的圖形解讀能力較差。為了優化模糊聚類算法在圖像分割中的效果，來自歐美頂尖實驗室的技術人員優先提出了迭代優化法，該算法可以從三維視角識別圖像的空間信息，算得上是最前沿的新型算法。

4）活動輪廓圖像分割法

活動輪廓分割法最初誕生于上世紀九十年代初，主要是指在圖像的閾值曲線或者曲面幾何特性和數據的共同作用下，以最小化能量函數的形式向邊界運動。這一方法從提出至今，已經過二十余年時間，活動輪廓建模理念已經在邊緣檢測、圖像分割領域取得了可喜的實驗結果，通過技術人員在算法上的優化與改進，最終使得圓滑輪廓曲線最大限度地切合目標物體的凹陷邊緣，因此在很大程度上解決了參數活動輪廓方法易于陷入局部能量區域這一技術障礙。

2 基于圖論的圖像分割法

2.1 以圖論為導向的研究方向

基于圖論的圖像分割技術是近年來圖像分割領域中引起廣泛關注的研究熱點，它的基本思想并不復雜：即通過圖像映射轉化為無向圖，在圖像邊緣界定錨點，令各個錨點之間邊的權重分別對應不同像素之間的不相似度，從而計算出割的容量。截至目前，基于圖論的圖像分割方法的研究主要集中在以下幾個方面：

1）最優切割準則設計原則；2）譜方法分割原則；3）快速算法。

基于圖論的分割方法，從本質上講，是將圖像分割問題轉化為特征識別問題，即轉化為聚類方法。、而最優分割原則是指通過劃分兩個子圖，取內部相似度最大值來作為界定圖像邊緣的參考。圖割算法中割集準則的選取對最終分割結果有直接影響，使用頻率較高的割集準則有最小割（Minimum cut）、平均割（Average cut）大小分流割（Max-minimum Cut）等。

2.2 割集選擇的基本原理

1）圖形最優分割

圖論算法在計算機應用技術中扮演著很重要的角色，該方法靈活度很高，可以解決很多問題。遺傳算法是解優化問題的有效算法，而并行遺傳算法是遺傳算法研究中的一個重要方向，受到了研究人員的高度重視。此類方法把圖像分割問題與圖的最小割（min cut）問題相關聯。首先將圖像映射為帶權無向圖G=，圖中每個節點N∈V對應于圖像中的每個像素，每條邊∈E都連接一對相鄰像素，邊的權值意味著相鄰像素之間在灰度、色度和紋理方面的非負相似度。而對圖像的分割就是對圖以某種指標為準進行裁切，被裁切出的每個區域C∈S分別對應了圖中一個子圖。

因此，分割的最優原則意味著劃分后的子圖在內部保持最大相似度，而子圖之間則保持最小相似度?；趫D論的分割方法的根本原理就是移除特定的邊，將圖劃分為若干子圖從而實現分割。目前所了解到的基于圖論的方法有智能圖形分割（GraphCut）和權函數運算等。

2）權函數運算

權函數一般定義為兩個節點之間的相似度，也就是在數據統計中計算出平均數等指標，然后對各個變量值權衡大小，所以顧名思義地被稱為“權函數”。在權函數運算中，對于灰度圖像，一般用F表示像素的灰度值，X表示像素的空間坐標，Y為灰度高斯函數的標準方差（用于測算出兩像素之間的有效距離）。一旦超過這一距離，則認為兩像素之間的相似度較大；反之兩像素之間的距離越小，則認為相似度越大。

3）圖形相似度矩陣

圖論分割算法常把最優割集準則轉化相似度矩陣以便求解。相似度常用字母W和A表示。相似度矩陣又稱親和力矩陣，運算原理是將原圖像中的像素重新排布。在相似度矩陣中，所有相鄰像素的相似度都可以通過函數運算得到。將相似度矩陣的每行元素相加，即得到該節點的度，以所有度值為對角元素構成的對角矩陣即為度矩陣，度矩陣常用字母D表示。令低量算符矩陣為L=D-W，則在圖論分割算法中低量算符矩陣為最常用的標準矩陣。

3 圖論分割方法的應用

1）臨床醫學圖像分割

圖論圖像分在醫學領域可以用于腦心電圖，以及脊椎骨核磁共振，即在區域生長和模糊連接度的基礎上結合各向異性濾波和邊緣檢測算子檢測邊緣，繼而從圖像中劃分出目標選區，為外科手術方案提供參考。同時，此項技術也可以患者腫瘤切片的深度分割，為醫學工作者診斷病情，確定治療方案提供了有效的數據參考。最新的研究方向表明，圖像分割技術還有可能被用于重建細胞全息圖，為醫學人員攻克免疫方面的病癥提供了更深入的數據分析，其潛在應用價值不可估量。

2）紋理分割

紋理分割（Texture Segmention ）對后續圖像的其他算法處理非常重要，對分割算法的掌握對于后續算法，比如目標跟蹤，人臉識別等等，都是非常重要的?？蓪ormalize Cut準則用于圖像中的邊緣與紋理質地測算識別，即將圖像信息分為干涉基元和紋理基元，并將兩種信息進行數據合并。同時，Normalize Cut準則還具有較好的兼容度，對于將明度信息與紋理信息數據整合的分割方式也適用。

3）智能圖形分割

智能圖形分割（Graph cuts）最先由國外的技術人員研發，近年來開始在國內廣為流傳，因其智能度高，操作易上手，因而受到了廣大商業運作機構的追捧，被廣泛應用在UI設計，商業攝影后期制作等領域。智能圖形分割的基本原理就是將圖像分割問題與圖的最小割（min cut）準則實行聯合運算，使圖像在保持較小容差值的情況下，依然可以大刀闊斧地進行輪廓識別，而不會被材質紋理造成的明暗變化所誤導?；谶@種基本原理，智能圖形分割也難免存在局限性，即它只適合邏輯簡單清晰地圖形。盡管如此，它仍然可以勝任相當多的行業操作終端對于圖像分割的需求。即使在操作中偶爾出現識別錯誤，通過若干次的容差值修改，最終也不難得到一個相對精確的圖形分割方案。

4 結論

在前文中，作者首先總結了目前常用的集中圖像分割技術，然后對基于圖論的圖形分割技術做出了詳細的分類探討。對圖像分割算法的研究歷史至今已有幾十年，基于各種理論至今已開發出了千余種分割算法。目前，圖像分割方法發展勢頭良好，正朝著更迅速、更精確、更智能的方向發展，通過研究新理論，引進國外先進技術，這一領域在不久的未來勢將取得更大的突破和進展。

參考文獻：

[1] 侯葉.基于圖論的圖像分割技術研究[D].西安電子科技大學，2011.

[2] 羅青青.基于圖論的圖像分割技術研究[D].南京郵電大學，2014.

[3] 賀錦鵬.基于圖論的彩色紋理圖像分割技術研究[D].哈爾濱工程大學，2011.

[4] 鄭倩.醫學圖像分割方法研究及其應用[D].南方醫科大學，2014.

[5] 董昌灝.基于圖論的交互式PCB圖像分割技術研究[D].解放軍信息工程大學，2013.

[6] 胡學剛，孫慧芬，王順.一種新的基于圖論的圖像分割算法[J].四川大學學報：工程科學版，2010（1）：138-142.