图像数据库多维索引优化方法

在内容检索中，图像是无处不在的。自计算机被发明后，人们发现只有对计算机进行有效利用，才能实现对数字图像的相应处理。其中比较经典的就是数字图像处理和分析系统，目前已经形成了专门的理论体系。所谓数字图像，是指一幅图像面向另一幅图像进行相应的修改或改进。这一过程也是从一幅图像向另一幅图像变化的过程。由于计算机技术是不断发展的，所以人们对图像的重视慢慢转向了计算机视觉识别技术和模式识别技术，也就是对图像中的很多系统进行理解，如自然景物等。虽然人们在计算机视觉识别与模式识别，以及图像分析方面已经取得了一定的成果，但到目前为止，在研究中也出现了很多问题。通过对这些问题进行理解和总结，我们可以认为它是图像在其语义上的理解，但目前这还无法得到根本性的解决。

（一）图像内容检索系统简介

目前，对图像数据库进行检索的比较成型的系统有很多，如QBIC（Query By Image Content）系统、PhotoBook系统等，它们都是优秀系统的重要代表。国内很多研究单位也对数据库检索系统进行了一定的研究，并且成功开发了一些有针对性的系统。接下来将对QBIC和PhotoBook这两种图像数据库检索系统进行简单介绍。

QBIC是20世纪90年代IBM公司开发的图像和动态影像检索系统。这一系统是支持Web图像检索服务的，特点是对图像内容进行技术上的检索，即对所需图像进行一定的描述，以实现对所需图像的检索。QBIC系统对很多特征进行了提取，如纹理和颜色等，然后通过对特征的定义实现对图像的检索。QBIC系统是开发较早的，相对比较完善的图像检索系统。在所有的图像检索系统中，它是第一个支持内容和关键字查询的图像检索系统。

Columbia实现了对VisualSEEK和WebSEEK的开发研究，是比较完善的图像检索系统。VisualSEEK是一款提供检索图像信息的工具，能实现网上搜寻工作，是比WebSEEK更具有代表性的图像检索系统。到目前为止，WebSEEK在网络上已经实现对超过65万张影像与图像的搜集，同时对文本、分类与内容等方面进行相应检索，为用户提供了更多的信息。WebSEEK对46个主题进行分类检索，如艺术、建筑和地理等，用户可以根据自己的兴趣对这些内容进行相应的浏览。

VisualSEEK这一技术的核心是在内容上的图像检索，是根据图像在纹理和颜色上的不同特征实现的。这一系统由四个部分组成，即图形用户界面、服务器应用、图像检索服务器和图像归档。它的优点是能高效实现对其在网上的图像信息查询，通过利用相应的特征提取手段，支持用户对信息的直接下载。VisualSEEK系统在电子图书馆和网络上已被投入使用，对关键字查询和内容查询均是支持的。

目前，MIT多媒体实验室已经实现了对PhotoBook的开放。PhotoBook是对图像进行浏览和搜索的工具，具有交互性。这一工具分为三个部分，分别对纹理、形状和面部特征进行相应的提取，然后用户根据不同的情况对其进行选择。

以上这些系统都有一个共同的问题，即检索过程的中心是计算机。这就说明其无法完全满足用户对查询结构的要求，主要原因是目前计算机视觉技术还不够完善，人们对很多日常图像描述上的高层次概念还无法理解。计算机视觉技术主要是对底层上的特征进行提取的。在一些领域，对于底层次特征和高层次特征而言，它们在映射关系上是比较容易被找到的，但是其中也存在很多问题。因此在对图像进行检索时，应该添加人机交互信息，如人工反馈信息等。通过高层次语义描述来实现图像在内容上的检索，是未来重要的发展方向和趋势。

对于不同内容实现图像检索技术来说，其在研究上的热点大概有以下四个方面。

第一，图像检索主要是在全局特征上进行查找，从而实现图像匹配的相似性的。这一方面具有代表性的有QBIC、PhotoBook、VisualSEEK等。

第二，图像检索方法在对象区域上的研究，主要是为了实现对图像进行适当的分割，以及对信息的提取。其中的区域应该是使用局部特征描述的，每个区域根据其不同的特征对其特征进行描述。这一方面具有代表性的有Netra、Blobworld等。虽然这一方法更加接近于用户查询的思路，但其图像分割本身的精确度不够高，会降低其在检索上的准确性。

第三，前两种研究方法是以图像为中心的，对用户本身的需求并没有进行分析。这里介绍第三个研究方向，是对这一问题展开的研究。根据用户需求的不同对其进行相应的调整，其特征和在相似性上的检查应该具有一定的灵活性，可以减少低层特征与高层语义上的差距。这一方面具有代表性的有MARS（Multimedia Analysis and Retrieval System）、Pichunter等。

第四，这个研究方向是从多种渠道实现图像在其语义上的信息获取，通过对低层特征与关键词的结合，实现对图像的标注，提升检索中的准确率。图像检索在内容上是为了缩小图像的视觉特性与用户在语义上的差距。要想解决这一“语义鸿沟”，在其他方面还要进行相应的研究，其中包括语义抽取规则和用户检索模型等。对于图像语义上的研究来说，还要考虑人对图像的理解机制。这就要涉及心理学的内容和人在视觉上所具有的认知模型等。

（二）索引和反馈机制

1.索引技术的特点

图像数据库中的数据是较多的，同时图像在其特征矢量上的维数是很高的。为了实现检索的有效性，必须要保证其在索引机制上的高效性。因为图像数据库与文本数据库的区别很大，所以在传统机制上不一定能实现对图像数据库的直接使用。

CBIR系统对于图像的描述是关于特征向量的使用的。特征向量在维数的数量级上能达到。相比很多幅数不大的小型图像数据库而言，特征向量在线性查找和优化上，通过线性查找就可以实现。但是对于很多集成检索系统而言，如数字化图书馆等，其图像库有着较大的容量，一般幅数过多。由于高位索引对检索的效率有着较大的影响，不适合对数据库进行遍历，对数据空间要进行最匹配子集的查询。因此，高效率索引机制的存在是至关重要的。就目前而言，通常使用的方法是通过维数缩减技术来降低维数，然后使用高维索引技术实现索引的功能。在目前国内外的相关研究工作中，对图像数据库在索引结构上有如下要求：

（1）索引结构要对高维数据特征进行有效处理。

基于图像数据库检索系统，依据内容的检索是能对高维特征进行处理的。在索引结构构建之后，其所具有的结点数不应根据维数的增长而相应地呈现指数级增长。

（2）索引结构能够适应相似查询。

与传统的数据库系统不同，图像检索系统在内容上对其的相似性查询是必不可少的。这是因为其处理的对象是没有一定格式的数据。索引结构要对相似查询进行有效处理。

（3）索引结构应支持不同的查询类型。

索引结构应能对多种查询类型进行处理，其中包括精确匹配查询和范围查询等。在性能处理上，索引结构应对每一种查询都有良好的体现。

2.索引技术的实现(www.xing528.com)

为了实现对索引技术的有效利用，目前比较合理的处理方式是降低图像特征向量的维数。相关研究表明，维数的降低对检索性能不会产生很大的影响。降低维数的方式主要有两种，即Karjimen-Loeve变换（KLT）和柱状聚类。

在完成了对维数的裁剪后，图像特征向量在维数上还是较高的，所以需要使用合适的高位索引算法，以实现在特征向量上建立索引。

3.用户反馈机制

相关反馈（Relevance Feedback，RF）是一种在文字检索系统中使用的技术，是指用户通过之前所具有的检索信息上的反馈对当前的查询进行自动调节（人机交互也可以实现低级特征表达上的细化），从而实现高层查询。对于图像检索来说，反馈的引入可以提供更多的信息，在检索时发挥着重要作用。有效检索在过程上应该是渐进的。在这一过程中通过对检索结果的反馈，用户会直接参与检索过程，因此其在这一过程中的作用是至关重要的。对于系统和用户来说，它们之间的交互使得检索在结果上根据用户的综合特征所进行的图像检索和反馈的研究在期望上是接近的，从而实现了用户的要求。检索是一个结合的过程，实现了客观和主观上的结合；而反馈是主观和客观在其结合上的重要实现手段。

（三）图像数据库内容检索的关键技术

传统的图像检索系统与基于内容和图像的检索系统的特点是不同的。基于内容检索的系统，在进行检索时，其使用的方法是逐步求精，每一层在其中间结果上形成一个集合，然后不断减小这一范围，并对目标进行定位。对于这几种检索方式来说，首先要提取图像中内容上的特征，并对图像内容进行相应的描述。这些一般都是呈现多维的矢量数据库特征。这样一来，图像检索在相似性上的查找就向多维矢量进行转化，所以，多维索引结构是需要进行相应设计的。除此之外，人眼在感知上对图像是有一定的主观性的。在这一检索系统中，交互性是必不可少的，这就要对用户的主观性进行修正，以满足检索需求。

1.特征的提取与表示

从广义上来说，图像具有文本特征和视觉特征。这两种特征对于图像的检索都是至关重要的。文本特征主要获取时间和图像作者等信息，手工注释是实现这些特征的唯一方式。视觉特征包括一般特征和领域特征。一般特征与应用是密切联系的，如对指纹和脸谱的识别等；领域特征需要提取相关领域的专家信息。模式识别领域是其重要的研究课题，但是在实际应用方面，它还是相对比较困难的。

（1）特征提取。

在颜色特征中，比较常用的有颜色集、颜色矩和颜色直方图。颜色直方图在实现颜色的提取方面是RGB在颜色空间上的量化，对图像中的颜色进行像素数量上的统计。在颜色直方图中，颜色量化会对其产生一定的影响，所以一般用颜色矩来表示颜色的特征。其所蕴含的数据基础如下：对于所有颜色分布特征而言，力矩都能对其进行刻画。为了实现对图像库更大规模的查询，可以用颜色集对颜色直方图进行近似代替。其主要方式就是对RGB颜色向着HSV空间上进行转化，对颜色空间进行量化，成为M个箱子。对于颜色集，从定义上对量化空间进行相应颜色的选择。因为颜色集本身的特征向量是二进制的，所以可以用二叉查找树加快对其的查找速度。

在20世纪70年代早期，共生矩阵纹理表示法实现了对纹理在灰度级空间上所具有的依赖关系的利用。在图像的像素方面，可从方位和距离上建立共生矩阵，并提取这一矩阵中有意义的信息，同时这也是对纹理特征的重要表示。对此，Tamura等人实现了对纹理属性在计算的相似性上的提取。这一方式与共生矩阵在表示方法上的区别是，纹理属性在视觉角度方面是有着重要意义的。之后，QBIC系统对这样的特征表示法进行了进一步改进。在20世纪90年代，人们开始对小波变换的方式在其纹理特征上的提取和表示进行了研究。形状特征有两种表示方式，即基于区域的形状特征和基于边缘的形状特征。对于力矩不变量来说，其对于形状特征上的表示还是通过区域力矩实现的，所具有的特点就是不会对这种变换进行改变。

（2）特征表示。

对于一些多媒体来说，它们在信息的形状、颜色和纹理上的不同表示方式，体现了其感兴趣的内容，用户对这些内容都能进行快速、有效的检索。不同公司的媒体数据库系统都是对不同形式的表达。这对于在特征标准上建立一套多媒体信息是至关重要的。MPEG-7标准是专家组对运动图像提出的国际标准，多媒体特征在这一标准上的表示是至关重要的。在多媒体领域，它所发挥的作用会越来越大。MPEG-7标准是多媒体在其信息特征的标准化上进行表示的标准，包括对多媒体、音频和视频进行描述等几个部分。

2.基于相似性检索的多维索引技术

为了保证内容图像检索的扩展性能，当这一数据集本身比较大时，应对其在性能上进行利用。这就需要充分利用多维索引技术，同时要保证它对相似性查找是有效的。索引结构设计对于本书而言，也是十分重要的研究部分。

多维索引技术的提出和发展是在应用过程中出现的。一开始，由于数据量不大，所以顺序扫描就能满足很多应用需求。随着计算机辅助设计（CAD）和地理信息系统（GIS）的不断发展，很多高效的索引机构支持空间数据的有效索引。20世纪80年代，很多多维索引结构相继出现。这些索引结构的出现使得索引数据在维数上从原本的单维向多维扩展，同时支持的查询种类也很多。传统数据库是支持精准查询的，同时也支持最近邻查询和范围查询等。20世纪90年代以来，随着数字图书馆和数字医疗等的发展，很多领域中的图像数据库也大量出现了。这些数据库有如下几个特点：第一，这些数据库的数据量是比较大的，其数据对象要超过100 000；第二，数据库的特征空间在维数上也是比较大的，其范围一般是10～100维；第三，数据库应用是动态呈现的，很多数据随时都能进行插入；第四，对于查询来说，其不仅仅是进行精确匹配，还像是相似性的匹配。它对与目标图像最接近的图像进行查询，或者保证其查询结果处在一定的合理范围内。图像在相似性的度量上有很多种方式，Euclidean距离只是其中的一种。针对这些特点，人们不仅提出了数据空间的降维技术，而且提出了很多新的索引结构，并在不同方面对图像在系统性能上的检索进行了改进。

3.交互式检索系统的设计技术

图像检索系统所进行的设计包括图形用户界面的设计和系统结构的设计。对于图形用户界面的设计来说，它是保证系统检索成功的重要条件，会大幅度提升检索效率。对于基于内容图像的检索来说，其基础特征向量就是高维向量，直观性不明显，所以其中的可视化输入手段是必不可少的。一般情况下，我们可以采用三种方式进行可视化输入，即操纵交互输入方式、模板选择输入方式和用户提交特征样例输入方式。同时，也要对一定的特征予以支持。除此之外，浏览查询结构也是必须的，能提供用户在界面上的浏览功能。需要注意的是，对内容进行检索时，文本关键字在图像上的检索不是替代关系，而是互为补充的关系。只有保证这两者之间的结合，才能真正满足检索的需要。

【注释】

[1]GIS是一种特定的十分重要的空间信息系统。它是在计算机硬件、软件系统的支持下，对整个或部分地球表层（包括大气层）空间中的有关地理分布数据进行采集、储存、管理、运算、分析、显示和描述的技术系统。

[2]MBR（Master Boot Record）：主引导记录，是硬盘的第一个扇区，即C/H/S地址的0柱面0磁头1扇区，也称作MBR扇区。

[3]key-value，即分布式存储系统，其查询速度快、存放数据量大、支持高并发，非常适合通过主键进行查询，但不能进行复杂的条件查询。

[4]VXWORKS是美国 Wind River System公司（简称风河公司，即WRS公司）推出的一个实时操作系统。Tornado是WRS公司推出的一套实时操作系统开发环境，类似Microsoft Visual C，但它提供了更丰富的调试、仿真环境和工具。