焦 揚(yáng) 楊傳穎 石 寶

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

0 引 言

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

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

1 算法設(shè)計(jì)

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

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

1.1 圖像預(yù)處理

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

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

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

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

輸出：灰度級gq的圖像

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

Step 2 掃描每個(gè)像素添加到數(shù)組H中，當(dāng)像素p具有亮度gp時(shí)，H?gp」+=1，形成圖像直方圖。

Step 3 形成累計(jì)的直方圖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ǔ)上進(jìn)一步增強(qiáng)圖像。對于一個(gè)噪聲圖像v(x)={v(x)|x∈I}，像素點(diǎn)x的鄰域稱為Nx，NLM去噪結(jié)果如下：

(1)

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

(2)

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

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

(3)

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

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

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

1.2 SIFT特征提取

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

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

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

(4)

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

圖3 DOG圖像

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

(5)

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

(6)

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

(7)

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

(8)

(9)

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

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

2 圖像檢索

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

2.1 K-means聚類算法

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

(10)

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

算法2 K-means聚類算法。

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

輸出：簇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個(gè)聚類中心，每個(gè)聚類中心對應(yīng)不同的特征點(diǎn)形成碼字，所有聚類中心形成一個(gè)視覺詞典，被稱為碼書。通過計(jì)算局部特征出現(xiàn)的次數(shù)以生成直方圖向量,過程如圖5所示。

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

3 實(shí)驗(yàn)及其結(jié)果分析

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

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

性能評價(jià)指標(biāo)選用圖像檢索領(lǐng)域常用的查準(zhǔn)率(P)和查全率(R)：

(11)

(12)

另外，還采用了F-Measure函數(shù)作為評價(jià)標(biāo)準(zhǔn)：

(13)

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

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

圖7 隨機(jī)選取的鞋印圖像

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

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

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

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

表2 隨機(jī)圖像的查準(zhǔn)率與查全率及均值

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

本文實(shí)驗(yàn)對圖像進(jìn)行SIFT特征提取后使用K-means算法聚類，生成k個(gè)聚類中心點(diǎn)，k值的選取對圖像檢索的結(jié)果有較大的影響。圖9展示了k取值不同時(shí)，查準(zhǔn)率和查全率結(jié)果對比?？梢钥闯觯?dāng)k=500時(shí)進(jìn)行圖像檢索，查準(zhǔn)率與查全率最優(yōu)。

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

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

4 結(jié) 語

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