基于區(qū)域相似性與相異性的數(shù)字圖像分割方法

李　楠，徐書(shū)文

(中國(guó)電子科技集團(tuán)公司電子三所，北京 100015)

?

基于區(qū)域相似性與相異性的數(shù)字圖像分割方法

李楠，徐書(shū)文

(中國(guó)電子科技集團(tuán)公司電子三所，北京 100015)

針對(duì)數(shù)字圖像數(shù)據(jù)量大、內(nèi)容復(fù)雜、特征度量困難的特點(diǎn)，提出了一種綜合區(qū)域相似性和相異性的基于圖模型的分割方法。使用顏色方差作為距離度量，依靠區(qū)域鄰接圖和最近鄰區(qū)域圖來(lái)完成數(shù)字圖像的快速區(qū)域合并分割。在合并過(guò)程中，通過(guò)合并區(qū)域的最小合并代價(jià)和最大合并代價(jià)變化，調(diào)整合并順序，從策略上保證了分割區(qū)域的同質(zhì)性和區(qū)域間的相異性。實(shí)驗(yàn)結(jié)果表明，該方法可以較好地解決圖像的誤分割現(xiàn)象。

圖像分割；相似性；相異性；圖模型

1　圖像分割

隨著圖像處理技術(shù)的發(fā)展，區(qū)域?qū)ο笞鳛楦咝畔⒌妮d體替代像素成為分析圖像的最小單元。對(duì)象可以提取包括亮度、顏色、紋理、形狀等多種特征，更容易建立圖像中各個(gè)關(guān)鍵要素的邏輯聯(lián)系，是圖像理解中最重要的中層描述之一[1]。

圖像分割方法是獲取對(duì)象的主要途徑之一，其分割獲得的區(qū)域完整性是理解對(duì)象的關(guān)鍵，但是現(xiàn)階段仍缺乏快速有效的圖像分割方法。特別是，小飛機(jī)、無(wú)人機(jī)等航拍工具應(yīng)用越來(lái)越廣泛，逐漸成為獲取偵察數(shù)據(jù)的主要方式。航拍視頻的幀數(shù)據(jù)量大，內(nèi)容復(fù)雜，難以使用特征度量，極大地限制了圖像分割方法在工程中的應(yīng)用。劉震坤等[2]提出了一種基于輪廓梯度擴(kuò)散場(chǎng)的水平集分割方法，可以有效解決CT斷面圖像的分割。葉齊祥等[3]使用區(qū)域復(fù)雜度模板將顏色信息和空間信息融合，較為準(zhǔn)確地分割出了圖像中的紋理區(qū)域。Comaniciu等[4]使用MeanShift進(jìn)行預(yù)處理和簡(jiǎn)單分割，也是較為實(shí)用的粗分割方法。Baatz等[5]使用了區(qū)域增長(zhǎng)與區(qū)域合并相結(jié)合的方法，成為現(xiàn)階段較為實(shí)用的對(duì)象建立方法之一。周芹等[6]對(duì)GrabCut算法進(jìn)行了改進(jìn)，解決了三維醫(yī)學(xué)分割效率低得難題。彭建喜[7]提出一種改進(jìn)的模糊核聚類圖像分割算法，解決了局部極值收斂問(wèn)題，迭代次數(shù)明顯降低。盡管研究者提出的方法在某些領(lǐng)域取得了較好的應(yīng)用，但是沒(méi)有一種方法能夠精度高、速度快地完成分割，尤其是隨著數(shù)據(jù)量的增大，部分算法的魯棒性出現(xiàn)了較大的下降。

而在特征建模上，區(qū)域相似性一般是分割時(shí)優(yōu)先選用的度量方法，但是區(qū)域間相似性還沒(méi)有一種普適的表達(dá)方法，尤其是使用區(qū)域增長(zhǎng)和區(qū)域合并方法時(shí)，隨著合并區(qū)域的變化，描述區(qū)域的顏色、形狀等特征常常會(huì)出現(xiàn)不平衡情況，初始設(shè)定的相似性表達(dá)方法會(huì)慢慢退化，造成部分區(qū)域過(guò)分割或欠分割。

本文提出了一種綜合區(qū)域相似性和相異性的基于圖模型的分割方法，通過(guò)對(duì)圖合并模型的修改，從策略上改變了合并方式，避免了相似性度量退化。方法使用顏色差異來(lái)描述區(qū)域，通過(guò)分水平算法建立初始圖模型，即區(qū)域鄰接圖(Region Adjacency Graph，RAG)和最鄰近區(qū)域圖(Nearest Neighbor Graph，NNG)，根據(jù)圖中節(jié)點(diǎn)的最小合并代價(jià)和最大合并代價(jià)，尋找全局最優(yōu)區(qū)域?qū)M(jìn)行合并，達(dá)到閾值即可終止得到分割結(jié)果。在合并過(guò)程中，通過(guò)合并區(qū)域的最小合并代價(jià)和最大合并代價(jià)變化，調(diào)整合并順序，從策略上保證了分割區(qū)域的同質(zhì)性和區(qū)域間的相異性。

2　基于圖模型的區(qū)域合并

2.1特征描述

本文使用區(qū)域間顏色方差來(lái)描述區(qū)域的相似性與相異性，區(qū)域α和區(qū)域β的合并距離dc為

(1)

式中：l為顏色通道數(shù)；n和σb表示區(qū)域的像素?cái)?shù)和區(qū)域在b通道的均方差；下標(biāo)α，β，m分別表示區(qū)域α、區(qū)域β和合并后區(qū)域m。

2.2圖模型

算法主要使用了區(qū)域鄰接圖(Region Adjacency Graph，RAG)[8]和最鄰近區(qū)域圖(Nearest Neighbor Graph，NNG)[9]來(lái)進(jìn)行區(qū)域合并分割。這兩種圖結(jié)構(gòu)相輔相成，共同完成了圖像對(duì)象的描述，其中RAG主要表示圖像中區(qū)域的拓?fù)潢P(guān)系，NNG則對(duì)區(qū)域拓?fù)潢P(guān)系進(jìn)行抽樣簡(jiǎn)化，反映了區(qū)域的合并順序。

圖1　圖模型示意圖

2.3區(qū)域合并方法

為了綜合區(qū)域間的相似度和相異度，基于圖模型的區(qū)域合并分割算法的基本流程如下：

1)首先通過(guò)平均各個(gè)通道數(shù)據(jù)獲得灰度圖像，使用中值濾波去除隨機(jī)噪聲，然后采用分水嶺漫水法獲得圖像初始分割區(qū)域。

2)對(duì)初始分割區(qū)域進(jìn)行標(biāo)注，得到K個(gè)區(qū)域，按照式(1)計(jì)算區(qū)域間的相似性距離，記作dij，其中i,j∈(1,2，…，K),i≠j。

3)尋找每個(gè)區(qū)域的最大距離，記作dmax(i)，i∈(1,2，…，K)。

4)綜合區(qū)域間相似度和相異度，則區(qū)域間合并代價(jià)為

(2)

式中：若區(qū)域i有且僅有1個(gè)鄰接區(qū)域j，則定義式(2)中dmax(i)=max(dmax(i),dmax(j))=dmax(j)。

式(2)表明：(1)兩個(gè)區(qū)域合并時(shí)，兩個(gè)區(qū)域間的相似度較高，且兩個(gè)區(qū)域與其他區(qū)域的差異度應(yīng)較大；(2)當(dāng)某個(gè)區(qū)域有且僅有1個(gè)鄰接區(qū)域時(shí)，其只能合并到其唯一鄰接區(qū)域，應(yīng)給予補(bǔ)償。

5)根據(jù)式(2)建立RAG和NNG圖，尋找NNG所有子圖中的最優(yōu)區(qū)域?qū)?，即環(huán)節(jié)點(diǎn)，建立環(huán)節(jié)點(diǎn)代價(jià)序列。

6)對(duì)環(huán)節(jié)點(diǎn)代價(jià)序列排序，則排序后序列即為圖像的全局最優(yōu)區(qū)域合并序列。

7)從序列中取出第一組節(jié)點(diǎn)對(duì)進(jìn)行合并，合并后將該節(jié)點(diǎn)對(duì)剔除序列。

8)使用2.4節(jié)方法更新RAG和NNG。將因合并操作而消失的環(huán)從序列中刪除，并加入新生成的環(huán)，重新排序，保持排序不變。

9)重復(fù)步驟7)直到序列中全局最有區(qū)域?qū)Φ膮^(qū)域合并代價(jià)大于閾值。

2.4更新RAG和NNG策略

當(dāng)區(qū)域?qū)喜r(shí)，需要更新RAG和NNG圖，分為2種情況：

1)區(qū)域合并后，使用式(1)重新計(jì)算合并后區(qū)域i與鄰接區(qū)域j的距離dij，若鄰接區(qū)域j的最大合并代價(jià)dmax(j)未發(fā)生變化，則只需更新合并后區(qū)域與鄰接區(qū)域的合并代價(jià)即可完成RAG圖更新。更新NNG圖，需更新合并后區(qū)域i和鄰接區(qū)域j的弧的指向，并記錄新生成的環(huán)和消失的環(huán)，圖2為圖1區(qū)域合并后更新的可能發(fā)生的情況示意圖。

圖2　RAG和NNG更新示意圖

2)區(qū)域合并后，若區(qū)域j的最大距離dmax(j)發(fā)生了變化，需更新合并后區(qū)域i與區(qū)域j的合并代價(jià)，并且更新區(qū)域j與其鄰接區(qū)域q的合并代價(jià)才能完成RAG圖更新。同樣的，NNG圖更新時(shí)，需更新區(qū)域i，j，q的弧的指向，并記錄新生成環(huán)和消失得環(huán)。圖3為圖1合并后更新可能發(fā)生的情況示意圖。

圖3　RAG和NNG更新示意圖

每次合并后，NNG都會(huì)存在至少一個(gè)環(huán)。從上面的兩種情況可以看到，由于使用了相異性，所以環(huán)的變化(生成或消失)不只發(fā)生在合并區(qū)域的鄰接頂點(diǎn)上，而且可能在鄰接頂點(diǎn)的鄰接頂點(diǎn)上。

證明：設(shè)NNG圖中有且僅有1個(gè)環(huán)，且環(huán)節(jié)點(diǎn)為vi與vj。根據(jù)NNG圖中弧的指向有

(3)

則至少存在1個(gè)頂點(diǎn)vq與頂點(diǎn)vi(或vj)的相鄰接。當(dāng)NNG圖中存在頂點(diǎn)不與頂點(diǎn)vi(或vj)相鄰接時(shí)，則至少存在1個(gè)頂點(diǎn)vp與vq相鄰接。同理，當(dāng)NNG圖中存在頂點(diǎn)不與頂點(diǎn)vi(或vj)和vq相鄰接時(shí)，則至少存在1個(gè)頂點(diǎn)vg與vp相鄰接。

當(dāng)環(huán)節(jié)點(diǎn)vi與vj合并后生成頂點(diǎn)vk時(shí)，根據(jù)式(1)可得dkq。

同理可證環(huán)消失情況。

證明完畢。

3　圖像分割實(shí)驗(yàn)

本文選擇了2幅航拍圖像進(jìn)行分割實(shí)驗(yàn)。采用相同的分割區(qū)域數(shù)作為終止條件，分別使用本文方法和RAG全局最優(yōu)合并方法對(duì)圖像進(jìn)行分割。其中RAG全局最優(yōu)合并方法只使用了相似性作為判斷最優(yōu)的標(biāo)準(zhǔn)。分割結(jié)果如圖4、圖5所示。

圖4　紅外航拍圖像分割結(jié)果

圖5　可見(jiàn)光航拍圖像分割結(jié)果

圖4為紅外航拍圖像分割結(jié)果。本文方法考慮了鄰域區(qū)域之間的相似性和相異性關(guān)系，對(duì)右上角的建筑區(qū)域分割效果較好；而RAG全局最優(yōu)方法只考慮相似性，得到的結(jié)果較為破碎，尤其是在右下角的建筑區(qū)域內(nèi)產(chǎn)生了多個(gè)條狀分割結(jié)果。圖6為兩種方法在區(qū)域合并時(shí)所用的時(shí)間，可以看出本文方法所用時(shí)要遠(yuǎn)遠(yuǎn)小于RAG全局最優(yōu)合并，且初始區(qū)域數(shù)越多，時(shí)間差別就越大。

圖6　紅外圖像分割時(shí)區(qū)域合并時(shí)間

圖7　可見(jiàn)光圖像分割時(shí)區(qū)域合并時(shí)間

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

本文提出了一種基于區(qū)域相似性和區(qū)域相異性的圖模型快速合并分割方法。方法使用區(qū)域鄰接圖和最鄰近區(qū)域圖建立區(qū)域合并模型。根據(jù)每次合并后區(qū)域的最小合并代價(jià)和最大合并代價(jià)變化，調(diào)整合并順序，從策略上保證了分割區(qū)域的同質(zhì)性和區(qū)域間的相異性。實(shí)驗(yàn)表明，該方法取得了較好的結(jié)果，為解決相似性度量退化問(wèn)題提供了一種方法。

[1]BENZ U. Multi-resolution， object-oriented fuzzy analysis of remote sensing data for GIS-ready information [J]. ISPRS journal of photogrammetry and remote sensing， 2004(58)： 239-258.

[2]劉震坤，古中濤，廖曉波，等. 基于梯度矢量C-V模型的空心葉片圖像分割[J]. 計(jì)算機(jī)工程，2010，36(8)： 224-226.

[3]葉齊祥，高文，王偉強(qiáng)，等. 一種融合顏色和空間信息的彩色圖像分割算法[J]. 軟件學(xué)報(bào)，2004，15(4)：522-530.

[4]COMANICIU D，MEER P. Mean shift： a robust approach toward feature space analysis [J]. IEEE transactions on pattern analysis and machine intelligence， 2002， 24(5)： 603-619.

[5]BAATZ M，SCHAPE A. Multiresolution segmentation： an optimization approach for high quality multi-scale image segmentation[C]//Proc. Angewandte Geographische Information. Wichmann， Heidelberg：[s.n.]， 2000：102-109.

[6]周芹，茹國(guó)寶，余紹德，等. 基于GrabCut的三維醫(yī)學(xué)圖像分割[J]. 電視技術(shù)，2016，40(2)：27-32.

[7]彭建喜. 一種基于C均值的模糊核聚類圖像分割算法[J]. 電視技術(shù)，2014，38(9)：28-31.

[8]YU Q Y，CLAUSI D A. IRGS： image segmentation using edge penalties and region growing[J]. IEEE transactions on pattern analysis and machine intelligence， 2008， 30(12)： 2126-2139.

[9]HARIS K. Hybrid image segmentation using watersheds and fast region merging[J]. IEEE transactions on image processing， 1998， 7(12)： 1684-1699.

李楠(1983— )，工程師，主研圖像處理、信號(hào)處理；

徐書(shū)文(1964— )，女，研究員，主要研究方向?yàn)閳D像處理、信號(hào)處理等。

責(zé)任編輯：時(shí)雯

Digital image segmentation method based on regional similarity and diversity

LI Nan，XU Shuwen

(TheThirdResearchInstituteofChinaElectronicsTechnologyGroupCorporation，Beijing100015，China)

The data of digital image are huge quantity and very complex， so they are difficult to be described by the features. This paper proposes a digital image segmentation method based on the graph model which integrated regional similarity and diversity. The method uses color variance to define the distance between regions， and achieve the fast region merging based on region adjacency graph and nearest neighbor graph. In the process of merging， the merge order adjusts with the change of the minimum and maximum cost of regional merge， so the homogeneity of regions and diversity between regions are ensured by the merge strategy. The experiments show that the proposed method is useful to solve the error segmentation.

image segmentation； similarity； diversity； graph model

TP391

ADOI：10.16280/j.videoe.2016.07.006

2016-03-15

文獻(xiàn)引用格式：李楠，徐書(shū)文.基于區(qū)域相似性與相異性的數(shù)字圖像分割方法[J].電視技術(shù)，2016，40(7)：24-27.

LI N，XU S W.Digital image segmentation method based on regional similarity and diversity[J].Video engineering，2016,40(7)：24-27.