基于圖論的圖像分割技術(shù)探討

湯龍

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

關(guān)鍵詞：圖論；圖像分割；邊緣識(shí)別

中圖分類號(hào)：TP302 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）12-0197-02

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

1 圖像分割的傳統(tǒng)方法歸納

1）邊緣檢測(cè)分割法

邊緣檢測(cè)是最基本的圖像分割技術(shù)，顧名思義，即通過智能測(cè)算，來確定圖像的邊緣，并進(jìn)行分割。首先識(shí)別出圖像中的邊緣點(diǎn)，然后以閉合曲線連結(jié)錨點(diǎn)，選出分割區(qū)域。

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

2）閾值分割法

閾值分割則也是傳統(tǒng)的分割技術(shù)之一，分割原理很容易理解，即利用圖像中目標(biāo)區(qū)域與背景區(qū)域之間的最大灰度差來識(shí)別不同物體之間的邊界，此時(shí)便將相同物體上灰度的相對(duì)均勻作為分割依據(jù)。閾值分割通過一個(gè)或幾個(gè)閾值將圖像劃分出幾個(gè)不同區(qū)域。

閾值圖像分割法的基本原理是根據(jù)直方圖的像素分布來指定恰當(dāng)?shù)拈撝担摲椒ㄒ灿芯窒扌裕褐荒軐?duì)動(dòng)態(tài)范圍廣，即像素分布均勻的圖像進(jìn)行精確分割。如果圖像的直方圖向左或向右傾斜過多（即像素集中分布在高亮部或暗部），實(shí)際區(qū)域劃分就會(huì)出現(xiàn)嚴(yán)重的誤差。

3）聚類分析分割法

聚類分析法的誕生，是圖形分割由單一算法走向多元統(tǒng)計(jì)的標(biāo)志。所謂的聚類分析，指的是根據(jù)圖形數(shù)據(jù)的內(nèi)部結(jié)構(gòu)來劃分類別，從而實(shí)現(xiàn)更智能化，成功率更高的邊緣識(shí)別。

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

模糊聚類則是在一種無監(jiān)督的聚類方法，它是在樣本點(diǎn)的正態(tài)分布區(qū)間中根據(jù)隸屬度取值，如此一來，各個(gè)樣本點(diǎn)對(duì)聚類都呈現(xiàn)出一種隸屬關(guān)系。模糊聚類法是圖像邊緣不確定性的典型表征。因此在運(yùn)用上硬聚類分割法更為繁瑣，目前多用于醫(yī)學(xué)圖像處理中。

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

4）活動(dòng)輪廓圖像分割法

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

2 基于圖論的圖像分割法

2.1 以圖論為導(dǎo)向的研究方向

基于圖論的圖像分割技術(shù)是近年來圖像分割領(lǐng)域中引起廣泛關(guān)注的研究熱點(diǎn)，它的基本思想并不復(fù)雜：即通過圖像映射轉(zhuǎn)化為無向圖，在圖像邊緣界定錨點(diǎn)，令各個(gè)錨點(diǎn)之間邊的權(quán)重分別對(duì)應(yīng)不同像素之間的不相似度，從而計(jì)算出割的容量。截至目前，基于圖論的圖像分割方法的研究主要集中在以下幾個(gè)方面：

1）最優(yōu)切割準(zhǔn)則設(shè)計(jì)原則；2）譜方法分割原則；3）快速算法。

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

2.2 割集選擇的基本原理

1）圖形最優(yōu)分割

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

因此，分割的最優(yōu)原則意味著劃分后的子圖在內(nèi)部保持最大相似度，而子圖之間則保持最小相似度。基于圖論的分割方法的根本原理就是移除特定的邊，將圖劃分為若干子圖從而實(shí)現(xiàn)分割。目前所了解到的基于圖論的方法有智能圖形分割（GraphCut）和權(quán)函數(shù)運(yùn)算等。

2）權(quán)函數(shù)運(yùn)算

權(quán)函數(shù)一般定義為兩個(gè)節(jié)點(diǎn)之間的相似度，也就是在數(shù)據(jù)統(tǒng)計(jì)中計(jì)算出平均數(shù)等指標(biāo)，然后對(duì)各個(gè)變量值權(quán)衡大小，所以顧名思義地被稱為“權(quán)函數(shù)”。在權(quán)函數(shù)運(yùn)算中，對(duì)于灰度圖像，一般用F表示像素的灰度值，X表示像素的空間坐標(biāo)，Y為灰度高斯函數(shù)的標(biāo)準(zhǔn)方差（用于測(cè)算出兩像素之間的有效距離）。一旦超過這一距離，則認(rèn)為兩像素之間的相似度較大；反之兩像素之間的距離越小，則認(rèn)為相似度越大。

3）圖形相似度矩陣

圖論分割算法常把最優(yōu)割集準(zhǔn)則轉(zhuǎn)化相似度矩陣以便求解。相似度常用字母W和A表示。相似度矩陣又稱親和力矩陣，運(yùn)算原理是將原圖像中的像素重新排布。在相似度矩陣中，所有相鄰像素的相似度都可以通過函數(shù)運(yùn)算得到。將相似度矩陣的每行元素相加，即得到該節(jié)點(diǎn)的度，以所有度值為對(duì)角元素構(gòu)成的對(duì)角矩陣即為度矩陣，度矩陣常用字母D表示。令低量算符矩陣為L(zhǎng)=D-W，則在圖論分割算法中低量算符矩陣為最常用的標(biāo)準(zhǔn)矩陣。

3 圖論分割方法的應(yīng)用

1）臨床醫(yī)學(xué)圖像分割

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

2）紋理分割

紋理分割（Texture Segmention ）對(duì)后續(xù)圖像的其他算法處理非常重要，對(duì)分割算法的掌握對(duì)于后續(xù)算法，比如目標(biāo)跟蹤，人臉識(shí)別等等，都是非常重要的。可將Normalize Cut準(zhǔn)則用于圖像中的邊緣與紋理質(zhì)地測(cè)算識(shí)別，即將圖像信息分為干涉基元和紋理基元，并將兩種信息進(jìn)行數(shù)據(jù)合并。同時(shí)，Normalize Cut準(zhǔn)則還具有較好的兼容度，對(duì)于將明度信息與紋理信息數(shù)據(jù)整合的分割方式也適用。

3）智能圖形分割

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

4 結(jié)論

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

參考文獻(xiàn)：

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

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

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

[4] 鄭倩.醫(yī)學(xué)圖像分割方法研究及其應(yīng)用[D].南方醫(yī)科大學(xué)，2014.

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

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