基于卷积神经网络和LSH的图像检索算法

杨 荣,张建刚，贾 晖

(1.西安邮电大学 计算机学院，陕西 西安 710121；2.西安热工研究院有限公司 电站信息及监控技术部，陕西 西安 710032)

随着多媒体技术的广泛应用，快速高效地从图片数据库中检索出满足条件的图片显得尤为重要。图像检索技术从最早的基于文本的检索技术(Text-based Image Retrieval,TBIR)已发展为基于内容的检索技术(Content-based Image Retrieval,CRIR)。CRIR有两个主要任务：一是提取图像的特征；二是为大量的图像进行特征匹配。随着深度学习的研究与发展，研究人员发现，经过大量带标签样本训练与学习后的卷积神经网络(Convolutional Neural Network,CNN)有能力抽象出高层的语义特征[1]，跨越“语义鸿沟”，满足基于内容的图像检索需求。

传统基于内容的图像检索方法是通过计算纹理、颜色等图像底层特征，并将特征进行比对，实现内容检索[2-3]。但是，这些特征都只能反映图像底层视觉特征，不能反映图像高层的语义特征，限制了检索的准确率。为了有效实现图像的语义检索，基于卷积神经网络的图像检索方法被提出。基于深度学习的尺度不变特征转换 (Scale Invariant Feature Transform,SIFT)图像检索算法[4]采用卷积神经网络提取SIFT 特征，并利用支持向量机 (Support Vector Machine,SVM)对图像库进行无监督聚类。文献[5]对图像的SIFT特征先进行局部特征聚合描述符 (Vector of Locally Aggregated Descriptors,VLAD)编码，保证图像SIFT特征的维度一致性，再进行特征向量局部聚合，实现特征检索。然而，以上特征都是手工设计，提取的特征与真实图像分布存在一定差距。近年来，随着深度学习的进一步发展，利用深度学习自动提取图像特征表现出色[6-7]。与传统的特征提取方法相比，深度学习方法更能保留与图像特征数据分布相关的高层语义信息，从而使得检索更加有效。但随着图像数量的日益爆炸式增长，对于维度很高的特征，树状搜索容易产生“维度灾难”，如最近邻搜索。目前解决维度灾难问题最为常用的方法是哈希算法，基于哈希算法的图像检索算法在特征维度很高时，将高维特征向量降维为低维散列码，通过比较两个散列码的海明距离，计算图像的相似程度，从而高效实现图像检索[8-9]。文献[10]将深度学习与哈希算法相结合，将图像哈希映射为二进制向量，减少特征存储开销，并将相似图像映射到相近区域，提高了检索效率。文献[11]提出了一种哈希算法，将图像输入分为检索图像、相似图像和不相似图像三元组，采用深度神经网络进行参数学习，检索效果较好，但每次都需要人为设计图像三元组，使得工作量增大。文献[12]提出了一种深度离散哈希算法，虽然该算法能够有效提高检索的准确率，但是图像的输入仍遵循成对输入的原则，计算开销较大。深度正则化相似度比较哈希(Deep Regularized Similarity Comparison Hashing，DRSCH)算法[13]通过保留多标签图像间的相似语义信息学习哈希函数，但需要对图像数据进行标记，工作量较大。

为了提高图像检索的速度和准确性，提出一种基于卷积神经网络和局部敏感哈希(Locality-Sensitive Hashing，LSH)算法的图像检索算法。在视觉几何小组16(Visual Geometry Group 16,VGG16)网络的基础上用哈希层代替全连接层，通过深度学习获取图像高维语义特征，利用哈希映射避免维度灾难。采用LSH算法，使用哈希函数将高维特征在保证度量距离的同时进行高效降维，构建索引结构。相似语义特征的图像放入同一个哈希桶中作为候选集，在候选集计算特征向量间的欧式距离，以期实现大规模图像的快速检索。

1 预备知识

1.1 卷积神经网络

传统的卷积神经网络包括输入层、卷积层、下采样层、全连接层和输出层。神经网络通过交替的连接卷积层和下采样层，将图像转化为特征图，通过全连接层形成特征输出。卷积层通过实现“局部感知”和“参数共享”两种方式，达到降维处理和提取特征的目的。当输入彩色图像时，卷积层使用3×3卷积核和长度为1的卷积步长进行提取局部特征，提升了决策函数的区分性。下采样层使用池化机制进行采样，通过池化过滤器对输入数据进行降维。全连接层的作用相当于“分类器”，每一个结点与下采样层进行全连接，将卷积和下采样之后的特征进行汇总，得到输入图像的特征向量。

VGG16网络模型包含13个卷积层，5个池化层和3个全连接层，具有层数更深更宽和卷积核更小结构两个特点，在图像分类领域表现出了较好的准确率和召回率。然而，VGG16网络模型训练准则是针对图像分类任务设计的，直接用于图像检索任务难以取得好的效果。

1.2 LSH算法

LSH算法的基本思想是定义一系列Hash函数h1,h2,…,hn，随机选取k个函数构成函数族g(x)，即g(x)=[h1(x),h2(x),…,hk(x)]。通过构造L个函数族g1(x),g2(x),…,gL(x)，将每个函数对应一个哈希表，即利用哈希函数族gj(x)将高维空间中的每个点x存入哈希表的哈希桶中。LSH算法使高维空间中相似的点出现在同一个桶中的概率大，不相似的点出现在同一个桶中的概率小，其索引结构如图1所示。

图1 LSH算法索引结构

对于任意高维空间的两个点p,q，应满足以下两个条件。

1)若D(p,q)p1。

即在高维空间中两点的距离小于r1，则哈希函数值相等的概率大于p1。其中，D(·)表示高维空间中p,q两点之间的距离，P(·)表示概率函数。

2)若D(p,q)>r2，则P[hi(p)=hi(q)]

LSH算法将d维空间Hd中的点映射到d′维海明空间Hd′中，映射具有保距性，因此，∀p,q,DHd(p,q)=DHd′(p,q)。

2 图像检索算法

基于卷积神经网络和LSH的图像检索算法框架主要包括特征提取和特征检索两个部分，如图2所示。在特征提取阶段，先从互联网上爬取大量图片，将其进行存储生成图像库。然后，利用改进的VGG16网络进行图像特征学习，得到图像特征向量。在特征检索阶段，利用哈希函数将高维特征向量进行降维，将语义相似的图像特征向量映射到同一个哈希桶中，在同一个哈希桶中实现图像检索。

图2 算法框架

2.1 改进的VGG16网络模型

传统的深度学习需要大量的训练样本才能保证参数的可用性。然而，在实际应用中样本数量有限，获取大量独立同分布的样本具有一定的难度。为了解决实际问题，提高训练参数收敛速度，在VGG16网络模型的基础上，采用大型数据集ImageNet对网络中的随机初始化参数进行训练，保存最终得到参数的权重值，将权重值作为VGG16网络的初始化参数。在提取图像库中图像的特征值时，对初始化参数进行微调，并去除VGG16网络中的全连接层，采用哈希层代替全连接层，实现特征检索。

改进的VGG16网络模型由13个卷积层、5个池化层和1个哈希层组成。输入的图片数据大小为224×224，初始卷积核的大小为3×3，步幅大小为1，有效填充大小为1，池化层采用2×2的最大池化函数Maxpooling。

卷积过程为：1)使用两次64个卷积核的卷积后，进行第1次Maxpooling；2)经过两次128个卷积核的卷积后，进行第2次Maxpooling；3)经过3次256个卷积核的卷积后，执行第3次Maxpooling；4)重复两次3个512个卷积核卷积后，进行最后一次Maxpooling。Maxpooling之后不进入全连接层，而是输出图像特征向量进入哈希层。去掉VGG16全连接层的原因在于卷积层提取的是局部特征，而全连接层通过权值矩阵将局部特征全部组装在一起进行图像的分类识别，全连接层之前的所有卷积层的工作任务就是提取图像特征。对于图像检索，不需要全连接层特征数据，并且全连接层产生参数多，计算量大，影响检索效率。改进的VGG16网络模型如图3所示。

图3 改进的VGG16网络模型

2.2 哈希函数构建

利用局部敏感哈希算法将高维空间中的数据点进行降维，使得在高维空间中距离近的点经降维后距离仍然近。考虑到传统LSH算法将图像特征映射到低维的海明空间内，计算海明距离时需要进行欧式距离与海明距离之间的距离换算，容易产生换算误差，因此，将采用基于p-稳定分布的LSH，直接计算欧式距离，并在保证度量距离的同时，对特征向量有效降维。

柯西分布是1-稳定分布，其密度函数为

高斯分布是2-稳定分布，其密度函数为

利用p-稳定分布可以近似描述高维特征向量，并对特征向量进行有效降维且保证向量之间度量距离的不变性。

定义哈希函数

(1)

式中：a为随机选择的满足p-稳定分布的d维向量；向量a与向量v的点积a·v将每个向量映射到直线上；b为[0,r]范围均匀分布的一个随机数；r为直线上分段的段长。哈希函数将一条直线分成等长为r的若干段，给映射到同一段的点赋予相同的哈希值，映射到不同段的点赋予不同的哈希值。

假设v1和v2为两个图像特征向量，定义v1和v2之间的距离c=‖v1-v2‖p，(a·v1-a·v2)与‖v1-v2‖pX同分布，则v1和v2的碰撞概率为

(2)

式中，fp(·)为p-稳定分布概率密度。当直线上分段的段长r固定时，碰撞概率会随着向量之间距离c的减小而增大。当原始空间中两张图像较为相似时，则向量距离较小，映射以后距离也较小，因此哈希函数可以保持位置敏感性。

为了避免单个哈希函数带来的随机性误差，定义哈希函数族gi(v)=[h1(v),…,hk(v)]，其中，hi(v)为满足p-稳定分布的随机哈希函数。每个向量v∈d经过函数g映射后，得到一个k维向量σ=(σ1,σ2,…,σk)，其哈希映射h1和h2分别表示为

(3)

(4)

2.3 图像检索算法的步骤

基于卷积神经网络和LSH的图像检索算法的具体步骤如下。

步骤1对图片库中的每一张图像经过改进的VGG16网络模型计算特征向量。即对ImageNet数据集训练改进的VGG16网络，用训练后得到的参数对网络进行初始化，使用改进的VGG16网络模型提取图像数据库中各图像的特征向量，得到w个25 088维特征向量，w为图像库中的图像数量。

步骤2构造哈希函数族。构造L个哈希函数族gi(v)，每个函数对应k个随机从式(1)中选取的哈希函数组成。函数格式为gi(v)=[h1(v),h2(v),…,hk(v)]，每个图像特征向量经过gi(v)变换之后变成k维向量(σ1,σ2,…,σk)，形成降维后的w×k维矩阵。

步骤3直接将(σ1,σ2,…,σk)放入哈希表中不利于查找，利用式(3)和式(4)中两个哈希映射h1和h2产生两个函数值，其中：h1是哈希表的索引值，指向哈希表的某个索引处；h2是h1指向的索引处的桶号。每个数据点经过以上过程后，h1和h2相同的数据点会被存入同一个哈希桶中。

步骤4对待检索图片提取特征并根据哈希函数计算哈希码，将其映射到哈希桶中，同一个哈希桶中的图像为粗检候选集，在候选集中利用欧式距离计算特征向量相似度，返回排名靠前的图像则为检索结果。

3 实验结果分析

3.1 数据获取

建立一个图像检索系统，通过爬虫程序在互联网上收集获取25 000张图像并进行整理，得到图像数据库，对图像数据库中的数据集进行手动标注，共12个标签。将数据集中数据进行旋转、裁剪、缩放、平移变换、图像亮度及对比度增强等预处理，所有图像的像素均为224×224，按4∶1将原始数据集划分为训练集及测试集，形成完备的数据集。通过图像数据库构建，可提升检索模型的泛化能力，有利于提高检索算法的鲁棒性。同时，爬虫爬取图像数据集还可定期对数据集进行数据增广，提高检索的实用性。

3.2 不同哈希算法的图像检索对比

在Windows 10操作系统、I5-5257U中央处理器、8 G内存和500 G硬盘环境下，采用TensorFlow深度学习框架和Python编程语言进行实验。实验中确定参数L和k的取值分别为L=10，k=20。

分别对比基于LSH算法、普哈希[15](Spectral Hashing,SH)、监督离散哈希[16](Supervised Discrete Hashing,SDH)、深度哈希[17](deep Convolutional Neural networks Hash,CNNH)和核监督哈希[18]( Kernel-Based Supervised Hashing,KSH)算法的图像检索算法的准确率和训练时间，如表1所示。

表1 不同哈希算法的图像检索算法的准确率和训练时间对比

由表1可知，基于LSH算法的图像检索算法并非具有最高的准确率，随机哈希函数的选择带来了准确率在有限范围内的下降。但与基于其他哈希算法的图像检索算法相比，检索时间缩短了。这是因为LSH算法不需要将数据分成特定的数据对进行数据学习，并且通过哈希函数将相似特征的图像映射到邻近的哈希桶中，算法时间复杂度是O(log(n))，在图像规模显著增加的前提下，检索准确率稳定，因此适用于大规模、对准确度要求不苛刻的图像检索问题。

基于不同哈希算法的图像检索算法的检索结果如图4所示。可以看出，基于LSH算法，即所提算法在8幅结果中全部为查询图像的相似图像，CNNH有8幅、SDH有7幅、KSH有6幅，而SH只有3幅。由此可见，所提算法具有较为准确的检索结果。

图4 基于不同哈希算法的图像检索算法检索结果

4 结语

基于卷积神经网络和LSH的图像检索算法，通过爬虫程序获得网络上的真实图像，形成图像数据库，利用ImageNet图像对VGG16网络进行训练，获得网络初始化参数，并对VGG16网络进行改进，将哈希层代替全连接层。利用满足p-稳定分布的位置敏感哈希函数对高维空间中的数据点进行降维，将相似图像映射到同一个哈希桶中作为粗检候选集，计算并排序粗选候选集中特征向量欧氏距离完成图像检索，得到最终的检索结果。实验结果表明，相比其他基于不同哈希算法的图像检索算法，所提算法具有较高的准确率和较快的检索速度，适用于大规模、对准确度要求不苛刻的图像检索问题。