（计算机软件与理论专业论文）一种基于pca的相关反馈图像检索算法与实现.pdf

一种基于p c a 的相关反馈图像检索算法与实现 专业：计算机软件与理论 硕士生：陆斌光 指导教师：李才伟 摘要 随着互联网的发展，人们对在互联网上进行图像检索，尤其是基于内容的图 像检索的需求越来越大。从2 0 世纪9 0 年代初起，基于内容的图像检索( c a m ) 就成为多媒体技术应用的研究热点。由于目前计算机视觉和图像理解的发展水平 所限，使得c b i r 还无法真正支持基于语义的图像检索，所以目前研究得较多也 比较成熟的检索算法大部分是基于图像的低层特征的，比如利用图像的颜色、纹 理、形状等特征来检索。 为了改进传统的c b i r 系统的检索性能，一般会对进行异种特征的组合或结 合相关反馈的技术。本文提出一种基于p c a ( p r i n c i p a lc o m p o n e n ta n a l y s i s ) 主 成份分析的方法结合颜色直方图，主色划分等特征，加以相关反馈的人机结合图 像检索的算法。颜色是描述图像内容的最直接的视觉特征，直方图有统计直观， 图像平移、旋转不变的性质，但用直方图进行图像检索中主要利用的是图像颜色 分布的全局特性，没有利用颜色的空间分布。本文加上区域主色划分等特征进行 p c a 主成份分析结合，在图像的匹配算法上作出了一定的创新，再加以相关反 馈的人机结合可以不断地提高检索性能。最后，本文编程实现了该算法，实验结 果证明了该算法的高效性与有效性。 关键字：基于内容的图像检索；p c a ( 主成份分析) ：相关反馈 a l g o r i t h m a n di m p l e m e n t a t i o no fi m a g er e t r i e v a l w i t hr e l e v a n c ef e e d b a c kb a s e do np c a m a j o r ： c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ： b i n g u a n gl u s u p e r v i s e r ：c a i w e il i w i t ht h ed e v e l o p m e n to fi n t e m e t ，t h es e a r c h i n gf o rp i c t u r e so ni n t e r n e t ， e s p e c i a l l yt h ed e m a n d t h a tt h ep i c t u r eb a s e do nc o n t e n ts e a r c h e si sg r e a t e ra n dg r e a t e r f r o mt h eb e g i n n i n go f1 9 9 0 s ，t h ec 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 ) i sb e c o m i n g t h ef o c u so nt h es t u d y i n go fm u l t i m e d i aa p p l i c a t i o n b e c a u s eo fc o m p u t e rv i s i o na n d r e s t r i c t i o no fp i c t u r eu n d e r s t o o da tp r e s e n t ，i tm a k e sc b i rs t i l lu n a b l et or e a l l y s u p p o r tt h es e a r c ho fp i c t u r eb a s e d o nc o n t e n t ，w h i c hm a k e ss e a r c h i n ga l g o r i t h ms t i l l b eb a s e do np i c t u r el o w e rc h a r a c t e r i s t i cm o s t l ya tp r e s e n t ，s u c ha sc o l o r , l a m i n a t i o n ， f o r mo f p i c t u r ec h a r a c t e r i s t i c f o ri m p r o v i n gt h ep e r f o r m a n c eo ft r a d i t i o n a lc b i rs y s t e m ，d i f f e r e n tk i n d so f c h a r a c t e r i s t i cw i l lb ec o m b i n e do rt h er e l e v a n tf e e d b a c kt e c h n o l o g yw i l lb eu s e d g e n e r a l l y t h i s a r t i c l er e p r e s e n t so n ea l g o r i t h mo nt h eb a s i so f p c a ( p r i n c i p a l c o m p o n e n ta n a l y s i s ) c o m b i n i n gt h ec o l o rh i s t o g r a ma n dd o m i n a n tc o l o ro fp a r t i t i o n s ， w i t hm a n m a c h i n ec o m b i n a t i o no fr e l e v a n c ef e e 曲a c k t h ec o l o ri st h em o s td i r e c t v i s i o nc h a r a c t e r i s t i co fd e s c r i b i n gt h ec o n t e n to ft h ep i c t u r e t h eh i s t o g r a mi sc o u n t e d s i m p l y t h et r a n s l a t i o no ft h ep i c t u r ea n dr o t a t i n gt h en a t u r ew i l ln o tc h a n g e b u ti t w a st h eo v e r a l lc h a r a c t e r i s t i ct h a ti si s s u e do ft h ec o l o ro ft h ep i c t u r e ，i th a sn o t u t i l i z e ds p a c ed i s t r i b u t i o no ft h ec o l o r s ot h i sa r t i c l ei n c l u d e sd o m i n a n tc o l o ro f p a r t i t i o n sw i t hi na d d i t i o n i tm a k e sc e r t a i ni n n o v a t i o ni nt h ea l g o r i t h mw i t hr e l e v a n c e f e e d b a c ka n dc a ni m p r o v ep e r f o r m a n c eo fs e a r c h i n gw h i l eb e i n gm a n m a c h i n e f i n a l l y , t h i sa l g o r i t h mo fp r o g r a m m i n gr e a l i z a t i o no ft h i sa r t i c l ea n dt h ee x p e r i m e n t a l r e s u l t sp r o v ee f f i c i e n c ya n dv a l i d i t yo ft h i sa l g o r i t h m k e y w o r d s ：c o n t e n t b a s e di m a g er e t r i e v a l ，p r i n c i p a lc o m p o n e n ta n a l y s i s ， r e l e v a n c ef e e d b a c k 第1 章引言 随着网络技术和存储技术的飞速发展，大规模多媒体数据库系统的应用变得 越来越迫切。作为多媒体数据库研究的内容之一，基于内容的图像检索的研究具 有愈加重要的意义。随着数字化多媒体数据的飞速增长，对于这些资料的快速查 找也成为一个非常迫切的需求。因此，基于内容的多媒体信息检索已经成为一个 热门的研究领域，它是对基于文本描述的检索方法的一个十分有益的补充。 图像检索的传统方法是基于文本的，使用关键字注释是最常用昀方法。这样， 对图像的检索就变成了对关键字的查找。但是，基于文本的检索存在的主要问题 是：由于图像注解的主观性和不完备性，因而不能保证正确率。为了克服基于文 本方法的局限性，2 0 世纪9 0 年代出现了基于内容的图像检索( 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 i r ) 系统，它是指直接针对图像内容进行图像信息查询的检 索系统。 基于内容的图像检索是由用户提交检索样本，系统根据样本对象的底层物理 特征生成特征集，然后在数据库中进行相似性匹配，得到检索结果的过程。由于 避开了人工分类等问题，基于内容的图像检索具有明显的优越性。目前，大部分 c b i r 是按照图像的原始视觉特征，在第一层次上进行检索。然而，从实际日常 应用的角度来说，语义图像检索的用途更加广泛。当前主要研究的重点都是在己 知图像的类别上进行图像理解的。例如，在遥感图像上找出目标，在机器人的视 觉图像上实时找出人脸，在人脸的图像中找出五官轮廓并进行匹配，在医学图像 上自动找出癌细胞等等。这些都能够很好地解决专业领域的问题，但是对于普通 的用户用不上。对于普通用户，如果可以使用类似于目前的文字搜索引擎的方式， 对要检索的内容进行基本的文字描述，“图像搜索引擎”则根据些基本的词法 分析，得到搜索的要点，然后在图像库中根据要点分门别类的逐级搜索，最终得 到内容上最贴切的一系列图像，那样就很不错了。这种搜索方式虽然类似于基于 关键字的搜索，但是他是在计算机理解了图像内容的基础上进行的。而这种基于 图像分类的图像检索的工作方式也与大多数在图像原始特征上进行的c b i r 有很 大的不同。但是由于图像内在语义( 用户的主观评价) 与系统自动提取的图像视觉 特征( 颜色、纹理等) 之间难以匹配( 即所谓的语义鸿沟) ，目前这种方法的检 索效果还不能满足实用的要求。 为了克服上述问题，源于信息检索领域的用户相关反馈( r e l e v a n c e f e e d b a c k ) 技术被引入到图像检索中，即系统借助用户对检索结果与检索样本的 相关度评价，不断地修正检索样本与相似度量中的相关参数，取得了较好的效果 相关反馈是一个用户与系统之间的反复交互过程，如何提高反馈的效率，减少交 互次数始终是相关反馈图像检索的关键问题。因此，用户相关反馈信息的利用已 成为个值得研究的问题。 本文就提出一种基于p c a ( p r i n c i p a lc o m p o n e n ta n a l y s i s ) 主成分分析的方 法结合颜色直方图，区域主色划分等特征，加以相关反馈的人机结合图像检索的 算法。本文基于的p c a 主成份分析结合人机结合的相关反馈，结合移动向量优 化算法和特征权重调整算法的动态调整，在图像的特征抽取与匹配算法上作出了 一定的创新，在实验中证明检索性能对比其它传统的相关反馈算法有所提高。本 文给出这样一种基于p c a 的相关反馈图像检索算法的具体思想设计与实现，以 期它以后能用于在互联网上进行基于内容的图像检索。 2 第2 章基于内容图像检索概述 2 1 图像检索发展历史 近几年来，计算机多媒体技术的发展突飞猛进。多媒体信息系统超越了传统 的数据库系统，将各种非文本数据，如数字化的声音、图像和视频图像等集合于 系统之中，用计算机进行处理，并通过计算机网络传输，极大地方便了我们对多 方位、多层次的信息需求。那么，如何根据图像可视特征进行更加直接的快速检 索就成为广大信息工作者关注的问题。近来出现了一种新型图像检索方式一一基 于内容的图像检索( c b i r - - c o n t e n tb a s e di m a g er e t r i e v a l ) ，即是一种根据图像的 可视特征对图像进行检索的方法。这种方法能够根据描述所需图像内容的提问检 索出所要的图像，如根据图像的颜色、纹路和形状等特征进行检索。近来随着多 媒体技术的发展，基于内容的图像检索引起了多交叉学科研究人员的注意。在国 外，特别是在美国，这项技术已成为一个研究热点。国外的一些科研部门、高等 院校、商业公司以至政府机构都纷纷投入大量人力和物力进行研究和开发，以期 取得领先地位，并相继取得了一些成果，使这一新兴领域得到迅速发展。如美国 的n a s a 、i b m 公司、哥伦比亚大学、麻省理工学院等，已开发出水平较高的实 用性产品，其中一些已经投放市场。 对图像检索的研究也是近几年逐渐受到各方面重视。最初的检索方法是用与 图像内容有关的文字对图像进行说明和注释，检索时使用传统的数据检索方法 根据关键词提问和查找所需要的图像。应该说这种方法是比较直接和有效的，并 且直到目前也仍在使用。但在大型的图像数据库中进行复杂图像检索时，这种方 法即表现出速度慢、效率低和提问范围过于狭窄等不足。基于内容的图像检索由 于是根据图像的可视特征检索，能满足多种层次的检索要求，目前已成为图像检 索研究的新热点，并显示出必将成为图像检索的主流方法的发展趋势。 过去对于基于内容的图像检索的研究主要是朝着两个方向。第一，图像内容 主要以一组人工抽取的属性来表现，并被约束在传统的数据库管理系统框架内。 提问被限定使用这些属性。以属性为基础的表现形式限制了较高水平的图像特征 抽取。总的来说，特征抽取的程度越高，对图像数据库提出问题的范围就越窄。 基于属性的检索主要是数据库研究人员所提倡和使用。第二，使用集中的特征抽 取，识男i j 子系统克服基于属性检索的局限性。这个子系统在图像被插入到数据库 中去时，能自动完成特征提取和主体识别的工作。然而，自动进行主体识别的方 3 法有代价高、困难大和领域狭窄等局限性。这种方法主要是图像分析的研究人员 所采用。 在近来的研究中，人们认识到需要将这两方面协调起来。为了达到这个目的， 经研究人员的努力，并融合了知识系统、认识科学、用户模型、计算机绘图、图 像处理、模式识别、数据库管理系统以及信息检索等领域的知识和先进技术，现 已得到了卓有成效的结果。它们主要表现在较为新颖的图像表示、数据模型、高 效灵活的提问处理算法以及专业的独立系统结构等方面。这些先进的内容已使 c b i r 系统从早期走向合理的成熟期。一些商用的软件已经在图像特征抽取和主 体识别自动化、可视特征与空间关系相结合、提问方式多样化、灵活方便的界面、 网络存取等方面具备了比较先进和实用的性能。 c b i r 的核心是抽取图像的各种特征从而对图像进行检索。从本质上讲，它 是一种相似匹配的技术，包括了图像处理、图像理解、计算机视觉和数据库等多 个领方面的技术。其中的图像特征的提取和索引的建立可由计算机自动完成，从 而避免了人工描述的主观性。一个典型的c b i r 系统的基本组成如图2 1 所示。 用户检索的过程一般是提供一个检索样本( q u e r yb ye x a m p l e ) ，于是系统就抽取 该检索样本的图像特征，然后与数据库中的特征进行相似性匹配，并将与特征相 似的图像返回给用户。 2 2c b i r 图像检索的关键技术 图2 1 c b i r 系统的实现依赖于几个关键技术：图像特征的提取、图像特征的相似 性匹配和相关反馈信息的利用等。 4 2 2 1 图像特征提取 图像的内容可以大致分成两种：高层语义内容，它包含高层的概念级反应 f 比如“床前明月光”) ，这需要我们人脑对物体进行识别和判别，往往需要依赖 人类的知识与推理逻辑。低层物理特征，它主要包括颜色、纹理、形状等。到 现在为止计算机视觉、图像处理与图像理解的发展水平所限，使得c b i r 还无法 做到真正支持基于高层语义内容的图像检索，因此目前为止比较完善成熟的图像 检索算法绝大部分是基于图像的低层特征的，也就是利用图像的颜色、纹理、形 状等特征来检索。 颜色 颜色是图像低层物理特征中最底层、最直观的，因为它通常对噪声，图像质 量的退化、分辨率、旋转性和方向等的变化具有很强的健壮性，是绝大多数基于 内容的图像和视频检索的多媒体数据库中经常使用的特征之一。通过颜色特征来 描述的方法主要有以下几种： f 1 1 颜色直方 羽( c o l o rh i s t o g r a m ) 。它是在许多图像检索系统中被广泛采用的 颜色特征，也是十分简单。它描述了图像颜色的统计分布特性，也就是不同色彩 在整幅图像中所占的比例，而并不关心每种色彩所外的空间位置。它具有平移、 尺度、旋转不变性。其核心思想是在颜色空间中采用一定的量化方法对颜色进行 量化，然后统计每一个量化通道在整幅图像中所占的比重。由于颜色直方图缺乏 颜色的空间分布信息，因此改进的方法包括在颜色信息时加入空间信息和基于区 域的颜色特征。最简单的方法是子窗口直方图法，也就是将图像分割成一系列的 子窗口，一一建立索引对应关系。文献【3 】中将图像分成了大小相等的九个子图 像，然后统计每个子图像中的颜色直方图。 ( 2 ) 颜色矩( c o l o rm o m e n t ) 。这是一种非常简单而有效的颜色特征。其基本思 想是在颜色直方图的基础上计算出每个颜色通道的均值、方差、偏差，用这些统 计量替代颜色的分布来表示颜色特征。它具有特征量少，处理简单的特点。 ( 3 ) 颜色相关 虱( c o l o rc o r r e l o g r a m ) 。它是图像颜色分布的另一种表达方式。 这不但刻画了某种颜色的像素数量占整个图像的比例，还反映了不同颜色对之间 的空间相关性。它的主要思想是用颜色对相对于距离的分布来描述信息，因此就 反映了像素对的空间相关性以及局部像素分布和总体像素分布的相关性，并且容 易计算，特征范围小，效果好。 ( 4 ) 颜色一致性向量( c c v ，c o l o rc o h e r e n c e v e c t o r s ) 。它是一种引入了空间位 5 景信息改进了的颜色直方图算法，统计了图像中各种颜色最大区域的像素数量。 从而通过分离开一致性像素和非一致性像素，不难看出它比颜色直方图具有更好 的区别效率。 纹理 纹理是图像的重要特征之一，是一种不依赖于颜色或亮度的反映图像中同质 现象的视觉特征。它是所有物体表面共有的内在特性，例如，云彩、树木、砖等 都有各自的纹理特征。它通常定义为图像的某种局部性质，或是对局部区域中像 素之间关系的一种度量，其本质是刻匿像素的邻域灰度空问分布规律。纹理特征 描述方法大致可以分为四类：统计法、结构法、频谱法与模型法。 ( 1 ) 统计法。它的主要思想是通过统计图像中灰度级分布的随机属性来描述 纹理特征。最简单的统计法是借助于灰度直方图的矩来描述纹理，但这种方法没 有利用像素相对位置的空间信息。为了综合利用这些像素空间位置信息，有入提 出了用共生矩阵来表示纹理特征。该方法研究了纹理的空间灰度级相关性，构造 出一个基于图像像素间方向和距离的共生矩阵，并且从矩阵中提取出反差、能量、 熵、相关等统计量作为特征量表示纹理特征。t a m u r a 等人从人类视觉心理学的 领域研究后提出了一些不同的方法来描述纹理特征【4 】，给出了几个不同的描述 纹理特征的术语：粗糙度( c o a r s e n e s s ) 、对比度( c o n t r a s t ) 、方向度( d i r e c t i o n a l i t y ) 、 线性度( u n e l i k e n e s s ) 、规则度( r e g u l a r i t y ) 、粗略度( r o u g h n e s s ) 等。 ( 2 ) 结构法。它分析纹理的基本思想是先做一个假设。它假定纹理模式由纹 理基本单元是以一定且有规律的形式重复排列组合而成，特征提取就变为确定这 些基元并定量分析它们的排列规则。c a r l u c e i 曾提出一个使用直线段、开放多边 形和封闭多边形作为纹理基元的纹理模型，其排列规则由一种图状语法结构定 义。l u a n d f u 4 给过一种树型语法结构来表示纹理，他们将纹理按照9 9 的窗 口进行分割，每个分解单元的空间结构表示为一棵树。因为实际的纹理大都是无 规则的，因此结构法受到很大限制。 ， ( 3 ) 频谱法。它借助于频率特性来描述纹理特征，包括傅里叶功率谱法、 g a b o r 变换、塔式小波变换( p y r a m i dw a v e l e tt r a n s f o r m ，p w n 、树式小波变换( t r e e w a v e l e t t r a n s f o r m ，r l w n 等方法。经实验指出，g a b o r 特征提供了最佳的模式检 索精度，检索性能优于t w t 和p w t ，缺点是计算速度慢，其尺度不变性和旋转 不变性仍有待研究。 ( 4 1 模型法。它利用一些成熟的图像模型来描述纹理，如基于随机场统计学 的马尔可夫随机场、子回归模型，以及在此基础上产生的多尺度子回归模型等。 这些模型的共同特点是通过少量的参数表征纹理。 形状 图像中物体和区域的形状是图像表达和图像检索中要用到的另一类重要特 征。但不同于颜色或纹理等特征，它的表达必须以对图像中物体或区域的分割为 基础。形状是刻画物体最本质的特征，也是最难描述的图像特征之一，主要难在 对图像中感兴趣目标的分割，由于当前的技术无法做到准确而的自动图像分割。 对形状特征的提取主要是寻找一些几何的变量。目前用于图像检索的形状描述方 法主要有两类：基于边缘和基于区域的形状方法。前者利用图像的边缘信息，而 后者则利用区域内的灰度分布信息。 ( 1 ) 基于边缘的形状特征提取是在边缘检测的基础上，用面积、周长、偏心 率、角点、兴趣点、傅里叶描述子等特征来描述物体的形状，适用于图像边缘较 为清晰、容易获取的图像。为达到一个理想的效果，一般基于边缘的兴趣点提取 首先应对图像进行高斯平滑，接着使用经典的兴趣点检测算法发现兴趣点，然后 用兴趣点的测度值作为图像特征进行匹配。这种方法由于是基于边缘上的一些特 殊点，但经过处理后对噪声和点位置的变化也较为敏感。 ( 2 ) 基于区域的形状特征提取的主要思路是通过图像分割技术提取出图像中 感兴趣的物体，依靠区域内像素的颜色分布信息提取图像特征，适合于区域能够 较为准确地分割出来、区域内颜色分布较为均匀的图像。近年来，基于区域的图 像检索方法已经成为基于内容的图像检索的一大研究热点。 基于三种特征检索方法的比较 目前绝大多数的图像检索系统都使用颜色特征，纹理和形状特征使用得相对 较少。颜色特征适用于色彩较为丰富的图像，如风景类图像，使用颜色特征的检 索常可以得到颜色相似的图像。纹理特征则较适合于物体和背景不易分割的图 像，单纯使用纹理特征的检索并不能总是得到纹理相同的图像，但除非数据库中 包含许多含有主要纹理的图像。形状特征由于不容易提取，一般只对物体形状易 于识别的图像较为适合，基于形状的检索常可能检索到意外的结果，因此用得相 对较少。袁2 1 列出了不同特征的提取方法及其不足。实际应用中，为提高检索 准确性，提出将不同特征组合到一起进行检索，如综合颜色和纹理的检索、综合 7 形状和纹理的检索等。 2 2 2 特征相似度匹配 特征的提取及其不足 表2 1 特征相似度匹配是图像检索的另一个关键技术，不同的特征应该采用不同的 度量方法。在检索的过程中，根据系统相似性比较的算法计算检索样本图像的特 征与数据特征库中所对应的每种特征的相似程度，也就是计算出来的距离，把所 得距离结果由小到大排列后得到个图像列表返回给用户。我们可以通过人机交 互，对检索的结果进一步求精，不断缩小检索结果集合的范围。相似性匹配的过 程常常要利用特征向量之间的距离函数来进行相似性度量，近似得到数据库所认 知的排序。常用的距离度量公式有如下几种( 公式2 1 中x ，y 代表两幅图像对应 的特征向量，五，y 代表特征分量，n 为特征向量的维数) ： 厂m a i l i l a t t a n 距离d ( x ，”2 善 i 茏一y ，i 。 m i n l ( 1 ( 。w s k yg 巨n d ( x ，y ) = ( 善 j 五一y ；i ) “7 l 酬d e 枷离d ( x ，洲砉( 以| ) 2 ) “2 加铀一n 距离。c x ，渊薯剁置- y l1 ) 2 ， c h e b y s h e v 距离n ( x ，y ) = m a xl 麓一y i i j - t lm a h a l a n o b 话距离( a 是，方芋矩阵) ld ( x ，y ) 2 善善( 耻) ，r ) 懈( * y ，) i 直方图交用于以直方! 为特征向量的相似置计算 ld ( x ，y ) - ( 善曲( x i 峭) ) ，善魁 其中，m a n h a t t a n 距离计算简单，效果也较好，被广泛采用。加权e u c l i d e a n 距离考虑了不同分量的重要性，也较为常用。m a h a l a n o b i s 距离考虑了样品的统 计特性和样品之间的相关性，在聚类分析中经常用到。当采用综合特征进行检索 时，需要对各特征向量进行归一化，以使得综合特征的各特征向量在相似距离计 算中地位相同。 2 2 3 结合相关反馈的检索 c b i r 的其中一个关键的问题是系统提取出的图像低层物理特征难以表达用 户查询的高层语义内容。为了弥补它们之间的差距，相关反馈( r e l e v a n c ef e e d b a c k ) 技术是一个重要的突破，也是一个不可缺少的内容。相关反馈是在图像检索系统 中的一种指导性学习的技术，它是用于提高检索系统的识别能力。引入到图像检 索中利用人机交互，让系统根据用户提交的反馈信息，从而对内部检索参数进行 调整达到优化检索结果，并返回给用户新的检索结果。 9 2 3c b i r 图像检索性能改进的方法 对于通用传统型的c b i r 图像检索系统来说，系统多使用颜色、纹理和形状 等常用的低层物理特征。这些特征的通用性使它们对于高层语义描述的能力受到 影响，检索性能要低于专门为某一类图像适用的特别的图像物理特征。而且系统 提取出的图像低层物理特征难以表达用户查询的高层语义内容。 为改进c b i r 系统的检索性能，我们一般在系统中引入异种特征查询 ( c o m p o 茧t eq u e r y ) 和相关反馈( r e l e v a n c ef e e d b a c k ) 技术。 2 3 1 异种特征的组合查询 因为不同的图像特征有各自的特征向量表示方法和相似性比较算法，于是基 于内容的图像检索通常是采用单独的一种特征来进行的。但是单个低层的物理特 征与高层语义内容之间可能存在相当的理解误差，某些语义上完全不相关的图像 的特征向量在某个特征空间中的位置却十分接近，这样在我们人脑中看起来极不 相似的图像基于这个特征却会得到很好的相似性距离测度。当单个特征不能够为 检索提供足够的区别性信息时，系统会给出一些错误的检索结果。 使用多种特征空间进行维合查询可以使上述情况有所改善。这是因为，两个 语义上不相关的图像虽然会在某个特征上有好的相似性测度，但同时在其它特征 上也取得好的相似性测试的几率是相当小的。另外，异种特征的组合查询使用户 可以更灵活、更有效地表达他们的查询要求。比如，用户可能希望查找在颜色和 形状上都与查询示例相似的图像，这时用户就可以向系统提交一个组合查询。 在我们的c b i r 系统中一般使用线性组合的算法来合并多个检索的结果序 列。它通过对各种特征的相似性量度进行加权的线性组合运算来生成综合的相似 性量度，进而得到一个合并了的距离量度。 合并前要先对单个特征的相似性测试进行特征间归一化( n t e r - f e a t u r e n o r m a l i z a t i o n ) 处理。这是因为不同特征的相似性测度算法得出的相似性测度的 值域不一定相同。某些特征的相似性测度( 如颜色直方图) 的值域为区间【o ，1 1 ， 而另一些特征( 如欧氏距离) 则不是。因此，我们必须统一各种特征的相似性量 度结果的取值范围进行组合。在归一化处理后，在组合查询中各特征的地位客观 上是平等的。于是，我们可以进步为各特征分配不同的权重值，称为特征问加 1 0 权( i n t e r - f e a t u r ew e i g h t s ) a 不同特征的检索性能一般都有差别。由各种实验的统计所得，在一般情况下 基于颜色特征的相似比较会比基于纹理或形状的比较有更高的查准率。当然，各 种特征的检索能力的差别可能最终取决于它们应用的领域上。而且，提交查询的 用户对各种特征也可能有不同的重视程度。例如，一个基于颜色和形状的组合查 询，用户可能更关心颜色特征的信息，在此前提下，用户希望对形状特征进行一 些考虑。在整体的考虑上，颜色的份量可能达到7 0 ，而形状只占3 0 。这时， 用户可以指定颜色特征的权重为7 而形状特征的权重为3 。可见，特征间加权可 以使用户更精确地描述其信息需求。 我们通常使用两种或以上不同的物理特征进行异种特征的组合。比如将颜色 直方图、主颜色、形状和纹理等这几种特征以相同的权重值进行等权组合。另外 我们还可以根据先验的知识与模型对于不同的图像类别，选出对该类图像的识别 率最大的若干个特征作为该类图像的较优比较特征，将其进行组合，并按照它们 的查准率的比值来分配其权重值。实验证明，无论对简单图像或复杂图像用2 个较优特征的加权组合方法则能够明显地改善对复杂图像的检索，查准率也略有 提高。 2 3 2 利用相关反馈改善查询效果 正如前面所说，c b i r 的其中一个关键的问题是系统提取出的图像低层物理 特征难以表达用户查询的高层语义内容。目前，基于内容的图像检索技术中所抽 取的图像特征基本上是图像的底层视觉特征，它们与图像的实际语义是脱离的， 底层视觉特征目前尚无能力辨别出图像中所包含的物体。因此，无论采用何种特 征，无论使用何种距离测度，最终决定两幅图像是否相似还取决于实际用户。我 们认为：基于内容的图像检索系统应该尽可能地做到以用户为中心，而不是以计 算机为中心。另外，由于侧重点的不同，不同的用户对图像的相似性的判断也存 在不同的标准。为了弥补它们之间的差距，需要研究如何使系统自动适应这种特 定的需求，从而实现更好的查询效果。相关反馈是提高系统查询效果的一种强有 力的方法。相关反馈是在图像检索系统中的一种指导性学习的技术，它是用于提 高检索系统的识别能力。引入到图像检索中利用人机交互，让系统根据用户提交 的反馈信息，从而对内部检索参数进行调整达到优化检索结果，并返回给用户新 的检索结果。 相关反馈的目标是从用户与查询系统的实际交互过程中进行学习，发现并捕 1 1 捉用户的实际查询意图，并以此修正系统的查询策略，从而得到与用户实际需求 尽可能相吻合的查询结果。由于相关反馈可以实时地修改系统的查询策略，从而 为图像检索系统增加了自适应功能。 在向量模型中，查询都可以表达为特征空间中的向量，也就是点的形式，称 为查询点。假设每次有用户进行查询时，他心目中都有一个理想的查询点恰好能 够准确地表达他的信息需求，称之为理想查询点。但实际上，用户必须借助某些 其他对象或手段才能够表达他的查询请求，比如输入查询文本或者提交例子图像 等，这些查询文本或例子图像有特征空间中对应的点就是查询点。查询点应该比 较接近理想查询点，但在一般情况下两者还是有明显差距的。对于采用向量空间 模型的系统，相关反馈技术一般采取两种策略：( 1 ) 移动向量优化算法；( 2 ) 特 征权重调整算法。 移动向量优化算法的本质就是根据用户反馈信息来调整查询点，使之更加接 近理想查询点，再用调整后的查询点去重新计算检索结果。在每次相关反馈中， 用户都会提交一些他所认为的与查询相关或者不相关的例子，称为反馈正例与反 馈负例。查询向量优化算法的具体做法是将移动查询点，使之更加靠近反馈正例 理想查询点。大量实验表明，采用优化后的查询点重新计算的检索结果优于前一 次的查询结果。 特征权重调整算法的中心思想也是非常简单直观的。以图像检索为例，每幅 图像都对应着特征空间中的一个n 维特征向量，而检索开始时特征空问每一维 度上的权重都是相等的。在相关反馈中，检查所有反馈正例和负例的特征向量： 假设所有反馈正例在某个维度上的值相关很大，则说明这个维度和用户查询的关 系并不密切，因此可以降低该维度上的权重；反之，如果所有正例在某个维度上 的值非常接近，则说明该很好地反映了查询中的某个特点，因此应该提高该维度 的权重。 2 4 基于相关反馈的已有c b i r 成果介绍 b a r t o l i n i 等人 5 】对系统积累的相关反馈历史数据的矛q 用问题进行了研究，提 出了f e e d b a c kb y p a s s 系统，该系统在用户提交的检索样本图像与检索中通过相 关反馈得到的“最优”参数之间建立映射关系，并把这种映射记录入历史数据库 中。当新的检索进行时，系统首先用新检索样本图像在历史数据库中进行相似匹 配，得到与其最相似的样本所对应的检索参数，然后按照这些“最优”参数在图 1 2 像数据库中进行检索，以提高检索效率。该方法的问题在于随着用户反馈数量的 不断增多，把新检索样本提交到历史数据库中进行匹配本身就是一个图像检索过 程，其准确程度不高；另一方面，不同检索提交的样本图像随意性大，相似程度 更小，也影响到匹配的准确性及最优参数的选择，减弱了对检索性能的改进。 p i c h u n t e r 6 系统是由c o x 等开发出来的，它设计用来寻找与用户头脑中构 想的图相似的图像。在实施相关反馈时，数据库中的每幅图都根据其与正图像的 距离进行记分，这样特征空间中向量的相关位置才是有意义的。距离的度量在全 局方式中不受影响。可以赋给每个图像特征描述的分量一个权值，这个权值用于 计算图像间的距离，然后根据用户响应对这些权值进行修改。这样在正图像中具 有最小变化的特征分量就会获得最大权值。也可以根据正图像和所有显示图像的 逆方差的不同进行加权。另一种可供选择的方法就是调节距离度量的方法以产生 正图像间最小的可达相关距离。还能通过结合数据库的层次化聚类以及从用户给 定的样例中得到的新规则的集合论机器学习来执行相关反馈。如果特征空间是低 维的，用相关反馈修改它的多间隔离散化就是可能的。考虑到一个特定的特征， 如颜色，那么基于直方图的匹配将转而有利于用户的相似性观点。该系统的缺点 就是没有考虑负图像所起的作用。 l e e 等人【7 】给出了一个利用用户反馈中隐含的图像的高层语义信息来改进 检索性能的检索系统。该系统初始时把图像数据库中的图像按低层物理特征进行 聚类，并通过各个子簇中心来计算子簇之间的相似度。检索时首先确定检索样本 对应的子簇( 称为目标子簇) ，其它的子簇按与目标子簇的相似度排名，子簇内部 的图像按图像与检索样本之间的“距离”进行排名。为了改进检索效果，该系统 通过用户在相关反馈中给出的正例图像对各个子簇进行“语义”更新。一般认为， 用户给出的反馈图像在语义上具有“一致性”。因此，系统可以根据用户的反馈 对图像子簇进行相应的分割与合并，使得同一个子簇中的图像在语义上相似度越 来越高，而子簇之间的语义相似度越来越低，使得系统的检索性能不断地得到改 善。但是图像的高层语义十分复杂，并且与具体的用户相关。因此，这种对图像 进行语义分类的方法缺乏灵活性。 2 5 本文的改进 从以上可以看出，从如何在相关反馈中提高检索性能这个个核心问题中，已 有的研究提出了多种不同的方案，每一种方案都涉及了一系列的技术。但这些相 关反馈检索算法正如上面所说也有一系列的不足。 本文提出一种基于p c a ( p r i n c i p a lc o m p o n e n ta n a l y s i s ) 主成分分析的方法 的相关反馈算法，这在一定程度上能解决上述的一些不足之处与自己的优点，比 如能动态调整、选取重要而去除次要信息、计算灵活等。该算法结合全局颜色直 方图，分块主色划分等特征，加以相关反馈的人机结合图像检索。众所周知颜色 是描述图像内容的最直接的视觉特征，直方图有统计直观，图像平移、旋转不变 的性质，但用直方图进行图像检索中主要利用的是图像颜色分布的全局特性，没 有利用颜色的空间位置分布特性，因此加上分块主色特征组合查询能使查询准确 率得到提高。 本文基于的p c a 主成分分析的方法结合人机结合的相关反馈技术，结合移 动向量优化算法和特征权重调整算法的动态调整，在图像的特征抽取与匹配算法 上作出了一定的创新，在实验中证明检索性能对比一般传统的相关反馈图像检索 算法有所提高。 1 4 第3 章基于p c a 的相关反馈检索算法 本章主要介绍本文中算法的一些背景理论知识，以及把颜色直方图和区域分 块主色划分的相关子特征，最后介绍运用p c a 的方法实现异种特征的组合查询 和相关反馈算法。 3 1 什么是p e a ( 主成分分析) 本文所提出的算法是基于p c a ( p r i n c i p a lc o m p o n e n ta n a l y s i s ) 主成分分析 的相关反馈算法，因此我们首先对p c a 作一个简单的介绍。 3 1 1p e a 用于减少数据突出重点的基本思想 假设我们进行一次调查，分别以英寸和厘米为单位测量1 0 0 个人的身高。我 们得到了测量身高的两个变量。如果再进行一次研究，调查不同的营养食品对身 高的影响，我们还要同时使用着两种测量方法吗? 不需要。不论是用何种单位测 量的，身高都是一个人的特征。 从这个研究中我们可以了解到研究者可能遇到的一些问题。假如，我们想测 量人们对生活的满意程度。我们设计了一个含有多个项目的满意程度调查表。除 此之外我们还询问：调查对象对他们喜好的满意程度( 第一项) 和追求喜好的强 烈程度( 第二项) 。对这两个问题的回答很有可能是高度相关的。如果两项商度 相关，我们认为这两项是冗余的，将两个变量结合为一个因子。我们可以用散点 图s c a t t e rp l o t 总结两变量之间的关联，拟合一条回归线对两个变量之间的线性 关系进行总结。如果我们可以定义一个近似于散点图中回归线的变量，那么该变 量就抓住了这两个项目中的本质东西。回归线所代表的对象在这个新因子上的数 值就可在以后的数据分析中代表这两个项目的本质。在这个意义上我们就将两个 变量缩小为一个因子，新因子实际上是两变量的线性结合。 上述的例子，将两变量结合成一个因子，准确地描述了因子分析或者主成分 分析的基本思想。如果我们将两变量的例子推广到多个变量，计算变得更为复杂， 但用一个因子来解释两个或多个变量的这种慕本原则仍然一样。 我们在这不对主成分分析的计算作详细的说明，有关计算的过程可在下面我 们对于检索的算法中的具体计算方法中见到。从根本上说，提取主成分相当于对 原变量空间进行最大方差( v a r i m a x ) 旋转。例如散点图中，我们可以将回归线认 为是x 轴经过旋转后近似成为一条回归线。这种旋转称为方差最大化，因为进 行旋转的标准( 目标) 是使新变量( 因子) 的方差( 变异) 最大，而使新变量周 围的方差最小。 当超过两个变量时，我们认为这些变量形成一个空间，正如两个变量形成了 一个平面。存在三个变量时，我们就可以画出一个三维的散点图，我们同样可对 数据拟合一个平面。当超过三个变量时，就只能用散点图表示这些数据了，但将 轴进行旋转使新因子的方差最大的逻辑思想仍然不变。 到现在为止，我们考虑主成分分析作为减少数据的方法，即作为减少变量数 目的方法。那么我们要提取多少个因子呢? 注意到当我们连续地提取因子时，这 些因子所能解释的变异越来越少。判断什么时候停止提取因子根本上依赖于什么 时候仅留下很小的随机变异。这种判断本质上是武断的，但已有了各种不同的指 导方法。 让我们看一看主成分分析的一些标准结果。我1 f 所提取的因子解释的交异是 越来越少。为了简便，我们通常从相关矩阵开始，假设矩阵中所有变量的方差都 为1 ，o 。因此矩阵总方差就等于变量的个数。例如，如果我们有1 0 个变量，每个 变量的方差都为1 o ，那么可被提取的潜在的变异就等于1 0 。假如在刚才提到的 满意度研究中，我们用1 0 个项目测量家庭与工作的各个方面的满意程度。被各 个因子所解释的方差可总结如下： 主成分分析 表3 1 1 6 我们从第二栏中特征值可以知道逐次提取的新因子解释的方差。在第三栏 中，这些值用总的变异( 在本例中为1 0 ) 的百分比来表示。我们可以看到，因 子1 解释了6 1 f 拘方差，因子2 解释1 8 等等。与预想的一致，特征值之和等 于变量数。第三栏列出了提取的累计方差。因子提取的方差称为特征值。这个名 称是由所涉及的计算而得来的。 由于我们计算出了每个因子提取方差的大小，我们就可以回到要保留多少个 因子的问题上了。正如上文提到的，这个判定是武断的。但存在着一些常用的指 导方法，实际中效果也很好。 我们可以只保留特征值大于1 的因子。本质上这好比说，除非因子提取的特 征值至少要与原变量提取的一样多，我们就舍弃掉。这个标准是由k a i s e r 于1 9 6 0 年提出的，也是最常用的一种方法。上例中使用这个准则，只保留2 个因子