概述
电商场景中，卖家为获取流量，常常出现重复铺货现象，当用户发布上传图像或视频时，在客户端进行图像特征提取和指纹生成，再将其上传至云端指纹库对比后，找出相似图片，杜绝重复铺货造成的计算及存储资源浪费。
该方法基于图像相似度计算，可广泛应用于安全、版权保护、电商等领域。
摘要
端上的图像相似度计算与传统图像相似度计算相比，对计算复杂度及检索效率有更高的要求。本文通过设计实验，对比三类图像相似度计算方法：感知哈希算法、基于局部不变性的图像相似度匹配算法以及基于卷积神经网络的图像相似度算法，权衡其在计算复杂度及检索效率方面的优劣，最终选取 Hessian Affine进行特征提取，SIFT特征描述生成指纹，作为端上的图像相似度计算模型。
关键词：图像相似度计算、特征提取、计算复杂度、检索效率
图像相似度计算在当前的云计算处理方式，会将客户端数据上传至云端，进行图像、视频检索相似度计算等一系列复杂逻辑处理后将结果反馈给终端，虽然在计算能力上云端优势明显，但该方式同时存在严重的存储、计算资源及流量的浪费且无法满足实时性要求。
随着手机计算能力的提升，一种显而易见的方式是将部分数据在客户端进行处理后，再将有价值的数据上传云端存储及进一步处理。对于电商场景中的重复铺货现象，可在用户发布上传图像、视频时，在客户端进行图像相似度计算，做到实时反馈，对于重复图像及视频不进行云端存储，避免了存储及计算资源的浪费。
图像检索算法的基本步骤包括特征提取、指纹生成和相似度匹配。业界常用的图像相似度计算方法大致分为三类，传统的感知哈希算法、基于局部不变性的图像相似度匹配算法以及利用深度学习算法进行的图像相似度计算方法。
1．传统的hash算法
自2011年百度借助TinEye发布百度识图后不久，google发布了类似的以图搜图图片搜索服务，“感知哈希算法”在图像搜索过程中发挥了重要作用。大致流程如下：
1.1感知哈希算法理论简介：
1.1.1均值hash:
通过对原始图像进行压缩（8*8）和灰度处理后计算压缩后的图像像素均值，用8*8图像的64个像素与均值对比，大于均值为1，小于均值为0，得到得64位二进制编码即为原图像的ahash值。算法速度快，但精确度较低。
1.1.2差异hash：
与均值hash相比，差异hash同样要进行图像压缩和灰度处理，然后用每行的前一个像素与后一个像素对比，大于为1，小于为0，来生成指纹信息。算法精确度较高，速度较快。
1.1.3感知hash：
通过对原始图像进行压缩（32*32）和灰度处理后计算压缩，对其进行离散余弦变换后，用32*32图像的前8*8像素计算均值，8*8像素值大于均值为1，小于均值为0，得到64位指纹信息为原始图像的phash值。算法精准度较高，速度较差。
根据以上三种算法可计算出两张图像响应的hash值，利用两张图像hash值得汉明距离，可判别出其相似程度，其中汉明距离越大，相似度越低，汉明距离越小，相似度越高。
1.2各个算法之间的抗干扰能力对比
从视频内容中选取两组测试集，通过设计抗干扰能力实验，对三种经典感知哈希算法进行对比。
测试集1：
结果对比
测试集2
结果对比
通过实验结果发现Hash在图像相似度计算上，准确度较低，无法满足实际业务需求。
2．利用卷积神经网络计算图片相似度
2.1 端到端的方式
利用卷积神经网络计算相似度时，一种方法是直接采用端到端的方式，利用卷积层提取两张图片的特征，再用全连接层输出两张图片的“匹配度”。可参考[1] 2015年CVPR文章： 《Learningto Compare Image Patches via ConvolutionalNeural Networks》，相关中文解释可参考[2] ：http://blog.csdn.net/hjimce/article/details/50098483
该方法对于少量图像相似度计算优势明显，但不适用于从大量图像中进行相似度匹配的场景，如视频检索。通常，视频检索大致步骤如下：
假设视频库中的存量视频有1万个，每个视频抽取10张图片，则帧库有10万张图片，一次视频查询需要的比对次数为：10 x 100000 = 100万次。
因此，尽管该方法对于图像相似度计算有较高的准确性，但在进行视频检索时计算量过大。
2.2 提取中间产物方式
由于卷积操作的本质即为特征提取，卷积层输出的矩阵天然代表各种特征，
通过对两张图片的特征矩阵进行相减，计算差值平方和（或者其他方式）得到的数值作为两张图片的相似度判断依据，即为利用卷积神经网络进行图像相似度计算的第二种方式。
利用预训练好的VGG16模型来做测试，网络结构如下（不带全连接层）：
以block5_pool 输出的结果做为目标产物（也可以用其它层），可以看到这一层输出的是形状为(7,7,512) 的矩阵,我们先用一组图片（来源网络）做测试，来验证输出的结果是否大致符合预期：
以上六张测试图片分别为：原图、加少量文字、修改少量底部、底部裁剪、修改底部一半、完全不同的另一张图片。
对每张图片用卷积模型计算得到7x7x512 形状的数组后，分别计算第一张图片与后面五张图片的特征数组差值的平方和，并将结果归一化处理以方便观察，结果如下：
Diff 1 - 2: 2
Diff 1 - 3: 128
Diff 1 - 4: 182
Diff 1 - 5: 226
Diff 1 - 6: 377
从观测结果中可以看出，第一张图片与其后的图片差异越来越大的。并且2和377 这两个值代表非常相似和完全不同的图片，具有一定辨识度。
进一步设计实验，用视频测试裁剪、加字幕、亮度调整、旋转、以及完全不一样的另一个视频等抗干扰能力。
针对视频的diff计算方式为：每个视频每隔1秒抽一帧图片，循环比对两个视频每个对应位置的图片帧，计算差异值，最后除以帧数得到平均差异。对于两个帧数不一致的情况，以较少帧为准，多出来的帧不处理。图片间的差异值计算方式同上，结果如下：
Diff 0 - 1: 6
Diff 0 - 2: 4
Diff 0 - 3: 2
Diff 0 - 4: 22
Diff 0 - 5: 26
从实验结果可以看出，对于裁剪、字幕、亮度调整的情况，差异值都在同一个数量级上，明显小于不同视频的情况，但是对于旋转的情况，该方法无效。
3．基于局部不变特征的相似度匹配算法
除了基于哈希和基于卷积神经网络的相似度匹配算法外，局部特征检测算法在相似度计算、图像检索、物体识别等领域具有重要意义。相对于像素级的全局特征，局部特征在描述图像特征时更加灵活，其中SIFT（Scale-invariant feature transform）是比较常用的，具有较好的尺度不变性，即使改变旋转角度或者拍摄角度，仍然能够得到较好的检测效果。
3.1抗干扰能力测试
用opencv+python，对测试图片提取SIFT特征：
进一步测试同样的裁剪、旋转等情况的特征点匹配情况：
裁剪：
字幕+改变大小：
亮度调整：
旋转90度：
不同视频：
从测试结果上看，SIFT做特征检测具有良好的抗干扰能力。
3.2 检索效率测试
初步确定采用局部不变特征来做特征提取后，需要做进一步的测试：搭建测试集，构建特征提取、检索系统，以测试准确率、召回率等指标。通过参考2017 年Araujo 和 BerndGirod的论文：《Large-Scale Video Retrieval Using ImageQueries》，基于其工程进行测试。
数据集准备：
1.图片库：取线上1000个视频，对每个视频每隔1秒抽一张视频帧图片，作为总图片库。
2.待查询图片：定义7种图片变换方式：旋转、拉伸、调整亮度、裁剪、加字幕、无处理，每种变换生成100个样本。每个样本的生成方式为：从1000个视频里随机选取一个视频，并从所有图片帧里随机取一帧。这样总共得到700个待查询图片。
局部特征提取包含两部分内容：特征点检测和特征点描述。
3.2.1 SIFT特征提取+SIFT描述子
对所有的库存图片以及待查询图片用SIFT提取特征，并利用特征从检索库里检索700个测试样本，计算召回率和准确率如下：
结果显示准确率较低，通过观察错误结果发现，部分图片提取到的特征数目较少，甚至只有个位数，而正常图片能达到几百到上千个特征点，特征点缺失会导致检索时易匹配到错误的样本。通过设置“最低样本数”限制，当样本数大于阈值时，认为其查询结果“可信”。
经测试，将“最低样本数”阈值定为30，并加入“排除率”指标，表示未达到最低样本数，该查询记录不可信。将特征数太少的样本排除后，再次测试结果如下：
结果显示在增加了“最低样本数”和“排除率”指标后，准确率大幅度提升，但仍有20% 左右的排除率，即有五分之一的查询是没有返回可信结果的。
3.2.2 Hessian Affine特征提取+SIFT描述子
为进一步提升准确率，参考[4]工程描述，将SIFT特征点检测换成Hessian-Affine特征检测会有更好的效果，即先用Hessian-Affine检测特征点，后用SIFT描述子描述特征。换用Hessian-Affine后，测试结果如下；
结果显示，召回率和准确率均有所提升，且排除率降至4%。
4. 结论
通过设计实验测试结果发现，基于局部不变特征做相似度计算具有良好的抗干扰能力，准确度优于传统感知哈希算法，对旋转不变性的支持优于卷积神经网络。最终权衡计算复杂度和检索效率，在端上选取Hessian-Affine做特征点检测，SIFT做描述子的方式进行图像相似度计算。
5. 趋势展望
尽管基于局部特征不变性的图像相似度计算在抗干扰能力及计算复杂度上占优，但仅能表达图像浅层特性，而卷积神经网络具有多层次语义表达能力，不同层所提取的图像特征具有不同含义，低层次表达角点特征，中间层聚合角点特征表达物体部件，高层进一步表达整个物体，选择不同卷积层会提取出不同层次的特征。在计算复杂度及检索效率高要求的客户端将局部特征提取与卷积神经网络相结合互相弥补不足，突出优势，可能会带来更好的效果，未来将进一步探索。
参考文献：
[1] 2015 CVPR《Learning to Compare Image Patches viaConvolutionalNeural Networks》
[2] http://blog.csdn.net/hjimce/article/details/50098483
[3] Araujo, A. and Girod, B 《Large-Scale Video Retrieval Using ImageQueries》2017
[4] https://github.com/andrefaraujo/videosearch.
加入闲鱼，一起玩些酷的。（阿里巴巴集团闲鱼官方技术号，欢迎同道者技术交流。） 简历投递：guicai.gxy@alibaba-inc.com
理论 CNN 哈希算法 图像压缩 深度学习 物体识别
相关数据
Neural Network
（人工）神经网络是一种起源于 20 世纪 50 年代的监督式机器学习模型，那时候研究者构想了「感知器（perceptron）」的想法。这一领域的研究者通常被称为「联结主义者（Connectionist）」，因为这种模型模拟了人脑的功能。神经网络模型通常是通过反向传播算法应用梯度下降训练的。目前神经网络有两大主要类型，它们都是前馈神经网络：卷积神经网络（CNN）和循环神经网络（RNN），其中 RNN 又包含长短期记忆（LSTM）、门控循环单元（GRU）等等。深度学习是一种主要应用于神经网络帮助其取得更好结果的技术。尽管神经网络主要用于监督学习，但也有一些为无监督学习设计的变体，比如自动编码器和生成对抗网络（GAN）。
来源：机器之心
Convolutional neural network
卷积神经网路（Convolutional Neural Network, CNN）是一种前馈神经网络，它的人工神经元可以响应一部分覆盖范围内的周围单元，对于大型图像处理有出色表现。卷积神经网路由一个或多个卷积层和顶端的全连通层（对应经典的神经网路）组成，同时也包括关联权重和池化层（pooling layer）。这一结构使得卷积神经网路能够利用输入数据的二维结构。与其他深度学习结构相比，卷积神经网路在图像和语音识别方面能够给出更好的结果。这一模型也可以使用反向传播算法进行训练。相比较其他深度、前馈神经网路，卷积神经网路需要考量的参数更少，使之成为一种颇具吸引力的深度学习结构。 卷积网络是一种专门用于处理具有已知的、网格状拓扑的数据的神经网络。例如时间序列数据，它可以被认为是以一定时间间隔采样的一维网格，又如图像数据，其可以被认为是二维像素网格。
来源：Goodfellow, I.; Bengio Y.; Courville A. (2016). Deep Learning. MIT Press. 维基百科
Logic
人工智能领域用逻辑来理解智能推理问题；它可以提供用于分析编程语言的技术，也可用作分析、表征知识或编程的工具。目前人们常用的逻辑分支有命题逻辑（Propositional Logic ）以及一阶逻辑（FOL）等谓词逻辑。
来源：机器之心
Image compression
图像压缩是数据压缩技术在数字图像上的应用，目的是减少图像数据中的冗余信息，从而用更加高效的格式存储和传输数据。图像压缩可以是有损数据压缩也可以是无损数据压缩。
来源： 维基百科
object recognition
计算机视觉领域的一个分支，研究物体的识别任务
perception
知觉或感知是外界刺激作用于感官时，脑对外界的整体的看法和理解，为我们对外界的感官信息进行组织和解释。在认知科学中，也可看作一组程序，包括获取信息、理解信息、筛选信息、组织信息。与感觉不同，知觉反映的是由对象的各样属性及关系构成的整体。
来源： 维基百科
Deep learning
深度学习（deep learning）是机器学习的分支，是一种试图使用包含复杂结构或由多重非线性变换构成的多个处理层对数据进行高层抽象的算法。 深度学习是机器学习中一种基于对数据进行表征学习的算法，至今已有数种深度学习框架，如卷积神经网络和深度置信网络和递归神经网络等已被应用在计算机视觉、语音识别、自然语言处理、音频识别与生物信息学等领域并获取了极好的效果。
来源： LeCun, Y., Bengio, Y., & Hinton, G. (2015). Deep learning. nature, 521(7553), 436.
Discrete cosine transform,
离散余弦变换（英语：discrete cosine transform, DCT）是与傅里叶变换相关的一种变换，类似于离散傅里叶变换，但是只使用实数。离散余弦变换相当于一个长度大概是它两倍的离散傅里叶变换，这个离散傅里叶变换是对一个实偶函数进行的（因为一个实偶函数的傅里叶变换仍然是一个实偶函数），在有些变形里面需要将输入或者输出的位置移动半个单位（DCT有8种标准类型，其中4种是常见的）。
来源： 维基百科
Accuracy
分类模型的正确预测所占的比例。在多类别分类中，准确率的定义为：正确的预测数/样本总数。 在二元分类中，准确率的定义为：(真正例数+真负例数)/样本总数
Cloud Computing
云计算（英语：cloud computing），是一种基于互联网的计算方式，通过这种方式，共享的软硬件资源和信息可以按需求提供给计算机各种终端和其他设备。
来源： Cloud Computing
以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持 码农网
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
Scalability Rules
Martin L. Abbott、Michael T. Fisher / Addison-Wesley Professional / 2011-5-15 / USD 29.99
"Once again, Abbott and Fisher provide a book that I'll be giving to our engineers. It's an essential read for anyone dealing with scaling an online business." --Chris Lalonde, VP, Technical Operatio......一起来看看 《Scalability Rules》 这本书的介绍吧!
