（信号与信息处理专业论文）基于显著点和关键块相结合的图像检索方法.pdf

基于显著点和关键块相结合的图像检索方法 摘要 本文提出了一种新的基于小波变换显著点和基于关键块相结合的图像检索 方法。首先利用小波变换提取图像的显著点，然后将图像划分成均匀的图像块， 按照图像块中是否有显著点，将图像块分为有显著点的和无显著点的两类。通过 提取块的低层次特征矢量，将两幅图像之问的匹配转换成图像块之间的匹配。在 图像检索时，通过对这两类图像块分别进行相似性度量，对得到的结果加以不同 的权重，以实现对图像局部或全局不同要求的检索。 基于小波变换的显著点已被用于图像检索，实验表明显著点大多位于图像中 物体的边缘，所以根据显著点提取的局部特征主要代表了图像中物体而不是背景 的信息。另一方面，基于关键块的方法模拟基于文本的信息检索的技术，提供了 一种基于内容图像检索的行之有效的方法，但是关键块是在整个图像的基础上构 建的，所以它们主要包含的是图像的全局特征。但是实际工作中，对于同一幅图 像，由于观察者的侧重点不同，希望得到的检索结果也会有所不同我们希望将 这两种方法有效的结合起来，不仅能提高检索的效率，而且可以在检索的过程中 得到更多的自由度 我们进行了一系列的实验来验证我们提出方法的有效性。实验结果证明，本 方法不仅同时具有基于关键块检索和基于小波变换显著点检索的优点，而且可根 据用户的选择，灵活的对图像进行检索，并具有令人满意的检索效果。 关键词：基于内容的图像检索；显著点；关键块：聚类；码书； i m a g er e t r i e v a lu s i n gs a l i e n tp o i n t sa n dk e y b l o c k s a b s t r a c t i nt h i sp a p e r ，an o v e ll n e t h o di sp r o p o s e d ，w h i c hi sb a s e do ns a l i e n tp o i n t sa n dk e y - b l o c k s f i r s tw ee x t r a c ts a l i e n tp o i n t su s i n gw a v e l e tw a r t s f o r m ，t h u ss e g m e n tt h ei m a g ei n t oe q u a ls i z e b l o c k s t h e s eb l o c k sc a nb ed i v i d e di n t ot w oc l a s s e s ，o i 瑚w i t ht h es a l i e n tp o i n t sa n dt h eo t h e r s n o lt h e nl o w - l e v e lf e a t u r e ss u c ha sc o l o r 蛳e x t r a c t e dt od e s c r i b eb l o c kb ya d j u s t i n gt h e w e i g h t so f t h et w oc l a s s e si ni m a g er e t r i e v a l ，w ec a ng e td i f f e r e n tr e s u l t sw h i c hd e p e n do no u r i n t e r e s ti nl o c a lo ro o b a ls i m i l a r i t y w a v e l e t - b a s e ds a l i e n tp o i n th a sb e e nu s e df o ri m a g er e t r i e v a l e x p e r i m e n t ss h o wt h a tt h e s a l i e n tp o i n t sa r cm o s t l yf o u n d0 1 1t h eb o u n d a r i e so ft h eo b j e c t s ，t h e r e f o r et h el o c a lf e a t u r e s a r o u n dt h es a l i e n tp o i n t sp r i m a r i l yr e p r e s e n tt h eo b j e c ti n f o r m a t i o ni n s t e a do f t h eb a c k g r o u n d o n t h eo t h e rh a n d ，k e y b l o c k - b a s e da p p r o a c ha l s ol n o v i d e sap r a c t i c a ls o l u 6 0 nf o rc o n t e n t - b a s e d i m a g er e t r i e v a la n a l o g o u st ot e x t - b a s e d 取t e c h n i q u e s 。b u tt h ek e y b l o c k sa r ec o n s a - u c t e do nt h e b a s i so f t h e t i r ei m a g e ，t h e yn m i n l yc o n t a i nt h eg l o b a lf e a t u r e so f t h ei m a g e kr e a lw o r l d ， b e c a u s et h ev i e w e r sh a v ed i f f e r e n tf o c u so nt h e 岛i i n ei m a g e ，t h u st h ew a n t e dr e t r i e v a lr e s u l t s m a y a l s ob ed i f f tt h m f o m ，w e h o p et oi n t e g r a t et h e s et w om e t h o d se f f e c t i v e l y ，s ot h a tw e 啪n e to n l yi l i l p r o v et h er e t r i e v a le f f i c i e n c y b u ta l s og e tm o md e g r e eo ff r e e d o md u r i n gt h e w eh a v ep e r f o r m e d s e r i e so fe x p o r i m e n t st oc o n f i r mt h ee f f e c t i v e n e s so fo u rm e t h o d e x p e r i m e n t a lr e s u l t si n d i c a t et h a t0 1 1 1 m e t h o dn o to n l yo w e st h ea d v a n t a g eo fk e y b l o c k - b a s e d a p p r o a c h ，b u ta l s ot h es a l i e n tp o i n t s m o r e o v e r ，u s e r sc a ng e ts a t i s f a c t o r yr e t r i e v a lr e s u l t s a c c o r d i n gt ot h e i ri n t e r e s tb ya d j u s t i n gt h ew e i g h t s k e y w o r d s ：c o n t e n t - b a s e du n a g er e t r i e v a l ：s a l i e n tp o i n t s ：k e y - b l o c k ：c l u s t e r i n g ；c o d e b c o k ： u 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研 究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 入已经发表或撰写过的研究成果，也不包含未获得 l 洼i 妻旦退查基丝盖薹挂型童明数：奎拦互窒2 或其他教育机构的学位或证书使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说 明并表示谢意。 学位论文作者签名：曲彩咖签字日期力形年穸月7 f 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，有权保留并向 国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授 权学校可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影 印、缩印或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在解密后适 用本授权书) 学位论文作者签名：曲晚毛 签字日期；2 斫年，月；f 日 学位论文作者毕业后去向： 工作单位： 通讯地址： 导师签字：训狮 签字日期：知一b 年 ，月日 电话： 邮编 基于显著点和关键块相结合的圈像检索方法 0 前言 随着多媒体、网络技术的迅速发展，不同文件格式的数字图像正在以爆炸式 的速度增长如何有效地使用如此巨大的数据资源。取决于我们从图像数据库中 查询和检索信息的能力，因此图像检索已成为一个相当活跃的研究领域。 自上世纪9 0 年代起，基于内容的图像检索( c o n t e n tb a s e di m a g er e t r i e v a l ) c b i r 成为人们研究的热点，它是现有图像检索技术研究的主流。它将数字图像处 理、模式识别、计算机视觉与数据库技术结合起来，其主要研究内容是在数字图 像处理基础上的视觉特征提取、多维索引以及检索系统设计l l j ，主要支持基于范 例检索( e x a m p l e - b a s e dr e t r i e v a l ) 、基于草图检索( s k e t c h - b a s e dr e t r i e v a l ) 和随机浏览及其组合的工作方式强前尽管基于内容的图像检索技术已经取德长 足的进步，但是它还不成熟。作为图像检索下一个阶段，即图像语义检索的重要 基础，它还需要人们进行更深入的研究。 在基于内容的图像检索系统中，基于关键块的方法通过对图像做固定的分。1 割，即将图像划分成为固定大小的块，绕开了对象识别的过程；而基于显著点的 方法，由于显著点往往分布在图像中物体的边缘，适合于对象检索如何将这两 种方法有机的结合起来，为用户提供准确的检索结果，并且在检索过程中根据用 户的喜好，赋予用户更大的自由度，是我们关注的主要问题。 本文首先采用小波变换提取出图像的显著点，然后将图像均匀的分块。根据 图像块中是否包含有显著点，将图像块分成两类。再对这两类图像块通过矢量量 化的方法分别提取出其特征，保存莛来。在图像检索对，通过对这两类特征分剐 进行相似性度量，并根据用户的选择，对检索的结果加以不同的权重，以得到更 符合用户要求的结果。 论文内容安排如下：第一章简要介绍基于内容的图像检索技术；第二章阐述 了基于关键块和基于显著点的图像检索方法，并提出了将显著点和关键块相结合 的图像检索方法；第三章详细阐述了基于显著点和关键块相结合的图像检索方 法；第四章通过分析实验结果，论证了本文提出方法的有效性：第五章是本论文 的工作总结，并讨论进一步研究的方向。 基于显著点和关键块相结合的图像检索方法 1 基于内容的图像检索( c b i r ) 随着多媒体、网络技术的迅速发展，不同文件格式的数字图像正在以爆炸式 的速度增长。如果我们不能将它们组织起来，进行有效的浏览，搜寻和检索，那 么我们就没有办法充分地利用这种信息。因此自上个世纪7 0 年代起，图像检索 就一直是人们研究的热点。目前基于内容的图像检索( c b i r ) 是这研究领域的 主流。 基于内容的图像检索技术兴起于上个世纪9 0 年代，这种技术由计算机自动 提取包含图像内容的可视特征，如颜色、纹理、。形状、对象的位置和相互关系等， 通过在特征空间中，对数据库中图像和查询样本图像进行相似匹配，检索出与样 本相似的图像。它融合了数字图像处理，模式识别，计算机视觉与数据库等技术， 并随着相关领域的发展而不断进步。它的三个重要的基础是视觉特征提取、多维 索引和设计检索系统2 j j 1 1 特征提取 图像特征的提取与表达是基于内容的图像检索技术的基础，大多数图像检索 系统都将它作为一个预处理步骤。从广义上讲，图像的特征包括基于文本的特征 ( 如关键字、注释等) 和视觉特征( 如色彩、纹理、形状、对象表面等) 两类。 对于基于内容的图像检索而言，使用的是图像的视觉特征而视觉特征又可分为 通用的视觉特征和领域相关的视觉特征两类。前者用于描述所有图像共有的特 征，与图像的具体类型或内容无关，主要包括颜色、纹理和形状等：后者则建立 在对所描述图像内容的某些先验知识或假设的基础上，与具体的应用紧密相关， 例如人的面部特征或指纹特征等。由于领域相关的图像特征主要属于模式识别的 研究范围，我们在此只关注通用的视觉特征 对于某个特定的图像特征，通常又有多种不同的表达方法，它们从不同的角 度刻画了该特征的某些性质。由于人们主观认识上的千差万别，对于某个特征并 不存在一个所谓的最佳的表达方法。 1 1 1 颜色特征提取 颜色是图像检索中最为广泛使用的视觉特征，它具有相对于复杂背景的强壮 性，并且与图像的大小和方向无关目前几乎所有基于内容检索的图像数据库系 统都将基于颜色的检索方法作为检索的一个重要手段。 2 基于显著点和关键块相结合的图像检素方法 为表示图像中的颜色，首先我们要选择一个合适的颜色空间。颜色空间的用 途是在某些标准下用通常可接受的方式简化彩色规范，系统中的每种颜色都由单 个点来表示。目前所用的大多数颜色空间模型都是面向硬件的( 如彩色监示器和 打印机) 或是面向应用的，具体有r g b 颜色空间、h i s 颜色空间、h s v 颜色空间， l 木a 窄b 木颜色空间、c i e 和蒙赛尔颜色顺序空问( m u n s e l lc o l o r o r d e rs p a c e ) 等。其中r g b 颜色空间是最常用的颜色空间，它属于面向硬件的模型，用于彩色 监示器和一大类彩色视频摄像机。但在研究基于颜色特征检索图像时，r g b 颜色 空间并不是最佳的选择。因为它不具有视觉一致的属性，会在后续的颜色量化和 相似性比较过程中带来较大的误差。具有视觉一致属性的颜色空间有h i s 、h s v 、 m u n s e l l 空间等。在比较图像颜色是否榴似时，应该将图像映射到具有视觉一致 性的颜色空间，这样才能减少误差。为对各种图像检索方法给出统一的评价，应 采用一致的颜色空间模型。 在图像检索中，颜色直方图是最为广泛使用的颜色特征，它统计每种颜色在 图像中出现的概率s w a i n 和b a i i a r d 使用直方图交作为直方图相似性度量吲。计 算颜色直方图需要将颜色空间划分成若干个小的颜色区问，每个小区间成为直方 图的一个箱，这个过程称为颜色量化然后，通过计算颜色落在每个小区问内的 像素数量可以得到颜色直方图颜色量化有许多方法，例如向量量化、聚类方法 或者神经网络方法。最为常用的做法是将颜色空间的各个分量( 维度) 均匀地进 行划分。相比之下，聚类算法则会考虑到图像颜色特征在整个空间中的分布情况， 从而避免出现某些箱中的像素数量非常稀疏的情况，使量化更为有效。因为大多t 数直方图非常稀疏，而且对噪声敏感，s t r i c k c r 和o r c n g o 提出了累计颜色直方图 方法，实验证明它优于传统的颜色直方图方法l j j 。 除颜色直方图外，颜色距和颜色集也被用于图像检索。为克服颜色直方图的 量化效应。s t r i c k c r 和o r c n 8 0 提出了颜色距方法i j j ，其数学基础是任何颜色分布 可由颜色距表示。由于颜色分布信息主要集中在低阶矩中，因此仅采用颜色的一 阶矩( m e a n ) 、二阶矩( v a r i a n c e ) 和三阶矩( s k e v n e s s ) 就足以表达图像的分 布与颜色直方图相比，该方法的另一个好处在于无需对特征进行量化。颜色距 的计算公式为： 基于显著点和关键块相结合的圈像检索方法 玑；专姜岛 q = 砖姜( ) 2 ) i 墨= ( 二l 善n ( 岛一辑) ， 其中p 。是图像中第，个像素的第j 个颜色分量。因此，图像的颜色矩只需要9 个 分量( 3 个颜色分量，每个分量上3 个低阶矩) ，与其他的颜色特征相比非常简 单。 为在大规模图像集合中进行快速的查找，s i i l i m 和c h a n g 提出了颜色集方法， 它是颜色直方图的一种近似1 4 ，纠。首先将r g b 颜色空间转换到一个视觉一致的颜 色空间，如h s v ，然后将转换后的颜色空间量化为m 个颜色箱。通过采用色彩自 动分割技术将图像分为若干区域，每个区域用量化颜色空间的某个颜色分量来索 引，从而将图像表达为一个二进制的颜色索引集。由于颜色集特征矢量是二进制 的，可构造一个二迸制查找树进行快速查找。 1 1 2 纹理特征提取 纹理是图像的一个重要属性尽管对纹理没有正式的定义，但是直觉上， 这种描绘子提供了对诸如平滑度、粗糙度和规律性等特性的度量。在图像处理中 用于描述区域纹理的主要方法有统计方法、结构化方法、模型方法和频谱方法 w 。统计方法指诸如平滑、粗糙、粒状等纹理的特征描述。结构化技术处理图 像元的排列，诸如基于均匀空间分布的平行线纹理描述。频谱技术基于傅里叶频 谱特性，主要用于通过识别频谱中高能量的窄波峰寻找图像中的整体周期性。 1 1 2 1 统计方法 统计方法分析纹理的主要思想是通过图像中灰度级分布的随机属性来描述 纹理特征。描述纹理的最简单的方法之一就是使用一幅图像或区域灰度级直方图 的统计矩但是仅使用直方图计算纹理，由于直方图不具有像素之间相对位置的 信息而受到限制。为了利用这些空间信息，上世纪7 0 年代，h a r a l i c k 等研究了 图像纹理中灰度级的空间依赖关系【o j ，根据图像中像素之问的位置和距离关系构 造了一个共生矩阵( c o m a t r i x ) ，然后从中提取有意义的统计特征作为纹理特征的 表达。许多其他的学者延用同样的思路，并提出改进的方法。在关于人类视觉感 知纹理的心理研究的推动下，t a m u r a 等人从另一个角度探索纹理表示，他们提 4 基于显著点和关键块相结合的图像拴索方法 出用计算来近似在心理研究中被发现是非常重要的纹理特征。这六个纹理特征分 别是粗糙度、对比度、方向度、线像度、规整度和粗略度，其中前三个分量对 于图像检索尤其重要i ，j 。t a m u r a 纹理表示和共生矩阵表示的一个主要区别在于 t a m u r a 表示具有视觉意义。而共生矩阵中的一些纹理性质则没有( 例如熵) 。这 一特点使得t a m u r a 的纹理表示在图像检索中使用得较多。q b i c 和m a r s 都进一 步证明了这种表示方法。 i i 2 2 结构化方法 结构化方法分析纹理的基本思想是假定纹理模式由纹理单元按照一定的、有 规律的形式重复排列组合而成，一个简单的纹理单元可以借助一些限制图元可能 的排列规刚组成更为复杂的纹理模式。这样纹理特征提取就变为确定这些单元并 定量分析它们的排列规则。c a r l u c c i 咧曾提出一个使用直线段，开放多边形和封 闭多边形作为纹理单元的纹理模型，其排列规则由一种图状语法结构定义。l u 和 f u p j 给过一种树型语法结构表示纹理，他们将纹理按照9x 9 的窗口进行分割， 每个分解单元的空间结构表示为一棵树。由于实际的纹理大都是无规则的，因此 结构法受到很大限制。 ” 1 1 2 3 模型方法 它利用一些成熟的图像模型来描述纹理，如基于随机场统计学的马尔可夫随 机场、予回归模型，以及在此基础上产生的多尺度子回归模型( m u l t i r e s o l u t i o n s i m u l t a n e o u sa u t o r e g r e s s i v e ，m r s a ) 剀等。这些模型的共同特点是通过少量的 参数表征纹理，m r s a 区分不同纹理模式的能力较强，但同时计算开销也较大。 1 1 z 4 频谱方法。 频谱方法借助于频率特性来描述纹理特征，包括傅里叶功率谱法u j 、g a b o r 变换【1 1 1 、塔式小波变换 1 2 1 、树式小波变榭1 刁等方法。随着小波变换理论框架的 建立，许多学者开始研究使用小波变换用于纹理表示如s m i t h 和c h a n g 使用从小 波子带中提取出的统计特征( 均值和方差) 作为图像的纹理表示，对于纹理图像 取得了很好的检索效果【l j 。m a 和m a n j t m a t h 评价了各种小波变换的纹理表示， 发现基 ：g a b o r 小波变换的效果最好l i ”，它与人类视觉研究的结果相匹配，其检 索性能优于t 盯和p 盯，略微优于m r s a ，缺点是计算速度慢，其旋转不变性和尺 度不变性仍有待探讨。 i 1 3 形状特征提取 物体和区域的形状是图像表达和图像检索中的另一重要特征。但不同于颜色 或纹理等底层特征，形状特征的表达必须以对图像中物体或区域的划分为基础。 由于当前的技术无法做到准确而鲁棒的自动图像分割，图像检索中的形状特征只 基于显著点和关键块相结合的图像检索方法 能用于某些特殊应用，在这些应用中图像包含的物体或区域可以直接获得。另一 方面，由于人们对物体形状的变换、旋转和缩放主观上不太敏感，合适的形状特 征必须满足对变换、旋转和缩放无关，这对形状相似度的计算也带来了难度。 通常来说，形状特征有两种表示方法，一种是基于边界的，一种是基于区域 的。前者只用到物体的外边界，而后者则关系到整个形状区域。这两类形状特征 的最典鍪! 方法分别是傅立叶描述子和形状无关矩 傅立叶形状描述子的基本思想是用物体边界的傅立叶变换作为其形状描述。 假设一个二维物体的轮廓是由一系列坐标为也，只) 的像素组成，其中 0 s s s n 一1 ，而是轮廓上像素的总数。从这些边界点的坐标中可以推导出三 种形状表达，分别是曲率函数、质心距离和复坐标函数。 轮廓线上某一点的曲率定义为轮廓切向角度相对于弧长的变化率。曲率函数 足( s ) 可以表示为； j k ( j ) = 口( j )( 卜2 ) 珊 其中口( j ) 是轮廓线的切向角度，定义为； 郎) 一。尊 y ：= 誓 小鲁 ( 1 _ 3 ) 质心距离定义为从物体边界点到物体中心瓴，儿) 的距离，如下所示： r ( s ) = 瓜j 了瓦而 ( 1 - 4 ) 复坐标函数是用复数所表示的像素坐标： z o ) = ( 一t ) + 7 ( 乃一儿) ( 卜5 ) 对这种复坐标函数的傅立叶变换会产生一系列复数系数。这些系数在频率上 表示了物体形状，其中低频分量表示形状的宏观属性，高频分量表达了形状的细 节特征。形状描述符可以从这些变换参数中得出傅立叶描述子对图像形状进行 描述具有良好的尺度，旋转，平移不变性。考虑到图像域的数字化噪音，r a i 等提出了一种改进的傅立叶描述子，它不仅对噪声具有鲁棒性，而且对于几何变 换具有不变性【i 。使用发展纯熟的傅立叶变换法来描述图像形状，具有较好的 理论基础，但也有其局限性，傅立叶描述子不能描述图像的局部信息。 形状无关矩的主要思想是利用区域的变换不变距，将其作为形状特征。假设 r 是用二值图像表示的物体，则r 形状的第p + 口阶中心矩为： 6 基予显著点和关键块相结合的图像检索方法 “，4 = o 一) o ，一兑) 。 ( 1 6 ) z ，y ) t 置 其中也，咒) 是物体的中心。h u l “1 提出了一系列分别具有变换、旋转和缩放无关 性的7 个矩，在此基础上，人们又陆续提出了许多改进。例如，由于发现大多数 有用的不变距是在广泛的实验和尝试的基础上被找到的，k a p t i r 等人开发出系统 地产生和查找一个给定不变距的算法l 埔j 。 近年来在形状表示和匹配方面的工作，包括有限元法( f e m ) 、旋转函数和小 波描述符等方法。f e m 【z o j 定义了一个刚性矩阵来描述物体上的每一个点与其它点 之间的联系这个刚性矩阵的特征向量被称为模，它们是特征空间的基所有的 形状都首先被映射到这个特征空间，然后根据特征僮计算相似性。沿着类似于傅 立叶描述子的思路，a r k i n 等提出旋转函数，它是基于比较凹面或凸面多边形的 方法j 。c h u a n g 和k u o 用小波变换来描述物体形状l z 2 】它几乎包含了符合我们 要求的所有性质，如不变性、单一性、稳定性和空间位置等。关于形状，c h a m f e r 匹配方法吸引了不少研究者的兴趣。b a r r o w 等首先提出了c h a m f e r 比较法j ， 该方法能够以线性的时间复杂度比较两个的形状片段的集合。为加快匹配的速“ 度，b o r g c r f o s 提出了分层c h a m f e r 匹配算法州，这种匹配算法可以从粗到细， 在不同的分辨率上进行 1 2 图像索引 在执行图像检索时，对于存储几百或几千幅图像的数据库，采用顺序扫描全 部图像的方法，对于系统性能的影响也许并不大但是随着图像集的数目不断增 长，检索的速度就会成为系统的瓶颈。所以对图像进行有效的索引和匹配是非常 有必要的。目前我们面临的两个主要挑战是特征矢量的高维性和非欧基里德相似 性度量，这是由于图像的特征矢量的维数通常是上百维的，而欧基里德相似性度 量也许并不能有效的模拟人类对某个视觉内容的理解。为了解决这些问题，合适 的方法应首先执行降维处理，然后在此基础上使用支持非欧基里德相似性度量的 合适的多维索引技术 1 2 1 矢量降维 尽管图像检索中的特征矢量的维数通常都很高，但是实际真正嵌入的维数要 少的多。无论我们使用何种索引技术，首先对数据进行降维处理都是非常有必要 的。目前关于降维的方法主要有k l 变换和按列聚类。 k l 变换以及它的变种p c a ( p r i n c i p a lc o m p o n e n ta n a l y s i s ) 已被用于降维处 理，f a l o u t s o s 和l i n 提出了一种k l 变换的快速近似，进行降维处理【2 6 1 实验结 7 基于显著点和关键块相结合的图像检素方法 果显示大多数真实的数据集( 视觉特征矢量) 可以被显著地降维，而不会明显影 响检索的质量瞵2 6 ，2 7 】 除了k l 变换，聚类也是执行降维处理的有利工具。聚类被用于许多学科， 如模式识别、讲话分析、信息检索等一般来说，它被用于聚类相似的事物( 例 如模式，信号和文档) ，以达到识别或分组的目的，这样的聚类被称为按行聚类。 但是聚类也可以按列进行，以减少特征空间的维数j 。实验显示这是一种简单 有效的方法。 值得关注的是，盲目的降维将会是非常危险的，因为当维数低于真正嵌入的 维数时，会造成信息的丢失。为此，在执行降维处理后进行事后验证是必要的。 1 2 2 图像的多维索弓 即使在我们执行降维处理后，我们面临的图像特征矢量的维数依然是相当高 的，常常是上百维的。要想索引高维的特征矢量，用传统的数据结构是不行的， 只能用多维索引技术。目前流行的多维索引技术主要有桶算法，k d 树，优先权 l 翻树、四叉树、k _ n b 树、h b 树、r 树及其变种r + 树和r + 树等 2 9 3 0 3 1 3 2 3 3 1 ，其中 r 树及其变化形式是应用最广的。 k d b 树是b 树向多维空间的一种发展。它对于多维空间中的点进行索引具有较 好的动态特性，删除和增加空间点对象也可以很方便地实现；其缺点是不直接支 持占据一定空间范围的地物要素，如二维空间中的线和面。该缺点可以通过空间 映射或变换的方法部分地得到解决。空间映射或变换就是将2 n 维空间中的区域变 换到2 n 维空间中的点，这样便可利用点索引结构来对区域进行索引，原始空间的 区域查询便转化为高维空间的点查询。但空间映射或变换方法仍然存在着缺点： 高维空间的点查询要比原始空间的点查询困难得多：经过变换，原始空间中相邻 的区域有可能在点空间中距离交得相当遥远，这些都将影响空间索引的性能。 r 树是一个和二叉树形式相似的索引结构，树内的节点表示一个k 维的超矩 形，而不是一个标量。因此，这种结构适合高维索引，特别是范围查询。由于r 树兄弟结点对应的空间区域可以重叠，因此，r 树可以较容易地进行插入和删除 操作；但正因为区域之间有重叠，空间索引可能要对多条路径进行搜索后才能得 到最后的结果，因此，其空间搜索的效率较低。正是这个原因促使t r + 树的产生。 在r + 树中，兄弟结点对应的空间区域没有重叠，而没有重叠的区域划分可以使空 间索引搜索的速度大大提高；但由于在插入和删除空间对象时要保证兄弟结点对 应的空间区域不重叠，而使插入和删除操作的效率降低。 由于大多数树型的索引技术是被设计用来查询传统数据库的，比如点查询或 范围查询，所以它们并不适合图像检索中的相似查询，特别是考虑到图像检索中 基于显著点和关键块相结合的图像检索方法 的相似性度量也许是非欧基里德，甚至是不可度量的，为此在模式识别中经常用 到的聚类和神经网络成为很有前景的索引方法。z h a n g 和z h o n g 提出了使用自组织 特征射影网( s o m ) 来构造图像检索的树索引结构【3 4 】。s o m 的优点在于它的无监督 学习能力，可以动态聚类以及支持任意的相似性度量。 1 3 相似性度量 相似性度量是图像检索的一个关键环节。基于文本的检索方法采用的是文本 的精确匹配，而基于内容的图像检索则通过计算查询图像和候选图像之问在视觉 特征上的相似程度进行匹配。因此，定义一个合适的视觉特征相似度度量方法对 检索的效果有很大的影响。由于视觉特征大都可以表示成向量的形式，常用的相 似度方法都是向量空间模型，即将视觉特征看作是向量空间中的点，通过计算两 个点之闻的接近程度来衡量图像特征间的相似度 在图像检索时，对于不同的特征矢量，应该采用不同的度量方法检索的过 程中，根据系统相似性度量的算法，计算查询特征与特征库中对应的每组特征之 问的相似程度，把所得结果由大到小排序后得到一个匹配图像序列返回给用户 其问可以通过人机交互，对检索的结果逐步求精，不断缩小匹配集合的范围，从 而定位到目标。匹配过程常利用特征向量之间的距离函数来进行相似性度量，模 仿人类的认知过程，近似得到数据库的认知排序。 1 3 1d 1 距离和d 2 距离 如果图像特征的各分量之问是正交无关的，而且各维度的重要程度相同，两 个特征向量x 和) ，之间距离可以用4 距离或者d 2 距离( 也称为欧氏距离) 来度 量。其中d 1 距离可以表示为： d l = i x , - y , i ( 1 7 ) “ 其中是特征向量的维数。类似地，d ，距离可以表示为： d 2 = ( 而一乃) 2 ( 1 8 ) 1 1 由上式可知，若特征向量工和y 位于同一类型区域里，欧式距离是比较小的； 若是位于不同的类型区域里，欧式距离则比较大。判断距离的大小就要定义一个 门限。门限的选取是正确分类的关键。若门限选取过大，则全部样本被视为同一 类型；若门限选取的过小，可能会出现每个样本都视为一种类型的情况。欧式距 离具有旋转不变的特性。 9 差于显著点和关键块相结合的雷像硷索方法 1 3 2 马氏距离 如果特征向量的各个分量闻具有相关性或者具有不同的权重，可以采用马氏 距离( m a h a l a n o b i s d i s t a n c e ) 来计算特征之间的相似度。马氏距离的数学表达为： ，2 - - ( x 一“) r - 1 g h ) ( 1 - 9 ) 其中“是均值向量，是协方差矩阵。马氏距离排除了不同特征之间相关性的影 响，关键在于协方差矩阵的计算。只有当是对角阵时，各个特征之间才完全独 立：当为单位阵时，马氏距离等于欧氏距离。由于甜和都与类型有关，因此 马氏距离，比较适用于对已初步分类的样本做进一步的考核和修正 1 3 3 直方图距离和直方图的交集 如果用- e u r r 和t t p r e v 表示具有n 种颜色箱的直方图，f 是索引直方图的变 量，那么两个直方图的距离可以用d 表示，直方图的交集可以用d 。表示。当直 方图经过归一化处理之后，两个直方图的相似度越高，d 。的值越接近1 。 1 4 相关反馈 ( 卜t o ) ( 卜1 1 ) 由于图像低层特征提取的方法还有待于完善以及低层特征与高层语义间存 在着很大差距等原因，仅仅是基于图像低层特征的一次查询很难给出令人满意 的结果，为了解决这个问题，一方面需要研究出更好的提取图像特征的方法， 另一方面需要通过人机交互的方式来捕捉和建立低层特征和高层语义之间的关 联，这就是所谓的相关反馈技术。 相关反馈是一种查询修正技术，它起源于信息检索，目的是捕捉到用户的准 确需求和查询细化。它的基本思想是：在检索过程中，系统根据用户的查询要 求返回检索结果，用户将对检索结果的评价和标记信息反馈给系统，系统则根 据这些反馈信息进行学习，并返回新的查询结果，从而使锝检索结果更加满足 用户的要求。自从它首次应用于图像检索领域以来，就引起了人们广泛的关注。 o 0 x 一 坐k 日 ，竺一划筹 虽一芝 鼾 型 日 _ 芎l 扣。 墨 基于显著点和关键块相结合的图像检索方法 由于缺乏一个有效的框架来表述图像的高级语义和人类的主观理解，用户的相 关反馈提供了一种学习特定案例的查询语义的方法。 正常情况下，用户的相关反馈只会得到与每个高级概念有关的少数的被标签 过的图像基于学习的方法典型地用于适当地修改特征集和相似性测度。为了克 服从小训练集学习的问题，札等提出一种区别性的e m 算法，它利用数据库中未 被标签过的图像来选取更具有区别力的特斛”j 。在统一的框架下，使用视觉特 征和有关的语义关键词执行相关反馈的方法被提出【j “相关反馈的一个问题 是，经过每轮用户交互后，通常与查询有关的最靠前的结果将不得不使用一个修 改过的相似性测度重新计算。w u 等提出一种加速这种近邻查找的方法p 刊。另一 个问题在于用户对于支持多轮反馈的耐心。一种减少用户交互的方法是将反馈历 史日志和当前查询相结合p ”操作的历史也有利于捕捉高级语义和底层特征的 关系 4 0 j 。我们也可以将相关反馈视为一种积极学习的过程，学习人员每轮从他 前一轮反馈结果中选择一个合适的子集，而不是随机选择一个子集。t o n g 等将 使用支持向量机的积极学习引入图像检索领域j 随着基于区域的图像检索 4 z , 4 3 1 越来越流行，人们尝试使用查询点移动和支 持向量机 4 4 , 4 5 j 将区域因素结合到相关反馈查询点移动是基于矢量模型发展而 来，本质上是通过使“理想查询点”移向好的样本点并远离坏的样本点来提高其 评估值。提高这一估计经常使用的技术是r o c c h i o 提出的如下公式，该公式是操 作于由用户给出的相关文档d ；和非相关文档珥的集合的； 11 9 = 她+ 局嗉 口) 一必手忍) ( 1 1 2 ) 1 r i e 曝o i 6 d n 其中，口，和，是适当的参数；，和。分别是d ；和仉中文档的数量。实 验证明这种相关反馈方法能够大大提高检索性能。l a a k m ) n e l l 等提出一种树结构 的自组织图作为一种相关反馈的基础技术h ，用于基于内容的图像检索系统一” 概率的方法也被提出用于相关反馈【4 8 , 4 9 , 5 0 k i m 研究在复杂查询的条件下，一种 结合了用户的理解的基于聚类的相关反馈的方法【，“基于对底层特征空间的几 何直觉的用户反馈的多重学习在p q 中被提出。尽管大多数提出的相关反馈算法 是处理两类问题的，即相关或不相关的图像，另一种看待相关反馈的方式是使用 一个合适的用户接口，考虑多个相关或不相关的图像组【5 3 5 4 # s 】。比如，如果用户 要查找小轿车，那么她可以重点强调蓝色的小轿车和红色的小轿车作为相关的范 例，因为也许在任何底层特征空间统一的表示轿车的感念都是不可能的。然而另 一种偏离常规的方法是使用多级相关分数，将指定图像的相对的相关度结合进用 户查询【5 6 1 。 基于显著点和关键块相结合的图像检索方法 1 5 系统评估 对检索效果的评价在于检索结果的正确与否，主要使用的是查准率 ( p r e c i s i o n ) 和查全率( r e c a l l ) 两个指标，通常用p r 图( 查准率与查全率关系 图) 表示。通过分析p r 图，可以提取各种信息。查全率的主要含义是在一次查 询过程中，用户所检索到的相关图像的数目，和数据库中与目标图像相关的所有 图像数日r 之比；而查准率主要指在一次查询过程中所检索到的相关图像数目， 同查询到的所有图像数目之比。用户在评价查询结果时，可以预先确定某些 图像作为查询的相关图像，然后根据系统返回的结果来计算查准率和查全率这 两个指标的值越高说明检索方法的效果越好。实验证明，在查全率和查准率之间 存在着相反的相互依赖关系。如果提高输出的查全率，就会降低其查准率，反之 亦然。 p r e c i s i o n ：三 r c c 口盯：二 五 ( 1 - 1 3 ) ( 1 - 1 4 ) 通常在检索图像时，不需要把所有相关的图像都检索出来。实验证明，最为 相关的图像一定会出现在相关系数最大的前若干幅图像中，具体数目要看数据库 的容量和图像之问的关系。既然不是所有的相关图像都被检索到，那么一般用到 的评价标准p r 图就不是很合适了。k i a n - l e et a n 和b e n gc h i no o i 提出用归一 化的查全率和归一化的查准率评价检索效果，公式定义如下： e 。= l - , ( t o g r a 丽n k i 一- l 0 9 0 ( 1 一1 5 ) l o g ( n - r ) ! r ! r 小呈! 坐i 二翌( 1 - 1 6 )。 【一r ) r 公式中的只和r 表示归一化的查准率和查全率，其中 ，表示集合中图像总 数，r 是集合中相关图像的数目，r a n k 表示系统检索到的第i 幅相关图像的相关 系数。 由于查准率和查全率是来自于信息检索，用于评价图像检索时，会因为重视 系统检索的精度忽视了检索的速度。而c b i r 系统主要面向的是大型的图像数据 库，对系统的响应时间要求比较高，所以检索速度也是评价的重要指标。检索速 度可以用响应时间表示，就是从用户将查询请求提交给系统到系统将查询结果反 基于显著点和关键块相结合的圈像检索方法 馈给用户的过程中所用的时间总和响应时间应当是越短越好。为了减少响应时 间，在保持精度的情况下，可以用简化特征矢量的方法加快匹配对于图像数据 库，使用合适的索引结构，是减少响应时间的有效手段之一 1 6 图像检索系统实例 目前已有许多基于内容的图像检索系统，既有用于科学研究的也有用于商 业目的的，其中比较有代表性的有q b i c 、v i l - a g e ，v i s u a l s e e k 和m a r s 。在这一 小节中，我们将对这几个系统进行重点介绍 1 6 1 q b i c m m 的q b i c ( q u e r y - b y - i m a g e - c o n t e n t ) 是c b i i l s 的典型代表，是第一个商用 的基于内容的图像查询系统，它的系统架构和使用的技术对于后来的图像检索系 统具有深远的影响。 q b i c 支持基于例图的查询，由用户构造草图和绘画的查询或是选择颜色和 纹理特征的查询等三种查询方式。q b i c 中用到的颜色特征是( r ，g ，b ) 、( y ， i ，q ) 、( l a ，b ) 和( m t m ) 等坐标的平均值，和含有k 种颜色成分的颜色直 方图【，”。它的纹理特征是t a m u r a 纹理表示的改进，即租糙度、对比度，方向性 的组合它的形状特征包括形状的面积、循环性、离心率、主轴方向和一系列代 数不变矩l ，”q b i c 是少数使用高维特征索引的系统之一在它的索引子系统 中，首先使用k l 变换执行降维处理，然后使用”树作为多维特征索引的结构 m ) 刿在它的新系统中，基于文本关键字的查询可以和基于内容相似性的查询 结合使用。 1 6 2 v i r a g e v i r a g e 是v i r a g e 公司研发的一个基于内容的图像搜索引擎。和q b i c 相似， v i r a g e 支持基于颜色、合成( 颜色布局) 、纹理和结构( 对象的边缘信息) 的视 觉查询。但是v i r a g e 比q b i c 更进一步，它还支持以上四种原子查询的任意组合， 而且用户可以根据他们关注的特征不同，来调整组合查询中的权重。j e f f r e y 等 人为图像管理提出了一种开放式框架结构一”。他们将视觉特征分类为一般性的 ( 例如颜色、形状或纹理) 和特殊领域性的( 例如人脸识别、癌细胞检测等) 。 根据研究领域的需要，还可以将各种基元加入到开发式框架结构中。除了基于范 例的模式之外，g u p t a 和j a i n 提出了用“九元素查询语言”检索框架。 基于显著点和关键块相结合的图像检索方法 1 6 3 v i s u a l s e e k 和w 曲s e e k v i s u a l s e e k 是一个视觉特征搜索引擎嘲，6 1 1 ，w e b s e e k 是面向万维网的文 本、图像搜索引擎【6 2 1 ，它们都是哥伦比亚大学研发的，其主要研究的内容是图 像区域的空间关系查询和压缩领域的视觉特征提取。这两个系统用到的视觉特征 是颜色集和基于纹理特征的小波变换矢量集。为了加快检索速度，它们使用基于 二叉树