基于區域相似性與相異性的數字圖像分割方法

李　楠，徐書文

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

?

基于區域相似性與相異性的數字圖像分割方法

李楠，徐書文

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

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

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

1　圖像分割

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

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

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

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

2　基于圖模型的區域合并

2.1特征描述

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

(1)

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

2.2圖模型

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

圖1　圖模型示意圖

2.3區域合并方法

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

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

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

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

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

(2)

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

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

5)根據式(2)建立RAG和NNG圖，尋找NNG所有子圖中的最優區域對，即環節點，建立環節點代價序列。

6)對環節點代價序列排序，則排序后序列即為圖像的全局最優區域合并序列。

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

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

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

2.4更新RAG和NNG策略

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

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

圖2　RAG和NNG更新示意圖

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

圖3　RAG和NNG更新示意圖

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

證明：設NNG圖中有且僅有1個環，且環節點為vi與vj。根據NNG圖中弧的指向有

(3)

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

當環節點vi與vj合并后生成頂點vk時，根據式(1)可得dkq。

同理可證環消失情況。

證明完畢。

3　圖像分割實驗

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

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

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

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

圖6　紅外圖像分割時區域合并時間

圖7　可見光圖像分割時區域合并時間

4　結束語

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

[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的三維醫學圖像分割[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

文獻引用格式：李楠，徐書文.基于區域相似性與相異性的數字圖像分割方法[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.