面向图像视觉特征检索的高维索引结构研究

张媛媛，杨洪娟，朱汇龙

（1. 昆明理工大学信息工程与自动化学院计算机技术，云南 昆明 650500；2. 昆明理工大学信息工程与自动化学院计算机技术，云南 昆明 650500）

0 引言

图像检索技术成为近年来多媒体领域的研究热点，在社会各行业领域都起到很重要的作用。其实它是将图像的视觉内容描述成高维数字特征信息，然后把图像检索问题转化成能相似查询的高维数据问题。随着网络科技的飞速发展，许多领域对于图像信息的应用颇多。在图像数据库规模不断增多的背景之下,我们要对目标信息进行查询与定位，这种问题直接关系到数据库的利用价值，而此时如何建立一种高效良好的高维索引结构就发挥它的重要性了。因此我们需要从图像检索技术角度来分析它的发展趋势以及主要应用方向。本文是研究图像视觉特征检索技术中构建索引结构的方法，为了实现这个目的，我们需要从整个技术涉及到的基础来入手[1]。

一些国内外的许多研究人员开始选择降维的方向，有些选择侧重于如何构建合适的索引方式。常用的降维方法有K-L变换以及聚类等。但是随意降维并不是个安全的举措，因为降维会在一定程度上损失关键图形信息。很多研究学家充分利用互联网的文本资源来做理解图像，高维向量的检索是非常关键的部分，随着图像维数的增多，未来对于图像检索的要求也越来越高，因此目前越来越多的研究着重于如何发现潜在的低维结构，以及如何利用高维数据来探索寻找低维空间与高维空间之间的关系，来建立特定的索引结构帮助人们来处理更大量的数据信息[2]。

1 高维索引结构研究相关知识

1.1 向量空间和度量空间的高维索引结构

高维索引方法分为两大类别：一类是向量空间索引结构SAM，另一类是度量空间索引结构MAM。下面将简单阐述这两类索引结构的区别，然后在给出这两类中比较常见的索引结构。

向量空间和度量空间中索引结构的区别：其实在一定条件下，这两种结构是可以互相转化的。一方面，如果有一个已经定义好的距离函数时，向量空间就可以利用这个函数转换成度量空间。另一方面，在做相似查询计算距离函数时，两者的算法执行主要代价不同。MAM是占用cpu的代价，而SAM是磁盘读取时的I/O代价[3]。不仅如此，在MAM中用到的唯一距离函数方法是三角不等式性质；而在SAM中更着重利用坐标信息，因此它具有更大的灵活性，例如后面将涉及到的K-D-B-tree算法就是一个很好的例子。

下面介绍向量空间中的高维索引结构R-tree以及度量空间中的M-tree。

（1）R-tree

R-tree属于动态索引结构，动态性表现在做插入和删除操作时并不影响查询操作。R树的每个结点对应一个磁盘页，根结点或者不是叶子结点的每个磁盘页会包含它的子结点的区域范围，因此这些子结点的磁盘页也会在相应的区域范围之内。如图是个简单的 R-tree，它反映了 R-tree的结构特点。我们可以很明显的看到，A空间包含 C，D，E，F的区域，B空间包含G，H，I，J这四个区域，所以很容易画出这种树的结构。

（2）M-tree

它是一颗平衡树，中间结点的结构比较特殊，是对于VP—tree的改进，减少了距离计算次数，是一种有效的高维索引结构。

1.2 高维索引结构存在的问题

图像是向人类传递信息的重要媒体之一，图像的优点便是直观简便，但是向人们传递各种信息的能力是毋庸置疑的。有一种现象叫做“维度灾难”。在大量数据的背景下，内存资源变成一种停滞不前的状态，而有那种基于磁盘的查找又会影响到查询的效率[4]。那么如何对这样大量的图像数据建立高维索引来满足查询的需求就变得很重要。不仅如此，像这种传统的高维索引建立方法一般来说都是独立的，它没有指出特征本身所具有的数据共性，因此这对检索性能的提高是相当有限的。所以难点就暴露出来了，我们需要挖掘视觉特征的潜在信息，然后利用该信息去建立高维索引，这样才能提高检索效率，当然这不仅是难点也是研究的新热点。而图像检索有两个研究方向，一个是数据管理，另一个是计算机视觉。区别就在于数据管理是文本描述，而计算机视觉是视觉描述。对于前者始于上世纪70年代末期，本文研究的是后者虽然研究学家研究出了许多索引方法，但仍然没有完全解决 “维度灾难”的问题。

2 距离度量公式

2.1 明可夫斯基距离

一个图像检索的性能好坏不止取决于所提出的图像特征，查询的关键还在于所使用的距离度量函数。它直接关系到检索的结果和检索效率[5]。明可夫斯基距离是基于Lp范数定义的：

如果p=l，L1(A, B)称为城区距离(city—block)，也就是绝对值距离；

如果 p=2，L2(A, B)称为欧式距离（Euclidean distance）：

如果 p→∞，L→(A, B)称为切比雪夫距离（Chebyshev distance）：

2.2 马氏距离

马氏距离可以有效计算两个未知特征向量的相似度。数学表达式为：

其中C为特征向量的协方差矩阵。这个距离标准常用来计算SAR（Simultaneous Auto Regressive）特征的相似度。将马氏距离进一步简化，表示如下：

假如Q为检索对象，D为一系列数据库中的任意图像，m和n是方向和尺度，提取的特征向量为m×n维，则两者之间的相似度量如下：

其中， dmn(Q,D)表示检索图像Q和D在相应条件下的欧式距离，μmn表示相应尺度和方向下各像素的均值，σmn表示相应尺度和方向下各像素的方差， ∂ (∂mn)和 ∂ (σmn)表示各自特征的标准差。表达式如下：

2.3 曼哈顿距离

曼哈顿距离又名CBD（City Block distance），它表示的是再某一空间的直角坐标系上存在两点构成的线段映射在x，y轴的距离之和。对于给定平面上的两点 A (x1,y1)和 B (x2, y2)之间的CBD距离为：

如果有两个 n维向量 A = ( x11,x12, … ,x1n)与B = ( x21, x22, … x2n)之间的曼哈顿距离为：

2.4 欧式距离

用来判断欧式空间中两点之间的直线距离，本文后面将采用欧式距离公式。平面上两点 A (x1,y1)和B(x2, y2)之间的欧式距离公式为：

如果有两个 n维向量 A = ( x11,x12, … ,x1n)与B = ( x21, x22, … x2n)之间的欧式距离为[6]：

3 构建SY-tree算法思想及实现过程

本节将首先介绍建立 SY-tree之前所要用到的K-means聚类方法，再介绍VP-tree的基本原理以及构造方法，然后又这两个基础就可以设计一种新的高维索引结构SY-tree，方便给出下一节的实验分析。

3.1 K-means聚类方法基本原理

通常的K-means聚类方法是一种聚类划分的技术，K-means算法的工作过程大致如下：我们从多个给定对象中随意选取 k个对象做为初始聚类中心，剩下来的就根据它们自己与这些k个操作对象的距离，分别把它们分配给与各自最相似的聚类，然后再计算每个新聚类中的对象的均值，依次重复上述相同的操作直到标准测度函数是收敛的，大多数情况下标准测度函数是均方差[7]。

3.2 VP-tree基本原理

VP-tree是一种基于距离的属于MAM的索引结构，是一颗平衡二叉树，具有平衡二叉树的特性。它的构造和搜索算法并不是特别的难，主要是利用二分查找的方法实现高维空间距离信息的搜索。VP-tree的构造和搜索算法如下。假设一个含有n个对象的数据集 S={S1, S2, …Sn}和度量空间距离函数d(Si, Sj)，现在来构造VP-tree，算法如下：

步骤1：如果|S|=0，则为空树；

步骤 2：如果不为空，则从 S中任取一个对象Sv，作为参考点vantage point，令M为S中所有对象与Sv的距离值，其中对象与Sv的距离小于M的数据集构成左子树，对象与Sv的距离大于M的数据集构成右子树。集合表达式为：Sr={Sj|d(Sj,Sv)≦M,Sj∈S,Sj≠Sv}；

步骤3：递归构造VP-tree。它的搜索方法也是利用递归，假设存在查询对象Q和距离范围r：

（1）如果d(Q,Sv)小于等于r，则返回Sr；

（2）如果d(Q,Sv)+r大于等于M，递归查找右子树Sr；

（3）如果d(Q,Sv)-r小于等于M，递归查找左子树Sl[8]。

3.3 SY-tree的算法设计思想

仿照上述K-means聚类方法以及 VP-tree的基本原理[9]，我给出构建SY-tree这个索引结构SY-tree的设计思想：首先从大量数据对象中选取k个对象做初始聚类中心，利用得到k个聚类；再将这些聚类的中心点集中在一个结点中；然后以中心点为参考点，令 r是所有对象与中心点的距离中值，与中心点的距离小于 r的构成左子树，相应的与中心点距离大于 r的构成右子树；依次重复上述操作，直到它的左子节点或者右子节点中的个数小于r；对于个数小于 r的左子节点或者右子节点，把它们作为叶子结点，在该结点中存放实际数据对象和相关信息。如此一来SY-tree的结点结构也形成了。我所设计的SY-tree只是在VP-tree的基础上运用了K-means聚类，并且聚类时计算的距离采用的是欧式距离公式，也就是说SY-tree的中间结点含有k个小聚类的聚类中心Oi(i=l，…，k)，中间结点中整体结构形式如下图所示。Si代表该中间结点中第i个聚类[10]。

图2 中间结点整体结构形式Fig.2 The overall structure of the intermediate node

SY-tree的中间结点中其他聚类的参考点数据结构如下图所示：

图3 各聚类的参考点数据结构Fig.3 Reference point data structure for each cluster

3.4 SY-tree的实现过程

有了以上SY-tree的设计思想和结点结构，开始对它用c语言进行构造：首先我们从含有N个对象的集合中选取k个对象做为初始聚类中心，其余对象根据它们与这些聚类中心的距离分别把各自分配给与其最相似的聚类；然后根据每个聚类的均值，计算聚类中每个对象与其相应中心对象的距离，并根据最小距离重新划分，再计算每个新聚类的均值[11]；重复上述操作直到不再有变化。此时，返回每个聚类Si的中心对象，并返回每个聚类的覆盖半径R(On)。然后把这些聚类中心Ol，…，Ok，作为每个聚类的参考对象，令M为所有对象与中心Qi的距离中值。同样的，把与Qi的距离小于M的集合构成左子树，距离大于 M 的集合构成右子树。如果左子树/右子树中对象个数小于等于m，则以左子树/右子树中的对象做为实际数据建立其相应的叶子结点；同样的，如果左子树/右子树中对象个数大于m，递归调用之前的步骤。这样就创建完成SY-tree。

4 实验结果与分析

4.1 测试方案

为了测试建立的索引结构 SY-tree是否有提高检索在距离计算次数、检索效率以及精准度方面的性能，我们做出以下3个方案：

（1）首先我们选择4100副64×64像素的图像，采集其中 16维，64维的数据特征向量组成集合，对这些数据集分别采用VP-tree和SY-tree索引结构，最后根据这两种结构进行相关查询。其中，选择SY-tree中2个对象作为初始聚类中心，叶子结点中对象个数m取6，利用matlab编程环境求得距离计算次数，分析它的性能[8]。

（2）采集16维的数据特征向量组成集合，分别利用VP-tree和SY-tree的索引结构来查询，根据不同数据量来得到相应的查询时间，从而分析他们各自的检索效率。

（3）采集16维的数据特征向量组成集合，分别选择10，20，30，40，50个数据对象进行查询，也就是进行10~50次等分查询，根据经查询后的对象是否在聚类中来检测两个不同索引结构的平均精准度。

4.2 实验环境

MATLAB软件是1984年由美国Math Work公司推出的一款商业数学软件，在进行数据挖掘、算法开发、数据分析处理、图形图像处理、仿真等都有着广泛的用处。MATLAB软件以其简便强大的功能迅速占领市场，被众多邻域青睐。MATLAB软件包含庞大的数学算法资源，包含我们上面提到的距离度量函数，可以方便的实现用户所需要的各种计算需求。本章将通过实验对 VP-tree和已经创建的SY-tree进行比较，并给出对比结果并进行定量分析。

测试使用的软件环境如下：

（1）操作系统平台：Microsoft Windows 8。

（2）编程环境：Matlab R2011a。

4.3 测试结果与分析

（1）如图4所示采集16维的数据集一次性搜索可得性能评价，随着查询范围的增大两个索引结构的距离计算次数也在相应的增加，但是两者增加幅度相差甚远，SY-tree的距离计算次数明显小于VP-tree。

（2）如图5所示采集64维的数据集一次性搜索可得性能评价，随着查询范围的增大两个索引结构的距离计算次数也在相应的增加，并且这种高维的增加也会导致距离次数增加，但是两者增加幅度依然相差甚远，也就是SY-tree的距离计算次数明显小于VP-tree。

图5 一次性搜索64维数据集的性能Fig.5 Perform a one-time search on the performance of a 64-dimensional dataset

（3）如图6所示，当选取16维的数据集进行不同条数的数据量查询，我们可以很明显的看到，当数据量在500条的时候，VP-tree与SY-tree的查询时间相同，随着数据量的增加VP-tree的查询时间明显比 SY-tree的查询时间要大，故由此可看到SY-tree比VP-tree的查询效率高。

图6 对不同数据量的查询时间Fig.6 Query time for different data volumes

（4）如图7所示，当选取16维的数据集分别选择 10~50个数据对象搜索时，分别采用 VP-tree和 SY-tree检索时的平均精准度，可以很清楚的发现，无论进行多少次查询，SY-tree查询的准确率都要高于VP-tree，并且随着数据对象的增多，精准度都会有所下降，故有此可见，查询数据时 SY-tree的精准度比VP-tree的精准度要高。

图7 对不同数据个数的查询精准度Fig.7 The number of different data query accuracy

综上所述，我们可以明显看到设计的 SY-tree是一种静态非平衡树，在每次构建树的过程中都使用了K-means聚合，与 VP-tree索引方法相比减少了距离计算次数，大大提高了检索效率。

5 结论

在本文中，我们描述了一种面向图像视觉特征检索的高维索引结构。运用到了图像视觉特征检索原理和高维索引领域研究基础知识，并且分析了数据间距离公式，选择合适的距离公式来设计一种新的高维索引结构 SY-tree。并将其与之前的 VP-tree进行对比，证实了该索引结构的高效性及精准性。

[1] 王崇锦. 面向图像检索的视觉特征提取及语义[D]. 吉林:长春工业大学图书馆, 2016.

[2] 黄元元, 等. 一种基于颜色特征的图像检索方法[J]. 中国图像图形学报, 2006, 16(4): 265-322.

[3] 严蔚敏, 等. 数据结构(c语言版)[M]. 北京: 清华大学出版社, 2011.

[4] 吴企渊, 等. 计算机操作系统(第2版)(教育部人才培养模式改革和开放教育试点教材)[M]. 北京: 清华大学出版社,2003.

[5] TonyF.Chan,等. 图像处理与分析[J]. 北京: 科学出版社,2009.

[6] 陈永春, 等. MATLAB M语言高级编程[M]. 北京: 清华大学出版社, 2004.

[7] 张志涌, 等. 精通MATLAB R2011a[M]. 北京: 北京航空航天大学出版社, 2011.

[8] 于静洋, 等. 海量数据的高维索引结构研究[D]. 河南: 河南大学图书馆, 2010.

[9] 梁俊杰, 等. 大规模高维数据库索引结构[J]. 计算机研究与发展, 2006, 43(2): 546-551.

[10] Hutflesz A, Siz H-'Winmayer Pf Twin grid files: Space optimizing access schemes[C]. In: Proc.Of the ACM SIGMOD Int.Conf.on Management of Data, 1988, 183-190.

[11] Bentley J L, Friedman J H. Data structures for range searching[J]. ACM Compute. 1979, 11(4): 3997-4009.