基于图谱理论的图像分割

翟永磊 田道坤

（中国人民解放军91604 部队，山东 龙口265700）

0 引言

图像分割就是将图像表示为物理上有意义的连通区域的集合。人们一般是通过对图像的不同特征如边缘、纹理、颜色、亮度等的分析达到图像分割的目的。 图像分割通常是为了进一步对图像进行分析、识别、跟踪、理解、压缩编码等，分割的准确性直接影响后续任务的有效性，因此具有十分重要的意义。

1 图像分割

1.1 图像分割的一般模型

图像分割是依据图像的灰度、颜色或几何性质将图像中具有的特殊含义的不同区域区分开来，这些区域是互不相交的，每一个区域都满足特定区域的一致性。 比如对同一物体的图像，一般需要将图像中属于该物体的像素（或物体的特征像素点）从背景中分割出来，将属于不同物体的像素点分离开。 分割出来的区域应该同时满足：

1.1.1 分割出来的图像区域的均匀性和连通性。 其中，均匀性指的是该区域中的所有像素点都满足基于灰度、纹理、彩色等特征的某种相似性准则，连通性是指该区域内存在连接任意两点的路径。

1.1.2 相邻分割区域之间针对选定的某种差异显著性。

1.1.3 分割区域边界应该规整，同时保证边缘的空间定位精度。

1.2 基于阈值选取的图像分割方法

基于阈值选取的图像分割方法是提取目标物体与背景在灰度上的差异， 把图像分为具有不同灰度级的目标区域和背景区域的组合。阈值法对物体和背景对比较强的景物分割有着很强的优势，计算较为简单，并且可以用封闭和连通的边界定义不交叠的区域，是图像分割中最有效且实用的技术之一。根据获取最优分割阈值的途径可以把阈值法分为全局阈值法、动态阈值法、模糊阈值法和随机阈值法等。尽管阈值选取的方法很多，但至今还没有找到一种对所有图像都可以有效分割的方法，一种阈值方法只能适用于某一类或某几类图像，因此一些学者在研究新的阈值选取方法之外，同时将新的数学工具融合到原有的阈值方法中，并取得了较好的分割效果。

2 一种新的基于图谱理论的图像阈值分割方法

基于图谱划分的图像分割方法通常具有较高的复杂性，实时性较差，因而在很多实时视觉处理场合无法采用。 采用一种基于图谱划分的阈值分割方法，采用图谱划分测度作为阈值分割的准则来区分目标和背景。 与现有的基于图谱划分的图像分割方法类似，我们仍将图像中的每个像素看作一个节点，而连接每两个节点的权值反映了这两个像素属于同一类的可能性。不同之处在于我们采用基于图像灰度级的对称矩M（其大小为256×256）来描述图像中各部分之间的关系，而不是采用一般的N×N （其中N 为图中节点的个数） 的对称的相似矩阵W。 算法的基本思想是：对每一个可能门限t，利用矩阵M 可快速地计算其对应的图谱划分值，其最小的图谱划分值对应的门限即为分割图像的最佳阈值。采用这种方法的一个最大的优点是避免了复杂的特征系统求解问题，因而极大减少了算法所需的存储空间以及计算的复杂度，大大提高了算法的实时性能。比较实验还表明，这种基于图谱划分的阈值分割方法的性能优于其他类型的阈值分割方法；同时针对一些适合于阈值分割的具有明显目标和背景的实际图像，这种方法较之通常用特征系统求阈值的方法更为有效。

3 实现过程

基于图谱理论新的阈值分割算法我采用matlab 语言加以实现，同样是采用Ncut 算法。 这种基于图谱理论新的阈值分割算法的实现流程图如图3-1。

首先读取图像，把图像转化成灰度值矩阵。 然后检测图像是否是彩色图像，如果是彩色图像就把它转化成灰度图像处理，如果是灰度图像就直接继续下一步。

在这里如果图像尺度很大时，将会严重影响程序运行速度，所以我在这里加入了调整图像大小的语句， 主要目的在于减少运算量，提高运算速度。 如果图像较小时这条语句就可以省略了。 显示原始图像如图3-2。

转化数据类型，接着就是对以下公式：

中的参数加以设置，这里dI设置为625，dX设置为4，r 设置为2。

图3-1 算法流程图

下一步是通过计算图中所有节点间的权值就可以构建基于灰度级的权值矩阵M。 运用M 矩阵的上三角形部分，分区求出每一个门限t 对应的cut（A，B），asso（A，A）和asso（B，B）的值，进而求出这个门限对应的Ncut（A，B）值。 画出Ncut（A，B）的曲线变化图，如图3-3。

图3-2 原始图像

图3-3 Ncut（A，B）的曲线变化图

根据Ncut（A，B）的曲线变化图，计算出最小Ncut（A，B）值对应的门限t 的值，此值即为我们要找的最佳分割阈值T，本文所采用的图像的分割阈值为77。

然后用求得的阈值T 对图像进行分割，将原图像中灰度值大于T的都赋值为0,显示分割的结果；将灰度值小于T 的都赋值为0，显示分割结果。

以下就是分割结果，把人物和背景成功地分离开来，如图3-4。

图3-4 图像分割结果

4 结论

基于图谱分组理论的图像分割方法通过将图像看作一个无向带权图，图像中的像素看作图的节点，构建节点邻接权值矩阵，进而采用求解特征系统的方法来寻求图谱划分测度的最优解， 并利用其相应的特征矢量对图中节点进行分类。 这类方法虽然效果较好，但是其巨大的计算复杂度使得该方法很难在很多实时应用场合使用， 如自动目标识别(ATR)等。 本文采用的基于图谱划分测度的阈值分割方法则有效克服了这一计算瓶颈问题。 选用图谱划分测度作为阈值分割的准则，构建基于灰度级的邻接权值矩阵， 通过查询权值矩阵即可快速得到每个阈值t（0≤t≤255）对应的Ncut 值，进而采用最小Ncut 值对应的门限对图像进行阈值分割。 理论分析及实验结果均表明，本方法极大地缩减了算法所需的存储空间及运算时间，能够有效地应用于实时视觉场合。 对比实验结果还表明：与文献中其他典型的图像分割方法相比，本文提出的基于图谱划分的阈值分割方法具有更好的分割性能，且鲁棒性较好。

［1］李弼程，彭天强，彭波.智能图像处理技术[M].北京：电子工业出版社，2004:589-651.

［2］Z Wu,R Leahy.An optimal graph theoretic approach to data clustering:Theory and its application to image segmentation[J].IEEE.Trans on PAMI,1993:1101-1113.

［3］卜月华.图论及其应用[M].南京：东南大学出版社，2002:1-28.

［4］王树禾.图论[M].北京：科学出版社，2004:1-5.