下载掌阅APP，畅读海量书库
立即打开
检索是计算机科学的基本功能，索引是支撑检索功能的核心技术。在计算机图像视觉等方向中，相似性检索是一种常用的查询类型。给定一个查询对象，相似性检索会根据相似性的定义找到相似的对象，这种功能在很多环境中非常有用。例如，在模式识别中，相似性查询可以基于标签根据已经分类好的对象对新对象进行分类；在多媒体检索中，相似性查询可以利用特定的图像来识别图像；在推荐系统中，可以通过相似性查询生成个性化的基于用户偏好的建议。本节介绍索引的概念与索引的作用。
索引是独立于被索引数据之外的一种数据，通过组织被索引数据的相关信息摘要，构建可按一定顺序查找的数据结构，在检索时过滤与目标无关的搜索空间，从而减少磁盘的访问次数，进而提高查询速度。
最初的图像检索技术是利用文本标注，为图像建立关键字，通过对关键字进行检索，进而搜索到图片。伴随着多媒体数据量的急剧增加，利用多媒体数据存储、浏览、索引和查找等技术来获取更高的经济效益成为一个新的热点。20世纪90年代以来，基于内容的图像检索（Content-Based Image Retrieval, CBIR）技术成为研究热点，至今依然热度不减。CBIR技术利用图像本身的视觉内容，如空间尺度、颜色、形状、特征等高维数据来检索有价值的图片。高维数据就是高维空间的数据，比如二维空间中的点、线、矩形，三维空间中的点、线、面、方体、球。最为重要的高维数据是从图像中提取的特征向量。
30多年来，科研工作者提出了近百种高维数据索引结构，这些结构都有各自的适用范围、优缺点。高维索引结构根据其功能又可以分为以下几种。
❑树形高维空间索引结构，例如KD（K-Dimensional）树、R树、混合（Hybrid）树。
❑基于相似性的索引结构，例如VA-File、VA + -File。
❑基于降低维度的索引结构，例如iDistance、Pyramid-Technique、iMinMax。
❑基于聚类的索引结构，例如Clindex、VQ-Index。
不同的高维索引结构对应不同的查询方法，基于特征向量常见的查询方法有：点查询、范围查询、K近邻查询。有些索引结构支持以上3种不同类型的查询，有些只支持其中一种或者两种查询方法。其中R树是B + 树在高维数据空间的扩展，只支持点查询和范围查询。大量的应用需要对高维空间中的数据进行相似性检索，为了给出相似度的计算，一种重要的方法就是对高维数据加上度量结构形成度量空间。
多维数据的查询处理在地球科学、机械CAD（Computer Aided Design，计算机辅助设计）、机器人技术、视觉技术、自动导航、环境保护以及医学成像等领域中发挥着重要的作用，其中的多维索引技术在提高查询效率、改善存取方式方面扮演着重要的角色。近几年来，对多维索引的研究由集中式逐步过渡到分布式，特别是基于对等计算的多维索引技术目前是研究的热点。
多维索引技术从20世纪中期开始到如今经历了半个多世纪的发展，简单地讲，多维索引的目的是提高查询多维数据的效率，基本方法是综合考虑数据对象的各个维度，从整体上进行统一组织，设计合理的数据结构与查询算法，从而加快查找速度。从根本上讲，利用索引提高查询效率的本质是进行数据剪枝。
数据的高维性是大规模图像检索面临的一个亟待解决的问题，索引系统面对高维数据时，效率会大大降低。图像库中的图像特征向量通常是维度很高的向量，其维数从几百维到几千维不等，甚至更高。
基于高维空间进行检索操作，其效率与特征向量的维数密切相关。面对大规模图像数据库，如何降低算法的时间复杂度，使其具有实时性是应用领域必须要解决的问题。如果没有建立索引结构，要检索某一个图像就需要扫描数据库所有的图像，该操作的时间复杂度是 O ( n )。建立索引结构的目的就是要减少计算机对不必要图片的访问，从而提高数据库的检索效率。如果需要达到实时性的要求，在大规模图像库中建立有效的高维索引方法来提高查询速度是至关重要的。
许多基于内容的检索技术在处理高维特征向量时，会遇到“维数灾难”问题，性能会显著退化，最终沦落到扫描整个图像数据库的地步，搜索响应时间还远不及顺序扫描。这些方法在高维空间中主要遇到了如下3个问题。
❑数据划分：只用到了其中一小部分维数，忽略了大部分维数，造成了非常大的损失。然而一个完整性的表示需要更多维度的信息，因此数据划分的效率很低。
❑覆盖对象：对高维空间覆盖时，大多数用到的是超球或者是超立方体，这样会存在误差，为了弥补误差就会在高维空间下产生大量的重叠现象。
❑精确检索：在精确查询的情况下，为了得到最终结果，所有与查询区域有交集的覆盖区间都需要被查询一遍，由于高维空间数据分布的极度稀疏性，这样查询的效率会非常低，性能退化成顺序查找。