基于各向异性扩散的图像分割算法_彭启民
DOI:10. 15918/j.t b i t1001-0645. 2005. 04. 009第25卷 第4期北京理工大学学报2005年4月Tr ansactions of Beijing Institute of T echnolog y
V o l. 25 No. 4
Apr. 2005
文章编号:1001-0645(2005) 04-0315-04
基于各向异性扩散的图像分割算法
彭启民, 贾云得
(北京理工大学信息科学技术学院计算机科学工程系, 北京 100081)
摘 要:提出了一种基于各向异性扩散的图像分割算法. 对现有的各向异性扩散的正则化方法进行了分析. 根据微分几何中共形映射的有关理论, 把原扩散方程分解为关于表面曲率的二阶方程, 给出了分解式的正则化条件, 保证了解的稳定性. 通过对扩散系数的调节, 提高了对各向异性扩散过程的控制能力. 在形态学分割的基础上, 通过能量函数最小化实现非线性尺度空间中的区域合并, 消除了分水岭算法造成的严重过分割现象. 实验结果表明, 该算法的分割结果可为后续识别和理解提供较理想的方式. 关键词:图像分割; 各向异性扩散; 非线性尺度空间中图分类号:T P 391 文献标识码:A
Algorithm for Image Segmentation Based on
Anisotropic Diffusion
PEN G Qi-min, JIA Yun-de
(Depar tment o f Co mputer Science and Enginee ring , Schoo l o f Infor matio n Science and T ech no lo g y, Beijing Institute of
T ech no lo gy , Beijing 100081, China)
Abstract :A new algo rithm fo r image seg mentation based o n aniso tro pic diffusio n is propo sed. The existing regularity method abo ut aniso tropic diffusion is introduced. The diffusion equation is decomposed as a seco nd o rder equatio n about surface differential curv ature acco rding to the theo ry of co nformal m apping in differential geometry . The reg ula rity conditio n of th e decomposed equatio n is discussed to guarantee a stable solution. Then, the diffusion coefficients in the decom posed equatio n a re analy zed to get a further control o n the aniso tro pic diffusio n. An initial seg menta tion is g enerated with a wa tershed transfo rm based o n the mathema tical mo rpholog y . The final segm entatio n is reached by eliminating the ov er-segm entatio n of initial regio ns. An energ y minimum criterion is applied to g uide the regio n m erging in nonlinear scale space. The ex periment show s tha t the pro po sed alg orithm prov ides recog nition and understa nding processing w ith improved input .
Key words :im ag e seg mentatio n ; anisotropic diffusion ; no nlinear scale space 自然场景图像一般比较复杂, 为便于分割, 应在保持图像重要特征的前提下抑制图像中的细节和噪声, 并增强图像中的重要边缘等不连续性信息. 传统方法是用高斯核卷积得到线性尺度空间, 但高斯函
数的低通特性导致边缘模糊和漂移. Pero na 和Malik 提出的各向异性扩散方程方法生成的是非线性尺度空间[1], 可以引入先验知识模型, 过程控制简便, 便于向高维扩展, 成为计算机视觉研究领域中的
收稿日期:20040601
基金项目:国家自然科学基金资助项目(60473049) 作者简介:彭启民(1969-) , 男, 博士生, E-mail :pengqm@h otmail. com. 贾云得(1962-) , 男, 教授, 博士生导师.
316
北京理工大学学报第25卷
一个热点. 但由于真实场景图像多为复杂背景, 具有非均质化的特点, 基于现有扩散方法的分割结果不理想[2]. 作者提出了一种非线性尺度空间中图像的分割算法, 根据图像表面的微分特性给出了扩散方程的二阶微分分解式及分解形式的正则化方法. 通过各向异性的局部扩散张量保持角点、交叉点等含有重要语义的特征, 对于经过预处理的图像采用形态学分水岭算法进行初始分割, 在各向异性扩散得到的非线性尺度空间中, 对获得的初始区域进行合并, 减少了形态学方法造成的过度分割.
量函数值的下降, 达到消除噪声、抑制细节的目的. 该方法可以用梯度法和变分法求解, 但速度慢, 且只对特定类型的图像效果显著.
2 基于微分几何性质的定向扩散
实际应用中, 若单纯依靠梯度模计算扩散系数, 可能导致图像中某些特征被错误地平滑, 例如, 对于视觉分析具有重要意义的角点通常都具有较大的梯度模, 若按常规算法, 则被赋予很快的扩散速度而逐渐消失, 因此有必要对图像中的变化情况进行更深入地分析.
根据微分几何的共形映射原理, 对图像的扩散处理可以看作曲面间的共形映射
i
[8]
1 各向异性扩散方程及其正则化
非线性扩散方程可以表示为
=Δ[c (x , t ) L ],(1) t 2
式中c (x , t ) 是值域为[0,1]的单调下降函数, 在边缘处取0值. 该方程最直观的思想是:在扩散过程中, 梯度小的地方具有较高的传导率, 而在梯度大的地方则相反, 因而具有在抑制图像细节的同时保持重要特征的良好特性. Pero na-Malik 使用了一个较快下降的各向异性算子,
g (| u |)=>0) 22, (λ1+| u |/λ
2
[1]
. 由于正则曲面S
的每点P (u ) 处有2个线性独立的坐标曲线的切向量r i (i =1, 2) 和一个法向量n , 根据曲面的第一、第二
i
基本形式, 可以确定曲面的基本公式的系数(k j ) , 用
来定义曲面上每点在切平面中的W eing r ten 变换(W-变换). 由于W-变换关于切平面中的内积是自共轭的, 因而有2个实特征值k 1, k 2, 且k 1≥k 2, 其对应的切平面的特征向量分别为e 1和e 2. 设T 为曲面S 上的任意单位向P 点切平面上与e 1的正向夹角为θ
量, 则根据Euler 公式, T 在θ方向的曲率为
W )==k (θ(T , T )
(W (e 1cos θ+e 2sin ) , e 1cos θ+e 2sin )=θθ
+k 2sin θ. k 1cos θ
2
2
(2)
式中λ为扩散阻止的梯度阈值. 当梯度小于等于λ
时, 扩散得到鼓励, 图像被平滑; 而梯度大于λ时, 扩散得到抑制, 边缘得到增强, 但此时系统将变为病态问题, 流函数不是单调的, 存在无数解, 因而缺乏稳定性[3]. 此外, 由于扩散限定在与梯度正交的方向上, 导致了在图像的平坦区域扩散效率较低.
现有的稳定方法可以分为以下两种:
第一种是正则化方法. 如Catte 等人通过对扩散结果进行卷积平滑, 即用g (| u e |) 代替g (| u |) , 其中u e =K e *u , 在空域实现了对原方程的正则化[4]. 又如Nitzberg 和Shiota 提出的时空域正则化方法, 是以牺牲对重要特征的保持性为代价的, 平滑掉了角点等特征, 随意性大, 较多地依靠个人的经验.
第二种是全局优化方法小化:
n I ∶K →R
(4)
可以验证, e 1(e 2) 的方向就是使点的法曲率达到最大(或最小) 的方向, 相应的法曲率k 1(k 2) 称为主曲率, 该形状算子对扩散过程是不变的, 使计算得以简化.
W-变换可归结为对图像二阶微分矩阵的计算:
G =
x y
2
22
2
. (5)
[5]
2
G 的2个特征值λ+≥λ-≥0分别为‖d I ‖的最大和
[6～7]
, 即目标函数的最
(3)
最小值, 其对应的特征向量u ⊥v 就是‖d I ‖2变化最大和最小的2个正交方向, 即灰度变化较大的方向和相关性较好的方向. 容易验证, 该2×2矩阵较大的特征值等于梯度模的平方. 分析λ+与λ-的关系, 有3种情况:
①λ+≈λ-≈0, 对应于平坦区域的点;
②λ+ λ-, 向量变化显著, 对应于边缘上的点; +0, .
min E (I )=
∫h (N (I ) ) d K ,
K
式中N (I ) 为与图像的局部变化有关的单调增函数.
把目标图像作为能量函数的解, 采用全局优化的方
第4期彭启民等:基于各向异性扩散的图像分割算法
317
[10]
首先根据图像表面局部变化特性决定的结构张量, 计算2个正交的方向u ⊥v , 用对应的特征值确定其权值c 1和c 2. 把一阶扩散方程改写为二阶形式, 则得到扩散方程的结构张量分解形式
1=c +c 2. t u v
2
2
区域合并的准则定义为
N (k )
E (K |K
k k -1
)=
∑∑
i =1p ∈K k
i
k
(K k -g k -1(p ) ) 2+λ|. K |i
k
(6)
(11)
k
式中:N (k ) 为在尺度k 上分割得到的区域数; K k 为i
i 的平均灰度; g 尺度k 上的区域K
k
k
k -1
由此看出, 扩散方程可以认为是2个相互正交方向上的一维扩散过程的复合, 即扩散过程由边缘的强度和方向共同决定
[9]
(p ) 为像素p 的
. 因此, 要保持边缘、角点等特
实际灰度; |K |为边界总长. 在不同的尺度上, 权值参数λ应根据该尺度上允许的区域数做相应的调整. 该函数的第一项保证获得正确的分割, 而第二项是为了惩罚过度分割. 若2个相邻区域的合并有助于降低该能量函数的值, 则执行合并, 否则比较下一个区域, 重复该过程直到任何合并都无法使上述能量函数的值减小, 则获得最佳分割.
征, 一是必须沿向量图像特征的路径扩散, 二是对扩散速度采用自适应策略进行调整. 正则化时, 显然必须禁止逆扩散, 同时为避免图像特征被模糊, 应该只允许边缘方向的扩散, 而禁止梯度方向的扩散. 因此, 上式中权值c 1和c 2应满足如下约束:
lim c 1=0, λlim λ λ λ
+
-+
-
c 1
=0, c 1≥0, c 2≥0. c 2
(7)
4 实 验
全部算法由Matlab 和V C ++6. 0混合编程实现, 并在Windo w s 2000环境下对所提出算法进行了验证. 图1为在北京理工大学校园内采集的一幅图像, 对该图像用本文提出的各向异性扩散算法处理, 结果见图2. 图3a 为对该幅图像进行分割的中间结果的边界及与原图叠加的效果. 最终结果的边界及
此外, 当无法确定图像几何性质时, 为提高扩散的效率应进行各向同性滤波, 即
λ→0
+
lim c 1=λlim c 2=T >0. →0
+
(8)
根据上述分析, 提出如下的局部各向异性系数:
T =
+-λ++-2
, 0≤T≤1,
2
(9)
可得到角点的强度C =(1-T ) ‖I ‖. 为保持角点, 扩散系数应与角点强度成反比变化; 而为了抑制对边缘的平滑作用, 可以为主曲率方向的扩散系数添
加系数(1-T ); 为了能够对噪声进行有效抑制, 还需根据估算的图像噪声水平为扩散系数增加一个鲁棒系数s . 最后得到权值系数
c 1=, c 2=, X >0.
C +C +(10)
图1 道路及汽车原图
Fig. 1 Th e original image of road and car
3 分割算法
形态学的分水岭算法最大的缺点是容易导致过度分割, 即使经过很好预处理的图像中仍然可能存
在一些虚假极小点, 造成分割结果过于琐碎, 增加了后续计算的难度. 改进的方法是根据预分割区域的邻接图进行区域合并. 由尺度空间的因果性可知, 较大尺度上的区域总是由较小尺度上的区域按与区域生长法类似的方法合并得到, 实现分割的同时也得到了图像中区域的分层表示.
根据非线性扩散方法, 从图像g 构造尺度空间中的一系列图像g (i =1, …, s ). 每次执行区域合并后
k k i
图2 各向异性扩散算法处理后的结果
Fig. 2 The diffused res ult u sing th e propos e alg orith m
与原图的叠加效果见图3b . 图4和图5分别为均值迁移(MeanShift) 和JSEG 算法的分割结果
[11, 12]
. 从测
318
北京理工大学学报第25卷
后续的图像自动识别和理解提供理想的输入
. 下一步要研究的内容.
参考文献:
[1] Pe ro na P , M alik J . Sca le -space a nd edg e de tec tion
using a niso tr opic diffusio n [J].IEEE Tr ans PAM I, 1990, 12(7):629-639.
[2] W eicke rt J . Fast pa rallel algo rithms for a br oad cla ss
of no nlinear va ria tio na l diffusio n approa ches [J].Real-Time Imaging , 2001, 7(1):31-45.
[3] Auber t G , Ko rnpro bst P. M a thema tical pro blems in
imag e
pro cessing :
PD E ' s a nd
the
calculus
of
v a ria tio ns [A ].
App M athem Sci [C ].
Be rlin :
(a)
中间结果
Spring er-V erlag , 2002.
[4] Catte F , Lio ns P L , M o r el J M , et al . Image selectiv e
smoo thing and edg e detectio n by no nlinear diffusion [J].N umer Anal, 1992, 29:182-193.
[5] Nit zberg M , Shiota T. N o nlinear imag e filtering with
(b) 最终结果
图3 道路及汽车图像分割合并过程的边界图及
其与原图像的叠加
Some s ample edge maps during region merging and F ig . 3
ov erlap
images
edg e and cor ne r enhancement [J ].IEEE Tr ans PAM I , 1992, 14:826-833. [6] Ta ng B, Sa piro G, Ca selles V. Diffusion o f g eneral
da ta o n no nflat manifolds v ia ha rmo nic maps theo ry:The directio n diffusio n case [J ].Visio n, 2000, 36(2):149-161. [7] Tschumper l ′e D,
Deriche R.
Diffusion PD E ' s on
v ecto r-v alued imag es [J ].
IEEE Signal Pr ocessing
J o urnal o f Comp
M ag azine , 2002, 19(5):16-25.
[8] 苏步青, 胡和生, 沈纯理等. 微分几何[M ].北京:人
民教育出版社, 1981. 79-102. Su Buqing ,
图4 M eanshift 算法的结果Fig. 4Th e res ult of M ean Sh
ift
图5 JSEG 算法的结果Fig. 5 The result of JS EG
Hu Hesheng , g eo metr y
Shen Chunli,
:Beijing
et al. People ' s
Differ ential
[M ].
Educa tio n Press, 1981. 79-102. (in Chinese) [9] K or npr obst P,
Derich e R, Co mpute r Lo pez C,
Auber t G. V ision M o r el J.
and
No nlinea r Pa ttern
opera to rs in ima ge r esto ra tio n [Z ].Confer ence
on
Recog nition, Puerto Rico , 1997. [10] Ko epfler G,
A multisca le
a lg orithm fo r imag e segmenta tion by va ria tio nal m etho d [J ].SI AM J N umer Anal , 1994, 31(1):282-299.
[11] Co maniciu D, M ee r P. M ean shif t :Ro bust approach
tow ard fea ture space a naly sis [J ].I EEE T ra ns on P AM I, 2002, 24(5):1-18.
[12] Deng Y N , M a njuna th B S. U nsuperv ised seg men-ta tio n of co lo r-tex ture regio ns in imag es a nd video [J ].I EEE Tr ans o n Pa tter n Analysis and M achine Intellig ence, 2001, 23(8):800-810.
Inter na tio nal
5 结 论
根据微分几何中共形映射的有关理论, 把原有的关于梯度的一阶扩散方程分解为关于表面曲率的二阶方程, 给出的正则化条件保证了扩散过程的稳定性, 提高了对各向异性扩散过程的控制能力. 实验结果表明, 采用分水岭算法进行初始分割后, 在非线性尺度空间中对过分割的初始区域进行合并的算法是有效的, 能够获得较准确的分割结果. 由于图像分割尚未有统一的评价体系, 还难以对有关算法做有效的量化比较. 如何提高该类算法的实现效率将是