学术研究
测绘技术装备季
刊第
卷
年第
期
基于
图论的图像分割方法及
其
局限性研究
曹建农’
方丹霞’
长安大学地球科
学与
国土资源学院西安
西
安建筑科技大学建筑学院西
安
摘要
本文研
究基于图
论的
图像分割方法及其局限
性以
图论为
工
具研究图
像分割问题的
成果已有
不少报
道对其局限性的研
究将有利于
将概率网络
的研
究成果
应用于
图像分割
及其它
图像问题
这其间图论方法
既
是桥梁也是
一个广阔
的应用领域它
在
图像分制问题
和概率论的
传统方法之间重
新建立了
一个充满
可能的
研
究空间
关键词
图像分割
图论概率网络
墓于图论方
法的图像分割概念标函
数易
于处理全局信
息的优点在
局部特
征和全
基于图论的聚类优化问题研究开始于世纪
局特征之间找到了一种平衡使得算法具有较
强的
年代前后【’
在图
像处理与分析方面的应用开始
于鲁棒性
虽然它的研究过于初级并
且没有持续
进行
世
纪年代
以后
一
文献
在
国内较早提出将但它的重要意义在
于将图论网
络与
目标函数功
能的
图论和目标
函数共
同作为聚类
约束的
混合聚类方深层作用联系在
一起为图论及其
网络理论在优化
法它结合了图论方法易于处理数据局域特征
和目
及其图
像处理中的应用提供了极好的实践
根据
图
分块聚
类步骤中的每一分
步的
结果图像
所有
像素都
被显示为它们各自的子
树的
平均强
度’
图
中显示了在图
中分别去
掉
弧段
之后的区
域
它们
分别对应于图
图
图
图
图图
从
世纪
年代初开始
以及世
纪
年中后
期
至今国际上出现了众多基于图论方法的图像
分
割聚
类和分析
研究成果
一
这些方法的
共同主
题
是加权图的
形式
和构成图的每
一个顶点相应
于
一个图
像像素或
区域图的每
一条边
被赋
予权
重
这个权
重是通过对那些处在
相同分割之中
的边相关
联
的像素或区
域所期望的某种度
量来测度
通过使
图的成份中的节点
或这些成份之间的边界
的特
定代价函
数
最小化将这样的图分
成一
些组成成份
将
一个图分裂成多
于两个成份的方法之一
是
递归地二
元分裂
咧
直到某种终止条件满足
通常终
止条件
是建
立在被
用于二
元分裂的相同
代价
函
数基础之上
的
在
此我们给出文献
提供的一个聚类的例子以
说
明基于图论的图像分割的基本原理
如图
是一幅合成图像
背
景具有
不同的强度
包含
个
目标
和它们的重叠区
域因测绘技术装备季刊第
卷
年第
期学术研究”
此图像被分为
个相互连接的区
域
小块
每
一
个区
域具有恒定的灰度
强度
如图
这
个区
域各自的灰度强度记录于表
从表中
可以看
出在
重叠和不重叠的近邻区
域之间的最小灰度强度
差值
是
那么
由此
生成的邻接图
如图
图的每
一
个顶点对应
于一个区
域块如果每
一个区
域块
互
为近邻
例如它们是空间相邻的
则相应
的节点
对之
间就产
生一个弧段那么弧上的流容
量
叩
就被赋予每一段弧这些容量
可以是
任何
非负对称函
数
即偶函
数
就此具体实例而言
文献
选择
了这类函
数作为
节点区
域块
之间的相
表
图
中区
域的灰度
级强度
区
域灰度
强度似性度量作为特例下面的容量函
数
其控制参
数
二
被用于这个实例
一
碑
二
些兰,
。
“
这里
气
表示节点
,
和
之间的近邻像素数量
从
和召
分别是区
域块
和的抽样平均值
那么
等
价树就可以
利用
算法川得到如图
这个等价树
上的所有
弧的容量值
记录于表〔
自上而
下以升序排列
表
图
中等价树
的弧容量值
编号弧段容量
,
气
城,。
班
二。
切
二
夏
成,
二
花
一
一
一
一
一
姗犯
现在从等价树中按照
容量增大的顺序
将弧
段删
去第一个被删去的弧段是。
二
因此产生了一
个
子树这个
子树包含了区
域
和图像中
剩余的其
它部分图显示了结果图像它的分区
部分具有
各自
子树的平均灰度强度类似地弧段碱
。
喻
心。
,
以及,。
分别被删去进
一步获得
分区部
分的图像如图
一
因为图
通过相似特征
在
本例中
只是像素灰度
强度
对图像近邻区
域进行
了正
确分类所以不再需要更多
的类别在等价树
中剩余的弧段表示为图
中的加黑加粗的连接线
可以
注意到区
域
和区域
没有聚类到一起因
为它们所在空间是不相连的
同样区
域
和区
域
也是如此最终的聚类数
是
从表
的第三列可
以看出在最后被删
去的弧段。
升。
和弧段,
之间其
容量具有一个显
著的突变这也是
停止条件
的判据
之一
上例中邻接
图
如图的构成是将
图像分
割
或聚类
问题转化为图论问题的关键一步
也
是用图论方法对图像分割
或聚类
问题的
模型化
过程这个邻接图是一个无向图可以理解为马尔科夫网
络因
为它满足马氏
性即无后效性近邻
相关性
等价树
如图的获得
可以理解为满足
某种优化准则的最优网
络的搜索过
程它是基于一
个无向图
马尔科夫
网络
的推理过程在
上例中
推理过程由
算法实
现
算法
是图论中的经典算
法它应用三角不等式原理在节
点集中搜索任意两个节点之间的最小容量路径
这
是一个动态规划过程表
记录了动态搜索结果
表
记
录的是任意两个节点之间相似性的全局最优
结
果对这些记录进行排序分析
可以发现相似性
突变的位
置以
此
为终止条件将相似性较小的弧段
逐步删去就达到了
保留全局
相似性最好的弧段的
目
的也就获得了
全局最佳图像分割
或聚类
基于
图论方法的图
像分割研究
文献
的主要思想是将被聚类数据用一个无向
邻接
图
来表示
的每
一个顶点相应于数据点
根据给定的近邻系统
一相
当于优化理论中
的目标函
数能量函数
以及前
文提
到的各种代价函
数
如果相应的数据
