基于SIFT、K-means和BOF的鞋底痕跡檢索

焦 揚 楊傳穎 石 寶

(內蒙古工業大學信息工程學院 內蒙古 呼和浩特 010080)

0 引 言

鞋印圖像是犯罪現場偵查中遺留率較高的一種證物，具有穩定性、易提取性等特點，在刑事偵查工作中有著十分重要的作用，是案件偵破以及法院取證中不可或缺的一部分[1]。刑事偵查人員將犯罪現場的鞋底痕跡花紋圖像與以往案件采集到的圖像信息比對，進行串并案件的處理，提高犯罪偵查效率。如今各地公安機關對鞋底痕跡花紋圖像信息管理各不相同，存在許多弊端，大多采用人工管理的模式，方式單一、任務量大、精度低，很難實現跨省等較大范圍的串并案件偵破。鞋底痕跡花紋的管理和應用與指紋相比存在許多困難，利用基于內容的圖像處理技術，可以更好地實現鞋底痕跡花紋的檢索與應用，減少人力、物力的消耗，降低了人工識別引起的二義性，增強刑偵人員破案效率[2]。

基于內容的圖像檢索(Content-BasedImageRetrieval,CBIR)利用在圖像中提取的低層視覺特征和語義內容特征描述圖像內容[3],對提取的內容進行相似度排序，實現檢索過程。主要提取顏色、紋理、形狀和平面空間位置特征來比較圖像相似度。鞋底痕跡花紋圖像因圖像質量較低需要對圖像進行預處理，圖像檢索主要以紋理特征、形狀特征和空間位置特征為主。文獻[1]采用Gabor變換域的積分直方圖作為鞋底痕跡花紋圖像紋理特征進行檢索，查準率為46.77%，較全局最優匹配方法提高了4.82%。文獻[4]通過對Laws掩模和紋理圖像卷積計算能量對鞋底痕跡花紋分類，分為線條型圖案、點型圖案、其他型圖案，但是對于其他類型圖案中交織型、邊塊型、圓型花紋還需要進一步識別計算。文獻[5]提出了一種使用SIFT提取關鍵點構成特征向量，計算每個鞋印圖像與數據庫中圖像的交叉關聯，進行相似度排序。文獻[6]基于小波變換的邊緣檢測、拐點檢測以及霍夫變換的方法，通過提取一些特征向量，長、寬、長寬比、面積等，計算出該圖像不同的紋理特征，前10幅圖片的查準率為91.1%，但是此方法不適合殘缺圖像檢索。

1 算法設計

本文提出的鞋底痕跡花紋圖像檢索方法的實現流程如圖1所示。由于案發現場復雜多變，對提取到的鞋底痕跡花紋圖像首先要進行圖像預處理，將鞋印圖像與背景分離，對圖像的尺寸、顏色歸一化；然后采用SIFT算法特征提取；接著使用K-means算法[7]聚類生成類中心點，構建視覺特征包(BagofFeatures,BOF)，這是本文的研究重點；最后根據相似度匹配實現圖像檢索。

圖1 鞋底痕跡花紋圖像檢索流程

1.1 圖像預處理

圖像的質量與圖像檢索效率成正比。因鞋底痕跡花紋圖像受到犯罪現場環境、人為破壞等其他因素影響，圖像質量差。為了提高檢索效率，需要對提取到的圖像進行預處理，減少在檢索過程中的干擾。預處理過程為：

(1) 直方圖均衡化[8]使變換后圖像灰度的概率密度呈現均勻分布，增強圖像對比度，減弱背景對鞋印圖像的影響，具體步驟如算法1所示。

算法1 直方圖均衡化算法。

輸入：G個灰度級大小為M×N的圖像

輸出：灰度級gq的圖像

Step 1 創建一個長為G的數組H，初始化為0。

Step 2 掃描每個像素添加到數組H中，當像素p具有亮度gp時，H?gp」+=1，形成圖像直方圖。

Step 3 形成累計的直方圖Hc：Hc[0]=H[0]，Hc[p]=Hc[p-1]+H[p]，其中p=1,2,…,G-1。

Step 5 重新掃描圖像，輸出圖像設置為gq=T?gp」。

(2) 非局部均值濾波算法(Non-local Means,NLM) 因環境、人為等多種因素的影響，圖像中干擾信息過多，需要濾除部分噪聲，在直方圖均衡化的基礎上進一步增強圖像。對于一個噪聲圖像v(x)={v(x)|x∈I}，像素點x的鄰域稱為Nx，NLM去噪結果如下：

(1)

式中:I是一個較大范圍的搜索框；權值w(x,y)表示像素點x和y間的相似度，值由v(Nx)、v(Ny)間的距離決定。

(2)

(3) 最大類間方差算法(Otsu)[9]對圖像進行二值化處理，將背景與圖像分離，增加圖像信息量：

g=ω1×ω2×(μ1-μ2)2

(3)

式中:ω1、ω2分別是背景、前景的像素占比；μ1、μ2分別是背景、前景的灰度平均值。

鞋底痕跡花紋圖像經預處理后效果如圖2所示。(a)為犯罪現場提取的鞋底痕跡花紋圖像，(b)為進行預處理后的圖像。

(a) (b)圖2 犯罪現場鞋印圖像與預處理后圖像

1.2 SIFT特征提取

通過提取圖像特征點可以區分不同的圖像特征，針對鞋底痕跡花紋圖像的特點，綜合分析圖像檢索特征提取，確定使用SIFT特征提取算法。SIFT算法是1999年由Lowe[10]教授提出，該算法在不同的尺度空間上查找特征點，并且計算出方向，對圖像識別具有魯棒性。算法主要流程描述如下。

一個圖像的尺度空間L(x,y,σ)由高斯函數G(x,y,σ)與原始圖像I(x,y)卷積運算得到：

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

(4)

找到高斯差分算子(Difference of Gaussian,DOG)的極值點，將每個像素點與其相鄰的像素點進行比較，共26個像素點，以確保在尺度空間和二維圖像空間中都檢測到極值點。如圖3所示，如果中間方塊是最大值或最小值，該點被選為候選特征點。

圖3 DOG圖像

以上檢測為離散空間的極值點，與連續空間極值點存在偏差。因此，有必要計算該點與極值點之間的距離。使用DOG函數的Taylor展開式：

(5)

式中X=(x,y,σ)T，通過求解式(5)得到：

(6)

對應的極值點方程為：

(7)

為了使描述子對圖像具備旋轉不變性，使用梯度直方圖指定每個關鍵點的方向，點(x,y)處的梯度幅值和方向的計算公式為：

(8)

(9)

使用直方圖統計梯度幅值和梯度方向的計算結果，且直方圖將方向劃分為36個部分，每個部分10度，直方圖中峰值方向即為關鍵點的主方向，如圖4所示。

圖4 關鍵點主方向直方圖

2 圖像檢索

采用SIFT提取圖像特征點，每個特征點可以表示為一個特征向量，通過K-means聚類算法對鞋底痕跡花紋圖像庫的特征向量進行聚類生成類心，通過特征點與類心的比對生成頻數表加權重后生成BOF(Bag of Features)模型[11]，最后，通過相似度計算與排序生成檢索結果。

2.1 K-means聚類算法

首先，我們需要初始化k個聚類中心，假設鞋底痕跡花紋圖像樣本集D={x1,x2,…,xn}，在數據集D中隨機選取k個樣本作為初始的k個聚類中心μj，j=(1,2,…,k)。

(10)

E的值越小，表示聚類樣本相似度越高，通過K-means聚類算法獲得k個聚類中心，代表不同類別的特征點。偽碼如算法2所示。

算法2 K-means聚類算法。

輸入：包含n個對象的圖像數據集D={x1,x2,…,xn}、k個聚類中心

輸出：簇C={C1,C2,…,Ck}

令Cj=?(1≤j≤k)

fori=(1,2,…,n) do

根據距離最近的均值向量確定xi的簇

將樣本xi加入相應的簇中

end

forj=(1,2,…,k) do

else

保持均值向量不變

end

end

2.2 BOF算法

BOF算法與文本檢索領域的BOW(Bag of works)算法相似，將每幅圖片描述為無序的局部特征集合，使用K-means算法聚類后獲得k個聚類中心，每個聚類中心對應不同的特征點形成碼字，所有聚類中心形成一個視覺詞典，被稱為碼書。通過計算局部特征出現的次數以生成直方圖向量,過程如圖5所示。

圖5 構建BOF向量

3 實驗及其結果分析

本文實驗采用硬件平臺為Intel Core i7-4790 CPU 3.60 GHz，8.00 GB RAM。基于MATLAB軟件作為技術平臺，實現對鞋底痕跡花紋的檢索。實驗數據集由西郵圖像與信息處理研究所提供。為了測試本文算法的魯棒性，從中選擇300幅包含不同類型的鞋底痕跡花紋的圖像，例如點型、波折型、圓型、波浪型、方塊型、交織型等多種鞋底花紋圖像，其中圖像像素寬度由鞋印寬度決定，高度均為586像素，分辨率為96 dpi。圖6為所選數據集中的部分圖像。

圖6 所選數據集中的部分圖像

性能評價指標選用圖像檢索領域常用的查準率(P)和查全率(R)：

(11)

(12)

另外，還采用了F-Measure函數作為評價標準：

(13)

式中：β是參數。

為了檢驗本文算法對旋轉、尺度縮放、殘缺等圖像是否具有穩定性，將圖像在0～360°每間隔45°旋轉一次，共旋轉8次。截取部分鞋底花紋圖像以及處理圖片達到部分殘缺的效果，再對每幅圖像進行相同比例縮放0.8、1、1.2倍，經處理后，測試圖像庫共包含9 900幅圖像。圖7為隨機選取的某一鞋底痕跡花紋圖像。

圖7 隨機選取的鞋印圖像

圖8給出了返回的檢索結果前12名，其中加邊框的圖像為查詢到屬于同一鞋印的圖像，根據圖像不同返回結果數量，計算不同的查準率與查全率，如表1所示。

圖8 返回檢索結果前12名

表1 不同返回結果的查準率與查全率

可以看出，查準率隨著返回數量的增加而呈下降趨勢，而查全率則為上升趨勢。隨機選取5幅鞋印圖片進行檢索，計算返回結果數量為30幅相似圖片的查準率與查全率以及平均值，其數據如表2所示。

表2 隨機圖像的查準率與查全率及均值

可以看出，隨機選取圖片檢索具有一定的穩定性，在返回結果數量為前30幅圖片時查詢結果浮動很小，根據表中平均值計算出F1-Measure的值為0.77，說明實驗方法比較有效。

本文實驗對圖像進行SIFT特征提取后使用K-means算法聚類，生成k個聚類中心點，k值的選取對圖像檢索的結果有較大的影響。圖9展示了k取值不同時，查準率和查全率結果對比。可以看出，當k=500時進行圖像檢索，查準率與查全率最優。

圖9 不同k值時的檢索結果

綜上實驗結果分析表明，本文采用SIFT特征描述對圖片的旋轉、縮放、光照等變化具有不變性，且對殘缺的鞋底痕跡花紋有較強的魯棒性。

4 結 語

本文提出了基于SIFT、K-means和BOF的算法用于鞋底痕跡花紋圖像檢索。實驗結果表明：該方法檢索準確率較高且對圖像的旋轉、縮放等具有良好的不變性。鞋印檢索在刑偵方面是一個值得研究的課題，在后續的研究中可以通過改進K-means算法聚類中心的數目達到最優值，進一步提高鞋印圖像的查準率。