基于kNN的鞋印花紋的圖像分割算法應用檢驗

馬華東 杜建軍

上海市公安局浦東分局刑偵支隊刑事科學技術研究所，上海 200125

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

一、鞋印在刑偵中的應用

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

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

二、圖像分割及其kNN算法

(一)圖像分割

圖像分割算法是從圖像處理到圖像分析的關鍵環節，與傳統的圖像分割算法相比，當前的圖像分割更加著眼于交互式分割，其根據圖像的某些特征，將圖像組織成有所區別的像素集合，在交互過程中，執行大量的迭代運算，從而生成最優解，實現特點像素點的提取。

在交互式圖像分割的研究領域，也有很多中方法，比如有從圖論出發的，有從目標輪廓標記出發的，等等。從目前來看，國內外的很多交互式圖像分割算法，都是基于Graph Cut算法的，但是，從計算量來看，計算復雜度較高。因此，后續出現了很多算法對該算法進行了優化，比如Grab Cut等。以上算法在某些方面或應用領域針對特定情況能夠對圖像進行有效分割，但是在復雜的前景背景顏色分布下，其適用性仍然有限，魯棒性較弱，達不到一個好的分割效果。為此，本文提出基于kNN的圖像分割算法。

(二)kNN算法

1.算法原理

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

2.算法描述

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

具體算法執行可以描述為以下步驟：

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

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

(3)計算區域相似度，根據需要，建立距離的度量標準(本文采用馬氏距離)、將距離轉化為numpy數組(這里采用Python完成處理)。

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

(5)在執行上述過程中，如果兩個區域相同，需要進行合并，然后繼續遍歷，得到區域的合并結果，最后提取鞋印花紋結果。

三、實驗結果與分析

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

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

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

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

四、結束語

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