基于高维局部特征和LSH索引的图像检索技术

刘 婉，徐望明，石汉路

（武汉科技大学 信息科学与工程学院，湖北 武汉 430081）

在如今信息化的时代，图像资源日益丰富，如何从海量图像资源里快速有效地获取有价值的信息，是亟需解决的问题。传统的基于文本的图像检索技术（TBIR）因其自身的局限性而无法从根本上解决这个问题。20世纪90年代，计算机视觉技术被应用到图像检索中，由此产生了基于内容的图像检索技术（CBIR），其关键在于：一是提取可靠的图像特征来表征图像的视觉内容，二是根据图像数据库规模寻找有效的特征索引和相似性匹配算法。

描述图像视觉内容的全局特征如颜色 （Color）、形状（Shape）、纹理（Texture）等虽被广泛应用于许多实际的图像检索系统中，但因其不能适应图像的局部变化而导致应用上的局限，目前流行的方法是提取图像的局部不变特征，从而用一组高维特征向量来表示图像，这其中SIFT[1]特征的性能得到了普遍认可。然而，高维局部特征在增强图像信息的可分辨性的同时，也带来了特征相似性搜索问题上的挑战：每幅常规大小的图像平均能提取成百上千的局部特征，这样对大规模的图像检索系统而言，所生成的特征库将是巨大的，一个高效的索引和匹配机制就成为特征相似性搜索迫切需要解决的难题。显然，简单的线性扫描搜索方法并不现实，而一般基于特征空间分割的索引方法如K-D Tree、R-Tree等随着维数的增加其检索性能急剧恶化。不过，LSH（Locality Sensitive Hashing）算法[2]为克服这种“维度灾难”问题提供了一条有效途径，可用来解决主存储器中高维特征的“近似近邻”（ANN，Approximate Nearest Neighbor）搜索问题。

文中将图像局部不变特征SIFT和高维特征索引算法LSH相结合应用于基于内容的图像检索，通过实验验证了即使在特征维数比较大时，仍能取得较好的检索效果。

1 算法描述

1.1 SIFT算法

SIFT（Scale Invariant Feature Transform）算法是 David.G.Lowe在2004年在总结基于不变量技术的特征检测方法的基础上提出的一种基于尺度空间对图像缩放、旋转、光照变化甚至遮挡、裁剪等保持不变性的特征提取算法。以下是生成SIFT特征的几个主要步骤[1-3]：

第1步：检测尺度空间极值点。搜寻所有尺度和空间坐标下的像素点，用层叠滤波的方式和高斯差分函数（DOG，Difference of Gauss）进行运算，以便找出潜在的特征点，这些点是不同尺度和空间中的局部极大值和极小值。

第2步：精确定位特征点。所有在第1步找出来的候选特征点中低对比度的点和不稳定的边缘点被丢弃，并构建了一个具体的模型以确定剩下的特征点的位置和尺度。

第3步：分配特征点方向。根据局部图像特征点的梯度方向，一个或多个方向被分配给每个有意义的（在第2步中确定的）特征点。

第4步：生成特征向量。这一步通过在每个特征点周围4×4共16个子区域采样图像像素的梯度幅度和8个方向形成一个覆盖采样区域的梯度方向直方图来完成。梯度在特征点所在尺度计算，以确保尺度不变性。将坐标轴旋转为特征点的方向，以确保旋转不变性。将梯度以加权的方式进行累加得到的直方图可转换形成一个128维的向量，即为特征描述子，进一步对其归一化，从而去除光照条件变化的影响。

由于每幅图像的内容不同，它们的特征向量数量也会不同，但通常每幅常规大小的图像平均都能提取成百上千个SIFT特征，并且每个特征向量都有128维。在图像数据库规模较大时就需要有高效的特征索引和特征相似性匹配机制来有效完成图像检索任务。

1.2 LSH算法

传统的近邻查询指出，数据点与查询点之间的距离应满足小于某个特定距离的条件，而在实际应用中，为了提高检索速度，可以以降低检索的准确度为代价。由此，基于“近邻查询”的概念提出了“近似近邻查询”的概念。近似近邻查询要求数据点与查询点之间的距离小于某个特定距离的概率应大于给定的概率值[4]。通过近似近邻的方法可以快速获取大致符合相似要求的点集，一种解决近似近邻问题的重要方法就是LSH算法。

LSH算法的基本思想[4]是对数据点集，利用一组具有一定约束条件的哈希函数来建立多个哈希表，使得在某种相似度量条件下，相似的点发生冲突的概率较大，而不相似的点发生冲突的概率相对较小。

引入LSH函数的定义[2]：

对任意的p，q∈S（S为查询高维矢量空间），定义哈希函数族H={hi:S→U}对距离函数D（·）应该满足如下条件：

1）若 D（p，q）p1]；

2）若 D（p，q）>r2，则 P[hi（q）=hi（p）

其中，P（·）是概率函数，i是随机数，i∈{1，…，k}。

LSH算法处理近似近邻搜索问题的高效性体现在如下的处理过程[2-5]：

对于给定参数（r1，r2，p1，p2）的哈希函数族 H 和常数 k，定义一个新的哈希函数族 Ω={g:S→Uk}， 满足 g （p）={h1（p），h2（p），…，hk（p）}，其中 hi∈H，p∈S 为特征向量。 从 Ω 中随机选择 L 个函数（g1，g2，…，gL）。 当建立特征索引时，将每一个 p 通过哈希映射后存储在哈希表项 gj（p）中，其中 j=0，…，L，由于这些表项的总数可能会很大，需要通过使用散列保留非空表项。当查询一个特征向量q时，通过搜索所有的哈希表项g1（q），g2（q），gL（q）得到属于 q 的相似域的所有特征向量。 如果p与q的距离在q的相似域阈值范围内，则返回p作为q的近似近邻。

2 CBIR系统构建

文中将SIFT特征提取算法和LSH索引算法应用到基于内容的图像检索系统（CBIR）中，构造实验系统结构如图1所示。

图1 提出的基于内容的图像检索系统Fig.1 The proposed CBIR system

首先，利用程序读取图像库中的每一幅图像，并采用SIFT算法提取其特征向量，然后依次存入特征数据库。特征数据库中应包含图像每个SIFT特征128维的向量信息以及每个特征向量所属原图像的ID（ID即图像编号）信息。然后，根据LSH算法建立图像特征索引。

对于用户给定的查询图像，系统首先提取其SIFT特征向量，通过LSH索引的近似近邻查询方法可以获得与给定图像的特征向量集相似的所有特征向量以及所属库图像的ID，对将得到的库图像ID进行投票统计，如果要求只找出与给定查询图像最相似的N幅图像，那就选出出现频数最多的前N个ID（即为与查询图像最相似的N幅库图像的ID），利用程序在图像库里找到对应ID的N幅图像，按照ID出现频数由大到小的顺序 （即与目标图像相似程度由高到低的顺序）显示检索得到的N幅图像。

3 图像检索实验及性能分析

1）实验设置

图像库采用Caltech Buildings图像库[6]中的图像，其中包含250幅建筑物的图片，图像尺寸为300×300，取自50处不同的建筑物，其中每一处建筑物图像存在不同程度的缩放、旋转、视角偏差和亮度变化等。另外，从Caltech Buildings提供的250幅图片中随机选取15幅图片作为查询图像对系统进行测试。文中采用Matlab实现整个实验过程。实验中，对图像库中250幅图像提取的SIFT特征总数为168 790，实验要求在图像库中检索出与目标图像具有相同建筑物的前5幅图像。

2）实验结果及性能评价

图2是对查询库中的任意两幅图像进行查询后所得实验结果的示例。从中可以看出，系统分别为两幅查询图像检索出5幅与之相似的图像。图2中5-NN（5-Nearest-Neighbor）检索结果即5幅近邻检索图像。对第一幅查询图像而言，系统准确地返回了图像库中与之相关图像的5幅图像的全部；对第二幅查询图像而言，系统返回了图像库中与之相关图像的5幅图像中的4幅，且排序比较靠前，最后1幅图像是错误的返回结果。

图2 两幅查询图像及实验结果示例Fig.2 Examples of two query images and the experimental results

对于该系统的性能评价，采用信息检索中标准的评价方法：查全率与查准率。

查全率是在一次查询过程中系统返回的查询结果中的相关图像的数目r在图像库中所有相关图像数目R中占有的比例，用公式表示为：

查准率是指在一次查询系统过程中系统返回的查询结果中的相关图像的数目r在所有返回图像数目N中占有的比例，用公式表示为：

由于实验中Caltech Buildings图像库中每幅查询图像只有5幅相关图像，系统指定返回5幅图像作为检索结果，R=N，从而查全率与查准率值相等。表1统计了查询库中15幅图像的检索结果。

表1 15幅查询图像的检索结果Tab.1 Retrieval results of 15 query images

由此，可初步估算出系统的平均查全率（或查准率）=每幅查询图像的查全率之和/查询图像的总数目=86.67%。更准确的平均查准率（或查准率）可使用更多的查询图像或使用不同的图像库重做实验加以统计。

4 结束语

文中将目前流行的图像局部不变特征提取算法SIFT和高维特征索引算法LSH应用到基于内容的图像检索系统（CBIR）中，在Caltech Buildings图像库上进行了图像检索实验，验证了该方法的有效性。

[1]David G L.Distinctive image features from scale-invariant keypoints[J].InternationalJournalofComputerVision，2004，60（2）：91-110.

[2]Indyk P，Motwani R.Approximate nearest neighbors：Towards removing the curse of dimensionality[C]//Proc.of the 30th ACM Symposium on Theory of Computing，New York:ACM Press，1998：604-613.

[3]David G L.Object recognition from local scale-invariant features[C]//International Conference on Computer Vision，Washimgtoin，DC，USA：IEEE Computer Society，1999：1150-1157.

[4]唐俊华，阎保平.基于LSH索引的快速图像检索[J].计算机工程与应用，2002，38（24）：20-21，63.TANG Jun-hua，YAN Bao-pin.Fast image retrieval based on LSH indexing[J].Computer Engineering and Applications，2002，38（24）：20-21，63.

[5]Gionis A，Indyk P，Motwani R.Similarity search in high dimensions via hashing[C]//Proc.International Conference on Very Large Data Bases，USA:Morgan Kaufmann Publisher Lnc.，1999：518-529.

[6]Caltech-building data set[EB/OL][2011-08-02].http://www.vision.caltech.edu/malaa/datasets/caltech-buildings/caltechbuildings.zip.