基于区域相似性与相异性的数字图像分割方法

李　楠，徐书文

(中国电子科技集团公司电子三所，北京 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.