（计算机应用技术专业论文）基于联盟的图像检索优化方法研究与实现.pdf

i 华 中 科 技 大 学 硕 士 学 位 论 文 摘 要 随着大规模数字图像库的出现，传统的依赖于人工标注进行的基于文本的图像 检索技术已经无法满足用户日益增长的要求，基于内容的图像检索技术 (content- based image retrieval cbir) 便应运而生。cbir 的一般做法是提取图像的 某些特征，构成其特征向量，为方便检索，对特征空间建立索引。现在已有一些不 同的建立索引的方法，cm- tree（度量聚类树）是一种较新的方法。 cm- tree 节点中保存了聚类半径及聚类之间距离表，基于度量空间聚类的范围 查询算法利用距离表的信息，根据三角不等式减少距离计算的次数，加快检索的时 间。在处理单个的、小数据量的查询检索上，基于度量聚类检索具有一定的优势。 但是用户在一段时间内提交的查询是具有相当的关联性的，或者极端的来说是重复 性的，如果仍然使用常规的检索方式对度量聚类索引树进行检索，毫无疑问的会多 做许多重复的工作，如对同一张图片进行多次检索，或者对关联性相关很大的图片 也是进行多次的检索。基于联盟对度量聚类检索的优化方法可以解决上述问题。 联盟即主查询和被邀请查询经过一系列的规则所形成的复合查询的技术手段。 联盟的应用层次就在度量聚类树根节点下的第一层导航节点上，在此层次上，主查 询在不同的导航节点上分别和被邀请查询根据一定的规则进行联盟操作，并创建复 合查询，对复合查询进行相应节点上的检索。同时，在主查询和被邀请查询相应的 属性中保留在该节点上的联盟信息，被邀请节点在下一次查询的过程中就不需要对 有联盟信息的节点上进行检索，此操作可避免重复查询，减少查询的次数，提高查 询的效率。基于联盟对度量聚类检索优化，主要在批量数据、实时查询的背景下应 用，实验表明了采用联盟的技术能有效地提高查询的效率，减少重复查询的次数。 关键词：图像检索; 度量聚类; 优化算法; 联盟 ii 华 中 科 技 大 学 硕 士 学 位 论 文 abstract with the emergence of the large- scale digital image database, the traditional reliance on artificial mark the text- based image retrieval technology has been unable to meet the growing requirements of users, so content- based image retrieval technology (content- based image retrieval cbir) appears. generally, cbir extracts certain features of images; its characteristics pose a vector, to facilitate the retrieval of the feature space index. now there are different ways of indexing, cm- tree (clustered metric tree) is a relatively new approach. the nodes of cm- tree preserve the clustered radius and the distance tables of clusters, the range query algorithm based on clustered metric speed up the retrieval time by using the distance tables information, according to the number of calculation reduced by the triangle inequality. the retrieval based on clustered metric have certain advantages when dealing with single query and query of small amount data. however, the queries submitted by users in a certain period of time have considerable relevance, extremely, they re repetitive. much have to be done if conventional retrieval method is still adopted, such as retrieval a same picture repeatedly, or retrieval quite related pictures for many times. the optimization method of clustered metric based on coalition can solve the above problem. coalition is a technical means that a main query and certain invited queries form a new compound query by using some rules. the application layer of coalition is under the root node, the main query invites other queries and conduct coalition operations with certain rules in different navigation nodes of the level, then create a new compound query and retrieval it in the corresponding navigation node. at the same time, the attributes in the main query and the invited queries keep the coalition information, the invited queries need not retrieval in the nodes which keep the coalition information during the next retrieval process, and the operations can avoid retrieving repeatedly, reduce the retrieval times, so it can improve the efficiency of retrieval. the optimization for clustered metric retrieval based on coalition mainly used in the condition of real- time iii 华 中 科 技 大 学 硕 士 学 位 论 文 query context. the experiment proved that the usage of technology can greatly improve the efficiency of retrieval. key words： image retrieval; clustered metric; optimization algorithm; coalition 独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本人完全意识到，本声明的法律结果由本人承担。 学位论文作者签名： 日期： 年 月 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。 本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密 ，在_年解密后适用本授权书。 不保密。 (请在以上方框内打“”) 学位论文作者签名： 指导教师签名： 日期： 年 月 日 日期： 年 月 日 本论文属于 1 华 中 科 技 大 学 硕 士 学 位 论 文 1 绪 论 本章主要介绍课题的研究背景及意义，分析了当前基于内容图像检索系统的研 究现状，阐述自己的主要研究工作，并介绍了章节安排。 1.1 课题背景 随着多媒体技术、网络技术的飞速发展，各种各样的信息爆炸式的增长，导致 人们对信息检索的要求越来越迫切。而在诸多的多媒体信息中，视频图像信息占据 了很大的一部分， 为了使这些庞杂的图像中所包含的信息被有效的访问和利用, 必然 需要一种能够快速而且准确的查找访问图像的技术，即图像的检索技术，与此同时， 随着大规模数字图像库的出现，传统的依赖于人工标注进行的基于文本的图像检索 技术已经无法满足用户日益增长的要求，基于内容的图像检索技术(content- based image retrieval cbir) 便应运而生。 cbir 的一般做法是先提取出图像的特征建立特征数据库，这样就把图像库中的 一个实例转化成了高维向量空间中的一个点，即特征向量。由于图像特征一般都是 高维的矢量数据，所以对图像基于内容的相似检索就转化为对特征数据库中高维数 据的近邻检索。对于大规模的图像数据库而言，其特征数据库也是大规模的。因此 传统的顺序扫描方式必然满足不了用户的检索要求，这就迫切需要有合适的索引机 制来辅助、加速检索的进程1。 1.2 基于内容图像检索的研究概况 近 10 年来，基于内容的图像检索已发展到几十种2，其中国外的 cbir 广为人 知的有以下四种： (1) qbic(query by image content)：ibm 公司 90 年代开发制作的图像和动态景 象检索系统，是第一个基于内容的商业化的图像检索系统。qbic 系统提供了多种的 查询方式，可以利用标准范图检索，用户绘制简图或扫描输入图像进行检索，选择 色彩或结构查询方式，用户输入动态影像片段和前景中运动的对象检索。qbic 对输 2 华 中 科 技 大 学 硕 士 学 位 论 文 入的查询图像进行颜色、纹理、形状等特征进行分析和抽取，然后根据用户选择的 查询方式分别进行不同的处理3 4。 (2) virage：virage 有限公司开发的基于内容的图像检索引擎，同 qbic 系统一 样，它也支持基于色彩、颜色布局、纹理和结构等视觉特征的图像检索。jerry 等人 还进一步提出了图像管理的一个开放式框架，将视觉特征分为通用特征（如颜色、 纹理和形状）和领域相关特征（如用于人脸识别和癌细胞检测等）两类。 virage 公司的 vir（visual information retrieval）图像引擎提供了四种可视属性 检索（颜色、成分、纹理和形状）。每种属性被赋予 0 到 10 的权值。通过颜色特性 检索是最简单明了的，该软件对选出的基础图像的色调、色彩以及饱和度进行分析， 然后在图像库中查找与这些颜色属性最接近的图像5。 (3) photobook：美国麻省理工学院的多媒体实验室所开发，用于图像查询和浏览 的交互式工具。它由 3 个子系统组成，分别负责提取形状、纹理、人脸特征，用户 就可以分别在这 3 个子系统中根据相应的特征来进行查找。picard 等人提出了把用 户加入到图像注注释和检索过程中的思想。同时由于人的感知是主观的，他们又提 出了“模型集合”来结合人的因素。这种方法对于交互式图像注释来说非常有效67。 (4) visualseek：基于视觉特征的搜索引擎，由哥伦比亚大学开发的，系统的主 要技术特点是采用了图像区域之间空间关系的视觉特征。webseek 是一种面向 www 的文本或图像搜索引擎。这两个检索系统都是由哥伦比亚大学开发的。它们 的主要特点是采用了图像区域之间空间关系和从压缩域中提取的视觉特征，系统所 采用的视觉特征是利用颜色集和基于小波变换的纹理特征。 visualseek 同时支持基 于视觉特征的查询和基于空间关系的查询。webseek 包括三个主要模块：图像/视 频采集模块，主题分类和索引模块，查找、浏览和检索模块。 相对于其它的多媒体检索系统，visualseek 的优点在于：高效的 web 图像信 息检索，采用了先进的特征抽取技术，用户界面强大，操作简单，查询途径丰富， 输出画面生动且支持用户直接下载信息。而 webseek 本身就是一个独立的万维网 可视化编程工具，已经对 650000 幅图像和 10000 个影象片段进行了编目，用户可 以使用目录浏览和特征检索方式进行图像检索8。 与此同时国内的 cbir 系统的发展如下： (1) 基于内容的原型系统：清华大学研制，基于 internet 上静态图像检索系统。 3 华 中 科 技 大 学 硕 士 学 位 论 文 该系统能在 internet/intranet环境下，通过友好的人- 机界面，以颜色、纹理等图像特 征或样本图像检索图像。 (2) 基于内容的商标图像检索系统：云南大学信息学院设计开发。 (3) 基于特征的多媒体信息检索系统：中国科学院计算技术研究所和北京图书馆 联合开发。该系统实现了按照图像的纹理、颜色、形状等特征对图像信息进行检索 的功能；同时能对中文信息进行全文检索，且提供了跨平台的客户端检索910 。 从上述的研究现状分析，基于内容的图像检索技术主要应用在专业图库中，对完 全自动化和智能化的检索要求还没有达到。针对海量数据的特点，如何快速地检索 图像，更好的满足用户的检索需求等问题还需解决。 1.3 主要研究工作 本课题来源于校基金项目：基于语义的智能中文多媒体搜索引擎。资助编号为： 2006z001b。本系统是基于度量聚类的多媒体分布式检索系统，实现了一个基于 mpeg- 7 标准的分布式检索系统。在本图像检索系统中，通过提取图像的低层视觉特 征，建立特征库，并且基于这些特征建立索引。在用户检索过程中，通过提取用户 提供的示例图像特征，采用顺序扫描算法遍历特征库进行相似度匹配，将距离最近 的 k 幅图像传给用户。在图像库不大的情况下，其检索速度是可以被接受的，但是 随着图像库的增大，尤其是面对大型网络多媒体数据库时，这种算法所付出的时间 代价是难以想象的，也是让人无法忍受的。鉴于此，本文通过介绍多媒体数据库高 维特征聚类与索引，致力于研究一种基于联盟对度量聚类检索的优化算法，从而实 现了对大量的具有实时需求的查询进行快速有效的多媒体信息检索。在应用项目组 其他成员的研究成果的基础上，实现了基于联盟的对度量聚类检索的优化。 基于此，本课题主要研究内容包括： 1 提出了基于联盟对度量聚类检索的优化算法。 分析度量聚类检索的查询算法， 肯定度量聚类检索算法的有效性的同时指出了其算法的应用局限性，并对所提出的 算法的局限性和缺陷加以改进。 2对基于联盟对度量聚类检索的优化算法进行设计，选择检索时间和检索中的 距离计算次数作为算法效率的评价参数，并在理论上分析评价参数在使用优化算法 4 华 中 科 技 大 学 硕 士 学 位 论 文 之前和使用优化算法之后的情况。 3利用上述的成果，实现一个简单的试验系统，以检验上述改进的效果，证明 了优化算法的有效性。 1.4 论文组织 本文共分五章，各章内容组织如下： 第一章介绍了课题的背景、国内外研究概况、课题的主要研究工作和论文的组 织结构。 第二章阐述了基于空间聚类图像检索的相关技术，介绍了对多维度量空间建立 索引的方法中比较经典的层次索引结构，并对基于度量空间聚类的索引做了比较详 细的说明，并说明了基于度量空间聚类的索引数的定义与结构，同时也简单的介绍 了基于度量空间聚类的范围查询算法，为后面的课题研究提供了必要的背景知识。 第三章主要介绍了基于联盟对度量聚类检索的优化算法。根据第二章所分析的 度量聚类检索算法，肯定度量聚类检索算法的有效性的同时指出了其算法的应用局 限性。并对所提出的算法的局限性和缺陷加以改进，提出了基于联盟对度量聚类检 索的优化算法。并详细的介绍了系统的操作流程，联盟的规则，前提条件和联盟的 算法，并附有流程图加以辅助说明。 第四章主要对基于联盟对度量聚类检索的优化算法进行设计和实现，并对算法 的效果进行分析对比，证明了算法的有效性。 第五章对全文做出总结，并给出了今后工作进一步的研究方向。 5 华 中 科 技 大 学 硕 士 学 位 论 文 2 基于度量空间聚类的图像检索 由于多媒体种类和数量的激增以及网络通讯技术的飞速发展，迫切需要一个有 效的存取方法，使用户能够方便地对多媒体进行浏览、查找和检索。目前，一些多 媒体搜索引擎已经开始为人们服务，这其中，以图像搜索引擎居多。这些存在的图 像搜索引擎，大多是采用基于文本关键字11和链接信息来进行图像的搜索和检索， 并没有利用图像本身的视觉内容信息，其检索精确度受到一定的限制。 传统的数据库之所以能支持高效的查询， 关键在于建立了对数据进行高效组织的 索引结构。针对日益增多的高维、大规模的数据库，给高效查询数据库的索引结构 提出了巨大的挑战，设计支持高维数据存取的索引结构便成为一个活跃的研究领域， 特别在多媒体图像数据库中建立高效的图像索引成为迫切需要解决的问题12 13。 2.1 层次结构索引 现在已有一些对多维度量空间建立索引的方法，经典的层次索引结构有 r- tree14，r*- tree15和 x- tree16。另外一种对度量空间建立索引的方法是将度量空间 映射到向量空间，这样数据集所有距离和结构性质都被保留，然后利用一些多维建 索方法进行建立索引17。用这种方法的索引结构有 fastmap18和 boostmap19。 一维索引结构被提议用于度量空间的建索，如 idistance 方法20利用 b+- tree 对 度量空间数据进行邻近搜索。它的思想是将数据分类并为每一个类选取参考对象。 每一个类中的对象根据其对应的参考对象可转化成一维值。 上述方法的大多数都用层次化数据结构，例如：树。它们都利用三角不等式性 质裁剪搜索空间。这些方法可以归为几类21。基于参考对象的方法都是用由 k 个参 考对象组成的对象集来对度量空间进行裁剪或者划分，更具数据库对象与参考对象 之间的距离决定将数据库对象存放在哪个划分出来的区间内并由此构建索引。在查 询过程中，给定一个查询对象，计算该对象与每个参考对象的距离，然后根据三角 不等式对搜索空间进行裁剪。基于该思想的层次化索引结构有 bk- tree22， metric- tree23，vp- tree24 25，mvp- tree26和 excluded middle vantage point forest27。 6 华 中 科 技 大 学 硕 士 学 位 论 文 这些方法的根本思想是选择一个或者几个参考对象作为树的根并且根据与参考对象 的距离划分空间。每一个划分出来的子空间区域对应一个子树。对每个子树选取新 的参考对象，以此递推。搜索过程就是从树根遍历该树并在该过程中不断用三角不 等式对子树进行搜索空间的裁剪。 利用参考对象的非层次方法有 aesa28，该方法依靠一个预先计算好的距离矩 阵，该矩阵存放每两个数据对象之间的距离。iaesa29方法是 aesa的改进，iaesa 选取了更加有效的参考对象。选取有效参考对象的方法在参考文献30。 尽可能将度量空间划分为紧凑区域的方法一般递归地位每一个区域存储一个参 考对象，该参考对象包含一些附加信息，这些信息可以在查询时有效率的判断该区 域是否与查询对象有关。划分区域时一般需要考虑两个准则：第一个是超平面，该 超平面由每个区域最有参考性的对象组成，运用超平面标准的索引结构有 gh- tree 和 gnat31。第二个标准是覆盖半径，覆盖半径一般用参考对象和该区域其他对象的最 大距离表示。在查询时，计算查询对象与参考对象的距离，然后综合利用三角不等 式性质和超平面或者覆盖半径将不相关的区域裁剪掉以加快搜索效率。运用覆盖半 径的几种方法有：聚类列表法32，该方法根据对象与参考对象的相似度对数据对象 进行聚类从而将度量空间进行划分，并且将覆盖半径作为每个聚类参考对象的属性 进行保存； m- tree33是一个分页并且平衡的度量树， 该树允许动态操作并且减少 cpu 和 i/o 的消耗。数据对象存储在叶子节点上，非叶子节点存储参考对象，这样每一个 参考对象代表一个子树，该子树包含一些与该参考对象相似的对象，当然参考对象 包含了其对应子树的覆盖半径。当一个新对象插入时，选取每一层中与该插入对象 距离最近的子树作为插入路径。当某一个节点溢出时采用与 b- tree 和 r- tree 类似的 拆分算法对该节点进行拆分。slim- tree34是 m- tree 的优化，它在构造时运用的拆分 算法是基于最小生成树的概念，并且它利用一种基于节点占用和申请后处理的叫做 slim- down 算法的插入机制来减少树的重叠部分，以此来优化查询。pm- tree35在 m- tree 上增加了一个超级环，该环由一组固定的全局参考对象组成，因此，一个节 点的度量空间区域有它的超球面和该超级环相交划分，这样达到将度量空间划分成 紧凑区域的目的。 7 华 中 科 技 大 学 硕 士 学 位 论 文 2.2 基于度量空间聚类的索引 2.2.1 度量空间聚类的索引说明 (1) 聚类 聚类就是按照一定的要求和规律对事物进行分区和分类的过程， 在这一过程中没 有任何关于分类的先验知识，仅靠事物间的相似性作为类属划分的准则，因此属于 无监督分类的范畴。所以研究用聚类方法根据图像之间的相似性度量函数对图像数 据库进行无监督的分类是非常有意义的。 目前，聚类算法主要分为五类：分区方法（最优化方法） 、层次方法、基于密度 的方法、基于网格的方法及基于模型的方法36。传统的聚类分析是一种硬划分，它 把待分类的对象严格地划分到某一类中，具有非此即彼的性质。模糊集理论的提出 为软划分提供了理论依据，人们开始用模糊的方法来处理聚类问题。对于基于内容 的图像的分类和检索而言，不同于传统文本的精确的匹配，它是一种相似度量。所 以模糊聚类方法更能客观的反映图像特征的特点37。 (2) 基于度量空间的索引技术 基于度量空间的索引技术是一种应用更为广泛的索引技术，它能够对普通的度 量空间的数据进行有效的查询。 定义 1 ：度量空间 m = ( d ，d ) ，其中d 是对象特征值的区间，d 是一个距离函数 d ： d d - r ，它具有如下特性：距离对称性、距离非负性、对象间距离满足三角不等式。 度量空间中包含两种最基本的相似性查询：范围查询和 k - 最近邻查询。 定义 2 ：给定对像 q d 和最大查询半径 r ，i 是依照某种索引结构建立索引的有 限对象集。范围查询 r a n g e （q ，r ）就是选取 i 子集 s 满足 s = x i | d ( q ，x ) = 1 ，i 是依照某种索引结构建立索引的有限对 象集。k - 最近邻查询 k n n （q ，k ）就是选取 i子集 s满足 s大小等于 k ， ），（），（：，yqdxqdsiysx，即从媒体数据库中查找与给定查询对象 间距离最小的 k 个媒体对象。 8 华 中 科 技 大 学 硕 士 学 位 论 文 解决度量空间中对象的相似性查询的一般策略是两个对象之间的距离越小我们 就认为它们之间就越相似。复杂对象间的距离计算一般被认为是比较费时的，因此 在相似查询时，通常使用需要计算的距离个数作为搜索复杂性的主要度量标准。对 于一个给定的数据库| s | = n ，最简单的相似性查询可以通过计算 n 个距离进行查询。 但是可以看出这样计算效率很低，特别是在数据库所含对象较多的时候。因此希望 能够建立索引，通过索引进行查询，尽量减少需要计算的距离个数。对于一般的 d 维空间( 如 m o l a p ) ，比较常见的索引有 k d - t r e e 和 r - t r e e ，或其变种38 39 40，这些 索引在低维空间中性能较好，但在高维数据空间中，性能急剧下降，甚至不如顺序 查询。 另外，随着网络的发展，人们越来越重视海量信息资源的合理利用及有效管理 等分布式计算方法，而 p e e r - t o - p e e r 系统因为所有节点具有相同的责任，协同完成 计算任务，有望成为解决海量计算的分布式计算模式而越来越受到人们的重视。当 前虽已有许多基于 p 2 p的应用系统，然而 p 2 p系统仍然缺乏有效的查询处理和信息 搜索机制41。第一代无组织的 p 2 p 系统，如 g n u t e l l a k a z z a ， l i m e w i r e 等盲目地 以 洪泛 方式或随机游走的方式向节点发送查询，搜索效率非常低下。第二代有组 织的 p 2 p 系统基于分布式哈希表( d h t ) 来组织结点，如 c h o r d 42，c a n43，p a s t r y44， t p a s t r y 45等，虽然可以改善搜索的效率，但只支持基于键的完全匹配搜索。 (3) 树形结构与聚类算法 聚类算法和树形索引算法的研究分别对应不同的目标。 传统的聚类方法动态性能 较差，当图像数据库中插入新的对象时，需要对整个图像样本集合重新聚类，反复 的迭代，聚类，对于多媒体数据库而言，代价是很大的，不利于建立高效的多媒体 检索系统。虽然聚类索引方法可以很好的支持 k 近邻搜索，但范围查询没有优势。 高维树形索引在动态性，查询方面都有优势。所以可以将高维树形空间索引和聚类 技术结合起来，取长补短，从而建立更高效的高维索引结构。两种技术可以互相利 用，可用树形索引进行聚类，也可用聚类技术建立空间索引，故将树形空间索引与 聚类技术的优势结合起来。两者都将相似或距离近的对象尽量聚在一起，而将不相 似或距离远的对象彼此分开。这个共同点为研究树形空间索引与聚类技术的融合提 供了切入点46 47。 9 华 中 科 技 大 学 硕 士 学 位 论 文 2.2.2 基于度量空间聚类的索引树的定义与结构 基于度量空间的聚类索引树为一个增量式动态平衡的聚类树。把数据对象放在 叶子节点，而非叶子节点（称为导航节点）存放本聚类的描述信息以及本聚类包含 子聚类的描述信息，该索引树的结构如下图 2 . 1 所示： 图 2.1 基于度量空间的聚类索引树的结构图 从图 2 . 1左部分可以看到，每一个聚类由一个代表对象和一个半径表示，一个 对象属于哪个聚类是由该对象与每一个聚类代表对象的相似度决定的，该对象属于 相似度最大的那个聚类，相似度的计算方法由度量函数决定。 从图 2 . 1右部分看到基于度量空间的聚类索引树的结构：叶子节点中每一项的 结构是 s ( x ) , i ( x ) , x 表示数据库对象， s ( x ) 表示通过特征提取后得到的数据库对象 x 的特征向量，i ( x ) 表示指向 x 自己的指针；非叶子节点（导航节点）中每一项的结 构是 s ( y ) , r ( y ) , t ( y ) , y 表示该聚类的代表对象， s ( y ) 表示代表对象 y 的特征向量， r ( y ) 表示以 y 为代表的聚类半径，t ( y ) 是指向它对应子节点的指针。 基于示例图像的检索方法是基于内容的图像检索中最常用的检索方式， 范围查询 是应用最广泛的查询方法48。 2.3 基于度量空间聚类的范围查询算法 2.3.1 定理及推论 基于 cm- tree 的范围查询，遍历了所有可能满足查询条件的路径。这个算法利用 了存储在树里面的距离信息（包括聚类半径，聚类之间距离表） ，空间向量满足三角 不等式的前提条件来尽早的判断待检索路径是否是目标路径之一。不同与现存的查 询算法，该算法充分利用了聚类之间的距离表，从而大大提高了裁减调无效路径的 10 华 中 科 技 大 学 硕 士 学 位 论 文 能力和系统的总体的检索效率。 以下定理证明了算法是正确的，也就是说算法不会把符合检索条件的路径裁减。 当算法遍历到某个结点n，一个查询q和它的查询范围 ( )qr 被用来和 n 的子树 () i ot 来比较，从而决定 n 指向的子树是否能够被裁减。 定理 1： 如果 ()( )() ii orqroqd+, ，那么对于子树 () i ot 里面的任何节点对象 j o ，一定有 ()( )qroqd j , 。 推论 1：如果 ()( )() ii orqroqd+, ，那么 () i ot 可以被安全的裁减。 为了可以使用定理 1， 距离 () i oqd, 不得不被计算，如果已经得到了这个节点里 的某个节点项 i o 与查询条件q的距离，就可以避免 () i oqd, 的计算。 定理 2：如果 ()()( )() ii orqroodoqd+ 00 , ，那么 ()( )() ii orqroqd+, 。 推论 2：如果 ()()( )() ii orqroodoqd+ 00 , ，那么 () i ot 可以被安全的裁减。 对于一个给定的节点项 i o ，如果它和另一个单独节点 0 o 满足定理 2 中的条件， 那么 i o 的子树可以被裁减。 cm- tree 的范围查询算法效率优于现存算法是因为它在定 理 2 基础上充分利用了聚类距离表来对检索路径进行裁减。查询项 q 和另外一个结 点项之间的距离被添加到一个距离集合中，用 distssetq 表示，对于当前结点 n 的导 航结点 i o ，定理 2 的条件被用在这个集合中的每一项，如果其中一个距离和导航结 点 i o 的子树满足定理 2，那么该子树可以被裁减，本算法的裁减效率非常高48。 2.3.2 范围查询算法 算法的输入：查询对象q，查询的范围 ( )qr ，节点n，距离表 ()noqd, 算法的输出：查询对象q在查询范围 ( )qr 内所有的对象 算法所用的主要变量见表 2.1 11 华 中 科 技 大 学 硕 士 学 位 论 文 表 2.1 查询算法主要变量表 变量名称 变量类型 变量属性 distssetq set 存储查询对象和节点对象n的距离，用于剪枝 resultset set 存储满足查询要求的对象 canbepruned boolean 是否能被剪枝，false 为不能裁减，true 为能裁减 具体算法如下： rangesearch(object q, radius r(q), node n, distance d(q,no) 1) 将 distssetq 置为空； 2) 将 resultset 置为空； 3) 如果 ()noqd, 中的值不为空，则将 ()noqd, 的值加入到 distssetq 中； 4) 对于节点中的每一个子节点，进行如下操作： 5) 将 canbepruned 的属性设置为 false； 6) 对于属于 distssetq 表中的 () k oqd, ，进行步骤 7)至 9)的循环操作： 7) 在距离表 dt(n)中检索节点 i o 和 k o 的距离； 8) 节点的类型是导航节点的情况下， ()()( )() ikik orqroodoqd+, ，或者节点 的类型是叶子节点的情况下， ()()( )qroodoqd kik , ； 9) 将 canbepruned 的属性设置为 true，即要剪去此分支，同时跳出循环； 10) 如果将 canbepruned 的属性为 false，则说明此子树不能被裁减，进行步骤 11) 计算 () i oqd, ，并将 () i oqd, 添加到 distssetq 表中； 12) 节点的类型是导航节点的情况下， ()( )() ii orqroqd+=, ，执行步骤 13)； 13) 将递归调用 rangesearch(object q, radius r(q), node n, distance d(q,qi)； 14) 节点的类型是导航节点的情况下， ()( )qroqd i =, ，执行步骤 15)； 15) 将结果集加入到 resultset 中；返回到步骤 4)； 16) 对整棵树遍历完毕后，返回结果集 resultset。 17) 12 华 中 科 技 大 学 硕 士 学 位 论 文 2.3.3 范围查询算法分析 基于度量聚类检索的范围查询算法优于其它索引结构的范围查询算法的最独特 之处在于每个节点（包括了根节点和导航节点）和查询中都保存了一张距离表，他 记录了聚类半径和聚类之间的距离信息，在度量聚类索引树的建立过程中就将聚类 半径和聚类之间的距离信息写入对应结构中。在程序执行的时候，当算法遍历到某 个结点 n，查询 q 和它的查询范围 r(q)被用来和 n 的子树oi来比较，从而决定 n 指向的子树是否可以被裁减，在判断的过程中，对距离表进行读取，而不需要重新 计算节点子树中导航节点间的距离，减少距离计算的次数，从而提高检索的效率。 但是基于度量空间聚类范围查询适用于单个的、小数据量的查询检索，当处理 大量且具有实时需求的查询时，在度量聚类索引树上进行的检索还是按照常规的方 式，对查询请求一个一个的使用范围查询方法进行检索，再一个一个的返回检索后 的结果。按照常规的检索方式对度量聚类索引树进行范围查询，毫无疑问的会多做 许多重复的工作，如对同一张图片进行多次范围查询，或者对关联性相关很大的图 片也是进行多次的范围查询。所以需要提出优化算法对范围查询算法加以改进，以 便更适用处理大量且具有实时需求的查询的情况。 2.4 本章小结 本章阐述了基于空间聚类图像检索的相关技术，介绍了对多维度量空间建立索 引的方法中比较经典的层次索引结构。度量聚类索引树是其中一种较新的方法，本 章对度量空间和聚类的概念进行详细的解释，并说明了基于度量空间聚类索引的定 义与结构。在度量聚类索引树的基础上，使用了范围查询算法对查询进行检索，故 介绍了基于度量空间聚类的范围查询算法，并对范围查询算法作了简单的分析，提 出了范围查询算法的不足之处，为后面的课题研究提供了必要的背景知识。 13 华 中 科 技 大 学 硕 士 学 位 论 文 3 基于联盟对度量聚类检索的优化 在度量空间聚类的检索算法中，存储在索引树的导航节点的距离表保存了同级 的导航节点之间的距离。当一个查询请求向下进行搜索查询的时候，首先要计算查 询请求与导航节点之间的距离，再通过使用距离表中的数据，可以大致判断和其他 导航节点的距离，根据判断对度量聚类索引树进行剪枝，继续向下搜索结果直到搜 索到叶子节点。这样就可以减少与其他导航节点之间距离的计算次数，而且效果是 很明显的。但是基于度量空间聚类范围查询适用于单个的、小数据量的查询检索， 当处理大量且具有实时需求的查询时，在度量聚类索引树上进行的检索还是按照常 规的方式，对查询请求一个一个的使用范围查询方法进行检索，再一个一个的返回 检索后的结果。 如果查询请求之间没有任何的关联，也即用户所需要查询的图片毫无联系，使 用度量空间聚类检索无可厚非。但是实际上经验显示，用户在一段时间内提交的查 询图片是具有相当的关联性的，或者极端的来说是重复性的，如因为网络的原因， 用户在无意识的情况下多次提交同一张图片。在以上的两种情况之下，还是按照常 规的检索方式对度量聚类索引树进行范围查询，毫无疑问的会多做许多重复的工作， 如对同一张图片进行多次范围查询，或者对关联性相关很大的图片也是进行多次的 范围查询。 而针对上述的情况，提出了联盟技术，用以解决在大数量查询下、数据关联性 较强的背景下的检索问题。联盟即主查询和被邀请查询经过一系列的规则所形成的 复合查询的技术手段。基于联盟对度量聚类检索优化，主要在批量数据、实时查询 的背景下应用，采用联盟的技术能极大的提高查询的效率，减少重复查询的次数。 3.1 基于联盟的检索方法 3.1.1 基本概念 (1) 联盟中的查询 在前文中提到，基于度量空间聚类的图像检索系统中，用户提交给检索系统的是 14 华 中 科 技 大 学 硕 士 学 位 论 文 一张图片，用户输入的图片为没有经过处理的原始查询，当原始查询经过特征提取 后成为一组高维的数据，即特征向量。特征向量作为查询对度量聚类索引树的检索， 在数据库中得到多个结果，返回给用户的结果是多张图片的缩略图，或者是按照某 种规则进行排列的图片的链接地址。查询对象中主要包含结构为特征向量、查询的 范围以及结果集（进行检索后，结果所存放的哈希表结构） 。 而在联盟技术中，为了更好的理解对查询的操作，把查询投影到平面上，即将高 维空间中的数据对象投影二维空间中。如图 3.1 所示，平面上的查询即可以看作为特 征向量 qfv 为圆心，查询范围 qr 为半径的圆。 图 3.1 查询的二维投影 (2) 联盟中的度量聚类索引树 参照前文 2.2 节中对度量聚类索引树的介绍，虽然索引树在高维空间中是具有层 次性的数据结构，但是由于在联盟技术中使用到的主要的信息为节点的特征向量和 节点的范围，投影到二维空间即平面上之后，也可以将节点表示为以特征向量为圆 心，节点的范围为圆心的圆。如图 3.2 度量聚类索引树的二维投影所示，表示了度量 聚类索引树投影到平面上的结构，叶子节点是没有范围的对象，投影到二维平面后 是用一个实心点来表示的，上一层导航节点包含了相应的叶子节点。同理，根节点 就是包含了第一层导航节点的大圆，第一层导航节点代表的圆又分别包含了第二层 的导航节点的圆，诸如此类，最后一层导航节点下包含的就是所有的叶子节点。 15 华 中 科 技 大 学 硕 士 学 位 论 文 图 3.2 度量聚类索引树的二维投影 (3) 联盟中查询与节点间的关系 如图 3.3 所示，表示了联盟中查询与节点间的关系。查询与节点之间的关系可以 分为两种，即相交（包含是相交的特殊情况）与不相交。图 3.3 的左图表示了在节点 的半径大于查询的节点的情况下查询和节点的关系， 图 3.3 的右图表示了在节点的半 径小于查询的节点的情况下查询和节点的关系，查询和节点相交，即查询会继续进 入此节点往下检索，说明在此节点中，此查询有和其它查询进行联盟的可能性；查 询和节点不相交，即查询不会继续进入此节点检索，说明在此节点中，此查询没有 和其它查询进行联盟的可能性。 图 3.3 查询与导航节点的关系图 (4) 联盟中查询和查询间的关系 16 华 中 科 技 大 学 硕 士 学 位 论 文 图3.4表示了联盟中查询与查询间的关系。 查询与查询之间的关系可以分为四种， 即包含、相交且交集很大、相交但是交集很小、不相交。在这四种情况中，前两种 的关系说明在某个节点中，这两个查询有进行联盟的可能性；后两种的关系说明在 某个节点中，这两个查询没有进行联盟的可能性。 之所以把查询间的关系分为了四种， 是因为要考虑到联盟的效率问题。如果两 个查询相交但是交集很小，也就是说两个查询的关联性很小或者是共性很小，把这 样的两个查询进行联盟，检索之后得到的结果只有很小一部分相同。这样，不仅对 这两个查询的检索未进行优化，检索所花费的时间没有减少，而且还将第一个查询 的检索时间变长，不能及时的返回给用户信息。 图 3.4 查询之间的关系图 (5) 查询队列 qlist 查询队列是存储查询的动态队列，因为在动态实时的环境中，接收到的查询是具 有先后次序的，通常都是先接收到的查询要先进行处理，对查询进行检索，返回结 果给用户后，此查询的生命周期也就结束了，就需要把此查询从查询队列中进行删 除。同时，又有新的查询进入查询队列中，就需要对查询队列进行处理，直至查询 队列中所有的元素都处理完毕。 (6) 主查询、被邀请查询与复合查询 参考上文中的查询队列，查询队列中存储着多个查询对象。当使用联盟技术对度 量聚类检索进行优化时，取出的要进行检索的查询被称作主查询，队列中其它的查 询被称作被邀请查询。之所以有主查询的概念，是系统默认将最开始接收到的查询 优先级设置为最高，要最先进行处理。 在处理一次查询检索的任务中，主查询只能为一个，而被邀请查询可以为多个， 17 华 中 科 技 大 学 硕 士 学 位 论 文 主查询和被邀请查询根据一定的规则进行联盟之后，生成新的查询结构，也就是复 合查询。 复合查询类是继承的查询类，有着查询类的基本结构，在复合查询的结构中，增 加了 slaverquerylist的对象，在此队列中，存储了已经确定了和主查询进行联盟的被 邀请查询对象。 复合查询在某个节点上的生成完毕，意味着主查询在某个节点联盟形成完毕。接 下来要做的工作就是复合查询继续从此节点往下检索。如上文所提到的，当一个普 通的查询请求向下进行搜索查询的时候，首先要计算查询请求与导航节点之间的距 离，再通过使用距离表中的数据，可以大致判断和其他导航节点的距离，根据判断 对度量聚类索引树进行剪枝，继续向下搜索结果直到叶子节点。 复合查询向下进行检索主要采用的是改进了的范围查询算法。 首先要计算主查询 与导航节点之间的距离，再通过使用距离表中的数据，可以大致判断主查询和其他 导航节点的距离，如果确定要进行剪枝，判断复合查询中 slaverquerylist 中被邀请查 询和被剪枝的导航节点之间的距离，如果被邀请查询落入被剪枝的导航节点，则保 留此导航节点，继续向下搜索。直到检索到叶子节点，叶子节点是没有范围的对象， 投影到一维平面后是用一个实心点来表示的，此时只需判断叶子节点