设为首页 | 收藏本站 | 每日归档
当前位置:ucbug游戏网 > 新闻中心 > 游戏开发 >
一种基于两步分割的非监督彩色图象分割方法(2)
作者:admin来源:未知发布时间:2009-06-23 07:58

对于两个区域 RK,RL的边的权重 WK
,L
,我们仿照分子间的作用力公式可以定义如
下的经验公式:

rr


rr


.


I
( K
).I
( L)

.


X
( p).
X
(q)

CX

WK
,L = e σ* p∈RK
,q∈RL ,

e
σ
(1)
X(r) ( p). X(r) ( q)

<D


其中, I(r) (K) ,I(r) (L) 分别表示两块区域的平均颜色, p,q分别是两个区域中的象
素点,X(v) ( p) ,X(v) (q) 为点 p,q的坐标,σ
C,σ
X为两个参数, D为距离域值,我们
可以认为当两个象素点的距离大于 D时,这两个点没有关系。可以看出这个公式符合区
域相似性的特性。计算每两块之间的 WK
,L
,则可以构成权重矩阵 W,易知 W是一个稀
疏的对称矩阵。

2.4 正规化划分
对于一个图 GV,E),若有两个集合 A,B,满足 A∪B
=V,A∩B
=Φ,则可通过将连
接着两个集合的边去掉,从而把这个图划分成两部分。可以将 A,B两个集合的相似度定
义为:

Cut
(A, B) =∑
w(u,v) (2)

u∈A,v∈B


其中 u是 A中的点,v是 B中的点,w(u,v)是边(u,v)的权重。

一个最小二分可以认为是使( 2)式取最小值的划分,这样的划分可以在多项式时间
内完成[2]。但是这样的划分会趋向于将图中的小块区域划分出来,如图 3所示。在图 3中,
点之间的权重由它们的距离决定,可以看出由公式( 2)所约束的划分会将较孤立的点划
分出来,这与实际较好的划分不符。实际较好的划分是将这图划分成两个区域,每个区域


的点有各自的分布密度。

为了修正这种错误的趋向,我们可以给出一个正规化的的相似度,定义公式为( 3):

Ncut(A, B) =cut(A, B) +
cut(A, B) (3)

asso(A,V
) asso(B,V
)

其中asso(A,V) =Σu∈A,t∈Vw(u,t) 表示 A中的点到 V中的点的权重的总和,同样

[3]
asso(B,V
) =Σv∈B,t∈Vw(v,t) ,其定义的合理性请见文献 。若是一个划分可以使
Ncut(A, B) 达到最小,则这个划分是一个正规化划分。求在公式( 3)的约束下的最优解
是一个具有 NP难度的问题,但是若只求次优解,则文献 [3]同时提出了一个方法可将这个
问题转变为一个求 W矩阵特征值的问题。并且若这个 W矩阵是稀疏矩阵,可以采用文献

[8]中的方法进行快速求解。
在具体的分割过程中,可以对 G进行递归二分,即对正规化划分得到的两个区域分
别进行划分。直到 Ncut(A, B) 的值大于一个设定的域值的时候停止。此时得到的分割即
为最终结果。通过调节这个域值,可以控制分割的程度,从而决定各分割块所带信息量的
大小。

试验结果


(a)输入图象(b)粗分的结果(c)最后细分结果
图 4输入图象及其分割结果
图 4为狗的图象及其分割结果。其中,图 4(a)为原始图象;图 4(b)为经过区域
生长法粗分的结果,总共有 270块,从图中可以看出每块有基本一致的颜色,但是这样的
分割结果过细,每块难以表达完整的信息;图 4(c)为通过正规化划分的结果,此时只
有 10块区域,每块区域可以表达完整的信息,大大方便了高层信息的提取。可以看到这
个分割算法有忽略物体对象内部细节,而只分割主要区域的性质。同时,可以看出这个算


法可以进行一定限度的纹理分割。

图 5是对不同类型图片的分割结果。所有的分割结果都是在同一组参数下得到的。由
于细分采用了全局最优化的约束条件,因此算法比较稳定。可以看到分割所得到的每块区
域都有较完整的信息。同时,本算法的运行速度也较快,对于 320×240的图片,在配置
为 P3 800的机器上,半分钟内能完成分割。这比 [3]中以象素为单位进行图划分在速度上
有大幅度提高,并且分割结果更加稳定。


图 5更多的分割结果

但是在试验过程中,我们也发现当区域间的分界线不是太明显时,会造成漏分;同时
当图片中有较明显的纹理区域时,会影响分割的结果。引起这些问题的主要原因是在计算
权重矩阵W时没有考虑这些因素。

结论

本文采用了两步分割的方法对彩色图象进行分割。在第一阶段,算法采用了基于边界
强度变化的区域生长算法对图象进行粗分,这个阶段充分利用了图象的局部信息;在第二


阶段,算法将粗分结果构造成图,同时给出了边的权重的经验公式,最后利用全局最优化
划分方法对图进行划分。试验证明本算法适用于基于内容的图象查询系统,能有效的将彩
色图象分割成带有较完整信息的区域。如何将权重计算公式定义得更加合理,以及如何对
有较强纹理的图片进行分割是我们下一步要研究的内容。同时,我们也将把本算法与其它
的算法进行比较。

致谢感谢景枫提供了试验所用的各种图象。感谢王立刚提供的技术支持。同时感谢王珏,邓可,刘策
对此论文提出的各种中肯的建议。

作者简介张竞丹,1978年生,广东省兴宁市人,硕士研究生,研究领域为虚拟现实,计算机视觉,
计算机图形;邓志东,教授,博士生导师,研究领域为人工智能,神经网络,人机交互技术及应用;郭
百宁,博士,主任研究员,研究领域为计算机图形,透视图和几何造型,基于图象的模型、纹理生成和
处理等。

声明:本站所有资源均来自网络,版权归原公司及个人所有。如有版权问题,请及时与我们联系,我们在第一时间予以删除,谢谢!
ucbug游戏网
关于我们 | 下载帮助 | 广告&合作 | 下载声明 | 版权声明
Copyright © 2010-2016 ucbug.com. All Rights Reserved ucbug游戏网
皖ICP备15003425号 适度游戏娱乐,沉迷游戏伤身。