（应用数学专业论文）基于子对象空间结构的roi图像检索.pdf

基于子对象空间结构的r o l 图像检索 基于子对象空间结构的r o i 图像检索 专业：应用数学专业 硕士生：邹卫文 指导老师：冯国灿教授 摘要 随着数码产品进入人们的日常生活，数字化图片的数量正以指数级速度增长。 如何有效地管理巨量的数字图片成为人们关心的话题。因此从大量的图像数据中快 速地检索满足用户要求的图像具有十分重要的现实意义。传统的基于内容的图像检 索系统通常使用低层次图像特征：颜色、纹理、形状等特征。这些特征不能满足用 户的高级检索需求，因此开发一种贴近用户的、高效的图像检索系统势在必行。 本文提出一种基于图像予对象的空间结构的r o l 图像检索系统。在传统检索 系统所使用的颜色、纹理、形状等特征的基础上，文章提出一种高层次的图像特 征：图像中子对象的空间位置关系。该特征具有很高的稳定性，对于平移、旋转、 缩放等变换能够保持不变性。利用此特征本图像检索系统不但可以从整体上理解图 像，也可以从语义的角度对图像进行理解，从而完成一系列高级的图像检索。同 时，本系统利用r 0 l 技术与用户进行交互，在分析的基础上把图像分为用户感兴 趣区域和非感兴趣区域。利用区域的划分，检索系统能够减少图像| i 无关信息对检 索性能的干扰，提高检索性能。实验结果表明本系统不但具有很好的稳定性：对平 移、旋转和缩放等变换具有不变性，而且本系统能完成查找具有特定1 1 扛司位置关系 对象的图像。 本文的主要工作如下：综述了图像检索技术的发展状况，介绍常用的三种图像 特征，并在此基础之上提出一种新的图像特征一一予对象空间结构特征。新的特征 和传统的图像特征结合，在r o l 图像检索系统的基础上实现了一个基于空间结构 的图像检索系统。实验证明此图像检索系统与现在的系统相比能更好地实现空间结 构关系的查找。 关键词：r o l ，c b 瓜，图像检索，空间关系，图像分割，主颜色 基于子对象空间结构的r o l 图像检索 r o ii m a g er e t r i e v a lb a s e do n o b j e c t s s p a t i a l s t i r i l c t u r e m a j o r ：a p p l i e dm a t h e m a t i c s n 锄e ：z o uw e i w e n s u p e i s o r ：p r 0 f e n gg u o c 锄 a b s t r a c t w i t ht h ed e v e l o p m e n to fd i g i t a lc a m e r a ，t h ed i 西t a li m a g e si n c r e a s er a p i d l y h o wt o m a n a g et h eg i 柚to fd i g i t a li m a g e si sac h a l l e n g i n gp r o b l e m 1 t sv e r yi m p o n a n tt o r e t r i e v et h ei m a g ew h i c hu s e fi si n t e r e s t e di i l 蕾r o mad e a lo fi m a g e s t h a t sw h ys om 柚y r e s e a r c h e r sf o c u so ni m a g er e t r i e v a lt e c h n i q u e h o w e v e r ，m o s to ft h ee x i s t i j l gi m a g er e t r i e v a ls y s t e m su s el o w l e v e lf e a t u r e s ：c o l o f ， t e x t u r e ，s h a p e 锄ds oo n 1 nt h i sp 印e r ，w ep r o p o s ean o v e lt e c h n i q u et 0d e s c 曲et h e s p a t i a lr e l a t i o n s h i pb e t w e e no b j e c t si ni m a g e a n dt h i sd e s c r i p t i o ni sr o t a t i o n - i n v a r i a n t ， s c a l e i i l v a r i a n ta n ds h m i n v a r i a n t t h e e x p e r i m e n t s s h o wt h i st e c h n i q u eh a sg o o d p e r f b 舯a n c e i i lt h i sp a p e r ，r o lt e c h n i q u ei su s e dt oi m p r 0 v et h ep e f f o 姗a n c eo ft h e i m a g er c t r i e v a ls y s t e m t h i sp a p c rc o n s i s t so ft h r e ep a n s f i r s t l y ，w es u m m a f i z et h ei m a g er e t d e v a l t e c h n i q u ea n dd e s c r i b el h e t h r e ei m a g ef e a t u r e s ：c o l o r ，t e x t u r ea n ds h a p e t h e n ，w e p r o p o s ean o v e lt e c h n i q u et o d e s c r i b et h es p a t i a ls t r i l c t u r eo ft h eo b j e c t si ni m a g e s f i n a l l y ，c o m b i n i n gn e w f e a t u r e 锄dt h eo t h e ff e a t u r e s ，t h i sp a p e rc o n d u c t st e s t so fi m a g e f e t r i e v a lb a s e do nr o l t e c h n i q u e t h er e s u l t ss h o wt h ep f o p o s e df e a t u f ec 锄i m p r o v et h e p e r f o m a n c eo fr e t r i e v a ls y s t e m k e y w o r d s ：r 0 l ，c b i r ，s p a t i a ls t m c t u r e ，s e 母n e n t a t i o n ，d o m i l i 锄tc 0 1 0 r 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指 导下，独立进行研究工作所取得的成果。除文中已经注明引 用的内容外，本论文不包含任何其他个人或集体已经发表或 撰写过的作品成果。对本文的研究作出重要贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的 法律结果由本人承担。 学位论文作者签名：却丑乞 日期：捌萨朋弓口日 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规 定，即：学校有权保留学位论文并向国家主管部门或其指定 机构送交论文的电子版和纸质版，有权将学位论文用于非赢 利目的的少量复制并允许论文进入学校图书馆、院系资料室 被查阅，有权将学位论文的内容编入有关数据库进行检索， 可以采用复印、缩印或其他方法保存学位论文。 学位论文作者签名：奸哆生 日期：脯朔矽日 导师签名：妈聃 日期：毋卅年6 月 o ( f ) 或h d ( f ) = o ( 2 - 7 ) ( 2 - 8 ) 若把直方图看成是高维空间中的一点，那么两直方图之间的相似度可以通过高 维空间中的两点所成角度表示。定义与的相似度如下： 以驴c o s 船矧 ( 2 - 9 ) 4 、直方图二次型距离 以上三种直方图相似度的描述都存在一个缺陷：用机械的欧氏距离来描述相似 度。直方图二次型距离可以克服上述缺陷。其定义如下 d ( ，) = ( 一) 么( 一) ( 2 1 0 ) 其中彳= ( 嘞) 为非负定二型，表示直方图中第f 类颜色和第类颜色的相似 度。显然，= 口。且吒= 1 。s c h e n i n i 等人提出了两种计算a 的方法【1 9 】： 嘞一一： ( 2 - 1 1 ) 。 m a ) ( ”【口，j 其中以表示在m u n s e l l 颜色空间【4 8 2 0 】的距离。或： 嘞：e x p ( 一仃( 乒) 2 ) ( 2 1 2 ) 嘞2 e x p ( 一仃芒2 ) ( 2 1 2 ) 其中仃为其一正数。 除了上述的方法外，下面介绍别一种特殊的二次型距离：m a l l a l a n o b i s 距离， 也称马氏距离。马氏距离的二次型矩阵么是通过直方图样本的协方差矩阵给出，即 彳= 。在这里，直方图可以看成是来自某一总体的一个样本，而这里的协方差 矩阵正基于这一类直方图样本的。 基于予对象空间结构的r o i 图像检索 m mq b i c 系统使用的就是二次型距离。二次型距离在实际使用中计算复杂性 比前三种方法复杂很多，不过二次型距离可以更好地利用人们对图像的先验信息。 直方图原理简单，算法简单，而且具有很好的平移，旋转，尺寸缩放等不变 性，是十分理想的颜色特征。但是，直方图对下面的颜色的偏移会产生较大的误差 【1 9 】。如图2 - 3 ： ( a ) 图2 3 ( a ) 直方图差异小但是视觉差异大； ( b ) ( b ) 直方图差异大但是视觉差异小； 图2 - 3 ( a ) 、( b ) 分别表示两组直方图心。如图所示，( a ) 组两直方图日q 差异比起( b ) 组中对应的两上方图差异小，但是从视觉解度( a ) 组的差异明显比( b ) 组 大。因此直方图对于灰度的平移( 光照影响) 是敏感的。 2 2 3 、主颜色描述子 2 2 3 1 主颜色 主颜色，也称主色。对于一张图像，少数的几颜色已经可以近似地描述图像 的颜色信息。而主颜色正是于此基础上发展出来的，用来描述图像局部的显著的颜 色特征。本文所使用的主颜色，是基于m p e g - 7 【2 1 】【2 2 】中所描述的主颜色简化而成 的。根据m p e g 7 中所述，主颜色描述了图像中任意不规则区域中处于支配地位 的颜色信息。在给定的图像区域，原图像的颜色信息将会映射到包含少数具有代表 性的颜色( 即主颜色) 的颜色空间上，从而减少图像使用的颜色数而用少量的颜色 描述图像的颜色特征。主颜色描述子的提取过程可以看成是一个如下的函数： ：j x ，其中x = 缸ix = e ，k ) ，s ) ，( f _ l ，2 ) ( 2 1 3 ) 其中_ ，表示图像域，例如，是基于尺g 艿颜色空间的图像域，若f ，则f 为一尺 基于子对象空间结构的r 0 l 图像检索 图像。x 为主颜色空间，其具体定义如下：c ，表示第f 个主颜色，表示e 所占 的比重，矿表示其颜色方差，s 表示主颜色的空问一致性。m p e g 一7 规定图像中 任意区域最多可以有8 个主颜色，g ，只，k 和s 可以在对颜色聚类后求得。而采用 3 x 3 遮罩窗口【2 1 】【2 2 】( m a s k i n gw 协d o w ) 来统计具有同一主颜色的连通像素的个数可 以计算出s 。若对于给定的图像，称工= ( ，) 为，的主颜色描述子，厂的定义由( 2 一 1 3 ) 式给出。本文的颜色特征提取算法只使用到c ：l 和只两变量，因而可以简化对主 颜色的描述。定义以下新的函数： 厂：，哼x 其中x = 缸lx ； g ，只， ，o = 1 ，刀) ( 2 1 4 ) 对v f ，我们定义厂( f ) = x ，其它的定义与( 2 一1 3 ) 式相同。对于两个图像，屯，其主颜 色描述子分别是j r l ，屯，则定义颜色的相似性： s = 跏( ，f 2 ) = 忖一纠 ( 2 1 5 ) 其中跏( ，) 为一i l 专r 的函数。 2 2 3 2 主颜色的特征提取 从一张图像，中提取出主颜色描述子分为以下三步完成： l 、量化图像 一般来讲，存储在计算机上的图像多以r g 口空间为基础，但如果直接在r 上进行主颜色描述子提取，计算量是十分巨大的。因为现实生活中，不论是在 尺g 8 颜色空间中，还是在矿颜色空间中，图像的所包含的颜色是无穷无尽的， 以2 4 位的彩色图像计算，一幅图像最多会包含2 “种颜色，这远远超出了我们计算 能力，而这样的计算也是没有必要的。计算机存储和处理图像只能在有限维的空间 上操作，对图像进行量化是十分必要的。因此本文在已经量化了的尺数字图像 上再对图像进行二量化，以减少算法的复杂性。具体操作如下： 对于图像，脚是，在r 空间上的量化，k 为尺g b 空间上的再次量化。 设量化后的颜色空间为尺g 艿( ，g 6 ) ( 尺g b ( ，g 6 ) 颜色空间为重新量化的颜色 空间，其中r e d 有，级的灰度，e n 有g 级的灰度，b l u e 有6 级的灰度。) ，定义 函数丁： 基于子对象空间结构的r o i 图像检索 r ：k = 三：j ；： 哼k = 曼：! ；曼 其中q = ( q g m o d ( g ，6 ) ) ( ，g ，6 ) ，”m o d ”，” 的定义如下： m o d ：若而= ( 口l ) ，艺= ( 6 l 瓯) ；贝l j 而m o d x 2 = ( 哆m o d q ) 鞠薰蒸 阁慝二 ( 2 - 1 6 ) ( 2 1 7 ) ( b ) 图2 4 图像分块示意图：( a ) 原图；放大了的图像；图中每一个分块会产生一个主颜色描述子 对于一个图像，若直接对其计算其主颜色描述子，计算量是十分巨大的。 因此，本文将在分块图像上提取主颜色描述子。具体如下：对于图像，先把其分 成n 块f = u ，再每一个分块乃进行提取。 f ， 3 、主颜色统计 统计每一个分块的主颜色信息，生成主颜色描述子。嘞= g ( ) ，g 为乃的主 颜色描述子提取函数，其定义在( 2 1 9 ) 式中给出。通过计算每一分块的主颜色描述 田 基于了对象空间结构的r o l 图像检索 m 。雕吲 8 ， 特征。本文为了减少运算量，优化搜索速度，在计算嘞一g ( 毛) 时只保留主颜色描 述子中只最大的颜色分量c ： ，即： 嘞一g ( ) - c jl f 曰一m 觚( 弓l 弓厂( ) ) ( 2 - 1 9 ) 厂( 瓦) 的定义由式( 2 1 4 ) 给出。 2 3 图像特征：纹理 2 3 1 图像纹理的定义 纹理是图像重复出现的视觉特征。图像纹理特征是所有视觉表面包括云层树木 织物等都具有的一种视觉特征。纹理的一语含义广泛，至今没有公认的定义。一般 认为纹理是图像各像素灰度的空间分布的一种感观描述，它是纹理基于元按某种特 定的方式或某一统计规律排列所组成的视觉感观，具体表现为平滑性、均一性、粗 糙情和复杂程度【2 3 1 。像颜色特征一样，它包含图像质地和结构等重要信息。纹理 特征在图像检索中也是非常有效的描述予，而且对没有颜色的图像或者同颜色不同 纹理的图像检索纹理显得特别重要。 2 3 2 纹理的特征 2 3 2 1 基于统计特征的纹理度量 图像的纹理特征可以通过统计特征来描述。这些统计特征包括能量、熵、对比 度、相关性等。它们不是直接从图像得出的统计特征，通常是图像的灰度步长 基于予对象空间结构的r o i 图像检索 ( g r a yv a 】u e 埘n1 e n g t l l ) ，灰度值差异( g r a yy a l u ed i 恐r c n c c ) ，或者灰度共生矩阵 【2 4 1 的统计特征。以下就共生矩阵做出详细说明。 对于灰度共牛矩阵p ，p o ，) 是指对于指定的步长l 和方向d 所有满足此步长 和方向的像素点对为a ，_ ) 的频率。一般来讲对于2 5 6 级灰度( 0 2 5 5 ) 的图像，对于 指定步长l 和方向d ，它的共生矩阵的维数为2 5 6 幸2 5 6 维。对于颜色图像，本文把 颜色图像转化为灰度图像，然后通过求灰度共生矩阵的方法求出。 对于一级灰度的灰度图，其2 维的共牛矩阵必然使计算复杂化，而且对于 不同的方法和不同的步长会产生不同的2 维共生矩阵，直接对共生矩阵进行计算 不现实。h a r a l i c k ，r m 提出了共生矩阵的1 4 个统计量作为描述共牛矩阵的统计 量，用以对共生矩阵特征进行提取，并达到降维的目的【2 4 1 。本文只介绍其中的5 个较为常用的统计量。 l 、能量( e n e r g y ) 绷e 呦一尸2 0 ，) ( 2 - 2 0 ) 能量是纹理的一致性的度量，也就是像素对的重复性。如果图像各个像素点的 灰度值相对接近，或者几乎所有指定方向d 和步长l 的情况下两个端点的灰度值 对a ，) 都一样，那么共生矩阵p 就会只有几个元素接近1 ，而绝大多数元素接近或 等于0 。在这种情况下，共生矩阵的能量将接近它的最大值1 。因此，当能量越 小，图像的纹理特征越复杂，反之当能量越大图像纹理就相对简单。 2 、熵( e n t m p y ) 。 绷f ；一耶，洲o g ( 邓，_ ) ) ( 2 2 1 ) 熵反映的是图像的无序性。如果图像不是纹理一致的，那么共生矩阵尸的绝大 多少元素都非常小，由上式可知此熵会十分大。例如，考虑一幅各个像素点的灰度 值是随机牛成的图像，那么p o ，_ ) 与随机模型一致。当选用均值分布的随机模型， p o ，j ) 为常数。这时熵就达到最大值。 3 、对比度( c o n t m s t ) 咒加盯一罗罗耶，j ) - ( f j ) 2( 2 2 2 ) - ，厶、。7 、 7 对比度是灰度共生矩阵主对角线附近的惯性矩，它度量矩阵的值是如何分布和 基于予对裂字间结构的r 0 l 图像检索 图像中局部变化的多少，反映了图像的清晰度和纹理的沟纹深浅。纹理的沟纹深， 对比值大，效果清晰；反之，对比值小，则沟纹浅，效果模糊。 4 、相关性( c o r r e l a t i o n ) 鲫= 盹抄掣 相关性是用来描述矩阵中行或列元素之间相似程度的，它是灰度值线性相关的 度量。【2 5 】 5 、同质性( h o m o g e n e 姆) h 。m * 粥 它度量图像纹理局部变化的多少。其值大，则说明图像纹理的不同区域间缺少 变化，局部的相似性高。 对于同一图像，步长l 的共牛矩阵，按一定的顺序排成一向量，称为共生矩 阵的特征向量= 【鲫p 恻，c 彻f ，口甜，c d ，五伽】。对于不同的d 与l ，取d 为四方向， l = 24 。则可以产生8 个共生矩阵。而把8 个共生矩阵的特征向量组合在一起组成 一向量，得到一3 2 维向量 r 叫疋乏删互疋e 瓦l 附l e l 】( 2 2 5 ) 其中下标n ，w n ，e n ，e 分别表示0 。，4 5 。，9 0 。，1 3 5 。本文使用此3 2 维向量作为图像纹 理特征。 对于两纹理特征互，互，定义图像纹理距离： c 抛f 把砌。= ( 互一是) 讳；( 互一互) 1( 2 - 2 6 ) 其中孵是一3 2 木3 2 维的对角阵，表示每一个特征分量的权值。本文取孵= i 。 2 3 2 2 基于时频分析的特征描述 图像，( f ，歹) 是一标准的纹理，那么，o ，歹) 可以看成为一个周期函数。时频分析 也是基于此质性发展而来的。其主要思想是把图像通过变换转化到频域，然后再在 频域上提取其特征。其中主要有傅利叶频谱法，g a b o r 小波变换表示等。 1 、傅利叶频谱法 基于子对象空间结构的r o i 图像检索 对灰度图像，o ，_ ) 做傅利叶变换： f ( “，1 ，) = r ，( x ，y ) e 2 州“训蛐 ( 2 2 7 ) 其中f ：一1 ，定义频谱： 风：f 户( 2 2 8 ) 则风一定情度上描述了纹理的粗糙程度。当纹理十分粗糙时，而会有明显的峰 值；而当纹理细腻时，乃不存在明显的峰值【1 】。 2 、g a b o r 小波变换法 g a b o r 过滤器提取纹理特征主要基于如下因素：g a b o r 表示法在减少空间和频 率的两维联合不定性方面是最优的；这些过滤器可以被看作方向和尺度可调的边缘 和线条探测器；而给定区域微特征的统计特征又常用来描述基本的纹理特征。 g a b o r 特征表示常被用于包括纹理分类和分割、图像识别和运动检测等多种图像分 析应用中。 在小波表示中，s m i t h 和c h a n g 等提出用小波子带的统计量【2 6 】( 均值和方 差) 作为纹理表示。 2 4 图像特征：形状 形状特征是图像的中级特征，理论上说图像的形状特征对于图像检索系统有极 其重要的帮助。但由于形状特征有着非稳定性，而在计算形状相似度也没有十分好 的方法，因而在实际使用过程中，形状轮廓参数常作为图像检索的辅助参数。 通常，形状表示方法可分为两类：一类是基于边缘的形状表示；另一类是基于 区域的形状表示。而关于形状特征的描述方法也有几种：傅里叶描述了，利用傅里 叶变换的边界作为形状特征；不变矩描述予，利用基于区域的矩作为形状特征；有 限元素法、旋转函数、小波描述予等等。基于形状的图像检索的应用丰要有商标图 像检索，指纹图像检索，建筑图纸检索，机械图纸检索和医学图像检索等方面。 同时，形状匹配和形状相似度计算的算法一般需要消耗大量的计算资源，特别是 a s m ，s n a k e 【2 7 】等方法对计算机资源的消耗十分大。本文在平衡算法复杂度和图 像检索性能的基础下，提出了一种基于p c a 的图像形状特征描述方法。 基于了对象空间结构的r o i 图像检索 对于图像中的图形s ，通过p c a 计算可以得到图形的两个主方向( d 1 ，d 2 ) ，主 方向的大小决定了图形大致的形状。因此得到描述形状特征的二维向量 s = 【凡九】。其中a 九分别为p c a 的两个特征值。形状的距离就可以通过下式给 出： 郎：) = 陪剖 ( 2 - 2 9 ) 实验证明，式( 2 2 7 ) 给出的形状特征虽然简单，但能有效地判别三角形，正方形等 形状。 基于子对象空间结构的r o i 图像检索 第三章图像分割算法及其改进 3 1 图像分割的意义 图像分割是一种重要的图像分析基础技术。在对图像的研究和应用中，人们 往往仅对图像中某些部分感兴趣。这些部分常称为目标或前景( 其他部分称为背 景) ，它们一般对应图像中特定的、具有独特性质的区域。为了辨识和分析图像中 的目标，需要将它们从图像中分离提取出来，在此基础上才有可能进一步对目标进 行测量和对图像进行利用。图像分割就是把图像分成各具特性的区域并提取出感兴 趣的目标的技术和过程。 对于图像理解来讲，图像分割极其重要。正确的图像分割是图像理解的前提。 3 2 常用的图像分割方法 文献【2 2 】介绍了四大类图像分割方法，分别是：基于图像像素的图像分割法， 基于区域的图像分割方法，基于边缘的图像分割方法和基于物理模型的图像分割方 法。虽然图像分割的方法种类很多，对于某一类特定的图片会存在一种特定的图像 分割方法，但是没有任何一种图像分割方法可以很好地对所有种类的图像进行分 割。 3 2 1 基于图像像素的分割方法( p i x e lb a s e d ) 基于图像像素的分割方法常用的一种图像分割方法，因为其算法复杂性低，理 论直观并且简单，常被采用。基于像素的分割方法按对像素的处理方法不同大体上 可以分为两类：其一是利用直方图阈值进行分割；其二是利用聚类的方法进行分 割。 基于直方图的方法的大体思路是通过分析直方图中的极大值与极小值的位置， 利用一系列先验知识计算出颜色阈值，利用这一阈值进行颜色分类从而达到图像分 割的效果。 基于子对象空间结构的r o i 图像检索 o h l 卸d e r 等人提出一种基于直方图方法【2 8 】。此方法主要通过查找直方图中的 峰值作为分割的阈值，然后用基于连通域选择的方法把图像分割成若干个区域。 o h t a 等人提出了一种基于颜色空间变换的直方图峰值分割方法：通过k l 变换把图 像从尺g 曰颜色空间转化到，。，：，3 图色特征空间，从而改进了o h l 柚d e r 的方法【2 9 】。 h o l l a 率先使用了2 维反色直方图，它把颜色转化到一基于两对反色红一绿黄一蓝 的颜盘中【3 0 】。这一方法使得其实使用了与人类视觉相似的颜色空间，从而提升图 像分割的精度。而l i l l 和c h e n 等人把图像从r 颜色空间转化到麟颜色空 间，利用册颜色空间的特性减少分割时因颜色空间所产生的误差。然后通过查 找直方图中的峰值计算出阈值，利用此阈值把分割技术应用在智能机器人汽车对公 路的识别上【3 1 】。 聚类方法从本质上是通过迭代的方法对样本分类，使得分类后预先设定的风险 函数或损失函数达到最小。如在k m e 柚s 聚类方法中，其损失函数就是总方差，当 在最小化总方差的同时k m e a n s 会产生与之相对应的图像分割结果。 k - m e a n s 聚类算法是一种最普遍的不断迭代调整k 个聚类质心的算法。设数n 个d 维数据 x ) 分属于k 个类别。每一类的类内方差和总方差分别为： 荟卜c 1 8 ( 3 - 1 ) c - t 荟卜q o ( 3 2 ) 其中4 是指属于第f 类的数据的下标，c ，是每一类的聚类中心。与其它的确聚类算 法相似，k - m e 锄s 算法的目标是最小化式( 3 2 ) 。以下为k 均值算法的步骤： ( 1 ) 适当选取k 个样本点作为k 个类别c l 气的初始聚类中心，令循环数i _ 0 ； ( 2 ) 计算样本点号与类别c 1 气之间的距离，把层分配给与其有最小距离的类c ， ( 1 气= k ) ； ( 3 ) 更新类的c ，聚类中心，按现在所有属于c ，的样本点的平均值来替代。 ( 4 ) 若i = n ( n 是预先设定的最大循环数) 返回到步骤( 5 ) ，否则令i = i + 1 返回到步 骤( 2 ) ； 基于子对象空间结构的r o l 图像检索 ( 5 ) 把最初在( 1 ) 中设定的k 个类别的中心按( 2 ) ( 4 ) 的处理进行更新，把现在的 聚类中心作为初始聚类中心，令i = 1 返回到步骤( 2 ) 。直到聚类中心不再被更 新为止。 实际操作上，同一类别的新旧两个聚类中心之间的距离小于某一预先给定的大 于零而远小于1 的阈值即可。本文所使用的图分割技术就是基于k - m e a n s 聚类算 法的。 从理论上分析可知任何现有的聚类方法都可以应用在图像分割上。而利用模糊 聚类的方法也是顺理成章的。模糊聚类是相对于一般的聚类方法来讲它是活动性更 高的聚类方法，它的聚类结果是得到一个每一个样本相对于每一类的隶属度。其中 f c m 算法( 模糊c m e a n s 算法) 是最广为使用的一种算法。t r i v e d i 和b e z d e k 使用 f c m 算法直接实现多谱图像( m u l t i s p e c t r a lh t l a g e s ) 的分割【3 2 】。而f c m 算法也常 常会结合基于直方图的算法一起组成图像分割算法。l i m 和l e e 使用直方图分析和 f c m 算法在尺g ! b ，圈眩，玎q ，l “v 等颜色空间中进行聚类，并通过把象素分到隶属 度最大的分类中，从而实现图像分割【3 3 】。 3 2 2 基于区域的分割方法( a r e ab a s e d ) 基于区域的分割方法丰要包括以下两类：一是区域生长法，二是分裂合并法。 区域牛长的方法是通过随机在图像中设定牛长种了，然后通过设定的牛长准则让种 子不断生长。本方法会在开始前设定停止牛长的条件，当种子遇到停止牛长条件时 就会停止生长。通过种予的扩长牛长，图像会被分成n 块，然后再对这n 个分块就 近进行分类合并，最后得到分割的图片。这种方法需解决两个问题：一是种子像素 的选择，二是区域生长准则的设计。由于生长准则的选取不仅依赖于具体问题本 身，且与所用的图像数据有关，若不考虑像素间的连通性和近邻性，会出现无意义 的分类结果【3 4 】。不同的停止生长条件和不同的分类合并准测会得到不同的区域生 长方法，而区域生长方法也常作为一基础算法与其它的算法结果一起组成新的图像 分割方法。 区域牛长的思想实质上是利用空间位置相邻的像素点往往具有很大的相似性 这一性质发展而来的。区域生长的形式多样，f e s h a r 描利用区域生长和 基于子对象空间结构的r o i 图像检索 k o l m 0 9 0 r o v - s m i n l o v 统计理论进行图像分割【3 5 】。m e y e r 利用分水领算法进行区域 生长，进而对图像进行分割【3 6 1 。 另一类基于区域的图像分割方法是分裂与合并法，它与区域生长方法类似， 不同的是此类方法首选通快速简单的方法先把图像进行粗略地分块，例如把图像分 为4 奉4 的1 6 个小块。然后对每一个分块进行判断，如果分块内包含两个或以上图 像区域的信息此分块继续进行划分；与此同时按给定的合并规则对分块进行合并， 最终达到图像分割目的。此类方法被誉为十分有前景的一种图像分害u 方法。 3 2 3 基于边缘的图像分割方法( e d g eb a s e d ) 基于边缘的图像分割是通过检测图像不同区域的边缘来进行分割。其丰要思想 是通过计算像素点与它相邻的其它像素点之间的差异，若差异达到某条件就认为它 是边缘。理论上它存在于目标与背景之间，是图像分割所依赖的最重要的特征。对 于边缘的检测常常借助于边缘检测算了进行，常用的边缘检测算了有：c a n n v 算 子、l a p l 扯e 算子、p r e w i t t 算予、s o b e l 算了、r o b i l l s o n 算予、硒r s c h 算了和r o b e r t s 算 子等。其中c a n n y 在1 9 8 6 年提出的c 柚n y 边缘检测是一种新的边缘检测算了【3 7 】。它 不容易受噪声的干扰，能够检测到真正的弱边缘，并且在进行c a n n v 边缘检测的同 时可以进行高斯( g a u s s i a n ) 滤波。因而c 觚n y 算了成为最广泛使用的边缘检测算子之 一【3 8 1 。不过基于边缘的分割技术依赖于由边缘检测算了找到的图像边缘，这些边 缘标示出了图像在灰度、色彩、纹理等方面不连续的位置。 常见的基于边缘的分割方法有：边缘图像阈值化、边缘松弛法、边界跟踪法、 作为图搜索的边缘跟踪法、作为动态规划的边缘跟踪法、h o u g h 变换法和基于边界 位置信息的边界检测法等【3 4 】。早在1 9 7 7 年，n e v a t i a 就利用h e u c k c l 算了和f 0 u r i e f 展开对图像进行分割，此方法提取的边缘是连续的f 3 9 1 。基于边缘的方法常会与统 计方法结合一起形成新的算法。d a i l y 通过对初始图像进行水平和垂直的边缘点检 测，而后结合边缘点和m a r k o v 随机场得到一种用于分割图像的能量函数。通过 h 0 p 矗e l d 神经网最小化能量函数，求出此时的边缘，从而达到图像分割的目的 【4 0 】。而d a i l y 的方法只需要提取出离散的边缘点即可。 基于子对象空间结构的r o i 图像检索 3 2 4 基于物理模型的图像分割方法( p h y s i c sb a s e d ) 这一类方法是在先验的物理模型上，通过对物体表面的物理特征( 颜色，纹理 等) 、光照条件、成像设备的光学特性等进行描述，并结合图像数据进行匹配，从 而达到图像分割的效果。这种花方法能比较好地处理由于光照等因素造成的图像亮 度变化，也能够识别阴影、光斑的影响，从而使分割在不同的光照条件下也可以得 到准确的和稳定的性质。 s h a n e 提出二分光反射模型( d i c h r o m a t i cr e 日e c t i o nm o d e l ) 【4 1 】。这模型将物体的 颜色定义为体反射和面反射分量的和。o n g 和m a t s u y 锄a 通过分析尺g b 空间数据 的分布确定反身分量，然后用统计主法抽取彩色聚类分量，进行二分光反射模型的 拟合f 4 2 】。 虽然基于物理模型的图像分割方法受到一定条件的限制，但是它从图像形成的 过程作为切入点，从较高层次的特征入手，改变了传统的依靠低层次特征和统计特 征方法的思维局限，引起人们的重视。 除上述的几大类方法外，现代的图像分割技术还包括基于数学形态学的方法， 基于微分方程的方法，基于变分法的分割方法、基于小波分析和变换的分割方法等 等【4 3 】。图像分割方法很多，但到目前为止，没有一种图像分割方法可以很好的地 分割所有种类的图像。 3 3 本文提出的彩色图像分割的方法 本文提出了一种基于聚类分割算法改进的聚类分割算法。实验表明此分割算法 与k m e a n s 和f c m 算法相比有更高的稳定性。 传统的k m e a n s 算法是通过最小化样本总方差从而计算出分类结果。从实验 结果表明直接通过k - m e a n s 对图像进行分割，有时会出现迭代过程中无法产生迭 代中心而中止。这是因为在图像中同一区域的像素有很高的相似性，这些像素在任 何颜色空间的距离都是很小，从而如果k m e a n s 算法在随机选择聚类中心时选择 了相似性很高的点，就很可能无法进行迭代。这说明k - m e a n s 算法对于图像的分 类有局限性。因此本文首先在基于k m e a n s 算法上做了一定的改进，目的是让k - 基于子对象空间结构的r o i 图像检索 m e 锄s 算法在任何条件下都可以聚类出较好的结果，再次是加入其它的图像相关的 先验知识作为补充。 传统的k m e 雒s 算法把图像点都看成是颜色空间中的样本，在处理这些样本 时，直接应用像素的颜色信息就会忽略了像素的空间信息。图像中的像素应该和与 它相邻的像素是相似的。因而可以认为如果两像素在图像中很靠近，那么它们的在 颜色空间也应该是很相近的。基于这样的假设，本文把像素的颜色信息和空间位置 信息结合一起。设像素尸= h 恐恐】，其中而屯在不同的颜色空间表示不同的分 量。本文采用口+ 6 颜色空间，则葺吒屯分别为口矿分量。在新的方法中一个五 维的向量将代替三维向量毛屯屯用以描绘像素： 尸= 【屯玛xy 】( 3 3 ) 其中五z ：屯为像素点的三颜色分量，算y 为像素所在的坐标。再分别对p 中各个分 量进行加权 尸= f j r l 艺而工纠西口g ( 比)( 3 - 4 ) 得到最终的聚集数据。其中m ，w ：，心分别为三颜色分量的权值，而h ，比分别为空 间位置的两分量的权重。通过如此处理，分割系统会把在图像中较近的像素点认为 是相似较高的。又因为每一个像素点的位置都不一样，从页尸没有完全一样的两 个数据，在利用f c m 或是k 哪e 趾s 进行计算时不会出现迭代不出聚类中心的情 况。通过多次实验，本文选定 m _ o 1 3 舻l 岷= 熹岷= 焉 ( 3 - 5 ) 其中放d w ，刀c d ，分别为图像的长和宽。m 为三分量的权值，取小于l 可以减少光 照对分割的影响。 改进的k - m e 锄s 方法的具体算法如下： ( 1 ) 对于图像中的每一个像素，利用( 3 4 ) 式进行转化，得到新的待聚类数据： ( 2 ) 初始化所有的权值和阈值； ( 3 ) 适当选取k 个样本点作为k 个类别q q 的初始聚类中心，令循环数i = o ； 基于子对象空间结构的r o i 图像检索 ( 4 ) 计算样本点霉与类别c l 靠之间的距离，把只分配给与其有最小距离的类0 ( 1 匀亟) ； ( 5 ) 更新类的勺聚类中心，按现在所有属于巳的样本点的平均值来替代； ( 6 ) 若i = n ( n 是预先设定的最大循环数) 返回到步骤( 7 ) ，否则令i = i + l 返回到步 骤( 3 ) ； ( 7 ) 把最初在( 1 ) 中设定的k 个类别的中心按( 4 ) ( 6 ) 的处理进行更新，把现在的 聚类中心作为初始聚类中心，令i _ l 返回到步骤( 4 ) 。直到聚类中心不再被更 新为止； 实验表示，本文的图像分割方法比传统的图像分割方法更具优势。 下文将列出几组图像分割结果。 3 4 1 实验一 一 _ 一厂j 虬。 ( a ) 一 o - ( f ) 3 4 实验结果 ( b ) i 卜 q ) 图3 1 图上方( a ) ( b ) ( c ) ( d ) ( e ) 为传统的k 皿黜算法的结果， 法的结果。 ( i )0 ) 图下方( o ( g ) ( i ) ( i ) 为本文的算 此实验对两种不同的k - m e a 那算法的实验结果作比较，其中同一列中的两图 为不同算法得到的同一类结果。( a ) 、( 1 3 1 分别为两结果的总体分割结果；( b ) 、( 曲为 基于子对象空闻结构的r o l 图像检索 黑色和灰色的聚类，可以看到传统的聚类方法会引入浅黄色的像素，如图( b ) 所 示；( c ) 、( 1 1 ) 为果皮部分的聚类：( d ) 、( i ) 为果肉的部分；( e ) 、( i ) 为黄色的果皮部 分，如图所示，0 ) 的结果明显好于( e ) 。 3 4 2 实验二 f t i 图3 2 猫的图像分割，聚类中心为3 个。( a ) 为原图；( b ) ( c ) ( d ) 分割结果 此实验对图( a ) 使用改进的k - m e 龇s 方法进行聚类，聚类中心为3 类。( b ) 为图 像的背景( 颜色部分) ；( c ) 为图像的背景( 灰色部分，黑色和白色) ；( d ) 为图像中的 猫。 3 4 3 实验三 【m ( e ) 图3 - 3 汽车图像分割，聚类中心为4 个。( a ) 为原图：( b ) ( c ) ( d ) ( e 汾割结果 此实验对图( a ) 使用改进的k - m e 锄s 方法进行聚类，聚类中心为4 类。其中汽 车被分割到( b ) 、( d ) 、( e ) 三个类别中。分割结果很好地反应了聚类算法对图像颜色 块的分割。 基于子对象空问结构的r o i 图像检索 实验证明，改进的k m e 弧s 算法有以下的优点： ( 1 ) 在迭代聚类中心时不会出现迭代不到聚类中心的情况； ( 2 ) 合理利用像素在图像中的位置信息； ( 3 ) 对本文所有采用的测试图像的分割特别有效： ( 4 ) 算法所用时间与传统的k - m e 锄s 算法相当； 同时，为了增强图像分块的可用性，本文对所有得到的图像分割结果进行开运算。 基于子对象空间结构的r o i 图像检索 第四章图像中物体对象的空间结构 图像中物体对象的空间结构是图像一个重要的特征。它对于计算机对图像进行 深层次的理解更好。有时用户关心的是图像中物体之问的空间关系，空间关系成为 图像的重要指标。如当用户需要在图中找出两个放在一起的苹果，此时除了苹果的 颜色，纹理，形状特征外，两个苹果的空间位置关系也是十分重要的。又如用户所 感兴趣的对象是由几个分块按特定的空间位置关系组成的，而用户若要查找这一类 对象，对象的空间关系是十分的重要。r a o ，s h m l a f i 等人提出的颜色空间划分法 【4 4 】用以描述图中对象的空间结构，其中最常用的是等距环形颜色划分方法。此方 法距有平移和旋转不变性，但是此特征对空间关系的描述不够具体。而基于2 d 串 ( 2 d - s t r i n g ) 的空间关系特征【4 5 】： s ( q ，r ) 一善芝，“一弓沁研w 一譬) + ，( y 卜y ；如锄( 卯一) ，；) ( 4 1 ) 具有很好的稳定性，但是对旋转敏感；基于有限空间关系模板方法【4 6 怕邑粗略地描 述已知的关系模板，但对于未知的模板无能为力。本文参考上述方法，并在此基础 上提出了一种基于多边形三角划分的空间描述方法。此方法可以比较准确地描述各 个对象的空间分布关系，并具有旋转不变性，缩放不变性，平移不变性等优秀的性 质。 4 ，1 图像分块的表示与图像分块相似度 对于任意图像，在通过分割后会形成若干个分块。本文从每一分块中提取出颜 色，形状，纹理等特征，并用一组向量记录起来。对于任意一图像分块s ，由本 文第二章所述的方法可以提取出s 的颜色特征( c o l o r ) ，图像形状( s h a p e ) ，纹理特征 ( t e x t l l m ) ，再添加上分块中心位置( c e n t c f ) ，图像形状主方向( d i r e c 曲n ) ，图像面积 ( a 犯a ) ，就可以得到一个描述分块的一组向量 s e g | k o t o r t e ) c t h r e h n p e e n t e r 五i r e c t t o n 乒r e 乩 媳。砼 其中d i r e c t i o n 是指s h 印e 的两个主方向。根据公式( 2 - 6 ) 、( 2 - 2 6 ) 、( 2 2 9 ) 可以得到两 图像块的距离： 基于予对象空间结构的r o l 图像检索 d i s ts c g b e g l ，s e g ；w c d i s t 。h r + w t d i s t c c m 。+ w s d i s ts h 4 p e媳- 3 其中+ m + m ；1 ，分别为颜色、纹理和形状的权值。然后利用g