一种利用图进行图像分割的高效方法

《一种利用图进行图像分割的高效方法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2008年6月山东师范大学学报(自然科学版)Jun.2008第23卷第2期JournalofShandongNormalUniversity(NaturalScience)Vol.23No.2一种利用图进行图像分割的高效方法1)2)3)张田周翔凤王希常(1)山东师范大学管理与经济学院,250014,济南;2)山东工商学院计算中心,264005,山东烟台;3)山东师范大学信息科学与工程学院,250014,济南∥第一作者23岁,男,硕士生)摘要利用图像的图表示定义了一个衡量区域间边界存在性的谓词函数,在此基础上给出了

2、一种运行时间与图中边的数目成近似线性,实际效果良好的有效图像分割方法。方法具有在高可变性区域时忽略细节,在低可变性图像区域时保存细节的能力.关键词图像分割;区域比较;网格图;最邻近图;全局特征中图分类号TP317.4图像的分割和合成是计算机视觉的重要研究方面,许多计算机视觉问题在原理上都与它相同,总的来讲图像分割具有重要意义.[1,2]图像分割算法有很多较好图像分割方法应该具有下面两个性质:1)获得感观上重要的区域,它经常反映的是图像的整体方面.2)高效,运行时间与图像的象素数目成近似线性.这样才有实际应用价值.

3、实验证明本文提出的方法具备上面的性质.[3]在基于图的图像分割中方法中令G=(V,E)为一无向图,顶点Vi∈V,为被分割元素的,边(vi,vj)∈E对应着一对相邻顶点,V中的元素是像素,一条边的权重w((vi,vj))是对该边连结的两个像素之间的某种相异程度量度(例如亮度).一个分割S是将V分成几个部分,每部分(区域)C∈S对应于图G′=(V,E′)E′∈E中一个连通的部分.1分割算法1.1区域比较谓词这个谓词用来判定区域间是否有边界.首先,将一个部分CAV的内部差别定义为本部分最小生成树中最大的权重.即Int(

4、C)=maxw(e).(1)e∈MST(C,E)接下来,将两个部分C1,C2AV之间的差别定义为连接两部分的最小边权重.即Dif(C1,C2)=minw((vi,vj)).(2)v∈C,v∈C,(v,v)∈Ei1j2ij如果没有边连接C1和C2,则令Dif(C1,C2)=∞.比较谓词定义为:ture,Dif(C1,C2)>MInt(C1,C2)D(C1,C2)=(3)false,otherwise其中,MInt(C1,C2)=min(Int(C1)+τ(C1),Int(C2)+τ(C2)).单个部分的任意非负函数

5、都可用作τ,对算法性质没有影响.比如令τ(C)=kP

6、C

7、,

8、C

9、表示C的大小,k为某一常数参数.1.2算法及其性质首先给出定义,然后给出算法以及算法具有的性质.定义1如果区域C1,C2∈S,而且它们之间没有边界,则称分割S过于精细.定义2考虑同一个基集合的两个分割S和T,当T中的任意一个部分都包含于(或者等于)S中的某一部分时,我们说T是S的一个精简.另外,如果T≠S,T称为S的完全精简.若S有一个不过于精细完全精炼,则称分割S过于粗糙.定理1对于任意(有限)图G=(V,E),都存在既不过于粗糙也不过于精细的分

10、割S.定理1说明了较好算法的存在性,证明略去.下面给出算法.分割算法:输入:有n个顶点和m条边的图G=(V,E).输出:是将V分成几部分的一个分割S=(C1,⋯⋯,Cr).步骤:收稿日期:2007-06-0510第2期张田,等:一种利用图进行图像分割的高效方法第23卷0)依据边的权重将E排成非降序的序列π=(O1,⋯Om);001)以一个分割S开始,S中每个顶点本身构成一个部分:2)分别令q=1,⋯,m来重复第三步;q-1q3)根据S按照下面的步骤构造S.令vi,vj表示有序序列中第q个边所连接的顶点,即Oq=(

11、vi,vj).如果vi和vj在q-1q-1S不的部分中并且w(Oq)与两个部分各自内部差别相比都小,则合并两个部分.否则,什么也不做.现形式化地,令Ci为q-1q-1q-1q-1q-1q-1q-1q-1S中包含vi的部分,Cj为包含vj的部分.如果Ci≠Ci并且w(Oq)

12、分割S不是过于精细.定理3根据定义2对过于粗糙的定义,使用(3)中定义的区域比较谓词时算法产生的分割不是过于粗糙.定理4算法产生的分割并不取决使用0)中哪一权重非降的边序列.2算法实现及运行时间用不相交集结合排序算法和路径压缩算法来实现.算法运行时间分为两部分,首先步聚0)中需要将边按权重非降序排列,对于整数权重可以在线性时间完成,一般地,利用常见排序算法可以在O(nlo