趙 婕，謝 剛

（1．太原理工大學(xué)信息工程學(xué)院，山西太原030024；2．太原大學(xué)計(jì)算機(jī)工程系，山西太原030032）

圖像區(qū)域分割中的無(wú)監(jiān)督圖割方法

趙 婕1，2，謝 剛1

（1．太原理工大學(xué)信息工程學(xué)院，山西太原030024；2．太原大學(xué)計(jì)算機(jī)工程系，山西太原030032）

提出一種基于圖割算法的圖像多區(qū)域分割方法，該方法采用核函數(shù)對(duì)數(shù)據(jù)項(xiàng)進(jìn)行隱性的非線性映射，將原始數(shù)據(jù)映射到高維特征空間，實(shí)現(xiàn)圖像的線性多類劃分，擴(kuò)展了分段常數(shù)模型的應(yīng)用范圍，提高了復(fù)雜區(qū)域的分割效果。由于圖像邊緣梯度變化劇烈，具有不連續(xù)性，在平滑項(xiàng)中加入圖像的梯度約束條件，減少過(guò)分割。同時(shí)，采用無(wú)監(jiān)督方法設(shè)置初始參數(shù)，避免了交互操作，更符合多區(qū)域分割的要求。實(shí)驗(yàn)結(jié)果表明，新方法不受圖像內(nèi)容的限制，無(wú)論是主觀視覺(jué)判斷還是客觀定量分析，該方法都具有較好的分割效果。

區(qū)域分割；圖割算法；核方法；邊緣梯度

0 引 言

圖像在人眼中是由不同目標(biāo)、不同區(qū)域聯(lián)合構(gòu)成，人們通過(guò)辨識(shí)圖像中包含的各個(gè)目標(biāo)，可以快速、準(zhǔn)確地理解其所包含的信息。但是對(duì)于計(jì)算機(jī)而言，這個(gè)過(guò)程極具挑戰(zhàn)性。圖像分割就是幫助計(jì)算機(jī)像人眼一樣，實(shí)現(xiàn)目標(biāo)提取與識(shí)別、圖像理解以及場(chǎng)景恢復(fù)等功能的前期環(huán)節(jié)，是圖像分析與理解的基礎(chǔ)技術(shù)［1］。圖像分割一直以來(lái)是計(jì)算機(jī)視覺(jué)領(lǐng)域的研究熱點(diǎn)，而圖像的多區(qū)域分割是圖像分割中最為關(guān)注的研究方向，廣大研究者努力尋找更準(zhǔn)確、更高效的多區(qū)域分割方法。由于能量函數(shù)模型具有統(tǒng)一的分割框架以及可以使用標(biāo)準(zhǔn)優(yōu)化方法求解的優(yōu)點(diǎn)，并且通過(guò)貝葉斯統(tǒng)計(jì)可以證明將圖像分割問(wèn)題轉(zhuǎn)換為求解能量函數(shù)最優(yōu)解的正確性，能量?jī)?yōu)化方法成為研究圖像分割的一個(gè)新流派［2－3］。

圖割算法是一種以圖論為理論基礎(chǔ)的優(yōu)化方法，可用于優(yōu)化能量函數(shù)全局解，而圖像中的像素點(diǎn)又可以與網(wǎng)絡(luò)圖的節(jié)點(diǎn)對(duì)應(yīng)，圖論的相關(guān)理論與方法適用于圖像分析與處理領(lǐng)域的研究。因此，圖割算法成為近年來(lái)廣大學(xué)者研究圖像分割的重要方法。2000年，加拿大西安大略大學(xué)Boykov等人［4］首次將圖割算法引入圖像分割領(lǐng)域，經(jīng)過(guò)數(shù)學(xué)證明驗(yàn)證了求解離散能量函數(shù)的全局最優(yōu)解與圖像的目標(biāo)分割過(guò)程等效，并且使用交互式方法，通過(guò)求解能量函數(shù)最優(yōu)解在實(shí)際應(yīng)用中實(shí)現(xiàn)了目標(biāo)與背景的分割。但是，當(dāng)能量函數(shù)是非凸函數(shù)時(shí)，無(wú)法精確獲得全局最優(yōu)解。2002年，美國(guó)康奈爾大學(xué)Kolmogorov等人［5］提出一種求解具有較強(qiáng)約束的局部最優(yōu)解的圖割算法，用特定的局部最優(yōu)解替代全局最優(yōu)解，實(shí)驗(yàn)證明了該算法的有效性，并成功地應(yīng)用于多鏡頭3D場(chǎng)景重建。經(jīng)典圖割算法適用于灰度圖像，2004年，英國(guó)微軟劍橋研究院Rother等人［6］提出GrabCut算法，用高斯混合模型代替單色直方圖模型，將圖割算法擴(kuò)展到彩色圖像的目標(biāo)分割；同時(shí)，用戶只需提供左上角和右下角兩個(gè)點(diǎn)，便可形成一個(gè)覆蓋目標(biāo)的矩形框，簡(jiǎn)化了交互操作。研究者們還在能量函數(shù)中融入各種先驗(yàn)信息，以提高圖割算法的圖像分割效率。2010年，西安大略大學(xué)Veksler［7］將星形作為通用的目標(biāo)形狀，以先驗(yàn)知識(shí)的形式融入能量函數(shù)的結(jié)構(gòu)中，用戶只需提供目標(biāo)的中心點(diǎn)就可以準(zhǔn)確分割出目標(biāo)，提高了圖像中目標(biāo)的分割效果。在近十幾年中，圖割算法得到了廣大研究者的關(guān)注，針對(duì)算法流程的設(shè)計(jì)與能量函數(shù)的構(gòu)造不斷地提出改進(jìn)方法［8－11］，促進(jìn)了圖像分析與處理研究的發(fā)展與進(jìn)步，尤其是在圖像分割領(lǐng)域。

圖割算法在圖像分割領(lǐng)域的使用范圍主要集中于目標(biāo)分割和交互式操作。這里指的目標(biāo)分割是將圖像中的目標(biāo)從背景中有效地分割出來(lái)，即圖像被分為兩個(gè)區(qū)域（目標(biāo)和背景），屬于二分類。用戶預(yù)先確定一定量的目標(biāo)像素和背景像素，通過(guò)交互式操作完成圖割算法中參數(shù)的初始化設(shè)置。圖割算法在交互式的兩區(qū)域分割研究中已經(jīng)取得了很好的效果［4－11］。但是，由于圖像的復(fù)雜性，實(shí)際圖像都是由多個(gè)區(qū)域組成，如何將圖像有效分割成多個(gè)具有特定性質(zhì)的區(qū)域，更具有實(shí)際應(yīng)用價(jià)值，同時(shí)也更具有挑戰(zhàn)性。圖像的多區(qū)域分割成為圖割算法目前以及未來(lái)研究的重點(diǎn)與難點(diǎn)。對(duì)于圖像的多區(qū)域分割，如果仍然使用交互式操作完成初始化設(shè)置，那么圖像越復(fù)雜，分割的區(qū)域越多，交互式操作也越困難。因此，交互式操作不適合圖像的多區(qū)域分割。

圖割算法應(yīng)用到圖像的多區(qū)域分割時(shí)，當(dāng)分割區(qū)域大于3個(gè)以上，能量函數(shù)的全局優(yōu)化成為NP－h(huán)ard問(wèn)題，通常采用α－擴(kuò)展、α－β交換等近似優(yōu)化方法［12］。能量函數(shù)模型的構(gòu)建是決定圖割算法處理圖像能力的關(guān)鍵因素，針對(duì)近似優(yōu)化方法，研究者們提出一些新的能量函數(shù)模型。文獻(xiàn)［13］提出一種離散能量函數(shù)模型，加入標(biāo)簽懲罰限制使用標(biāo)簽的數(shù)量，通過(guò)能量平衡解決經(jīng)典優(yōu)化問(wèn)題中的無(wú)容量限制的設(shè)施選址問(wèn)題（uncapacitated facility location problem，UFLP），經(jīng)過(guò)實(shí)驗(yàn)驗(yàn)證了該模型的有效性。文獻(xiàn)［14］構(gòu)造了評(píng)價(jià)標(biāo)簽質(zhì)量的多模型能量函數(shù)，包括測(cè)量模型相似程度的相似項(xiàng)和測(cè)量證明模型合理的證據(jù)數(shù)量的模型懲罰項(xiàng)兩部分。采用一種快速的融合移動(dòng)方法實(shí)現(xiàn)多模型能量函數(shù)的優(yōu)化，將融合問(wèn)題變換為最小加權(quán)點(diǎn)覆蓋問(wèn)題，該方法具有近鄰傳播一樣的魯棒性。文獻(xiàn)［15］通過(guò)t－權(quán)重將多個(gè)形狀先驗(yàn)信息引入能量函數(shù)構(gòu)造的圖中，形狀距離是對(duì)稱的，同時(shí)還符合三角不等式定理，采用多階段圖割算法完成有重疊的多目標(biāo)分割。這些能量函數(shù)模型的提出推進(jìn)了圖割算法在多區(qū)域分割中的應(yīng)用，但是仍然存在一些缺點(diǎn)有待改進(jìn)，例如模型復(fù)雜、計(jì)算量大，分割效果與分割區(qū)域的數(shù)量有關(guān)，并且分割區(qū)域的數(shù)量需要人為指定等問(wèn)題。

本文將核方法與邊緣梯度信息有機(jī)融合，提出一種無(wú)監(jiān)督圖割方法。首先，采用常數(shù)模型描述各個(gè)劃分區(qū)域內(nèi)的圖像數(shù)據(jù)，將圖像數(shù)據(jù)映射到高維空間，實(shí)現(xiàn)復(fù)雜圖像數(shù)據(jù)的線性可分，統(tǒng)計(jì)模型簡(jiǎn)單、計(jì)算量小，并且提高了復(fù)雜區(qū)域的分割效果。其次，在多標(biāo)簽分配過(guò)程中，加入梯度約束條件以保持邊緣不連續(xù)性，減少過(guò)分割。最后，參數(shù)初始化設(shè)置避免了交互操作，通過(guò)少量樣本測(cè)試便可以確定合適的參數(shù)值，完成多區(qū)域的自動(dòng)分割。

1 無(wú)監(jiān)督圖割方法的基本步驟

圖像多區(qū)域分割中應(yīng)用圖割算法的核心思想是構(gòu)建一個(gè)能夠體現(xiàn)圖像特征的能量函數(shù)，對(duì)能量函數(shù)的最優(yōu)化求解，完成各個(gè)區(qū)域的標(biāo)簽分配。每一個(gè)分割區(qū)域可以看作一類數(shù)據(jù)，每一類圖像數(shù)據(jù)都有唯一的標(biāo)簽與之對(duì)應(yīng)，通過(guò)解決標(biāo)簽分配問(wèn)題實(shí)現(xiàn)圖像數(shù)據(jù)的空間聚類。無(wú)監(jiān)督圖割方法避免了交互式操作，主要包含有以下3個(gè)基本步驟：

步驟1 構(gòu)造無(wú)監(jiān)督圖割的能量函數(shù)

設(shè)I表示一幅圖像，P為該圖像中所有像素的集合，將圖像I分割為Nseg個(gè)區(qū)域，對(duì)于任意像素p，則存在一個(gè)對(duì)應(yīng)函數(shù)f（p）表示像素點(diǎn)p的分類標(biāo)簽，即

式中，L是標(biāo)簽類別的集合，其基數(shù)小于等于Nseg。標(biāo)簽類別為l（l∈L）的所有像素構(gòu)成一個(gè)劃分區(qū)域Rl，即

通常能量函數(shù)由數(shù)據(jù)約束和平滑約束兩個(gè)特征項(xiàng)之和組成

這兩個(gè)約束項(xiàng)中包含圖像分割所需的圖像特征，其中EData（f）是數(shù)據(jù)約束項(xiàng)，衡量分割區(qū)域中圖像數(shù)據(jù)和統(tǒng)計(jì)模型的一致性程度。采用分段常數(shù)模型［13］（piecewise constant model，PCM）作為統(tǒng)計(jì)模型描述劃分區(qū)域內(nèi)像素的特征。PCM中同一區(qū)域內(nèi)圖像特征近似等同，不同區(qū)域內(nèi)圖像特征差異較大，每個(gè)區(qū)域內(nèi)的像素分配統(tǒng)一的標(biāo)簽，用相同的圖像特征進(jìn)行表示，適用于圖像的多區(qū)域分割，并且計(jì)算量小。

式中，μl為區(qū)域Rl的PCM參數(shù)；Ip表示像素p的圖像特征。

但是，在實(shí)際應(yīng)用中圖像數(shù)據(jù)分布復(fù)雜，而PCM要求圖像數(shù)據(jù)按照線性分布，大大限制了其應(yīng)用范圍。為了擴(kuò)展PCM在實(shí)踐中的應(yīng)用范圍，采用核映射方法［16－18］對(duì)非線性可分的圖像數(shù)據(jù)進(jìn)行隱性的非線性映射，將原始數(shù)據(jù)映射到高維特征空間，實(shí)現(xiàn)線性可分的目的。

ESmooth（f）是平滑約束項(xiàng)，用來(lái)描述分割區(qū)域的光滑程度，融入梯度變化作為約束條件，體現(xiàn)出分割區(qū)域內(nèi)光滑連續(xù)而區(qū)域邊緣不連續(xù)的特性。

式中，λ為比例系數(shù)，用來(lái)調(diào)節(jié)數(shù)據(jù)約束和平滑約束兩個(gè)特征項(xiàng)所占的比重；N表示像素鄰域。

步驟2 構(gòu)建加權(quán)圖

根據(jù)構(gòu)造的能量函數(shù)可以構(gòu)建一個(gè)加權(quán)圖，設(shè)圖G＝〈v，ε〉，其中v是圖中的頂點(diǎn)，包括圖像中的所有像素點(diǎn)p∈P，以及用于表示標(biāo)簽類別的額外端點(diǎn)l∈L。ε是圖中的邊，也相應(yīng)地包括兩部分：相鄰像素點(diǎn)之間的邊和像素點(diǎn)與額外端點(diǎn)之間的邊。邊的權(quán)重如表1所示。

表1 邊的權(quán)重分配

步驟3 基于圖割的近似優(yōu)化實(shí)現(xiàn)多區(qū)域分割

采用α－β交換的最大流／最小割算法［12］迭代進(jìn)行能量函數(shù)的近似最優(yōu)化，實(shí)現(xiàn)圖像的多區(qū)域分割。

本文提出的無(wú)監(jiān)督圖割方法，本質(zhì)上是一種融合核方法與邊緣梯度變化的多目標(biāo)自動(dòng)分割方法。該方法的關(guān)鍵在于能量函數(shù)的構(gòu)造和參數(shù)初始化設(shè)置，后面的第2節(jié)和第3節(jié)對(duì)這兩部分內(nèi)容分別做詳細(xì)介紹。

2 能量函數(shù)的構(gòu)造

2．1 數(shù)據(jù)項(xiàng)在核空間的轉(zhuǎn)換及計(jì)算

為了使PCM符合實(shí)際應(yīng)用要求，采用核方法對(duì)非線性可分的圖像數(shù)據(jù)進(jìn)行隱性的非線性映射，將原始數(shù)據(jù)映射到高維特征空間，實(shí)現(xiàn)線性可分的目的。這里“隱性”是指，不必明確給出非線性映射函數(shù)φ（·）的具體表達(dá)形式，內(nèi)積運(yùn)算可以用核函數(shù)代替［19］，即K（x，y）＝φ（x）·φ（y）。因此，在經(jīng)典圖割算法中引入核方法，既可以使PCM成為有效描述圖像數(shù)據(jù)的通用的簡(jiǎn)單模型，也可以充分利用基于圖割的能量?jī)?yōu)化方法，同時(shí)還體現(xiàn)了線性方法便于處理、計(jì)算簡(jiǎn)單的優(yōu)點(diǎn)，有效實(shí)現(xiàn)圖像的同質(zhì)多區(qū)域分割，此方法適用范圍廣泛，不受圖像類型的限制。

將數(shù)據(jù)項(xiàng)通過(guò)非線性映射函數(shù)φ（·）映射到核空間，則數(shù)據(jù)項(xiàng)轉(zhuǎn)換后的計(jì)算公式為

設(shè)K（·）為選用的核函數(shù)，定義

將式（7）代入式（6），數(shù)據(jù)項(xiàng)的核空間轉(zhuǎn)換公式簡(jiǎn)化為

轉(zhuǎn)換到核空間的數(shù)據(jù)項(xiàng)，不必考慮映射函數(shù)φ（·），只要確定使用的核函數(shù)即可完成數(shù)據(jù)項(xiàng)的計(jì)算。本文采用徑向基函數(shù)（radial basis function，RBF）中的拉普拉斯核函數(shù)（Laplace kernel，LRBF），該核函數(shù)在數(shù)據(jù)聚類中具有優(yōu)勢(shì)，且受參數(shù)影響較小，適合于區(qū)域分割。LRBF核函數(shù)的公式如下：

2．2 融合邊緣梯度約束的平滑項(xiàng)計(jì)算

邊緣信息是劃分圖像不同區(qū)域的重要特征。平滑項(xiàng)的作用是描述圖像分割區(qū)域的光滑程度，為使分割達(dá)到更好的效果，在平滑項(xiàng)中考慮圖像的邊緣信息，可以減少多區(qū)域分割產(chǎn)生的過(guò)分割。由于梯度特征在圖像邊緣變化劇烈，梯度變化可以作為判定圖像邊緣的基本準(zhǔn)則。將圖像中邊緣梯度變化作為約束條件融入平滑項(xiàng)，可以保持邊緣的不連續(xù)性，提高區(qū)域邊緣分割的準(zhǔn)確性，同時(shí)降低過(guò)分割現(xiàn)象的出現(xiàn)。則融合梯度約束的平滑項(xiàng)定義為

式中，Bpq為相鄰兩像素點(diǎn)的邊緣梯度約束。設(shè)Gp和Gq分別表示像素p和像素q的梯度，則

式中，σ是梯度變化閾值，其值取分割區(qū)域內(nèi)的梯度方差。因?yàn)榻y(tǒng)計(jì)模型采用PCM，Bpq的值由常數(shù)C決定，實(shí)驗(yàn)中C取值為5。

從平滑項(xiàng)公式可以看出，像素p和q劃分在不同區(qū)域時(shí)，需要確定邊緣不連續(xù)性。如果像素p和q梯度差異較大時(shí)，表明兩個(gè)像素處于區(qū)域邊緣，那么Bpq的值越小，平滑項(xiàng)確定的能量也越小，則像素p和q被分割可能性越大，可以保持邊緣的不連續(xù)性。如果像素p和q梯度差異較小時(shí)，Bpq的值增大，像素p和q被分割可能性減小，減少過(guò)分割現(xiàn)象。

3 多區(qū)域標(biāo)簽初始分配與模型參數(shù)計(jì)算

統(tǒng)計(jì)圖像的顏色特征，用直方圖描述統(tǒng)計(jì)量，對(duì)于任意級(jí)值i，如果H（i）≥H（i±1），則H（i）是峰值。設(shè)置K均值聚類的個(gè)數(shù)為峰值數(shù)n，即區(qū)域標(biāo)簽個(gè)數(shù)為n。特征值與峰值最接近的像素點(diǎn)設(shè)為聚類初始中心。利用確定的中心點(diǎn)和聚類個(gè)數(shù)，對(duì)圖像數(shù)據(jù)進(jìn)行K均值聚類，每一個(gè)聚類結(jié)果成為一個(gè)分割區(qū)域，為各個(gè)區(qū)域分配初始標(biāo)簽。聚類個(gè)數(shù)n與顏色直方圖組距h有關(guān)，n與h成反比，經(jīng)過(guò)實(shí)驗(yàn)驗(yàn)證，h的取值范圍為［10，20］。

計(jì)算每個(gè)分割區(qū)域Rl（l∈L）的PCM參數(shù)μl。首先，μl的初始值為區(qū)域Rl內(nèi)所有像素顏色特征的均值，用μlo表示。當(dāng)采用α－β交換算法迭代逼近能量函數(shù)最優(yōu)解時(shí)，在每次迭代過(guò)程中，區(qū)域標(biāo)簽都會(huì)重新分配，μl值也會(huì)發(fā)生改變。μl的計(jì)算公式如下：

式中，m表示迭代次數(shù)，即μlm為第m次迭代時(shí)PCM參數(shù)μl的值。

4 實(shí)驗(yàn)結(jié)果與分析

Berkeley圖像庫(kù)是經(jīng)典的測(cè)試圖像分割效果的數(shù)據(jù)庫(kù)，其中還包含了人工標(biāo)準(zhǔn)分割結(jié)果。本文選用該圖像庫(kù)中的10幅圖像作為訓(xùn)練圖像，用于無(wú)監(jiān)督圖割方法中參數(shù)的選擇實(shí)驗(yàn)；選用300幅圖像做多區(qū)域分割效果測(cè)試實(shí)驗(yàn)。實(shí)驗(yàn)的硬件環(huán)境為雙核CPU T2390 1．8GHz，內(nèi)存2G；軟件環(huán)境為Matlab R2011a開(kāi)發(fā)平臺(tái)。

4．1 平滑項(xiàng)比例系數(shù)λ選擇與測(cè)試分析

平滑項(xiàng)比例系數(shù)λ的取值對(duì)圖像多區(qū)域分割的效果有較大的影響，下面具體討論λ的取值原則。

圖1 λ的選擇分析

λ表示在能量函數(shù)中平滑項(xiàng)與數(shù)據(jù)項(xiàng)的比例。λ的值不同，平滑項(xiàng)相對(duì)于數(shù)據(jù)項(xiàng)占有的比例不同，圖像多區(qū)域分割的效果也會(huì)不同。依據(jù)分割效果的視覺(jué)直觀判斷，選擇合適的λ值。以Berkeley庫(kù)中圖12003為例，λ的選擇分析過(guò)程如圖1所示。如果λ很小，則平滑約束項(xiàng)占有的比重很小，此時(shí)主要考慮數(shù)據(jù)項(xiàng)對(duì)能量函數(shù)的影響，忽略了平滑項(xiàng)，數(shù)據(jù)項(xiàng)的約束使圖像中同質(zhì)區(qū)域都被有效分割，但是由于缺少了平滑項(xiàng)中邊緣梯度約束，分割區(qū)域較小且零散，過(guò)分割現(xiàn)象嚴(yán)重，不利于后續(xù)的圖像分析與理解。如果λ增大，則平滑項(xiàng)中邊緣梯度約束的作用加大，過(guò)分割現(xiàn)象逐漸減小，多區(qū)域分割效果好。但是λ增大到一定程度，平滑項(xiàng)的占有率遠(yuǎn)遠(yuǎn)大于數(shù)據(jù)項(xiàng)時(shí)，雖然過(guò)分割現(xiàn)象消失，但是圖像中有些區(qū)域不能被分割出來(lái)。經(jīng)過(guò)實(shí)驗(yàn)測(cè)試，λ取值在［2，3］范圍內(nèi)，無(wú)監(jiān)督圖割方法的分割效果最好。

4．2 與其他分割方法的比較

通過(guò)圖像訓(xùn)練測(cè)試，選擇好合適的參數(shù)之后，進(jìn)行多區(qū)域分割效果比較實(shí)驗(yàn)。將本文提出的方法與聚類結(jié)果融合法［20］（fusion of clustering results，F(xiàn)CR）、歸一化分割法［21］（normalized cuts，Ncuts）等經(jīng)典多區(qū)域分割方法進(jìn)行比較。3種分割方法的區(qū)域分割效果如圖2所示，由于篇幅有限，僅展示了Berkeley庫(kù)中一部分的圖像分割結(jié)果。以圖2中的分割效果為例，對(duì)3種方法進(jìn)行分析比較。

FCR是一種聚類結(jié)果融合方法，采用非穩(wěn)定的馬爾可夫隨機(jī)場(chǎng)（Markov rank field，MRF）模型實(shí)現(xiàn)6個(gè)顏色空間特征聚類結(jié)果的融合。由于包含了6個(gè)顏色空間中的紋元特征和candy邊緣特征，并進(jìn)行邊緣的軟分割，圖像誤分割現(xiàn)象較少，但是過(guò)分割現(xiàn)象嚴(yán)重。例如，圖67079中建筑的屋頂、圖296059中大象的脊背輪廓和圖187029中孩子的頭頂都出現(xiàn)了雙邊緣分割線。

Ncuts是基于圖論的歸一化分割算法，由于歸一化處理，減少了分割結(jié)果中的單一孤立分割點(diǎn)，因而分割區(qū)域形狀緊湊。Ncuts方法可以控制分割區(qū)域的數(shù)量，而分割區(qū)域總數(shù)較?。ǎ?）時(shí)，分割效果不理想，本文選用的分割區(qū)域數(shù)量為20。圖2的分割效果顯示Ncuts方法分割所得區(qū)域面積大致相近，多區(qū)域分割結(jié)果基本準(zhǔn)確，但是邊緣分割線波動(dòng)較大，影響了分割精度。例如，圖295087中樹(shù)枝的邊緣線和圖67079中石柱的邊緣線都有較大跳變，與標(biāo)準(zhǔn)分割線有明顯的差別。

本文提出的方法將數(shù)據(jù)項(xiàng)映射到核空間，實(shí)現(xiàn)復(fù)雜數(shù)據(jù)的線性可分，模型簡(jiǎn)單通用，計(jì)算復(fù)雜度低，而區(qū)域分割效果較好，尤其是低維空間中分割復(fù)雜的區(qū)域。例如，圖295087上石頭中間的兩個(gè)空洞和圖296059中右邊大象嘴下方的天空和草地等區(qū)域處于全包圍狀態(tài)，屬于復(fù)雜的分割區(qū)域。本文提出的方法對(duì)這些區(qū)域的分割效果比其他方法要好。同時(shí)，由于融合了邊緣梯度約束，過(guò)分割現(xiàn)象也得到抑制，并且邊緣分割線也較為流暢連貫。因此，從視覺(jué)效果直觀判斷，本文提出的方法分割效果更為理想。

下面采用概率Rand指數(shù)（probabilistic rand index，PRI）、信息變化指數(shù)（variation of information，VoI）和邊界偏離誤差（boundary displacement error，BDE）3個(gè)評(píng)價(jià)指標(biāo)，客觀定量地評(píng)價(jià)3種方法的分割效果。PRI指標(biāo)的作用是判斷算法分割結(jié)果與標(biāo)準(zhǔn)分割的相同程度，取值范圍在0～1之間，該指標(biāo)值越大表示算法分割結(jié)果越接近標(biāo)準(zhǔn)分割，分割效果越好。VoI是信息變化指數(shù)，其值域?yàn)榉秦?fù)實(shí)數(shù)，用條件熵描述算法分割結(jié)果不能被標(biāo)準(zhǔn)分割結(jié)果解釋的隨機(jī)性，該指標(biāo)越小分割效果越好。BDE指標(biāo)通過(guò)計(jì)算區(qū)域邊緣精度來(lái)判定分割效果，取值范圍是［0，∞），取值越小表示邊緣偏離誤差越小，分割效果越好。

圖2 3種區(qū)域分割方法圖像分割效果比較

采用本文提出的方法對(duì)Berkeley庫(kù)中300幅圖像進(jìn)行區(qū)域分割，統(tǒng)計(jì)PRI指標(biāo)的分布情況如圖3所示。PRI指標(biāo)高于0．8的圖像數(shù)量超出整個(gè)圖像庫(kù)的四分之三，表明本方法適用范圍廣泛，分割效果不受圖像內(nèi)容限制。為了進(jìn)一步驗(yàn)證本文方法的分割效果，將本文方法與其他兩種典型的多區(qū)域分割方法作量化比較。標(biāo)準(zhǔn)分割和3種分割算法的定量評(píng)價(jià)指標(biāo)如表2所示，表中各指標(biāo)的值是測(cè)試Berkeley庫(kù)中300幅圖的平均值。通過(guò)定量分析，表明本文提出的方法優(yōu)于另外兩種方法。

圖3 Berkeley庫(kù)中300幅圖像的PRI指標(biāo)統(tǒng)計(jì)

表2 定量評(píng)價(jià)指標(biāo)

通過(guò)實(shí)驗(yàn)證明，本文提出的方法不論是主觀視覺(jué)判斷還是客觀定量分析，都具有較好的分割效果，表明了該方法在圖像多區(qū)域分割中的有效性。

5 結(jié)束語(yǔ)

本文提出一種融合了核方法與邊緣梯度信息的無(wú)監(jiān)督圖割算法，通過(guò)圖像數(shù)據(jù)向高維特征空間的映射，擴(kuò)展了分段常數(shù)模型的實(shí)際使用范圍，實(shí)現(xiàn)了復(fù)雜圖像數(shù)據(jù)的線性可分，既提高了區(qū)域分割效果又降低了計(jì)算量。同時(shí)，在平滑項(xiàng)中加入邊緣梯度信息，增加了邊緣的劃分精度，減少了過(guò)分割的出現(xiàn)，進(jìn)一步提高區(qū)域分割性能。經(jīng)實(shí)驗(yàn)定性定量分析，該方法具有較好的多區(qū)域分割效果，也符合多區(qū)域分割的實(shí)際要求。本文提出的多區(qū)域分割方法可以較好地解決圖像中多目標(biāo)自動(dòng)分割問(wèn)題，為后面的多目標(biāo)識(shí)別、語(yǔ)義標(biāo)注、場(chǎng)景理解等研究奠定了良好的基礎(chǔ)。

［1］Carreira J，Sminchisescu C．CPMC：automatic object segmentation using constrained parametric min－cuts［J］．IEEE Trans．on Pattern Analysis and Machine Intelligence，2012，34（7）：1312－1328．

［2］Kappes J H，Andres B，Hamprecht F A，et al．A comparative study of modern inference techniques for discrete energy minimization problems［C］∥Proc．of the IEEE Conference on Computer Vision and Pattern Recognition，2013：1328－1355．

［3］Liu G，Zhou Z，Xie S．Global minimization of adaptive local image fitting energy for image segmentation［J］．Journal of Systems Engineering and Electronics，2014，25（2）：307－313．

［4］Boykov Y，Jolly M P．Interactive organ segmentation using graph cuts［C］∥Proc．of the 3rd International Conference on Medical Image Computing and Computer－Assisted Interven－tion，2000：276－286．

［5］Kolmogorov V，Zabih R．Multi－camera scene reconstruction via graph cuts［J］．Lecture Notes in Computer Science，2002，2352：82－96．

［6］Rother C，Kolmogorov V，Blake A．“GrabCut”－interactive foreground extraction using iterated graph cuts［J］．ACM Trans．on Graphics，2004，23（3）：309－314．

［7］Veksler O．Star shape prior for graph－cut image segmentation［J］．Lecture Notes in Computer Science，2008，5304：454－467．

［8］Wang B，Li J，Gao X B．An edge－and region－based level set method with shape priors for image segmentation［J］．Chinese Journal of Computers，2012，35（5）：1067－1072．（王斌，李潔，高新波．一種基于邊緣與區(qū)域信息的先驗(yàn)水平集圖像分割方法［J］．計(jì)算機(jī)學(xué)報(bào)，2012，35（5）：1067－1072．）

［9］Liu S T，Wang H L，Yin F L．Interactive ship infrared image segmentation method based on graph cut and fuzzy connectedness［J］．Acta Automatic Sinica，2012，38（11）：1735－1750．（劉松濤，王慧麗，殷福亮．基于圖割和模糊連接度的交互式艦船紅外圖像分割方法［J］．自動(dòng)化學(xué)報(bào)，2012，38（11）：1735－1750．）

［10］Chang J C，Chou T．Iterative graph cuts for image segmentation with a nonlinear statistical shape prior［J］．Journal of Mathematical Imaging and Vision，2014，49（1）：87－97．

［11］Wang H，Zhang H，Ray N．Adaptive shape prior in graph cut image segmentation［J］．Pattern Recognition，2013，46（5）：1409－1414．

［12］Boykov Y，Veksler O，Zabih R．Fast approximate energy minimization via graph cuts［J］．IEEE Trans．on Pattern Analysis and Machine Intelligence，2001，23（11）：1222－1239．

［13］Delong A，Osokin A，Isack H N，et al．Fast approximate energy minimization with label costs［J］．International Journal of Computer Vision，2012，96（1）：1－27．

［14］Delong A，Veksler O，Boykov Y．Fast fusion moves for multi－model estimation［C］∥Proc．of the 12th European Conference on Computer Vision，2012：370－384．

［15］Vu N，Manjunath B S．Shape prior segmentation of multiple objects with graph cuts［C］∥Proc．of the IEEE Conference on Computer Vision and Pattern Recognition，2008．

［16］Dhillon I S，Guan Y，Kulis B．Kernel K－means，spectral clustering and normalized cuts［C］∥Proc．of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，2004：551－556．

［17］Kulis B，Basu S，Dhillon I S，et al．Semi－supervised graph clustering：a kernel approach［J］．Machine Learning，2009，74（1）：1－22．

［18］Dhillon I S，Guan Y，Kulis B．Weighted graph cuts without eigenvectors：a multilevel approach［J］．IEEE Trans．on Pattern Analysis and Machine Intelligence，2007，29（11）：1944－1957．

［19］Salah M B，Mitiche A，Ayed I B．Multiregion image segmentation by parametric kernel graph cuts［J］．IEEE Trans．on Image Processing，2011，20（2）：545－557．

［20］Mignotte M．Segmentation by fusion of histogram－based K－means clusters in different color spaces［J］．IEEE Trans．on Image Processing，2008，17（5）：780－787．

［21］Shi J，Malik J．Normalized cuts and image segmentation［J］．IEEE Trans．on Pattern Analysis and Machine Intelligence，2000，22（8）：888－905．

E－mail：tydxcomputer＠163．com

謝 剛（1972－），通信作者，男，教授，博士，主要研究方向?yàn)橹悄苄畔⑻幚?、智能控制?/p>

E－mail：xiegang＠tyut．edu．cn

Unsupervised graph cuts for image region segmentation

ZHAO Jie1，2，XIE Gang1
（1．College of Information Engineering，Taiyuan University of Technology，Taiyuan 030024，China；2．Department of Computer Engineering，Taiyuan University，Taiyuan 030032，China）

A multi－region image segmentation method based on graph cuts is proposed．Original image data is transformed into high－dimension feature space via the implicit nonlinear mapping of data term by kernel function，so that the effect of segmentation is improved，multi－class partition of the image is achieved and the application of the piecewise constant model is extended．Due to the edge gradient of the image dramatically changes with discontinuity，the gradient constraint is introduced to smooth terms in order to reduce the over segmentation．Simultaneously，initial parameters are set by the unsupervised method without user interactions to meet the requirements of multi－region segmentation．Experiment results show that the proposed method is not restricted by the content of the image and has better segmentation results through both the subjective visual judgement and the quantitative analysis．

region segmentation；graph cuts；kernel method；edge gradient

TP 391

A

10．3969／j．issn．1001－506X．2015．06．31

趙 婕（1978－），女，講師，博士研究生，主要研究方向?yàn)閳D像處理、分析與理解、模式識(shí)別與機(jī)器學(xué)習(xí)。

1001－506X（2015）06－1431－06

2014－07－07；

2014－10－10；網(wǎng)絡(luò)優(yōu)先出版日期：2014－11－20。

網(wǎng)絡(luò)優(yōu)先出版地址：http：／／www．cnki．net／kcms／detail／11．2422．TN．20141120．1831．004．html

太原市科技項(xiàng)目人才專項(xiàng)基金（12024728）資助課題