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

焦 揚 楊傳穎 石 寶

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

0 引 言

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

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

1 算法設(shè)計

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

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

1.1 圖像預(yù)處理

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

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

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

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

輸出：灰度級gq的圖像

Step 1 創(chuàng)建一個長為G的數(shù)組H，初始化為0。

Step 2 掃描每個像素添加到數(shù)組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 重新掃描圖像，輸出圖像設(shè)置為gq=T?gp」。

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

(1)

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

(2)

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

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

(3)

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

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

(a) (b)圖2 犯罪現(xiàn)場鞋印圖像與預(yù)處理后圖像

1.2 SIFT特征提取

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

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

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

(4)

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

圖3 DOG圖像

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

(5)

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

(6)

對應(yīng)的極值點方程為：

(7)

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

(8)

(9)

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

圖4 關(guān)鍵點主方向直方圖

2 圖像檢索

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

2.1 K-means聚類算法

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

(10)

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

算法2 K-means聚類算法。

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

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

令Cj=?(1≤j≤k)

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

根據(jù)距離最近的均值向量確定xi的簇

將樣本xi加入相應(yīng)的簇中

end

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

else

保持均值向量不變

end

end

2.2 BOF算法

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

圖5 構(gòu)建BOF向量

3 實驗及其結(jié)果分析

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

圖6 所選數(shù)據(jù)集中的部分圖像

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

(11)

(12)

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

(13)

式中：β是參數(shù)。

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

圖7 隨機選取的鞋印圖像

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

圖8 返回檢索結(jié)果前12名

表1 不同返回結(jié)果的查準率與查全率

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

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

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

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

圖9 不同k值時的檢索結(jié)果

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

4 結(jié) 語

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