董艷麗，崔 艷

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

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

董艷麗，崔 艷

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

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

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

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

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

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

1 SIFT算法

1.1 檢測尺度空間極值點

SIFT算法是在尺度空間中進行特征點檢測的，不同尺度表示圖像的不同特征.

圖像的尺度空間定義為函數(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)代表圖像像素坐標處的灰度；σ是空間尺度.采用高斯差分DoG(Difference of Gaussian)圖像來獲取圖像的極值點，DoG為相鄰尺度空間的函數(shù)之差，即

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

(3)

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

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

1.2 精確定位極值點的位置

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

1.3 特征點方向的分配

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

(4)

(5)

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

1.4 生成特征點描述子

為了確保旋轉不變性，先將坐標軸旋轉為特征點的方向.以特征點為中心在16×16的鄰域內計算，將鄰域分成4×4的子像素塊，然后對子像素塊計算8個方向的直方圖.因此，每個特征點的特征描述符的特征向量是4×4×8=128維.

圖1 SIFT描述子Fig.1 SIFT descriptor

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

2 隨機抽樣一致性算法

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

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

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

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

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

3 特征點的匹配

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

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

4 實驗和分析

采用MatlabR2015a來實現(xiàn)整個實驗過程，評價指標是正確匹配率(CorrectMatchingRate，CMR)，即正確的匹配序列對數(shù)與總匹配序列對數(shù)的比值[18-19].

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

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

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

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

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

表2 P1～P4旋轉失真圖像SIFT算法和RANSAC算法相結合的實驗結果

表3 P1～P4縮放失真圖像SIFT算法和RANSAC算法相結合的實驗結果

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

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

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

由圖4(a)可知，無論局部鞋印的質量如何，利用本方法進行匹配，前腳掌和后腳跟圖像的正確匹配率均為95%～100%，左右局部圖像的正確匹配率均為75%～100%.這是因為一些左右兩部分鞋印圖案在縱向分割時，鞋印的圖案被破壞，局部特征發(fā)生了變化，影響了特征點的提取.而橫向切割的鞋印圖像如前腳掌和后腳跟，相對于左右局部圖像保存了鞋印圖案的完整性，保留了大部分信息，故提取的特征點數(shù)目較多.

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

5 結語

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

[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-)，女，山東菏澤人，碩士研究生，主要研究方向為圖像匹配.

崔艷(1963-)，女，天津人，副教授，碩士生導師，主要研究方向為圖像處理與模式識別.E-mail:cuiyan@tjpu.edu.cn.

TP391.7

A

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