李大湘，邱 鑫 ，劉 穎

（1. 西安郵電大學(xué)通信與信息工程學(xué)院，西安 710121；2. 電子信息現(xiàn)場勘驗應(yīng)用技術(shù)公安部重點實驗室，西安 710121）

足跡作為犯罪現(xiàn)場中最常見的一種痕跡物證，在案件串并及法庭舉證等工作中一直具有重要作用。但是，隨著刑偵數(shù)字化與網(wǎng)絡(luò)化技術(shù)的發(fā)展，鞋底庫中的圖像數(shù)量越來越多。當(dāng)從犯罪現(xiàn)場采集到鞋印圖像時，利用圖像自動比對技術(shù)，在大規(guī)模鞋印庫中快速而準(zhǔn)確地查詢到其他相似鞋印，為刑偵工作尋找破案線索，在當(dāng)前“科技強(qiáng)警”工作中具有重要意義[1]。

針對鞋印圖像快速查詢應(yīng)用需求，相關(guān)算法可分為三類：1）基于鞋印圖像檢索的方法，該類方法的基本思想是提取鞋印圖像的全局或局部底層視覺特征，再結(jié)合機(jī)器學(xué)習(xí)或相似度量方法，以實現(xiàn)鞋印圖像相似查找，例如文獻(xiàn)[ 2]提出基于聚類的鞋印圖像檢索算法，該算法針對鞋印圖像類別之間存在隔離帶這一情況，設(shè)計一種K步穩(wěn)定聚類算法以實現(xiàn)鞋印圖像檢索；文獻(xiàn)[ 3]融合局部二值模式（LBP）紋理特征與局部敏感哈希(LSH)索引方法，提出一種大規(guī)模鞋印圖像快速檢索方法。2）基于鞋印圖像分類的方法，該類方法的基本思想是對鞋印圖像實現(xiàn)自動分類，以縮小排查范圍而提高查找效率，如文獻(xiàn)[ 4]提出一種基于卷積神經(jīng)網(wǎng)絡(luò)的鞋印分類算法，該算法在將CNN模型引入鞋印圖像分類的基礎(chǔ)上，針對網(wǎng)絡(luò)中存在相似特征圖的性質(zhì)，設(shè)計一種去冗余連接的CNN改進(jìn)模型，加快了網(wǎng)絡(luò)收斂速度，也提高了分類精度；文獻(xiàn)[ 5]提出一種基于語義的鞋印分類算法，該算法在鞋印圖像底層視覺特征的基礎(chǔ)上，還引入了語義信息，有效地提高了分類性能。3）基于鞋印圖像匹配的方法，該類方法的基本思想是提取鞋印圖像局部或關(guān)鍵點信息，給定查詢樣圖直接在鞋印庫進(jìn)行相似比對，如文獻(xiàn)[ 6]利用鞋印圖像的尺度不變特征變換 (scale-invariant feature transform, SIFT)描述子，提出一種基于RANSAC 算法的圖像匹配方法；除此之外，還有基于能量譜密度（power spectral density，PSD）特征[7]、Gabor紋理特征[8]的鞋印匹配算法，且在相應(yīng)的測試集都具有一定的匹配精度。

在現(xiàn)勘鞋印圖像比對實際應(yīng)用中，鞋印圖像存在的特點有：1）鞋印花紋結(jié)構(gòu)種類很多，且同種花紋的鞋印樣本很少；2）犯罪現(xiàn)場很難提取與拍攝到清晰而完整的鞋印圖像；3）鞋印圖像庫中的圖像總量很多。所以，基于機(jī)器學(xué)習(xí)的鞋印圖像檢索與分類方法無法預(yù)先定義完備的鞋印花紋類別而提前訓(xùn)練出性能優(yōu)異的分類器，不具有通用性；而基于匹配的鞋印查詢方法，沒有考慮大數(shù)據(jù)集問題，即當(dāng)庫中的圖像數(shù)量非常多時，若采用窮舉比對的方法進(jìn)行相似查找，效率非常低，不能滿足實時性的應(yīng)用需求。

針對上述問題及大規(guī)模鞋印圖像快速比對應(yīng)用需求，本文提出一種基于稀疏編碼（sparse coding,SC）[9]與反向索引（reverted index, RI）[10]的鞋印圖像快速比對算法，稱之為SC-RI算法。該算法的主要思想是：首先，提取鞋印圖像的SIFT局部特征，然后采用字典學(xué)習(xí)、稀疏編碼與最大池化處理等方法，計算出鞋印圖像的稀疏編碼特征；最后，通過構(gòu)建“詞-圖像矩陣”而設(shè)計反向索引結(jié)構(gòu)。試驗結(jié)果表明，真實采集的鞋印圖像雖然整體上來說不完整，但只要存在局部清晰的花紋結(jié)構(gòu)，就可以應(yīng)用SC-RI算法簡單而有效地實現(xiàn)比對查詢。

1 鞋印圖像局部特征提取

為了提高后續(xù)算法的穩(wěn)定性與可靠性，鞋印圖像在錄入數(shù)據(jù)庫時，在做局部特征提取之前，首先，按圖1所示方法對鞋印圖像進(jìn)行直方圖均衡化視覺增強(qiáng)、中值濾波與OSTU二值分割等預(yù)處理；然后，基于二值分割之后的圖像，自動檢測關(guān)鍵點并計算其SIFT描述子[6,10]，用于表示鞋印圖像的局部結(jié)構(gòu)特征。

圖1 鞋印圖像預(yù)處理方法與效果示意圖Fig.1 Effect of preprocessing on shoeprint image

設(shè)IMG表示任一鞋印圖像，對其采用SIFT方法檢測到關(guān)鍵點數(shù)量為n個，則IMG的局部特征集記為：

表示第j個關(guān)鍵點的SIFT描述子。

2 CS-RI鞋印比對算法

設(shè)T={IMGi:i=1,2,...,N}表示鞋印圖像庫，其中N表示鞋印圖像的總數(shù)量，對T中的每幅圖像進(jìn)行SIFT局部特征提取之后，設(shè)由所有SIFT描述子組成的數(shù)據(jù)集為：

從圖2所示操作過程可見，雖然現(xiàn)勘中很難采集到完整而清晰的鞋印圖像，但只要其存在局部清晰的花紋區(qū)域，本系統(tǒng)就可將其剪取下來，并進(jìn)行中值濾波與二值分割等預(yù)處理，作為查詢樣圖而實現(xiàn)鞋印比對查詢。從圖3所示的實現(xiàn)結(jié)果可見，排在第1、2與7的圖像，都是“嫌犯鞋印庫”中與之相對應(yīng)的正確比對結(jié)果。本次比對耗時119.64 ms，電腦平臺是：浪潮圖像工作站，Win7操作系統(tǒng)（64位），8G RAM內(nèi)存，Intel Xeon(R) 3.1G CPU處理器。

圖2 鞋印圖像比對操作流程（A：待比對的原始圖像；B：剪切的目標(biāo)圖像；C：預(yù)處理之后的圖像）Fig.2 Operational process of the shoeprint image comparison (A.original image for query; B. target image cut from the original; C.target image after preprocessing)

圖3 鞋印圖像比對查詢結(jié)果Fig.3 Query results on comparing shoeprint images

在“以人查案”應(yīng)用實例中：首先，打開嫌疑人鞋印圖像，如圖4A所示；然后，采用上述相同方法在圖像中剪切局部清晰的花紋區(qū)域并進(jìn)行預(yù)處理，如圖4B所示；最后，點“比對識別”按鈕（對應(yīng)傳統(tǒng)SIFT匹配與逐個窮舉比對方法），得到圖4C所示比對結(jié)果。

為了綜合評估本文算法的比對速度與比對精度，選取“折波型、交織型、線條型、邊塊型與圓點型”等5種常見花紋結(jié)構(gòu)，每種10個，共50個局部花紋結(jié)構(gòu)作為比對樣圖，進(jìn)行綜合評估實驗，其平均比對時間、Top10與Top20的正確率如表1所示。其中：平均比對時間是指50次比對的平均耗時，平均Top10或Top20正確率是指50次比對實驗中，比對結(jié)果前10幅或前20幅圖像中比對正確的圖像總數(shù)除以150，這是因為：在鞋印庫中大部分同類圖像都存在3幅，每次比對過程中都希望那3幅圖像均能排在前10或前20之中，即150（50×3）為真正正確圖像的總數(shù)。

由表1中試驗結(jié)果可見，本文利用鞋印圖像的SIFT局部特征，再結(jié)合稀疏編碼與反向索引技術(shù)而提出的CS-RI鞋印比對算法，其比對精度接近于傳統(tǒng)SIFT匹配窮舉比對方法，只要鞋印圖像存在局部清晰的花紋結(jié)構(gòu)，比對正確率均在90%以上，但其比對速度提高了140多倍。這說明CS-RI是非常有效的鞋印比對算法，其原因是：1）SIFT描述子是一種非常有效的圖像局部特征提取方法，其不但能捕獲豐富的圖像底層視覺特征，而且還對圖像旋轉(zhuǎn)、尺度縮放、光照變化均具有不變性；2）通過字典學(xué)習(xí)與稀疏編碼，能從鞋印圖像中獲取有意義的結(jié)構(gòu)基元，最后得到的編碼系數(shù)，能很好地描述鞋印圖像中所包含的各種花紋信息，近些年，稀疏編碼在圖像語義分析問題已得到成功應(yīng)用，且性能卓越。

圖4 鞋印圖像比對操作流程及比對結(jié)果（A：嫌犯鞋印原始圖像；B：預(yù)處理后的目標(biāo)區(qū)域；C：比對結(jié)果）Fig.4 Operational course of comparing shoeprint images and the result (A. original image of suspect; B. target image preprocessed;C. query result)

表1 比對精度與時間對比Table 1 Comparison of both the matching accuracy and used time

4 小結(jié)

針對刑偵中大規(guī)模鞋印圖像快速查詢應(yīng)用需求，本文基于鞋印圖像的SIFT局部特征，再結(jié)合稀疏編碼與反向索引技術(shù)，提出了一種CS-RI鞋印圖像快速比對算法，且利用VS2010+OpenCV編程環(huán)境，實現(xiàn)了所提算法而開發(fā)了一套鞋印比對測試系統(tǒng)，其主要工作是將SIFT特征、稀疏編碼與反向索引技術(shù)用于鞋印比對問題，并進(jìn)行了對比試驗與分析。實驗結(jié)果表明，CS-RI算法比對精度高且速度快，是一種非常有效的鞋印比對算法。在后續(xù)工作中，將在更大規(guī)模的殘缺鞋印集中做進(jìn)一步驗證，由于鞋印比對在刑偵中具有重要應(yīng)用價值，是一個值得進(jìn)行深入研究的課題。