基于图论和特征的图像分割

桂露，何绍勇

（四川大学计算机学院，成都 610065）

基于图论和特征的图像分割

桂露，何绍勇

（四川大学计算机学院，成都 610065）

传统的基于图论的特征分割方法，使用图的表示方法，定义一个量去测量两个邻域间是否有边界，然后产生基于此量的分割算法，尽管此算法是贪心的，但它满足全局要求。算法是线性的，在实际中运行速度很快。在此基础上，提出用特征去处理所有的这些分支，计算分支之间的欧式距离，解决相同的非邻域分支无法正确处理的问题。

图像分割；特征；图算法

0 引言

图像分割的问题仍然是计算机视觉的巨大挑战，它是对图像中的每个像素加标签的一个过程，这一过程使得具有相同标签的像素具有某种共同视觉特性；简化或改变图像的表示形式，根据灰度、颜色、纹理和形状等特征把图像划分成若干互不交迭的区域，并使这些特征在同一区域内呈现出相似性，而在不同区域间呈现出明显的差异性，使得图像更容易理解和分析。图像分割通常用于定位图像中的物体和边界。

1 基于图和特征提取的图像分割

使用基于图的方法去分割，无向图G=（V，E），Vi∈V表示要被分割的点的集合，边（Vi，Vj）∈E表示相邻的点组成的边，每条边都有一个对应的边的权重W（Vi，Vj），这是一个非负数，它代表两个相邻的元素Vi和Vj的相似度。

在图像分割的方法中，分割S是对点V的分割，使得分割得到的每一部分C∈S，且C为连通的组件，形成了G'=（V，E'）。换句话说，任何分割都是由边的集合E的子集形成的。有多种不同的方式去测量分割的质量，总体而言，我们希望的是在同一部分相同，在不同部分不同，这意味着，在相同部分，每两个顶点之间的边的权重相对而言小，在不同部分的边相对而言大。

对于非邻域的分支，如果是同一表现形式的话，应该是属于同一部分，却不能分在一个区域，这里，采用了全局特征CEDD，计算不同分支的特征，如果特征是一样的，这应该是同一分支，反之不是。

2 边界判定

在这一节中，我们定义了D，评估是否有证据表明边界的两个组成部分之间存在边界。D是基于测量同一边界的两部分外部的差异相对于其两部分内部各自的差异。我们定义内部差异：

外部差异：

这里，最小的内部差异：

|C|表示C的大小，K是一个常量。对于小的分量而言，我们需要边界的更强烈的迹象。在实际中，K设置了一个观量尺度，在这里，一个更大的K引起较大的部件的偏好。然而，K并不是一个最小的分支的大小，如果在两个相邻分支之间有较大的差异，更小的部分是被允许的。

3 算法

输入是图G=（V，E），有n个顶点，和m条边，输出是分割后的图像的各个部分S=（C1，…，Cr）

①将图中的所有边按照非递减的顺序排列成（O1，…，Om）。

②开始于S0，每一个顶点都是一个单独的分支。

③重复步骤④，对于q=1，2，…，m。

④由Sq-1建立Sq。让Vi和=Vj表示第q条边Oq=（vi，vj），如果vi和vj在Sq-1不同的分支，并且w（Oq）比它们分支内部的差异小，合并。

⑤返回S=Sm。

以上是传统的方法，基于图的图像分割方法。然而，实际意义中，不是邻域的两个分支也可能属于同一分支，但以上方法却无法解决，因此，本文提出了一种新方法，在上面方法的基础上，对每一个分支提取CEDD特征，将每一分支映射到特征空间，计算其相似度。

①～⑤同上。

⑥提取所有分支的CEDD特征。

⑦计算两两分支之间的欧式距离，若小于阈值k，这是同一分支。反之，输出最后的分支。

4 实验及结果

（1）数据结构，我们用图的方法去表示要分割的图片，同一个区域的点拥有同一个根节点，每个区域都用一颗树去代替，多个区域就是多棵树的森林。属于同一个区域的像素点拥有同一个根节点。在判断两个区域是否合并的时候，使用了贪心策略，这个算法第一部分执行的时间与图的边是呈线性的。

（2）使用基于颜色的边的权重计算方法

W（vi，vj）=|I（pi）-I（pj）|，这里I（pi）是每个像素的强度，一般而言，为了弥补数字化伪影，在计算边的权重之前，采用高斯滤波器平滑图像。通常采用高斯参数d=0.8，这对图像并不会产生视觉上的变化，但可以帮助移除伪影。对于彩色图片的第一部分，执行3次，分别为红、绿、蓝。本文认为若两个像素点相邻，它们在这3个平面都在同一分支，就认为其为同一分支，反之不是。如图1所示。

图1

（3）获取CEDD特征

对于每一分支，分别获取CEDD特征。如图2所示。

图2

图1和图2对比就可以知道，第二个运动员的两个手套就分为了同一个分支。

5 结语

基于图的图像分割方法，只能对邻域进行区分，对不相邻的分支，无法计算。本文提出了一种新方法，在基于图的图像分割方法上，提取特征，将每一个分支映射到特征空间中，对每两分支进行相似度计算，使得在不相邻区域的相同分支有可能分到同一分支，得出的结果更加符合实际意义，为图像分割算法开辟了新径。

参考文献：

[1] Jordi Freixenet，Xavier Mu，Joan Mart and Xavier Llad.Colour Texture Segmentation by Region-Boundary Cooperation[C].8th European Conference on Computer Vision，May 11～14，2004

[2] David R.Martin，Charless Fowlkes and Jitendra Malik.Learning to Detect Natural Image Boundaries Using Local Brightness，Color，and Texture

[3] Pedro F.Felzenszwalb，Daniel P.Huttenlocher.Efficient Graph-Based Image Segmentation.International Journal of Computer Vision September 2004，59（2）：167～181

[4] S.Arya and D.M.Mount.Approximate Nearest Neighbor Searching.Proc.4th Annual ACM-SIAM Symposium on Discrete Algorithms，1993：271～280

[5] G.Ausiello，P.Crescenzi，G.Gambosi，V.Kann，A.Marchetti Spaccamela and M.Protasi.Complexity and Approximation.Combinatorial Optimization Problems and their Approximability Properties，to Appear，Springer-Verlag，Berlin

Image Segmentation Based on Efficient Graph and Feature

GUI Lu，HE Shao-yong
（College of Computer Science,Sichuan University，Chengdu 610065）

Defines a predicate for measuring the evidence for a boundary between two regions using a traditional graph-based representation of the image.Develops an efficient segmentation algorithm based on this predicate,and shows that although this algorithm makes greedy decisions,it produces segmentations that satisfy global properties.The algorithm runs in time nearly linear in the number of graph edges and is also fast in practice.Extracts feature to deal with all of the components,then calculates the distance of the components,which can solve the similar components which is not neighboring can not be classified.

Image Segmentation;Feature;Graph

1007-1423（2015）02-0070-03

10.3969/j.issn.1007-1423.2015.02.018

桂露（1990-），女，湖北咸宁人，硕士研究生，研究方向为图像检索

何绍勇（1984-），男，云南昆明人，硕士研究生，研究方向为无线传感器网络

2014-11-20

2014-12-16