基于图论的图像分割软件设计

姬治华++曹金香++杨发顺

摘要：本文设计了一款基于图论的图像分割软件，并对交互方式进行了改进。该软件基于VS2010软件平台和OpenCV库，使用C++作为开发语言，运用MFC进行软件界面和对话框的设计，为图像分割提供了一个良好的界面交互环境和可视化平台。

关键词：图像分割；图论；最小割；MFC

中图分类号：TP18 文献标识码：A 文章编号：1009-3044（2016）20-0183-02

1 概述

图像分割是计算机视觉中最基本最重要的研究内容之一，对图像处理、图像分析和图像理解起着关键性的作用。所谓图像分割是指根据图像的某个特定属性将图像划分为若干个互不交叠的区域，并从中提取目标的过程[1]。

图像分割的定义[2]：

2算法原理

2.1图论的基本概述

图论（Graph Theory）是数学的一个分支，它以图为研究对象。图论中的图是由点和连接两点的线所构成，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应的两个事物之间具有的某种关系[3]。

基于图论的图像分析指将待处理的图像映射为带权的无向连通图G=（V，E，W），节点集V是图I中所有像素点的集合，边集E表示连接两个邻接顶点的边的集合，W表示每条边权值的集合，边的权值反映了该边的两个顶点的差异或相似度。

权值集合W的构建是图像分割成功的关键，好的相似度度量函数需要体现出两个节点在颜色、亮度、距离等方面的相似程度。常用的相似度度量函数有特征空间的欧氏距离：

作为相似度的度量函数，前者的优点是直观且计算简单，后者的优点是与实际情况更加接近，但是运算量较大[4]。

2.2最小割/最大流方法

基于图论的分割方法是将整幅图像映射为图，图的顶点和图中像素一一对应，根据一定的割集准则将图划分为两个子图，使得子图之间的相似性最小，而子图内的相似性最大[5]。图割示意图如图1所示：

使得代价函数最小的划分即为图像的最佳分割，也即图的最小割。

最小割/最大流方法主要包括两大类[6]：推进重标记（Push relabel）方法和增广路径（Augmenting paths）方法。推进重标记法易于并行实现，通常采用GPU加速实现来提高效率。基于增广路径的方法通过标号不断生长一棵树，直到找不到关于可行流的增广路径为止。该类方法的计算复杂性和网络的节点数和边数无关，而与边上的权值有关。

3软件系统设计

3.1设计思路

3.2软件测试及结果

单击选择图像按钮读入待分割图像，根据图像中目标的形状选择交互方式，单击分割按钮运行分割程序，矩形交互和圆形交互分割结果分别如图3和图4所示：

从上图可以看出，分割结果图像边缘比较光滑，所设计软件操作简便且具有较好的分割效果。

4 结论

基于图论的分割方法可以将图像的全局分割与局部信息处理相结合，可减少由于图像离散化造成的误差，从而可获得良好的分割结果。本系统具有如下技术特点：（1）将原始图像，交互图像和分割后图像显示在同一界面上，运算结果形象直观，便于用户观察；（2）界面简洁，操作简单，运行效率和分割精度较高。

参考文献：

[1] 章毓晋. 图像分割[M].北京：科学出版社， 2000.

[2] 罗希平， 田捷， 诸葛婴，等. 图像分割方法综述[J]. 模式识别与人工智能， 1999（3）：300-312.

[3] 张建梅， 孙志田， 余秀萍. 基于图论的图像分割算法仿真研究[J]. 计算机仿真， 2011， 28（12）： 268-271.

[4] 杨帆，廖庆敏. 基于图论的图像分割算法的分析与研究[J]. 电视技术， 2006 （7）： 80-83.

[5] Sarkar S， Soundararajan P. Supervised learning of large perceptual organization： Graph spectral partitioning and learning automata[J]. Pattern Analysis and Machine Intelligence， IEEE Transactions on， 2000， 22（5）： 504-525.

[6] Boykov Y， Veksler O. Graph cuts in vision and graphics： Theories and applications[M]. Handbook of mathematical models in computer vision. Springer US， 2006： 79-96.