基于图论的图像分割技术探讨

汤龙

摘要：数字图像处理技术的发展历史并不算久，却是一种极具挑战性的跨学科技术，不但涉及美学和物理学的基础知识，更需要计算机的算法作为技术支持。在信息化网络时代，各行各业的管理运作都离不开计算机技术。其中，对图像数据的处理和分析技术更是许多工作岗位上计算机实务操作的根本原理所在。其中，图像分割技术历来是图像分割处理中的技术难点。该文将专门针对基于图论的图像分割技术来进行探讨与研究。

关键词：图论；图像分割；边缘识别

中图分类号：TP302 文献标识码：A 文章编号：1009-3044（2016）12-0197-02

图像分割（Image Segmentation）是根据图形的灰度、颜色、纹理和形状等不同指标来进行信息分组，将同一指标中特征相似的归为一类，继而不同类别的较大差异来分割图像。

1 图像分割的传统方法归纳

1）边缘检测分割法

边缘检测是最基本的图像分割技术，顾名思义，即通过智能测算，来确定图像的边缘，并进行分割。首先识别出图像中的边缘点，然后以闭合曲线连结锚点，选出分割区域。

从色彩学的基本原理上看，图像的边缘，通常是灰度、色相或纹理等特性发生骤变的地方。因此，对于图像边缘的识别，主要是依赖算法对上述特征的界定。边缘检测算法种类繁多，且各有优缺点。其中，智能识别逻辑含义简单，边缘灰度变化明显，且噪点不多的简单图像。而对一些题材超现实，或是色彩和明度变化微妙，又或者噪点过多的图像，执行这一简单的算法就无法正确地识别边缘。即使反复操作，效果也不好：一来噪点过多，与图像本身的边缘区分不开，二来降低噪点又必然折损原图的结构纹理，更容易误导边缘识别。

2）阈值分割法

阈值分割则也是传统的分割技术之一，分割原理很容易理解，即利用图像中目标区域与背景区域之间的最大灰度差来识别不同物体之间的边界，此时便将相同物体上灰度的相对均匀作为分割依据。阈值分割通过一个或几个阈值将图像划分出几个不同区域。

阈值图像分割法的基本原理是根据直方图的像素分布来指定恰当的阈值，该方法也有局限性：只能对动态范围广，即像素分布均匀的图像进行精确分割。如果图像的直方图向左或向右倾斜过多（即像素集中分布在高亮部或暗部），实际区域划分就会出现严重的误差。

3）聚类分析分割法

聚类分析法的诞生，是图形分割由单一算法走向多元统计的标志。所谓的聚类分析，指的是根据图形数据的内部结构来划分类别，从而实现更智能化，成功率更高的边缘识别。

聚类分析有两种，一种是硬聚类，还有一种是模糊聚类分析法，一般前者比较常用，其基本工作原理是在非同一类别的函数中，将隶属度取值为0或1，换言之单个样本只可属于单一类别。

模糊聚类则是在一种无监督的聚类方法，它是在样本点的正态分布区间中根据隶属度取值，如此一来，各个样本点对聚类都呈现出一种隶属关系。模糊聚类法是图像边缘不确定性的典型表征。因此在运用上硬聚类分割法更为繁琐，目前多用于医学图像处理中。

而可能性聚类则不同于上述方法，它不仅要顾及到样本与聚类中心的隶属关系，还要兼顾样本对分类结果的影响。传统聚类算法不能覆盖到图像的空间性，所以对局部强噪点和灰度变化大的图形解读能力较差。为了优化模糊聚类算法在图像分割中的效果，来自欧美顶尖实验室的技术人员优先提出了迭代优化法，该算法可以从三维视角识别图像的空间信息，算得上是最前沿的新型算法。

4）活动轮廓图像分割法

活动轮廓分割法最初诞生于上世纪九十年代初，主要是指在图像的阈值曲线或者曲面几何特性和数据的共同作用下，以最小化能量函数的形式向边界运动。这一方法从提出至今，已经过二十余年时间，活动轮廓建模理念已经在边缘检测、图像分割领域取得了可喜的实验结果，通过技术人员在算法上的优化与改进，最终使得圆滑轮廓曲线最大限度地切合目标物体的凹陷边缘，因此在很大程度上解决了参数活动轮廓方法易于陷入局部能量区域这一技术障碍。

2 基于图论的图像分割法

2.1 以图论为导向的研究方向

基于图论的图像分割技术是近年来图像分割领域中引起广泛关注的研究热点，它的基本思想并不复杂：即通过图像映射转化为无向图，在图像边缘界定锚点，令各个锚点之间边的权重分别对应不同像素之间的不相似度，从而计算出割的容量。截至目前，基于图论的图像分割方法的研究主要集中在以下几个方面：

1）最优切割准则设计原则；2）谱方法分割原则；3）快速算法。

基于图论的分割方法，从本质上讲，是将图像分割问题转化为特征识别问题，即转化为聚类方法。、而最优分割原则是指通过划分两个子图，取内部相似度最大值来作为界定图像边缘的参考。图割算法中割集准则的选取对最终分割结果有直接影响，使用频率较高的割集准则有最小割（Minimum cut）、平均割（Average cut）大小分流割（Max-minimum Cut）等。

2.2 割集选择的基本原理

1）图形最优分割

图论算法在计算机应用技术中扮演着很重要的角色，该方法灵活度很高，可以解决很多问题。遗传算法是解优化问题的有效算法，而并行遗传算法是遗传算法研究中的一个重要方向，受到了研究人员的高度重视。此类方法把图像分割问题与图的最小割（min cut）问题相关联。首先将图像映射为带权无向图G=，图中每个节点N∈V对应于图像中的每个像素，每条边∈E都连接一对相邻像素，边的权值意味着相邻像素之间在灰度、色度和纹理方面的非负相似度。而对图像的分割就是对图以某种指标为准进行裁切，被裁切出的每个区域C∈S分别对应了图中一个子图。

因此，分割的最优原则意味着划分后的子图在内部保持最大相似度，而子图之间则保持最小相似度。基于图论的分割方法的根本原理就是移除特定的边，将图划分为若干子图从而实现分割。目前所了解到的基于图论的方法有智能图形分割（GraphCut）和权函数运算等。

2）权函数运算

权函数一般定义为两个节点之间的相似度，也就是在数据统计中计算出平均数等指标，然后对各个变量值权衡大小，所以顾名思义地被称为“权函数”。在权函数运算中，对于灰度图像，一般用F表示像素的灰度值，X表示像素的空间坐标，Y为灰度高斯函数的标准方差（用于测算出两像素之间的有效距离）。一旦超过这一距离，则认为两像素之间的相似度较大；反之两像素之间的距离越小，则认为相似度越大。

3）图形相似度矩阵

图论分割算法常把最优割集准则转化相似度矩阵以便求解。相似度常用字母W和A表示。相似度矩阵又称亲和力矩阵，运算原理是将原图像中的像素重新排布。在相似度矩阵中，所有相邻像素的相似度都可以通过函数运算得到。将相似度矩阵的每行元素相加，即得到该节点的度，以所有度值为对角元素构成的对角矩阵即为度矩阵，度矩阵常用字母D表示。令低量算符矩阵为L=D-W，则在图论分割算法中低量算符矩阵为最常用的标准矩阵。

3 图论分割方法的应用

1）临床医学图像分割

图论图像分在医学领域可以用于脑心电图，以及脊椎骨核磁共振，即在区域生长和模糊连接度的基础上结合各向异性滤波和边缘检测算子检测边缘，继而从图像中划分出目标选区，为外科手术方案提供参考。同时，此项技术也可以患者肿瘤切片的深度分割，为医学工作者诊断病情，确定治疗方案提供了有效的数据参考。最新的研究方向表明，图像分割技术还有可能被用于重建细胞全息图，为医学人员攻克免疫方面的病症提供了更深入的数据分析，其潜在应用价值不可估量。

2）纹理分割

纹理分割（Texture Segmention ）对后续图像的其他算法处理非常重要，对分割算法的掌握对于后续算法，比如目标跟踪，人脸识别等等，都是非常重要的。可将Normalize Cut准则用于图像中的边缘与纹理质地测算识别，即将图像信息分为干涉基元和纹理基元，并将两种信息进行数据合并。同时，Normalize Cut准则还具有较好的兼容度，对于将明度信息与纹理信息数据整合的分割方式也适用。

3）智能图形分割

智能图形分割（Graph cuts）最先由国外的技术人员研发，近年来开始在国内广为流传，因其智能度高，操作易上手，因而受到了广大商业运作机构的追捧，被广泛应用在UI设计，商业摄影后期制作等领域。智能图形分割的基本原理就是将图像分割问题与图的最小割（min cut）准则实行联合运算，使图像在保持较小容差值的情况下，依然可以大刀阔斧地进行轮廓识别，而不会被材质纹理造成的明暗变化所误导。基于这种基本原理，智能图形分割也难免存在局限性，即它只适合逻辑简单清晰地图形。尽管如此，它仍然可以胜任相当多的行业操作终端对于图像分割的需求。即使在操作中偶尔出现识别错误，通过若干次的容差值修改，最终也不难得到一个相对精确的图形分割方案。

4 结论

在前文中，作者首先总结了目前常用的集中图像分割技术，然后对基于图论的图形分割技术做出了详细的分类探讨。对图像分割算法的研究历史至今已有几十年，基于各种理论至今已开发出了千余种分割算法。目前，图像分割方法发展势头良好，正朝着更迅速、更精确、更智能的方向发展，通过研究新理论，引进国外先进技术，这一领域在不久的未来势将取得更大的突破和进展。

参考文献：

[1] 侯叶.基于图论的图像分割技术研究[D].西安电子科技大学，2011.

[2] 罗青青.基于图论的图像分割技术研究[D].南京邮电大学，2014.

[3] 贺锦鹏.基于图论的彩色纹理图像分割技术研究[D].哈尔滨工程大学，2011.

[4] 郑倩.医学图像分割方法研究及其应用[D].南方医科大学，2014.

[5] 董昌灏.基于图论的交互式PCB图像分割技术研究[D].解放军信息工程大学，2013.

[6] 胡学刚，孙慧芬，王顺.一种新的基于图论的图像分割算法[J].四川大学学报：工程科学版，2010（1）：138-142.