（计算机应用技术专业论文）基于内容的图像检索中相关反馈技术的研究及系统实现.pdf

摘要 相关反馈技术是基于内容的图像检索领域中，关系到系统检索效率的一项 关键技术，本文主要研究工作放在基于s v m 的相关反馈技术和个性化检索单 元上，这里需要指出的是，本文的个性化检索单元是作为对相关反馈长期学习 机制的探讨而出现的，主要内容有： 1 研究了基于s v m 的相关反馈算法，针对反馈样本少的问题，通过累积 每轮反馈得到的正负样本来增加训练样本；但是，这种算法存在一定的缺陷， 为了进一步改进检索性能，提出了一种基于二次分类的s v m 分类器进行检索 的算法。并通过实验同基本的s v m 反馈算法进行了比较。实验证明，与s v m 方法相比，二次分类s v m 方法在用户相关反馈仅提供极少量反馈样本的情况 下，得到的检索结果是在查全率和查准率上都比s v m 方法有所提高。 2 针对目前大多数基于s v m 的相关反馈方法在当前检索任务完成后，不 再保留用户的反馈信息，只能进行当前检索任务内的学习的缺点，本文设计了 一个个性化检索单元用于收集分析用户的使用记录，进而推测出用户可能的检 索意图，以利于系统的下次检索。经过实验证明，加入了个性化检索单元后， 用户的反馈次数减少。 3 设计了一个实验用的基于内容的图像检索系统，该系统提供简单的图像 特征的提取及匹配，并设计了基于二次分类的s v m 反馈方式和基于个性化检 索单元的系统学习机制。 关键词：基于内容的图像检索，相关反馈，支持向量机，个性化检索 a bs t r a c t t h er e l e v a n c ef e e d b a c kt e c h n o l o g yi sak e yt e c h n o l o g yt h a ti sr e l a t e dt ot h e e f f i c i e n c y o ft h er e t r i e v a l s y s t e m s i nc o n t e n t b a s e di m a g er e t r i e v a l t h e p e r s o n a l i z a t i o nr e t r i e v a lu n i ta n dt h er e l e v a n c ef e e d b a c kt e c h n o l o g yb a s e do ns v m a r es t u d i e d a n dt h ep e r s o n a l i z a t i o nr e t r i e v a lu n i ti sp r o p o s e df o rt h el o n g t e r ml e a r n m e c h a n i s mo ft h er e l e v a n c ef e e d b a c kt e c h n o l o g y t h em a i nw o r kt h a th a sb e e nd o n e i ss h o w na sf o l l o w s 1 t h er 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 ns v mi ss t u d i e d a i m i n ga tt h e p r o b l e mo fl a c ko ff e e d b a c ks a m p l e s ，t h ep o s i t i v ea n dn e g a t i v es a m p l e sw h i c ha r e g o t t e na f t e re a c ht u r nf e e d b a c ka r ec u m u l a t e d ，s ot h en u m b e r so f t r a i n i n gs w a t c h e sa r e i n c r e a s i n g as e c o n d a r yc l a s s i f y i n ga l g o r i t h mb a s e do ns v m i sp r o p o s e dt oi m p r o v e t h es e a r c h i n gp e r f o r m a n c e a n dt h ec o m p a r eb e t w e e nt h es e c o n d a r yc l a s s i f y i n g a l g o r i t h ma n dt h et r a d i t i o n a ls v mf e e d b a c ka l g o r i t h mi so p e r a t e d t h ee x p e r i m e n t r e s u l t sp r o v et h a tt h es e c o n d a r yc l a s s i f y i n ga l g o r i t h m sr e c a l lr a t ea n dp r e c i s i o nr a t ei s b e t t e rt h a ns v m a l g o r i t h m ，e v e ni ft h ed e c i s i o n m a k i n gs a m p l e so f f e r e db y u s e r sa r e v e r yf e w 2 t h em o s te x i s t i n gs v mr e l e v a n c ef e e d b a c ka l g o r i t h m sd on o ts a v eo ru s et h e f e e d b a c ki n f o r m a t i o na f t e rt h es e a r c h i n gt a s ki sd o w n a i m i n ga tt h i ss h o r t c o m i n go f o n l yl e a r n i n gf o rt h ec u r r e n tt a s k ，ap e r s o n a l i z a t i o nr e t r i e v a lu n i ti sd e s i g n e dt oc o l l e c t a n da n a l y z eu s e r s u s er e c o r d sa n df e e d b a c ki n f o r m a t i o n ，s ot h ep o s s i b l es e a r c l l i n g i n t e n t i o nc a nb es p e c u l a t e d a n dt h i so f f e rg i v e sc o n v e n i e n c ef o rn e x ts e a r c h 。t h e e x p e r i m e n tr e s u l t ss h o wt h a tt h es y s t e mw i t hp e r s o n a l i z a t i o nr e t r i e v a lu n i tc a n r e d u c e t h ef e e d b a c kt i m e so b v i o u s l y 3 ac o n t e n t - b a s e di m a g er e t r i e v a ls y s t e mf o rl a bi sd e s i g n e d t h es y s t e mc a n r e t r i e v ea n dm a t c ho ft h ei m a g ec h a r a c t e r s t h es y s t e mp r o v i d e st h es v mf e e d b a c k a l g o r i t h mb a s e do ns e c o n d a r yc l a s s i f y i n ga n dt h el e a r nm e c h a n i s mb a s e do nt h e p e r s o n a l i z a t i o nr e t r i e v a lu n i t k e y w o r d sc o n t e n t - b a s e di m a g er e t r i e v a l ，r e l e v a n c ef e e d b a c k ，s v m ，p e r s o n a l i z a t i o n r e t r i e v a l 西北大学学位论文知识产权声明书 本人完全了解西北大学关于收集、保存、使用学位论文的规定。学校 有权保留并向国家有关部门或机构送交论文的复印件和电子版。本人允许 论文被查阅和借阅。本人授权西北大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存 和汇编本学位论文。同时授权中国科学技术信息研究所等机构将本学位论 文收录到中国学位论文全文数据库或其它相关数据库。 保密论文待解密后适用本声明。 学位论文作者签名：孓l ! 堡拯 指导教师签名： 旷尸年厂月丫汨彻歹年月砂日 西北大学学位论文独创性声明 本人声明：所呈交的学位论文是本人在导师指导下进行的研究工作及 取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，本 论文不包含其他人已经发表或撰写过的研究成果，也不包含为获得西北大 学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对 本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：酬、牮桷 沙7 年d 月砂y 日 西北大学硕士学位论文 1 1 研究的背景与意义 第一章绪论 图像作为自然信息的载体是一种非常重要的信息承载方式，在人们生活的各个领 域，每天都会产生大量的图像信息，这些图像的出现是无序且分散的。随之而来的问题 就是需要在海量的分散图像数据中快速而准确的找到人们需要的数据，这就需要一种有 效的图像检索技术。 大规模图像检索技术的历史可追溯到2 0 世纪7 0 年代，当时出现了基于文本的图像 检索( t b i r ) 【l 】，其原理是将图像作为一个对象存储在数据库中，根据图像语义，由 人工对这些对象作关键字标注，查询操作则是对这些关键字的精确或模糊匹配，实质就 是把图像检索转换为与图像相对应的文本检索。但是由于图像本身固有的特点，人工标 注文本信息的工作量巨大，而且人工标注的文本描述信息具有主观性，难以全面的涵盖 图像的意义。 为了突破基于文本对图像检索的局限性，从2 0 世纪9 0 年代起，出现了对图像基于 内容的检索( c b i r ) 【2 1 ，即查询时是针对图像的内容本身而非图像的文本标注，它需要 从图像中提取一些特征，例如颜色、纹理、形状或空间位置等，根据这些特征信息建立 索引，利用图像特征向量间的距离来衡量图像的相似程度，在一定的响应时间内返回查 询结果。它具有以下几个特点：1 、从图像中提取特征信息( 包括颜色、形状、纹理等) 来建立索引；2 、采用相似性度量对图像库中的图像进行匹配。3 、特征提取和索引建立 可由计算机自动实现，避免了人工描述的主观性，这也是基于内容方法最大的优势所在。 1 2 基于内容的图像检索系统的发展现状 由于基于内容的图像检索技术被认为是能够有效的解决在海量数据中快速而准确 的检索出所需内容的技术，所以，近些年来很多的学术组织对基于内容的图像检索技术 领域予以了高度的关注，而i e e e 等业内享有崇高声誉的权威学术组织更是针对基于内 容的图像检索技术召开了一系列专门的会议，得益于此，这一技术也得到了长足的发展。 由于传统的图像检索技术的实质是基于文本的检索，而文本的来源是人们手工的注 释，这样，图像的注释就不可避免的带有注释人员的主观判断色彩，而且工作成本高昂， 检索方式单一，只能进行基于文本的检索。基于内容的图像检索就不会存在这些问题， 第一章绪论 首先它的判断取值取的是图像客观存在的属性，如颜色、纹理和形状等，图像的这些属 性是不会随着人们的意志而变化的；其次，基于内容的图像检索对图像内容的提取是全 自动化的，不需要人工的干预，因此对图像的收集、特征的采集和匹配都可以由机器自 动完成，极大地减少了人工工作量和工作成本；再者，基于内容的图像检索可以对图像 基于多种特征进行检索，这就解决了单一特征对图像语义的表达能力欠缺的问题。总的 来说，对基于内容的图像检索技术的研究取得了巨大的成就，但是仍然不足以解决表述 图像语义的问题。 基于内容的图像检索发展至今，一些著名的图像检索系统也相继问世。依照各检索 系统的使用范围，本文将它们分作商用系统、网络应用系统和科学研究用系统三大类。 1 商用系统 该类系统典型的代表是m m 公司的q b i c ( q u e r yb yi m a g ec o n t e n t ，网址： w w w q b i c a l m a d e n i b m c o r n ) 【3 】系统和v i r a g e 公司的v i r a g e 系统【4 1 。 i b m 公司的q b i c 是第一个商业化的基于内容的图像检索系统。该系统支持以图像 和用户构造的草图为查询实例，并且支持选择查询的特征，可以基于颜色或纹理或二者 的组合的特征查询，同时也支持最基本的文本查询方式。该系统中使用的颜色特征是颜 色直方图，它采用的纹理表示是粗糙度、对比度和方向的结合( t a m u r a 5 】提出的一种纹 理表示的改进) ；它的形状特征是主轴偏向、面积、偏心度、一组代数矩不变量和圆形 度。q b i c 系统一个引人注目的特点是它使用了高维索引技术，同时有效的控制了数据 量，减少维数并采用r 树为多维索引结构。q b i c 系统是m 公司d b 2 数字图书馆的 图像检索系统，同时，它也是m 公司的一个独立的软件产品。 v i r a g e ( 网址：w w w v i r a g e t o m ) 系统是v i r a g e 公司的v i r 图像工程系统，它也是 商用的基于内容的图像检索系统中比较成功的一个。它的特点是支持颜色、颜色布局、 纹理和边缘四种原子检索的任意组合，而且用户可以根据自己的实际需求调整组合中原 子检索的权重，它的技术核心点是v i r a g e 引擎和在图像对象层上的操作。v i r a g e 引擎具 有图像分析、对比和管理的功能，它将查询引擎作为一个插件，应用到特定领域，同时 也具有通用性。 2 网络应用系统 网络应用类系统中具有代表性的系统是美国波士顿大学的i m a g e r o v e r 系统和哥伦 比亚大学开发的w e b s e e k 6 】系统，它们共同的特点是按主题分类，适合关键词搜索， 其搜索方式灵活。i m a g e r o v e r 系统搜索结果显示的是简图和文本，相比之下w e b s e e k 2 两北人学硕士学位论文 系统的检索结果没有文字说明。 i m a g e r o v e r 系统的特征提取是纹理、颜色和方向直方图，使用潜在语义索引技术 获取用户所需信息。 w e b s e e k 系统是哥伦比亚大学开发的v i s u a l s e e k 7 1 实验系统的面向万维网的检索 工具，它提取的特征是颜色、形状和结构，自动化处理程度高，支持文本检索，可用任 意可视属性检索。 3 科学研究用系统 科学研究类的图像检索系统较多，比较著名的有m i t 的p h o t o b o o k 8 1 系统、哥伦比 亚大学v i s u a l s e e k 系统、伊利诺斯大学的m a r s 9 1 系统等等。这些系统在不断的进行 新理论的研究应用的尝试。 p h o t o b o o k 系统包括了三个子系统，分别用于形状、纹理和面部特征的提取和匹配， 已经应用在了美国的警察系统中。f o u r e y e s 是p h o t o b o o k 的改进版本，它记录用户的反 馈结果，并根据用户记录来挖掘用户的使用特点，突出了系统的交互和学习的能力。 v i s u a l s e e k 系统是最早的用于图像检索演示的软件，它以颜色、形状和空间位置 为特征进行提取和匹配，它是一种面向网络的检索系统，同时也支持基于文本的图像检 - - 索。 m a r s 系统是最早正式提出相关反馈的图像检索系统，其特点是将各子特征组合成 有意义的整体特征，并且可以进行动态的调整以适应不同的应用需求，它忽略了单一特 征的最佳匹配，寻求整体的组合以求接近图像语义检索的层次。它的研究特点是数据库 管理系统和信息检索的结合，以优化的索引结构来提高检索算法的效率，以人机交互的 方式来实现系统的学习和自我优化能力。m a r s 系统形式化的提出了相关反馈结构，并 将相关反馈技术集成到检索的不同层次上，包括矢量优化、自动匹配工具选择和自动特 征适应。 其他还有一些比较具有代表性的系统，例如，e x c a l i b u r 技术公司开发的将神经网 络应用于图像检索中的r e t r i e v a lw a r e 1 0 1 系统；u s c b 大学亚历山大数字图书馆项目组 开发的n e t r a 1 1 】系统，它的主要特点是基于g a b o r 过滤器的纹理分析、基于神经网络的 图像分类和基于边缘的区域分块；还有斯坦福大学研制的s i m p l i c i t 1 2 1 系统和奥尔良 大学开发的c l u e 系统，他们的特点是获取高层语义信息，此外我国的清华大学也有类 似的研究系统。 第一章绪论 1 3 问题的提出及本论文的研究内容 基于内容的图像检索技术克服了基于人工标注的文本检索的主观性，大大减少了人 工工作量，提高了检索的准确度，但同时它也存在许多不足，主要表现在以下两个方面： 1 反馈效率不够理想。相关反馈技术发展至今，出现了很多相关反馈算法，这些 算法各有优劣，但总的来说，反馈效果并不理想，用户依然将大量的时间消耗在对查询 结果的反馈上。 2 缺乏长期学习机制。目前的多数相关反馈方案一个共同的缺点是，在当前检索 任务完成后，这就意味着，系统的学习机制是即时的，当检索任务完成后，系统的学习 也中止了，并且是将学习的成果丢弃了。 本文主要研究基于s v m 的相关反馈方法，在文中提出了一种二次分类的s v m 反 馈方法，并通过实验同基本的s v m 反馈算法进行了比较。另外，作为对目前大多数反 馈方法缺乏长期学习机制的一种补充，本文提出使用个性化检索单元收集并分析用户的 反馈信息，加以利用来增强未来的检索效果。最后，本文实现了一个实验用图像检索系 统，支持对颜色、纹理和形状的任意组合进行检索，加入了基于二次分类s v m 反馈模 块和个性化检索单元。 1 4 论文的组织结构 本文对各章节的安排是：第一章绪论，介绍有关基于内容的图像检索的研究背景和 研究现状，并对论文的组织结构做出安排；第二章，综述基于内容的图像检索的相关技 术；第三章，论述支持向量机理论并提出二次分类的s v m 反馈算法；第四章，设计了 一个个性化检索单元作为对相关反馈长期学习机制的探讨；第五章，系统的设计与实现； 第六章，实验及结果分析；最后是总结与展望。 4 西北大学硕士学位论文 第二章基于内容的图像检索的相关技术概述 基于内容的图像检索系统的实现需要使用到很多与之相关的技术，这些技术包括图 像特征的提取、特征相似度度量、特征索引技术和相关反馈技术等。历年来，大量的学 者对这些技术做了许多成熟的研究，本章将列举实现系统所需要使用到的成熟的研究成 果。 2 1 图像的特征提取技术 对图像特征的提取和分析是基于内容的图像检索中的一项关键技术。事实上，就目 前针对图像的检索方式而言，图像的特征应包含文本特征、视觉特征和高层语义特征三 大类，文本特征与基于内容的图像检索关系不大，我们主要关注图像的视觉特征。所谓 视觉特征即通过对图像的颜色、纹理和形状等本身固有的可视化的属性进行一系列的抽 象，得到一组相关的数字描述，我们将这组与图像可视化内容相关的数字描述称之为图 像的视觉特征。高层语义特征比较复杂，涉及到图像的抽象属性，需要结合心理学和认 知科学等多门科学对图像的场景含义和目标进行高层推理。目前研究最多，成果最显著 是对图像视觉特征方面的研究。 1 颜色特征的提取 颜色是图像内容组成的基本要素，是人识别图像的主要感知特征之一，相对于其它 特征，颜色特征非常稳定，对于图像的平移、尺度和旋转变化不敏感，具有很强的鲁棒 性，而且颜色特征计算简单，因此基于颜色的查询是基于内容的图像检索中应用最广泛 的方法。目前常用的颜色特征提取技术有颜色直方图、颜色矩、颜色集、颜色聚合向量 和颜色相关图等。 1 ) 颜色直方图1 3 】。颜色直方图法认为，各种颜色在图像中的位置是无关紧要的， 重要的是每种颜色在图像中所占的比例，如果两幅图像具有比较相近的颜色构成比例， 那么两幅图像相似的可能性就很大。用数学的方法描述就是，假设图像所处的颜色空间 被划分为x 种不同的颜色，那么颜色直方图就可以表示为： 。其中， 1 t i i 所代表的意思是图像中所具有的第i 种颜色的像素数。 很显然，无论一幅图像如何旋转、移动、放大或者缩小，对图像所具有的像素数是 没有影响的，而且也不会影响像素的种类。所以颜色直方图对图像的上述变化是不敏感 的，而且它表现的是图像的全局特点。颜色直方图比较适合用于只需表达图像颜色特点 5 第二章基于内容的图像检索的相关技术 的图像，对图像中具体的某一事物却欠缺表达力，因此，使用颜色直方图法描述图像， 往往会导致检索结果与用户期望的不一致。 2 ) 颜色矩1 4 1 。颜色矩是一种简单而有效的颜色度量方法，s t r i c k e r 和o r e n g o 认为 如果使用颜色矩来表达图像，那么只需要9 个分量( 3 个颜色分量，每个分量上3 个低 阶矩) 就足以表达一幅图像大部分的颜色特征，因为图像的颜色信息主要集中在低阶矩 上。颜色的一、二、三阶矩的数学表达式如( 2 1 ) 所示。 以2 专善弓 q 2 ( 专善( 鳓一肼) 2 ) i ( 2 1 ) 邑2 ( 专丢( 岛一一) 3 ) i 式中p “是第j 个像素的第i 个颜色分量。其中，式( 2 1 ) 中的第一个式子代颜色分 量的平均强度，第二个式子表示它的方差，第三个式子是偏斜度的表述。在实际使用 中，颜色矩可以起到过滤并缩小范围的作用，而且，如果能够把颜色矩和其他图像特征 一起使用，就可以有效的避免( 2 1 ) 式分辨能力差的缺陷。 3 ) 颜色集。颜色集是对颜色直方图的一种近似表示，如果要使用颜色集，那么首 先需要对颜色空间进行转换，一般是从r g b 空间转换到h s v 空间。在转换颜色空间的 同时还需要把颜色空间量化，再将图像按照一定的规则划分成若干个部分，每个部分建 立一个索引，索引一般是该图像所处的颜色空间中的某个颜色分量，这样处理后，图像 就可以由颜色索引集表示了。现在的图像库规模都很大，如果没有合适的查找方法对图 像库进行操作会极大地影响检索的速度，由于颜色索引集是二进制的，所以可以构造成 二分查找树，对提高图像库的查找速度很有帮助。 4 ) 颜色聚合向量。颜色聚和向量的出现是建立在颜色直方图存在不能表达色彩的 空间位置的基础上的，对颜色直方图作一些变化：把每个b i n 的像素分成两部分，一部 分是聚合像素，另一部分是非聚合像素，划分的标准是像素所占的连续区域的面积的大 小，若是大于预先设定阈值，则将其判定为聚合向量，若小于预先设定的阈值，就判定 为非聚合向量。 这样，图像的聚合向量就可以表示为( ( ，屈) ，( ，属) ，( ，风) ) ，其中qt 和1 3 t ， 分别代表第i 个b i n 中聚合像素和非聚合像素的数量，n 为颜色种类的个数。而 6 西北大学硕上学位论文 ( ( + 届) ，( + 屈) ，( 十风) ) 就是该图像的颜色直方图。上文中所谓像素所占连续 区域，往往对应于图像中具体事物的位置，所以聚合向量对图像中具体的事物表达能力 比较强，在检索时使用聚合向量就能够比较图像中事物的空间位置，这对使用颜色直方 图不能对比物体空间关系是一个提高。 5 ) 颜色相关图。相对于颜色直方图和颜色聚合向量来说，颜色相关图对图像中的 物体的空间关系具有更强的表达能力。如式( 2 2 ) 所示，假设i 表示整张图像的全部像 素，l ( f ) 则表示颜色为c ( f ) 的所有像素。 哆l 聃p m r 孵， p z 慨一p zi = k ( 2 2 ) 式中f ， 1 ，2 ，) ，k 1 ，2 ，d ，i 岛一仍i 代表两个像素点之间的距离，颜色相关 图可以看成是一张表，表的索引是颜色对( f ，j ) ，( f ，) 的每个分量都代表一种概率，该 概率表述的是颜色c ( f ) 到c ( _ ，) 的像素的距离小于某值的概率。 2 纹理特征的提取 一般可以认为纹理是某种局部图案的序列性，纹理区域内任何地方都有大致相同的 结构尺寸，如果一个局部特性周期性重复出现，通常把这种图像称为确定型纹理图像， 反之则成为随机型纹理图像。 一般常用的纹理特征有t a m u r a 纹理特征、共生矩阵和小波变换等形式。 1 ) t a m u r a 纹理特征 在t a m u r a 等【1 5 1 提出了纹理特征的表达法中，有粗糙度、对比度、方向度、线像度、 规整度、粗略度六个纹理特征分量【1 3 _ 7 1 ，他们都是基于人类对纹理的视觉感知的心理 学的研究的。 粗糙度，表征图像的粗糙程度，在对粗糙度进行计算时首先计算图像中活动窗口中 像素的平均强度；然后，对于每个像素，分别计算它在水平方向和垂直方向上互不重叠 的窗口之间的平均强度差；最后，通过计算整幅图像中最佳尺寸的平均值来得到粗糙度。 对比度，通过对像素强度分布情况的统计而得到。 纹理基元的方向性和它排序的方向性是纹理区域的两个基本属性，方向性是纹理区 域的全局特征。计算图像的方向度需要两个步骤，第一步是计算出给定纹理区域的每个 像素的梯度向量，第二步是根据计算出来的梯度向量构建一个直方图h d 来表达臼值，9 7 第一二章基于内容的图像检索的相关技术 表示的是梯度向量的方向。当直方图构建出来以后，对口的值域离散化，统计每个b i n 对应的i g l 大于给定阈值的像素数量，i g i 表示的是梯度向量的模。该直方图对图像 方向性的反映具体表现为，当选定的纹理区域有明显的方向性时，直方图会出现峰值， 否则就会表现的比较平坦。计算直方图中峰值的尖锐程度就可以获得整个图像的方向 性。 线像度，由局部方向共生矩阵产生，表征了图像中纹理基元的一种形状特性。 规整度也是图像的一种全局特征，它表现的是图像的整体有序性。纹理基于自身的 变化会影响整个纹理的规整性，计算的方法是= l 一，( + + + ) ，其中， r 为归一化因子，分别为如，民的均方差。 粗略度的数计算方法是= + 。 2 ) 共生矩阵 h a r a l i c k 等在上世纪7 0 年代提出用灰度共生矩阵表示纹理。一幅图像有关方向、 变化幅度和相邻间隔等信息都可以通过该图像的共生矩阵反映出来，它是分析图象的局 部模式和它们排列规则的基础。 共生矩阵的建立分为两步，第一步是建立矩阵，矩阵中包含的内容是像素间的距离 和方向性，第二步是从这个矩阵提取有意义的统计量。常用的统计量有角二阶矩、熵、 同质区、非相似性等。为了能更清晰的表述图像，除了这些常用统计量，还需要更进一 步提取图像纹理的一系列特征，比如角二阶矩、熵、惯性、局部均匀性、相关性、最大 概率、聚类渐变性、聚类突变性和灰度均方差等。最常用的是前五个特征，所以可以根 据不同的取值情况计算得到多个五维特征向量，再经过处理得到最终的检索向量。 上文所述的几个分量所代表的物理意义和取值范围都不相同，为了使各个分量在计 算相似距离时具有相同的权重，必须对他们进行内部归一化。 3 ) 小波变换 小波变换是一种多分辨率分析方法，用小波变换的方法提取纹理图像特征。可分为 两种，一种是基于金字塔小波变换，一般来说，这种变换方法的计算复杂度比第二种低， 第二种就是树状小波变换，在纹理图像的信息包含在h l 和l h 频段中的情况，该方法 比第一种变化方法更有效。 对小波变换后得到的小波系数提取纹理特征，可以有效的对纹理图像进行描述，在 实际应用中，s m i t h 等人提出了一系列基于小波变换的纹理检索方法，限于篇幅不在这 西北大学硕十学位论文 里一一陈述了。 3 形状特征的提取 在现实情况中，人们在关注图像的颜色和纹理的同时，也很关注图像的形状特征， 在某些情景下，形状能够比颜色和纹理传达给人们更多的信息，因此，在这些情境下， 人们对形状特征的关注程度要远高于颜色和纹理。 图像颜色和纹理特征的表达大多是基于统计学理论进行的，对颜色和纹理特征描述 时往往只需要针对特征的全局分布状况做出描述就足以表达整幅图像了，而图像的形状 特征则不同，由于这个特征是要通过对图像中的物体的轮廓做出描述来表达图像内容 的，所以要使用图像的形状特征就必须能够对图像中物体和区域做出划分。目前的现实 情况是基于形状特征的图像检索只能应用在一些特殊的领域中，比如前文提到的美国脸 谱识别系统，而尚不能够通用于各个领域，原因在于目前的技术还达不到对图像进行准 确而鲁棒的分割，并且，合适的形状特征必须满足对变换、旋转和缩放无关的条件，而 这些条件的满足有一定的难度，所以形状相似度的计算也有一定的困难。 一般来说，形状特征有两种表示方法，一种是轮廓法，只用到了物体的边界，另一 种是区域法，关系到整个形状区域。 基于轮廓的形状描述方法主要是利用图像的边缘信息对图像形状进行刻画。常用的 方法是傅立叶描述符【1 6 】、边缘直方图、弗里曼链码。傅立叶描述符的基本思想是用物体 边界的傅立叶变换作为其形状描述。f r e e m a n h 提出链码的概念：用一系列具有特定方 向、单位长度的线段来描述物体。链码的优点在于降低了问题的复杂度，它把二维图像 的存储和处理转换为了一维链的问题。 基于区域的形状描述方法主要是利用区域内的灰度分布信息，最常用的方法是几何 不变矩和z e m i k e 矩。最著名的不变矩法是h u 基于形状无关矩提出了一系列分别具有 变换、旋转和缩放无关性的7 个矩。h u 1 7 】根据正交多项式的原理提出用正交矩来恢复 图像，并引进了z e m i k e 矩，其思想和傅立叶变换思想类似。z e m i k e 矩无需知道边界信 息，所以更适合于描述复杂形状。 2 2 相似性度量技术 在上文中提到的图像特征的提取大多可以表示为向量形式，所以图像特征的相似性 度量方法也都是基于向量空间模型的，具体的说就是把图像特征看作向量空间中的两个 点，以两个点之间的距离来衡量两幅图像相似度的大小。计算方法主要有以下几种： 9 第二章基于内容的图像检索的相关技术 1 欧拉距离 图像的两个特征向量之间的距离能否用厶距离或者与距离( 也称为欧拉距离) 来度 量，取决于图像特征的各分量的权重比和正交相关性，如特征，如果各分量的重要权重 相同又是正交无关的，那么两个特征向量之间的距离就可以用厶距离或者易距离( 也称 为欧拉距离) 来度量。其中厶距离如式( 2 3 ) 所示。 q = y + 1 4 - 一e i i = l ( 2 3 ) 式中，n 是特征向量的维数。类似地，厶距离如式( 2 4 ) 所示。 皿：n ( 4 一剐2 ( 2 4 ) 2 直方图相交 直方图相交法的思想是假设i 和q 是两个含有1 1 个b i n 的颜色直方图，则它们之间 的相交距离如式( 2 5 ) 所示。 e m i n ( i j ，g ) ( 2 5 ) 直方图相交是指两个直方图在每个b i n 中共有的象素数量。该值通过除以其中一个 直方图中所有象素的数量来实现标准化。标准化公式如式( 2 6 ) 所示。 s ( 厶q ) 2 荟m i n ( 1 j ，g 否g 2 6 ) 3 二次式距离 二次式距离考虑了不同颜色之间存在的相似度。二次式距离计算公式如式( 2 7 ) 所示。 d = ( 9 一，) + ( q - 1 ) c 2 7 ) 这种方法引入了颜色相似矩阵a ，a = e a y ，勺表示直方图中下标为i 和j 的两个颜 色b i n 之间的相似度。 4 马氏距离 马氏距离适合用来计算特征向量的各个分量具有相关性或者具有不同的权重的情 况，计算公式如式( 2 8 ) 所示。 1 0 西北大学硕上学位论文 d 幺 4 ，= ( 么一b ) c 。1 ( a - b ) ( 2 8 ) 其中c 是特征向量的协方差矩阵。若特征向量的各分量之间没有相关性，马氏距 离可以表示如公式( 2 9 ) 。 ：主掣 ( 2 9 ) 5 非几何的相似度度量方法 t v e r s k y 提出了特征对比模型【1 8 】。该模型把每个实体用一个特征集来表示。设实体 m 和n 对应的特征为m 和n ，两个特征问满足独立性、单调性和匹配性假设。t v e r s k y 提出对比模型定理：对于满足独立性、单调性和匹配性假设的度量函数，存在一个相似 度度量函数s 和一个非负函数f ，以及两个常量口，。对于实体a 、b 、c 、d 和它们的特 征集a 、b 、c 、d ，它们之间的关系如公式( 2 1 0 ) 所示： 趴s ( a 口暑b 三篙2 孓裴糊二影。b 叫 ( 2 舯， ，) = 厂( 4 r 、b ) 一口厂( 彳一曰) 一厂( b 一彳) 2 3 索引技术 图像数据库的数据量非常庞大，所以其特征数据库规模也是巨大的，在传统的线性 扫描方式下，检索的效率非常低下，欠缺有效的数据结构来组织特征向量。针对这个问 题，人们提出了多维索引机制，多维索引机制存在着一个“维度灾难 的问题，实验证 明【l9 1 ，当特征向量的维数大于2 0 时，多维索引机制效率急剧下降，甚至不如线性扫描 机制，研究者提出了一些的解决方案，这些方案可以分成五类：多维索引方法、降维的 方法、近似最近邻方法、多重填充曲线方法和基于过滤的方法。限于文章篇幅，本文不 在这里一一论述。 2 4 相关反馈技术 目前的相关反馈方法主要可以分为四种类型：查询点移动法，特征权重调整法、基 于传统的统计学习理论的方法和基于机器学习理论的方法。 1 查询点移动 查询点移动法是最早应用在基于内容的图像检索中的相关反馈方法，它最初是文本 检索中的相关反馈思想，r u i 将这种思想引入到了图像检索中。查询点移动法的思想是 第二章基于内容的图像检索的相关技术 把图像特征转换为向量模型中权向量的形式，利用r o c c h i o 公式修改查询向量，使新的 查询点逐渐向相关图像靠近，而远离不相关的图像。 2 特征权重调整法 特征权重调整法的主要思想是加大用户看重的特征分量在相似度匹配中的权重比 例，减小用户认为不重要的特征分量的权重比例。具体做法是在正反馈样本集上，对每 一维的特征进行统计，如果某一维的方差较小，就认为用户更加看重这一特征分量，然 后相应的改变相似性度量准则。 r u i 在m a r s 系统中给出了一个多层图像表示和动态调整权相结合的方法，这个方 法包括多层图像表示和动态调整权两个方面，假定一个图像有多个特征，每个特征有多 种表示，那么每种特征表示就是一个高维向量。如果在某个特征分量上，所有正例有相 似的取值，那么就说明该分量对用户来说是重要的，反之则该分量是不重要的。查询时 特征的比较从低层到高层，进行加权求和，把所有的正例样本在各特征分量上取值的标 准差的倒数作为权值。 还有一些方法是做一些线性变化，使得正例在变换后的空间中更聚拢，反例更分散。 3 基于传统的统计学习理论的方法 这一类型的相关反馈以概率学习理论为基础，估计每一幅图像与查询图像的相关概 率，认为高概率的图像就是检索的相关图像。这一类型的反馈算法的代表是基于贝叶斯 理论系列的反馈算法。 4 基于机器学习理论的方法 这一类型的反馈算法主要有支持向量机系列的算法和b o o s t i n g 算法等，其共同点是 通过对样本集的学习，得出查询例图与被检索图像特征之间对应的模型，根据学习的模 型指导新一轮的检索。 支持向量机在小样本下具有良好的推广能力，在非线性及高维模式识别问题中比较 具有优势。本文在下面的章节将对基于s v m 的反馈技术在深入的探讨。 2 5 图像检索系统性能评价标准 基于内容的图像检索算法很多，每种算法的侧重点不同，很难判断孰优孰劣。为了 能够在相同条件下找出最佳算法，人们一般采用查全率( p r e c i s i o n ) 、查准率( r e c a l l ) 和系 统响应时间三个指标作为衡量一个检索算法性能的标准，其中系统响应时间这个标准使 用的比较少，用的最多也最为人们普遍接受是查全率和查准率两个指标，如式( 2 1 1 ) 1 2 西北大学硕：学位论文 酸耘鬟一川似 ，1 ， 查准率= 笺糍器川。 2 6 小结 本章根据图像检索系统实现的需要，列举了与之相关的技术，包括图像特征的提取、 特征相似度度量、索引技术、相关反馈技术以及图像检索系统性能评价标准等。由于前 人在这些技术上做了大量成熟的研究，所以在系统实现时可以直接借鉴这些成果。 1 3 第三章基于s v m 的相关反馈技术 第三章基于二次分类的s v m 反馈技术 本章在基本的s v m 算法基础上提出了二次分类的s v m 算法，该算法是系统实现 中反馈模块的算法。二次分类s v m 算法通过对经用户初次反馈标记的训练集的特征分 离再合并的方法，产生比不经过二次分类更大的训练样本集，用于对反馈系统的训练。 s v m 系列的算法基础是支持向量机理论，本章首先列举系统实现中用到的支持向量机 的相关理论，然后提出二次分类的s v m 算法。 3 1 支持向量机理论 支持向量机是v l a d i m i rn v a p n i k 等人提出的一种基于统计学习理论的机器学习算 法呦m ，该理论的思想是将样本看做正负两类，把图像检索看作一个实时分类问题。 针对训练样本小的问题，支持向量机通过累积学习的方式增加训练样本。同时，支持向 量机也在非线性及高维模式识别问题中表现出许多特有的优势。 3 1 1 统计学习理论 传统的学习理论方法中使用经验风险最小化( e r m ) 准则，即用样本定义经验风险 ( 川2 吉荟l ( y t , f ( x t , 计) 来估计期望风险冗( w ) = 八只( 五w ) ) d f ( x , y ) ，并设计学习 算法使经验风险最小化。上面两式中，u ( x ，叻) 称作预测函数集，w q 是函数的广义 参数。所谓统计学习就是根据一些独立的观测样本，在一组预测函数 厂( 工，叻) 集中找到 一个最优解使得期望风险尺( 川2j ( 乃厂( z ，们) 卵( 石，y 取到极小值。 实际上，e r m 准则能否替代期望风险最小化只是直观上合理的做法，在有限样本下， 该准则是否能使真实风险也较小是没有经过理论论证的。文献乜羽指出，有限样本情况下， 经验风险最小与期望风险最小并不等价，并且学习机器的复杂性与所研究的系统和有限 数目的样本都有关。 统计学习理论能够在小样本情况下建立有效的学习和推广方法，与此相关的一个核 心概念是v c 维乜，v c 维越大则学习机器越复杂( 容量越大) 。统计学习理论系统地研 究了推广性的界，所谓推广性的界就是经验风险和实际风险之间在各种类型的函数集的 关系。由此得出，学习机器的实际风险事实上是由经验风险和置信范围两部分组成的， 1 4 西北人学硕士学位论文 其中，经验风险是一种训练的误差，是系统固定存在的风险；置信范围和学习机器的 v c 维及训练样本数有关，是可以人为控制的。上述关系式可以简单地表示为式( 3 。1 ) ： 尺( 川( w ) + ( 办刀) ( 3 1 ) 其中，r ( w ) 、( w ) 、h 、n 分别表示实际风险、经验风险、v c 维数、样本数。 从式( 3 1 ) 中可以得到一个结论，训练样本有限的情况下，v c 维越高，置信范围 越大，间接导致r ( w ) 和( w ) 之间的差别越大。所以有时机器会出现过学习现象。s r m 准则( 结构风险最小化) 的基本思想是为了得到较小的实际风险，统计学习理论把函数 集分划为一个函数子集序列，在每个函数子集中寻找最小的经验风险，然后在置信范围 和经验风险之间取一个合适的平衡点，以求达到最小的实际风险。其中各个子集按照 v c 维的大小排列。 支持向量机方法实际上是结构风险最小化的一种具体实现。 3 1 2 v c 理论 统计学习理论系统地研究了二个问题，一个是经验风险最小化原则成立的条件；另 一个是有限样本下经验风险与期望风险的关系。因此它被认为是目前针对小样本统计估 计和预测学习的最佳理论。v c 维是其中最重要的部分。 v c 维数是期望风险函数的近似函数组 厂( x ，w ) ) 的一个属性。下面举例说明什么是 v c 维数。把一个含有x 个元素集合一分为二的方法共有2 1 种，如果对于每一种方法， 厂( 五叻 都能正确地标记分类，那么这个函数组能够j 下确标记的集合的元素个数就成为 该函数的v c 维数。 例如，在二维空间中，取函数组为如式( 3 2 ) ( x ，们) = s g n ( m o x + m o ) ( 3 2 ) 式中的参数w = m ，m 。) 。当x = 2 时有4 种分法，当x = 3 时有8 种分法，均可用式( 3 2 ) 中的有向直线分完。但当x = 4 时，如图3 1 所示的这种情况，按照式( 3 2 ) 将其划分， 无论采用什么样的办法都不能按照上式的要求将其正确划分，因此，该函数组( 3 2 ) 能正确标记的集合最