一種基于詞匯樹的鞋印圖像可伸縮檢索方法

劉 偉, 姜樂怡, 徐晨苗, 王富平, 劉 穎

(1. 電子信息現(xiàn)場勘驗應用技術公安部重點實驗室, 陜西 西安 710121;2. 陜西省無線通信與信息處理技術國際合作研究中心, 陜西 西安 710121;3. 西安郵電大學 計算機學院, 陜西 西安 710121; 4. 西安郵電大學 通信與信息工程學院, 陜西 西安 710121)

鞋印是案發(fā)現(xiàn)場常見的一種物證痕跡，在案件偵破過程中發(fā)揮著重要作用。對案發(fā)現(xiàn)場發(fā)現(xiàn)的鞋印圖像進行查詢比對在為公安機關縮小偵查范圍、提供破案線索、串并案分析以及提供訴訟證據等方面發(fā)揮著重要作用。

早期的鞋印圖像的檢索主要采用了基于文本的人工標注的方式，為了克服在基于文本的圖像檢索中人工標注的低效性、主觀性和工作量大等弊端，基于內容的圖像檢索(content-based image retrieval，CBIR)方法得到了廣泛的研究與應用[1-3]。CBIR中的典型方法是按例查詢(query by example，QBE)，即通過計算查詢圖像的特征并與圖像庫對應的特征庫進行匹配來尋找與查詢圖像在內容上最“相似”的圖像。例如文[4]采用了一種基于紋理與形狀特征融合的檢索算法，使用街區(qū)距離作為相似性度量對刑偵圖像進行檢索；文[5]提出了一個完整的鞋印圖像匹配框架，設計了傅里葉功率譜密度函數(shù)用于校正輸入的傾斜鞋印圖像，校正后的圖像通過計算其相關度來確定它們之間的相似性以實現(xiàn)匹配。由于刑事勘驗中采集的鞋印圖像具有殘缺不全且含有噪聲的特點，QBE框架下的圖像特征提取算法在刑偵圖像檢索中效果并不理想[6]。

一些研究者采用了局部特征如SIFT算子[7]來進行圖像檢索。局部特征算子能更好地描述圖像內容。例如文[8]采用SIFT特征用于鞋印圖像識別與檢索；文[9]使用3個鞋印圖像數(shù)據庫，評估了幾種鞋印圖像識別算法的性能，認為基于圖像局部描述子的算法性能較好；文[10]提出了2種描述圖像局部特征的算子并用于鞋印圖像檢索；文[11]用SIFT特征描述圖像內容，用隨機抽樣一致算法進行圖像的匹配。基于圖像局部特征的方法在部分鞋印圖像檢索中取得了很好的結果，但是已有的文獻均未研究當鞋印圖像數(shù)據庫的容量動態(tài)變化時的檢索性能。

隨著圖像數(shù)據庫的擴大，詞匯樹在圖像檢索中得到了廣泛的應用。詞匯樹的結構特點是將海量的鞋印圖像數(shù)據量化為有限葉子節(jié)點上的詞頻向量，每個詞頻向量取決于詞匯樹的深度和聚類中心的個數(shù)。在鞋印圖像檢索階段，只需要將查詢圖像的詞頻向量與葉子節(jié)點上的詞頻向量進行比較就可以快速得出檢索結果。正是因為具有如此的特點，適用于海量數(shù)據檢索[12]。

為了在海量動態(tài)變化的鞋印圖像數(shù)據庫中提高檢索精度，降低檢索時間，本文擬提出一種基于詞匯樹的鞋印圖像可伸縮檢索方法。該方法首先提取鞋印圖像的SIFT局部特征，采用層次性聚類方法生成詞匯樹；然后，基于詞匯樹計算查詢圖像和數(shù)據庫圖像之間的相似性以得到檢索結果。最后擬在鞋印圖像數(shù)據庫上的驗證本文所提方法的有效性。

1 算法設計

1.1 算法原理

算法原理如圖1所示。

圖1 算法原理

如圖1所示，首先計算鞋印數(shù)據庫圖像的SIFT特征，并采用層次型K均值聚類算法對所有圖像的特征進行聚類以構建詞匯樹，并生成圖像對應的文檔向量。文檔向量記錄著該圖像在詞匯樹節(jié)點上的詞頻向量。其次，查詢時計算查詢圖像的SIFT特征，根據詞匯樹中的聚類中心與查詢圖像所有特征分量之間的距離得到查詢圖像的文檔向量。最后，計算查詢圖像和數(shù)據庫圖像文檔向量之間的余弦距離以得到檢索結果。

1.2 鞋印的特征提取

SIFT算子[7]可以有效檢測鞋印圖像的局部特征，它通過對圖像尺度的特征選擇，建立圖像的多尺度空間；在不同尺度下檢測到相同的特征點，確定特征的尺度和位置；把對比度較低的點和邊緣響應點刪除，以提取圖像的旋轉不變特征描述符。

SIFT算法主要包含4個步驟。

步驟1在鞋印圖像中建立空間尺度找到特征選點。圖像的尺度空間

L(x,y,σ)=G(x,y,σ)I(x,y)。

其中，(x,y)為圖像I的空間坐標，σ是尺度空間因子，G(x,y,σ)表示可變尺度高斯函數(shù)。

步驟2通過包含常數(shù)因子k的高斯尺度差分空間

D(x,y)=L(x,y,kσ)-L(x,y,σ)

進行曲線擬合，尋找極值點，確定特征點和關鍵點，刪除邊緣響應和不穩(wěn)定點。

步驟3確定特征點的幅度和方向。對于每個圖像樣本中的像素(x,y)，計算其梯度幅度m(x,y)和方向θ(x,y)，其中

步驟4提取特征描述符。

使用SIFT算子提取鞋印圖像局部特征，如圖2所示。

圖2 鞋印圖像的SIFT特征提取

1.3 詞匯樹的構造

詞匯樹是實現(xiàn)鞋印圖像可伸縮檢索的關鍵結構，可用于物體識別[12]。使用該方法進行鞋印圖像可實現(xiàn)伸縮檢索。詞匯樹構造算法如下。

輸入鞋印圖像數(shù)據庫

輸出構建的詞匯樹

(1) 計算鞋印圖像數(shù)據庫中每一幅圖像的SIFT特征，全部特征數(shù)據組成矩陣X；

(2) 對X進行層次聚類。先對X進行一次K均值聚類，得到k個聚類中心和聚類簇；然后對聚類后的每一簇依次進行K均值聚類，直至達到指定詞匯樹的深度，完成詞匯樹構建。在完成每一次聚類后，需要計算數(shù)據庫圖像在每個簇中的詞頻向量，該詞頻向量用于圖像檢索的相似性度量。

上述算法中的聚類中心即為視覺詞(visual word)，是詞匯樹上的一個節(jié)點。每個節(jié)點對應有一個倒排文件。該文件記錄數(shù)據庫圖像在該簇中的特征點數(shù)。

1.4 可伸縮圖像檢索

為了實現(xiàn)可伸縮檢索，使用文檔模型來描述鞋印圖像內容，即對圖像中出現(xiàn)在每一聚類簇中的特征個數(shù)進行統(tǒng)計。假設第i幅圖像在每一聚類簇中的SIFT特征點個數(shù)分別為n1,n2,…,nc，其中c為聚類簇的個數(shù)，則所有鞋印圖像可表示為c×N的矩陣D，其中N為數(shù)據庫中的鞋印圖像個數(shù)。使用詞頻-逆文本頻率(term frequency-inverse document frequency，TF-IDF)指數(shù)方法用于加權。詞頻和逆文本頻率分別為

(1)

其中，F(xiàn)T表示詞頻，bi表示一幅圖像在第i個聚類簇中的特征點個數(shù)，NF表示該圖像提取的特征點數(shù)目。FID表示逆文本頻率，N表示數(shù)據庫中的圖像總數(shù)，Ii表示在第i個聚類簇中存在特征點的鞋印圖像個數(shù)。

利用式(1)，數(shù)據庫中每一幅圖像的權重可以計算為FT×FID，可得到一個c×N的權重矩陣W，利用W對矩陣D進行加權得結果矩陣DW。

查詢過程為，先提取查詢圖片的SIFT特征，然后計算查詢圖像的每一個特征與詞匯樹中每一個聚類中心之間的歐式距離。計算每個聚類簇中的特征點個數(shù)，將查詢圖像所有特征點記為向量q。然后用式(1)計算查詢圖像的權重并進行加權。計算查詢加權向量qW和矩陣DW中每一列的余弦距離，確定最終的檢索結果。

2 實驗結果與分析

為了考查基于詞匯樹的可伸縮檢索框架的性能，使用圖像檢索中的按例檢索(query by example，QBE)框架[2]進行對照。

2.1 實驗數(shù)據與環(huán)境

本文實驗環(huán)境參數(shù)為CPU為Intel Core i3雙核(64位處理器)，3.4 GHz；內存為8 G；操作系統(tǒng)為Windows 8.1中文版(64位系統(tǒng))；實驗程序用Matlab 2010b編寫。

實驗數(shù)據庫中數(shù)據來源，包括依托電子信息現(xiàn)場勘驗應用技術公安部重點實驗室采集的實際案件現(xiàn)場勘驗鞋印圖像以及從互聯(lián)網上采集的鞋印圖像。數(shù)據庫中包含了1 916個被試的總計9 691幅圖像。每個被試視為1個語義類，采集了2～14幅不等的鞋印圖像。數(shù)據庫中部分圖像示例，如圖3所示。

圖3 鞋印圖像數(shù)據庫示例

實驗中從每幅圖像上提取100個特征點，層次聚類時K值為3，詞匯樹深度為3。計算上述指標時，從每個語義類中隨機選取2幅圖像(有些被試僅采集了2幅圖像)，依次作為查詢圖像進行檢索。這樣的過程共進行10輪，取所有語義類檢索結果指標的平均值作為最終評價指標。

2.2 結果與分析

實驗采用查準率、召回率和檢索單幅圖像所需時間等3個指標作為評價算法性能的指標。查準率和召回率是圖像檢索中的標準評價指標[4]，查準率是指檢索出圖像中正確圖像的比例，召回率是指檢出正確圖像數(shù)目占整個數(shù)據庫中所有準確圖像的比例。

為了驗證本文方法的可伸縮性能，實驗中依次取數(shù)據庫尺寸為1 000、2 000、3 000、4 000、5 000、6 000、7 000、8 000和9 000幅圖像，分別計算不同數(shù)據庫尺寸下的QBE框架和本文方法對應的指標。不同數(shù)據庫尺寸下查準率、召回率和檢索單幅圖像所需時間的實驗結果，如圖4所示。

由圖4可知，在查準率和檢索時間上，本文算法優(yōu)于QBE框架，在召回率指標上則略低于QBE框架。當數(shù)據庫的大小每增加1 000幅圖像時，本文方法的單幅圖像的查準率平均下降0.008，QBE框架平均下降0.009；本文方法的單幅圖像檢索時間平均增加0.119 s，QBE框架平均增加1.120 s。導致這一結果的原因可能為，詞匯樹中節(jié)點的個數(shù)不會增加且用于相似度比較的矩陣較小。而QBE框架隨著數(shù)據庫尺寸的增大，其需要進行相似度比較的矩陣個數(shù)不僅隨數(shù)據庫增大而增大，且其矩陣自身也較大，造成QBE框架檢索需要較長時間。這說明所提方法在針對鞋印圖像數(shù)據庫規(guī)模增長的情況時具有可伸縮特性，具有應用價值。

圖4 實驗結果

3 結語

提出了一種基于詞匯樹的鞋印圖像可伸縮檢索方法。該方法提取鞋印圖像的SIFT局部特征，采用層次性聚類方法生成詞匯樹；基于詞匯樹計算查詢圖像和數(shù)據庫圖像之間的相似性以得到檢索結果。相對于QBE框架，本文方法在查準率上平均提高9%，在檢索時間上平均下降了4.927 s，證實了本文所提方法的有效性。