基于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算法进行后续的处理，实现图像初始区域的合并、修正、去燥等处理，从而提高了花纹与背景判定的准确性，也进一步提高了花纹提取的精度。