（计算机应用技术专业论文）基于查询向量转移和聚类相结合的相关反馈技术研究.pdf

摘要 随着信息技术的迅猛发展和数字图像应用的f 1 趋广泛，许多大型、复杂的图像信息 库不断涌现出来。如何从海量的数字图像中快速准确地找到所需要的图像数据越来越受 到人们的关注。当传统的图像检索方法不能满足实际需求时，相关反馈技术被引入进来， 成为图像研究领域的新的热点问题之一。 本文研究了基于颜色的图像检索相关技术，在对颜色空| 、日j 信息深入分析的基础上， 提出了基于分块二值化思想的图像检索方法。该方法能够较准确的分割出图像的目标和 背景，突出图像目标在检索中的主体地位，更加符合人眼对图像的识别要求。实验证明， 该方法能够更有针对性地检索图像，较大程度的提高查准率。 本文在对向量转移反馈算法的研究基础上，将查询向量转移算法和聚类算法结合起 来，并对向量转移的精度和速度进行改进，使图像的特征向量在聚类的过程中充分利用 用户的反馈信息，更迅速更精确的向所属类的中心转移，与查询向量不相关的类中的向 量则勿需转移。该算法缩小了运算代价，减少了反馈次数，同时提高了图像的检索效率。 最后，本文构建了一个具有相关反馈机制的基于颜色特征的图像检索系统，对本文 提出的几种改进算法进行了实验比较和性能分析。实验数据表明，本文算法具有更优的 检索效率。 关键词：图像检索，颜色，相关反馈，聚类，向量转移 s e a r c ho nr e l e v a n c ef e e d b a c kb a s e dc l u s t e r i n g a n dv e c t o rt r a n s f e r r i n g j i a n gx i a o h o n g ( c o m p u t e ra p p l i c a t i o nt e c h n o l o g y ) d i r e c t e db yp r o f e s s o rz h e n gq i u m e i a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fi n f o r m a t i o nt e c h n o l o g ya n dt h ew i d e l ya p p li c a t i o no f d i g i t a li m a g e s ，m o r ea n dm o r ec o m p l i c a t e da n dl a r g ei m a g ei n f o r m a t i o nd a t a b a s ec o m ef o r t h h o wt of i n dt h ei m a g ed a t aw en e e df l e e t l ya n dp r e c i s e l yi sa t t r a c t e db ym o r ea n dm o r e p e o p l e w h e nt r a d i t i o n a li m a g er e t r i e v a lm e t h o d sa r en om o r ea p p r o p r i a t e df o rp r a c t i c a l r e q u i r e m e n t ，r e l e v a n c ef e e d b a c kt e c h n o l o g yh a sb e e ni n t r o d u c e da n db e c o m eo n eo ft h e h o t t e s tr e s e a r c ha r e a si ni m a g ed o m a i n t h et h e s i ss t u d i e st h ec o l o r - b a s e di m a g er e t r i e v a lt e c h n i q u ea n dp r o p o s e st h em e t h o do f i m a g er e t r i e v a lb a s e do np a r t i t i o na n db i n a r yo nb a s eo fa n a l y s i so fp l a c ei n f o r m a t i o no fc o l o r t h em e t h o dc o u l dd i v i d ei m a g ei n t of o r e g r o u n da n db a c k g r o u n dp r e c i s e l y , g i v ep r o m i n e n c e t of o r e g r o u n di ni m a g er e t r i e v a l ，a c c o r dw i t hh u m a nv i s u a lp e r c e p t i o n e x p e r i m e n t a lr e s u l t s p r o v et h a tt h em e t h o dc o u l dr e t r i e v ei m a g e sm o r ep u r p o s e f u l l ya n di m p r o v ep r e c i s i o ng r e a t l y o nt h eb a s i so fs t u d y i n gv e c t o r - t r a n s f e r r i n gr e l e v a n c ef e e d b a c k ，t h et h e s i sc o m b i n e s v e c t o r - t r a n s f e r r i n ga n dc l u s t e r i n g ，a n di n c r e a s e st h es p e e da n dp r e c i s i o no fv e c t o r - t r a n s f e r i m a g e f e a l u r ev e c t o r st r a n s f e rt oc l u s t e r i n gc e n t e rw h i c ht h e yb e l o n gt om o r ef l e e t l ya n dp r e c i s e l yb yg o o d u s eo fu s e r s r e l e v a n c ef e e d b a c ki n f o r m a t i o n t h ea r i t h m e t i ch a sl e s s c o s t ，l e s st i m e so f f e e d b a c ka n dh i g h e re f f i c i e n c yo fi m a g er e t r i e v a l ac o l o r - b a s e di m a g er e t r i e v a l s y s t e mw h i c hi m p l e m e n t st h et e c h n i q u eo fr e l e v a n c e f e e d b a c ki sc o n s t r u c t e d t h et h e s i s sa r i t h m e t i ca r e c o m p a r e dw i t he a c ho t h e ro np e r f o r m a n c e ， a n d b yt h ee x p e r i m e n t a ld a t at h e yh a v eb e a e rr e t r i e v a le f f i c i e n c y k e y w o r d s ：i m a g er e t r i e v a l ，c o l o r , r e l e v a n c ef e e d b a c k ，c l u s t e r i n g ，v e c t o r - t r a n s f e r r i n g 关于学位论文的独创性声明 本人郑重声明：所呈交的论文是本人在指导教师指导下独立进行研究工作所取得的 成果，论文中有关资料和数据足实事求是的。尽我所知，除文中已经加以标注和致谢外， 本论文不包含其他人已经发表或撰写的研究成果，也不包含本人或他人为获得中国石油 大学( 华东) 或其它教育机构的学位或学历证书而使用过的材料。与我一同工作的同志 对研究所做的任何贡献均已在论文中作出了明确的说明。 若有不实之处，本人愿意承担相关法律责任。 学位论文作者签名：整盘红同期：u 叼够年多月- 6 同 学位论文使用授权书 本人完全同意中国石油大学( 华东) 有权使用本学位论文( 包括但不限于其印刷版 和电子版) ，使用方式包括但不限于：保留学位论文，按规定向国家有关部门( 机构) 送交学位论文，以学术交流为目的赠送和交换学位论文，允许学位论文被查阅、借阅和 复印，将学位论文的全部或部分内容编入有关数据库进行检索，采用影印、缩印或其他 复制手段保存学位论文。 保密学位论文在解密后的使用授权同上。 学位论文作者签名： 指导教师签名： 藉魂江 日期：如d g 年 日期：弘加艿年 专月。6f i f 月吃r 中罔油人学( o 仁东) 顾i j 学位论文 1 1引言 第一章绪论 随着网络和多媒体技术的飞速发展，互联网上的信息由单一的文本方式逐步发展到 以图像、视频、音频、动画等多媒体信息为主的表现方式，数字图像的应用同益广泛， 成为信息社会的主要资源之一。如何从浩瀚的多媒体信息中查询到用户感兴趣的图像成 为了一个极具挑战性的问题。近年来，研究人员试图用基于内容的图像检索 ( c o n t e n t b a s e di m a g er e t r i e v a l ，c b i r ) 方法来解决这个难题。目前基于内容的图像检索 技术1 1 1 已发展成为涉及图像处理、模式识别、人工智能、神经网络及数掘库技术等多种 学科的一种图像媒体检索技术。其基本步骤是：先提取图像的底层特征，如颜色、纹理、 形状等，然后基于这些特征把用户想要查询的图像与数据库中的图像做相似度的运算， 从而实现图像的检索。但图像检索系统都存在一个主要问题，就足枪索过程是以计算机 为中心，使得奄洵结果不能很好地满足用户的需求。由于人们在h 常生活中使用的是高 层次的概念( 如房屋、汽车) ，而计算机依靠其视觉特征，从图像中提取的是底层的特 征( 如颜色形状) ，很难直接建立从底层特征到高层特征之i n j 的映射。为解决这个问题， 人们又把相关反馈技术用于c b i r ，通过引入用户的反馈信息以获得更好的检索效果。 1 2 研究目的及意义 本文的研究重点为相关反馈技术在图像检索领域中的应用。相关反馈技术最早是在 文本检索领域中被提出的，应用到图像检索领域中以后，在短短的几年时间旱，已经提 出了很多种技术方法，目日i 仍然是一个十分活跃的研究课题。基于内容的图像检索技术 中所提取的图像特征是图像的底层视觉特征，它们无法体现图像的实际语义。因此，无 论采用何种特征，使用何种相似性度量方法，最终决定两幅图像足否相似还是取决于实 际用户。基于内容的图像检索系统应尽可能地做到以用户为中心，而不是以计算机为中 心。另外，由于侧重点的不同，不同的用户对图像相似性的判断也存在不同的标准。为 此需要研究如何使系统自动适应这种特定的需求，以获得更好的查询结果，相关反馈是 提高系统检索效果的一种强有力的方法。 相关反馈的目的就是在用户与查询系统的实际交互过程中进行学习，发现并捕捉用 户的实际查询意图，一次次修正系统的查询策略，得到与用户实际需求尽可能吻合的查 筛章绪论 询结果。由于相关反馈可以实时地修改系统的查询策略，从而为图像柃索系统增加了自 适应功能。相关反馈技术能促进图像检索技术的发展和应用，推动图像技术的发展、丰 富信息处理理论、解决信息膨胀，因此基于内容的图像检索反馈机制研究有着重要的研 究意义和应用价值，是当f j 图像检索的热点和趋势。 1 3 研究现状 c b i r 领域的研究起步于二十世纪八十年代，从9 0 年代中期丌始，逐渐成为热门研 究领域。通过十多年的深入研究，c b i r 得到了许多国际学术组织的重视和关注，并在 许多方面有了新的进展。c b i r 结合了图像处理、图像识别、数据库三个领域的技术， 并且现在多种成果丌始转化为应用技术。随着这些技术的不断成熟，c b i r 已经被广泛 的应用到了网络搜索引擎、数字图书馆图像检索、商标检索等领域。 随着相关反馈技术的兴起和发展，1 9 9 7 年r u i 提出了将相关反馈用于图像检索中的 具体方法，并于1 9 9 8 年在m a r s 系统中首次将相关反馈应用于基于内容的图像检索， 自此采用相关反馈法进行图像检索的研究丌始多起来，许多当日盯的实用及原型系统也都 引入了相关反馈来提高系统的性能。 在此列举一些国内外具有代表性的图像检索及相关反馈系统，并分别对它们的结构 功能以及相关技术进行介绍： ( 1 ) q b i c 系统1 2 j 。q b i c ( q u e r yb yi m a g ec o n t e n t ) 是由国际商用机器公司i b m ( i n t e r n a t i o n a lb u s i n e s sm a c h i n e r y ) 著名的a l m a d e n 实验室开发的第一个商业化的基于 内容的图像检索系统。它是目前应用最广的图像检索系统，支持用户使用例子查询、草 图查询和指定特征等查询方式，提供了四种图像特征( 颜色、颜色布局、纹理和形状) 的检索功能。颜色特性的查询包括颜色百分比查询和颜色分布查询，利用颜色百分比查 询，用户可以找到具有相似颜色及比例的图像，而利用颜色分布查询可进一步找到不仅 颜色相似且颜色分布也相似的图像。纹理特性采用改进的t a m u r a 纹理表示法，是对图 像中线条的粗糙性、对比性、方向性三者的综合考虑。形状信息采用面积、圆形度、偏 心度、矩不变量等。在q b i c 的最新版系统中，除了上面的基于图像特性的检索，还辅 以文本查询手段，较好地实现了基于文本的关键词查找方式与基于图像特征的相似性查 找方式的结合。该系统的框架和采用的技术对后来的图像检索系统产生了深刻的影响。 ( 2 ) m a r s 系统1 3 j 。m a r s 是多媒体分析检索系统( m u l t i m e d i a a n a l y s i sa n dr e t r i e v a l s y s t e m ) ，它是由美国伊利诺斯大学开发的。m a r s 无论在研究角度还足应用领域都和 2 中阳山油人学( f # 东) 坝i j 学位论文 其它的图像检索系统有很大的差异，这主要体现在m a r s 是一个多交叉学科融合的产 物，包括计算机视觉、数据库管理系统以及传统的信息检索技术。m a r s 在科研方面的 主要特点包括数据库管理系统d b m s 和信息检索技术i r 的结合( 如何进行分级的精确 匹配) ，索引和检索技术的融合( 检索算法如何发挥底层索引结构的优点) ，以及计算机 和人的融合( 相关反馈技术) 。m a r s 系统的主要目的不在于寻找单个的最佳特征表示， 而在于如何将图像不同的外观特征组织成有意义的检索体系，以动态适应不同用户及应 用场合。m a r s 系统是正式提出相关反馈( r e l e v a n c ef e e d b a c k ，r f ) 的图像检索系统。 ( 3 ) p h o t o b o o k 系统1 4 j 。p h o t o b o o k 是美国麻省理工学院的多媒体实验室所开发的用 于图像查询和浏览的交_ 瓦式工具。它主要包括三个子模块，分别用以提取形状、纹理、 人脸特征。这样一来，用户就可以分别在这三个子系统中根据相应的特征来进行查找。 然而，对于不同的领域，没有哪一种“最好”的特征能够单独地描述一幅图像。所以， 在p h o t o b o o k 更新一些的版本f o u r e y e s 中，p i c a r d 等人提出了把用户加入到图像注释和 检索中的想法，因为他们发现没有哪个图像特征可以适用于任何领域。更进一步，由于 人的感知是主观的，他们又提出了“模型集合”( s o c i e t yo f m o d e l ) 来结合人的冈素。实 验表明，这种方法对于交互式图像注释来说非常有效。 ( 4 ) v i s u a l s e e k 和w e b s e e k p j 。v i s u a l s e e k 和w e b s e e k 是由美国哥伦比亚大学开 发的姊妹系统，其主要技术特点是采用了图像区域之问空间关系和从压缩域中提取的视 觉特征。系统中主要使用的特征是颜色特征和基于小波变换的纹理特征。为了加速查淘 过程，系统也开发了基于二叉树的索引算法。其中，v i s u a l s e e k 同时支持视觉特征和 空问关系的查询。例如用户要查询“同落”图像，其提交的查询条件可以是这样一个草 图：上面是橘红颜色区域，底部是蓝或绿的区域。w e b s e e k 主要是面向w e b 查询的。 它包含有3 个模块：图像采集模块，分类和索引模块，查询、浏览和检索模块。它同时 支持关键字查询和视觉特征查询。 ( 5 ) p i c h u n t e r 系统【6 j 。p i c h u n t e r 系统是由c o x 等丌发出来的、具有代表性的结合相 关反馈的图像检索系统。在实施相关反馈时，数据库中的每幅图都根据其与f 例图像的 距离进行记分，这样特征空间中向量的相关位置才是有意义的。距离的度量在全局方式 中不受影响。可以赋给每个图像特征描述的分量一个权值，这个权值用于计算图像i 、日j 的 距离，然后根据用户的响应对这些权值进行修改。这样在j 下例图像中具有最小变化的特 征分量就会获得最大权值。也可以根据j 下例图像和所有显示图像的逆方差的不同进行加 权。该系统的缺点就是没有考虑负图像所起的作用。 3 第一章绪论 近年来，国内在图像检索技术的研究方面也取得了很人的进展，其中从事基于内容 的图像检索研究比较有名的有清华大学、中科院自动化所、浙江大学计算机系等。取得 的主要成果有，浙江大学计算机系研究的基于图像颜色的检索系统和基于图像形状的检 索系统、清华大学的i n t e m e t 上静念图像的c b i r 的原型系统、中国科学院计算机技术 研究所的多媒体信息检索系统( m u l t i m e d i ai n f o r m a t i o nr e t r i e v a ls y s t e m ，m i r e s i7 】) 等。 其中，m i r e s 是中科院计算所智能信息处理重点实验室，在国家9 6 3 计划支持下研制 的，可以完成示例图像、关键词或两种模式交互混合三种方式的检索，允许用户设置各 种特征的权重因子，支持相关反馈。复旦大学计算机科学系在一种图像语义信息和视觉 特征相结合的相关反馈方法基础上实现了一个基于内容的图像检索系统i f i n d ，较其它 基于视觉特征的图像检索系统而言在图像检索性能上有了很大的改善【8 】。 1 4 本文主要研究内容 本文论述了基于内容的图像检索的关键技术：针对颜色空间特征，提出了一种基于 分块二值化图像检索算法，突出了图像中目标图像的主体地位，获得了较好的检索性能； 对查询向量转移反馈算法进行了深入研究，提出了一种提高向量转移精度和速度的改进 反馈算法；将查询向量转移算法与聚类算法相结合，融合二者的优点，提高了相关反馈 算法的检索效率；开发了一个带有相关反馈机制的图像检索系统，实现了各种改进算法 并与传统算法进行了比较和分析。 1 5 论文结构 本文以后各章的研究内容如下： 第一章绪论 阐述了基于内容的图像检索技术的产生背景和研究现状，同时介绍了本文的主要研 究工作内容和结构安排。 第二章相关关键技术 介绍了在基于内容图像检索中涉及的关键技术，包括图像特征提取、相似性度量、 相关反馈算法、聚类方法以及系统性能评价标准。 第三章基于聚类和向量转移相结合的相关反馈算法研究 对传统的向量转移和聚类反馈算法进行了改进，将二者结合起来，在聚类过程中根 据用户的反馈信息调整特征向量，从而提高检索效率。实验证明，该方法能够改善检索 4 中罔4 j 由人学( # 东) f ! i ii 学位沦义 结果。 第四章基于相关反馈的图像检索系统的设计与实现 基于第三章的改进算法构造了一个带有相关反馈机制的图像检索原型系统，并对实 验结果进行分析、比较和评价。 总结 对全文的创新点、理论和实际意义做了一个总结，列出论文完成的主要工作，指出 进一步的研究方向。 5 第_ 二帚相关关键技术 第二章相关关键技术 基于内容的图像检索利用图像的视觉内容，如颜色、纹理、形状和空i 日j 关系来表示 图像，设计了图像处理、数据库、机器学习等多方面的技术。本章首先介绍基于内容的 图像检索系统模型，其中包括图像的底层特征提取、相似性匹配等基本技术，然后再对 相关反馈技术以及检索性能评价标准进行介绍。 2 1基于内容的图像检索 2 0 世纪7 0 年代，图像数据研究者们提出并研究了基于文本方式的图像检索，但基 于文本的图像检索方式存在着很大的难题：完全手工注解的工作量太大；文本注解不可 避免的存在主观性和不精确性。事实上，图像内容带给人们的信息是多方面的，没有入 仅仅借助标号来回忆场景，对图像信息的检索需要根据图像所表达的内容来进行，因此， 人们提出了基于内容的图像检索技术【9 1 。 基于内容的图像检索利用图像的视觉内容，如颜色、纹理、形状、空间关系来表示 图像，涉及了图像处理、数据库、模式识别等多方面的技术。基于内容的图像检索技术 依靠计算机自动提取图像特征并存入图像特征库，检索时依据图像特征比较特征库中的 对应信息，最后将最佳的匹配结果和相关信息输出给用户【旧1 ，过程如图所示： 用 ! 户 f 台 ：询 接 口 2 1 1 图像特征提取 图像台询端 i 图像管理端 ： 图2 1 图像检索系统结构图 f i 9 2 is y s t e ms t r u c t u r ec h a r to fi m a g er e t r i e v a l 图像的特征提取是基于内容的图像检索技术的基础。图像特征实际是人对图像视觉 感受的量化描述，它在一定程度上描述了图像的内在语义，从而可以作为图像的抽象表 6 一雎一；： 岬卫 一 中冈石油人学( o 仁东) 坝i j 学位论文 不。 经过多年的研究，基于内容的图像检索技术仍将研究重点放在底层特征的提取。因 为底层特征最能够直观的表达图像内容，并且底层研究是语义等上层研究的基础，为了 给上层建立准确、有效的图像特征提取方法，底层的研究仍在不断发展。现有的图像检 索系统主要是根据图像的颜色、纹理、形状以及空i 日j 特征等底层图像特征，提取图像特 征向量。 一、颜色特征 颜色特征是在图像检索中应用最为广泛的视觉特征f l l 】，因为颜色往往和图像中包含 的内容十分相关，而且，与其它视觉特征相比，颜色特征对图像的大小、方向、角度的 依赖性较小，有较好的鲁棒性。本文将主要介绍颜色直方图、累计直方图、颜色矩、颜 色集等颜色特征的表示方法及其优缺点。 ( 1 ) 颜色直方图 颜色直方图是最常用的颜色特征。最早使用该方法的是s w a i n 和b a l l a r d l l2 1 ，其核 心思想是在一定的颜色空间中对各种颜色出现的频数进行统计，因此颜色直方图是一个 n 维向量 h ( f ，f ) ，i = l ，2 ，n ，n 是颜色或灰度级数。然后采用颜色直方图的交来度量 两幅图像的相似性。 图像直方图的优点在于对图像的平移和旋转都具有不变性。当对直方图进行归一 化，则归一化直方图对图像的尺寸具有不变性，其最大的缺点是完全丢失了图像色彩的 空间信息。 ( 2 ) 累计直方图 当图像颜色不能取遍所有的可取值时，颜色直方图中会出现若干个零值。这些零值 会影响直方图相交的计算结果，从而使匹配值不能正确地反映两幅图像之问的颜色差 别。为了改进这个不足，以颜色作为横坐标，以颜色频数的累计作为纵坐标，引入累计 直方图【1 3 i 。 累计直方图可以有效地解决零值问题。而且在一般情况下，使用累计直方图检索图 像的效果要优于统计直方图。 无论哪种直方图，都要对颜色特征进行量化。量化区问越多，准确性越高，但运算 代价越大。一些改进方法将直方图结合空问信息，将图像分割成若干子块，分别计算各 子块中的颜色直方图。 7 第一：章相关天 矬技术 ( 3 ) 颜色矩 颜色矩是由s t r i c k e r 和o r e n g o 提出的一种简单而有效的颜色特征，其数学皋础在于 图像中任何的颜色分布均可以用它的矩表示【1 4 1 。而且，颜色分布信息主要集中在低阶矩 中，因此仅采用颜色的一阶矩、二阶矩和三阶矩就足以表达图像的颜色分布。与颜色直 方图相比，该方法的另一个好处在于无需对特征进行量化。 ( 4 ) 颜色集 为了支持大规模图像库中的快速查找，s m i t h 和c h a n g 提出了用颜色集( c o l o rs e t s ) 作为对颜色直方图的一种近似f 1 5 】。其基本过程是先将r g b 颜色空间转化成视觉均衡的 颜色空间( 如h s v 空间) ，并将颜色空i 日j 量化成若干个b i n 。然后，他们用色彩自动分割 技术将图像分为若干区域，每个区域用量化颜色空问的某个颜色分量来索引，从而将图 像表达成一个二进制的颜色索引集。在图像匹配中，比较不同图像颜色集之问的距离和 色彩区域的空问关系( 包括区域的分离、包含、交等，每种对应于不同的评分) 。因为 颜色集表达为二进制的特征向量，可以构造二分查找树来加快检索速度，这对于大规模 的图像集合十分有利。 颜色特征具有较强的鲁棒性，是最可靠、最稳定的特征，但由于图像全体颜色均参 与检索，反而丧失了图像的目标主体地位。本文通过引入二值化思想和颜色空间关系对 颜色特征检索进行改进，突出了图像目标的重要性，获得了较好的实验结果。 二、纹理特征 纹理特征是图像的另一个重要特征，它反应了图像的空问分稀信息和结构信息【1 6 】。 纹理特征不依赖于图像的颜色或亮度，它是物体表面共有的内在特性，表达了物体表面 颜色和灰度的某种变化，例如云彩、树木、砖墙、织物等都有各自的纹理特征。纹理实 质上是由一个具有一定不变性的视觉基元( 统称纹理基元) ，在给定区域内的不同位置 上，以不同的形变及不同的方向重复出现的一种图纹。 纹理通常被认为是像素狄度值在空问区域的变化模式，所以数字图像中的纹理就是 向量像素的灰度或颜色的空间相关性，或是图像灰度和颜色随空间位置变化的视觉表 现。由于纹理特征可用来对图像中的空l 日j 信息进行一定程度的定量描述，所以纹理特征 也在c b i r 技术中广泛应用【1 7 1 。纹理特征的提取方法主要有三种：统计法、结构法及频 谱法【1 8 】。由于纹理特征不足本文研究的重点，这旱不做过多陈述。 三、形状特征 形状特征也是图像的重要特征之一。图像的形状信息不随图像颜色等特征的变化而 8 中困吖j 油人学( o 坪东) 硕i ：学位论义 变化，是物体稳定的特征。但相对于颜色和纹理特征来说，用形状特征检索比较困难。 因为，形状特征的提取必须建立在对图像中的物体或区域准确划分的基础之上，而目前 的技术还彳i 能实现对图像的准确而鲁棒的自动分割。另外，人们对物体形状的变换、旋 转和缩放主观上不太敏感，合适的形状特征应满足变换、旋转和缩放的不变性，这对形 状特征的相似度计算也带来了难度【1 9 】。 通常来说，根据特征提取方式的不同，形状特征的表示方法分为两类：一类是轮廓 特征2 0 1 ，一类足区域特征。前者只用到物体的外边界，而后者关系到整个形状区域。 2 1 21 1 1 化x 度匹配 在基于内容的图像检索中，两幅图像是否相似就是指它们的特征是否相似。如何用 数值来表示图像在特征上的相似程度，就是相似度匹配问题。定义一个合适的图像特征 相似度匹配方法对检索效果有很大的影响。由于图像特征大多可以表示成向量的形式， 因此常用的相似度匹配方法都是向量空间模型，即将视觉特征看作是向量空间中的点， 通过计算两个点之f 日j 的接近程度，来衡量图像特征间的相似度2 1 1 。多年以来，人们对相 似度匹配方法进行了广泛的研究，提出了多种匹配方案。下面介绍几种常用的相似度匹 配方法： ( 1 ) l 1 距离和l 2 距离 如果图像特征的各分量之间是正交无关的，而且各维度的重要程度相同，则两个特 征向量a 和b 之间距离可以用l l 距离或者l 2 距离( 即欧氏距离) 柬度量。l 1 距离可 以表示为： q = la 。- b , l ( 2 1 ) 其中是特征向量的维数。该距离计算复杂度低，常常用于具有平等关系的组特征 的距离计算，特别是颜色直方图。 同样，l 2 距离( 即欧氏距离) 可以表示为： ， d 2 = ( 4 一e ) 2 ( 2 2 ) k l 欧氏距离比较合理地反映了一种人类常用的视觉相似评判准则，它不考虑向量各维 之间的差异，认为各维分量是同等重要的。通常为了适应c b l r 系统中不同特征的重要 性不同，一般采用加权欧氏距离。 9 第一二币市丌关关键于上术 ( 2 ) 直方图相交 上述两种距离常用来计算颜色直方图之f 、【1 j 的距离。计算直方图距离的另一种方法就 是直方图相交。其距离表示如下： d = r a i n ( 1 , ，q ) ( 2 - 3 ) f - l 其中，和q 是两个各含有j 7 v 个b i n 的颜色直方图。直方图相交实质是计算两个直 方图在每个b i n 中共有的像素数量。有时为了计算需要，可以通过除以其中一个直方图 的所有像素数量来实现归一化，使其值落在【0 ，1 区间之内，表示如下： m i n ( i , ，q ) s ( ，q ) = _ 矿一 ( 2 - 4 ) q ， # l 该距离一般用于以直方图为特征矢量的相似性度量，特征矢量经过归一化处理后， 直方图相交等价于l 1 距离。 ( 3 ) 二次式距离 以基于颜色直方图的图像检索为例，已经证明，二次式距离比使用欧式距离或是直 方图相交更为有效。原因在于这种距离考虑到了不同颜色之间存在的相似度，更加符合 人的视觉效果。颜色直方图，和q 之| 日j 的二次式距离可以表示为： d = ( q 一，) 7 彳( 9 一，)( 2 5 ) 其中a = 【】为相似性矩阵， 】表示直方图中第f 个和第个颜色b i n 之间的相似 度。这样，颜色直方图本身就包含了不同颜色之间的相似性因素，因此可以直接地使用 欧拉距离或直方图相交距离。这种对直方图预处理的方法的好处在于在检索过程中计算 相似度的代价较小。但a 矩阵的确定较为闪难，而且只能描述特征分量的平面关系。 ( 4 ) 马氏距离 当特征向量的各个分量之间具有相关性或者具有不同的权重，可以用马氏距离来计 算特征之i 、日j 的相似度。马氏距离的数学表达为： 绒。f = ( 彳一b ) c 叫( 彳一b )( 2 - 6 ) 其中，c 是特征向量的协方差矩阵。 当特征向量问的个分量间没有相关性时，马氏距离还可以进一步简化为： 1 0 中图钉油人学( 1 仁东) 硕i j 学位论文 p ：兰丝乒( 2 - 7 )p = 掣 ，il f 上述几种方法都是基于向量空间模型的，采用几何距离作为相似度度量。在c b i r 系统中，选择一种合适的相似性度量方法是获取满意的检索效果的重要保证。本文在权 衡了各算法的有效性和复杂性之后，选择欧氏距离和马氏距离作为本文算法的桐似度度 量方法。 2 2 相关反馈技术 基于内容的图像检索对海量图像的查找带了了方便，但是查找的准确率却不是很 高，尤其对图像语义的检索显得力不从心。因为图像检索是人查找所需要的图像，人的 主观性在图像检索中具有重要的指导性作用，因此把人的作用放到图像检索过程中就显 得非常重要。基于这一点，相关反馈( r e l e v a n c ef e e d b a c k ，r f ) 被引入基于内容的图像 检索中，并发挥了重要作用。基于相关反馈的图像检索系统结构如图： 相似性比较 结果输出图像数据库管理 图2 - 2基于相关反馈的图像检索系统结构图 f i 9 2 - 2s y s t e ms t r u c t u r ec h a r t o fi m a g er e t r i e v a lb a s e do nr e l e v a n c ef e e d b a c k 2 2 1 相关反馈技术的分类 在过去的几年罩，人们对相关反馈开展了许多研究工作，并提出了不少算法。根据 相关反馈算法所采用的检索模型把算法分为：基于修改查询向量的相关反馈算法、基于 特征权重调整的相关反馈算法、基于概率的相关反馈算法、基于机器学习的十日关反馈算 法。由于图像特征都是表示为向量形式，可以看做是空间中的点，检索过程实质上是寻 找特征空间中离查询向量最近的那些点所对应的图像，在相关反馈过程中也是一样的。 第一二章相关关键技术 下面分别介绍上面提到的几种相关反馈算法。 一、基于修改查询向量的相关反馈算法 修改查询向量的本质就是根据用户的反馈信息来调整奄询点，使之更接近理想查询 点，再用调整后的的查询点去重新计算查询结果。在每次相关反馈中，用户提交他认为 与查询相关或者不相关的例子，成为反馈f 例和反例，然后系统移动查询点，使之更加 接近反馈j 下例在特征空间中对应的点，同时远离反馈反例在特征空间中对应的点，通过 这种方式来接近理想查询点。 r u i 等人将文本检索中的相关反馈方法用于图像检索0 2 2 1 ，利用文本检索中的r i c c h i o 公式修改查询向量。r i c c h i o 公式形式如下： q = g t q 邯瓦1 ，驴吖寿，驴 ( 2 1 8 ) 其中口，和7 分别是常数；和氏为用户在上一次返回的查询结果中，选取了 一些他认为的相关图像集合和无关图像集合，即所谓的反馈币例集合和负例集合；1 ，表 示图像库中图像所对应的特征向量：尺和n n 是在& 和p u 中的图像数目。因此，可以 根据这些反馈对初始查询9 进行调整，o 是优化后的查询向量它能够通过不断的相关反 馈逐步逼近理想的最优查询向量，。每一次用户反馈后，可以计算优化的q 7 ，然后用 新的蟛为查询向量计算新的检索结果，可以逐渐提高检索精度。 r i c c h i o 公式在图像检索的相关反馈系统中得到了广泛的应用，大部分系统都是基 于这样的系统框架来实现相关反馈，如自仃面提到的m a r s 系统。基于向量转移的相关 反馈算法是本文的重点，本文在传统算法的基础上，提出了加快收敛速度的改进算法， 在第三章中会对传统算法和改进算法进行更详细的介绍。 二、基于特征权重调整的相关反馈算法 特征权重调整的基本思想是：提高那些有助于检索相关图像的特征的权重，同时降 低有碍于检索相关图像的特征的权重。其原则就是加强能使j 下例样本收敛和把正例及反 例分丌的特征分量。权重调整的方法试图通过调整各个特征及特征各维的权重来优化检 索结果。有人提出了一种利用特征标准差的算法。其基本思路是在特征空间中对特征分 布标准羞较大的特征维降低权重，反之则增加权重以提高检索的效果。同时他们提出了 一种多层的图像模型，并以此模型为基础，使用全局优化的方法来处理权值调整的问题。 1 2 中罔缸油人学( o # 东) 颂f j 学位论义 基于特征权重调整的相关反馈算法已经有了较大的研究成果及较多的算法改进。在 h u a n g 的工作中【2 3 】，距离度量采用了加权的l 1 距离，根据反馈的正例及负例经验性地 修改对应各特征分量的权值。r u i 等人用所有j 下例样本在各特征分量上取值的标准差的 倒数作为该分量的权值。他们的方法是基于这样的考虑：如果在某个特征分量上，所有 j 下例有相似的取值，那么这个特征分量就能较好地反映用户的需求；相反地，如果所有 正例的取值很分散，那么这个特征分量对于当前查询就不重要。p e n g 等人1 2 4 】用一个基 于分类的框架来估计局部特征相关性，一个特征分量的权值通过考察在该分量上靠近查 询的被用户标记的图像数量多少来计算。其中标记为相关的越多，该分量的权值越高。 a k s o y 等人【2 5 1 通过在各特征分量上比较正例的方差和全体图像的方差来调整对应的权 值。这些方法都假设特征分量间相互独立，对权值的调整在各个分量上独立进行。 三、基于密度估计的相关反馈算法 基于密度估计的相关反馈方法不是通过细化查询或距离度量，而是使用b a y e s i a n 学 习和用户相关反馈相结合柬更新数据库中所有图像的概率分布。贝叶斯方法有两个优 势，其一，对于不同的图像类别，可以定义完全不同的图像特征和相似度计算方法，所 有相关细节都将包含在计算方法中；其二，由于该模型是基于概率的，这就给设计基于 可信度传递的相关反馈算法提供了基础。假定图像的初始概率分布是均匀的，在每次迭 代时，用户可从中选择概率分布与用户希望得到的图像最相似的图像，然后使用用户提 供的信息通过相关反馈更新概率分布。简单的说就是利用现有的概率密度估计方法，通 过用户提供的j 下负反馈样本来估计正负样本类的概率分布，并以此形成决策准则来输出 检索结果。 最基本的概率密度估计方法是高斯分布假设下的概率密度估计。r u i 和i s h i k a w a 等 方法也可以看作是基于高斯分布假设的正样本类概率密度估计。这几个方法之间的主要 区别是对高斯分布的协方差矩阵做了不同的限制。 在c o x 等人的工作中f 2 创，首先定义了在给定用户目标图像的情况下用户在交互中的 行为模型，然后通过对当前用户行为的观察，根据贝叶斯规则来预测目标图像。n a s t a r l 2 7 j 通过用户的反馈信息来估计相关图像的概率分布，在进行估计时同时考虑减小检索出不 相关图像的可能性。他们假设各个特征分鼍独立，在沿各特征分量估计相关图像的分布 时，采用一种经验性的策略束考虑负例。 w u 等人针对相关反馈问题中训练样本少的困难，提出了一种基于贝叶斯规则的相 关反馈概率框架【2 8 l ，在利用标记样本的同时考虑了全体样本( 标记和未标记的样本) 的 1 3 第一二章相关关键技术 分前i 特点，以提高检索性能。 四、基于机器学习的相关反馈算法 机器学习足目自订的一个研究热点，它是以统计学习理论为基础，主要研究利用观测 数据( 样本) 学习规律，从而达到对未知数据或无法观测的数据的预测。传统的统计理 论大多研究的是样本趋向无穷大时的渐进理论，而在许多实际应用中，根本无法取得大 量的学习样本，所以传统的统计方法尽管有着相当峰实的理论基础，但往往在实际应用 中效果不尽如人意。 与传统的统计理论不同，目前的机器学习理论大多数研究在小样本情况下机器学习 的规律。这方面研究的主要代表人是v n v a p n i k ，他从2 0 世纪7 0 年代丌始致力于该领 域的研究，目自c f 已经形成了一套较为完整的理论框架。在机器学习理论的基础上，9 0 年代初他提出了一个机器学习的通用方法一支持向量机( 简称为s v m ) ，s v m 被证明 解决小样本问题具有明显的优势，因此己经被广泛的应用到模式识别的许多领域，如： 数字识别、手写体识别和人脸检测等。 图像检索中的相关反馈过程完全可以看作是小样本的学习问题，由于在实际的反馈 过程中，用户一般不会提供很多的反馈信息，所以基于样本无穷多假设的传统统计学习 理论对于图像检索中的相关反馈是不适合的，而解决小样本学习问题性能突出的s v m 能够取得较好的反馈效果。 m a c a r t h u r 等人【2 9 1 采用决策树来解决这个两类分类问题。首先用一个决策树顺序地 裁剪特征空j 日j ，直到所有在同一个划分中的点属于同一类。然后用得到的决策树把数据 库中所有的图像分类，再把落到相关叶子节点的图像按它们到查询例图的距离排序返 回。 2 2 2 相关判断的度量方式 在目日订的相关反馈方案中，多数都采用二值的相关尺度，即相关或不相关来度量用 户的相关判断。一些研究人员也认识到采用有多个相关级别的相关尺度能更好地反映用 户的偏好。文献【3 0 , 3 1 1 中的工作支持多级相关尺度，在r u i 等人的工作中采用五级的相 关尺度。五级标记为非常相关( h i g h l yr e l e v a n t ) 、相关( r e l e v a n t ) 、无标注( n o o p i n i o n ) 、 不相关( n o n - r e l e v a n t ) 、非常不相关( h i g h l yn o n - r e l e v a n t ) ，对应的权重数值分别为3 ，1 ，0 ， 一1 ，一3 。w u 等人进一步分析了进行多级相关度量的必要性，并对相关尺度的选择进 行了探索例。另外一些工作不使用相关度量尺度，只要求用户比较不同图像的相关程度， 1 4 中罔油人学( f f ；东) 彤ji j 学位论义 给出相对的判断。c o x 的工作中针对目标搜索，系统每次显示四幅检出图像，要求用户 指出其中哪一幅或几幅图像比较而言与目标图像吏相似。文献中，用户可以按照自己对 图像问的语义关系的理解来安排和调整图像在显示中的布局，使图像间的位置关系能反 映这种语义关系。 本文将上面提到的五级标记应用到相关反馈算法的改进中，获得了较好的实验结 果。 2 3 聚类 聚类是将数据集中的数据分成多个有意义的类的过程，要使类问的相似性尽可能的 小，而类内的相似性尽可能的大。聚类在数据挖掘、模式识别、图像处理和数据压缩等 领域有着广泛的应用。很显然，聚类的这种思想对基于内容的图像检索很有借鉴意义。 通过对海量图像数据集按某种相似度原则进行聚类，可以把相似的图像聚合到一起，从 而大大缩小图像搜索的范围，达到快速准确检索的目的。现有的聚类算法是将数据对象 用其特征来表示，对象表达为多维特征空间中的点，在特征空间中聚类。这和基于内容 检索非常相似，现有的聚类方法都可以应用到c b i r 中