董艷麗，崔 艷

(天津工業(yè)大學(xué) 理學(xué)院，天津 300387)

基于SIFT和RANSAC的鞋印圖像匹配算法

董艷麗，崔 艷

(天津工業(yè)大學(xué) 理學(xué)院，天津 300387)

針對(duì)失真的鞋印圖像的匹配問題，在研究中引入了基于尺度不變特征變換SIFT(scale-invariant feature transform)算法與RANSAC算法相結(jié)合的圖像匹配方法.首先，對(duì)圖像進(jìn)行SIFT特征點(diǎn)的提取，在分析 SIFT 特征描述子生成的基礎(chǔ)上，以最小歐式距離為標(biāo)準(zhǔn)來判斷特征點(diǎn)是否匹配.然后，用最小歐式距離與次小歐氏距離之比進(jìn)行初始匹配，用隨機(jī)抽樣一致性算法剔除SIFT算法匹配過程中存在的誤匹配點(diǎn)對(duì)，從而實(shí)現(xiàn)精確匹配.實(shí)驗(yàn)結(jié)果表明，在局部鞋印圖像中含有尺度縮放和旋轉(zhuǎn)失真的情況下，該算法達(dá)到了良好的匹配精度且具有較強(qiáng)的魯棒性和有效性.

鞋印圖像；圖像匹配；SIFT算法；RANSAC算法

鞋印是一種重要的物理證據(jù)，可以提供犯罪嫌疑人與犯罪地點(diǎn)之間的聯(lián)系[1-2].相對(duì)于指紋，鞋印在犯罪現(xiàn)場很常見且容易獲取，通過將犯罪現(xiàn)場的鞋印圖像與鞋印數(shù)據(jù)庫進(jìn)行對(duì)比，可以獲得非常有價(jià)值的案件偵破線索[3].在犯罪現(xiàn)場，由于環(huán)境的復(fù)雜性與地理特征的局限性，局部鞋印圖像相對(duì)于完整的鞋印圖像更容易提取.因此，研究局部鞋印在鞋印自動(dòng)識(shí)別系統(tǒng)中具有重要的意義，而鞋印圖像匹配作為鞋印自動(dòng)識(shí)別系統(tǒng)中的重要內(nèi)容，其匹配算法具有重要的研究價(jià)值[4-5].

圖像匹配算法一般分為兩種,一種是基于圖像的某些區(qū)域的匹配算法，另一種是基于圖像的局部特征點(diǎn)匹配算法,如尺度不變特征變換算法(Scale-invariant Feature Transform,SIFT)[6].該方法充分利用了圖像灰度的統(tǒng)計(jì)特性，避免了由于局部環(huán)境、光照、噪聲等造成失真引起的誤匹配，對(duì)匹配圖像的非本質(zhì)變化不敏感，對(duì)含有尺度、旋轉(zhuǎn)、噪聲失真的圖像匹配效果較好.在鞋印圖像匹配的應(yīng)用上，SIFT算子的總體性能優(yōu)于其他算子，提取的特征點(diǎn)具有良好的幾何穩(wěn)定性，尤其適合圖像存在較大變形的局部目標(biāo)識(shí)別、 圖像匹配等任務(wù).SIFT算法對(duì)圖像的縮放、旋轉(zhuǎn)、位移等保持不變性，具有抗干擾能力強(qiáng)、穩(wěn)定性好等諸多優(yōu)點(diǎn)，被廣泛應(yīng)用于多個(gè)領(lǐng)域[7-9].

鞋印匹配的關(guān)鍵是克服所收集鞋印圖像質(zhì)量方面無法控制的問題，如背景、尺度縮放、旋轉(zhuǎn)、噪聲等由于非垂直拍攝而引起的失真[10-11].為了提取具有高穩(wěn)定性、高匹配性的局部特征，解決局部鞋印的失真問題，本研究在原始SIFT算法[12]的基礎(chǔ)上，利用隨機(jī)抽樣一致性算法(Random Sample Consensus，RANSAC)[13-14]對(duì)特征點(diǎn)匹配點(diǎn)對(duì)提純，根據(jù)精確匹配的特征點(diǎn)數(shù)實(shí)現(xiàn)鞋印圖像匹配的魯棒性和有效性.

1 SIFT算法

1.1 檢測(cè)尺度空間極值點(diǎn)

SIFT算法是在尺度空間中進(jìn)行特征點(diǎn)檢測(cè)的，不同尺度表示圖像的不同特征.

圖像的尺度空間定義為函數(shù)L(x，y，σ)，即具有尺度變化的高斯函數(shù)G(x，y，σ)與圖像I(x，y)的卷積，生成圖像的高斯金字塔LoG，如式(1)和式(2)所示：

L(x，y，σ)=G(x，y，σ)×I(x，y)，

(1)

(2)

式中：(x，y)代表圖像像素坐標(biāo)處的灰度；σ是空間尺度.采用高斯差分DoG(Difference of Gaussian)圖像來獲取圖像的極值點(diǎn)，DoG為相鄰尺度空間的函數(shù)之差，即

D(x，y，σ)=[G(x，y，kσ)-G(x，y，σ)]×I(x，y)=L(x，y，kσ)-L(x，y，σ)，

(3)

式中：k為乘性因子，是一個(gè)常數(shù).

尋找尺度空間的極值點(diǎn)，每一個(gè)采樣點(diǎn)需要和它所有的相鄰點(diǎn)進(jìn)行比較，采樣點(diǎn)和它同尺度的8個(gè)相鄰點(diǎn)及上下相鄰尺度對(duì)應(yīng)的9×2個(gè)相鄰點(diǎn)共26個(gè)點(diǎn)進(jìn)行比較，若該像素點(diǎn)的灰度值在這26個(gè)鄰域像素中皆為極值，則為候選的極值點(diǎn).

1.2 精確定位極值點(diǎn)的位置

為了獲取穩(wěn)定的特征點(diǎn)，采用擬合函數(shù)來實(shí)現(xiàn)空間極值點(diǎn)的精確定位，同時(shí)要去除低對(duì)比度的特征點(diǎn)和不穩(wěn)定的邊緣響應(yīng)點(diǎn)，以增強(qiáng)匹配的穩(wěn)定性，進(jìn)而提高抗噪聲能力.DoG函數(shù)在圖像邊緣有很強(qiáng)的邊緣響應(yīng)，利用Hessian矩陣剔除不穩(wěn)定的邊緣響應(yīng)點(diǎn)，再次精確定位特征點(diǎn)的位置[15].

1.3 特征點(diǎn)方向的分配

為了使算子具備旋轉(zhuǎn)不變性，通過梯度直方圖確定特征點(diǎn)的主方向：

(4)

(5)

式(4)和式(5)分別為特征點(diǎn)處的梯度幅值和梯度方向的計(jì)算公式.每個(gè)特征點(diǎn)被指定有一個(gè)主方向，少許特征點(diǎn)有一個(gè)主方向和多個(gè)輔方向，以增強(qiáng)匹配的魯棒性[16].

1.4 生成特征點(diǎn)描述子

為了確保旋轉(zhuǎn)不變性，先將坐標(biāo)軸旋轉(zhuǎn)為特征點(diǎn)的方向.以特征點(diǎn)為中心在16×16的鄰域內(nèi)計(jì)算，將鄰域分成4×4的子像素塊，然后對(duì)子像素塊計(jì)算8個(gè)方向的直方圖.因此，每個(gè)特征點(diǎn)的特征描述符的特征向量是4×4×8=128維.

圖1 SIFT描述子Fig.1 SIFT descriptor

SIFT特征向量除去尺度變化、旋轉(zhuǎn)等幾何變形因素的影響之后，歸一化特征向量的長度，進(jìn)一步除去光照變化的影響[17]，如圖1所示.

2 隨機(jī)抽樣一致性算法

隨機(jī)抽樣一致性算法(RANSAC)是根據(jù)一組包含異常數(shù)據(jù)的樣本集，通過假設(shè)計(jì)算出數(shù)據(jù)的數(shù)學(xué)模型參數(shù)，從而得到有效的樣本數(shù)據(jù)的算法.RANSAC算法的基本假設(shè)是樣本中包含正確數(shù)據(jù)(即可以被模型描述的數(shù)據(jù))，也包含異常數(shù)據(jù) (即無法適應(yīng)數(shù)學(xué)模型的數(shù)據(jù)).為了得到最優(yōu)的模型，需確定模型所需數(shù)據(jù)的最小集合.RANSAC算法的基本思想描述如下：

(1)從樣本集P中隨機(jī)選取一個(gè)最小抽樣集，由這個(gè)子集初始化模型.

(2)找出根據(jù)閾值Td判斷后成為當(dāng)前模型的支撐點(diǎn)集S，集合S就是樣本的內(nèi)點(diǎn).

(3)若集合S的大小超過了某個(gè)閾值Ts，用S重新估計(jì)模型并結(jié)束.

(4)若集合S小于閾值Ts，選取下一個(gè)新的樣本，重復(fù)上述步驟；隨機(jī)抽樣計(jì)算N次，選出最大的一致集，重新計(jì)算模型，得到最后的結(jié)果.

3 特征點(diǎn)的匹配

當(dāng)兩幅圖像的關(guān)鍵點(diǎn)特征向量生成后，采用關(guān)鍵點(diǎn)特征向量的歐式距離為兩幅圖像中關(guān)鍵點(diǎn)的相似性判定度量.取待匹配圖像中某個(gè)關(guān)鍵點(diǎn)的特征向量，找出其與原始圖像中歐式距離最近的前兩個(gè)特征點(diǎn)，在這兩個(gè)特征點(diǎn)中，如果最近鄰的距離與上次近鄰的距離的比值小于某個(gè)比例閾值δ(δ設(shè)定為0.8)，則接受這一對(duì)匹配點(diǎn).

在匹配的過程中，會(huì)出現(xiàn)一些錯(cuò)誤的匹配點(diǎn)對(duì)，可利用RANSAC算法將其剔除.首先，輸入4個(gè)匹配點(diǎn)對(duì)數(shù)據(jù)，得到模型參數(shù)，利用此模型尋找其他局內(nèi)匹配點(diǎn)，計(jì)算出符合模型的局內(nèi)數(shù)據(jù)并重新計(jì)算模型參數(shù)作為下一個(gè)狀態(tài)，迭代此過程.重復(fù)操作隨機(jī)抽樣計(jì)算N次，選擇數(shù)目最多的局內(nèi)點(diǎn)為最終局內(nèi)點(diǎn).確定一個(gè)適當(dāng)?shù)牡螖?shù)M，確保4對(duì)匹配點(diǎn)都是局內(nèi)點(diǎn)的概率為99%.RANSAC算法在剔除誤匹配點(diǎn)的同時(shí)，計(jì)算匹配點(diǎn)在變換矩陣的正變換與逆變換后的誤差，利用設(shè)置的閾值剔除誤差較大的點(diǎn)，得到進(jìn)一步精化的匹配點(diǎn)，以達(dá)到最佳的匹配效果.

4 實(shí)驗(yàn)和分析

采用MatlabR2015a來實(shí)現(xiàn)整個(gè)實(shí)驗(yàn)過程，評(píng)價(jià)指標(biāo)是正確匹配率(CorrectMatchingRate，CMR)，即正確的匹配序列對(duì)數(shù)與總匹配序列對(duì)數(shù)的比值[18-19].

實(shí)驗(yàn)采用人工提取的鞋印圖像進(jìn)行測(cè)試，每個(gè)樣本圖像的磨損程度不同.從每幅樣本圖像中各截取4幅不同的局部鞋印圖像，截取的局部圖像分別為前腳掌、后腳跟、左半部鞋印與右半部鞋印，分別用P1～P4來表示.圖像P1～P4均占原始鞋印圖像的50%左右，樣本圖像尺寸為240像素×640像素.然后，對(duì)每個(gè)局部圖像進(jìn)行旋轉(zhuǎn)和縮放失真，產(chǎn)生失真圖像，從而構(gòu)成測(cè)試數(shù)據(jù)庫，如圖2所示.

圖2 測(cè)試數(shù)據(jù)庫Fig.2 Test database

實(shí)驗(yàn)采用的樣本待匹配圖像如圖2(a)所示，樣本圖像中待匹配目標(biāo)如圖2(P1)～(P4)所示.首先，進(jìn)行SIFT特征點(diǎn)提取，之后檢測(cè)出圖像的匹配點(diǎn)對(duì)，利用RANSAC算法篩選出全部正確的匹配點(diǎn)對(duì)，實(shí)驗(yàn)結(jié)果如圖3和表1所示.從表1可知，鞋印局部圖像P1～P4與樣本圖像的正確匹配率為98%～100%，匹配精度較高.同時(shí)，對(duì)P1～P4這4組局部圖像增加隨機(jī)旋轉(zhuǎn)和縮放失真，再次組成測(cè)試圖組.表2和表3為測(cè)試數(shù)據(jù)庫中4組局部鞋印圖像在不同質(zhì)量下的實(shí)驗(yàn)結(jié)果.表2的數(shù)據(jù)顯示，旋轉(zhuǎn)失真后的圖像P1～P4與樣本圖像的正確匹配率為71%～86%；表3的數(shù)據(jù)顯示，縮放失真后的圖像P1～P4與樣本圖像的正確匹配率為91%～96%.由此可知，SIFT與RANSAC相結(jié)合的算法處理鞋印圖像能達(dá)到較高的匹配精度，對(duì)存在旋轉(zhuǎn)和尺度失真的鞋印圖像具有一定的有效性.

圖3 局部鞋印圖像匹配結(jié)果Fig.3 The matching result of partial shoeprints image

匹配圖像 SIFT預(yù)匹配點(diǎn)數(shù)RANSAC后匹配點(diǎn)數(shù)正確匹配率/%P1(前腳掌)6636 6636 100．00P2(后腳跟)5345 5343 99．96P3(左半部)864 849 98．26P4(右半部)811 806 99．38

表2 P1～P4旋轉(zhuǎn)失真圖像SIFT算法和RANSAC算法相結(jié)合的實(shí)驗(yàn)結(jié)果

表3 P1～P4縮放失真圖像SIFT算法和RANSAC算法相結(jié)合的實(shí)驗(yàn)結(jié)果

為了測(cè)試本算法的魯棒性和有效性，避開隨機(jī)性帶來的誤差，取10幅樣本圖像，共120幅局部圖像組成測(cè)試數(shù)據(jù)庫.對(duì)測(cè)試數(shù)據(jù)庫進(jìn)行實(shí)驗(yàn)，得出不同局部鞋印圖像匹配精準(zhǔn)度的對(duì)比曲線，如圖4所示.

由圖4可以看出，本實(shí)驗(yàn)用SIFT算法預(yù)匹配和RANSAC算法去除誤匹配后，得到的正確匹配率均在70%以上.圖4(a)中，該算法的正確匹配率為75%～100%；圖4(b)和(c)是對(duì)旋轉(zhuǎn)和縮放圖像的實(shí)驗(yàn)結(jié)果，該算法的匹配精度為70%～95%，增加旋轉(zhuǎn)和縮放失真的圖像對(duì)其匹配精度沒有太大的影響.這就證明了SIFT和RANSAC相結(jié)合的算法對(duì)存在尺度和旋轉(zhuǎn)失真的圖像的匹配有一定的不變性，利用圖像的局部特征點(diǎn)對(duì)來完成模板匹配，匹配的精準(zhǔn)度較高.

圖4 不同質(zhì)量鞋印圖像的正確匹配率Fig.4 The correct matching rate of partial shoeprints in different qualities

由圖4(a)可知，無論局部鞋印的質(zhì)量如何，利用本方法進(jìn)行匹配，前腳掌和后腳跟圖像的正確匹配率均為95%～100%，左右局部圖像的正確匹配率均為75%～100%.這是因?yàn)橐恍┳笥覂刹糠中D案在縱向分割時(shí)，鞋印的圖案被破壞，局部特征發(fā)生了變化，影響了特征點(diǎn)的提取.而橫向切割的鞋印圖像如前腳掌和后腳跟，相對(duì)于左右局部圖像保存了鞋印圖案的完整性，保留了大部分信息，故提取的特征點(diǎn)數(shù)目較多.

從上述實(shí)驗(yàn)結(jié)果可知，利用本匹配算法進(jìn)行鞋印的局部特征點(diǎn)模板匹配，鞋印圖像的前腳掌和后腳跟區(qū)域要優(yōu)于左右局部鞋印圖像的匹配精度，多數(shù)特征點(diǎn)的匹配受圖像失真的影響較小.

5 結(jié)語

將SIFT算法和RANSAC算法結(jié)合，提出的鞋印匹配方法充分利用SIFT特征與RANSAC算法的魯棒性，有效地解決了存在旋轉(zhuǎn)和尺度失真的圖像的匹配問題，具有較高的匹配精確度，未來的研究工作是提高匹配效率的同時(shí)保持匹配效果不變.

[1] BODZIAK W J.Footwear Impression Evidence-Detection,Recovery and Examination[M].Boca Raton：CRC Press LLC,2000.

[2] THOMPSON T,BLACK S.Forensic Human Identification:an Introduction [M].Boca Raton：CRC Press,2007.

[3] CHAZAL P D,FLYNN J,REILLY R B.Automated processing of shoeprint image based on the fourier transform for use in forensic science [J].IEEE Transaction on Pattern Analysis and Machine Intelligence,2005,27(3):341-350.

[4] ALGARNI G,HAMIANE M.A novel technique for automatic shoeprint image retrieval [J].Forensic Science International,2008,181(1/3):10-14.

[5] TAPIO L,ANTTI L.Measuring the accuracy of automatic shoeprint recognition methods [J].Journal of Forensic Sciences,2014,59(3):1-7.

[6] DAVID G L.Object recogniton from local scale-invariant features[J].The Proceedings of the International Conference on Computer Vision,1999(2):1150-1157.

[7] RAJEEV R,KH M S.Digital Image forgery detection using SIFT feature [J].International Symposium on Advanced Computing and Communication,2015(4):186-191.

[8] TONY L.Image matching using generalized scale-space interest points [J].Journal of Mathematical Imaging and Vision,2015,52(1):3-36.

[9] CHEN Y,SHANG L.Improved SIFT image registration algorithm on characteristic statistical distributions and consistency constraint[J].Optik,2016,127(2):900-911.

[10]SHEIDA H,RIAN M S,JOHN B.The interpretation of shoeprint comparison class correspondences [J].Science and Justice,2012,52(4):243-248.

[11]ALMAADEED S,BOURIDANE A,CROOKES D,et al.Partial shoeprint retrieval using multiple point-of-interest detectors and SIFT descriptors [J].Integrated Computer-Aided Engineering,2015(22):41-58.

[12]LOWE D G.Distinctive image features from scale-invariant keypoints [J].International Journal of Computer Vision,2004,60(2):91-110.

[13]FISCHLER M A,BOLLES R C.Random sample consensus:a paradigm for model fitting with applications to image analysis and automated cartography [J].Communications of the Association for Computing Machinery,1981,24(6):381-395.

[14]CHALOM E,ASA E,BITON E.Measuring image similarity:an overview of some useful applications [J].IEEE Instrumentation & Measurement Magazine,2013,16(1):24-28.

[15]AHROR B,DJAMAL B.A new generalised α scale spaces quadrature filters [J].Pattern Recognition,2014,47(10):3209-3224.

[16]LIAO K,LIU G Z,HUI Y S.An improvement to the SIFT descriptor for image representation and matching [J].Pattern Recognition Letters,2013,34(11):1211-1220.

[17]YIU Y,LIU S P,WANG Z F.Multi-focus image fusion with dense SIFT [J].Information Fusion,2015(23):139-155.

[18]PRADEEP M P,JAYANT V K.Rotation and intensity invariant shoeprint matching using Gabor transform with application to forensic science [J].Pattern Recognition:the Journal of the Pattern Recognition Society,2009,42(7):1308-1317.

[19]KHAN M A,ANSARI M B.Rotation invariant matching of partial shoeprints [J].International Journal of Engineering Research and Applications，2014,4(9):1-5.

An approach to the partial shoeprints image matching based on SIFT and RANSAC

DONG Yanli, CUI Yan

(SchoolofScience,TianjinPolytechnicUniversity,Tianjin300387,China)

This paper presents a solution for the matching of shoeprints which is considerably more robust than existing solutions in the presence of geometric distortions such as scale, rotation distortions. A new matching method is proposed based on SIFT and RANSAC algorithm. Firstly, feature detection and pre-matching of images are done by using SIFT algorithm. Then we applied the matching between the extracting interest points descriptor with a nearest neighbor method using the Euclidean distance. Secondly, the mismatching is wiped out by using RANSAC algorithm. This method solves the mismatching problem of image matching. Experimental results show that compared with conventional algorithms, the proposed algorithm is more robust while maintaining good registration accuracy when analyzing partial shoeprint images in the presence of geometric distortions such as scale, rotation distortions.

shoeprint image; image matching; SIFT algorithm; RANSAC algorithm

2016-08-29

董艷麗(1988-)，女，山東菏澤人，碩士研究生，主要研究方向?yàn)閳D像匹配.

崔艷(1963-)，女，天津人，副教授，碩士生導(dǎo)師，主要研究方向?yàn)閳D像處理與模式識(shí)別.E-mail:cuiyan@tjpu.edu.cn.

TP391.7

A

1674-330X(2017)01-0071-05