基于稀疏編碼與反向索引的鞋印圖像比對(duì)算法

李大湘，邱 鑫 ，劉 穎

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

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

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

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

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

1 鞋印圖像局部特征提取

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

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

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

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

2 CS-RI鞋印比對(duì)算法

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

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

圖2 鞋印圖像比對(duì)操作流程（A：待比對(duì)的原始圖像；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 鞋印圖像比對(duì)查詢結(jié)果Fig.3 Query results on comparing shoeprint images

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

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

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

圖4 鞋印圖像比對(duì)操作流程及比對(duì)結(jié)果（A：嫌犯鞋印原始圖像；B：預(yù)處理后的目標(biāo)區(qū)域；C：比對(duì)結(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 比對(duì)精度與時(shí)間對(duì)比Table 1 Comparison of both the matching accuracy and used time

4 小結(jié)

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