（计算机软件与理论专业论文）cbir中的检索算法研究.pdf

摘要中国科学技术大学硕士学位论文 摘要 随着数字化技术的发展和多媒体数据的普及，基于内容的图像检索( c o n t e n t b a s e d i m a g er e t r i e v a l ，c b m ) 的理论和方法成为目前信息领域的研究重点。 相关反馈技术已经被证实是一项强大的技术应用于可交互式的基于内容图 像检索，尽管已经有不少先进的学习技术提出来构建相关反馈算法，但目前的技 术仍有许多缺陷和不足，其中包括以下几个方面：( 1 ) 协方差矩阵的奇异问题； ( 2 ) 小样本问题：( 3 ) 对反例样本的学习问题。针对这些问题，本论文从不同的角 度提出有效的算法来改善这些问题。 首先，针对协方差矩阵的奇异问题，我们提出了一种新的相关反馈算法。该 方法根据正例图像的散布矩阵来计算该类图像分布密集的投影空间，把投影空间 中与查询向量距离较近的图像作为相似图像反馈给用户。在c o r d 图像库中的实 验结果表明该算法对多例图像查询有较好的检索效果。 其次，针对小样本问题，经典的相关反馈算法由于正例样本的稀缺导致无法 准确估计权值矩阵，因此提出两种不同向上采样方法。大量实验的结果说明：通 过对正例样本的向上采样，可以有效地改善检索的性能。 此外，提出一种新的结合反例样本的检索算法，并认为检索过程应分为两个 阶段：第一个阶段是“求同”阶段，从图像库中选出那些与正例样本的特征相似 的图像，无论这些特征是否出现在反例样本中；第二个阶段是“求异”阶段，主 要是根据正例样本和反例样本不同的分布方式增强那些使正例样本和反例样本 可区分开的特征，进一步优化第一阶段得到的检索结果。在c o r e l 图像库上的实 验结果验证了该算法的有效性。 关键词；基于内容的图像检索，相关反馈，奇异闯题，小样本阔题，正例样本， 反例样本，特征选择 a b s t r a c t 中国科学技术大学硕士学位论文 a b s t r a c t a l o n gw i t ht h ed e v e l o p m e n to fd i g i t a lt e c h n o l o g ya n dp o p u l a r i t yo fm u l t i m e d i a ， t h e o r i e sa n dt e c h n i q u e so fc 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 m ) h a v eb e e nak e y p o i n ti nt h ec u r r e n ti n f o r m a t i o na r e a r e l e v a n c ef e e d b a c kh a sb e e ns h o w na sa p o w e r f u lt e c h n i q u ef o ri n t e r a c t i v ec o n t e n t b a s e d i m a g e r e t r i e v a l a l t h o u g h an u m b e ro fs t a t e - o f - t h e a r tt e c h n i q u e sh a v eb e e n d e v o t e dt or e l e v a n c ef e e d b a c k ，e x i a i n g t e c h n i q u e ss t i l lh a v em a n y d r a w b a c k sa n d l i m i t a t i o n s ，i n c l u d i n g ：( 1 ) s i n g u l a r i t yi s s u ei ns a m p l ec o v a r i a n c em a t r i x ；( 2 ) s m a l l s a m p l ei s s u e ；( 3 ) i s s u eo n h o wt ol e a r nf r o m n e g a t i v ee x a m p l e s t h i sd i s s e r t a t i o n i n v e s t i g a t e st h e a b o v ei s s u e sa n d p r o p o s e se f f e c t i v ea l g o r i t h m s t oi m p r o v et h e m t h r o u g h d i f f e r e n tp e r s p e c t i v e s w ef i r s tp r e s e n tan o v e la l g o r i t h mt oa t t a c kt h e s i n g u l a r i t yi s s u ei ns a m p l e c o v a r i a n c e m a t r i xb y a n a l y z i n gt h es c a t t e rm a t r i xo f p o s i t i v ei m a g e s ，t h ep r o j e c t e ds p a c e w h e r e i m a g e so f t h e s a m ec l a s sd i s t r i b u t ec l o s e l yi sc a l c u l a t e d ，a n dt h e nt h ei m a g e sw h i c h a r en e a rt h eq u e r y p o i n ti nt h ep r o j e c t e ds p a c ea r ef e d b a c ka ss i m i l a ri m a g e st ou s e r s e x p e r i m e n t a lr e s u h so n t h ec o r e li m a g ec o l l e c t i o nh a v ed e m o n s t r a t e dt h a tt h i s a l g o r i t h ma c h i e v e sa b e t t e rr e t r i e v a lp e r f o r m a n c ei nr e t r i e v i n gm u l t i i m a g e s s e c o n d ，a st ot h es m a l ls a m p l ei s s u e ，i n s u f f i c i e n tp o s k i v ee x a m p l e sr e s u ri nt h e i m p r e c i s ee s t i m a t eo f t h ew e i g h tm a t r i xi nt h ec l a s s i c a lr e l e v a n c ef e e d b a c ka l g o r i t h m s t h e r e f o r e ，t w od i f f e r e n to v e r - s a m p l i n gm e t h o d sa r ep r o p o s e dt h er e s u l t so f al a r g e n u m b e ro f e x p e r i m e n t s h a v es h o w nt h a tt h er e t r i e v a lp e r f o r m a n c eh a sb e e ni m p r o v e d e f f e c t i v e l yt h r o u g ho v e r - s a m p l i n gp o s k i v es a m p l e s f u r t h e r m o r e ，w ep u tf o r w a r d an e wr e t r i e v a l a l g o r i t h mb yc o m b i n i n gn e g a t i v e e x a m p l e s w ea r g u et h a t t h er e t r i e v a lp r o c e s sh a st w op h a s e s i nt h ef i r s tp h a s e 一“s e a r c hs i m i l a r k y ”p h a s e ，t h ei m a g e sw h o s ef e a t u r e sa r es i m i l a rt ot h o s eo f p o s i t i v e e x a m p l e s a r ec h o s e nf r o mt h ei m a g ec o l l e c t i o n ，r e g a r d l e s so ft h e i re m e r g e n c ei n 2 a b s t r a c t中图科学技术大学硕士学位论立 n e g a t i v ee x a m p l e s i nt h es e c o n dp h a s e 一“s e a r c hd i f f e r e n c e ”p h a s e ，a c c o r d i n gt ot h e d i f f e r e n td i s t r i b u t i o n so fp o s i t i v ee x a m p l e sa n dn e g a t i v ee x a m p l e s ，t h er e t r i e v a l r e s u l t so ft h ef i r s t p h a s e a r er e f i n e d b ye n h a n c i n g t h o s e f e a t u r e s ，w h i c h c a n d i f f e r e n t i a t et h et w os e t so fe x a m p l e s t h es u g g e s t e ds c h e m e i sv a l i d a t e d b y e x p e r i m e n t a lr e s u l t so n _ t h ec o r e li m a g e c o l l e c t i o n k e y w o r d ：c 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 i n g u l a r i t yi s s u e ， s m a l ls a m p l ei s s u e ，p o s i t n ee x a m p l e ，n e g a t i v ee x a m p l e ，f e a t u r es e l e c t i o n 3 第l 章绪论中国科学技术大学硕士学位论文 第1 章绪论 1 1 图像检索简介 随着i n t e r n e t 和数字化技术的发展，人类进入信息社会，以图像、视频、 音频为代表的多媒体信息出现了急剧增长的趋势。但是由于多媒体数据具有数据 结构复杂、数据量巨大、媒体处理要求高等特点，因此，迫切需要研究不同于传 统数据库的多媒体数据的查询方法，丽图像是信息载体中最活跃和重要的媒体之 一，所以对图像的检索成为我们研究的主要内容。 早在二十世纪七十年代，图像数据研究者们就提出基于文本方式的图像检索 1 ，2 ，3 。其基本步骤是先对图像用文本进行注解，然后通过数据库管理系统来 完成图像检索。其检索技术主要有自然语言描述法，采用该方法描述图像信息时 一般不设计对物理图像的分析处理，具体检索时是以系统存储图像的有关信息内 容( 如题名、类别、主题等) 作为检索入口，现在实用的图像检索系统大多采取这 种方式。该方法实质是把图像检索转换为对与该图像对应的文本检索，文献 4 对该技术进行了较为全面的综述。随着图像数据库数量的飞速增长，基于文本标 注的图像检索存在的主要问题是：一是手工对图像进行标注所需的工作量太大， 其二是图像注解的主观性和不准确性可能导致检索过程的失配。由于个人感知的 差异，不同的人对相同的图像可能有不同的理解，即使是同一个人在不同的时候 也会有不同的理解，因此以用户标注的关键字来检索，很可能导致检索产生错误 的匹配。 到了二十世纪九十年代，随着信息处理技术和计算机网络蓬勃发展，特别是 i n t e r n e t 技术的发展，信息的发布由单一的文本向多媒体形式( 图像、视频、音 频等) 扩展，发布人也由少数公司团体向个人分散，任何群体或个人都很容易向 网络中提供大量的信息，众多的大规模图像数据库的出现，从而导致原有的基于 文本标注的检索越来越不适应网络信息检索的要求 1 ，2 。为了克服基于文本方 式检索的弊端，研究者提出了基于内容的图像检索，其主要思想是：根据图像的 视觉特征如颜色特征、纹理特征、形状特征以及空间关系等，计算查询图像和目 标图像之间的相似距离，然后按相似度匹配进行检索。 第1 章绪论中国科学技术大学硕士学位论文 比较典型的系统包括瑕m 公司的q m c 系统 5 】，m i t 实验室的p h o t o b o o k 6 】，u i u c 的m a r s 7 】，哥伦比亚大学的v i s u a t s e e k 8 】，以及微软亚辨l 研究院 开发的i f i n d 9 等检索系统。 基于内容的图像检索按应用背景大致可以分为两类：一类是面向特定图像数 据库的图像检索系统，如目前应用得较多的指纹数据库、头像数据库、数字图书 馆、医用影像数据库等；另一类是面向网络图像数据库的检索系统。 1 2 相关反馈概述 1 2 1 提出背景 相关反馈技术最初从文本检索领域发展而来 1 0 】，后来被用到基于内容的多 媒体检索，二十世纪九十年代后主要是用于基于内容的图像检索( c o n t e n tb a s e d i m a g er e t r i e v a l ，c b i r ) 方面 1 l 一1 7 】。由于人们对一幅图像一般只需看一眼就能 很快了解它的含义，而对一篇文章则需要花费很长时问才能领会其内容，因此对 图像的反馈过程比较快也更容易让用户评价。而且不同的用户在不同的时候对同 一幅图像有不同的解释。完全由计算机来进行离线预处理( 如聚类、分类) 对某 些特定领域的图像类可以得到较好的效果，但对于大多数图像类而言，完全忽视 用户的主观性会得到无意义的检索结果。更重要的是，由于图像的高层语义和低 层视觉特征之间存在着“语义鸿沟”，所以在图像检索过程中需要与用户进行交 互。早期c b i r 系统需要用户在检索过程中选择感兴趣的图像特征并指定不同特 征的权值以试图找到最接近用户查询的图像。但这样的系统并不能得到满意的效 果，存在两个主要缺点：1 ) 权值的设定强加给用户了过多的负担，要求用户对 图像检索中用到的底层特征具有一定的理解，但这并不符合实际需求；2 ) 查询 中的特征及其相应权值是固定的，并不能反映用户感知的主观性。 1 2 2 相关反馈算法 1 h e u r i s t i cw e i g h t i n gm e t h o d s 信息领域主要有四种检索模型 1 7 ：布尔模型、向量空间模型、概率模型和 第1 章绪论 中国科学技术大学硕士学位论文 逻辑模型，其中向量模型是最常用的模型。早期的c b l r 中的相关反馈方法具有 明显的文本检索方法的特征，如m a r s 系统采用r o c c h i o 公式，通过向正例样 本移动而远离反例样本来更好地估计“理想查询点”，实验结果说明，通过用户 的反馈，系统的检索精度得到一定的提高。文 1 3 】中把文本领域中的“t e r m f r e q u e n c y ”和“i n v e r s ed o c u m e n tf r e q u e n c y ”的概念引入到图像检索中，把对一篇 文档中的词的权重估计转变为对图像特征空间中每一维特征的权重估计。 r u i & h u a n g 在文 1 4 1 e 0 提出了一种利用特征标准差的算法，他们认为标准方差越 小的特征维越重要，对特征空间中特征分布标准差小的特征维增加权值，反之则 降低权值，取得了较好的检索效果。除了缺乏优化外，这些h e u r i s t i c - b a s e d 特征 加权方法还做了一个强条件的假设：特征之间是相互独立的 2 7 】。 2 优化学习算法 相关反馈从早期的h e u r i s t i c - b a s e d 特征加权方法发展到近期提出的优化学习 算法 2 3 2 5 ，2 7 。研究者开始从一个更加系统的观点来研究相关反馈，把检索过 程看作是对两个要素的学习过程；一是学习合适的空间变换，即把原来的特征空 间变换为一个更好地映射到用户的高层概念空间。特殊地，这种变换是一种简单 地对原特征空间不同坐标的加权。二是学习用户头脑中的“理想”查询点。在 文 1 8 ，1 9 1r 9 ，基于最小化新的查询向量和所有正例样本的总距离，求出的最优查 询向量是正例样本的加权平均值，最优的权值矩阵是加权的白化变换矩阵。 2 各种机器学习方法 机器学习的经典定义是利用经验改善系统自身的性能 2 6 ，根据m i t c h e l l 的 这个定义，任何利用经验来提高系统性能的任务都可被看作是机器学习任务。在 c b i r 中，每次用户反馈的信息就是“经验”，通过相关反馈来提高系统的检索 性能 2 4 】。因此各种机器学习方法 2 8 都可以被应用到相关反馈中；神经网络方 法 2 0 1 、决策树方法 2 9 1 、贝叶斯学习 3 0 3 3 1 ，b o o s t i n g 技术 3 4 1 、判别分析方法 3 5 1 和支持向量机方法 3 6 3 8 】等。 文 2 0 1 采用t s - s o m ( t r e e - s t r u c t u r e ds e l f - o r g a n i z i n gm a p ) 为不同特征建立图 像索引，把正例和反例样本映射为正负脉冲，通过低通操作可以看出不同特征之 间的相对重要性：因为一个“好”的映射使正例样本聚集而使反例样本分散。 第1 章绪论 中国科学技术大学硕士学位论文 m a c a r t h u r 等人 2 9 把相关反馈作为一个二分类的学习问题，并用决策树去 依次“切割”特征空间直到落在一个区域中的所有点属于同一个类。这样得到的 决策树把图像库分类：把落入相关叶节点的图像收集起来并返回查询图像的近 邻。 c o xe 3 0 3 和n u n o 3 1 用贝叶斯规则来预测样本属于一个特定类的概率并 试图将检索错误降到最低。s u 3 2 ，3 3 1 认为每幅查询和与之对应的所有正反馈图 像构成了一个拥有共同语义含义的图像集合，并构造出该检索样本图像在特征空 间的贝叶斯分类器。 支持向量机方法 3 6 3 8 1 主要是寻找一个能将正例图像和反例图像分开且分 类空隙最大的最优分类面。 t i e u 和0 1 a 在文 3 4 通过b o o s t i n g 技术构造一个强分类器，实验证明可以有 效地对一个有大量特征的图像进行学习。 判别分析方法 3 5 】认为正例样本属于同一个类，而每个反例样本单独成为一 类，主要是寻找一个最优判别子空间，在该空间中正例图像相对更密集，而反例 图像则远离正例图像。 由于用户通常不会提供大量的反馈样本，训练样本的数量很少，所以关键问 题是如何在高维特征空间中对小样本进行学习。小样本使得许多学习方法，例如 决策树方法和神经网络方法，不适合做基于内容的图像检索【2 7 】。 一些研究者从模式识别或分类的角度来研究c b i r 中的相关反馈过程：把用 户标注的正例和反例样本作为训练样本，用训练好的分类器把图像库分为相关类 图像和不相关类图像。因此许多现有的模式识别工具被用作分类器，如最近邻分 类i 撂 3 9 1 、贝叶斯分类n 3 1 1 、支持向量机 3 7 1 等，然而对c b i r 中的相关反馈过 程进行学习不同于经典的模式分类问题。在传统的模式识别领域，通常存在一个 明晰的类结构，即数据集合里的每个项目都属于一个或几个良定义的类，分类算 法通常有一个非常明确的目标：尽量把整个数据集分为不同的类。但是多数c b i r 中都没有预先定义的类结构，即使有预定义的类结构，仍然很难决定一幅图像属 于哪个类。因为这取决于人的主观性和人类认知的不一致性，因此c b i r 中的分 4 第1 章绪论中国科学技术大学硕士学位论文 类算法常常缺少明晰的目标。从这个观点看，这些基于分类的方法在一些约束环 境下可以提高检索性能，但并不都适用于通用图像库。 1 2 3 相关反馈的特点 1 ，用户查询目标 尽管大多数研究者认为用户要检索与查询图像“相似的一类图像”即“类搜 索( c a t e g o r ys e a r c h ) ”；而c o x 等在文 3 0 ，4 0 认为用户要查询“一幅具体的 图像”即“目标搜索( t a r g e ts e a r c h ) ”并且反馈是以“相关性判断”的形式给 出，如正例图像不一定是目标图像而是比其他图像更接近于目标图像。在c o x 等在文e 4 0 中提出目标检索的概念前，类搜索是c b i r 系统唯一的检索方式。类 搜索是查询和用户提供的样本图像内容相似的图像。目标搜索是用户查询一个具 体的目标图像，正例样本是用户标注的和查询图像相似的那些图像。但是，这种 方式存在一些实际问题：第一，实际中很难达到用户主观的一致性，用户很难确 定哪幅图像更接近目标图像；第二，内容相似的图像也许在特征空间中分布得较 远，这使得相关反馈不能解决目标搜索问题。 2 训练数据 在相关反馈框架下，用户通过作出相关性评价来不断优化检索性能：如文 3 l ，3 4 ，4 1 中系统只需用户对正例和反例样本给出二值评价；文 1 8 ，1 9 ，4 2 只考 虑对正例图像的肯定评价；还有一些系统提供更加复杂的交互方法，如文 1 5 ，4 3 要求用户标注出正例图像及其相关程度、反例图像及其不相关程度。c o x 在文 4 0 3 中把反馈认为仅仅是“相对的判断”而不是一个绝对的是或不是的判断；还有一 些算法用标记和未标记的数据作训练 4 4 ：在e m 迭代中对用户反馈( 标记数据) 和其它数据点( 未标记数据) 作判别分析，选择特征子空间使对两类样本的分布 假设都能得到更好的支持，但该方法对大型数据集的计算量很大。另一种新的训 练方式是在浏览或数据可视化过程中“从图像的布局中学习” 4 5 ，4 6 。 3 特征选择和表示 就特征选择而言，大多数c b i r 系统那样采用了诸如颜色直方图或颜色矩、 第1 章绪论中国科学技术大学硕士学位论文 纹理、形状和结构特征，而t i e u 和v i o l a 在文 3 4 采用了b o o s t i n g 技术在一个超 过4 ，5 0 0 0 维的特征空间中训练分类器，假设正例样本和( 随即选择的) 反例样 本符合高斯分布，为每个特征维独立构造弱二类分类器，强分类器就是如 a d a b o o s t 方法对若干弱分类器加权得到。就特征表示而言，尽管多数方法用一 个特征向量表示一幅图像区域，v a s c o n c e l o s 和l i p p m a n 4 7 采用d c t 系数上的 高斯模型来表示图像，再用贝叶斯推导来分类和学习。 4 类的分布 认为样本分布符合高斯模型是一种常用简便的假设 3 4 ，4 7 ；m e i l h a c 和 n a s t a r 4 8 用p a r z e n 窗e l 方法来估计正例样本的分布；还有 3 5 ，3 7 通过基于核 函数的方法把样本转换到新空间中以实现原空间中的非线性判别。 1 2 4 相关反馈算法存在的问题 1 。小样本问题 相对于特征空间的维数( 从几十维到上百维) 和现实图像库的图像类别数目 而言，训练样本的数目比较少，一般交互过程中不超过2 0 幅。一些学习算法如 支持向量机在小样本的情况下不能给出稳定的、有意义的结果 3 4 ，3 5 ，除非用 户提供更多的样本 4 9 】。 2 协方差矩阵的奇异问题 文【1 8 ，1 9 】中由于在高维空间中的对小样本进行学习，容易导致奇异问题( 协 方差矩阵不可逆) 。i s h i k a w a 【1 8 】用伪逆阵来代替奇异协方差矩阵的逆矩阵不仅缺 乏数学论证，其计算结果也违反人们的直观理解 2 5 1 ，尤其对零方差的子空间求 逆将导致矛盾的加权结果。r u i & h u a n g 在文 1 9 采用两层加权模型( 在部分独立 的假设下) 来更好地处理由于较少的训练样本造成的奇异问题，但并没有从根本 上解决这个问题。 3 反例样本 考虑负反馈时应该如何处理反例样本也是个关键问题。大致有两神选择反例 样本的方式：一种是随机选择，如t i e u 和v i o l a 3 4 】用随机采样来解决反例样 第l 章绪论 中国科学技术大学硕士学位论文 本数量少的问题，但是可能把正例样本错误地当作反例样本来计算；v a s c o n c e l o s 和l i p p m a n 3 1 在选择一类的反例时，从其补类的正例中随机选择。另一种则由 用户在反馈过程中标注出反例样本。 4 训练样本的不对称性 图像检索的理想输出并不是要求出每幅图像的0 - 1 判定结果( o 代表无关图 像、1 代表相关图像) ，而是返回一个排序结果中的排在前面的k 幅图像。后者 相对于前者而言是个更容易的任务，因为所有排列位置在k 以后的图像都被判定 为无关图像，因此不需要计算对它们和查询图像的相似性作比较。多数分类算法 或学习算法，比如线性判别分析方法 5 0 】或支持向量机方法【5 1 】认为正例样本和 反例样本都分别代表了相关图像类和无关图像类的真实分布，因此对正例样本和 反例样本采用同样的处理方法。然而在实际的相关反馈过程中，用户标注的反例 样本不能反映所有无关图像类的分布，所以对正例样本和反例样本需作不对称处 理 3 5 。 5 实时需求 在用户和计算机交互的过程中，反馈时间要比较短，算法时间复杂度要比较 小，算法收敛比较快，否则用户容易疲劳，因此有必要避免在每次反馈时都对整 个图像库作大规模计算。 1 3 本论文的研究内容及组织 1 3 1 本论文的研究内容 本文主要针对目前c b i r 中的相关反馈算法中存在的以下问题：协方差矩阵 的奇异问题、小样本问题、和训练样本中的不对称性问题，作了一些研究。本文 的研究内容从以下几个方面展开： 1 、针对协方差矩阵的奇异问题，提出了一种新的基于相关反馈和样本散布 矩阵的相关反馈算法。实验结果表明该算法对多例图像查询有较好的检 索效果。 7 2 、针对小样本问题，经典的相关反馈算法由于缺少足够的正例样本导致无 法准确估计权值矩阵( 全矩阵) 的参数，因此提出两种不同向上采样方 法。大量实验结果说明：对正例样本向上采样可以显著提高系统的检索 性能。 3 、根据正例样本和反例样本在检索的两个阶段中的不同作用及其在特征空 间中不同的分布方式提出一种新的结合反例样本的检索算法，实验结果 表明该算法有较好的检索结果。 1 3 2 本论文的内容安排 全文共分六章，具体安排如下： 本章即是第1 章绪论。首先对图像检索发展的历史作了简单概述，然后介绍 了能有效解决“语义鸿沟”的一种关键技术一相关反馈技术的研究现状，最后列 出了本文的组织和章节结构。 第2 章描述了基于相关反馈的图像检索系统的框架。 第3 章针对经典相关反馈算法中协方差矩阵的奇异问题，提出了一种新的基 于相关反馈和样本散布矩阵的图像检索方法，在c o r e l 图像库中的实验结果表明 该算法对多例图像查询有较好的检索效果。 第4 章主要研究采样在检索中的作用，通过大量的实验验证并比较了两种不 同的向上采样方法对检索算法的有效性。 第5 章提出一种新的结合反例样本的检索算法，在c o r e l 图像库上的实验结 果表明该算法提高了系统的检索性能。 第6 章对本论文的研究工作进行了总结和归纳，并指出了本文论文研究的特 色，最后对今后进一步的工作做了展望。 第2 章基于相关反馈的图像检索系统框架中国科学技术大学硕士学位论文 第2 章基于相关反馈的图像检索系统框架 本章首先介绍基于相关反馈的c b i r 系统框架，然后概述多数c b i r 系统采 用的图像特征并给出常用的相似度度量方法，最后介绍c b i r 系统中常用的检索 性能评估参数。 2 - 1 基于相关反馈的c b i r 系统框杂 典型的基于相关反馈的c b i r 系统如图2 1 所示：首先抽取图像的视觉内容弗 用多维特征向量表示图像，图像库的图像特征构成特征库。当用户按图例或草稿 图来检索图像时，系统先把这些查询图像转换成其内部的表示形式即特征向量； 然后计算所有图像和查询图像间的相似度，距离，把和查询图像最相似的前k 幅图 像返回给用户；用户对反馈图像做出其相关性评价后，系统根据用户反馈的信息 和图像的底层视觉特征再重新计算相似图像，重复以上过程直到用户满意。 图2 - 1 基于相关反馈的l r 检索系统框架 第2 章基于相关反馈的图像检索系统框架 中图科学技术大学硕士学位论文 2 2 图像的视觉特征 图像特征包括高层语义特征和底层视觉特征。图像的语义一般涉及到图像的 抽象属性，可以分成场景语义、行为语义、情感语义，但目前仍缺乏对图像语义 的有效描述方式和提取方法。因此下面主要介绍图像的视觉特征，c b i r 中常用 的视觉特征有颜色、纹理、形状等特征。 2 1 1 颜色特征 颜色是物体表面的一种视觉特征， 事物往往有着相似或相同的颜色特征 每种物体都有其特有的颜色特征，同一类 因此可以利用颜色特征来区分不同物体。 目前几乎所有的c b i r 系统都采用了颜色直方图，颜色直方图是表示图像中 颜色分布的一种统计值，它的横轴表示颜色值，纵轴表示具有相同颜色值的像素 个数在整幅图像中所占的比例 5 2 ，5 3 1 。该方法优点在于简单有效，而且具有尺 度、平移以及旋转不变性，缺点是忽略了色彩的空间分布信息。s t r i c k e r 和o r e n g o 提出了颜色矩方法 5 4 】，认为颜色信息集中在图像颜色的低阶矩中，他们主要对 每种颜色分量的一阶、二阶和三阶矩进行统计。对于图像检索来说，颜色矩是一 种简单有效的颜色特征表示方法。此外，还有颜色聚合矢量( c o l o rc o h e r e n c e - j v e c t o r ) 、颜色相关图等方法。 以上各种颜色特征是基于全局颜色特征索引来获得整幅图像颜色分布的信 息，但是丢失了许多局部的颜色空间信息。s m i t h 等考虑了颜色的局部分布，提 出用颜色集( c o l o rs e t ) 方法来提取空间局部颜色信息并提供颜色区域的有效索 引 8 。 2 1 2 蚊理特征 纹理特征是一种反映图像中同质现象的视觉特征，例如云彩、树木、砖、织 物等都有各自的纹理特征。纹理特征对模式识别和计算机视觉等领域的重要意 义，在c b i r 中得到了广泛的应用。 纹理分析方法主要有两类：结构分析方法和统计分析方法。结构分析方法包 1 0 第2 章基于相关反馈的图像检索系统框架中国科学技术大学硕士学位论文 括形态学算子、边界图等，认为图像由较小的基元按一定规律排列而成，采用的 是句法分析方法，对于规则的结构纹理分析有较好的效果。 统计方法是对图像的空间分布信息进行统计。h a r a l i c k 等提出了关于纹理特 征的共生矩阵表示 5 5 ，他们首先根据图像像素之间的距离和方向构造了一个共 生矩阵( c o m a t r i x ) ，从中提取出有意义的统计量作为纹理特征的描述，一般 基于共生矩阵可以导出以下统计量：角二阶矩、对比度度量、相关、方差、反差 分矩、和的方差、和的均值、和的熵、熵、差的方差、差的熵、二种相关信息测 度和最大相关系数等。t a m u r a 等从人类对纹理特征视觉感知的心理学角度上提 出了的六个对应的基本特征。纹理分析方法还包括w o l d 分解、马尔可夫随机场、 分形模型、多分辨率分析方法如g a b o r 和小波变换等。 2 1 3 形状特征 形状是刻划对象的一个重要特征。对形状特征描述的一个重要标准是要求它 必须具有仿射不变性，即相对于旋转、平移和尺度变换具有不变性。 形状被认为是一条封闭的轮廓曲线所包围的区域，对形状的描述分为对轮廓 的描述以及对轮廓所围区域的描述，前者用到物体的外边界，面后者则关系到整 个对象所在的区域。对于轮廓的描述主要有：直线段描述、样条拟合曲线、高斯 参数曲线和傅立叶描述子等传统算法，其中最典型的方法为傅立叶描述符。对于 区域描述主要有无关矩、区域面积、区域纵横比等。 2 3 相似性度量 目前研究图像内容的相似性度量是指图像特征间的相似性，是图像检索研究 的重要组成部分。相似性度量方法的好坏影响到图像检索的性能；而相似性度量 的计算复杂性影响到图像检索的用户响应时间。一般假设图像特征矢量是距离空 间中的元素。距离空n i x ，d ) 是集合x 和映射d ：x x - r 满足以下距离公理： 协，y ，：x 1 ) d ( x ，”= 0 x = y 第2 章基于相关反馈的图像检索系统框架 中国科学技术大学硕士学位论文 2 ) d ( x ，y ) 2 d ( z x ) 3 ) d ( x ，z ) d ( x ，y ) + d ( y ，z ) 下面介绍常用的相似性度量。定义d ( i ，j ) 为查询图像i 和图像数据库中图像j 之间的距离，其中( i ) 表示图像i 中的第f 个特征向量。 1 m i n k o w s k i 距离 如果图像特征向量相互独立而且同等重要那么可以采用m i n k o w s l d 距离k ， 来度量图像之间的相似性： d ( i ，l ，) = ( j z ( ，) 一五秒 当p = 1 ，2 ，m 时，d ( i ，j ) 分别称为l 1 ，l 2 ( 也称为欧氏距离) 和瓦。 许多c b i r 系统采用m i n k o w s k i 距离，比如m a r s 系统采用欧氏距离计算纹 理特征之间的相似性。n e t r a 系统采用欧氏距离计算颜色和形状特征的相似性， 采用l 1 计算纹理特征间的相似性。b o l b w o r l d 系统采用欧氏距离来计算纹理和形 状特征之间的相似性。 直方图交距离( h i s t o g r a mi m e r s e c t i o n ) w 以认为是l l 距离的一种特殊形式， s w a i n s w a i n1 9 9 1 等用来计算图像颜色之间的相似性。图像i 和图像j 的直方图 之间的交距离定义为： = 驾筹产 2 q u a d r a t i cf o r m ( q f ) 距离 m i n k o w s k i 距离对所有的特征向量平均对待，而没有考虑特征向量之间的关 系。然而在实际情况下，各个特征向量之间是有关联的，为了解决这个问题，可 以采用以下q f 距离： d q ，j ) = ( e f j ) a ( f i f j ) 1 2 第2 章基于相关反馈的图像检索系统框架中国科学技术大学硕士学位论文 这里a = 砌是一个对称矩阵，表示特征向量之间的相关性，而且 为特征i 和特 征之问的相似性。许多检索系统用q f 距离对图像的颜色直方图特征作计算， 相对于欧氏距离和直方图交距离而言，由于q r 距离考虑到颜色之间的相关性， 检索结果更加符合人的视觉感觉，但是相关性矩阵的计算量较大。 3 m a h a l a n o b i s 距离( 马氏距离) 当特征向量之间具有相关性，而且各个特征向量对距离的贡献大小不同的时 候，一般可以采用m a h a l a n o b i s 距离，其定义为： d ( i ，) = ( f i f j ) c 。( e f j ) 这里c 表示特征向量的协方差矩阵。如果各个特征向量相互独立，那么在第j 维特征上的协方差值为c f ，则m a h a l a n o b i s 距离公式可以简化为： d ( i ，- ，) = ：。( e f j ) 2 q 图像高维特征也可以看成各元素的集合，因此可以采用集合之间的距离来度量特 征之间的相似性。 上述的相似性度量所用的特征矢量对于每幅图像来说维数都是固定的。对于 另外一些特征向量，不同图像之间的特征维数是不同的，如w a n g 所用的基于区 域特征的矢量i s 6 ，对于每幅图像来说区域数目是不同的，他们采用集成区域匹 配法( i n t e g r a t e dr e g i o nm a t c h i n g ) 对两幅图像的每个区域对进行距离度量，最后再 通过相似性矩阵综合得到相似性距离。总之，相似性度量仍然是图像检索研究中 的个重要的问题，心理学研究表明，人对图像感知的相似性度量和目前使用的 距离度量有很大的差异，也是导致检索效果不理想的重要原因之一。寻找便于计 算和更加符合感知相似性的数学模型是提高图像检索性能的途径。 2 4 检索性能评估参数 目前的对图像检索算法的评价主要集中在对检索结果正确度的评价上，其他 方面如系统响应时间、数据处理能力等指标研究的较少。目前c b i r 系统的性能 评估技术e s 7 ，5 8 起源予信息检索( i n f o r m a t i o nr e t r i e v a l ) 。c b i r 系统中主要 的性能评估参数，例如查准率( p r e c i s i o n ) 和查全率( r e c a l l ) 都是信息检索中最 第2 章基于相关反馈的图像检索系统框架中国科学技术大学硕士学位论文 常用的性能评测参数。假定检索规模为一次检索反馈中系统提供给用户的侯选图 像数目记为，则查准率和查全率的定义为： 查准率( p r e c i s i o n ) = 每次反馈的相关图像数目检索规模 查全率( r e c a l l )= 每次反馈的相关图像数目胁该类图像数目 查准率和查全率越高，表明该检索系统的效果越好。一般地，查全率和查准率 是一对矛盾，当要求精度较高时，查全率较低，反之亦然。因此，一般的检索系 统只要求在这两者之间达到一个最优的平衡点，就认为达到了较好的检索性能。 采用排序方法评价系统性能也是一种常用的方法 1 9 ，5 7 。一次检索中的正例 图像数目为。，凤为第k 幅正例图像的排序序号，则正例图像的平均排序a v r r 定义为： 1n p a ， a v r r = 二r n ，。钙 一般地，a v r r 越小，检索算法越好。在相同的检索规模下比较方法a 和方法b 的检索效果，如果a 的查准率比b 高，而a v r r 比b 小，则方法a 比方法b 好， 但如果a 的查准率和a v r r 都比b 大，则无法判断。查准率只能说明检索到的 正例图像的数目，而a v r r 则反映正例图像在反馈图像中的排序位置。 上述评价方法在一定程度上评价了检索系统的效果，但这些评价并不能充分 反映系统的一些性能。主要的困难还是在于人对图像内容的感知上具有主观性， 很难定义一个客观的评价标准来评价检索的效果。 2 5 小结 本章首先介绍基于相关反馈的c b i r 系统框架并概述多数c b i r 系统采用的 图像特征：颜色、纹理和形状特征；然后给出常用的度量图像特征问相似性的三 种距离：m i n k o w s k i 距离、q f 距离和m a h a l a n o b i s 距离，最后给出c b i r 系统中 用于评价算法优劣的主要性能评估参数：查准率、查全率和a v i l r 。 1 4 第3 章奇异问题及其改进算法 中国科学技术大学硕士学位论文 第3 章奇异问题及其改进算法 本章首先介绍经典的相关反馈算法，并针对协方差矩阵的奇异问题，提出一 种新的基于相关反馈和样本散布矩阵的图像检索方法。 3 1 经典的相关反馈算法 3 1 1 基本概念和定义 用欧氏距离公式来计算图像x 与查询向量q 间的距离，有以下几种计算欧式 距离的变体：普通欧氏距离，加权欧氏距离和广义欧氏距离【1 8 】。 1 ) 普通欧氏距离公式： d = ( x - - q ) 7 ( x q ) 2 ) 加权欧氏距离公式 d = ( x q ) 7 a ( x q ) 3 ) 广义欧氏距离公式 d = ( x q ) 7 w ( x q ) 其中加权欧氏距离公式中的a 是个对角阵，其对角线上的元素就是特征每维的权 重。广义欧氏距离公式中的w 是是对称矩阵，实对称矩阵w 可以被分解为如下 形式：w = p t a p ，其中a 是w 的特征值构成的对角阵，p 是对应的特征向量构 成的正交阵。那么广义的欧氏距离也可以写为： d = ( x q ) 1 w ( x q ) = ( x q ) 7 u a p ( x q ) = ( p ( x q ) ) 1 盈p ( x q ) ) 。 在一个二维特征空间中，用空心圆点表示查询向量q ，则这三种欧氏距离分 别在以q 为中心的圆或椭圆中计算相似图像。普通欧氏距离是在原特征空间中直 接计算距离，而加权欧氏距离公式改变了原特征空间中每一维特征的权重，广义 欧氏距离公式则用矩阵p 把特征空间先映射到一个新空问再用对角阵a 对新空 间的每一维进行权值调整。 s 第3 章奇异问题及其改进算法 中国科学技术大学硕士学