（计算机应用技术专业论文）矢量图形检索中的相关反馈技术研究.pdf

1 n a n j i n gu n i v e r s i t yo f a e r o n a u t i c sa n d a s t r o n a u t i c s t h eg r a d u a t es c h o o l c o l l e g e o fi n f o r m a t i o ns c i e n c ea n dt e c h n o l o g y r e s e a r c ho nr e l e v a n c ef e e d b a c ki n v e c t o rg r a p h i c sr e t r i e v a l a 刃 e s i si n c o m p u t e rs c i e n c ea n dt e c h n o l o g ye n g i n e e r i n g b y l ux i a o y a n a d v i s e db y z h o ul i a n g s u b m i t t e di np a r t i a lf u l f i l l m e n t o ft h er e q u i r e m e n t s f o rt h ed e g r e eo f m a s t e ro f e n g i n e e r i n g j a n u a r y , 2 0 1 0 承诺书 本人郑重声明：所呈交的学位论文，是本人在导师指导下， 独立进行研究工作所取得的成果。尽我所知，除文中已经注明 引用的内容外，本学位论文的研究成果不包含任何他人享有著 作权的内容。对本论文所涉及的研究工作做出贡献的其他个人 和集体，均己在文中以明确方式标明。 本人授权南京航空航天大学可以有权保留送交论文的复 印件，允许论文被查阅和借阅，可以将学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复 制手段保存论文。 ( 保密的学位论文在解密后适用本承诺书) 作者签名：磁咝艺 日 期：皇里埋二；二! i 一 南京航空航天大学硕士学位论文 摘要 相关反馈的目标是从用户与检索系统的实际交互过程中进行学习，发现并捕捉用户的实际 检索意图，并以此修正系统的检索策略，从而得到与用户实际需求尽可能相吻合的检索结果。 将相关反馈技术引入矢量图形检索中，通过无记忆的反馈和有记忆的反馈可以有效地利用用户 反馈信息捕捉用户的检索意图，以改善系统检索性能。 本文首先分析了矢量图形检索和相关反馈技术的研究现状，根据矢量图形检索需求，给出 了基于相关反馈的矢量图形检索系统框架，并对其中涉及的主要关键技术进行阐述。然后，在 广泛分析和研究已有学习算法和相关反馈算法的基础上，提出了一种基于组合分类器的相关反 馈算法。算法以每一个正负反馈样本作为唯一的训练样本形成各个独立的最近邻分类器，融合 各个分类器的预估结果，计算库中每个图形的相关分数，并引入贝叶斯查询点移动技术优化相 关分数。该算法可以充分利用每一个正负反馈样本所提供的信息，进一步提高矢量图形检索系 统的查准率。接着，针对目前现有的检索系统缺乏对用户意图的长期学习问题，本文提出了一 种基于反馈日志的个性化检索算法。该算法采用长期学习策略，根据反馈日志定义图形之间的 语义关联度，建立个性化和共性化的语义相关矩阵。在此基础上，建立用户模型以实现个性化 检索，使得系统逐渐适应不同用户的认知习惯，从而有效地改善系统检索性能。最后，给出了 基于相关反馈的矢量图形检索系统的实现，并在该系统基础上构建实验平台，验证了本文提出 的算法的有效性。 关键词：矢量图形检索，相关反馈，组合分类器，贝叶斯查询点移动，反馈日志，个性化检索 矢量图形检索中的相关反馈技术研究 a b s t r a c t t h eo b j e c t i v eo fr e l e v a n c ef e e d b a c ki st oi e a r nf r o mt h ea c t u a li n t e r a c t i o nb e t w e e nt h eu s e ra n d r e t r i e v a ls y s t e m ，d i s c o v e ra n dc a p t u r et h eu s e r sa c t u a lr e t r i e v a li n t e n t i o n ，a n dt h u st oa m e n dt h e r e t r i e v a ls t r a t e g yo ft h es y s t e mt og e tt h es e a r c hr e s u l t st h a tw i l la sm u c ha sp o s s i b l ef i tt h eu s e r s a c t u a ln e e d s i n t r o d u c i n gr e l e v a n c ef e e d b a c kt e c h n o l o g yi n t ov e c t o rg r a p h i c sr e t r i e v a la n db ym e a n s o fn o n - m e m o r yf e e d b a c ka n dm e m o r yf e e d b a c kc a ne f f e c t i v e l ym a k e 鹏eo ft h eu s e r sf e e d b a c k i n f o r m a t i o nt oc a p t u r et h eu s e r sr e t r i e v a li n t e n t i o n ，s oa st oi m p r o v et h ep e r f o r m a n c eo f t h es y s t e m f i r s t l y , t h er e s e a r c hs i t u a t i o n so fv e c t o rg r a p h i c sr e t r i e v a la n dr e l e v a n c ef e e d b a c kt e c h n o l o g ya r e a n a l y z e d a c c o r d i n gt ot h er e t r i e v a lr e q u i r e m e n t so fv e c t o rg r a p h i c s ，as y s t e mf r a m e w o r ko ft h e v e c t o rg r a p h i c sr 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 ki sp r o p o s e da n dt h ei n v o l v e dk e yt e c h n o l o g i e s a r ee l a b o r a t e d a f t e rt h a t ，o nt h eb a s i so fe x t e n s i v ea n a l y s i sa n dr e s e a r c ho ne x i s t i n gl e a r n i n g a l g o r i t h m sa n dr e l e v a n c ef e e d b a c ka l g o r i t h m s ，ar e l e v a n c ef e e d b a c ka l g o r i t h mb a s e do nc o m b i n i n g c l a s s i f i e r si sp r o p o s e d ，w h i c hc o m b i n e st h ee x p e c t e dr e s u l t sf r o mt h ei n d e p e n d e n tn e a r e s tn e i g h b o r c l a s s i f i e r sw i t ho n l yo n et r a i n i n gs a m p l ef o r m e db ye a c hp o s i t i v eo rn e g a t i v ef e e d b a c k s a m p l e ， c o m p u t e st h er e l e v a n c es c o r eo fe v e r yv e c t o rg r a p h i c sa n do p t i m i z e st h er e l e v a n c es c o r eb y i n t r o d u c i n gt h et e c h n i q u ec a l l e d b a y e s i a nq u e r ys h i f t i n g t h ea l g o r i t h mc a nt a k ef u l la d v a n t a g eo f t h ei n f o r m a t i o np r o p o s e db ye a c hp o s i t i v eo rn e g a t i v ef e e d b a c ks a m p l e ，b e s i d e si tc a nf u r t h e ri m p r o v e t h ep r e c i s i o no ft h ev e c t o rg r a p h i c sr e t r i e v a ls y s t e m n e x t ，i nv i e wo ft h ep r o b l e mt h a tt h ee x i s t i n g r e t r i e v a ls y s t e mi sl a c ko fl o n g t e r ml e a r n i n ga b o u tt h eu s e r si n t e n s i o n s ，ap e r s o n a l i z e dr e t r i e v a l a l g o r i t h mi sp r o p o s e d t h ea l g o r i t h ma d o p t sal o n g - t e r ml e a r n i n gs t r a t e g y , d e f i n e st h es e m a n t i c c o r r e l a t i o nb e t w e e nt w ov e c t o rg r a p l l i c sa c c o r d i n gt of e e d b a c kl o ga n de s t a b l i s h e sp e r s o n a l i z e da n d c o m m o ns e m a n t i cc o r r e l a t i o nm a t r i x o nt h i s b a s i s ，e s t a b l i s h i n gt h eu s e r m o d e lt or e a l i z et h e p e r s o n a l i z e dr e t r i e v a lw h i c hc a nm a k et h es y s t e mg r a d u a l l ya d a p t t ot h ec o g n i t i v eh a b i t so fd i f f e r e n t u s e r sa n de f f e c t i v e l yi m p r o v et h es y s t e mr e t r i e v a lp e r f o r m a n c e f i n a l l y , t h ei m p l e m e n t a t i o no fv e c t o r g r a p h i c sr e t r i e v a ls y s t e mb a s e do nr e l e v a n c ef e e d b a c ki sp r e s e n t e d b a s e do nt h es y s t e m , t h e e x p e r i m e n tp l a t f o r mi sb u i l tt ov e r i f yt h ee f f e c t i v e n e s so ft h ep r o p o s e da l g o r i t h m si nt h i sp a p e r k e y w o r d s ：v e c t o rg r a p h i c sr e t r i e v a l ，r e l e v a n c ef e e d b a c k ，c o m b i n i n gc l a s s i f i e r s ，b a y e s i a nq u e r y s h i f t i n g ，f e e d b a c kl o g ，p e r s o n a l i z e dr e t r i e v a l 南京航空航大人学硕士学位论文 目录 第一章绪论l 1 1 研究背景及意义l 1 2 国内外研究现状2 1 2 1 矢量图形检索技术研究现状2 1 2 2 相关反馈技术研究现状4 1 3 研究领域现存的问题6 1 4 本文主要研究内容及组织结构7 1 4 1 本文的主要研究内容：一7 1 4 2 本文的组织结构8 第二章基于相关反馈的矢量图形检索系统设计一9 2 1 系统总体框架设计9 2 。2 关键技术1 l 2 2 1 预处理1 l 2 2 2 特征提取一1 3 2 2 - 3 相似度匹配1 7 2 2 4 相关反馈1 8 2 3 本章小结一2 0 第三章基于组合分类器的相关反馈算法2 l 3 1 组合分类器2 l 3 1 1 组合分类器思想一2 1 3 1 2 分类器输出信息描述2 2 3 1 - 3 组合结构选择一2 3 3 1 4 融合规则选择2 5 3 2 基于组合分类器的相关反馈算法2 7 3 2 1 基于组合分类器的相关反馈算法设计一2 8 3 2 2 距离度量函数的选择2 9 3 2 3 相关分数计算3 0 3 2 4 相关分数优化3 2 3 3 本章小结3 4 矢量图形检索中的相关反馈技术研究 第四章基于反馈日志的个性化检索3 5 4 1 用户模型建立3 5 4 2 反馈日志的表示方法：3 6 4 2 1 相关矩阵表示法3 6 4 2 2 反馈序列表示法3 7 4 2 3 反馈序列表示法的改进3 7 4 3 基于反馈日志的语义相关矩阵的建立3 8 4 3 1 语义关联度的计算3 8 4 3 2 个性化的语义相关矩阵的建立3 9 4 3 3 共性化的语义相关矩阵的建立4 0 4 4 个性化检索算法4 l 4 5 本章小结4 4 第五章系统实现及实验结果比较分析4 5 5 1 系统设计4 5 5 1 1 功能模块4 5 5 1 2 系统类图4 7 5 1 3 时序图4 8 5 2 系统运行实例5 0 5 3 基于组合分类器的相关反馈算法有效性实验5 l 5 3 1 实验设计5l 5 3 2 实验结果5 2 5 3 3 结果分析5 3 5 4 个性化检索算法有效性实验5 4 5 4 1 实验设计5 4 5 4 2 实验结果。5 5 5 4 3 结果分析5 6 5 5 本章小结一5 7 第六章总结与展望5 8 6 1 总结5 8 6 2 展望5 9 参考文献6 0 致谢6 5 南京航空航天大学硕士学位论文 在学期间的研究成果及发表的学术论文6 6 v 矢量图形检索中的相关反馈技术研究 图表清单 图2 1 基于相关反馈的矢量图形检索系统总体框架一1 0 图2 2 去噪声处理示意l l 图2 3 三角形的拆分情况1 2 图2 4 矢量图形全局几何特征表示1 4 图2 5 顶点类型和空间关系类型1 5 图2 6 矢量图形以及对应的类型直方图。1 6 图2 7 相邻关系的拓扑图表示：一1 6 图2 8 图谱计算过程一1 7 图3 1 组合分类器串联方式结构示意2 3 图3 2 组合分类器并联方式结构示意2 4 图3 3 基于组合分类器的相关反馈检索流程2 9 图3 4 贝叶斯查询点移动技术3 2 图4 1 反馈日志的相关矩阵表示一3 6 图4 2 简单的图形语义连接网络4 1 图4 3 个性化检索算法流程4 3 图5 1 系统功能模块图一4 6 图5 2 系统类图一4 8 图5 - 3 矢量图形建库时序图。4 9 图5 4 基于相关反馈的矢量图形检索时序图5 0 图5 5 基于相关反馈的矢量图形检索界面。5 1 图5 6 基于组合分类器的相关反馈算法的查准率5 2 图5 7 基于组合分类器的相关反馈算法的查全率一5 3 图5 8 基于不同数目反馈日志记录的个性化检索算法查准率比较一5 5 图5 9 基于不同数目反馈日志记录的个性化检索算法查全率比较一5 6 表2 1 全局几何特征具体描述1 4 南京航空航天大学硕十学位论文 注释表 c b v g rc o n t e n t - b a s e dv e c t o rg r a p h i c sr e t r i e v a l 基于内容的矢量图形检索 t b r c b t d x f s v m c a d n p c c b q s r m s c m c o p m c o f m u m l x d o m n n t e x tb a s e di m a g er e t r i e v a l 基于文本的图像检索 c o n t e n tb a s e di m a g er e t r i e v a l 基于内容的图像检索 d r a w i n ge x c h a n g ef o r m a t 图形交换格式 s u p p o r tv e c t o rm a c h i n e c o m p u t e ra i d e dd e s i g n 支持向量机 计算机辅助设计 n o n d e t e r m i n i s t i cp o l y n o m i a l 非确定性多项式 c o m b i n e dc l a s s i f i e r s b a y e s i a nq u e r ys h i f t i n g r e l e v a n c em a t r i x 组合分类器 贝叶斯查询点移动 相关矩阵 s e m a n t i cc o r r e l a t i o nm a t r i x 语义相关矩阵 c o - p o s i t i v e f e e d b a c kf r e q u e n c ym a t r i x 同时正反馈频数矩阵 c o - f e e d b a c kf r e q u e n c ym a t r i x 同时反馈频数矩阵 u n i f i e dm o d e l i n gl a n g u a g e 统一建模语言 e x t e n s i b l em a k e u pl a n g u a g e 可扩展标记语言 d o c u m e n to b j e c tm o d e l n e a r e s tn e i g h b o r 文档对象模型 最近邻 南京航空航天大学硕十学位论文 1 1 研究背景及意义 第一章绪论 信息的快速增长促进了社会的发展，但在很多情况下，信息膨胀已给人类带来过多的信息 量以至于要超过人的接受能力了。当前迫切需要解决的问题是：如何有效地组织和管理这些数 据，并从中检索出自己所需要的信息。数据库技术的发展为存储和管理海量的信息提供了技术 上的保证。然而急剧增多的信息使得检索问题变的非常困难。当今世界上最著名的综合性搜索 引擎是g o o g l e ，而中文领域最大的综合性搜索引擎则是百度。不过遗憾的是目前这些主流的商 用搜索引擎，即便是针对图形图像领域的专业搜索引擎也仅仅是根据图形图像的文本关键字来 进行检索。这种搜索方式对于文本的检索有着明显的优势，但是对于图形图像等以二进制格式 为存储对象的检索领域来说则显出了其局限性【l 】。因为文本和图形图像的区别在于文本的内容 本身即是由字符串组成，而图形图像文件的内容则是由诸如0 和1 的二进制字符串组成。 作为当今计算机辅助设计( c o m p u t e ra i d e dd e s i g n ，c a d ) 和计算机辅助制造行业的主要 劳动成果之一的矢量工程图，是一种以二进制格式存储的图形文件类型。目前几乎所有的主流 c a d 软件都提供了强大的二维矢量j r ：程图绘制及编辑工具，此类工具被广泛地应用于诸如建筑 设计、电子制造、机械制造、工业设计以及医疗影像等科研、工业领域。矢量： 程图是矢量图 形的集合，它的实际意义在于向设计以外的工作传递设计信息，据估计，目前有数以兆计的矢 量工程图存在，并且每天都有大量的矢量工程图产生和传播。同时，在机械设计中一般只有2 0 左右的原创思想需要完全新的设计，而8 0 左右采用基于实例的设计方法( 通过组合或修改已 有设计) 。传统基于关键字的矢量图形检索由于人工标注费时费力、关键字选择主观性强等缺陷 难以完全满足实际工程应用的需要。因此，有效利用庞大的矢量图形资源，提高已有图形的重 用效率是智能和数字化设计领域面临的一个重要课题。 目前，基于内容的矢量图形检索( c o n t e n t - b a s e dv e c t o rg r a p h i c sr e t r i e v a l ，c b v g r ) 技术 中所抽取的图形特征基本上是图形的底层几何特征，它们与图形的实际语义是脱离的，底层几 何特征目前尚无能力辨别出图形中所包含的所有图元信息【2 】。因此，无论采用何种特征，无论 使用何种距离测度，最终决定两幅图形是否相似，还是取决于实际用户。基于内容的图形检索 系统应该尽可能地做到以用户为中心，而不是以计算机为中心。另外，由于侧重点的不同，不 同用户对图形的相似性的判断也存在不同的标准。为此需要研究如何使系统自动适应这种特定 的需求，从而实现更好的查询效果。而相关反馈技术则从机器学习的角度出发，把检索过程看 作一个人机协同工作的过程，利用人对图形语义的认知和理解来弥补计算机在这方面的不足， 矢量图形检索中的相关反馈技术研究 它是提高系统检索性能的一种有效方法。 相关反馈的目标是从用户与检索系统的实际交互过程中进行学习，发现并捕捉用户的实际 检索意图，并以此修正系统的检索策略，从而得到与用户实际需求尽可能相吻合的检索结果【3 】。 同时，由于相关反馈可以实时地修改系统的检索策略，相应地可以为矢量图形检索系统增加自 适应功能。相关反馈技术能促进矢量图形检索技术的发展和应用，因此基于内容的矢量图形检 索中的相关反馈技术研究有着重要的研究意义和应用价值，是当前矢量图形检索的热点和趋势。 1 2 国内外研究现状 1 2 1 矢量图形检索技术研究现状 传统的基于文本的图像检索【4 l 【5 1 ( t e x tb a s e di m a g er e t r i e v a l ，t b i r ) 技术，需要对图像库 中的图像逐一手工注释，耗费人力，而且当对图像描述的标准变了时，需要对整个图像库进行 重新注释。随着图像数字化进程的加速，这种检索方式越来越不能满足实际需要。近年来，基 于内容的图像检索6 】【7 1 【8 1 ( 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 ) 技术飞速发展，许多科研机构 对这一技术的发展做出了重大贡献。目前c b i r 研究的主要方向集中在：图像特征的提取，相 似性度量，相关反馈等技术。 而本文研究的对象矢量图形是不完全属于计算机图像范畴的另一种数字格式信息。矢量图 形内容隐含三个层次：底层、中间层和高层内容，分别表示矢量图形的细：肖信息、视觉信息和 语义信息。三个层次的信息实际上是对矢量图形不同程度的抽象，反映了人们对矢量图形不同 的认知程度。矢量图形的内容与图像的内容比较而言，其难点主要体现在三方面：矢量图形 的基本组成单元为笔画或基本图元，而非象素。如在工程图档中，基本图元为直线、圆、折线 等；矢量图形存储的是笔画或图元的坐标信息，而不以点阵形式存储：结构是矢量图形中 很重要的信息特征，而对其中的颜色、纹理等特征可以适当弱化，甚至不予考虑。因此采用基 于内容的图像检索方法无法完全满足矢量图形检索的要求，因为它忽略了矢量图形的结构化特 征以及其笔画所表达的语义信息，无法完整捕捉用户的意图，这使得基于内容的矢量图形检索 成为学术界的一个热点研究课题。 根据对国内外现阶段研究情况的分析，矢量图形检索大致有两类，即把检索对象视为图像 和把检索对象视为矢量图形两大类。前者的前提是把矢量图形视为计算机内可识别的基于2 5 6 位灰度值的点阵象素图像文件，之后利用图像的离散化分割方法，把图像上的象素点按一定的 规律进行识别和处理。该方法因矢量图形本身的特性限制了其进一步深入研究的可能。因为工 程图是以基本图元为设计单位，所以第二类的研究方法更符合人类对图形的认识本能。c h a n g 等 9 1 的工作可以认为是基于空间关系的图形检索研究的始祖，他们通过使用2 d s t r i n g 的方法对 2 南京航空航天大学硕士学位论文 图标图形进行建模。每个字符代表图标在二维空间关系上的位置。这种方法使得对图形的检索 转化为更简单的对字符串的匹配。文献 1 0 1 中提出了一种基于图形分类反馈技术的识别检索方 法，该算法通过采用不断交互的手段，识别草图图元并提取特征值实现。但算法的特征矩阵的 构建比较费时且对矢量图的分析归纳仍有不足之处。文献【11 1 1 2 中提出了一种基于图形拓扑关 系的检索算法，该算法通过对图形的相关拓扑信息分析，提取特征并构造邻接矩阵和内含矩阵， 可以得到理想的检索结果，但该算法仅仅适用于由线、弧等构成的简单图形。文献【1 3 】中提出 了一种基丁二空间结构的二维图形检索算法，该算法通过约束满意度原理构造检索树，对于简单 矢量图形，具有较高的检索性能，但受其空间关系思想的限制，当图形中包含的图元数量较多 时，算法的检索性能明显降低。原因是该类算法都以提取外部约束明显的特征为主，没有充分 利用图元自身的几何特征。这也是目前矢量图形检索算法中普遍存在的技术难点。 在此列举一些国内外具有代表性的矢量图形检索系统，并分别对它们的结构功能以及相关 技术进行介绍： ( 1 ) 葡萄牙里斯本大学m a n u e lj f o n s e c a 博士、j o a q u i ma j o r g e 博士以及a l f r e d of e r r e i r a 博七研制的针对二维矢量图形、手绘草图的矢量图形检索系统【1 4 】【1 5 】。该系统主要对简单矢量线 条为研究对象，能够对线条的形状等基本特征做出良好的识别，并采用了一种新的方法对矢量 图形进行分类、建立索引以及检索。同时，结合数字扫描仪器将很多矢量图形录入了该系统的 图库，丰富了其矢量图形库的内容。 ( 2 ) 美国普林斯顿大学形状检索和分析实验室开发的三维搜索引擎【l6 1 。该搜索引擎的一 个主要特点便是拥有大量的三维模型，并且数据库还在不断扩充中。系统提供了三种检索方式， 第一种是文本与二维草图，该检索类型允许输入一个或多个关键字以及l 至3 个简单的轮廓图 作为检索条件，第二种是文本与三维草图，它允许输入一个或多个关键字以及一个单独的三维 草图作为检索条件，最后一种是实例查询，即用户可以上传自己的三维模型文件作为检索条件 进行查询。目前，该小组已经展开对分子生物模型的检索研究，该系统也可以检索分子生物模 型。 ( 3 ) 吉林大学研究的简单c a d 图形检索技术可以从a u t o c a d 的d x f 格式工程图形文件 中读取基本的儿何实体【1 7 1 ，利用各实体在空间上的相邻或相近关系对图形进行子图分割，在检 索所需图形时，首先进行各个子图的检索，在检索到具有与各子图类似图形后，再检查该图形 的各子图中包含的图形是否与原子图中的图形类似以及各子图的空间关系是否相同。为了提高 检索效率，在子图的形状信息检索中使用了多维索引树。这一研究的特点是在图形检索前，按 空间关系将多个图形实体组合成一个查询单元，在查询前期处理的是图形的组合体，后期再处 理组合体内的几何实体，这种处理方式可以在查询的前期排除掉大多数不相似的查询单元及其 包含的几何实体，大大降低了查询的复杂程度，减少了查询时间。 3 矢量图形检索中的相关反馈技术研究 1 2 2 相关反馈技术研究现状 相关反馈技术起源于文本检索系鲥1 8 】，已经有3 0 多年的历史，它利用用户对先前检索结 果的反馈信息来自动调节当前查询，借助人机交互，细化用低级特征表达的高层查询。为了弥 补图像底层特征和高层语义之间的差距，在9 0 年代中期，相关反馈技术被引入到了图像检索中。 它根据用户先前检索结果与需求相关性的反馈信息自动地调整已有的查询使之更好地吻合用户 的需求。在检索过程中，用户向搜索引擎提交检索结果的相关性反馈信息，搜索引擎根据用户 反馈信息去构造一个更好的查询描述，然后利用新的描述重新计算检索结果。它将检索过程分 割为更小的检索序列，便于逐步逼近用户的意图。和文本检索以及图像检索一样，相关反馈技 术进入矢量图形检索领域是研究的必然趋势，在基于内容的矢量图形检索系统中，恰当地应用 相关反馈技术可以很好地提高系统的检索性能。近年来，人们对相关反馈开展了许多研究t 作， 并提出了多种算法。 当前研究中的相关反馈技术可以分为三种类型：基于距离度量的方法、基于概率框架的方 法和i 基于机器学习的方法。 ( 1 ) 基于距离度量的方法 在这种检索模型下，相关反馈的主要策略有查询向量转移以及调整特征权重。查询向量转 移算法是文本检索中的经典反馈算法，它通过修改查询向量使其向相关结果的中心移动来改进 查询结果，这种算法较为直观简单。1 9 9 7 年，y o n gr u i 在图像检索中引入了该算法【1 9 1 ，并提出 修改距离公式的相关反馈算法。j i n gh u a n g 后来提出了另一种修改距离公式的方法也就是调整 特征权重算法【2 们。通过利用反馈信息来修改距离公式各分量的权重，突出查询向量中较为重要 的分量，修改依据是相关结果各分量的离散度。特征空间中的距离公式如果采用欧式距离，如 o ( x ，g ) = g ，g ) r g ，q ) ，如果采用加权欧式距离以调整各个分量的重要性，如 d ( x ，g ) = g ，g ) r 彳g ，g ) ，a 为对角矩阵，经过反馈后，与查询向量等距离的点则构成沿坐标 轴方向的超椭球面。 1 9 9 8 年，i s h i k a w a 扩展了距离公式使其可以为全矩阵形式的广义欧式距离【2 1 1 ，如 d g ，q ) - - g ，g y 形g ，g ) ，形为全矩阵，与距离查询向量等距离的点构成任意方向的超椭球面。 i s h i k a w a 定义了反馈的优化函数：最小化各正例结果与查询向量的距离之和，通过求解优化问 题得到矩阵形，并将优化后的查询向量设为各正例检索结果的加权平均，这种形式的距离公式 显然比对角形式的距离公式更能捕捉正例对象的空间分布特点。 1 9 9 9 年，y o n gr u i 在i s h i k a w a 的算法基础上【2 2 1 ，将优化方法改进，推广到多种特征的情 况，并支持层次式的结构。 2 0 0 0 年，y el u 在r u i 提出的结构上【2 3 1 ，将关键字技术再次引入图像检索中，在关键字和 图像间建立语义关联网络，通过相关反馈技术学习关联的权值。这种算法可以将传统的关键字 4 南京航空航天大学硕士学位论文 技术与基于内容特征的图像检索技术较好地结合起来。 ( 2 ) 基于概率框架的方法 用概率框架描述检索问题，往往就是借鉴统计模式识别中的一些方法。1 9 9 8 年，在c o x 等人的工作中【2 4 1 ，首先定义了在给定用户目标图像的情况下用户在交互中的行为模型，然后通 过对当前用户行为的观察，根据贝叶斯规则来预测目标图像。同年，n a s t a r 通过用户的反馈信 息来估计相关图像的概率分布，在进行估计的同时，还需考虑减小检索出不相关图像的可能性。 他们假设各个特征分量独立，在沿着各个特征分量估计相关图像的分布时，采用一种经验性的 策略来考虑负例口5 1 。 2 0 0 0 年，v a s c o n c e l o s 和l i p p m a n 采用d c t 系数上的混合高斯模型作为特征表示【2 6 1 ，在图 像的局部特征上采用贝叶斯规则推断，进行相关反馈学习，他们的算法在不需要图像分割的情 况下支持对区域的查询。 2 0 0 2 年，w u 等人针对相关反馈中训练样本少的问剐2 7 1 ，提出了一种基于贝叶斯规则的相 关反馈概率框架，它在利用标记样本的同时考虑了全体样本( 标记和未标记的样本) 的分布特 点以提高检索性能。 ( 3 ) 基于机器学习的方法 近年来，相关反馈已经被归结为不同类型的监督学习问题，二类( 相关或者不相关) 或者 是( 1 + x ) 类的分类问题。( 1 + x ) 分类问题也可以称之为有偏学习问题，库中的类别的个数是不 知道的，而用户只对其中一类感兴趣。根据这些学习问题的特点，各种机器学习方法已被引入 到相关反馈算法的研究中。 1 9 9 8 年，w o o d 采用了区域特征1 2 8 1 ，要求用户判断返回图像中被选中的区域是否和目标区 域匹配，并将返回的数据标定为正例或反例，然后利用正例、反例数据对样本集进行聚类，最 后根据用户的标记把聚类结果标为相关或不相关，并且把最近邻为相关的区域中的图像作为检 索结果返回给用户。 2 0 0 0 年，m a e a r t h u r 采用决策树来求解两值分类问题【2 9 1 ，首先用一个决策树顺序地裁剪特 征空间，直到落入同一个划分节点的所有样本点属于同类，然后用得到的决策树把检索库中 所有的图像分类，再把落到相关划分节点的图像按它们到查询点的距离计算相似度，根据相似 度将检索结果排序返回。同年，t i e u 和v i o l a 在采用超过4 5 0 0 0 个高度选择性的特征( 在库中只 有少数图像在特征上取大的值) ，然后采用b o o s t i n g 技术在这个特征空间学习一个分类函数【3 0 1 。 同时在每个特征维上，假设正例和反例数据都服从高斯分布并训练一个分类器，最后利用 a d a b o o s t 方法通过这些弱分类器的加权和来构造一个强的分类器，并利用该强分类器进行相关 反馈。在他们的工作中，通过随机采样的方法解决反例样本少的问题。然而该采样方法可能将 相关的图像特征也当成反例。 5 矢量图形检索中的相关反馈技术研究 2 0 0 1 年，张磊等提出了用前向神经网络来表示正例对象的分布算法【3 i 】，前向神经网络的构 造采用了构造式学习方法，根据用户反馈的正例和反例样本，用多个超球来逼近正例对象在特 征空间中的分布。在下一次检索中对检索库中的特征向量不再是仅仅与查询对象比较相似性， 而是与所有这些相关类的特征向量比较相似性。 考虑到支持向量机( s u p p o av e c t o rm a c h i n e ，s v m ) 在有限样本下良好的推广能力，2 0 0 1 年，c h e n 等充分利用正例样本的同时舍弃反例样本【3 2 1 ，采用o n e 1 a s ss v m 来对样本集进行划 分。o n e 1 a s ss v m 在非线性变换得到的特征空间中用特征空间的超球面来包含多数的正例样 本。核技巧是一种很好的处理数据中非线性的方法，加上s v m 良好的泛化能力使得这种方法 具有更好的性能。在o n e c l a s ss v m 的分类算法中，反例数据被简单地舍弃了。 2 0 0 4 年，在c h u h o n gh o i 3 3 垮人的：r ：作中利用b i a s e d - s v m 构造分类器进行相关反馈。 b i a s e d - s v m 分类器利用同心的超球面对特征空间进行划分，内球面包含多数的正例样本，外球 面排斥多数的反例样本。该分类器充分利用止例样本的同时考虑反例样本的影响，具有较好的 性能。 2 0 0 8 年，j i 等人的工作中利用基下聚类的子空间s v m 集进行动态的相关反馈学习p 4 1 。首 先