李大湘, 吳　倩, 李　娜, 劉　穎

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

圖像分塊及惰性多示例學(xué)習(xí)鞋印圖像識別

李大湘1,2, 吳倩1, 李娜1,2, 劉穎1,2

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

摘要:結(jié)合圖像分塊與惰性多示例學(xué)習(xí)(MIL)給出一種鞋印識別新算法。將整個鞋印圖像當(dāng)作包，根據(jù)腳底生物特征比例，采用均勻網(wǎng)格分塊的方法將鞋印圖像分成15個子塊，并提取每個子塊的紋理與形狀特征，當(dāng)作包中的示例，將鞋印圖像識別問題轉(zhuǎn)化成MIL問題；然后，將推土機(jī)距離(EMD)應(yīng)用到K最近鄰 (KNN)算法中，得出一種惰性MIL新方法用于鞋印識別。在包含5種不同類型花紋的鞋印庫中進(jìn)行實(shí)驗(yàn)，識別正確率可達(dá)91.28%，較之基于歐氏距離的KNN算法，識別精度平均提高4.0%。

關(guān)鍵詞:多示例學(xué)習(xí)；鞋印圖像識別；紋理-形狀特征

鞋印是犯罪現(xiàn)場最常見的痕跡物證[1]。隨著刑偵科學(xué)的發(fā)展，從犯罪現(xiàn)場收集的鞋印圖像越來越多。從大規(guī)模足跡庫中找到與犯罪現(xiàn)場相匹配的鞋印，需要高效的圖像自動識別技術(shù)[2]。已有鞋印識別算法[3-7]，多是對整幅鞋印圖像提取其全局紋理或形狀特征，易受圖像背景干擾，鞋印花紋在結(jié)構(gòu)上的整體相似性不易到到反映，識別精度有限。

本文擬將圖像當(dāng)作包(bag)，圖像子塊的視覺特征當(dāng)作包中的示例(instance)，基于圖像分塊與惰性多示例學(xué)習(xí)(multi-instancelearning,MIL)[8],給出一種鞋印識別新方法。

1基于“網(wǎng)格分塊”的多示例建模

對鞋印圖像進(jìn)行高斯平滑與直方圖均衡化預(yù)處理，采用“網(wǎng)格分塊”的方法將鞋印圖像劃分成多個子塊，并提取每個子塊的紋理和形狀等底層特征，作為包(圖像)中的示例，將鞋印圖像識別問題轉(zhuǎn)化成標(biāo)準(zhǔn)的MIL問題。

1.1網(wǎng)格分塊

鞋印圖像可分為腳掌區(qū)、腳弓區(qū)和腳跟區(qū)三部分，并普遍遵循0.49∶0.20∶0.31的生物特征分割比例[2]。腳弓區(qū)通常殘缺嚴(yán)重，紋理很少，為減少計算量，對其可不予考慮，而只把腳掌區(qū)和腳跟區(qū)采用均勻網(wǎng)格分塊的方法劃分為15個子塊，如圖1所示。

圖1　鞋印圖像網(wǎng)格分塊

1.2特征提取

鞋印識別主要依賴圖像的紋理與形狀特征。

(1) 灰度共生紋理特征

分別針對距離差分值(1,0)、(1,1)、(0,1)與(-1,1)，計算每個“子塊”的灰度共生陣G及其能量E、熵H、對比度C和相關(guān)系數(shù)R，作為“子塊”的紋理特征。

設(shè)某對灰度值(m,n)(1≤m,n≤L)對應(yīng)的灰度共生陣元素為g(m,n),那么[9]

其中

(2) 不變矩形狀特征

設(shè)“子塊”f在(x,y)處的像素值為f(x,y)，定義“子塊”f的p+q階原點(diǎn)矩Mp,q和p+q階中心矩up,q分別為[10]

其中p和q為非負(fù)整數(shù)，H和W分別表示子塊f的高和寬，(xc,yc)為“子塊”f的重心，即

進(jìn)而定義規(guī)范化中心矩

基于歸一化的二階和三階中心矩，可構(gòu)造7個不變矩[10]

ψ1=η2,0+η0,2,

ψ3=(η3,0-3η1,2)2+(η0,3-3η2,1)2,

ψ4=(η3,0+η1,2)2+(η0,3+η2,1)2,

ψ5=(η3,0-3η1,2)(η0,3+η1,2)[(η3,0+

η1,2)2-3(η0,3+η1,2)2]+

(3η2,1-η0,3)(η2,1+η0,3)[3(η3,0+

η1,2)2-(η0,3+η2,1)2],

ψ6=(η2,0-η0,2)[(η3,0+η1,2)2-

(η0,3+η2,1)2]+4η1,1(η3,0+

η1,2)(η0,3+η2,1),

ψ7=(3η2,1-η0,3)(η3,0+η1,2)[(η3,0+

η1,2)2-3(η0,3+η2,1)2]+

(3η1,2-η3,0)(η2,1+η0,3)[3(η3,0+

η1,2)2-(η0,3+η2,1)2]。

通過分塊與特征提取，可將任一鞋印圖像轉(zhuǎn)化成多示例包

B={Xt∈23: t=1,2,…,15}。

2惰性MIL鞋印識別算法

記由N個多示例包(鞋印圖像)組成的訓(xùn)練集

D={(Bi,yi):i=1,2,…,N},

其中

Bi={Xi,j: j=1,2,…,15}(i=1,2,…,N)

表示由15個示例Xi,j∈23(j=1,2,…,15)組成的第i個多示例包，yi為Bi的類別標(biāo)號。

2.1惰性MIL算法

為了用K最近鄰(K-nearestneighbor，KNN))惰性算法進(jìn)行鞋印圖像識別，采用推土機(jī)距離(EarthMoversDistance，EMD)[11]來度量多示例包之間的相似度。

分別記第r幅和第s幅鞋印圖像對應(yīng)的多示例包為

Br={Xr,j: j=1,2,…,15},

Bs={Xs,k: k=1,2,…,15},

兩者中的示例Xr,j與Xs,k之間的歐氏距離

cj,k=‖Xr,j-Xs,k‖,

則求解多標(biāo)例包Br與Bs之間的EMD距離，可轉(zhuǎn)化成線性優(yōu)化問題

即尋找最優(yōu)流量

F=(aj,k)15×15,

以使其目標(biāo)函數(shù)達(dá)到最小值。

確定F之后，定義Br與Bs之間的EMD距離為

2.2鞋印識別算法

惰性MIL鞋印識別算法可描述如下。

輸入帶有類別標(biāo)號的鞋印圖像訓(xùn)練集D，待識別的圖像I，以及KNN算法中的K值。

輸出圖像I的識別結(jié)果。

步驟1對D中的每幅圖像進(jìn)行分塊與特征提取，將其構(gòu)造成多示例包

D={(Bi,yi): i=1,2,…,N}。

步驟2對待識別圖像I進(jìn)行分塊與特征提取，將其構(gòu)造成多示例包

I={Xj: j=1,2,…,15}。

步驟3計算多示例包I與D中每個包之間的EMD距離，選擇I的K近鄰。

步驟4統(tǒng)計I的K近鄰類別標(biāo)號，將I歸入標(biāo)號最多的類別。

3實(shí)驗(yàn)結(jié)果

選取150幅鞋印圖像作為訓(xùn)練測試集，這些圖像分為折波型、交織型、線條型、邊塊型與圓點(diǎn)型(其類型號依次記為1至5)，每類30幅。對所有圖像進(jìn)行方向校正、二值化及尺度歸一化處理，部分樣圖如圖2所示。

圖2 訓(xùn)練測試集圖例

從每類圖像中隨機(jī)選取10幅組成訓(xùn)練集，其余20幅組成測試集，設(shè)置KNN算法的參數(shù)K為10。經(jīng)10次隨機(jī)實(shí)驗(yàn)，得平均識別準(zhǔn)確率的混淆矩陣

其中對角線上的數(shù)據(jù)表示每類的識別準(zhǔn)確率，其余數(shù)據(jù)表示相應(yīng)的錯誤率。

對訓(xùn)練測試集中所有鞋印圖像提取其全局“灰度共生紋理”與“不變矩形狀特征”，將新算法與基于歐氏距離的KNN算法[12]進(jìn)行對比。

從每類圖像中隨機(jī)選取10幅組成訓(xùn)練集，其余20幅組成測試集。分別設(shè)置KNN算法的參數(shù)K為5或10。經(jīng)10次隨機(jī)實(shí)驗(yàn)，所得平均查全率與查準(zhǔn)率如表1和表2所示，可見，在不同參數(shù)設(shè)置下，新方法均優(yōu)于基于歐氏距離的KNN算法。

表1　識別精度對比(K=5)

表2　識別精度對比(K=10)

在鞋印圖像識別時，依據(jù)多個相關(guān)子塊的共同作用，可以獲得更佳識別效果。EMD距離能自動在兩個圖像的不同子塊間完成最佳匹配，更好地反映了圖像間的整體相似度，對圖像分塊精度不太敏感,這正是新算法精度得以提升的原因所在。

4結(jié)語

針對鞋印圖像識別問題，基于圖像分塊與惰性MIL算法，給出一種鞋印識別新方法，對比實(shí)驗(yàn)結(jié)果表明，該鞋印識別方法簡單有效，且識別精度高于基于歐氏距離的KNN算法。

參考文獻(xiàn)

[1]高毅, 陳青, 葉瀘鍵,等. 足跡邊緣弧度變化區(qū)分足別的量化研究[J]. 中國人民公安大學(xué)學(xué)報:自然科學(xué)版, 2013, 77(3): 6-10.

[2]劉家浩. 鞋印圖像識別算法的研究及系統(tǒng)實(shí)現(xiàn)[D]. 大連：大連海事大學(xué), 2012:3-28.

[3]SUHJ,CROOKESD,BOURIDANEA.Thresholdingofnoisyshoeprintimagesbasedonpixelcontext[J].PatternRecognitionLetters, 2007, 28(1): 301-307.

[4]馬臣. 基于LBP與形狀上下文的足跡比對算法研究[D]. 大連:大連海事大學(xué), 2014:5-24.

[5]CHAZALP,FLYNNJ,REILLYRB.AutomatedprocessingofshoeprintimagesbasedontheFouriertransformforuseinforensicscience[J].IEEETransactionsonPatternAnalysisandMachineIntelligence. 2005, 27(3): 341-350.

[6]KHANMA,TIDKESM.AutomatedProcessingofShoeprintImagesforUseinForensicScience[J].InternationalJournalofAdvancedResearchinComputerandCommunicationEngineering, 2013, 2(11): 4292-4294.

[7]NIBOUCHEO,BOURIDANEA,CROOKESD.RotationinvariantmatchingofpartialShoeprints[C]//13thInternationalMachineVisionandImageProcessingConference.IrelandDublin:IEEE, 2009: 94-98.

[8]李大湘，趙小強(qiáng)，劉穎，等. 融合SIFT與MIL的紅外人臉識別方法[J]. 西安郵電學(xué)院學(xué)報，2012，17(4)：15-20.

[9]賈世杰,石薇,曾潔,等. 基于紋理特征的鞋底花紋識別分類[J]. 大連交通大學(xué)學(xué)報, 2008，29(1)：59-63.

[10]ALGARNIG,HAMIANEM.Anoveltechniqueforautomaticshoeprintimageretrieval[J].ForensicScienceInternational, 2008, 181(10): 10-14.

[11] 李大湘, 彭進(jìn)業(yè), 賀靜芳. 基于EMD-CkNN多示例學(xué)習(xí)算法的圖像分類[J]. 光電子·激光, 2010, 21(2): 302-306.

[12] 劉穎,黃源,高梓銘.刑偵圖像檢索中的特征提取及相似性度量[J].西安郵電大學(xué)學(xué)報, 2014, 19(6): 11-16.

[責(zé)任編輯:瑞金]

Shoeprintimagerecognitionalgorithmbasedonimageblockandlazymulti-instancelearning

LIDaxiang1,2,WUQian1,LINa1,2,LIUYing1,2

(1.SchoolofCommunicationandInformationEngineering,Xi’anUniversityofPostsandTelecommunications,Xi’an710121,China;2.MinistryofPublicSecurityKeyLaboratoryofElectronicInformationApplicationTechnologyforSceneInvestigation,Xi’an710121,China)

Abstract:A novel shoeprint recognition algorithm is proposed based on image block and lazy multi-instance learning (MIL). Firstly, the algorithm regards every shoeprint image as a bag. Then according to the proportion of foot biometrics, a uniform grid partitioning method is used to divide shoeprint image into 15 sub-blocks, and the texture and shape features of each block are extracted. Therefore the shoeprint image recognition problem is transform into a MIL problem. Secondly, the earth mover’s distance (EMD) is introduced into the traditional k-nearest neighbour (KNN) method to improve the accuracy of image similarity measure, and a new lazy MIL algorithm is designed for shoe prints recognition. Experimental results on shoeprint images datasets where contains five different types of shoeprint pattern indicate that the recognition accuracy of the new method can reach 91.28%, and that compared with Euclidean distance based KNN algorithm, its average recognition accuracy is improved by 4%.

Keywords:multi-instance learning (MIL), shoeprint image recognition, texture-shape features

doi:10.13682/j.issn.2095-6533.2016.01.011

收稿日期：2015-09-08

基金項(xiàng)目：公安部科技強(qiáng)警基礎(chǔ)工作專項(xiàng)基金資助項(xiàng)目(2014GABJC022)；陜西省自然科學(xué)基金資助項(xiàng)目(2013JM8031,2015KW-014)；陜西省教育廳科學(xué)研究計劃資助項(xiàng)目(15JK1660, 15JK1661)；中國博士后科研基金資助項(xiàng)目(2013M542386).

作者簡介：李大湘 (1974-)，男，博士，副教授，從事刑偵圖像分析研究。E-mail: www_ldx@163.com 吳倩 (1991-)，女，碩士研究生，研究方向?yàn)樾盘柵c信息處理。E-mail:35108809@qq.com

中圖分類號：TP391

文獻(xiàn)標(biāo)識碼：A

文章編號：2095-6533(2016)01-0059-04