图片相似性匹配中的特征提取方法综述

stevenmiao(苗捷)，2016年7月博士毕业于华南理工大学，应届毕业加入TEG信息安全部。八年计算机视觉算法经验，博士期间主要研究面向视频的特征提取和内容识别算法。入职以来主要负责部门内基于大规模图像和视频检索、匹配的恶意内容过滤算法。

一、引言

图片相似性匹配，即对比两张图片的相似程度，可以用于图片搜索、聚类、版权保护、恶意图片过滤等应用。本文主要介绍用于图片相似性匹配的特征各类特征提取方法。对于图片的相似性匹配，可根据匹配的形式分为四个层次，分别概括如下：

1.像素级别相似：两张图片每个对应像素值完全相等，直接表现就是两张图片文件在二进制内容上完全一致。

2. 全局视觉相似：两张像素级相似的图片分别经过缩放和压缩等操作后，其对应像素值也因为缩放或压缩导致一定变化，但视觉上保持一致。

3. 局部视觉相似：两张全局相似的图片因为裁剪、拼接、PS等不再全局相似，但仍然能够在两张图片中各自找到一个局部区域，这两个局部区域在视觉上基本保持一致。

4. 语义级别相似：两张图片所表达的内容在视觉上差异较大，甚至完全没有视觉相似区域，但在语义内容上相似。

上述四个相似层次在信息的对比上由精确到抽象，需要的相似性匹配算法也由简单到困难。然而这里需要指出的是，这四个层次的相似性在各类应用场景中都由其独特的作用，无法互相取代。除了像素级相似可以直接通过简单的计算数据MD5等方法来解决，其他几个层次的图片相似性匹配都需要引入计算机视觉算法，即进行图片的特征提取后通过图片特征进行对比。下面本文着重介绍用于各个层次图片相似性匹配技术的特征提取方法。

二、图片相似性匹配中的特征提取

2.1 全局视觉相似

两张像素级相似的图片经过缩放和压缩等操作后，视觉上保持基本一致，但图片本身的像素值数据差异较大。此类图片相似性可以使用图片的全局特征或图片哈希（Image Hashing）算法来解决。相关算法从简单的Perceptual Image Hash[1]到经典的全局特征GIST特征[2]，再到近期各类基于机器学习的图像哈希算法[3]–[5]，在功能、复杂度、应用场景等方面等具有较大差异。

虽然现存图形哈希算法众多，但均围绕着两个核心特性进行调整和改进，即鲁棒性和区分性（Robustness and discrimination）。具有高鲁棒性的算法会将具有较大差异的图片判断为一致，常规应用中我们希望特征能够对图像缩放、有损压缩、全局色调变换，甚至图片旋转和平移等具有较强的鲁棒性，即这些操作都对最终图片产生的特征没有影响。另一方面，区分性的是对图片的分辨能力的要求，例如对两张图片中文字内容的差异，色彩不一致等的分辨能力。

实际应用中，通常要求算法具有缩放、有损压缩、旋转等鲁棒性，但在其他方面的鲁棒性和区分性上有灵活的要求。举例而言，某些情况下用户希望算法能够分辨图片中额外添加的文字，即具有较高的区分性；而某些情况下用户希望算法对两张照片中有少量的文字差异不敏感，即具有较高的鲁棒性。因此，介于各类灵活多变的应用场景，当前并没有最好的算法，只有特定应用场景上最合适的算法。

2.2 局部视觉相似

两张图片中只有局部区域相似的情况下，此类相似大多无法通过简单的图片哈希或全局特征来进行比较，而需要引入具有局部不变性的图片特征来进行相似性匹配，经典的特征提取算法包括SIFT (Scale-Invariant Feature Transform)算法[6]、SURF(Speeded-Up Robust Features)算法[7]等、ORB（Oriented FAST and Rotated BRIEF）算法[8]等。

自2004年David Lowe提出SIFT特征[6]以来，各类用于图像匹配的局部不变性特征相继被提出。原始的SIFT特征具有旋转、尺度等不变性，此外对于各类仿射变换也具有良好的鲁棒性。在保证特征的效果的前提下，SURF特征[7]在SIFT特征的基础上进行了优化改进，实际应用中SURF特征提取的耗时只有SIFT特征提取耗时的三分之一。

值得一提的是，SIFT和SURF均已被注册专利，因此知名的计算机视觉算法库OpenCV的开发团队研发了ORB特征[8]。具体的，ORB特征通过将FAST特征点检测算法[9]与BRIEF特征点描述算法[10]结合，并引入了旋转不变性和多尺度，ORB特征在图像匹配邻域被广泛应用，其速度比SURF快数倍。ORB特征与SIFT和SURF特征相比有一个重要不同之处，即在于ORB特征是二值化特征，基于Hamming距离进行相似性比较，而SURF和SIFT特征则是基于欧氏距离的。因此，ORB特征在实际的匹配和检索应用中速度也更快。

上述几种局部特征均在线性尺度空间进行，近年来被提出的AKAZE算法[11]直接从非线性尺度空间进行特征提取，在理论上能够更好的解决尺度变化问题，但在速度方面不理想，实际使用与SURF和SIFT相比也没有压倒性优势。一些学者对各类局部不变性特征提取方法进行了系统性的分析对比，具体可以参考文献[12], [13]。

2.3 语义级别相似

两张图片在视觉上差异较大，但所表达的语义内容相似，即语义级别相似。此类问题一直被广泛研究，还没有得到完善的解决。从早期基于词带模型（BOW: Bag of Visual Words）的语义级别的图像相似性匹配，到当前基于深度学习的各类算法，近年来针对此类问题学术界已经取得了长足的进步。

相比于视觉级别的图片相似，语义级别相似的定义更加泛化，相应用于解决语义级别图像相似性匹配的方法也更加复杂。

在基于深度学习的方法出现之前，语义基本的图像相似性描述主要以基于词带模型模型的图像检索（Image Retrival）的形式出现[14]–[16]。具体的，首先在图片中提取局部不变性特征，然后将不定量的局部不变性特征通过词带模型转化为定长的语义特征，再根据特征的度量进行语义级别的相似性匹配。

自2012年基于卷积神经网络（CNN: Convolutional Neural Network）的深度学习（Deep Learning）方法在ImageNet数据集上取得突破性的进展[17]后，深度学习就被广泛应用于各类计算机视觉应用[18]–[20]，从传统的图像处理应用如去雾、超分辨率重建、压缩编码、分割等到复杂的图像识别、检测、跟踪等应用，学术界均提出了很多基于深度学习的方案，效果显著。时至今日，卷积神经网络已经取得了长足的发展，各类网络结构层出不穷[18]–[20]。卷积神经网络能够通过多层的特征提取机制将图片的像素信息进行层次化的抽象和描述，在网络的前半部分形成描述局部的底层特征，中间部分形成感受野较大且具有一定抽象能力的中层特征，在后半部分形成对整张图片具有较强抽象能力的语义特征。综上，卷积神经网络的这个特性可以被良好的应用于语义级别图像相似度的匹配。

与传统方法不同的是，基于卷积神经网络的方法可以监督性的对图片相似性进行训练，具体的，可以提供若干对相似/不相似的图片，基于这些图片的相似性作为网络的训练目标，针对性的进行特征提取环节的训练和优化，常用的相似性对比的损失函数主要包括Constrative Loss和Triplet Loss等。当前基于深度学习的图像相似性匹配的研究热点主要集中在如何通过监督性训练的方法得到紧凑且易于检索的特征表达[21], [22]。紧凑的特征可以减小存储的空间，并减少匹配和检索的计算量，但同时紧凑的特征对于特征的鲁棒性和区分性提出了更高的挑战。当前的经典方法是直接将图片通过神经网络的训练量化为哈希值，并通过Hamming距离进行相似性对比[22], [23]，此类方法其主要的难点在于特征的量化约束等。

总结

本文将图片的相似性从不同的抽象层次归纳为四个级别，即从精确的视觉相似到局部的、抽象的语义相似，并介绍了不同层次相似性匹配的常用特征提取方法。在实际业务场景中，不同的应用需要不同抽象形式的相似性匹配标准，且需针对具体的业务需求进行算法的选择和优化，且需要额外考虑特征提取、匹配等环节的时间和空间复杂度。由其在需要大规模检索和匹配的应用场景中，更需要额外考虑与特征相配合的快速检索算法。

Reference

[1] C. Zauner, “Implementation and Benchmarking of Perceptual Image Hash Functions,”Rev. Music. Chil., vol. 65, no. 215, pp. 71–72, 2010.

[2] C. Siagian and L. Itti, “Rapid biologically-inspired scene classification using features shared with visual attention,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 29, no. 2, 2007.

[3] L. Liu and L. Shao, “Sequential Compact Code Learning for Unsupervised Image Hashing,” IEEE Trans. Neural Netw. Learn. Syst., vol. 27, no. 12, pp. 2526–2536, Dec. 2016.

[4] C. Qin, X. Chen, D. Ye, J. Wang, and X. Sun, “A novel image hashing scheme with perceptual robustness using block truncation coding,” Inf. Sci., vol. 361–362, pp. 84–99, Sep. 2016.

[5] Z. Tang, X. Zhang, X. Li, and S. Zhang, “Robust Image Hashing With Ring Partition and Invariant Vector Distance,” IEEE Trans. Inf. Forensics Secur., vol. 11, no. 1, pp. 200–214, Jan. 2016.

[6] D. G. Lowe, “Distinctive image features from scale-invariant keypoints,” Int. J. Comput. Vis., vol. 60, no. 2, pp. 91–110, 2004.

[7] H. Bay, T. Tuytelaars, and L. Van Gool, “Surf: Speeded up robust features,” Comput. Vision–ECCV 2006, pp. 404–417, 2006.

[8] E. Rublee, V. Rabaud, K. Konolige, and G. Bradski, “ORB: An Efficient Alternative to SIFT or SURF,” in Proceedings of the 2011 International Conference on Computer Vision, Washington, DC, USA, 2011, pp. 2564–2571.

[9] E. Rosten and T. Drummond, “Machine learning for high-speed corner detection,”Comput. Vision–ECCV 2006, pp. 430–443, 2006.

[10] M. Calonder, V. Lepetit, C. Strecha, and P. Fua, “BRIEF: Binary Robust Independent Elementary Features,” in Computer Vision – ECCV 2010, K. Daniilidis, P. Maragos, and N. Paragios, Eds. Springer Berlin Heidelberg, 2010, pp. 778–792.

[11] P. F. Alcantarilla and T. Solutions, “Fast explicit diffusion for accelerated features in nonlinear scale spaces,” IEEE Trans Patt Anal Mach Intell, vol. 34, no. 7, pp. 1281–1298, 2011.

[12] O. Andersson and S. Reyna Marquez, A comparison of object detection algorithms using unmanipulated testing images: Comparing SIFT, KAZE, AKAZE and ORB. 2016.

[13] M. Muja and D. G. Lowe, “Fast Matching of Binary Features,” in Proceedings of the 2012 Ninth Conference on Computer and Robot Vision, Washington, DC, USA, 2012, pp. 404–410.

[14] F. Perronnin, Y. Liu, J. Sánchez, and H. Poirier, “Large-scale image retrieval with compressed Fisher vectors,” in 2010 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2010, pp. 3384–3391.

[15] J. Deng, A. C. Berg, and L. Fei-Fei, “Hierarchical semantic indexing for large scale image retrieval,” in 2011 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2011, pp. 785–792.

[16] H. Jegou, F. Perronnin, M. Douze, J. Sánchez, P. Perez, and C. Schmid, “Aggregating Local Image Descriptors into Compact Codes,” IEEE Trans Pattern Anal Mach Intell, vol. 34, no. 9, pp. 1704–1716, Sep. 2012.

[17] A. Krizhevsky, I. Sutskever, and G. E. Hinton, “ImageNet Classification with Deep Convolutional Neural Networks,” in Advances in Neural Information Processing Systems 25, F. Pereira, C. J. C. Burges, L. Bottou, and K. Q. Weinberger, Eds. Curran Associates, Inc., 2012, pp. 1097–1105.

[18] C. Szegedy, S. Ioffe, and V. Vanhoucke, “Inception-v4, Inception-ResNet and the Impact of Residual Connections on Learning,” ArXiv160207261 Cs, Feb. 2016.

[19] K. He, X. Zhang, S. Ren, and J. Sun, “Identity Mappings in Deep Residual Networks,”ArXiv160305027 Cs, Mar. 2016.

[20] F. N. Iandola, S. Han, M. W. Moskewicz, K. Ashraf, W. J. Dally, and K. Keutzer, “SqueezeNet: AlexNet-level accuracy with 50x fewer parameters and <0.5MB model size,”ArXiv160207360 Cs, Feb. 2016.

[21] H. Zhu, M. Long, J. Wang, and Y. Cao, “Deep Hashing Network for efficient similarity retrieval,” in Thirtieth AAAI Conference on Artificial Intelligence, 2016, pp. 2415–2421.

[22] J. Lu, V. E. Liong, and Z. Jie, “Deep Hashing for Scalable Image Search,” IEEE Trans. Image Process., vol. 26, no. 5, pp. 2352–2367, 2017.

[23] R. Zhang, L. Lin, R. Zhang, W. Zuo, and L. Zhang, “Bit-Scalable Deep Hashing With Regularized Similarity Learning for Image Retrieval and Person Re-Identification,” IEEE Trans. Image Process., vol. 24, no. 12, pp. 4766–4779, 2015.