基于kNN的鞋印花紋的圖像分割算法應(yīng)用檢驗(yàn)

馬華東 杜建軍

上海市公安局浦東分局刑偵支隊刑事科學(xué)技術(shù)研究所，上海 200125

在案發(fā)現(xiàn)場，工作人員采集到的鞋印通過技術(shù)手段的處理，為案件的偵破提供了強(qiáng)有力的線索。但是，在技術(shù)處理上，從復(fù)雜的背景中提取出有效的鞋印花紋，是一項挑戰(zhàn)性極大的工作，已成為足跡識別中的關(guān)鍵技術(shù)。雖然目前計算機(jī)的圖像識別能力已經(jīng)提升到一個新的高度，但是對于高層語義的理解，仍然面臨著極大的挑戰(zhàn)。

一、鞋印在刑偵中的應(yīng)用

在犯罪現(xiàn)場，工作人員可以采集到很多痕跡數(shù)據(jù)，比如指紋痕跡、相關(guān)工具痕跡、鞋印痕跡等。但是，與其他痕跡相比，鞋印更易獲取，而且在技術(shù)處理上也取得了很大的進(jìn)展，可以實(shí)現(xiàn)跨省市的協(xié)同分析，從而為案件的偵破提供了有力的證據(jù)。

因此，鞋印識別及其技術(shù)處理已經(jīng)成為刑事技術(shù)中非常重要的一項手段，借助現(xiàn)代信息技術(shù)，通過采集鞋印從而對獲取到的鞋印花紋進(jìn)行進(jìn)一步的處理，為刑事偵破注入了新的活力。然而，通常情況下，從現(xiàn)場獲得的鞋印是非常模糊的，并且不完整性大量存在，因此，要提取鞋印花紋是非常困難的。這就需要對鞋印花紋進(jìn)行分割，通過人機(jī)交互方式實(shí)現(xiàn)理想化的花紋提取。

二、圖像分割及其kNN算法

(一)圖像分割

圖像分割算法是從圖像處理到圖像分析的關(guān)鍵環(huán)節(jié)，與傳統(tǒng)的圖像分割算法相比，當(dāng)前的圖像分割更加著眼于交互式分割，其根據(jù)圖像的某些特征，將圖像組織成有所區(qū)別的像素集合，在交互過程中，執(zhí)行大量的迭代運(yùn)算，從而生成最優(yōu)解，實(shí)現(xiàn)特點(diǎn)像素點(diǎn)的提取。

在交互式圖像分割的研究領(lǐng)域，也有很多中方法，比如有從圖論出發(fā)的，有從目標(biāo)輪廓標(biāo)記出發(fā)的，等等。從目前來看，國內(nèi)外的很多交互式圖像分割算法，都是基于Graph Cut算法的，但是，從計算量來看，計算復(fù)雜度較高。因此，后續(xù)出現(xiàn)了很多算法對該算法進(jìn)行了優(yōu)化，比如Grab Cut等。以上算法在某些方面或應(yīng)用領(lǐng)域針對特定情況能夠?qū)D像進(jìn)行有效分割，但是在復(fù)雜的前景背景顏色分布下，其適用性仍然有限，魯棒性較弱，達(dá)不到一個好的分割效果。為此，本文提出基于kNN的圖像分割算法。

(二)kNN算法

1.算法原理

K近鄰算法(k-Nearest Neighbor，簡稱kNN)是“懶惰學(xué)習(xí)”的代表，既可處理分類問題，也可處理回歸問題，其本質(zhì)是基于一種數(shù)據(jù)統(tǒng)計的方法，在執(zhí)行過程中，將未知樣本點(diǎn)在附近找K個最近的點(diǎn)進(jìn)行投票，最后選擇k個最相似數(shù)據(jù)中出現(xiàn)次數(shù)最多的類別作為未知樣本點(diǎn)的分類。本文在MSRM算法初始花紋的提取基礎(chǔ)上，修正前景和背景的誤分情況，運(yùn)用相鄰區(qū)域的相似性，即基于kNN算法，確定標(biāo)記點(diǎn)周圍鄰接區(qū)域的類型，從而完成對鄰接區(qū)域的重新判定。

2.算法描述

將MSRM算法的分割結(jié)果P作為輸入，然后標(biāo)記分割不滿意區(qū)域R，計算區(qū)域R的鄰接區(qū)域Ri和初始標(biāo)記區(qū)域相似度S，由kNN算法判別區(qū)域Ri的類型，如果相同，進(jìn)行區(qū)域的合并并更新R，最后進(jìn)行R的標(biāo)記，最后對結(jié)果是否滿意進(jìn)行評判。

具體算法執(zhí)行可以描述為以下步驟：

(1)對鞋印花紋圖像的前景區(qū)域和背景區(qū)域進(jìn)行標(biāo)注，具體包括：獲取圖片的個數(shù)，遍歷單個圖片進(jìn)行區(qū)域的標(biāo)注，以及圖片的保存。

(2)提取顏色直方圖特征和方向直方圖特征，具體包括設(shè)置直方圖的參數(shù)信息，對直方圖進(jìn)行展示等。

(3)計算區(qū)域相似度，根據(jù)需要，建立距離的度量標(biāo)準(zhǔn)(本文采用馬氏距離)、將距離轉(zhuǎn)化為numpy數(shù)組(這里采用Python完成處理)。

(4)進(jìn)行判別，具體也就是分類的過程。

(5)在執(zhí)行上述過程中，如果兩個區(qū)域相同，需要進(jìn)行合并，然后繼續(xù)遍歷，得到區(qū)域的合并結(jié)果，最后提取鞋印花紋結(jié)果。

三、實(shí)驗(yàn)結(jié)果與分析

為了將整個處理過程流程化，形成一個整體化的處理框架，這里給出基于kNN的鞋印花紋圖像分割算法的執(zhí)行流程，見圖1。

MSRM算法作用于背景輪廓不明顯的圖像，其切割效果就會受到一定的影響，但是，MSRM是基于最大相似度的區(qū)域合并算法，是機(jī)器學(xué)習(xí)中的分類思想在圖像背景識別中的具體應(yīng)用，也可用于多目標(biāo)提取。因此，本文在此基礎(chǔ)上，對MSRM算法加以改進(jìn)，提出基于kNN的鞋印花紋分割算法。其改進(jìn)的效果如何，是否能在分割的準(zhǔn)確性上有更好地表現(xiàn)，本文進(jìn)行了測試對比，具體對比結(jié)果，見表1。

表1中的四種評價指標(biāo)，是以最終的平均作為分割結(jié)果的性能指標(biāo)。其中準(zhǔn)確率和召回率越接近于1，表示分割效果越好，當(dāng)二者出現(xiàn)不一致時，使用F-Score進(jìn)行綜合反映，而概率邊緣指數(shù)用以描述待分類和標(biāo)準(zhǔn)分類之間在屬性方面擁有一致性的像素數(shù)量，取值越大，表示分割效果越好。

從輸出可以看出，kNN算法下的鞋印花紋提取更加準(zhǔn)確，分割性能有所提高。

四、結(jié)束語

本文對當(dāng)前的圖像分割方法及技術(shù)進(jìn)行了綜述，基于MSRM算法的不足和優(yōu)勢，針對鞋印花紋的分割實(shí)際，提出了基于kNN的圖像分割算法，即以MSRM的初始處理作為輸入，然后運(yùn)用kNN算法進(jìn)行后續(xù)的處理，實(shí)現(xiàn)圖像初始區(qū)域的合并、修正、去燥等處理，從而提高了花紋與背景判定的準(zhǔn)確性，也進(jìn)一步提高了花紋提取的精度。