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

李　楠，徐書文

(中國電子科技集團公司電子三所，北京 100015)

?

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

李楠，徐書文

(中國電子科技集團公司電子三所，北京 100015)

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

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

1　圖像分割

隨著圖像處理技術的發(fā)展，區(qū)域對象作為更高信息的載體替代像素成為分析圖像的最小單元。對象可以提取包括亮度、顏色、紋理、形狀等多種特征，更容易建立圖像中各個關鍵要素的邏輯聯(lián)系，是圖像理解中最重要的中層描述之一[1]。

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

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

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

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

2.1特征描述

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

(1)

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

2.2圖模型

算法主要使用了區(qū)域鄰接圖(Region Adjacency Graph，RAG)[8]和最鄰近區(qū)域圖(Nearest Neighbor Graph，NNG)[9]來進行區(qū)域合并分割。這兩種圖結構相輔相成，共同完成了圖像對象的描述，其中RAG主要表示圖像中區(qū)域的拓撲關系，NNG則對區(qū)域拓撲關系進行抽樣簡化，反映了區(qū)域的合并順序。

圖1　圖模型示意圖

2.3區(qū)域合并方法

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

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

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

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

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

(2)

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

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

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

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

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

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

9)重復步驟7)直到序列中全局最有區(qū)域對的區(qū)域合并代價大于閾值。

2.4更新RAG和NNG策略

當區(qū)域對合并時，需要更新RAG和NNG圖，分為2種情況：

1)區(qū)域合并后，使用式(1)重新計算合并后區(qū)域i與鄰接區(qū)域j的距離dij，若鄰接區(qū)域j的最大合并代價dmax(j)未發(fā)生變化，則只需更新合并后區(qū)域與鄰接區(qū)域的合并代價即可完成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的合并代價，并且更新區(qū)域j與其鄰接區(qū)域q的合并代價才能完成RAG圖更新。同樣的，NNG圖更新時，需更新區(qū)域i，j，q的弧的指向，并記錄新生成環(huán)和消失得環(huán)。圖3為圖1合并后更新可能發(fā)生的情況示意圖。

圖3　RAG和NNG更新示意圖

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

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

(3)

則至少存在1個頂點vq與頂點vi(或vj)的相鄰接。當NNG圖中存在頂點不與頂點vi(或vj)相鄰接時，則至少存在1個頂點vp與vq相鄰接。同理，當NNG圖中存在頂點不與頂點vi(或vj)和vq相鄰接時，則至少存在1個頂點vg與vp相鄰接。

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

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

證明完畢。

3　圖像分割實驗

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

圖4　紅外航拍圖像分割結果

圖5　可見光航拍圖像分割結果

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

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

圖7　可見光圖像分割時區(qū)域合并時間

4　結束語

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

[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]. 計算機工程，2010，36(8)： 224-226.

[3]葉齊祥，高文，王偉強，等. 一種融合顏色和空間信息的彩色圖像分割算法[J]. 軟件學報，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]周芹，茹國寶，余紹德，等. 基于GrabCut的三維醫(yī)學圖像分割[J]. 電視技術，2016，40(2)：27-32.

[7]彭建喜. 一種基于C均值的模糊核聚類圖像分割算法[J]. 電視技術，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— )，工程師，主研圖像處理、信號處理；

徐書文(1964— )，女，研究員，主要研究方向為圖像處理、信號處理等。

責任編輯：時雯

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

文獻引用格式：李楠，徐書文.基于區(qū)域相似性與相異性的數(shù)字圖像分割方法[J].電視技術，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.