（计算机系统结构专业论文）基于内容的图像索引和浏览算法研究.pdf

硕士学位论文 摘要 随着互联网与多媒体技术的迅猛发展，数据信息也飞速增长，这使得图像检 索技术倍受关注。基于内容的图像检索直接利用图像的视觉特征进行检索，能有 效地提高检索的速度和效率，为图像检索的应用提供了更为广阔的前景。而高维 数据索引结构、检索结果的组织及浏览模式作为图像检索中的重要技术，更是成 为了基于内容的图像检索领域中的研究热点。 高维索引机制是大规模图像库检索达到实时性要求的关键技术，能够有效地 提高相似性检索的查询性能。虽然已经提出了很多高维数据索引结构，但是大部 分索引结构在数据维数较高时。性能会急剧下降。针对高维数据索引结构的研究 现状，本文在对高维索引结构进行深入研究的基础上，运用主成分分析中第一主 成分方差最大的统计特性，提出一种基于主成分的索引结构：p 2 t r e e 。算法首先 对数据集进行主成分分析，然后通过逐步聚类来分割数据集并建立索引树；查询 时，综合运用三角不等式性质及主成分来过滤数据空间。从理论及实验上证明了 该算法可以有效地减少距离计算的次数，具有较好的相似性查询性能，在一定程 度上克服了维数危机。 目前的图像搜索引擎大多运用基于文本的检索方式，检索返回的结果，采用 的是基于排序的浏览方式。由于这种浏览方式忽略了图像本身的视觉特征，使得 检索返回的图像集虽然丰富却很杂乱，不便于用户进行浏览和筛选。针对目i j 图 像搜索引擎的浏览方式存在的不足，本文结合信息可视化技术，提出一种基于近 邻可视的图像浏览算法，该算法综合了图像的语义及视觉特征，将搜索返回的图 像集，依掘图像的视觉特征相似度进行组织。此外，为降低计算时间，提高相似 性搜索的性能，提出一种基于关键维的近邻搜索算法。实验显示文中提出的图像 浏览方式，不仅能从一定程度上克服语义鸿沟的问题，也能加强系统与用户之间 的互动，方便用户更高效更自然的对检索结果进行浏览。 关键词：图像检索：高维索引；图像浏览：主成分；可视化 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 t e r n e ta n dm u l t i m e d i at e c h n o l o g y , t h ea m o u n t o fd i g i t a li n f o r m a t i o ni si n c r e a s i n gr a p i d l y t h e r e f o r e ，r e s e a r c ho ni m a g er e t r i e v a li s a t t r a c t i n gm o r ea n dm o r ea t t e n t i o n c o n t e n t b a s e di m a g er e t r i e v a lp e r f o r mr e t r i e v a l a c c o r d i n gt ot h ev i s u a lf e a t u r eo fi m a g e s ，c a ns u p p o r ti m a g er e t r i e v a le f f i c i e n t l y , i t h a sb e c o m ea ni m p o r t a n tt o p i ci nm u l t i m e d i ar e t r i e v a lf i e l d s h i g h - d i m e n s i o n a ld a t a s p a c ei n d e x i n gs c h e m e ，o r g a n i z i n ga n db r o w s i n go ft h er e t r i e v a lr e s u l t sh a v eb e c o m e t h eh o t s p o ti nc o n t e n t - b a s e di m a g er e t r i e v a lf i e l d s e f f i c i e n th i g h - d i m e n s i o n a li n d e x i n gs c h e m ei sr e q u i r e df o rr e a lt i m er e t r i e v a li n l a r g e s c a l ei m a g ed a t a b a s e m a n yi n d e xs t r u c t u r e sh a v eb e e np r o p o s e dt os o l v et h i s d i f f i c u l tp r o b l e m ，b u ta st h ed i m e n s i o n a l i t yi n c r e a s i n g ，t h eq u e r yp e r f o r m a n c eo f m o s ti n d e xs t r u c t u r e sw i l ls u f f e rg r e a t l y b ys y s t e m a t i c a l l ya n a l y z i n ge x i s t i n g h i g h d i m e n s i o n a li n d e x i n gt e c h n i q u e sa n dr e l e v a n ta l g o r i t h m s ，w em a k ef u l lu s eo f t h es t a t i s t i cc h a r a c t e r i s t i co ft h ef i r s tp r i n c i p a lc o m p o n e n tt op r u n ed a t as p a c e ，a n d p r o p o s e an o v e l i n d e xs t r u c t u r e ，c a l l e dp 2 t r e e f i r s t l y ，w ea p p l yp r i n c i p a l c o m p o n e n ta n a l y s i so no r i g i n a ld a t as p a c e ，t h e nu s et o p - d o w nc l u s t e r i n gs c h e m et o r e c u r s i v e l yd e c o m p o s e t h e d a t a s e t ，c o m b i n et r i a n g l ei n e q u a t i o np r o p e r t y a n d p r i n c i p a lc o m p o n e n tt op r u n ed a t as p a c ew h e nq u e r y t h ee x p e r i m e n tr e s u l t ss h o w t h a tt h ep r o p o s e di n d e xs t r u c t u r eb a s e do np r i n c i p a lc o m p o n e n th a sg o o de f f i c i e n c y f o r r e d u c i n g t h et i m e so fd i s t a n c ec a l c u l a t i o n ，c a n s u p p o r ts i m i l a r i t yq u e r y e f f e c t i v e l y m o s to fe x i s t i n gi m a g es e a r c he n g i n e sa r et e x t b a s e dr e t r i e v a lm o d e l ，a n d i m a g es e a r c hr e s u l t sb r o w s i n gi sr a n k i n g b a s e dl i s tp r e s e n t a t i o n b e c a u s et h i sm o d e l i g n o r e sv i s u a l - f e a t u r eo fi m a g e ，i ti st i m e - c o n s u m i n gp r o c e s s f o ru s e r st of i n d i m a g e so fi n t e r e s ti nr e t u r n e di m a g ec o l l e c t i o n t h i sp a p e re x p l o r e st h ep r o b l e mo f b r o w s i n gw e bi m a g e s e a r c h r e s u l t s ，a p p l i e s i n f o r m a t i o nr e s u l tv i s u a l i z a t i o n t e c h n i q u e ，p r o p o s e san o v e li m a g eb r o w s i n ga l g o r i t h mb a s e do nn e a r e s tn e i g h b o r v i s u a l i z a t i o n t h ea l g o r i t h mc o m b i n e sm e t h o d so fs e m a n t i c - b a s e da n dv i s u a l b a s e d r e t r i e v a l ，a n a l y s e sr e t r i e v a lr e s u l t so fi m a g es e a r c he n g i n ea n do r g a n i z e st h er e s u l t s b a s e do nv i s u a ls i m i l a r i t y an e a r e s tn e i g h b o rs e a r c ha l g o r i t h mb a s e do nk e y i n d e xi s p r o p o s e di nt h i sp a p e r ，w h i c hc a nb eu s e dt oi m p r o v et h ep e r f o r m a n c eo fs i m i l a r i t y s e a r c h e x p e r i m e n t a lr e s u l t ss h o wt h ev a l i d i t yo fa l g o r i t h m s ，i t c a ne n h a n c et h e m u t u a l i t yo fi m a g er e t r i e v a ls y s t e ma n du s e r ，c a nh e l pu s e rt oe x p l o r ei m a g es e a r c h r e s u l t sm o r en a t u r a l l ya n de f f i c i e n t l y k e yw o r d s ：i m a g er e t r i e v a l ；h i g h - d i m e n s i o n a li n d e x ；i m a g eb r o w s e ；p r i n c i p a l c o m p o n e n t ；v i s u a l i z a t i o n i 插图索引 2 1 典型的c b i r 系统4 2 2k - d t r e e ，。1 2 2 3r t r e e 1 3 2 4s s t r e c 1 3 2 5 三角不等式性质1 4 2 6b k t r e e 1 5 2 7v p t r e e 1 5 2 8m t r e e 1 6 3 1 主成分分析2 1 4 1p 2 t r e e 的结构3 2 4 2 建树算法3 3 4 3 插入算法一3 4 4 4k n n 查询半径设置3 5 4 5k n n 查询算法3 6 4 6 范围查询3 6 4 7 性能分析距离计算次数3 7 4 8 性能分析运行时间一3 8 5 1 基于近邻可视的图像浏览方式4 4 5 2g o o g l e 捡索结果4 7 5 3 聚类分析检索结果4 7 5 4 基于近邻的浏览方式4 8 5 5 算法比较4 9 i v 图图图图图图图图图图图图图图图图图图图图图图 附表索引 表4 1m t r e ev sm 4 - t r e ev sm t r e e ：距离计算次数3 8 表4 。2m t r e ev sm 4 - t r e ev sm + - t r e e ：运行时1 日j ( m s ) 3 9 表4 3c + t r e ev sc t r e ev sp 2 t r e e ：距离计算次数3 9 表4 4c + t r e ev sc t r e ev sp 2 - t r e e ：运行时间( m s ) 3 9 表4 5k e y i n d e xv sp r i n c i p a lc o m p o n e n t 4 0 v 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的 研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或 集体己经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均 已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。 作者签名：岛南 r 期。砷年，肘口日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入有关数据库进行 检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在 年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“”) 作者签名：内 毛 7 ) 剔程每劬饭彳移。弧 同期：p - 7 年，月；。同 开期：0 钿7 年，月多口只 颈十学位论文 1 1 研究背景及意义 第1 章绪论 近年来，随着计算机通信技术的飞速发展，尤其是存储技术的进步和因特网 的日益普及，全世界信息资源的容量j 下以惊人的速度增长，这些资源不仅有文本 数据，更包含了大量的声音、图像、视频等多媒体信息。图像作为一种重要的信 息载体，具有内容丰富、形象直观等特点，是表达信息的一种重要方式。由于图 像的数据量大，信息丰富，因此，如何更好的对图像数据进行组织、分类和检索， 己成为信息检索领域中的关键问题。 图像检索经历了两个发展阶段。第一个阶段是基于文本的检索，主要是把关 键字、标题、附加描述信息等图像标注作为索引，对图像的检索实质上是对标注 进行文本信息匹配来获取检索结果。这种方法的缺陷在于不能充分体现图像丰富 的内容和图像中对象之闯的关系，此外，用文本对图像进行描述存在着不充分性 和主观性。第二个阶段是基于图像视觉特征的检索。考虑到文本检索的局限性， 人们一直在探索更加有效的图像检索方法。基于内容的图像检索方法 ( 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 ) 则是利用图像的颜色、纹理、形状等低层 视觉特征束进行图像的检索i t - 3 】。由于视觉特征可以依据特征提取算法由计算机 自动提取，不仅节约了手工标注所需要的人力，也避免了因为主观性带来的偏差。 目i j i ，基于内容的检索技术已成为图像检索技术研究的热点，它具有传统的文本 检索技术无法比拟的优越性。 基于内容的图像检索方法利用图像本身的可视化特征进行索引和检索，已经 取得了很大发展并具有很好的前景，目前主要面临着如下问题： 1 ) 低层特征的有效性：图像所包含的信息极其丰富，而现有的低层视觉特征 通常不能真实地表征图像内容。因此需要进一步研究如何有效地提取反映图像内 容且具有旋转、平移、放缩不变性的低层视觉特征。 2 ) 索引机制：图像视觉特征通常由高维向量表示，基于内容的图像检索则是 在高维数掘空间中的搜索。在大容量图像库中如何提高搜索效率已成为亟待解决 的问题。目前提出的众多索引结构，如r t r e e i4 1 ，s s t r e e ! ”，m t r e e t 6 】等，在低 维空间中性能较好，但在高维数据空间中，性能急剧下降，甚至不如顺序查询。 因此，面向大容量图像库的检索需要更有效的高维索引机制束加速检索过程，以 满足实时性的要求。 埔r 内窖的图像索引和谢览算法研究 3 1 语义间隔：图像的内容实质上可以包含两个层次：视觉特征和语义特征， 现有的文本检索方法主要侧重于对图像内容的语义描述，而基于视觉特征的方法 则侧重于图像内容的特征提取。用户检索通常所表达的是具有高层语义的查询概 念，若检索系统仅使用低层可视化特征来表征图像，则低层的图像特征与高层语 义之间就会存在巨大的语义间隔，因此应该将二者结合起来取长补短。二者虽侧 重不同但却可以相互补充，将两个层次的内容综合运用才能获得较好结果。 4 1 用户查询接口的不足：理想的图像检索系统中，人是主动的，用户的查询 接口能提供丰富的交互能力，且直观易用。但是目前众多的检索系统在与用户的 交互上存在着很多的不足：检索界面单一、忽略人与系统的交互、检索结果的表 达方式每次提供给用户的信息也非常有限，不利于检索的整体浏览。已有研究显 示，可视化、智能化的检索技术可以有效地提高检索的效率，利用可视化技术对 检索结果进行有效的梳理可以帮助用户从中更快的发现自己所需的信息。 1 2 研究目标及主要贡献 针对基于内容的图像检索的研究现状和存在的主要问题，本文对高维索引机 制和检索结果的浏览方式进行了深入研究分析，主要研究内容包括： 1 1 深入分析了图像的高维数据特征及目前的高维索引结构。考虑到对数据集 进行主成分分析之后，第一主成分方差最大的统计特性，提出了基于主成分的过 滤方式，同时，结合分层聚类建树机制，提出一种基于主成分的索引算法：p 2 t r e e 。 文章从理论及实验上证明了所提出的索引结构，对数据空间有较好的删减效果， 可以有效地减少距离计算的次数，降低c p u 的开销，从而具有较好的相似性检 索性能，同时，实验结果也说明了数据的方差特性对于索引的性能有较大的影响。 2 ) 介绍了信息检索可视化技术及其在图像检索领域中的一些应用；讨论了已 有的一些图像浏览方式。针对现有图像搜索引擎的不足，充分结合信息检索可视 化技术及当前的基于文本的图像搜索引擎技术，将通过搜索引擎检索返回的图像 集依据其视觉特征的相似性，重新进行组织，在此基础上提出一种基于近邻可视 的图像浏览算法。算法结合了图像的语义及视觉特征，提供给用户的浏览结果更 便于用户进行浏览及筛选。此外，为降低计算时间，提出了种基于关键维的近 邻搜索算法。实验证明了所提出的算法具有较好的性能。 1 3 论文结构 本文的结构安排如下： 第一章：根据基于内容的图像检索技术的研究现状，提出了本课题的研究背 景及意义，并提出了本文的研究目标和主要贡献。 第二章：描述了基于内容的图像检索关键技术。并对一些相关技术及知识进 行了研究分析：描述了典型的图像特征提取算法；详细介绍了高维数据和高维索 引技术的特点；对现有的高维索引技术进行了综述；介绍了信息可视化相关技术 及其在图像检索领域中的应用，并对现有的一些图像浏览方式进行了介绍。 第三章：详细介绍了主成分分析及聚类分析算法。 第四章；提出一种基于主成分的高维空间索引算法，从理论上证明了算法的 有效性；最后用实验说明算法的可行性，通过与相关算法进行比较分析，证明了 该算法具有较好的性能。 第五章：提出一种基于近邻可视的图像浏览方式，并和现有的一些浏览方式 进行了分析及比较，用实验结果证明了算法的可行性。 最后对论文工作进行了总结，提出了进一步工作展望。 3 端丁内容的酗像索引和溺览算法研究 第2 章相关研究 2 1 基于内容的图像检索关键技术 c b i r 是一门交叉学科，涉及了图像处理、模式识别、人工智能、神经网络 及数据库技术等多种学科，包括特征提取、相似性度量、高维索引，相关反馈、 人机交互、检索性能评价等环节，这些环节对检索系统的性能有着重要的影响。 一个典型的基于内容的图像检索系统的基本组成如图2 1 所示。 吵器圃 ，、，7 、 掣 图2 1 典型的c b i r 系统 如图所示，上述的每个环节都在图像检索系统中起着十分重要的作用，针对 本文的研究内容，下面对其中的一些关键技术进行分析。 2 2 特征提取 c b i r 利用图像的颜色、纹理、形状等视觉特征进行检索，特征提取算法的 研究和应用已经得到了长足的发展【2 3 l 。图像特征的提取与表达是图像检索技术 的基础，图像的内容可以分为两类：低层视觉内容和高层语义内容。低层视觉内 容主要包括颜色、纹理、形状、空间关系等特征，可以通过特征提取获得，而高 层语义内容则包含图像对应的语义信息，需要对图像中目标进行检测、识别和解 释，往往要借助人类的知识推理以及人机交互的方式获得。本节主要介绍的是图 像低层视觉特征的提取，如何从图像中提取有效的视觉特征是影响图像检索系统 性能的一个重要方面。 1 ) 颜色特征：颜色特征是在基于内容的图像检索中最早被使用也是最广泛 使用的视觉特征，主要原因在于颜色特征的定义比较明确，特征提取方法比较简 单，并且颜色特征能较好的体现图像中所包含的物体或场景。此外，与其他的视 觉特征相比，颜色特征对图像本身的尺寸、方向、视角的依赖性较小。目前，在 颜色特征提取方面，常用的有颜色直方图、颜色矩、颜色集以及颜色聚合向量等 一些方法。这些特征提取方法适用于针对图像的颜色进行检索的情况。颜色特征 4 的提取方法存在的主要问题是不能较好的反映图像中的空间信息。 2 ) 纹理特征：纹理特征是一种反映图像中同质现象的视觉特征，不依赖于 图像的颜色和亮度。纹理可以视为某些近似形状的重复分布，它是物体表面共有 的内在特性，例如云彩、树木、砖、织物等都有各自的纹理特征。纹理特征在基 于内容的图像检索中得到了广泛的应用，用户可以通过提交包含有某种纹理的图 像来查找含有相似纹理的其他图像。纹理描述的难点在于它与物体形状之间存在 密切的关系，千变万化的物体形状与嵌套式的分布使纹理的分类变得十分困难。 纹理的建模和分析通常分为以下三类：统计的、频谱的和结构的。纹理统计分析 主要包括t a m u r a 特征、共生矩阵以及自回归纹理模型等；纹理频谱分析主要包 括小波变换等；纹理结构分析假定图像由较小的纹理基元排列而成，多采用句法 分析的方法，由于只适用于规则的结构纹理分析，目酊研究不是十分广泛。这些 纹理特征提取方法适用于对具有明显纹理特征的图像进行检索，对于普通图像需 要结合其他特征共同检索。 3 ) 形状特征：图像的形状不像纹理那么难定义，许多自然的物体都是用形 状来区别的。目标的形状是对图像进行描述和检索的另一个重要特征。与颜色特 征和纹理特征不同，形状特征经常和目标联系在一起，从而形状特征具有一定的 语义含义。形状特征的表达必须以对图像中物体和区域的分割为基础，由于当前 的目标检测和分割技术无法做到准确而鲁棒的自动图像分割，所以，形状特征只 能用于图像中的物体和区域可以直接得到的特殊应用。同时，由于人们对物体形 状的旋转、缩放和平移主观上的不敏感性，所以，提取的形状特征应具有旋转、 缩放和平移不变性，这对形状特征的提取带来了困难。通常束说，形状特征有两 种表示方法，轮廓特征和区域特征。轮廓特征只利用物体的外边界来描述图像中 目标的形状，适用于目标的边缘可以较好的描述目标对象的图像，如傅立叶描述 子、基于内角的形状特征和形状上下文特征等；区域特征则利用图像中目标区域 特征描述目标的形状，适用于通过对目标区域的分析可以获得图像中目标形状信 息的情况，如不变矩等。 4 ) 空间关系特征：上述的颜色、纹理和形状等多种特征反映的都是图像的 整体特征，无法体现图像中所包含的对象的关系。事：实上，图像中对象所在位置 和对象之间的空间关系同样是图像检索中重要的特征。所以，设计出包含空问关 系的图像特征对图像检索有很大帮助。基于图像分割的空间关系特征描述方法是 最近研究的热点。 2 3 高维数据及索引技术 基于内容的图像检索系统中，通过提取图像的颜色、纹理、形状等多方面特 5 恭丁内容的图像索引和浏施算法研究 征来对图像进行描述，通常，我们用向量来表示这些代表着图像的高( 多) 维特征。 高维数据库的应用得到了快速的发展，如图像数据库，生物信息学中的d n a 数据库等。与传统的数据库相比较，高维数据库对数据对象的描述更加复杂，需 要建立合适的索引技术来对其进行组织和管理。 2 3 1 高维数据特点 设一个数据对象的n 个特征值分别为x 。x 2 c - os x 。，由于它们来自同一个对象， 所以应将它们作为整体一起考虑，为此，由它们构成一个n 维特征向量x ， x 一( x 。，x ：，x 。) 7 ，x 是对原对象的一种数学抽象。用其来代表原对象，也是高 维数据的一般模式。 与简单数据相比，高维数据有其自身的特点【7 】： 1 ) 无序性：假设有高维数据的某一特征变量的值分别为x ，y z ，若有x ty t z ， 并不代表对象o 。与对象o ，之| 日j 的相似度要比对象o 。与对象o ，之间的相似度 高，因此无法对高维数据进行常规意义下的排序。 2 ) 稀疏性：假设一个d 维的数据集d 存在于一个超级立方体单元o f o ，1 】d 中， 数据在空间中均匀分布，并且各个维之间是独立的。对一个边长为s 的超级立 方体范围，一个点在这个范围内的概率为s d ，由于s t l ，因此随着维数d 的增大， 这个概率的值会越来越小。也就是说即使在一个很大的范围内很可能连一个点也 不包含。例如当d = 1 0 0 时，一个边长为0 9 5 的超级立方体范围只包含0 5 9 的 数据点，这个超级立方体范围可以位于数据空间0 的任何地方。因此我们得出结 论，在高维空间中，数据点是非常稀疏的。 3 ) 空空间现象：对于币态分稚的数据，一个正态分布可以用期望值和标准差 来表示。数据点与期望值点之间的距离服从高斯分稚，但与期望点的相对方位是 随机选取的。应该注意的是，相对于一个点的可能方向的数目，也是随着维数的 增大而呈指数级的增长，结果是，虽然与中心点之间的距离仍然服从同样的分布， 但数据点之间的距离会随着维数的增大而增加。如果我们考虑数据集的密度函 数，就会发现，虽然可能没有一个点离中心点的距离很近，但在中心点还是会出 现一个最大值。这种在高维空间中在空区域中点的密度可能会很高的现象称为 “空空间现象”。 2 3 2 高维数据查询方式 高维数据的查询通常是相似性查询。与传统数据库的精确匹配不同，传统的 精确查询是找到数据库中与查询对象精确匹配的记录，而相似性查询是找到高维 数据库中与查询对象相似的对象集合。 6 2 3 2 1 相似性度量 高维数据库中主要通过对象之间的距离来衡量两个对象的相似程度。因此， 在高维查询处理中，相似性度量是非常重要的一个课题【引。下面介绍一些较为常 用的距离公式。 1 ) m i n k o w s k y 距离： nl d y ) i 【黔t y 牡( 1 s 九* ) ( 2 1 ) 当九1 时，式2 1 为m a n h a t t a n 距离，d ( x y ) - 善i x l - - y i l ( 2 2 ) 当九一2 时，式2 1 为e u c l i d c a n 距离，d ( ) ( y ) - 【善i x - 一y i l 2 】_ ( 2 3 ) 当九一* 时，式2 1 为m a x i m u m 离，d ( x ，y ) 一m a x ( i x f y i i ) ( 2 4 ) 基于m a n h a t t a n 距离的查询在几何意义上对应的是超立方体，基于m a x i m u m 的查询则是超菱形，我们最常用的是e u c l i d e a n 距离，也称欧氏距离，其查询则 对应了超球体。 2 、加权欧几罩德距离 d ( x ，y ) -隔 ( 2 5 ) 其中w 是各维对应的权值。加权欧几罩德距离考虑了各维具有不同的重要 性。由于通常提取所得的特征向量各维的重要性是不同的，因此，加权欧几罩德 距离应用也很广。 3 ) 加权欧几罩德距离的推广 d ( x ，y ) - ( x y ) a ( x y ) 7( 2 6 ) 其中a 是一个正定对称矩阵。在实际应用中，a 通常是根据向量子空间内 向量的分布计算得到的协方差矩阵。 2 3 2 2 相似性查询 高维数据的查询通常是相似性查询，相似性查询包括下列几种常见的方式： 1 1 点查询( p o i n tq u e r y ) 点查询是最简单的查询类型。对于数据库d b ，查询点q ，相似性度量m ， 其查询表达式为： p o i n t q u e r y ( d b ，q ，m ) t p e d l 目p q ， ( 2 7 ) 点查询和传统的精确查询类似。 7 蕈丁冉容的幽像索引和浏瓷算法研究 2 ) 范围查询( r a n g eq u e r y ) 范围查询是为了获得与被查询对象在某一特定范围内的所有相似对象的集 合。对于查询目标q ，查询范围f ，相似性度量m ，距离d 和数据库d b ，其范围 查询表达式为： r a n g e q u e r y ( d b ，q ，r ，m ) - p c d b v p e p ，d 。q ，q ) r ( 2 8 ) 显然，点查询可以看作范围查询在r - - 0 时的一种特例。如果m 是欧氏距离， 则范围查询的几何意义为以查询点为中心，半径为r 的一个超球体。类似地，i l l 取m a n h a t t a n 距离，则对应了一个超立方体。 范围查询的结果集大小是不确定的，若r 取值太小，结果集可能为空，若取 值太大，则可能返回整个数据集。 3 1 最近邻查询( n e a r e s tn e i g h b o rq u e r y ) 最近邻查询按照近邻原则进行查询，它的返回结果是数据库中离查询对象最 近的一个数据对象。对于查询目标q ，查询范围r ，度量m ，距离d ，其最近邻 查询表达式为： n n q u e r y ( d b ，q ，m ) 一 p d b f v p ，( d b - p ) ，d 。q ，q ) d m ( p ，q ) ( 2 9 ) 当数据库中有多个对象与查询点距离最近时，有两种不同的处理方法：一是 返回所有符合条件的点作为查询结果，二是任选其中一个作为查询结果。 4 ) k 一近邻查询f k n e a r e s tn e i g h b o rq u e r y ) k 近邻查询就是从数据库中选择离查询对象最近的k 个对象。最近邻查询可 以说是k 近邻查询的特例，它指定了返回数据集的大小为1 。对于一个给定的查 询目标q ，查询度量m ，距离d ，其k 最近邻查询表达式为： k n n q u e r y ( i 卫，q ，l 【，m ) p c d i j v p e ( d b - p ) ，d 。 j ，q ) 葺d 。0 ，q ) ，p i p ，0 i r + fi d o ，q ) r ( 2 1 2 ) d ( p ，p ) c ri 此时，就可以将p 所代表的整个数据子集从候选队列中删除。 对于众多的树型索引结构，它们大多利用最小外接矩形或最小外接圆形对数 据空间逐层进行划分形成树中的节点，因此在进行查询时，可通过剪枝路径快速 实现查询，这一方法就称为分支界限技术( b o u n d a n d b r a n c h ) ，其基本思想是： 从根节点开始，计算每个节点与查询向量之间的距离，如发现不可能包含查询结 果的节点，则放弃该节点路径，从而减少访问及计算代价。 下面是几种典型的度量空问索引结构： 1 1b k - t r e e 是由b u r k h a r d 和k e l l e r 在1 9 7 3 年提出的【2 0 1 ，是最早提出的度量 空间树型索引结构。b k - t r e e 的构造方法是从数据集中任意选取元素p 作为索引 1 4 硕士学位论文 树的根节点；对于任意的离散距离b 0 ，将p 周围的数据空问以半径r 的倍数划 分：将每一个与p 的距离在r ，2 r ，n r 的数据对象划分为一个个数掘子集；当数据 集中剩余的对象少于设定的阈值时，停止划分。如此再对数姑子集递归的划分下 去，最终形成树型的索引结构 在进行相似性查找时，b k - t r e e 的查询算法从根节点出发，找到所有满足不 等式d ( p ，q ) 一r s d ( p ，c 0 + i 的子节点b ，递归直到叶子节点。对路径上所有的支点和 叶子节点中的每一个元素都要与查询点q 进行比较将所有满足d ( q ，u ) sr ，u p f 的 数据对象作为结果返回。在查询中，三角不等式性质保证了所有满足查询条件的 点均能被检索到。 一盱、 一 一一 b j 毫 一 f g c 图2 6b k - t r e e 2 ) v p t r e e 是一种基于连续距离函数的二叉平衡树，它的思想在于如何将二 分查找用至只有距离信息的高维度量空间中。类似于k - d t r e e ，v p t r e e 的每一 个节点都相当于对空间的一个划分，所不同的是v p t r e e 使用的是距离信息而不 是坐标信息。具体的构造方法为：选取一个元素p ( v a n t a g e - p o i n t ) 作为根节点，将 剩余的所有元素根据其与p 的距离远近分别放至p 的左右子树中，离p 较近的一 半元素放入p 的左子树中。离p 较远的一半元素放入p 的右子树中：将左右孑树 的临界距离值m 作为节点的附加信息保存；分别对左右子树重复以上过程，直 到节点中的元素数目小于设定的阈值。在v p t r e e 上的查询同样是利用三角不等 式性质减少查询分支。如果d ( q ，p ) + r s m ，则进入p 的左子树；如果d ( q ，p ) + r ，m ， 则进入p 的右予树。 1 23 叼，1 32 业9 堙9 3 0 3 0 4567 圈2 7v p t r e e 幕丁内容的幽像索引和浏览算法研究 m v p t r e e 2 1 l 对v p t r e e 的结构做了少许改变。m v p t r e e 扩展了v p t r e e 的思 想，它将中间节点包含元素的数目由v p t r e e 的一个增加到两个，这样提高了每 个节点的输出能力，降低了树的高度，从而减少了距离函数的计算次数。 3 ) m t r e e 是度量空间中第一个真j 下动态的索引结构，它不仅考虑运用三角不 等式原理来减少距离函数的计算次数，而且考虑了i 0 性能。m t r e e 的结构与 r t r e e 类似，也是基于磁盘页面的、层次化的平衡树结构，所有指向实际数据的 指针都存放在叶子节点上。m t r e e 将向量空间索引结构的动态性与平衡性和度量 空间索引结构的距离定义结合起来，以提高检索的效率。如果给m t r e e 加上坐 标信息，实际上就成为了向量空问中的另一种索引结构：s s t r e e 。 一、 0 i 、 if c 2 ； 嶝：i 弋 、：“：- 一 ；一_ r 一刁、 ，7 i 岛 i 芒。一6 订 一1 一1 一 “1 一 图2 8 m t r e e s l i m t r e e1 2 2 】在m t r e e 的基础上，特别针对索引空间的重叠进行了优化。它 提出了一种基于m s t ( m i n i m a ls p a n n i n gt r e e ) 的节点分裂方法，首先为待分裂节 点中的所有元素构造一棵最小生成树( 边的权值用距离表示) ，选择权值最大的 边进行切分；将剩余的两个连通图之中的元素分别作为两个新节点之中的元素； 最后为每个新节点选取有代表性的元素和最小覆盖半径。文中还提出了一种衡量 度量空间中空间重叠程度的办法，并且利用这种衡量标准给出了一种在节点之间 移动数据项的算法，以期达到降低节点相互重叠程度的目的。 4 ) c l u s t e r t r e e l 2 3 是一棵层次聚类索引树，它的高层节点代表粗聚类，而低层 节点代表细聚类，c l u s t e r t r e e 根据不同层的聚类信息组织数据。 建树时，一开始把整个数据集作为一个类，如果类中拥有的向量数目超过某 一阈值，则对该数据集进行聚类，把该类划分为几个子类，对每个子类重复上述 过程。在c l u s t e r t r e e 中，使用改进的k m e d o i d s 聚类算法进行聚类，以使各个 子聚类拥有的数据量差别不大。 查询时，对一个给定的范围查询q ，从根节点往下，根据各入口中的边界超球 体信息进行剪枝，直到叶子节点。k n n 查询的执行建立在范围查询的基础上，即 先设定一个足够大的查询半径，随着查询的执行逐步缩小查询半径。 c l u s t e r t r e e 中，把待插入数据分为3 类： c l u s t e rp o i n t s ”、“c l o s e b yp o i n t s ”、 “r a n d o mp o i n t s ”。其中前两类数据与某个叶子节点的超球体足够接近，进行插入 后不会对树的结构造成很大的影响，而第三类数据的插入会对树的结构造成大的 影响。对于前两类数据，c l u s t e r t r e e 直接进行插入，插入后如果出现节点溢出， 则进行分裂。而对第三类数据，先不进行插入，而是等到“r a n d o mp o i n t s ”达到一 定数目的时候再一起进行插入。 5 1 a + 一t r e e 2 4 i 是一神动态索引结构。采用的是自顶向下的建树方法，使用聚 类算法束构建索引树，并且在对数据集经过主成分分析之后，针对不同的分层数 据空间，使用不同的数据维进行索引的建立。 在过去的数十年中，人们对索引结构进行了大量的研究，提出了众多索引结 构和算法，它们各有优缺点，尽管这样，到目前为止高维索引结构仍没有得到广 泛的应用，这是因为目l j i 索引结构的性能都受到以下三个因素的制约：1 ) 随着范 围查询半径的增大，查询的时问复杂度迅速上升：2 ) 随着维数的增加，索引结构 的性能也迅速下降；3 ) 无法对在空问中任意分布方式的数据都能取得比较好的性 能。也正因为如此，如何建立有效的高维索引结构以提高检索速度便成了一个非 常具有挑战性的课题。 2 5 可视化信息检索 因特网是一个巨大的、无序的信息海洋，迫切需要各种有效的工具及检索技 术对信息进行浏览和查找，帮助用户更方便地获取需要的信息且不至于迷途。检 索结果可视化通过对检索结果进行分析、处理，用便于用户获取信息的方式来呈 现信息，可以帮助人们更加直观有效地发现所需要的信息，与此同时，还能够增 强用户与系统间的交互作用【2 5 1 。 2 5 1w w w 图像检索现状 近半个世纪以来，计算机信息检索经历了批处理、回溯检索到联机检索等多 个发展阶段。2 0 世纪9 0 年代，因特网的迅速发展与普及为信息检索丌创了新局 面，用户可以在浏览器上直接获取信息而无须知道烦琐的检索命令。然而，用常 规浏览器在因特网上检索信息使人们处于两难的境地：一方面因特网是最大的信 息资源网络，到处都是信息；另一方面，用户所需的信息又很难找到。 我们知道，造成上述问题的原因是因特网上的信息资源是一个无序的集合 体，丰富却杂乱。目i ； f 的w w w 检索系统在与用户