張闖 楊咸兆 徐齊全 陳蘇婷

摘 ?要： 針對SIFT算法在應(yīng)用于圖像匹配時，存在準(zhǔn)確率低下和耗時等問題，提出一種SIFT特征的哈?？焖贆z索與圖像匹配方法。文中提出以二值化SIFT關(guān)鍵點(diǎn)描述子和哈希表相結(jié)合的方法對圖像進(jìn)行匹配。針對實(shí)驗(yàn)過程中出現(xiàn)的沖突項(xiàng)，通過在哈希表中添加標(biāo)志位并記錄沖突相個數(shù)和地址，完美地解決了高維描述子轉(zhuǎn)化到低維沖突項(xiàng)的問題，加快了匹配速度。實(shí)驗(yàn)結(jié)果表明，該方法圖像匹配速度優(yōu)于傳統(tǒng)SIFT匹配方法，加快了相似特征檢索速度、提高了查詢效率，并能夠滿足實(shí)時應(yīng)用。所提出的采用SIFT關(guān)鍵點(diǎn)描述子的二值化與哈希檢索相結(jié)合的方法，通過對比實(shí)驗(yàn)，證明了該方法在保證準(zhǔn)確率的同時，提高了效率，實(shí)現(xiàn)了圖像的實(shí)時快速匹配。

關(guān)鍵詞： SIFT特征; 哈希檢索; 圖像匹配; 二值化; 沖突項(xiàng); 關(guān)鍵點(diǎn)

中圖分類號： TN911.73?34; TP391.41 ? ? ? ? ? ? 文獻(xiàn)標(biāo)識碼： 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 ?引 ?言

隨著自媒體的出現(xiàn)，使得互聯(lián)網(wǎng)上圖像資源爆炸式增長。為了更好地利用海量的數(shù)據(jù)，如何更好地快速檢索圖像愈發(fā)重要。傳統(tǒng)的圖像檢索方法主要分為兩類：基于標(biāo)簽的圖像檢索（Text?Based Image Retrieval，TBIR）和基于內(nèi)容的圖像檢索（Content?Based Image Retrieval，CBIR）。TBIR需要初始圖像包含標(biāo)題、關(guān)鍵詞等標(biāo)簽信息;CBIR則是從圖像自身的視覺特征出發(fā)，進(jìn)行特征提取，然后與海量數(shù)據(jù)特征進(jìn)行相似度匹配，最終進(jìn)行排名，將結(jié)果返給用戶。CBIR方式依據(jù)圖像抽象進(jìn)行檢索，實(shí)現(xiàn)了自動分類，提高了檢索的魯棒性[1]。本文提出的方法屬于CBIR類，在傳統(tǒng)SIFT特征提取算法的基礎(chǔ)上引入哈希碼，加快了檢索效率。

SIFT算法通過提取圖像的SIFT特征來實(shí)現(xiàn)圖像匹配，在穩(wěn)定性、獨(dú)特性、多量性以及可擴(kuò)展性等方面具有很好的表現(xiàn)[2]。但SIFT算法在應(yīng)用于圖像匹配時，需要計(jì)算高維特征向量之間的歐氏距離，而歐氏距離需要計(jì)算平方根，非常耗時[3?4]。 因此，為了提高SIFT匹配的速度，本文提出一種哈希檢索方法，并解決了沖突項(xiàng)的問題。

1 ?SIFT特征及其提取方法

SIFT特征是圖像的局部特征，影像的尺度、光照等因素對SIFT特征具有很小的影響。

SIFT特征提取[5]算法進(jìn)行圖像匹配主要有4步，如圖1所示。開始建立模板圖像庫，選取一定數(shù)量的平面二維圖片。查詢時，圖像采用窮舉匹配法與圖像庫中的每幅圖像進(jìn)行匹配，輸出匹配特征點(diǎn)最多的圖像，即為所需查詢的原始圖像

圖1 ?SIFT算法實(shí)現(xiàn)步驟

SIFT特征提取算法具有穩(wěn)定性、獨(dú)特性、多量性、高速性、可擴(kuò)展性好等優(yōu)點(diǎn)[6?8]，在一定程度上可避免：目標(biāo)的旋轉(zhuǎn)、縮放、平移，圖像仿射/投影變換，光照影響，目標(biāo)遮擋，雜物場景以及噪聲等。

SIFT算法中，SIFT關(guān)鍵點(diǎn)描述子為128維的向量，每一維都是一個雙精度浮點(diǎn)型數(shù)，在特征點(diǎn)匹配時需要對128維描述子計(jì)算歐氏距離，影響算法速度。

2 ?SIFT特征的哈?？焖贆z索

針對SIFT由于采用歐氏距離帶來的匹配速度與效率的不足，提出一種SIFT特征的哈?？焖贆z索算法來加快圖像匹配速度。

2.1 ?SIFT特征的二值化

以一幅圖像的處理過程為例，分為3個步驟：

1） 圖像預(yù)處理

首先將模板圖像轉(zhuǎn)化為灰度圖像，分辨率調(diào)低為240×320，避免產(chǎn)生大量的SIFT關(guān)鍵點(diǎn)描述子。

2） SIFT關(guān)鍵點(diǎn)描述子二值化

先利用SIFT算法來獲得圖像關(guān)鍵點(diǎn)描述子，再二值化為128位的二進(jìn)制碼。

步驟1：假設(shè)一個128位的關(guān)鍵點(diǎn)描述子為[D0，D1，…，D127]。

圖2 ?二值化關(guān)鍵點(diǎn)描述子

3） 哈希表的建立

首先，將得到的SIFT關(guān)鍵點(diǎn)描述子的二值碼：[b0，b1，…，b127]，按8位一組劃分，得到16個8位的子二值碼[9]，每個子二值碼按式（3）來計(jì)算得到對應(yīng)的[Ni]：

式中，H就是關(guān)鍵點(diǎn)描述子的哈希地址碼。圖3展示了二值化描述子的哈希地址碼生成步驟。

圖3 ?生成哈希地址碼

建立哈希表如圖4所示。第1位為標(biāo)志位Flag，初始值為0。當(dāng)有數(shù)據(jù)存入時置為1，第2～129位用來存儲SIFT關(guān)鍵點(diǎn)描述子二值碼，第130位為標(biāo)志位Sum，用來記錄沖突項(xiàng)的個數(shù)，初始為0，第131和132位用來存儲SIFT關(guān)鍵點(diǎn)描述子的坐標(biāo)，132位后面的位數(shù)可隨時擴(kuò)展。

圖4 ?哈希表中數(shù)據(jù)結(jié)構(gòu)

1） 當(dāng)?shù)谝粭l數(shù)據(jù)插入時，將標(biāo)志位Flag置1，2～129列存入128位的SIFT關(guān)鍵點(diǎn)描述子二值碼，Sum為0，x，y存入SIFT關(guān)鍵點(diǎn)描述子的坐標(biāo)。

2） 如果又有相同的哈希地址碼不同的二值化關(guān)鍵點(diǎn)描述子進(jìn)入哈希表時，此時該地址碼已經(jīng)有數(shù)據(jù)，F(xiàn)lag為1，所以Sum+1。設(shè)此時哈希表的總行數(shù)為R，則在第133列存入R+1，再將沖突項(xiàng)插入地址碼為R+1的那一行。

3） 每有一個沖突項(xiàng)進(jìn)來，Sum加1，然后在132+Sum處存入R+1，最后在R+1處存入沖突項(xiàng)數(shù)據(jù)。

2.2 ?SIFT二值化特征的哈?？焖贆z索

SIFT特征的二值化及哈希表的建立是為了實(shí)現(xiàn)查詢圖像與模板圖像的特征快速匹配。

歐氏距離則需要計(jì)算平方根，顯然漢明距離計(jì)算要快得多。匹配方法可以描述為下列4個步驟：

1）、2） 按照第2.1節(jié)中的方法。

3） SIFT關(guān)鍵點(diǎn)描述子檢索。獲得SIFT關(guān)鍵點(diǎn)描述子的二進(jìn)制碼后，按式（2）～式（6）計(jì)算SIFT關(guān)鍵點(diǎn)描述子的哈希地址碼[Hq]。

4） 匹配SIFT關(guān)鍵點(diǎn)描述子的二進(jìn)制碼。

根據(jù)[Hq]在模板圖像的哈希表里查詢該地址碼的數(shù)據(jù)。首先若Flag為0，則沒有相匹配的點(diǎn);若Flag為1，則有匹配點(diǎn);然后計(jì)算哈希表中模板圖像的SIFT關(guān)鍵點(diǎn)描述子的二進(jìn)制碼和查詢圖像二進(jìn)制碼的漢明距離。將漢明距離與設(shè)置的閾值T比較，當(dāng)漢明距離小于

T（取10）時則認(rèn)為這兩個點(diǎn)匹配，否則認(rèn)為不匹配。

2.3 ?二值化SIFT關(guān)鍵點(diǎn)描述子的哈希算法優(yōu)化

2.3.1 ?閾值M的優(yōu)化

首先，設(shè)初始閾值M=0，臨時變量i=0，沖突項(xiàng)數(shù)量S=圖像的SIFT關(guān)鍵點(diǎn)總數(shù)。按初始閾值M來根據(jù)式（2）計(jì)算得到SIFT關(guān)鍵點(diǎn)描述子的二值碼。然后由式（3）～式（6）計(jì)算得到SIFT關(guān)鍵點(diǎn)描述子的哈希地址碼。將得到的哈希地址碼逐一比較，記錄下沖突項(xiàng)的個數(shù)Num，判斷Num是否比S小，若果Num比S小，則i=M，S=Num。再將初始閾值M加0.000 1，否則直接將初始閾值M加0.000 1，重復(fù)這一操作一直到閾值M為1。循環(huán)結(jié)束后i是最優(yōu)閾值。具體流程如圖5所示。

2.3.2 ?沖突項(xiàng)的處理

設(shè)計(jì)一個算法來處理這些沖突項(xiàng)，解決沖突問題。將沖突項(xiàng)插入到65 535之后的地址中，然后在沖突的地址碼設(shè)置一個字段表示這一地址碼存在幾個沖突項(xiàng)，另外再存下這些沖突項(xiàng)的地址碼。

匹配時，如果查詢圖像的SIFT關(guān)鍵點(diǎn)描述子地址碼所查到的數(shù)據(jù)里的Sum大于1，則取出所有沖突項(xiàng)[10]的地址碼依次去與查詢圖像的二值化SIFT關(guān)鍵點(diǎn)描述子計(jì)算漢明距離;小于閾值T則認(rèn)為匹配，不然就認(rèn)為不匹配，完美解決了沖突問題。具體流程如圖6所示。

圖5 ?閾值選取流程圖

圖6 ?沖突項(xiàng)插入哈希表流程圖

3 ?快速圖像匹配實(shí)驗(yàn)

本實(shí)驗(yàn)選取了TID2018數(shù)據(jù)庫中的1 000張圖片建立模板圖像庫，用待檢索圖像檢索出原始完整圖像。

3.1 ?建立圖像數(shù)據(jù)庫

利用SIFT算法來為每一幅圖像獲取它的SIFT關(guān)鍵點(diǎn)描述子，依據(jù)第2.2節(jié)中哈希算法最終獲得每幅圖像所對應(yīng)的哈希表，每幅圖像對應(yīng)一張哈希表。

3.2 ?圖像檢索

3.2.1 ?關(guān)鍵點(diǎn)描述子檢索

在模板圖像數(shù)據(jù)庫中尋找相同地址碼進(jìn)行匹配。設(shè)置數(shù)組[Sm]，長度為圖像數(shù)據(jù)庫中圖像的個數(shù)，數(shù)組的下標(biāo)m就是圖像的ID。初始時數(shù)組[Sm]中的所有值都是0，每當(dāng)查詢圖像與數(shù)據(jù)庫中的圖像SIFT關(guān)鍵點(diǎn)描述子匹配完成時，把匹配點(diǎn)的個數(shù)存到[Sm]中圖像ID位。數(shù)組[Sm]流程圖如圖7所示。

3.2.2 ?相似性度量

在二值化SIFT關(guān)鍵點(diǎn)描述子檢索完之后，根據(jù)[Sm]來確定數(shù)據(jù)庫中的哪一幅圖像是與查詢圖像最相似的SIFT關(guān)鍵點(diǎn)描述子匹配最多的那一幅圖像就是最相似的圖像。另外也考慮到查詢圖像是圖像數(shù)據(jù)庫中所沒有的圖像，當(dāng)匹配點(diǎn)數(shù)量小于設(shè)定的閾值T=10時會提示彈出“沒有對應(yīng)的圖片”。

圖7 ?Sm生成流程圖

3.3 ?實(shí)驗(yàn)結(jié)果與分析

該實(shí)驗(yàn)采用Matlab代碼編寫，首先將圖像數(shù)據(jù)庫里的每一幅圖片生成哈希表，然后將這些哈希表導(dǎo)入Workspace里，用不同尺度的相似的圖片做查詢。實(shí)驗(yàn)結(jié)果如圖8～圖12所示。

圖8 ?圖像檢索實(shí)驗(yàn)結(jié)果圖 （一）

圖9 ?圖像檢索實(shí)驗(yàn)結(jié)果圖 （二）

從實(shí)驗(yàn)結(jié)果中看出，根據(jù)原數(shù)據(jù)庫圖像的一小塊區(qū)域能夠準(zhǔn)確地查詢到對應(yīng)的原始圖像，證明本文提出的SIFT特征的哈希快速檢索與圖像匹配檢索方法是可行的。為了進(jìn)一步分析各算法的性能，對5組實(shí)驗(yàn)中兩種算法的匹配時間進(jìn)行比較。5組圖像的具體實(shí)驗(yàn)數(shù)據(jù)如圖13所示。

圖10 ?圖像檢索實(shí)驗(yàn)結(jié)果圖（三）

圖11 ?圖像檢索實(shí)驗(yàn)結(jié)果圖（四）

圖12 ?圖像檢索實(shí)驗(yàn)結(jié)果圖（五）

圖13 ?匹配速度對比圖

從圖13可知，在匹配速度方面，本文提出的SIFT特征的哈?？焖贆z索的匹配時間相對于SIFT匹配時間明顯要快。本文采用二值化關(guān)鍵點(diǎn)描述子再將其導(dǎo)入哈希表，將高維的特征描述向量映射為二進(jìn)制哈希編碼形式，通過漢明距離即可實(shí)現(xiàn)特征點(diǎn)間的快速匹配。

4 ?結(jié) ?論

本文結(jié)合哈希方法，對SIFT關(guān)鍵點(diǎn)描述子進(jìn)行二值化操作，將SIFT關(guān)鍵點(diǎn)描述子二值化，并建立哈希表，利用哈希檢索實(shí)現(xiàn)快速圖像匹配的功能。將哈希結(jié)合傳統(tǒng)SIFT檢索方法時，完美地解決了哈希的沖突項(xiàng)問題。圖像匹配速度優(yōu)于傳統(tǒng)SIFT匹配，有效地提高了圖像的檢索速度，滿足實(shí)時應(yīng)用。

今后的工作重點(diǎn)是在采用GPU編程提升算法效率的同時，進(jìn)一步引入深度學(xué)習(xí)中卷積神經(jīng)網(wǎng)絡(luò)模型如Googlenet，Resnet，Vgg等，同時利用實(shí)驗(yàn)室的計(jì)算機(jī)設(shè)備集群，搭建搜索任務(wù)自動分配，并行計(jì)算統(tǒng)計(jì)的整套云計(jì)算圖像檢索系統(tǒng)。

參考文獻(xiàn)

[1] 王凡.基于SIFT的圖像檢索特征改進(jìn)方法[J].數(shù)字技術(shù)與應(yīng)用，2016（1）：139?141.

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

[2] 方壯.一種迭代有序K最鄰近距離實(shí)現(xiàn)數(shù)字圖像特征點(diǎn)匹配的算法[J].湖北民族學(xué)院學(xué)報(bào)（自然科學(xué)版），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].科學(xué)技術(shù)與工程，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].儀器儀表學(xué)報(bào)，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] 胡鵬.基于嵌入式系統(tǒng)的自適應(yīng)SIFT圖像配準(zhǔn)算法的研究[D].西安：西安電子科技大學(xué)，2014.

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

[6] 黃東曉.基于三線陣CCD的新型三維形貌測量系統(tǒng)研究[D].天津：天津大學(xué)，2014.

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

[7] 劉俊.基于多特征融合的奶牛圖像識別系統(tǒng)研究[D].上海：上海師范大學(xué)，2013.

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

[8] 李學(xué)超.基于斑點(diǎn)跟蹤算法的心臟超聲圖像運(yùn)動分析[D].沈陽：東北大學(xué)，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.