基于内容的商品图像检索技术与系统研究
2016-05-14李灿
李灿
提出了一种新的基于商品图像的检索系统，充分利用当前学术界的一些高效算法，包括基于Hadoop平台的大数据处理技术，基于E2LSH的高维数据近邻查找技术，基于图像全局特征提取的GIST技术以及基于深度学习的卷积神经网络技术CNN。紧密结合这些新技术，在基于商品图像的检索方面取得了较好的检索效果。
1 引言
基于内容的商品图像检索作为移动互联网中一种新兴的购物方式和商品推荐方式，目前仍然处于研发阶段。相比于普通的基于内容的图像检索（如Google识图、百度识图等），它主要侧重于电商平台的商品图像检索和广告推荐。为了使其能够应用到商业平台并且为人们提供更加便捷的购物方式，这就对基于内容的图像检索提出了更高的要求。因为检索结果不仅要与被检索商品图像非常相似，而且要与被检索商品图像同属于一个类别。如用户希望查询相似的衣服，那么反馈给用户的检索结果只能是与用户查询图像相似的衣服类图像。现在是信息爆炸的时代，像阿里巴巴、京东以及亚马逊等大的电商平台同样也面临着日益增长的海量商品图像数据以及高访问量所带来的压力，显然传统的基于集中式的数据处理方式很难满足这方面的需求。而在大数据处理方面，开源的Hadoop框架是目前非常流行的分布式并行计算框架。因此，将其应用在图像数据处理方面是一个很好的选择。
位置敏感的哈希算法（Locality Sensitive Hashing，LSH）[1]是解决高维数据近似最近邻检索算法。基于内容的图像检索方法往往是将提取图像的内容特征，如纹理、颜色、形状、轮廓等转化成一个高维向量，通过检索相似的高维向量来进行图像匹配。因此，将LSH应用在基于内容的图像检索方面也是目前的一个研究热点。
基于内容的图像检索同样也存在自身的局限性，那就是太依赖图像的特征提取，图像特征提取的好坏会直接影响查询的正确率。目前虽然已经有比较多的图像特征提取算法被提出，但这方面的提取算法依然处于发展阶段。而基于深度学习的图像识别算法，如卷积神经网络（CNN）[2]在图像识别准确率上是非常高的。因此，如果将其和一般的基于内容的图像检索算法相结合，过滤掉一些非同一类别的候选结果，这样可以大大提高用户检索的准确性。
基于以上原因，提出了一种新的基于内容的商品图像检索技术及系统，并实现了基于Hadoop[3]大数据处理框架的图像检索算法。在图像特征提取方面选取经典的GIST[4]图像特征提取算法，在图像检索上选取E2LSH[5]算法，而在候选结果集的过滤上选取开源的深度学习处理框架Caffe[6]提供的CNNs图像识别算法。
2 总体框架
2.1 Hadoop框架
Hadoop是Apache共享出的一个开源的分布式计算基础架构。在该平台上提交上来的计算任务被称之为“Job”。而这些“Job”又会被分割为一个个的“任务（Task）”。通过将这些分割出来的“Task”分发到不同的集群节点中实现分布式并行计算，可以大大地提高“Job”的处理速度。而HDFS则是Hadoop提供的一个分布式文件系统，用于数据的存储。在数据处理方面提供了MapReduce的编程模型。
（1）分布式文件系统HDFS
HDFS是Hadoop的一个分布式文件系统，由于它具有存储容量大、容错能力强、吞吐量高等特点同样也得到了一些其它的分布式计算平台的支持。HDFS主要采用主/从（Master/Slave）的结构模型，在HDFS中有两个非常重要的组成部分，一个是主要负责整个分布式文件系统的命名空间，存储文件的元数据和集群中各个节点与数据块之间的映射。通过“心跳机制”监控着集群中各个节点的存储情况，将其称之为“NameNode”节点；另一个是“DataNode”，它主要负责存储用户数据，数据在这些节点中均以块的形式进行存储。
在HDFS中，当用户提交存储数据之后，这些数据均会被划分成块的形式，然后分发保存在集群中不同的“DataNode”中。
（2）MapReduce编程模型
MapReduce是Hadoop提供的处理海量数据的分布式编程模型和并行计算框架。在MapReduce编程模型中，用户只需要将主要精力放在Map（）方法和Reduce（）方法的设计上，同时Map阶段将以块形式输入的数据按照
在MapReduce模型中同样运用到了“分而治之”的思想。其中，通过JobTracker将用户提交的作业分割成多个任务并分配给TaskTracker执行。MapReduce框架采用“移动计算优于移动数据”的理念，计算的执行应该尽量存储在有相关数据的DateNode中，这样做可以节省宽带资源。
2.2 图像的全局特征GIST
本系统所处理的数据都是一些背景比较简单的商品图像，因此本系统选用提取图像全局特征的方式来表征图像，即图像的GIST特征。这种方式所描述的是图像的一些比较宏观的信息，提取出来的GIST特征向量主要由图像的开放度、粗糙度、自然度、膨胀度和险峻度5个维度信息组成，并不考虑图像的一些局部特征信息，如SIFT算法需要提取非常多的图像局部特征信息。
2.3 LSH
令q∈B（o，s）={q∈Rd|‖o，q‖≤s}记作以数据对象o∈D为中心，半径为s的超球体。因此，LSH函数定义如下：
其中，P[h（o）=h（q）]表示对象o和q落入相同桶中的概率，c>1和p1>p2。此外，组合的哈希函数表示成g=（h1， … ， hk），其中h1， …， hk是从LSH哈希函数族中随机抽取的k个距离敏感函数。根据文献[18]，一个用以构造适用于l2距离度量的LSH函数家族的形式如下：
其中，o为数据对象o∈Rd的向量表示；a为每个维度均符合随机分布，从标准正态分布中抽取的d维向量；w是一个常数代表，划分出桶的宽度；b是随机地从均匀分布[0， w）中抽取的实数。
一个LSH函数ha，b（o）哈希过程如下：首先，把数据对象o投影到以向量a表示的一维空间上；再把o的投影移动b的长度；最后把a以宽度w划分成多个区间；返回o经过投影后所得的桶号。令s=‖o1，o2‖，表示对于任意两个数据对象o1和o2的距离，则o1和o2在LSH函数ha，b（o）作用下产生碰撞的概率p（s）为：
对于给定的桶宽w，碰撞概率p（s）随着s的增大而减小。因此，哈希函数ha，b是（s， cs， p1， p2）敏感的，其中p1=p（s），p2=p（cs）。当s=1时，该函数为（1， c， p1， p2）敏感，且p1=p（1），p2=p（c）[7]。
2.4 卷积神经网络
卷积神经网络是人工神经网络的一种。与其它神经网络不同的是，这种网络采用的是权值共享的方式，与生物神经网络更相似。通过这种设计不仅可以使模型的复杂度降低，而且使网络权值的数量也大大地减少。在卷积神经网络中，可以直接对图像数据进行处理，而无需像传统神经网络算法那样对数据进行特征提取和重新构建，往往这些过程需要耗费非常大的开销。因此，在卷积神经网络中，相比于传统的神经网络，模型的训练速度是很快的。通过卷积神经网络中多层感知器的构造方式可以对一些结构平移的图像、比例不同的图像或者图像内容有倾斜的图像都有较高的容忍能力。
CNNs利用权值共享的方式减少需要学习的参数数目，和一般前向BP[8]算法相比，使得训练速度和准确度得到了极大的提高。CNNs作为一个深度学习算法，可以使数据的预处理开销达到最小化。在该算法中，作为层级结构的最低层的输入只是图像的一小部分（即局部感受区域或者视野感受子），经过处理后的信息再传输到更深的层次，每层会通有滤波器来取得上层输入的观测数据特征。
图1展示了在卷积神经网络中，网络组成以及图像数据在各个层次网络中的转化，其中C1层称之为特征映射层。在特征映射层中，图像数据会以每5个像素为一组进行求和以及加上权值和偏置，然后通过符号函数得到S1层，即滤波层。通过对S1层进行滤波得到C2层。然后通过重复之间的处理方式一直到得到S4层。最终，这些像素值被光栅化并通过BP全连接网络得到最终的输出。
卷积过程如图2所示，包括用可训练的滤波器fx对输入的图像进行卷积，并且通过与偏置bx求和，得到卷积层Cx。在子采样过程中，通过对每4个像素的邻域求和转化成一个像素，然后通过与标量Wx+1进行运算，再加上bx+1偏置，最后通过一个符号函数，产生一个大概缩小四倍的特征映射图Sx+1。
3 系统流程图及各个部分的实现
图3展示了本系统中索引文件的建立过程和用户在线查询过程的流程图。整个系统划分为两个部分。首先是离线建立索引阶段；其次便是在线查询阶段。这也与一般的基于Web的服务相同。从流程图也可知，整个系统的核心分为以下几个部分：一是基于GIST图像特征的E2LSH算法和Hadoop平台索引文件的建立；二是CNN算法的实现。下面将从这两个方面对该系统进行介绍。
3.2 基于图像GIST特征的E2LSH算法
图像的GIST特征是图像的全局特征信息，并不像SIFT特征那样具有多样性。一幅图像只能提取出一个GIST特征向量，并且以高维特征向量（维数都超过10维）来表示。由于“维度灾难”的原因，并不适合选用KD-tree、R-tree等树形索引结构来对这些高维数据进行检索。
E2LSH算法是近似最近邻检索算法，并且在维度很高的情况下比一般的树形结构的检索算法效果更加明显。本算法将其应用到了基于图像GIST特征的检索上。基于图像的GIST特征的E2LSH算法主要包括两个阶段，分别是创建索引文件阶段和离线图像检索阶段。
（1）创建索引文件阶段
由于本算法是基于Hadoop分布式并行处理框架，所以在创建索引文件阶段需要首先将图库图像数据集存储到Hadoop分布式文件系统HDFS中，然后对这些图像进行GIST特征提取，提取出来的GIST特征向量保存到HDFS文件上。由于数据量较大，这些数据会以块的形式被单独保存到各个节点中。
特征向量的数据格式为<图像名， 高维特征向量>的键值对形式。每一行保存一幅图像的图像名和特征向量对。图像名不仅包含图像的文件名同时也包含图像在HDFS文件系统中的逻辑路径，方便后续阶段取出图像源文件。高维特征向量则使各个维度之间以空格的形式保存。同时图像与特征向量之间以“，”进行标识。
将这些数据保存在HDFS上后，便可以用E2LSH位置敏感的哈希函数对这些特征向量建立索引。通过将图像GIST高维特征哈希到相同的哈希桶中，并保存到以桶号所代表的文件中，使得图像集中原本比较相似的图像保存到一起。
经过LSH函数后高维GIST特征向量变成一维哈希桶号，但是准确率和查全率并不高。因此，为了提高算法的准确率和查全率，E2LSH算法对位置敏感的哈希函数的使用进行了改变。将每一幅图像改为使用由k个h（o）组成的g（o）函数，其中g（o）=
在单个g（o）中，每幅图像被映射成一个k维的组合哈希桶号，这可能会使很多原本相似的图像得到不相近的k维索引值，从而使得算法的查全率降低。为了解决这个问题，可以通过使用L个g（o），即G=（g1， g2， …， gL）来创建L个索引表。这样在查询的时候通过多个索引表之间的“OR”操作可以避免“AND”操作所导致的假阴性增大的问题。
其中每一行保存着一个k维索引值代表“AND”之后的组合哈希桶号以及其中所保存的图像名列表（其中图像名代表的是图像的绝对路径）。
（2）基于开源Caffe框架CNNs的实现
本系统在图像识别上采用的是目前非常流行的伯克利实验室的Caffe开源深度学习框架，即6层的深度学习算法CNN。其中训练图片在各个层次中的转化如图4所示。
图4展示了在CNN算法中经过各个层次的特征提取C层或者滤波S层后输出的图像数据。其中每幅图片只是对结果中的一部分进行展示。如第一层特征提取层的输出C1有256个，只显示了前36个特征提取进行显示。一层过滤器S1有256个，其中每个尺寸为5×5×48像素，只显示前48个过滤器，每个通道分别显示，使每个过滤器是一排。其中第五层为采用BP算法的全连接层。最终输出结果用直方图进行展示，如图5所示。
最终的预测结果如图6所示，其中横轴坐标为类别（有1000个类别），按照相似图表示成柱状图。
得到预测的类别图后，取其中最相似的类别进行输出，结果如表2所示：
4 实验数据及结果
4.1 Hadoop分布式环境的部署
Hadoop部署在4台Ubuntu12.04的Linux操作系统PC机上。其中，Hadoop的主服务器（即Master节点）运行NameNode、JobTracker进程；其余作为Hadoop的工作节点（即Slave节点），运行着DataNode和TaskTracker等进程。
4.2 实验的图像数据集以及开发工具
在图像检索中有很多评价方式，常见的评价测度包括查全率（Recall）和准确率（Precision），本文采用比较常用的评价测度方式。如对于一幅查询图像，根据检索返回的结果的正确性将其标记为4种类型：假阳性FP（False Positive）、真阴性TN（True Negative）、真阳性TP（（True Positive）、假阴性FN（False Negative）。根据以上概念，可以得到Precision和Recall的计算公式定义为：
其中符号代表该项结果的数据个数，TP和FN的和是数据库所有相关图片的总数。其中，FP的含义是检索判定为相似图像，但实际上这些结果与查询图像却并不相似；TP的含义是检索为相似的图像，实际上与查询图像也不相似；FN的含义是检索为不相似图像，但实际上这些结果与查询图像是相似的；TN的含义是检索为不相似的图像，实际上这些结果与查询图像的确不相似。
本文采用的三个实验数据集分别来自：（1）ImageNet[9]：这是一个计算机视觉系统识别项目，是目前世界上图像识别最大的数据库，是美国哈佛的计算机科学家模拟人类的识别系统建立的。从中挑选出了具有商品图片性质的1000幅图片作为实验数据集。（2）Flickr[10]：Flickr是目前世界上最好的线上相片管理和分享应用程式之一，从中挑选出了1000幅图像作为实验数据集。（3）来自于亚马逊商城[11]收集的商品图片2000幅。实验图片在选取过程中主要集中于鞋子、衣服、皮包、首饰等类别。
从实验（1）和实验（2）可以看出：k值越大，查准率普遍升高，其中Shoes的查准率由62%升到了86%，Leather Bag由85%升到100%；但是查准率提高的同时，查全率下降的也比较明显，Clothes的查全率由66%下降到43%，Bag的查全率由55%降到29%；如果k值较小，查找到的图片总数量会很多，但准确率会下降，因为其中不相似的图片数量也会增多，而查全率会升高。
从实验（1）和实验（3）可以得出，随着L值的减小，准确率和查全率都呈下降趋势。因此，从上述实验结果得出，L值和k值也不能很大，随着L值的增大，虽然会使算法的查全率和准确率相应地提高但会使索引文件的数量增多，增加查询时间的开销；对于k值，随着k增大，算法的准确率会提高，但又会降低算法的查全率。参数L值和k值的选取需要通过实验进行优化。
5 结束语
本文主要研究了基于内容的商品图像检索系统并将其应用到了Hadoop分布式计算平台上，详细地描述了系统的实现以及所用到的核心技术。其中，基于Hadoop图像GIST特征的E2LSH算法是检索相似商品图像的算法；基于Caffe的CNNs深度学习算法是开源高效的图像识别算法。通过Hadoop的MapReduce编程模型实现了E2LSH算法，生成图像的索引文件并保存在Hadoop的HDFS文件系统中。算法的实现主要分为两个阶段，一是创建索引文件阶段，另一阶段即为离线查询阶段。通过实验对算法中所涉及的各个参数进行优化，本文进行了大量的实验来测试本系统的效果，并对实验结果进行了分析对比。
通过实验可以发现，在图像的检索阶段通过采用E2LSH的近似最近邻检索算法可以加快候选集的检索速度，然后通过CNN的深度学习算法可以过滤掉候选集中和被检索图像不属于同一个类别的图像，从而大大提高了检索的正确率。这也说明了该系统在基于内容的商品图像检索上的有效性。
参考文献：
[1] Gionis A， Indyk P， Motwani R. Similarity Search in High Dimensions via Hashing[A]. Proc of the 25th International Conference on Very Large Data Bases， 1999： 518-529.
[2] Roska T， Chua L O. The CNN universal machine： an analogic array computer[J]. IEEE Transactions on Circuits & Systems II Analog & Digital Signal Processing， 1993，40（3）： 163-173.
[3] Chansler R， Sunnyvale Y. The Hadoop Distributed File System[J]. IEEE Symposium on Mass Storage Systems & Technologies， 2010（11）： 1-10.
[4] Oliva A， Torralba A. Modeling the shape of the scene： A holistic representation of the spatial envelope[J]. International journal of computer vision， 2001，42（3）： 145-175.
[5] Datar M， Indyk P， Immorlica N， et al. Locality-Sensitive Hashing Scheme Based on p-Stable Distributions[J]. SoCG， 2004（2）： 253-262.
[6] Sun Y， Wang X， Tang X. Deep learning face representation from predicting 10，000 classes[A]. Computer Vision and Pattern Recognition （CVPR）， 2014 IEEE Conference on IEEE， 2014： 1891-1898.
[7] Tao Yu fei， Yi Ke， Sheng Cheng， et al. Quality And Efficiency In High Dimensional Nearest Neighbor Search[A]. Proc of the 35th SIGMOD international conference on Management of data， 2009： 563-575.
[8] STUIVER M， REIMER P J， BARD E， et al. INTCAL98 radiocarbon age calibration， 24 000-0 cal BP[J]. Radiocarbon， 1998，40（3）： 1041-1083.
[9] Krizhevsky A， Sutskever I， Hinton G E. ImageNet classification with deep convolutional neural networks[J]. Advances in neural information processing systems， 2012（2）： 1097-1105.
[10] Sawant N， Li J， Wang J Z. Automatic image semantic interpretation using social action and tagging data[J]. Multimedia Tools & Applications， 2011，51（1）： 213-246.
