小型微型计算机系统Journal of Ch inese Computer System s 2008年6月第6期V o l 129N o . 62008
种子区域生长技术在彩色图像分割中的应用
李唯为, 黄辉先, 张东波, 汤红忠
(湘潭大学信息工程学院, 湖南湘潭411105) E 2m ail :li w ei w ei 1223@yahoo . com . cn
摘 要:提出一种基于种子区域生长(Seeded R egi on Grow ing , SR G ) 技术的彩色图像分割方法. 该算法利用L 3a 3b 3颜色空间的象素与其邻域的颜色差异及相对欧式距离自动选择种子; 应用SR G 技术由已知的种子生长出初始分割区域; 根据融合了颜色空间和邻接关系的区域距离对初始区域进行分级合并. 算法克服了传统区域生长方法不能自动选择种子且容易导致过分割的局限性. 将新的分割方法应用到彩色图像, 并得到与视觉判断相一致的有意义的分割结果. 实验结果显示了所提出的方法对于不同自然彩色图像分割的有效性与适应性.
关键词:彩色图像分割; 种子区域生长; 区域合并; 欧式距离
中图分类号:T P 391. 41 文献标识码:A 文章编号:100021220(2008) 0621163205
Appl ica tion of Seeded Reg ion Grow i ng to Color I mage Segm en ta L IW ei 2w ei , HUAN G H ui 2xian , ZHAN G Dong 2bo , TAN G Hong 2(Colleg e of Inf or m a tion E ng ineering , X iang T an U n iversity , X )
Abstract :A co lo r i m age segm entati on p SR G m ethod . Seeds can be autom atically selected in the L 3a 3b 3co lo r space bo r and relative Euclidean distances in the new algo rithm ; the new m ethods of SR G is segm ented regi ons ; and the initial regi ons are h ierarch ically m erged based on the re 2gi on distance defined by lo r spatial and adjacent info r m ati on . T he p ropo sed algo rithm can overcom e the disadvantages of no t selecting seeds autom atically and leading to the result of over 2segm ented by the traditi onal SR G m ethod . A nd it can be ap 2p lied to co lo r i m age segm entati on successfully . T he m eaningful experi m ent results of co lo r i m age segm entati on ho ld favo rable . consistency in ter m s of hum an percep ti on and have show n feasibility and effectiveness to vari ous natural co lo r i m ages Key words :co lo r i m age segm entati on ; seeded regi on grow ing (SR G ) ; regi on m erging ; euclidean distances
1 引 言
图像分割是一种基本的计算机视觉技术, 是从图像处理到图像分析的关键步骤. 有效合理的图像分割能够为基于内容的图像检索、对象分析等抽象出十分有用的信息, 从而使得更高层的图像理解成为可能.
目前一般将图像分割技术分为4类:
(1) 阈值分割技术;
(2) 基于边缘的技术; (3) 基于区域的技术; (4) 混合技术.
基于边缘的技术主要是基于在边界上的象素值变化很快的特点. 现在成熟的算法中, 简单的有Sobel , Roberts , P rew itt 算子, 复杂的有Canny 算子. 目前的边缘检测算法得到的边缘结果仅仅只能用来作为候选边缘. 因为这些边缘一般都是不连续的, 但是实际的边缘都是闭合的曲线. 所以, 用一些后处理(如边缘跟踪、平滑和细化等等) 来得到闭合的边缘[425].
基于区域的技术主要利用同一个区域的相邻像素有共同的特点, 比如灰度值、颜色值和纹理等等[6]. 很显然, 这种方法的性能主要取决于所选的共同特点的标准, 即同类判据(ho 2mogeneity criteri on ) .
混合技术是一种结合边缘检测和区域生长的混合方法, 可以用来更精确地分割图像[728].
近年来, 彩色图像分割方法研究越来越为人们所重视. 由于彩色图像包含较多的有效信息量, 且给人以较直观的视觉感受, 因此对它的研究有利于克服传统灰度图像分割方法的不足, 是一个有着广阔前景的研究领域[9]. 由于区域生长法直
其中, 阈值分割技术主要是基于邻近的像素之间, 在某一个范围内有一些相同的特点. 对于只有两个相反部分的图像, 由于阈值分割技术忽略了图像信息之间的空间相关性, 可以得到很好的结果; 对于边界模糊的图像和有多个部分的图像, 这种技术是低效的[123].
收稿日期:2007202226 基金项目:湖南省自然科学基金项目(06JJ 5112) 资助; 湖南省教育厅基金科研项目(05C 093) 资助. 作者简介:李唯为, 女, 1982年生, 硕士研究生, 研究方向为图像处理; 黄辉先, 男, 1957年生, 博士, 教授, 研究方向为智能控制及其在城市智能交通系统中的应用、先进控制理论及其在工业自动化控制中的应用, 图像图形处理; 张东波, 男, 1973年生, 博士研究生, 副教授, 研究方向为粗糙集、神经网络、模式识别与处理; 汤红忠, 女, 1979年生, 硕士, 讲师, 研究方向为图像图形处理.
1164 小 型 微 型 计 算 机 系 统 2008年
接作用于颜色空间, 在分割过程中同时考虑了色彩分布以及其空域上的重新划分, 因此, 它较其他方法更适合于彩色图像分割[10]. 为了避免调整同类判据的参数, 种子区域生长(SR G ) 技术[11]选择了一系列初始种子来控制算法效果, 但这种通过人机交互确定种子的方法会导致种子点选择不准确. 实际上SR G 方法主要有两个难题:一是怎样自动选取初始种子, 二是怎样确定区域检测的顺序, 由此得到精确的图像分割区域.
本文针对以上问题, 在SR G 方法的基础上提出了一种简单有效的彩色图像分割方法. 该方法克服了传统区域生长方法不能自动选择种子且容易导致过分割的局限性, 在保证区域内部一致性的同时, 能够得到与人类视觉判断相一致的有意义区域的分割,
满足一般基于内容的图像检索或识别处理.
系统, 现在已成为世界各国正式采纳、作为国际通用的测色标准. 它适用于一切光源色或物体色的表示与计算. 笔者经过分析与比较最后决定使用L 3a 3b 3颜色空间模型, 因为它具有如下3个主要特性:
(1) 可用欧氏距离直接表达知觉差异(色差) ; (2) 均衡的彩色空间; (3) 与人类视觉的相似性. 在计算机中, 彩色数字图像的存储、显示一般均采用R GB 颜色空间模型, 则要将R GB 空间的图像转换到L 3a 3b 3空间, 如公式(1) 和(2) 所示[13]. 其中X 、Y 、Z 是物体的三刺激值; X 0、
Y 0、Z 0为C IE 标准照明体的三刺激值; L 3表示心理明度, a 3、
3
b 为心理色度.
L L
33
3
=116(Y Y 0) 1 -16 (Y Y 0>0. 01)
2 算法描述
本算法的基本流程如图1所示. 首先将彩色图像转换到
333
C IE 1976LAB (L a b ) 颜色空间; 其次结合象素与其邻域的颜色差异和欧式距离来确定种子象素; 然后给出适合L 3a 3
b 3颜色空间的同类判据, 应用SR G =903. 3(Y Y 0) (Y Y 0
3
(Y Y 0) 1 ]3( Z 0) 1 ]
3
a 3=500[(X X 0) 1 -3b 3=200[(Y Y 0) 1 (1)
X
Y Z
=
0. 0. 00. 00. 0100. 2000. 0110. R G B
(2)
:由X 、Y 、Z 变换为L 3、a 3、b 3时, 经过这种非线形变换后, 可用笛卡
图1 图像分割算法流程图
F ig . 1 O utline of the p ropo sed algo rithm
出待分割的区域;
在区域合并中, 融合颜色空间和邻接关系信息定义了区域距离, 并根据区域距离进行分级的区域合并, 最后输出处理结果. 下面介绍具体实现过程. 2. 1 颜色空间选取与转换
颜色空间是对颜色进行量化的空间坐标. 目前, 人们对于色彩的描述大致可分为三类模型:色度学模型、工业模型以及视觉模型. 具体来说, 有R GB 颜色模型、C M Y 颜色模型、YUV 颜色模型、H IS 颜色空间等等, 各种颜色空间从颜色特性的不同方面进行了量化描述[12].
由于不同的颜色空间模型反映了颜色不同方面的特性, 使用不同的颜色空间模型会对颜色的相似性比较有一定的影响. R GB 适合于显示系统, 但其并不适合于图像分割和分析. 因为R 、G 、B 3个分量是高度相关的, 即只要亮度改变, 3个分量都会相应改变, 而且, 由于R GB 是一种很不均匀的颜色空间, 所以两种颜色之间的知觉差异(色差) 不能表示为该颜色空间中两点间的距离. 1976年C IE (国际照明委员会) 推荐了新的颜色空间及其有关色差公式, 即C IE 1976LAB (L 3a 3b 3)
图2 L 3a 3b 3空间坐标系
F ig . 2 Coo rdinate of L 3a 3b 3space
儿直角坐标体系来表示光谱轨迹, 如图2所示. 在这一坐标系统中, +a 3表示红色, 2a 3表示绿色, +b 3表示黄色, 2b 3表示蓝色. a 3和b 3的取值范围均是-120～120, L 3的取值范围是0～100.
2. 2 种子自动选择算法
在种子点的自动选择中, 必须满足以下三条准则:(1) 种子与其邻域必须有高相似度;
(2) 在想得到的区域内, 至少要能产生一颗种子; (3) 不同区域的种子不能连接.
本文按如下方法计算象素与其邻域的相似度. 在3×3的邻域中, 分量L 3、a 3和b 3的标准差为:
Ρx =
9
9
θ) 2
(x i -x ∑i =1
(3)
θ3
x i 为L 、a 3或b 3, 其平均值x =
9
x i , 则总的标准差为:∑i =1
9
Ρ=ΡL 3+Ρa 3+Ρb 3
(4)
6期 李唯为等:种子区域生长技术在彩色图像分割中的应用
Step 6. 输出处理结果.
(5)
1165
将标准差归一化到[0, 1]区间内, 则:
ΡN =Ρ Ρm ax 其中, Ρm ax 为图中标准差的最大值.
则象素与其邻域的相似度为:
H =1-ΡN
说明:在Step 3, 数组T 中的象素还未被归入任何区域, 但至少与一个区域S i 相邻. 象素j 与其相邻区域的相对欧氏距离
d j 由式(9) 计算:
(6)
d j =
定义候选种子象素必须满足的条件1:候选种子象素与其邻域的相似度H 必须大于阈值T s .
另外, 本文按式(7) 计算某象素与其邻域的相对欧式距离(在L 3a 3b 3空间) :
d i =
3
23232222
(L 3(a 3(b 3j ) +j ) +j )
(9)
(L , a , b ) 表示区域的分量L 3、a 3或b 3的平均值.
在Step 4, 是将T 中与其相邻区域具有最小距离量的象素提取出来. 若多个象素有相同的最小距离量, 则考察其相邻区域的大小, 若象素p 的相邻区域最大, 则将p 提取出来. 若对象素p 的多个邻接区域来说, p 到它们的距离相同, 则将p 归入最大的区域. 2. 4 区域合并
很可能由于过多种子的产生, 在区域生长过程中一同质区域就会被分割为多个区域, , 对于差别不是很明显的区域, .
, 距离度. 两:两个区域在颜色上相近, 空间. 于是融合了颜色和邻接关系信息, 式(10) 给出了两个区域的距离定义.
区域距离:
d r (R i , R j ) =d c (R i , R j ) ∃ij
3
222
33333(L ) +(a ) +(b ) i =1, 2, …, 8
3
2
3
2
3
2
, (7)
从实验效果来看, 采用相对欧式距离比标准欧式距离要
好. 本文按式(8) 计算某象素与其邻域的最大距离:
d m ax =m ax (d i )
i =1
8
(8)
由d m ax 可定义候选种子象素必须满足的条件2:候选种子点象素与其邻域的最大距离d m ax 必须低于阈值T d .
若象素满足上述条件1和条件2, 则将其归为种子象素. 本文运用O tsu 方法(大津法) [14]自动得到条件1T s 22表示类间方差, Ρw 表示类内方差s ΡB
22 为最大. d 0. ΡB Ρw
了一个小一些的值, , 那么某些目标物体不能被分割出来, , 从而导致非同质区域的连接.
若多个种子点象素相连通, 则将之视为一个种子. 因此, 生成的种子可以是一个象素也可以是包含多个象素的区域. 条件1可检查种子象素与其邻域是否具有高相似度; 条件2则可保证种子没有在两个非同质区域的边界上. 2. 3 分割算法
令A 1, A 2, …, A i 表示初始种子, S i 指示与A i 相对应的区
(10)
其中, d c (R i , R j ) 和∃ij 代表两个区域的颜色距离和邻接关系, 定义如下:颜色距离:
d c (R i , R j ) =
r i + r j
L
2
j
m in (
222
L
2
i 22
+a +b , i i 22
) +a +b j j
(11)
域. 则分量L 3、a 3或b 3在区域S i 所有象素的平均值表示为
(L , a , b ) . 分割算法如下:
Step 1. 自动选择种子.
Step 2. 将每个种子区域标上不同的label 值.
Step 3. 将所有种子区域的邻域象素记录在数组T 中, 按
邻接关系:
∃ij =
1. 0+∞
if r i is adjcent to r j if r i is no t adjcent to r j
(12)
其中, r i 和 r j 分别代表区域i 和j 中包含的象素个数.
式(10) 中分子部分 r i 和 r j 的乘积使得包含象素数目较少
的区域和其他区域的颜色距离减小, 从而在颜色的相对欧式其与区域距离的大小升序排列.
距离相同情况下, 有利于小区域的优先合并, 使得分割结果更Step 4.
符合人们的视觉特性. ∃ij 用来表示区域r i 和r j 之间是否有邻(1) 当T 非空, 将其中第一个象素p 取出并检查p 的4-接关系, 如果存在邻接关系, ∃ij 取值为1. 0, 否则取值为+∞, 邻域. 如果p 所有被标记的4-邻域象素拥有的是相同的la 2
此时的区域距离也为+∞. bel , 则将p 归为具有此label 值的区域; 如果p 被标记的邻域象
区域合并过程为:计算所有相邻区域的距离d r (R i , R j ) , 素的label 不同, 计算p 到这些具有不同label 的邻域的距离,
存放到距离表中, 将距离最短的区域合并; 重新计算新区域与与哪个区域的距离最小, 就将p 归为此区域.
其相邻区域的距离, 并将距离表更新; 重复上述过程, 直到最(2) 更新新区域象素的平均值(L , a , b ) ; 将象素p 的
短距离超出阈值T r . 最后, 检查所有区域内的像素点个数, 如42邻域中未被归类于任何区域也未列入T 的象素按升序记录
果一个区域内的像素点个数在图像中所占的比例小于图像的在T 中.
(3) 重复(1) 和(2) , 当遍历完全图象素, 分割也就完成1 150, 该区域也将合并到最相似的相邻区域中.
在图3, 将本文分割算法与文献[7]的JSEG 算法对彩色了.
图像的分割结果进行了比较. 图3(a 2) 和(b 2) 是本文分割算法Step 5. 运行区域合并算法.
1166 小 型 微 型 计 算 机 系 统 2008年
对图3(a 1) 和(b 1) 的分割结果, 图3(a 3) 和(b 3) 是JSEG 算法对图3(a 1) 和(b 1) 的分割结果. 可见, 与JSEG 算法相比, 本文分割算法能更好地克服过分割问题, 且能得到与人类视觉判断相一致的有意义的分割结果
.
域生长和区域聚合. 在种子自动选择中, 计算标准差和相对欧式距离, 每个象素需要O (n ) , 其中n 是图像总的象素数. 在区域生长中, 每个未归类的象素要插入数组T 一次, 而检查其相邻区域和计算距离可在持续时间段进行; 将一个象素插入数组T 需要log (n ) , 所以区域生长需要O (nlog (n ) ) . 在区域合并阶段, 计算区域间的差异需要O (m 2) , m 是区域的数目; 计算所有区域的大小需要O (n ) , 一般来说, m 远小于n ; 为了合并两区域, 要给这两个区域标上标上不同的label 值, 并计算两者之间的距离, 因此需要O (n +m ) ≈O (n ) 来合并两个区域. 那么区域合并的时间复杂度是O (m 2+n +m n ) ≈O (m n ) . 因此本文分割算法总的时间复杂度是O (n +nlog (n ) +m n ) ≈O ((m +log (n ) ) n ) .
4 实验结果及总结
用本文提出的算法, 对120内容的分割. 11. 9%, 低于JSEG 方14. 图4.
. 该3; 应用SR G 技术由已知的种子生长出初始分割区域; 根据融合了颜色空间和邻接关系的区域距离对初始区域进行分级合并.
算法克服了传统区域生长方法
3 算法时间复杂度分析
, 区
不能自动选择种子且容易导致过分割的局限性. 将新的算法特征融入算法中, 提高分割性能, 是今后进一步的研究重点. 应用到彩色图像分割, 在保证区域内部一致性的同时, 能得到
References :
与人类视觉判断相一致的有意义区域的分割, 满足一般基于
[1]Kurugo llu F , Sankur B , H ar m anciA E . Co lo r i m age segm enta 2
内容的图像检索或识别处理. 本文提出的算法也存在不足之ti on using h istogram m ulti 2th resho lding and fusi on [J ]. I m age 处, 对于具有高彩色纹理(例如含有很多小的目标物体且混有and V isi on Computing , 2001, 19(13) :9152928. 多种色彩) 的图像, 由于平均值不能很好表达区域的性质特[2]SezginM , Sankur B . Survey over i m age th resho lding techniques 点, 很可能得不到好的分割效果. 如何更好地将图像的纹理等and quantitative perfo r m ance evaluati on [J ]. Journal of E lec 2
6期 李唯为等:种子区域生长技术在彩色图像分割中的应用
119121203.
1167
tronic I m aging , 2004, 13(1) :1462165.
[3]Saha P K , U dupa J K . Op ti m um i m age th resho ld via class un 2
certainty and regi on homogeneity [J ]. 706.
[4]Zhang Yu 2jin .
I m age engineering ( ) i m age analysis (second
editi on ) [M ]. Beijing :T singhua U niversity P ress , 2005. [5]Zhang A i 2hua , Yu Sheng 2sheng , Zhou J ing 2li . A local 2th resh 2
o ld segm ent algo rithm based on edge 2detecti on [J ]. M ini 2M icro System s, 2003, 24(4) :6612663.
[6]T rem eau A , Bo lel N . A regi on grow ing and m erging algo rithm
to co lo r segm entati on [J ]. Pattern R ecogniti on , 1997, 30(7) :119121203.
[7]D eng Y , M anjunath B S . U nsupervised segm entati on of co lo r 2
texture regi ons in i m ages and video [J ]. 810.
[8]Fan J , Yau D K Y , E l m agar m id A K , et al . A utom atic i m age
segm entati on by integrating co lo r 2edge extracti on and seeded re 2gi on grow ing [J ]. IEEE T ransacti ons on I m age P rocessing , 2001, 10(10) :145421466.
[9]L in Kai 2yan , W u Jun 2hui , Xu L i 2hong . A co lo r i segm entati on techniques [J ]. I 2005, 10(1) :1210.
[10]T rem eau A , Bo rel N and m erging algo rithm
to co lo r segm entati on []. Pattern R ecogniti on , 1997, 30(7) :
IEEE T ransacti ons of
Pattern A nalysis and M ach ine Intelligence , 2001, 23(8) :8002
IEEE T ransacti ons on
Pattern A nalysis and M ach ine Intelligence , 2001, 23(7) :6892
[11]A dam s R , B ischof L . Seeded regi on grow ing [J ]. IEEE T rans 2
acti ons on Pattern A nalysis and M ach ine Intelligence , 1994, 16(6) :6412647.
[12]J iang Su 2rong, W ang Song, Fen Gang . i R GA :A n i m p roved re 2
gi on grow ing app roach fo r co lo r i m age segm entati on [J ]. Com 2puter Engineering and A pp licati on , 2003, 39(7) :96297.
[13]H u Rong , Chen J ian . A dap tive m esh i m age segm entati on fo r se 2
m i 2autom atic video object extracti on [J ]. Journal of D ata A c 2quisiti on &P rocessing, 2001, 16(4) :4692472.
[14]O tsu N . A th resho ld selecti on m ethod from gray 2level h is 2
togram [J ]. IEEE T ransacti ons on System s , M an , and Cyber 2netics , 1979, 9(1) :62266.
附中文参考文献:
[4]章毓晋. 图像工程(中册) 图像分析(第2版) [M ].北京:清华大
学出版社, 2005.
[5]张爱华, 余胜生, 周敬利. 法[J , 24(4) :6612663.
[9, , . [J ].中国图象
, 1:1210.
[], 王松, 冯 刚. I R GA :一种改进的区域生长彩色图像分
割方法[J ]. 计算机工程与应用, 2003, 39(7) :96297.
[13]胡 荣, 陈 健. 用于半自动视频对象提取的自适应网格图像
分割[J ]. 数据采集与处理, 2001, 16(4) :4692472.