基于SIFT、K-means和BOF的鞋底痕迹检索

焦 扬 杨传颖 石 宝

(内蒙古工业大学信息工程学院 内蒙古 呼和浩特 010080)

0 引 言

鞋印图像是犯罪现场侦查中遗留率较高的一种证物，具有稳定性、易提取性等特点，在刑事侦查工作中有着十分重要的作用，是案件侦破以及法院取证中不可或缺的一部分[1]。刑事侦查人员将犯罪现场的鞋底痕迹花纹图像与以往案件采集到的图像信息比对，进行串并案件的处理，提高犯罪侦查效率。如今各地公安机关对鞋底痕迹花纹图像信息管理各不相同，存在许多弊端，大多采用人工管理的模式，方式单一、任务量大、精度低，很难实现跨省等较大范围的串并案件侦破。鞋底痕迹花纹的管理和应用与指纹相比存在许多困难，利用基于内容的图像处理技术，可以更好地实现鞋底痕迹花纹的检索与应用，减少人力、物力的消耗，降低了人工识别引起的二义性，增强刑侦人员破案效率[2]。

基于内容的图像检索(Content-BasedImageRetrieval,CBIR)利用在图像中提取的低层视觉特征和语义内容特征描述图像内容[3],对提取的内容进行相似度排序，实现检索过程。主要提取颜色、纹理、形状和平面空间位置特征来比较图像相似度。鞋底痕迹花纹图像因图像质量较低需要对图像进行预处理，图像检索主要以纹理特征、形状特征和空间位置特征为主。文献[1]采用Gabor变换域的积分直方图作为鞋底痕迹花纹图像纹理特征进行检索，查准率为46.77%，较全局最优匹配方法提高了4.82%。文献[4]通过对Laws掩模和纹理图像卷积计算能量对鞋底痕迹花纹分类，分为线条型图案、点型图案、其他型图案，但是对于其他类型图案中交织型、边块型、圆型花纹还需要进一步识别计算。文献[5]提出了一种使用SIFT提取关键点构成特征向量，计算每个鞋印图像与数据库中图像的交叉关联，进行相似度排序。文献[6]基于小波变换的边缘检测、拐点检测以及霍夫变换的方法，通过提取一些特征向量，长、宽、长宽比、面积等，计算出该图像不同的纹理特征，前10幅图片的查准率为91.1%，但是此方法不适合残缺图像检索。

1 算法设计

本文提出的鞋底痕迹花纹图像检索方法的实现流程如图1所示。由于案发现场复杂多变，对提取到的鞋底痕迹花纹图像首先要进行图像预处理，将鞋印图像与背景分离，对图像的尺寸、颜色归一化；然后采用SIFT算法特征提取；接着使用K-means算法[7]聚类生成类中心点，构建视觉特征包(BagofFeatures,BOF)，这是本文的研究重点；最后根据相似度匹配实现图像检索。

图1 鞋底痕迹花纹图像检索流程

1.1 图像预处理

图像的质量与图像检索效率成正比。因鞋底痕迹花纹图像受到犯罪现场环境、人为破坏等其他因素影响，图像质量差。为了提高检索效率，需要对提取到的图像进行预处理，减少在检索过程中的干扰。预处理过程为：

(1) 直方图均衡化[8]使变换后图像灰度的概率密度呈现均匀分布，增强图像对比度，减弱背景对鞋印图像的影响，具体步骤如算法1所示。

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

输入：G个灰度级大小为M×N的图像

输出：灰度级gq的图像

Step 1 创建一个长为G的数组H，初始化为0。

Step 2 扫描每个像素添加到数组H中，当像素p具有亮度gp时，H⎣gp」+=1，形成图像直方图。

Step 3 形成累计的直方图Hc：Hc[0]=H[0]，Hc[p]=Hc[p-1]+H[p]，其中p=1,2,…,G-1。

Step 5 重新扫描图像，输出图像设置为gq=T⎣gp」。

(2) 非局部均值滤波算法(Non-local Means,NLM) 因环境、人为等多种因素的影响，图像中干扰信息过多，需要滤除部分噪声，在直方图均衡化的基础上进一步增强图像。对于一个噪声图像v(x)={v(x)|x∈I}，像素点x的邻域称为Nx，NLM去噪结果如下：

(1)

式中:I是一个较大范围的搜索框；权值w(x,y)表示像素点x和y间的相似度，值由v(Nx)、v(Ny)间的距离决定。

(2)

(3) 最大类间方差算法(Otsu)[9]对图像进行二值化处理，将背景与图像分离，增加图像信息量：

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

(3)

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

鞋底痕迹花纹图像经预处理后效果如图2所示。(a)为犯罪现场提取的鞋底痕迹花纹图像，(b)为进行预处理后的图像。

(a) (b)图2 犯罪现场鞋印图像与预处理后图像

1.2 SIFT特征提取

通过提取图像特征点可以区分不同的图像特征，针对鞋底痕迹花纹图像的特点，综合分析图像检索特征提取，确定使用SIFT特征提取算法。SIFT算法是1999年由Lowe[10]教授提出，该算法在不同的尺度空间上查找特征点，并且计算出方向，对图像识别具有鲁棒性。算法主要流程描述如下。

一个图像的尺度空间L(x,y,σ)由高斯函数G(x,y,σ)与原始图像I(x,y)卷积运算得到：

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

(4)

找到高斯差分算子(Difference of Gaussian,DOG)的极值点，将每个像素点与其相邻的像素点进行比较，共26个像素点，以确保在尺度空间和二维图像空间中都检测到极值点。如图3所示，如果中间方块是最大值或最小值，该点被选为候选特征点。

图3 DOG图像

以上检测为离散空间的极值点，与连续空间极值点存在偏差。因此，有必要计算该点与极值点之间的距离。使用DOG函数的Taylor展开式：

(5)

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

(6)

对应的极值点方程为：

(7)

为了使描述子对图像具备旋转不变性，使用梯度直方图指定每个关键点的方向，点(x,y)处的梯度幅值和方向的计算公式为：

(8)

(9)

使用直方图统计梯度幅值和梯度方向的计算结果，且直方图将方向划分为36个部分，每个部分10度，直方图中峰值方向即为关键点的主方向，如图4所示。

图4 关键点主方向直方图

2 图像检索

采用SIFT提取图像特征点，每个特征点可以表示为一个特征向量，通过K-means聚类算法对鞋底痕迹花纹图像库的特征向量进行聚类生成类心，通过特征点与类心的比对生成频数表加权重后生成BOF(Bag of Features)模型[11]，最后，通过相似度计算与排序生成检索结果。

2.1 K-means聚类算法

首先，我们需要初始化k个聚类中心，假设鞋底痕迹花纹图像样本集D={x1,x2,…,xn}，在数据集D中随机选取k个样本作为初始的k个聚类中心μj，j=(1,2,…,k)。

(10)

E的值越小，表示聚类样本相似度越高，通过K-means聚类算法获得k个聚类中心，代表不同类别的特征点。伪码如算法2所示。

算法2 K-means聚类算法。

输入：包含n个对象的图像数据集D={x1,x2,…,xn}、k个聚类中心

输出：簇C={C1,C2,…,Ck}

令Cj=∅(1≤j≤k)

fori=(1,2,…,n) do

根据距离最近的均值向量确定xi的簇

将样本xi加入相应的簇中

end

forj=(1,2,…,k) do

else

保持均值向量不变

end

end

2.2 BOF算法

BOF算法与文本检索领域的BOW(Bag of works)算法相似，将每幅图片描述为无序的局部特征集合，使用K-means算法聚类后获得k个聚类中心，每个聚类中心对应不同的特征点形成码字，所有聚类中心形成一个视觉词典，被称为码书。通过计算局部特征出现的次数以生成直方图向量,过程如图5所示。

图5 构建BOF向量

3 实验及其结果分析

本文实验采用硬件平台为Intel Core i7-4790 CPU 3.60 GHz，8.00 GB RAM。基于MATLAB软件作为技术平台，实现对鞋底痕迹花纹的检索。实验数据集由西邮图像与信息处理研究所提供。为了测试本文算法的鲁棒性，从中选择300幅包含不同类型的鞋底痕迹花纹的图像，例如点型、波折型、圆型、波浪型、方块型、交织型等多种鞋底花纹图像，其中图像像素宽度由鞋印宽度决定，高度均为586像素，分辨率为96 dpi。图6为所选数据集中的部分图像。

图6 所选数据集中的部分图像

性能评价指标选用图像检索领域常用的查准率(P)和查全率(R)：

(11)

(12)

另外，还采用了F-Measure函数作为评价标准：

(13)

式中：β是参数。

为了检验本文算法对旋转、尺度缩放、残缺等图像是否具有稳定性，将图像在0～360°每间隔45°旋转一次，共旋转8次。截取部分鞋底花纹图像以及处理图片达到部分残缺的效果，再对每幅图像进行相同比例缩放0.8、1、1.2倍，经处理后，测试图像库共包含9 900幅图像。图7为随机选取的某一鞋底痕迹花纹图像。

图7 随机选取的鞋印图像

图8给出了返回的检索结果前12名，其中加边框的图像为查询到属于同一鞋印的图像，根据图像不同返回结果数量，计算不同的查准率与查全率，如表1所示。

图8 返回检索结果前12名

表1 不同返回结果的查准率与查全率

可以看出，查准率随着返回数量的增加而呈下降趋势，而查全率则为上升趋势。随机选取5幅鞋印图片进行检索，计算返回结果数量为30幅相似图片的查准率与查全率以及平均值，其数据如表2所示。

表2 随机图像的查准率与查全率及均值

可以看出，随机选取图片检索具有一定的稳定性，在返回结果数量为前30幅图片时查询结果浮动很小，根据表中平均值计算出F1-Measure的值为0.77，说明实验方法比较有效。

本文实验对图像进行SIFT特征提取后使用K-means算法聚类，生成k个聚类中心点，k值的选取对图像检索的结果有较大的影响。图9展示了k取值不同时，查准率和查全率结果对比。可以看出，当k=500时进行图像检索，查准率与查全率最优。

图9 不同k值时的检索结果

综上实验结果分析表明，本文采用SIFT特征描述对图片的旋转、缩放、光照等变化具有不变性，且对残缺的鞋底痕迹花纹有较强的鲁棒性。

4 结 语

本文提出了基于SIFT、K-means和BOF的算法用于鞋底痕迹花纹图像检索。实验结果表明：该方法检索准确率较高且对图像的旋转、缩放等具有良好的不变性。鞋印检索在刑侦方面是一个值得研究的课题，在后续的研究中可以通过改进K-means算法聚类中心的数目达到最优值，进一步提高鞋印图像的查准率。