基于卷积神经网络的图像搜索技术研究

(山东师范大学物理与电子科学学院，250358，济南)

随着数字多媒体和各类应用APP的普及，人们每天都要接触到大量的图像信息，在网络上进行频繁的图像下载、上传和查找操作.在实际生活中，相似图像搜索技术有着巨大的应用价值.它可以用来查找某些图片的同源图片、识别图像内容、检测盗版图片、商品比价、图片导购等.而要有效地利用图像信息，并能够在海量的图像数据库中比较准确地找到用户所需要的图像信息，就需要高效的机器学习语言.但是对于这些海量的图像数据，当我们对其进行检索时，因其数量大、图像特征维度高以及要求检索实时响应的特点，使得图像搜索技术面临巨大的挑战.虽然传统的线性扫描的搜索方法能得到比较好的搜索精度，但是极其耗时而且内存使用效率很低.后来，提出了基于树的相似最近邻的方法.KD树算法[1]通过对多维数据空间的分割，然后在特定空间的内进行相关搜索操作从而实现高效索引的数据结构.在KD树提出之后，也陆续地提出了其他的树形结构，如M树,Cover树，Metric树等.基于树的图像搜索方法在处理低维数据时能有较好的结果，但是在处理高维数据时搜索效率会急剧下降，无法适应对海量数据的处理.为此，基于哈希编码的图像搜索方法被提出来了.

哈希编码可以将表示图像的高维向量表示成二进制码的形式，每一个图像都有自己独一无二的哈希码，我们通过这个编码就可以快速找到相关图像并比较出图像间的相似程度.哈希编码能够降低数据维度，减少数据的存储和搜索代价，从而显著提高检索系统的效率.因此，成为了图像搜索领域的一个研究热点.现在主流的哈希算法是将图像检索系统中的表征图像特征的高维向量，通过哈希函数映射成简洁的二进制的哈希码并构建哈希表，而图像间的相似度可以直接通过计算海明距离来进行比较，计算速度大大提高，从而能进行快速的图像检索.对于基于哈希编码的图像检索系统而言，哈希函数的选择至关重要，要能保证哈希前和哈希后的特征之间的相似度是一致的.如图1所示，哈希后原本相似的图像的哈希码尽可能一样，而不相似的图像的哈希码要尽可能地不一样.

虽然哈希编码应用在相似图像搜索上有不错的效果，但是这种方法也存在着一些不足.目前的主流方法是将特征提取和哈希学习分开的，我们只有先提取到图像的特征才能进行后续的哈希编码.如果我们一开始提取到的图像特征没法准确地表达各类图像，那后续哈希函数的选择就会失去意义.因此，如何提高特征提取的准确度，将特征提取的方法和哈希编码结合在一起，从而提高整个图像搜索系统的精度具有十分重要的研究和应用意义.

图1 哈希编码示意图

综合上述的研究和分析，本文提出了将深度卷积神经网络和哈希编码相结合的快速图像搜索算法.与其他图像搜索算法相比，本文提出的基于卷积神经网络和哈希编码的方法有以下优点:1)无需采用人工的方法对图像提取特征，而是直接通过深度学习的卷积神经网络来进行学习，提高了搜索精度;2)通过运用己经训练的深度神经网络，提高哈希编码的速度和效果，缩短了检索时间.

1 哈希编码

1.1图像哈希方法分类2007年,Salakhutdinov和Hinton[3]将哈希编码应用到机器学习方面，广泛应用于信息检索、计算机视觉、以及图像搜索等多个领域.因为哈希编码能将图像信息表示成二进制的形式，从而大大解放了图像存储的内存，提高了图像查找的速度，是近几年在图像搜索领域的一个研究热点.

现在大多的哈希编码都可以通过两步来实现——先采用度量学习[2]的方法将原数据集合映射到低维空间;然后对降维后的特征向量进行离散化处理得到二进制的哈希码并生成哈希编码表.从机器学习的层面来看，目哈希算法可以分为无监督哈希算法、半监督哈希算法和有监督哈希算法三类[14].

无监督聚类是无监督学习的一种方法，在搜索图像时我们只需向系统输入代表图像信息的向量，哈希算法就能够自动地学习哈希函数并生成对应的二进制哈希码.无监督哈希中有许多极具代表性的算法，例如局部敏感哈希算法(Locality Sensitive Hashing,LSH)，KLSH[4]，SH[5]，ITQ[6]等.

1998年，Indyk等人提出了LSH算法的雏形，LSH算法对后续哈希算法的发展具有重要意义.LSH算法可以利用随机投影实现，随机投影依据Johnson-Lindenstrauss定理产生特定分布的投影矩阵，然后根据该投影矩阵对原始的高维数据进行线性变换投影到低维空间，并且使得投影后的低维空间在很大程度上都能维持原始高维空间下的距离信息[7].LSH算法采用的是过滤-验证结构(Filter-and-Refineframwork)的概率方法.在过滤阶段，LSH利用哈希技术把不相似的图像都过滤掉，剩下的图像放到候选集合里，这样候选集合里的图像就是粗略筛选出的在某些特征上相似的对象.在进行图像搜索时，只需要对这些候选集里的图像进行相似度量计算，因为候选集里图像的数量远少于实际图像集里的图像 ，这样就可以大大缩短查询计算时间，提高了查询效率.

经典的LSH算法在原始空间上的映射是随机进行的，该算法的要求是对已知的原空间进行操作，这就限制了图像搜索技术及其搜索精度的提高.2009年Kulis等人提出了能在核空间而不是在原空间构造哈希函数的KLSH算法[4](Kernelized Locality-sensitive Hashing).KLSH算法能够应用于任意的核函数从而弥补了LSH在可以处理的图像空间上的不足.

LSH是通过随机投影实现的，因为与数据无关所以具有通用性，但想提高它的准确度就需要增加编码的长度.为了使系统只需较短的编码长度就能达到比较好的检索效率，于是基于学习的哈希编码方式被提出来.谱哈希(Spectral Hashing,SH)是无监督学习中具有代表性的一种算法，能给每个对象生成一种二进制编码，从而使得对象之间的相似度只与其二进制编码之间的海明距离有关.图像间的相似度越高它们的海明距离越小，相似度越低海明距离越大.

2011年，Gong等人提出了既可以用于有监督也可以用于无监督算法的迭代量化哈希算法(Iterative Quantization,ITQ).ITQ的主要思路是先用PCA对原始空间的数据集进行降维处理，要使量化误差尽量地小，只需将该数据集中的数据点映射到二进制超立方体的顶点上，就能得到对应该数据集优良的二进制编码[6].ITQ采用旋转数据的方法使其量化误差达到最小，该做法最早可参考文献[8,9]，不过文献[9]中的算法并没有对数据进行降维，而文献[8]中的算法也没有针对二进制哈希码的操作.

无监督哈希与数据无关所以大多具有通用性，而与数据相关的有监督哈希则不具备通用性.但是相比无监督哈希，有监督的哈希能学习到更紧凑的编码方式，哈希效果要比无监督好.虽然有监督哈希的效果会随着编码长度的增加而提升，但是当编码长度达到一定程度后，哈希效果不会再随着编码长度的增加而提升，甚至图像检索的效果会变差.

2011年Norouzi和Blei提出了一种有监督的哈希算法(Minimal Loss Hashing，MLH)，它可以根据结构化SVM(Structural SVM)构造一个用于哈希函数学习的目标函数.由于它采用的是连续且非凸的目标损失函数，所以它很难被直接优化.Kulis等提出的BRE (Binary Reconstructive Embedding)算法构造哈希函数的方法与基于随机投影构造哈希函数的方法不同，它采用了坐标梯度下降的办法迭代地更新哈希函数直到找到一个局部最优解，主要思想是尽量使哈希学习前后原数据集中图像间的相似程度一致.

2012年，Liu等人提出了有监督的哈希算法(Kerncl-based Supervised Hashing，KSH).前面提到的MLH和 BRE是直接通过将哈希码间的海明距离最小化以达到训练哈希函数的目的的，KSH与他们不同的是它是将哈希码的内积最小化了，也就是说它计算哈希码的内积就相当于计算海明距离.将哈希码的内积最小化可以使问题变得更简单更易解决.

考虑到无监督和有监督哈希的优缺点，2010年Wang等人提出了SSH(Scmi-Supervised Hashing),它综合了有监督哈希和无监督哈希算法的优点，是一种半监督哈希算法，在某种程度上可以使哈希函数的质量得到提高.

1.2哈希编码算法为便于说明，先定义算法中的相似性矩阵S，

我们通过神经网络对哈希函数进行训练，并且需要得到数据集中图片相应的哈希码，下面就介绍构造训练集的哈希编码的算法的推导过程.

由此，可我们可以将以下目标函数最小化，从而来得到训练集中图像的哈希码:

(1)

其中,‖·‖F为弗罗贝尼乌斯范数，Q∈{一1，1}m×n.

虽然定义了目标函数，但直接优化公式仍然是非常困难的.由于二值约束条件Q∈{一1，1}m×n的存在，该问题很难求解，因此需要与谱哈希求解一样放宽约束条件，即将矩阵Q的取值范围转变为Q∈[-1,1]，而不是原有的离散值一1和1，那么目标函数就转化成下面的形式,

(2)

式(2)依然需要继续优化，由于存在项QQT，可知该问题是非凸的(non-convex)，可以采用贪心策略来处理非凸问题.每次按顺序更新或者随机选更新Q中的某一元素，同时保持其他元素不变.假设当前要更新的元素为Qij，其他元素不变，使Q=[Q·1,Q·2,...,Q·q]，其中Q·j表示为矩阵Q的第j列.重写式(2)为:

(3)

其中，为了便于推导说明，我们定义矩阵R为:

(4)

因为定义的矩阵S是对称阵，可知R也是对称阵，所以Qij的目标函数可以写作:

(5)

假设想要更新Qij为Qij+d，那么将式子优化为:

(6)

为了便于得到d，将g(Qij+d)近似泰勒展开为:

(7)

其中，g'(Qij)和g"(Qij)分别为函数g的一阶导和二阶导，即:

(8)

对近似的二次函数中的d求导，假设导数为0,得到d的解:

(9)

除了需要满足-1≤Qij+d≤1外，为了使Qij+d的结果为1或-1，根据哈希编码的二值定义，还必须约束d的取值范围.由上可知，d的取值应为-1-Qij或1-Qij+d，通过算法首先得到在理想情况下d的取值，然后取-1-Qij和1-Qij+d这两个更接近d的值，与传统方法方法相比，减少了需要对结果取整造成的误差，同时提高了算法的运算速度.

通过式(9)求得d的解后，Qij的形式就更新为Qij→Qij+d.

可以发现，每一次更新Qij时都需要计算一次d,而其中求解矩阵R又是耗时最多的，时间复杂度为O(n2)，如果训练集n过大会使得每次更新的代价过高.因此，下面将讨论如何更好地计算R，从而将每次更新Qij的时间复杂度降到O(n).

施行教学评价最重要的目是为了不断得到反馈，改善教学效果，因此师徒制教学评价体系中应该设置顺畅的反馈渠道和激励方法，将采集、分析和汇总的各种相关信息及时传递到有关部门，相关部门根据这些信息能够及时进行总结和整改，修改和制定各项措施，使教学质量不断提高。

定义新矩阵L=QQT-nS，计算新矩阵的一阶导g'(Qij)和二阶导g"(Qij):

(10)

可以发现，当给定矩阵L时，该算法能够在O(n)的时间内得到g'(Qij)和g'(Qij)，也可以在O(n)的时间内求出d.与此同时，当更新Qij←Qij+d后，只有矩阵L的i行和j列发生变化，所以得到新的矩阵L为：

(11)

由式(11)可以发现更新矩阵L的时间复杂度只有O(n)，所以开始时只要先构造矩阵L=QQT-nS，就能保证在O(n)时间内完成后面Qij以及矩阵L的每一轮更新，每轮更新的时间复杂度为O(n).

图2 基于深度学习的啥希算法模型示意图

2 深度学习

2.1深度卷积神经网络概述早期的基于图像内容的图像搜索方法主要是通过人工来提取图像特征，但是人工提取不仅工作量大而且提取图像特征的准确度也不够高.深度学习是近些年的一项热门研究.我们可以利用深度学习，建立模型让系统自己学习图像的特征，这样就可以大大降低人工提取特征的误差.

本文中使用的深度学习模型是卷积神经网络(Convolutional Neural Network,CNN)[11]的架构.卷积神经网络与一般的神经网络的区别在于，卷积神经网络包含一个由卷积层和次采样层组成的特征抽取器.在卷积神经网络的卷积层中，一个神经元仅与部分相邻层的神经元连接.在CNN的卷积层,神经元平面分享相同的特征权重.卷积核通常以随机十进制矩阵的形式初始化.在网络的训练过程中，卷积核将学习获得一个合理的权重.共享权重(卷积核)的直接好处是减少网络层之间的连接性，同时减少过拟合的风险.抽样也叫池,通常用平均抽样(平均池)和最大抽样(MAX池)两种形式.次采样可以看作是一个特殊的卷积过程.卷积和次采样大大减少了模型的参数，降低了模型的复杂度.

本文参考使用了卷积神经网络中的AlexNet 网络模型，与之前的卷积神经网络(比如LeNet5等)相比优点在于:1)采用ReLU非线性激活函数，使用这种非线性激活函数比使用Sigmoid激活函数有更快的收敛速度.2)采用多个GPU编程，充分利用GPU资源加速网络训练.3)Dropout方法，相当于将多个网络叠加为一个网络，增强网络能力.4)卷积阶段的权重共享减少了参数数量，因而降低了网络模型的复杂度.5)在训练图像上采集小窗口进行训练，扩充了训练数据，减少了过拟合.

图3 Alex Net网络模型

2.2图像预处理为了便于基于深度学习的图像搜索模型进行训练和计算，我们先对图像进行预处理.通过对图像进行简单的缩放、逐样本均值削减以及白化处理，来减少图像的冗余信息.

2.2.1 简单缩放 调整图像原始数据的维度，使得缩放后图像的数据都落在[0,1]内.具体如公式为：

xi=xi/255.

(12)

其中，xi为图像像素的灰度值.

2.2.2 逐样本均值消减 对图像的数据点进行均值消除，移除图像的平均灰度值并消除数据的直流分量.设图像各个像素的灰度值为x(i)∈Rn，对图像进行零均值化:

(13)

(14)

2.2.3 白化 图像的相邻像素之间如果有很强的相关性，我们把这种相关像素信息称为冗余信息.为了去掉图像的冗余信息、降低图像特征间的相关性，对图像进行白化操作，并使得所有特征拥有相同的方差.这样有利于简化卷积神经网络的训练过程，有利于模型对图像特征的学习.设R为任意正交矩阵，并且RRT=RTR=I，令R=U，得到公式：

(15)

(16)

一般来说，当x在区间[-1,1]时，取值为ε≈10-5.在公式(15)加上ε，对输入图像而言，也起到了低通滤波的作用，消除了图像内产生的噪声，对学习到更好的特征有所帮助.

2.3算法框架总结

本文提出了一个基于深度学习和哈希算法的图像搜索算法，具体算法的流程如下.

1) 给定n个训练图片{I1，I2，...，In}，已知其相似信息来构造相似性矩阵S;

2) 将相似矩阵S作为输入，运行优化算法，得到训练图片的哈希矩阵Q;

3) 将训练图片集合{I1，I2，...，In}和哈希编码矩阵Q输入到深度卷积神经网络模型来学习哈希函数;

4) 搜索图像时将图像作为输入，获取的输出层节点上的值sign(b-0.5)即为图片的哈希码.

本文提出的算法不需要事先通过人工来提取图像的特征再进行哈希学习，只要提供数据集中原始图像就能直接学习到图像间的相似性信息并得到相应的哈希函数.

3 实验和分析

3.1实验使用的数据集为了验证本文提出的与深度学习相结合的哈希算法的性能，通过训练数据集中的图像对所提算法进行实验分析，并和主流的哈希算法做出比较.

实验对象是CIFAR-10数据集[12]，它含有6万张32×32的彩色图片，涵盖了猫、狗、车等10个类别.从CIFAR-10数据集的每一类别中随机抽取100张图片用作训练样本，其余的列为实验的图像数据库.对于无监督的哈希学习算法，将从测试集抽取的图像作为训练样本.而对于有监督的哈希学习算法，训练样本是从每个类别随机抽取的1 000张图片.

3.2多种算法的对比我们将本文提出的算法与前面提到的传统的哈希算法进行比较:1)局部敏感哈希(LSH); 2)谱哈希(SH); 3)迭代量化哈希(ITQ); 4)最小损失哈希(MLH); 5)二值重构嵌入哈希(BRE) ; 6)核哈希(KSH);

3.3实验结果分析由于本文提出的算法无需事先提取图像特征，因此可以直接将图片的像素作为算法的输入,而其他用来对比的算法，输入采用的是数据集最常用的特征.用一个512维的GIST向量[13]来表示CIFAR-10数据集中图像的特征.

表1 在CIFAR-10上使用不同哈希算法的海明排序MAP

实验中使用MAP(Mean Average Precision)作为结果的评价标准.表1是在CIFAR-10数据集上的实验结果，对比各项数据可以发现:在以MAP为评价标准的情况下，有监督哈希算法大部分的MAP都比无监督的效果要好.与所有传统的哈希算法对比，本文提出的算法图像处理的效果更好.实验证明了该算法通过深度神经网络框架结合哈希编码的方法能够在保持图像间的相似度的基础上更快的搜索出图像.

4 结 语

大规模的图像搜索通常采用近相似最近邻的方法，哈希算法在计算图像最近邻的方面具有训练速度快、存储空间小等优点，因而成为大规模图像搜索中一项关键的编码技术.但目前各种主要的哈希算法也存在着各自的不足，本文将哈希编码与深度学习中的卷积神经网络结合起来，通过选择合适的深度卷积神经网络模型来提取图像特征，优化哈希编码算法，使得提出的图像搜索算法在图像的搜索效率和效果上都得到了更好的表现.

本文提出的基于深度学习的方法仍然存在着一些问题，例如深度神经网络的设计复杂训练时间较长，所以算法的可扩展性和实用性较差.后续的研究重点可以考虑改进传统的哈希算法，并将其和优秀的深度学习模型结合起来，从而进一步提高图像搜索系统的性能.