（信号与信息处理专业论文）cbir中相关反馈技术的研究.pdf

摘要 摘要 随着网络技术的发展，基于内容的图像检索已经成为图像处理领 域一个研究热点。但由于图像理解技术发展有限，图像的视觉底层特 征与高层语义之间存在鸿沟，使基于内容的图像检索结果不能满足用 户的需求。为了克服这个困难，在图像检索中引入了人机交互的相关 反馈技术，有效的提高了系统的检索性能。论文首先对相关反馈技术 的发展现状以及特点进行了综述，然后在相关反馈技术所涉及的查询 向量修改，权值矩阵更新以及长期学习策略上进行了深入的研究。论 文取得的创新成果如下： 1 从非参数估计的角度出发，利用核密度估计理论，把经核密度估 计得到的样本分布的峰值作为更新后的查询向量，并引入均值漂 移的优化方法，通过迭代获得最优的查询向量。 2 对于当前的反馈，通过分析所有相关图像与非相关图像特征各维 的分布情况，动态更新不同特征之间权重以及每个特征各维之间 的权重来捕捉用户的查询意图。 3 从长期学习的策略出发，建立了一个有记忆性的语义树来实时记 录用户的反馈检索情况，有效的缩小了后继图像检索时的搜索空 间并提高了整个图像检索系统的检索效率。 4 针对提出的相关反馈算法，设计了一个基于w e b 的人机交互式图 像检索系统一i m a g e f in d e r 。 关键词：图像检索、相关反馈、非参数估计、均值漂移 a b s 础c r a b s t r a c t w i t h l ed e v e l o p m e n to ft h en e ”o r kt e c h o l o g y ，c o t c n t - b a s e di m a g er e t r i e v a lh a s b e e nah o ir e s e a r c j ln e l d b u t b e c a l i s eo ft h c1 i m i t 撕o no fc u r r e mi m a g eu d e r s t a n d i n g t e c l l i i o l o g ya n di h eg r e a lg a pb e t w e e nl l i g hl e v e lc o n c c p ta n dl o w1 e v e lf e a t u r e sf o ra n i m a g e ，t h cp e r f o m a n c co ft l l ec o n t e n tb a s e di m a g et e t r i c v a li sn o tg o o d i no r d e rt o o v e r c o m em e s ep r o b i c m s ，m eh u m a n c o m p u t c rj n t e r a c t i v cr e i e v a n c ef e e d b a c kt e c h n i q u e i si m p o n e dj n t om ef e 删e v 时a n dt h ep c f f d f m a n c eh a sb e e nj m p f o v e d i t h i sp a p e lf h e 主1 1 e o r ya n dt h e 曲盯a c t e fo f l b ef e 】e v 卸c cf e e d b a c kw i l | b ej m m d u c e da lf i 砧f ，a n dl h 朋o l i f p r o p o s e dm e t l i o df o c l l s c do nt h eq u c r yr e f i b i n g ，w e i g h tm a t r i xl 州a t i i l g ，a n d1 0 n g - t e r m 1 e a m i n gt e c h l l o l o g yw mb es h o 啪i nd e t a n 1 1 h em i nc o n t r i b u t i o n so ft h i sd i s s e r t a t i o n a r e a sf o l l o w s ： 1 f r o mt h ea l l i t u d eo f n - p a r a m e t r i ce s “m a t i o n ，u s i n gt h ek e m e ld e n s i t ye s t i n i a t e t e c h n i q u e ，m e a n - s h i nb a s e do p t i m 娩i gt c c h n i q u ei si m p o r t e dt ou p d a t em eq u e r y i m a g ef c a t u r c 2 f o rt h cc i f c mr e l e v a n c ef 色e d b a c k ，t h ef 色e d b a c ki n f o r m a t i o no ft h er e l e v a n ta n d j r r e l e v 曲ti m a g e si sa n “y z e d t h et w ow e j g h tm a 仃谴e sw h i c hw ec a i it h c ma sj n t e r 如dj n 打aw e j 曲fm a t r j xa r eu p d a c e d 3 a na n a m n e s t i cs e m a t i ct i e c b 勰e d 埘e v 柚c ef e e d b a c km e l h o dj sp r e s c 丑l e du s i d g t h el o n gt e n ak a m i n gs l r a t c g y u s i n gt h i sm e t h 州，t b es c a f c h i n gs p a c ef o rt h ef u t u r e q u e r yj m a g ew i ub ed e c r e a s e da n dt h ep e r f o r m a n c eo ft h ei m a g er e t r i e v a ls y s t e m w i l lb ei m p r o v c d 4 aw e b - b a s e dh u m a n c o m p u t e ri n t e r a c t i v ei m 8 9 cr e 虹i e v a l s y s t e m - 一i m a g c f i n d c rh a s b e e nd e v e l o p e d k e y w o r d s ：i m a g er c t r i e v a l ，r e l c v a i i c cf e e d b a c k ，n 伽- p a r a m e t r i ce s t i m a t i o n ，m e a ns h i f t i i y 8 7 9 1 6 9 独创性声明 本人声明，所呈交的学位论文是我个人在导师指导 下进行的研究工作及取得的研究成果。尽本人所知，除 了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得北 京交通大学或其他教学机构的学位或证书而使用过的 材料。与我一起工作的同志对本研究所做的任何贡献已 在论文中作了明确的说明并表示了谢意。 本人签名：樾 日期：j 丛年土月 关于论文使用授权的说明 本人完全了解北京交通大学有关保留、使用学位论 文的规定，即：学校有权保留送交论文的复印件，允许 论文被查阅和借阅；学校可以公布论文的全部或部分内 容，可以采用影印、缩印或其他复制手段保存论文。论 文中所有创新和成果归北京交通大学计算机与信息技 术学院所有。未经许可，任何单位和个人不得拷贝。版 权所有，违者必究。 本人签名：遥邋 日期：丛年土月 第一章绪论 1 1 课题的研究背景与意义 随着互联网的迅速普及与多媒体技术的飞速发展，数字图像的数 量快速增长，图像的应用和传播越来越广泛，但是图像的无序化问题 也变得越来越突出。这使得快速有效的寻找感兴趣的相关信息越来越 困难，迫切需要对海量的多媒体数据实施有效的管理。为了能在巨 大的图像库中快速查找到用户感兴趣的图像，一些著名的搜索引擎如 呦o o ，础t a v j s t a 和g o o g l e 等，采用关键字和描述性的文本进行查询 来实现图像的搜索。不可否认这些应用在实际中取得了相当的成功， 但也存在着一些无法回避的问题。例如：手工建立图像内容描述耗时 费力，这种描述往往带有很强的主观性，随着用户对相同图像与视频 关注点的不同，只用关键字很难将媒体中不同的对象属性及相互关系 完全描述出来，因此其通用性不好。为了克服以上困难，9 0 年代初， 建立在计算机视觉，模式识别及图像理解理论的基础之上，综合人 工智能，面向对象技术，认知心理学，数据库等多领域知识，人们提 出了基于内容的图像检索技术。基于内容的图像检索就是要根据图像 本身的颜色，纹理等特征进行检索，这项新技术已经成为一个国内外 图像处理领域一个研究热点，并成为数字化图书馆等重大研究项目中 的关键技术。近年来，一些基于内窖的图像检索系统被相继推出：如 q b i c f l 】，p h o o b 0 0 k 2 】，v i s u a l s e e k l 3 1 等。但是这些系统检索效率有限， 根本原因在于基于内容的图像检索中的相似度匹配是在图像的底层 特征上进行的，由于图像的视觉底层特征和图像的高层语义之间存在 一对多的映射关系，使得底层特征相似但在高层语义上非常不相关的 北京交通大学硕士学位论文 图像大量存在，导致许多检索系统不能满足用户的需求。为了有效的 缩小底层特征与高层语义之间的鸿沟，在基于内容的视觉信息检索系 统中通常采用两种机制：基于目标的图像匹配和相关反馈。基于目标 的图像匹配就是将图像中有意义的目标区域通过聚类等其它的一些 方法分离出来，然后在目标层上对图像进行相似性匹配，从而提高检 索系统的准确率。相关反馈则主要是通过一种人机交互机制使计算机 能够不断了解用户的查询意图，并通过逐步学习使检索结果符合用户 的满意程度。 相关反馈最初用于文本检索中，1 9 9 8 年，r “4 】等人在m a r s 系 统中首次将相关反馈应用于基于内容的图像检索中，取得了良好的效 果。相关反馈的主要b 的是通过人机交互，将用户对图像的理解反映 到系统中，在一定程度上能够弥补图像的高层语义与底层特征之间的 鸿沟。近年来，相关反馈算法已经成为基于内容的图像检索的研究热 点。 1 2 基于内容的图像检索技术 1 2 1 图像检索技术的发展历史 图像检索从7 0 年代开始便成为个非常活跃的研究领域。图像 检索技术的发展大概经历了三个发展阶段：基于文本标注的检索阶 段，基于内容的图像检索阶段和基于相关反馈技术的图像检索阶段。 基于文本标注的图像检索一个典型框架是，首先对图像用文本进 行注解，根据其内容手工将其标注为系列关键字，并对关键字建立 索引，然后用基于文本的数据库管理系统( d b m s ) 来进行图像检索。但 2 是，当图像的数量非常大的时候，基于文本标注的图像检索存在两大 困难，一是必须由人工完整地标注所有图像，费时也费力，第二个问 题在于图像所包含的信息量庞大，不同用户对于同一张图像的看法不 尽相同，这将导致对图像的标注没有一个统一标准，检索出的结果不 能很好的符合用户的需求。 9 0 年代以来，随着多媒体技术以及网络技术的飞速发展，使基于 文本标注的检索不能适应对海量图像库的检索需求。为了克服文本标 注的检索所带来的困难，人们提出了基于内容的图像检索技术，主要 是对图像的底层特征，比如说颜色，纹理和形状等进行提取，然后在 底层的特征空间上进行图像之间相似度的匹配，晟后将图像库中按照 相似度进行排序后的图像返回给用户。但是底层特征与高层语义之间 的鸿沟直存在，使得基于内容的图像检索的检索效率并不能满足用 户的要求。 为了有效的解决上述问题，文本检索中的相关反馈技术被引入进 来，产生了基于相关反馈算法的图像检索技术。通过相关反馈技术试 图建立图像的底层特征与高层语义之间的关联，从而在人为的交互后 提高整个检索系统的检索效率。 1 2 2 基于内容的图像检索技术的发展现状 纵观大量文献，我们可以将国内外图像检索的发展概括为以下几 个方面： ( 1 ) 目前有关图像特征描述的研究主要集中在几种基本的底层 特征研究上，例如颜色、纹理、形状、布局等等。其中颜色特征是研 究最广泛，同时使用也最为广泛的一种低层特征。常用的描述方法包 3 北京交通人学硕士学位论文 括颜色直方图、颜色矩和颜色集等。纹理特征的研究一直是图像理解 的一个重要研究课题，经典的方法如：共生矩阵法、t a m u r a 纹理特征 等都在以往的系统中有所体现：同时，近年来还出现了基于小波变换 的纹理特征描述方法，其中以g a b o r 小波的纹理特征描述应用最为突 出。形状特征相对于前两种特征的研究而言发展较为缓慢，主要是因 为目前图像理解技术还很不成熟，图像中的对象很难自动的分割出 来。就目前建立在区域分割基础上的形状特征描述方法而言，主要包 括以付立叶描述子为代表的基于边缘的形状特征描述，和以矩不变量 为代表的基于区域的形状特征描述。布局特征的研究为上述几种特征 描述为基础的全局描述提供了有效的补充，相关直方图法、c c v 等方 法都是布局特征与其它几种结合的产物。尽管以上几种特征已经得到 了较为广泛的研究，但是如何有效的组织和综合以上各种特征来有效 的描述图像内容仍然需要更多的关注。有关低层特征的常用描述方法 我们将在第二章中详细介绍。 ( 2 ) 在如何弥补低层视觉特征与高层语义特征之间的缺口的研 究中，目前出现了两种趋势：一是基于区域特征描述的检索方法：二 是基于相关反馈的检索方法。前者主要是想借助区域这一中层描述模 型来弥补此缺口，而后者主要是想借助人的参与来达到此目的。在基 于区域的图像检索中，关注区域相似性匹配、综合区域匹配及区域布 局关系匹配等方法在实际应用中取得了较好的检索效果：在基于相关 反馈的图像检索中，修改查询向量、修改特征分量在相似性计算中的 权重以及修改图像库分类情况等反馈更新方法在实际系统中取得了 相当好的效果。然而在如何实现有效的区域匹配及如何减少相关反馈 的反馈次数，降低用户的操作复杂度等方面仍需更多的关注。 4 ( 3 )系统设计与评价。从第一个以商业为目的检索系统q b i c 起，国内外不同的商业与研究机构已经建立1 翟哩辩确稍娟酾鞘j 掰潲 潮穗蔗嚏罐商僚慷温趱，淫漉，梨誊耐善蘸# 如岌商斟参薹型薹强 魅m 业赠割萋掣燮i 醴鞋键蟹哪鲳静鞘鼓鞠”二噬峰凇冰砌喏瞳溃倘 凄孺陋瓤挑瓢辩羁裙鲕p h 薪拜。 j ? 毳霞羹 向量空间中对图像进 行基于向量模型的操作。将数学中关于向量的一些定理和理论应用进 来，完成图像检索从具体到抽象的细化。 b 有效的特征提取方法 一个好的图像特征描述应具有以下特点：特征描述能够表达信息 1 枷裉卣髅枋鲇哂幸韵绿氐悖禾卣髅枋瞿芄槐泶镄畔1 1 x 北京交通人学硕士学位论文 1 2 4 现有的图像检索系统 在过去的十几年里，人们开发出了许多图像检索系统，既有商业 上的、也有用于学术研究的、还有因特网上图像检索引擎。我们在这 里列举一些有代表性的系统。代表性的商业系统有：i b m 的q b i c 4 1 。 v i r a g e 公司的v i ri m a g ee n g i n e 叫。 e x c a l i b u r 的v i s u a l r e t r i e v a l w a r e 等。一些学术研究的系统有：m i t 的p h o t o b o o 1 和 f o u r e v e s “。c 。1 u m b i a 大学v i s u a l s e e 。u i u c 的m a r s 。 i n r i a 的s u r f i m a g e ，u c s b 的n e t r a 1 “以及u cb e r k e l e y 的b 1 0 b w o r l d n l l 等等。 目前，总的来说商业图像检索系统还不太成功；而针对不同研究目的 的研究型系统层出不穷；一些图像搜索引擎己有不错的性能，但主要 是按文字检索。 1 3 本文的研究工作及章节安排 本文在对基本内容的图像检索中相关反馈技术作了理论研究基 础上，总结以前一些反馈技术的优点，提出了新的反馈策略。并将此 算法用于图像检索中，大大提高了检索系统的检索效率。我们的研究 工作主要集中在以下几方面： ( 1 ) 针对传统的用相关图像的均值来更新查询向量的算法，本文提 出了从非参数估计角度来分析查询向量更新，并采用均值漂移 的方法求解每次反馈中最优查询向量。 ( 2 ) 传统的相关反馈算法中，侧重于对检索回的相关图像的分析， 而忽略了非相关图像所代表的反馈信息。但是非相关图像所反 映的信息也非常重要，针对于查询图像来说，非相关图像就是 6 c b l r 中的相关反馈技术研究 第二章c b l r 中的相关反馈技术研究 2 1 引言 在图像检索中，因为人对图像的描述有相当的主观性，所以对图 像的检索结果的判定也具有主观性，同时，对图像的描述也依赖于对 图像描述特征的提取。限于目前的技术水平，所提取的描述特征还不 能完整地或全面地描述图像的内容。这些问题表明，期望通过一次搜 索就找到需要的图像在具体应用中通常是不现实的。基于内容的图像 检索技术需要随使用者的不同而调整。这种调整就是动态的和交互 的，因为这样可随时将用户的特殊要求反馈给系统，以便使检索更有 效且更接近用户的要求。由此看来有效的检索应该是一个渐进的过 程，把人的因素引入到系统中就非常必要了。这就是所谓的基于相关 反馈的图像检索系统。系统和用户通过交互逐步使检索向着接近用户 期望的方向前进，并最终达到用户的要求。检索可以看作是一个主观 和客观有机结合的过程，而反馈则是借助人机交互实现主客观结合的 重要手段。 2 2 相关反馈技术的特点 2 2 1 相关反馈的基本思想 相关反馈原是一种在文字检索系统中使用的技术，它利用用户对 先前的检索结果信息进行反馈来自动调节当前查询，也可借助人机交 互细化用低级特征表达的高层查询。它根据用户先前的检索结果与需 求相关性的反馈信息自动地调整已有的查询使之更好地吻合用户的 9 北京交通大学硕士学位论文 需求。在图像检索中，相关反馈的引入可以给检索系统提供更多的信 息，对于检索过程的正确的进行具有重要的指导作用。相关反馈的目 标是从用户与查询系统的实际交互过程中进行学习，发现并捕捉用户 的实际查询意图，并以此修正系统的查询策略，从而得到与用户实际 需求尽可能相吻合的查询结果。由于相关反馈可以实时地修改系统的 查询策略，从而为检索系增加了自适应功能。 基于内容的图像检索中相关反馈过程与文本检索中的类似，具体 过程如下： ( 1 ) 用户通过关键字，示例图或草图给出查询，系统返回初始的检 索结果： ( 2 ) 用户对当前显示的检索结果，根据自己的信息需求给出它们是 否相关或相关程度的判断； ( 3 ) 系统根据用户的反馈进行学习，返回新的检索结果。如果检索 结果满足用户的需求则结束，如果不满足，返回第二步，继续。 2 2 2 基于相关反馈的c b i r 系统基本框架 基于相关反馈的c b i r 系统主要由以下四个模块组成，特征提取模 块，特征匹配模块，用户接口模块，相关反馈模块。查询接口的形式 一般有三种：范例查询，简图查询，关键宇查询。对于图像数据库的 特征，一般情况下都是离线提取。 基于相关反馈的c b i r 系统检索框图如下所示： 北京交通大学硕士学位论文 和用户的需求之间存在的清晰联系，用户易于指定查询，系统也可以 进行有效的检索。特征描述能够明确的区分语义不相关的图像。目前 常用的特征包括颜色，纹理，形状，轮廓，运动参数及特征的空间分 布等等。这些特征的常见描述有：颜色直方图，高阶矩，基于小波的 纹理分析，形状的集合特征等。 c 有效的图像相似性度量 一般来说，图像的内容含有语义信息( 主观的) 和视觉特征( 客观 的) 。在语义信息上的相似性度量需要专家系统的帮助，这不属于c b i r 系统的范围，因此c b i r 系统的相似性的度量应建立在图像视觉特征的 基础上。通常用作图像相似性度量的距离包括欧氏距离，马氏距离， c o s i n e 距离等。此三种距离是建立在同一的向量模型的基础上，对于 特定的图像特征，也有专门针对特征本身的性质所定义的距离，例如 对于颜色直方图来说，有直方图相交距离等。 d 高效的相关反馈算法 由于图像的底层特征与高层语义之间鸿沟的存在，使得用户的查 询意图很难通过一幅图像或几幅图像来精确表示，这将导致按底层特 征相似的原则检索回的图像中存在大量语义不相关的图像。相关反馈 的引入就是要缩小此鸿沟，把图像检索系统改进成一个逐步求精的系 统。用户根据系统输出的查询结果与用户所期望的结果之间的差异， 向系统提供相关信息的反馈，让系统依照用户的反馈重新调整查询过 程，使下次的查询结果接近用户的期望。所以高效的相关反馈算法对 基于内容的图像检索起着非常关键的作用。如何有效的捕捉用户对图 像的理解以及用户反馈给系统的信息，在有限的反馈次数内提高检索 系统的检索效果是相关反馈算法设计的最终目的。 c b l r 中的相关反馈技术研究 2 2 4 相关反馈算法设计依据 在基于内容的图像检索中，相关反馈的研究非常活跃。在不到十 年的时间里，人们提出了许多相关反馈算法。对这些算法可以从不同 的角度来考察，譬如：检索中采用的视觉底层特征的类型，检索的目 的，相关度量方式以及反馈中的用户模型。从这些角度来分析算法， 就可以让我们了解算法各方面的特点。 a 不同的底层特征类型 根据特征对图像局部信息描述的程度可以把特征分为全局特征、 布局特征和区域特征“。 目前多数的基于内容的图像检索系统采用全局图像特征，如颜色 直方图、颜色矩、t e m u r a 纹理特征都属于这一类。一幅图像可以采用 多种特征来描述，如颜色，纹理等。每个特征又可以有多个表示方法。 对于这些特征和特征表示存在着两种组织形式。种是把各个特征表 示首尾相连 x 北京交通大学硕十学位论文 息的方式是把图像分割为一个个的对象，再对他们的底层特征进行提 取并用于检索。但是由于对一般性的图像进行自动分割还非常困难， 一些工作”。“3 把图像分割成一些在特征上同质的区域，然后再抽去 每个区域的特征，这种特征表示方式被称为区域特征。区域特征间的 相似性度量往往采用更复杂的方式，如文献 1 2 中提出了集成区域匹 配机制。采用区域特征的检索系统往往既可以支持按区域的检索也可 以支持按全图的检索。由于采用区域特征的情况比较复杂，在设计相 关反馈算法时，有的工作构造出新颖的学习算法“，有的工作“”把特 征的表示转换为类似的全局特征的情况，然后采用现有的一些方法。 b 不同的检索目的 按检索的目的可以把检索分为以下两类： 目标检索：用户要在图像库中找某个特定的图像。如c o 妒7 3 等人的工 作。 按类搜索：用户在图像库中寻找与查询图像相似的一类图像，这个类 对应着用户的一个主观语义概念。目前的多数研究工作对应这类检 索。 c 用户相关判断的度量方式 不同的相关反馈方案，用户的相关判断方式也不同：有采用二值 的相关尺度或多级的相关尺度进行度量的，也有采用间接方式进行度 量的。 目前多数的相关反馈方案中，都采用的是二值的相关尺度度量方 式相关或不相关，来度量用户的相关判断。一些研究人员也认识 到采用有多个相关级别的相关尺度能更好的反映用户的偏好。文献 4 ，1 8 ，1 9 中的工作支持多级相关尺度，在r u i 等人的工作“中，采 1 4 c b i r 中的相关反馈技术研究 用五级的相关尺度。另外一些工作不使用相关度量尺度，只要求用户 给出相对的判断。针对目标搜索，在c o ”的工作中，系统每次显示 四幅检索的结果，要求用户指出哪一幅或哪几幅图像与目标更接近。 在文献 2 0 ，2 1 中，用户要求按照自己对图像间的语义关系的理解来 安排或调整图像在显示中的布局，使被显示的图像间的位置关系能反 映这种理解。 2 3 图像检索中的相关反馈算法 基于相关反馈的c b i r 系统是一种通过用户对检索结果的评判将 用户模型嵌入到了图像检索系统之中，以提高图像检索的检索效率的 技术。自从上个世纪9 0 年代末，r u i 提出将相关反馈用于图像检索中 的具体方法并在m r s 系统中首次使用以后，采用相关反馈法进行图像 检索的研究开始多起来，许多当前实用及原型系统也都引入了相关反 馈来提高系统的性能，这促使许多用于图像检索中的相关反馈算法被 先后提出。目前，美国麻省理工学院，伊得诺斯大学，荷兰阿姆斯特 丹大学等相继开展了相关反馈在图像检索系统中的应用研究。虽然相 关反馈算法很多，但总的来说可以分为四种类型：查询点移动，特征 权重调整，基于传统的统计学习理论和基于机器学习理论。本节将对 这些算法进行简要介绍。 2 3 1 基于查询向量与权重更新的方法 图像检索可以看成是一种 近邻搜索，图像被表示为特征空问中 的一个点，然后根据图像的特征和查询向量之间的距离，将t 幅离查 询向量最近的图像检索出来。在此以m i n k o w s k i 距离为例：假设查询 北京交通大学硕士学位论文 向量的特征为q = ( 9 1 ) 一，吼) 7 和图像f 的特征为爿。= “l i - ，) 7 ，加权 的m i n k o w s k i 距离为： d ，( 盖，日，) = ( 叶l _ 一日，1 ) 厅 ( 2 一1 ) 马氏距离为： d 2 ( x 。，g ， ，) = ( 五一鼋) 7 f ( 置一窜) ：妻妻m 斗魄q ) 训 心。2 o 厶 、q 。、。 其中= ( q ，) 7 为权值向量，ml 】为一实对称矩阵。 在这种检索模型下，相关反馈算法的主要策略有：改进查询向量， 更新相似性度量和选择不同的距离度量。 在向量模型中。查询向量都可以表达为特征空间中的向量，即点 的形式，称为查询点。查询点移动借用基于文本检索中的相关反馈思 想，通过不断的反馈将查询图像对应的特征点朝着靠近正例、负例的 方向移动，从而输出更准确的结果。假设每次用户进行查询时，心目 中都有一个理想的查询点恰好能够准确地表达他的信息需求，称之为 理想查询点。但实际上，用户必须借助某些其他对象或手段才能够表 达他的查询请示，比如输入查询文本或者提交查询图像等，这些查询 文本或查询图像在特征空间中对应的点就是查询点。查询点应该比较 接近理想查询点，但在一般情况下两者还是有明显差距“。查询向量 优化算法的本质就是根据用户反馈信息来调整查询点，使之更加接近 理想查询点，再用调整后的查询点去重新计算检索结果。3 。“1 。在每次 相关反馈中，用户都会提交一些他所认为的与查询图像相关或者不相 关的示例图像，称为反馈正例和反馈负例。查询向量算法的具体做法 1 6 c b i r 中的相关反馈技术研究 是移动查询点，使之更加靠近反馈正例在特征空间中所对应的点，同 时远离反馈负例所对应的点，通过这种方式来接近理想查询点。大量 实验结果表明，采用优化后的查询点重新计算的检索结果明显优于前 一次的查询结果。这类算法中比较有代表性的是舭r s 系统中实现的算 法。 设初始查询向量q ，q 代表优化后的查询向量，则： q 卅+ 卢砖p 州忐磊u 。) 其中口，芦，y 是常数，足，昂为上一次返回的查询结果中，用户反馈的 相关图像集合和非相关图像集合，即所谓的反馈的正例集合和负例集 合，表示图像库中图像所对应的特征向量，表示相关图像 与非常关图像集合中的图像的数目，q 表示优化后的查询向量。因此， 可以根据这些反馈对初始查询向量q 进行调整，它能够通过不断的相 关反馈逐步逼近理想的最优查询向量q ，每一次用户反馈后，可以 计算优化的q ，然后用新的q 。作为查询向量计算新的检索结果，可以 逐渐提高检索精度。 特征权重调整算法的中心思想是非常简单直观的。以图像检索为 例，每幅图像都对应着特征空间中一个维特征向量，而检索开始时 特征空间每一维度上的权重都是相等的。在相关反馈中，对于所有反 馈正例和负例特征向量：假设所有反馈正例在某个维度上的值相差很 大，则说明这个维度和用户查询的关系并不密切，因此可以降低该维 上的权重：反之，如果所有正例在某个维度上的值非常接近，则说明 1 7 北京交通大学硕士学位论文 该维特征分量能很好地反映了查询中的某个特点，因此应该提高该维 的权重。在m a r s 系统中同样实现了这类算法，它的基本方法是用反馈 正倒某个维度上值的标准偏差束筏量该维度的权重。 p e n g 等人3 用一个基于分类的框架来估计局部特征相关性，一个 特征分量的权重值通过考察在该分量上靠近查询的c 个被用户标记的 图像来计算。在这些图像中标记为相关的越多该分量的权值也越高。 a k s o y 等人”1 通过在各特征分量上比较正例的方差和全体图像的方差 来调整对应的权值。这些方法都假设特征分量间相互独立，对权值的 修改在个分量上独立进行。 在文献 1 8 ，1 9 中，通过解一个优化问题最小化所有正例到 新的查询向量的距离和，求得最佳的查询q 和系数肘。z h o u 和h u a n g “7 1 注意到正例和负例在数量和分布上的不对称性，对他们采用不对称的 方式对待。他们提出了种的新的判别分析方法，叫做有偏向的判别 分析( b i a s e dd i s c r i m i n a t i o na n a l y s i sb d a ) 。b d a 被用来找到一 个变换，在变换后的空间中，正例更聚拢，同时负例被散开。b d a 采 用了k n e r a l 的形式后成为b i a s i i i a p ，可以处理非线性的数据。 2 3 2 基于传统的统计学习的方法 基于传统的统计学习理论：这种类型的相关反馈算法基于概率学 习理论，主要思想是把相关反馈看成是一个分类问题，大部分情况下 考虑的是两类分类的问题。如b a y e s 决策算法等为基础，通过反馈信 息，估计每幅图像与查询图像的相关概率，将高概率的图像检索出来， 从而提高检索效率。 对于每个检索样本图像，假定该图像和与其对应的所有正反馈图 1 8 c b i r 中的相关反馈技术研究 像构成了一个拥有共同语义含义的图像集合，通过对该图像集的高斯 拟合构造出该检索样本图像在特征空间的贝叶斯分类器。该分类器参 数反映了语义类在特征空间中的分布信息。同时，利用用户的正反馈 信息来不断的更新该分类器的参数。使得检索效果不断得到提高，方 便以后的用户检索。对于负反馈信息，通过对于大量试验的观察，有 理由假定负反馈样本是彼此独立的，这样通过构造一个简单的混合高 斯模型来拟合出负反馈样本在特征空间的分布，从而提高系统的检索 性能3 。 高斯分布模型是一种通用的概率分布模型。这种模型运算简单， 而且现实世界的很多事件都和高斯分布有着极大的相似性。假定n 维 空间r 中的向量x 满足高斯分布，那么x 的概率密度函数就是： 口( x f ，q “( x f 】，2 p 旺) = 二_ 百了一 ( 2 4 ) ( h ) 2i q l 2 其中，盖= k ，z ：，】，f = p “) ，s 0 ：) ，s 以) 】，基于这种分布的 假设，并建立贝叶斯分类器。可以得到x 以的概率判别函数为： & ( 盖) = l n a ( 丑) = l i l p ( x i q ) + l n p ( q ) 一三僻一) r q 一- ( 盖一q ) + i n p ( q ) + c f 2 5 2 3 3 基于机器学习的方法 基于机器学习理论：随着相关反馈技术的深入研究，许多学者将 相关反馈看作模式识别中的有监督学习或分类问题，利用成熟的、较 为新兴的机器学习理论，如神经网络”、支持向量机”1 ，b o o s t i n g 3 等，通过对样本集的学习，得出用户查询目的与图像特征之间对应的 北京交通大学硕十学位论文 模型，然后根据学习的模型指导新一轮的检索。 在p i c s o m 。”中采用了一种树结构的自组织映射图( t s s 0 m ) 在相 关反馈中进行动态数据聚类。在w o o d 的工作。“中，用户被要求判断返 回图像中被选中的区域是否和目标区域匹配( 作为正例或负例) ，然后 用k o h o n e n 的l vq 算法对这些训练样本聚类，根据用户的标记，把聚 得的类标为正或负，然后把最近邻为正类的区域对应的图像检出。在 文献”3 。“中，相关反馈被看成一个两类分类问题，采用s w 来训练分类 器。c h e n g 等“”采用o n e c l a s ss v h l 来估计相关图像特征的支持( 密度 大于0 的区域) 。o n e c l a s ss v m 在非线性变换得到的特征空间中用一 个紧致的超球来包含多数的相关图像。核技巧是种很好的处理数据 中非线性方法，加上s 良好的推广性，使这种方法比文献 1 8 ，1 9 的 方法有更好的性能。m a c a r t h u r 等人”采用决策树来解这个两类分类 问题，首先用一个决策树顺序地裁剪特征空间直到所有在同一个划分 中的点属于同一类，然后用得到的决策树把数据库中所有的图像分 类，再把落到相关叶子节点的图像按它们与查询向量的距离排序返 回。在每个特征维上，假设正例和负例都服从高斯分布，并训练一个 两类分类器；然后通过a d a b o o s t 方法”7 3 实现弱分类器的集成，从而构 造一个强的分类器。在他们的工作中，通过随机采样的方法来解决负 例样本少的问题，但相关图像也可能被当成负例。 在监督学习中，要达到好的推广性往往需要大量的标记样本，而 标记样本的搜集常常很费力。但在另一方面，未标记样本可能比较容 易获得。近些年来，为了利用未标记样本来提高分类器性能以应对标 记样本少的情况，人们提出了一些被称为半监督( s e m i s u p e r v i s e d ) 的学习方法。其中比较有代表性的有基于期望最大化的方法。”1 和 2 0 匕京交通人学硕士学位论文 几个方向作了综述。 北京交通大学硕士学位论文 算法还存在着一定的弊端：用户的反馈信息没有被充分利用，而且整 个检索系统可能需要很多次反馈才能达到一个稳定的状态1 。 本文提出了一种融合多种策略的相关反馈算法，一方面利用核密 度估计理论，把经核密度估计得到的样本分布的峰值作为更新后的查 询向量。在对此峰值的优化问题的求解上引入了基于均值漂移( m e a n s h i f t ) “”“”的优化技术，通过循环迭代快速求出更新后的查询 向量；另一方面，在考虑相关图像各类特征各维之间的权重分配的同 时，还通过分析相关图像和非相关图像来更新特征之间的权重，实时 地把握图像的语义信息以及用户的查询意图，实现图像之间相似性的 有效计算。此外在每次反馈中，对用户标注的相关图像进行奖励，对 非相关图像进行惩罚，从而在每次反馈中尽可能的去除那些底层特征 上相似但在高层语义上不相关的非相关图像给检索带来的负面影响， 使库中未被检索到的相关图像在下次反馈中有更大的机会被检索到。 实验的结果表明，本文提出的多策略融合的相关反馈技术很大程度地 提高了检索的查全率和准确率。 3 2 基于均值漂移的查询向量计算 设q 代表查询图像，p 代表图像库中的任意幅图像，q 表示图 像的特征向量空间。对查询向量的更新计算，本文将从两个不同的角 度来进行分析。 一方面，可以认为查询向量代表了所有相关图像的共性，代表了 用户的查询意图，它与用户反馈的相关图像之间具有最大的相似度。 向量之间的相似度一般用两个向量的内积来表示，反馈的过程就相当 于将图像库中相关图像与非相关图像分离的过程。根据模式识别理 论，处于原特征空间的样本通常是线性不可分的，为了将其变成线性 基于查询向量和权值矩阵动态更新的相关反馈算法 可分，可通过一个隐映射函数妒将原特征空间映射到线性可分的高维 空间中去。这样，在原特征空间中寻找新的查询向量就等价于在变换 后的高维空间中寻找能够代替当前反馈回的所有相关图像语义特征 的某一向量；也就是说，在变化后的空间中，此向量可以保证它与所 有相关图像之间的相似度之和可阱达到最大，因而有如下优化问题： q = a f g ? a x ( 芝q 妒瓴) 妒g ) ) ( 3 1 ) 其中t 表示反馈回的第f 幅相关图像的特征向量，x ，t q ，q 表示分 配给各相关图像的权重，符号“”表示两个向量之间的点积运算。 一般情况下，点积运算妒( t ，工) 可以用一个核函数t “，x ) 来代替，这样 公式( 3 1 ) 可以改写成如下形式： q 。a r g ，8 x ( 珊；七，x ) ) ( 3 2 ) 另方面，从概率密度分布的角度分析，假设属于同一语义类的 所有图像在特征空间中服从同一分布，这样该分布的峰值所对应的特 征向量可以被认为能够很好的描述该语义类的属性，也即它可以作为 新一轮反馈的查询向量。但是无法知道任何关于此分布的先验知识， 所以本文使用非参数的核密度估计方法来估计查询向量的分布情况， 因而查询向量的更新可转化为如下的优化问题： q 2a r g ? a x ( q ，( t ，z ) ) ( 3 3 ) 其中，( 鼍，x ) 代表局部核密度估计函数。从公式( 3 2 ) 和( 3 3 ) 可以 看出，无论从分类的角度，还是从核密度估计的角度，查询向量的修 改都可以等价为一个最优化的问题。在本文中，用高斯核函数来代替 ，陇，砖和瓴，z ) ： 北京交通大学硕士学位论文 q 。a l g 掣善n 耐一卜玉l r 7 2 0 2 ) ) 3 4 其中k 表示当前反馈中相关图像的数目。假设 g o ) 。q e 甲( 一o z 一葺1 1 2 2 盯2 ) ( 3 5 ) 求解更新的查询向量就等价于求解使得g 0 ) 取极值时x 的取值。根据 极值存在的必要条件，在公式( 3 5 ) 中对x 求导可得： g ( x ) 2 专m o ) 善q 唧( 一忙i | 2 2 。2 ) 其中： 。善叩印( 一忙圳2 伽2 ) ( 3 6 ) 埘“) 一。 一一z 7 乏m ，e 印( 一2 a 2 ) 被定义为均值漂移量旧”1 ，它的方向总是和密度梯度的方向一致并总 是指向密度最大的上升方向。最终的收敛点也就是更新的查询向量可 由以下的迭代算法得到，即： 口一 著叩，p ( 一”吐| l ! 2 a 2 ) z 1 善叩。p ( 一”q 2 。2 ) 均值漂移的迭代过程如图3 一l 所示。 ( 3 7 ) 图3 1 均值漂移过程示意图 为了保证上述迭代过程的收敛性，由文献m 1 可知，盯要满足以下 条件： 基于查询向量和权值矩阵动态更新的相关反馈算法 2 0 2 d x t 咖碉# 号i ) ) f f = l z j ，h ( 3 8 ) 其中d 表示图像特征向量的维数，g 表示第f 个特征向量的第j 维分 量。给定一个阈值，当迭代过程满足下述条件时 i i q “”一q ( 5 0 c ( 3 9 ) 迭代过程停止，此时的q “就是要求解的更新后的查询图像的特征向 量。 3 3 权值矩阵的更新算法 3 3 1 图像之间相似度匹配度量方法 在图像检索中，通常采用具有较好度量性能的马氏距离来计算两 幅图像之间的相似性。假设图像库中的图像为p ，查询图像为q ，其 相似性可以由以下公式”1 求得： s q ) = ( p 一岬一q ) ( 3 1 0 ) 其中，缈为表示特征各维分量的权值矩阵。 由公式( 3 1 0 ) 可以看出，一般情况下，为图像提取的多类视觉 底层特征总是按一定的比例组合成一个大的特征向量来表示一幅图 像，而且这种比例关系在整个图像检索的过程中并不发生变化。事实 上，采用不同类的特征对同一幅图像进行表示所产生的效果是不一样 的。比如说：对纹理图像用纹理特征来表示要比用颜色直方图等特征 来表示要有效的多，而对于国旗图像来说可能颜色和形状特征相对于 纹理特征来说就比较有效。这就使得检索系统在底层特征上不能根据 不同的图像自动的获取表示此图像的各个特征之间的相对重要程度 j b 京交通大学硕士学位论文 的信息。如何将这些特征有机的组合起来对有效的提高图像的检索效 果非常重要。针对上述情况，本文定义两个权值矩阵“和彤“”7 分 别表示各类特征之间以及每类特征内部在相似性计算时的权值分配 矩阵，并有： “一 w p 4 ，w “，w ：”4 )( 3 1 1 ) 形= 彬j “，一箩，孵等 ( 3 1 2 ) 其中，f ；1 ，2 ，肌，m 表示为图像提取的视觉底层特征的类数，l ，表 示第f 类特征的维数。这样，在进行相似性度量时，通过引入上述各 类特征之间权值矩阵“8 及每类特征内部权值矩阵彬“”。可以使系统 自动的获取特征向量的每一维在相似性比较中所作的贡献的同时，自 动跟踪用户的查询意图，并把这些抽象的查询意图反映到定量的特征 之间的权重上。实验表明，此权重更新方法很大地提高了检索系统的 检索性能。 3 3 2 各类特征间权值矩阵“的求解 考虑当前反馈所得到的相关图像和非相关图像的影响，本文如下 定义图像各类特征之间权值的更新算法。假设第七次反馈后，通过用 户标注返回给系统的相关图像和非相关图像集合分别为：r 。和u ，n 。 为所对图像提取的第f 类特征的维数，y 为所有相关图像的第z 类 特征的第j 维分量组成的集合，其中j = 1 ，2 ，n ，：同理对所有非相关 图像进行如上操