哈希快速图像匹配算法研究

王 拓 于徐红 刘志杰

(贵州师范大学贵州省信息与计算科学重点实验室， 贵阳 550025)



哈希快速图像匹配算法研究

王 拓 于徐红 刘志杰

(贵州师范大学贵州省信息与计算科学重点实验室， 贵阳 550025)

如何快速有效地在大量数据中将图片筛选匹配出来，是图像匹配技术研究的重点课题之一。通过分析感知哈希算法及Surf算法各自的优点，提出用感知哈希算法进行初步图片搜索，利用Surf算法提取相似图片局部特征，从而更精准地确定最相似图片，增加图片匹配的鲁棒性。实验结果表明，在对图片进行处理后，哈希快速图像匹配算法仍能快速地从本地图片库中将最相似图片搜索出来。

感知哈希算法； DCT变换； Surf算法； 指纹数据

近年来，随着计算机、手机等电子产品的不断发展和普及，图片已成为我们记录生活的一种重要方式。据Facebook官方公布，现在每天上传的图片数量约20亿张，并且这个数字还在不断增加。同时，人们也不再仅仅局限于使用文字来搜索图片，“以图搜图”在这种情况下应运而生。目前应用“以图搜图”的主要是互联网图像搜索引擎网站，例如Google、百度、搜狗、Picitup、Bing、TinEye、Incogno等。大部分人的手机、电脑或其他存储设备里面也有成千上万张图片，如何在自己的图片库里快速找出想要查看的图片也是一个急需解决的问题。因此，如何将大量的图片进行数据处理与存储已成为大数据时代面临和必须解决的一个重要难题[1]。

目前，对图片进行特征提取应用最多的还是在Sift算法基础上，先对图像进行特征提取，然后根据提取特征对图像进行哈希编码，生成这个图像的“指纹”特征。Sift算法的优点是对图像的旋转、变换等都有很好的鲁棒性，缺点是复杂度比较高。此次研究基于Sift算法的改进算法——Surf算法，并基于哈希编码规则来提升图片的搜索比对速度[3-4]。

1 算法描述

1.1 感知哈希算法

哈希算法是一种将图片生成一组“指纹”数据的方法。在进行图片搜索比对时，首先对图片进行特征信息提取，并生成一组二维数组即图片指纹。通过对目标图像进行处理得到“指纹”后，将其与哈希图像库中的图片直接进行“指纹”比对。相对于其他形式的特征值对比，二维数组有更高的时效性优点。

感知哈希算法(perceptual hash algorithm，简写为pHash)。其流程图见图1。

图1 感知哈希算法流程图

pHash对一幅图片的处理过程如下：

(1) 缩小尺寸。pHash将图片缩小成N*N。这样做的目的是简化了DCT的计算，去除各种图片尺寸和图片比例的差异, 只保留结构、明暗等基本信息。一般情况下，N的值设置为32。

(2) 简化色彩。将图片转化成灰度图像，进一步简化计算量。

(3) 计算平均灰度。计算图片中所有像素的灰度平均值。

(4) 计算平均值。如同均值哈希算法一样，计算DCT的均值。

(5) 计算hash值。这是最主要的一步，根据DCT变换得到的32*32矩阵中，因为绝大部分信息包含在左上角8*8的系数子矩阵中，并且为了简化计算，在计算时只取其左上角8*8的系数子矩阵，然后将其设置成0或1的64位的hash值，大于等于DCT均值的设为“1”，小于DCT均值的设为“0”。组合在一起，就构成了一个64位的整数，即为这张图片的指纹。

本算法中，根据矩阵中8*8的系数子矩阵得出二维离散余弦变换(DCT)：

(1)

u≥0,v

式中:g——N*N图像像素点；

G——N*N矩阵中阈矩阵；

α—— 余弦系数矩阵。

对一张图片进行DCT变换后，便可将其像素信息以矩阵形式输出。若代表矩阵形式，式(1)可简化为：

F(u,v)=Af(x,y)AT

在利用pHash算法生成图片指纹后，就可比对不同图片的指纹来确定出最相似图片。首先要计算出8*8矩阵中图片信息生成的64位中有多少位是不一样的。如果不相同的数据位数不超过5, 就说明两张图片很相似, 如果超过10, 说明它们是两张不同的图片[5]。

感知哈希算法在处理大量图片时的时效性很高，然而该算法针对的是图片的整体特征，不能对局部特征进行提取和细致的识别，这就需要在局部特征提取方面来加强算法的鲁棒性。

1.2 Surf算法

1999年，David Lowe提出尺度不变特征变换(scale-invariant feature transform，简写为Sift)，Sift算法有以下特点：

(1) 尺度不变特征检测；

(2) 特征匹配和索引；

(3) 独特性好，信息量丰富；

(4) 高速性；

(5) 可扩展性。

利用Sift算法进行图片特征提取，可很好地避免光照强度变化、目标遮挡及其他因素干扰对图片特征的影响。但由于其计算复杂度较高，因此，研究选取Surf算法代替Sift算法来提取图片特征[6]。

Surf算法是Sift算法的一个提升，其借鉴了Sift算法中简化近似的思想，将DoH中的高斯二阶微分方程模板进行了简化，使得模板对图像的滤波只需要进行几个简单的加减法运算。

在对一幅图片进行特征提取时，Surf算法借助积分图像原理，首先将目标图像通过高斯二阶微分模板滤波，然后转化为对积分图像的加减运算。因为图像由若干个像素点构成的，因此，若假设以左上角为原点构建像素坐标系，对于图像中的任意一个点(I,i),其值假设为ii(I,j)表示为原图像左上角到点(j,j)相应的对角线区域灰度值的总和，即为：

式中：p(r,c) —— 图像中点(r,c)的灰度值。

接下来构建Hessian矩阵，并将提取的灰度信息生成所有兴趣点，用于特征的提取。其Hessian矩阵如下：

式中：f(x,y) —— 图像函数。

为了找出当前关键位置点，要将图像f(x,y)经过高斯滤波，对图像信息进行提取。其Hessian矩阵为：

图像信息在经过高斯滤波以后，假设L(x,t)表示在不同解析度下的一幅图像，可利用高斯核G(t)与图像函数I(x)在点x处的卷积来实现，其卷积计算公式如下：

L(x,t)=G(t)*I(x,t)

其中高斯核G(t)为：

式中：g(t) —— 高斯函数；

t—— 高斯方差。

为平衡准确值与近似值间的误差，引入权值。权值随尺度变化，则H矩阵判别式可表示为：

det(Happrox)=DxxDyy-(0.9Dxy)2

通过Hessian矩阵可以找出当前比周围其他更亮或者更暗的关键位置点，也就是特征提取[7-8]。

2 哈希快速图像匹配算法设计

哈希快速图像匹配算法是利用感知哈希算法复杂度低的优点，并结合Surf算法对局部特征及噪声的敏感性好等优点设计出的一种新算法，旨在提高图片搜索速度的基础上，保证检索出的图片的鲁棒性。该算法步骤如下：

(1) 归一化处理：首先将原始图像进行不同角度的旋转以及不同比例缩放后，生成相同的8*8尺寸。

(2) 对生成的图片进行DCT变换，通过设定阈值将矩阵生成64位的一维向量。

(3) 根据生成的初步指纹，利用Hamming距离方法，标记系列近相似图片。

(4) 利用Surf算法对标记的近相似图片进行特征提取，利用Hamming距离作为相似度度量，找出最近似的图片[9-11]。

3 实验结果分析

在对图像进行分析前，首先对图像的色彩进行提取，找出色彩分布区域。图2为目标图像的颜色分布图。然后利用DCT算法对图片进行整理，得出感知哈希序列指纹。

图2 目标图像的颜色分布图

目标图像颜色直方图见图3。首先对图片进行分析，得出其颜色分布区域，然后根据颜色分布进行DCT变换，并根据图像信息设定阈值，通过对阈值的比较生成8*8矩阵，并将其变换成一维64位数组，并将指纹数据以文本格式存放在本地文件中。

经过感知哈希算法处理后，便可通过第一次粗筛选。在此基础上，利用Surf算法对筛选出的图像信息进行二次比较，并利用特征点选取的方法进行二次筛选。利用Surf算法对图片进行特征提取示意图见图4。利用Surf算法，右面被马赛克处理过的图片也被找出特征相似点，从而在本地文件中找出最相似图片。局部特征点的提取示意图见图5。尽管图像被其他软件处理，该算法亦能通过排除干扰找出最相似图片[12]。

图3 目标图像颜色直方图

图4 利用Surf算法对图片进行特征提取

图5 局部特征点提取示意图

通过上述比较可知，此次研究中提出的感知哈希算法和Surf结合算法的时效性与文献[11]中提出的算法不相上下，唯一不足的就是在利用Surf算法时，由于要提高算法的速度，从而需减少匹配点数量。另外，本算法在利用双重定位方法的基础上，延续了尺度不变的特性，对于图像的翻转变换、明暗等变化都有良好的抗噪声效果，并能够将其准确匹配搜索出。

4 结 语

哈希快速图像匹配算法使用VS2013对图像进行处理编程，在对图像进行处理及编码指纹提取方面有了很大的改进，提高了速度，并且摒弃了哈希算法对局部不敏感等缺点，利用由粗到细的图像检索方法，实现图片快速准确的匹配。通过大量实验表明，该算法比利用Sift算法速度更快，并且能够保证图片的对比精度，快速准确地找到所需图片。

[1] YANG B, GU F,NIU X. Block Mean Value Based Image Perceptual Hashing [C] //Proc of IEEE International Conference on IIH-MSP. USA:IEEE,2006:167-172.

[2] XIANG S, KIM H J, HUANG J. Histogram-based Image Hashing Scheme Robust Against Geometric Deformations [C] //Proc of the 9th ACM Workshop on Multimedia and Security. USA: ACM，2007:121-128.

[3] 孙锐，闫晓星，高隽. 基于SIFT和PCA的图像感知哈希方法[J].电路与系统学报，2013，18(1): 274-278.

[4] 杜京义，胡益民，刘宇程. 基于区域分块的SIFT图像匹配技术研究与实现[J].光电工程，2013，40(8): 52-58.

[5] MONGA V, EVANS B L. Robust Perceptual Image Hashing Using Feature Point [C]∥Proceedings of IEEE International Conference on Image Processing(ICIP). Singapore: IEEE,2004:677-680.

[6] 赵璐璐，耿国华，李康，等. 基于SURF和快速近似最近邻搜索的图像匹配算法[J].计算机应用研究，2013，30(3): 921-923.

[7] BAY H,TUYTEPLAARS T, VAN G L. Speeded-up Robust Features(SURF)[J]. Computer Vision and Image Understanding,2008,110(3):346-359.

[8] ZAUNER C. Implementation and Benchmarking of Perceptual Image Hash Functions [D] . Upper Austria: Upper Austria University, 2010.

[9] MATTHEW B, DAVID L. Invariant Features from Interest Point Groups[C]. Cardiff: British Machine Vision Conference, 2002(23)：1-10.

[10] 王阿川，陈海涛. 基于离散余弦变换的鲁棒感知图像哈希技术[J].中国安全科学学报，2009，19(4): 91-96.

[11] 邱丽君，唐加山. 一种快速的两步骤图像匹配新算法[J].计算机技术与发展，2015，25(8): 67-70.

[12] ANGELIS A D, MOSCHITTA A, RUSSO F, et al. Image Quality Assessment: An Overview and Some Metrological Considerations[C]∥International Workshop on Advanced Methods for Uncertainty Estimation in Measurement. Trento: IEEE,2007：47-52.

Fast Image Matching Algorithm Base on Hash

WANGTuoYUXuhongLIUZhijie

(Key Laboratory of Information and Computing Science of Guizhou Province, Guizhou Normal University, Guiyang 550025, China)

Nowadays, data and image update each minute. How to match the image quickly and effectively is the key issue in image matching technology and research. By analyzing the merits of the perceptual hash algorithm and Surf algorithm, this paper proposes a preliminary image search using the perceptual hash algorithm, and then uses Surf algorithm to extract the local characteristics of similar images to determine the most similar images more accurately and increase the robustness for image matching. Experimental results show, when the image is processed, the Hash Fast Image Matching algorithm can still quickly search the most similar images from the local gallery.

perceptual Hash Algorithm; DCT transform; Surf Algorithm; fingerprint Data

2016-11-29

贵州省科学技术基金项目“基于Nutch的单位内部网络智能搜索引擎研究”(黔科合J字LKS[2009]17号)；贵州省经济和信息化委员会资助项目“大规模点模型的并行化真实感实时渲染技术研究”(1158号)；贵州省科技厅攻关项目“海龙囤申报世界文化遗产关键性技术研究”(黔科合SY字LKS[2014]3072号)

王拓(1991 — )，男，贵州师范大学在读硕士研究生，研究方向为图形图像处理。

TP391.41

A

1673-1980(2017)03-0075-04