张闯 杨咸兆 徐齐全 陈苏婷

摘  要： 针对SIFT算法在应用于图像匹配时，存在准确率低下和耗时等问题，提出一种SIFT特征的哈希快速检索与图像匹配方法。文中提出以二值化SIFT关键点描述子和哈希表相结合的方法对图像进行匹配。针对实验过程中出现的冲突项，通过在哈希表中添加标志位并记录冲突相个数和地址，完美地解决了高维描述子转化到低维冲突项的问题，加快了匹配速度。实验结果表明，该方法图像匹配速度优于传统SIFT匹配方法，加快了相似特征检索速度、提高了查询效率，并能够满足实时应用。所提出的采用SIFT关键点描述子的二值化与哈希检索相结合的方法，通过对比实验，证明了该方法在保证准确率的同时，提高了效率，实现了图像的实时快速匹配。

关键词： SIFT特征; 哈希检索; 图像匹配; 二值化; 冲突项; 关键点

中图分类号： TN911.73?34; TP391.41             文献标识码： A                 文章编号： 1004?373X（2019）12?0127?05

Abstract： In allusion to the low accuracy rate and time?consumption problems existing during the application of the SIFT algorithm in image matching， a hash fast retrieval and image matching method based on the SIFT feature is proposed. A method combining the binarized SIFT key point descriptors and hash table is proposed to conduct image matching. For the conflict items that appear in the experiment， the problem of transforming the high?dimensional descriptors to low?dimensional conflict items is perfectly solved and the matching speed is accelerated by adding the flag and recording the number and addresses of conflicts in the hash table. The experimental results show that in comparison with the traditional SIFT matching method， the method has a better image matching speed， can accelerate the retrieval speed of similar features， improve the query efficiency and meet the real?time application requirement. The proposed method combining the binarization of SIFT key point descriptors and hash retrieval can improve the efficiency and realize real?time and fast matching of images at the prerequisite of ensuring the accuracy， which is demonstrated in the comparison experiment.

Keywords： SIFT feature; hash retrieval; image matching; binarization; conflict item; key point

0  引  言

随着自媒体的出现，使得互联网上图像资源爆炸式增长。为了更好地利用海量的数据，如何更好地快速检索图像愈发重要。传统的图像检索方法主要分为两类：基于标签的图像检索（Text?Based Image Retrieval，TBIR）和基于内容的图像检索（Content?Based Image Retrieval，CBIR）。TBIR需要初始图像包含标题、关键词等标签信息;CBIR则是从图像自身的视觉特征出发，进行特征提取，然后与海量数据特征进行相似度匹配，最终进行排名，将结果返给用户。CBIR方式依据图像抽象进行检索，实现了自动分类，提高了检索的鲁棒性[1]。本文提出的方法属于CBIR类，在传统SIFT特征提取算法的基础上引入哈希码，加快了检索效率。

SIFT算法通过提取图像的SIFT特征来实现图像匹配，在稳定性、独特性、多量性以及可扩展性等方面具有很好的表现[2]。但SIFT算法在应用于图像匹配时，需要计算高维特征向量之间的欧氏距离，而欧氏距离需要计算平方根，非常耗时[3?4]。 因此，为了提高SIFT匹配的速度，本文提出一种哈希检索方法，并解决了冲突项的问题。

1  SIFT特征及其提取方法

SIFT特征是图像的局部特征，影像的尺度、光照等因素对SIFT特征具有很小的影响。

SIFT特征提取[5]算法进行图像匹配主要有4步，如图1所示。开始建立模板图像库，选取一定数量的平面二维图片。查询时，图像采用穷举匹配法与图像库中的每幅图像进行匹配，输出匹配特征点最多的图像，即为所需查询的原始图像

图1  SIFT算法实现步骤

SIFT特征提取算法具有稳定性、独特性、多量性、高速性、可扩展性好等优点[6?8]，在一定程度上可避免：目标的旋转、缩放、平移，图像仿射/投影变换，光照影响，目标遮挡，杂物场景以及噪声等。

SIFT算法中，SIFT关键点描述子为128维的向量，每一维都是一个双精度浮点型数，在特征点匹配时需要对128维描述子计算欧氏距离，影响算法速度。

2  SIFT特征的哈希快速检索

针对SIFT由于采用欧氏距离带来的匹配速度与效率的不足，提出一种SIFT特征的哈希快速检索算法来加快图像匹配速度。

2.1  SIFT特征的二值化

以一幅图像的处理过程为例，分为3个步骤：

1） 图像预处理

首先将模板图像转化为灰度图像，分辨率调低为240×320，避免产生大量的SIFT关键点描述子。

2） SIFT关键点描述子二值化

先利用SIFT算法来获得图像关键点描述子，再二值化为128位的二进制码。

步骤1：假设一个128位的关键点描述子为[D0，D1，…，D127]。

图2  二值化关键点描述子

3） 哈希表的建立

首先，将得到的SIFT关键点描述子的二值码：[b0，b1，…，b127]，按8位一组划分，得到16个8位的子二值码[9]，每个子二值码按式（3）来计算得到对应的[Ni]：

式中，H就是关键点描述子的哈希地址码。图3展示了二值化描述子的哈希地址码生成步骤。

图3  生成哈希地址码

建立哈希表如圖4所示。第1位为标志位Flag，初始值为0。当有数据存入时置为1，第2～129位用来存储SIFT关键点描述子二值码，第130位为标志位Sum，用来记录冲突项的个数，初始为0，第131和132位用来存储SIFT关键点描述子的坐标，132位后面的位数可随时扩展。

图4  哈希表中数据结构

1） 当第一条数据插入时，将标志位Flag置1，2～129列存入128位的SIFT关键点描述子二值码，Sum为0，x，y存入SIFT关键点描述子的坐标。

2） 如果又有相同的哈希地址码不同的二值化关键点描述子进入哈希表时，此时该地址码已经有数据，Flag为1，所以Sum+1。设此时哈希表的总行数为R，则在第133列存入R+1，再将冲突项插入地址码为R+1的那一行。

3） 每有一个冲突项进来，Sum加1，然后在132+Sum处存入R+1，最后在R+1处存入冲突项数据。

2.2  SIFT二值化特征的哈希快速检索

SIFT特征的二值化及哈希表的建立是为了实现查询图像与模板图像的特征快速匹配。

欧氏距离则需要计算平方根，显然汉明距离计算要快得多。匹配方法可以描述为下列4个步骤：

1）、2） 按照第2.1节中的方法。

3） SIFT关键点描述子检索。获得SIFT关键点描述子的二进制码后，按式（2）～式（6）计算SIFT关键点描述子的哈希地址码[Hq]。

4） 匹配SIFT关键点描述子的二进制码。

根据[Hq]在模板图像的哈希表里查询该地址码的数据。首先若Flag为0，则没有相匹配的点;若Flag为1，则有匹配点;然后计算哈希表中模板图像的SIFT关键点描述子的二进制码和查询图像二进制码的汉明距离。将汉明距离与设置的阈值T比较，当汉明距离小于

T（取10）时则认为这两个点匹配，否则认为不匹配。

2.3  二值化SIFT关键点描述子的哈希算法优化

2.3.1  阈值M的优化

首先，设初始阈值M=0，临时变量i=0，冲突项数量S=图像的SIFT关键点总数。按初始阈值M来根据式（2）计算得到SIFT关键点描述子的二值码。然后由式（3）～式（6）计算得到SIFT关键点描述子的哈希地址码。将得到的哈希地址码逐一比较，记录下冲突项的个数Num，判断Num是否比S小，若果Num比S小，则i=M，S=Num。再将初始阈值M加0.000 1，否则直接将初始阈值M加0.000 1，重复这一操作一直到阈值M为1。循环结束后i是最优阈值。具体流程如图5所示。

2.3.2  冲突项的处理

设计一个算法来处理这些冲突项，解决冲突问题。将冲突项插入到65 535之后的地址中，然后在冲突的地址码设置一个字段表示这一地址码存在几个冲突项，另外再存下这些冲突项的地址码。

匹配时，如果查询图像的SIFT关键点描述子地址码所查到的数据里的Sum大于1，则取出所有冲突项[10]的地址码依次去与查询图像的二值化SIFT关键点描述子计算汉明距离;小于阈值T则认为匹配，不然就认为不匹配，完美解决了冲突问题。具体流程如图6所示。

图5  阈值选取流程图

圖6  冲突项插入哈希表流程图

3  快速图像匹配实验

本实验选取了TID2018数据库中的1 000张图片建立模板图像库，用待检索图像检索出原始完整图像。

3.1  建立图像数据库

利用SIFT算法来为每一幅图像获取它的SIFT关键点描述子，依据第2.2节中哈希算法最终获得每幅图像所对应的哈希表，每幅图像对应一张哈希表。

3.2  图像检索

3.2.1  关键点描述子检索

在模板图像数据库中寻找相同地址码进行匹配。设置数组[Sm]，长度为图像数据库中图像的个数，数组的下标m就是图像的ID。初始时数组[Sm]中的所有值都是0，每当查询图像与数据库中的图像SIFT关键点描述子匹配完成时，把匹配点的个数存到[Sm]中图像ID位。数组[Sm]流程图如图7所示。

3.2.2  相似性度量

在二值化SIFT关键点描述子检索完之后，根据[Sm]来确定数据库中的哪一幅图像是与查询图像最相似的SIFT关键点描述子匹配最多的那一幅图像就是最相似的图像。另外也考虑到查询图像是图像数据库中所没有的图像，当匹配点数量小于设定的阈值T=10时会提示弹出“没有对应的图片”。

图7  Sm生成流程图

3.3  实验结果与分析

该实验采用Matlab代码编写，首先将图像数据库里的每一幅图片生成哈希表，然后将这些哈希表导入Workspace里，用不同尺度的相似的图片做查询。实验结果如图8～图12所示。

图8  图像检索实验结果图 （一）

图9  图像检索实验结果图 （二）

从实验结果中看出，根据原数据库图像的一小块区域能够准确地查询到对应的原始图像，证明本文提出的SIFT特征的哈希快速检索与图像匹配检索方法是可行的。为了进一步分析各算法的性能，对5组实验中两种算法的匹配时间进行比较。5组图像的具体实验数据如图13所示。

图10  图像检索实验结果图（三）

图11  图像检索实验结果图（四）

图12  图像检索实验结果图（五）

图13  匹配速度对比图

从图13可知，在匹配速度方面，本文提出的SIFT特征的哈希快速检索的匹配时间相对于SIFT匹配时间明显要快。本文采用二值化关键点描述子再将其导入哈希表，将高维的特征描述向量映射为二进制哈希编码形式，通过汉明距离即可实现特征点间的快速匹配。

4  结  论

本文结合哈希方法，对SIFT关键点描述子进行二值化操作，将SIFT关键点描述子二值化，并建立哈希表，利用哈希检索实现快速图像匹配的功能。将哈希结合传统SIFT检索方法时，完美地解决了哈希的冲突项问题。图像匹配速度优于传统SIFT匹配，有效地提高了图像的检索速度，满足实时应用。

今后的工作重点是在采用GPU编程提升算法效率的同时，进一步引入深度学习中卷积神经网络模型如Googlenet，Resnet，Vgg等，同时利用实验室的计算机设备集群，搭建搜索任务自动分配，并行计算统计的整套云计算图像检索系统。

参考文献

[1] 王凡.基于SIFT的图像检索特征改进方法[J].数字技术与应用，2016（1）：139?141.

WANG Fan. Image retrieval feature improvement method based on SIFT [J]. Numerical technology & applications， 2016（1）： 139?141.

[2] 方壮.一种迭代有序K最邻近距离实现数字图像特征点匹配的算法[J].湖北民族学院学报（自然科学版），2013，31（1）：36?37.

FANG Zhuang. A kind of digital image feature points matching algorithm realized by sequential iteration K?neighbor [J]. Journal of Hubei University for Nationalities （Natural science edition）， 2013， 31（1）： 36?37.

[3] 闫家梅.基于SIFT特征的人脸识别[J].科学技术与工程，2013，13（5）：1219?1222.

YAN Jiamei. Face recognition based on SIFT features [J]. Science technology and engineering， 2013， 13（5）： 1219?1222.

[4] 刘兆庆，李琼，刘景瑞，等.一种基于SIFT的图像哈希算法[J].仪器仪表学报，2011，32（9）：2024?2028.

LIU Zhaoqing， LI Qiong， LIU Jingrui， et al. SIFT based image hashing algorithm [J]. Chinese journal of scientific instrument， 2011， 32（9）： 2024?2028.

[5] 胡鹏.基于嵌入式系统的自适应SIFT图像配准算法的研究[D].西安：西安电子科技大学，2014.

HU Peng. Embedded system based image registration using adaptive SIFT algorithm [D]. Xian： Xidian University， 2014.

[6] 黄东晓.基于三线阵CCD的新型三维形貌测量系统研究[D].天津：天津大学，2014.

HUANG Dongxiao. Study of a new 3D shape measurement system based on tri?linear CCDs [D]. Tianjin： Tianjin University， 2014.

[7] 刘俊.基于多特征融合的奶牛图像识别系统研究[D].上海：上海师范大学，2013.

LIU Jun. The research on cow image recognition system based on multi?feature fusion [D]. Shanghai： Shanghai Normal University， 2013.

[8] 李学超.基于斑点跟踪算法的心脏超声图像运动分析[D].沈阳：东北大学，2013.

LI Xuechao. Motion analysis on cardiac ultrasound images based on speckle tracking technology [D]. Shenyang： Northeastern University， 2013.

[9] CHEN C C， HSIEH S L. Using binarization and hashing for efficient SIFT matching [D]. Journal of visual communication and image presentation， 2015， 30： 86?93.

[10] HE T， WEI Y， LIU Z， et al. Content based image retrieval method based on SIFT feature [C]// Proceedings of 2018 International Conference on Intelligent Transportation， Big Data & Smart City. Jinan： IEEE Computer Society， 2018： 649?652.