基于选择性卷积特征描述子融合的鞋印检索算法

史文韬， 唐云祁

(中国人民公安大学侦查学院， 北京 100038)

鞋印是刑事案件中出现率最高的痕迹物证，通过现场鞋印一方面可以分析人身特点，另一方面在鞋印数据库中检索相同花纹的鞋印，可以串并案或者得到有关鞋型的信息。近年来得益于大规模鞋印数据库的建设，鞋印检索的作用愈加重要，促使研究人员探索了各种类型的鞋印检索算法并开发了相对成熟的足迹系统投入公安实战。但是由于鞋印检索的问题难度大，现场鞋印大多质量低并且残缺，目前的鞋印检索算法并未完全满足公安机关的实战需求，基层公安机关普遍反映大多数通过鞋印串并案的工作仍然由人工比对完成，这一现状说明鞋印检索算法仍然是一个值得持续研究的方向。

鞋印检索问题的挑战来源于犯罪现场鞋印视觉质量低和残缺两个方面，其中低质量问题依赖优秀的鞋印提取算法和稳定的鞋印特征[1]。研究人员已经提出了很多基于不同特征的鞋印检索算法。Gueham等[2]以鞋印图片在傅里叶域的相位信息为特征，使用一种改进的纯相位相关函数(modified phase-only-correlation function，MPOC)作为相似性度量来检索鞋印。Nibouche等[3]使用多尺度的Harris特征检测子和尺度不变特征变换(scale-invariant feature transform, SIFT)特征描述符，匹配阶段使用随机抽样一致性算法(random sample consensus，RANSAC)获得稳定的关键点。Wang等[4]提出了基于小波-傅里叶变换的全局不变特征用于鞋印图片的特征提取，在MUES-SR10KS2S数据集上top1%和top2%的识别率分别达到81.8%和87.5%。Wang等[5]在上述工作的基础上提出基于流行排序的检索算法，在MUES-SR10KS2S数据集上top1%和top2%的识别率分别达到85.3%和93.5%。Cui等[6]使用预训练VGG-16模型提取了鞋印卷积特征和全连接特征，然后使用主成分分析(principal amponent analysis, PCA)降维，在1 000幅嫌疑鞋印和37 886幅样本鞋印的数据库中，top1和top10的识别率分别是64.4%和87.9%。Bailey等[7]使用预训练的Resnet50模型提取鞋印图片的特征，使用多通道归一化互相关(multi-channel normalized cross-correlation,MCNCC)比较特征距离，在FID-300数据集上top1%和top10%的识别率分别为79.67%和89%。Cui等[8]使用深度置信网络(deep belief networks, DBN)和空间金字塔匹配(spatial pyramid matching, SPM)检索鞋印，在536幅的嫌疑鞋印和34 768幅样本鞋印的数据集上top10和top100的识别率分别为65.67%和81.16%。Ma等[9]使用多部分加权卷积神经网络(multi-part weighted convolutional neural network，MP-CNN)提取鞋印特征，在FID-300数据集top1%和top10%的识别率分别为61.02%和89.83%。周思越[10]选取嫌疑鞋印图片中的标志性语义信息块和周期性语义信息块，训练局部语义滤波器组，计算局部语义滤波器模型与样本鞋印之间的相似度，在MUES-SR10KS2S数据集上top1%和top2%的识别率分别达到92.3%和95.2%。彭飞[11]提出了一种基于局部语义块和改进流行排序的鞋印检算法，在MUES-SR10KS2S数据集上top1%和top2%的识别率分别达到90.3%和93.7%。Wu等[12]提出了一种基于近邻图像信息和混合特征的鞋印检索算法，在MUES-SR10KS2S数据集上top1%和top2%的识别率分别达到90.9%和94.8%。

现针对残缺问题和目前残缺鞋印检索方法的不足，引入文献[1]中的选择性卷积特征描述子融合方法(selective convolutional descriptor aggregation，SCDA)，提出了基于选择性卷积特征描述子融合的鞋印检索算法，评价算法时使用的指标是累积匹配曲线(cumulative match characteristic curve，CMC)。

1 残缺鞋印的检索策略

残缺鞋印是鞋印检索问题中的难点，残缺鞋印与完整鞋印之间的差异对特征距离的计算会产生较大的影响。除了使用对残缺具有不变性的鞋印特征，研究人员也会使用一定的检索策略来避免这一影响，这样的策略可以大致分为两类。

1.1 分区策略

先对鞋印进行标准化，然后将鞋印分成若干个区域分别提取特征，之后可将每个区域的特征聚合成一个整体特征或者由每个区域之间的特征相似度计算得到整体相似度，这样由局部到全局的提取方法可以减小部分区域缺损对于鞋印特征整体的影响。Tang等[13]将鞋印分为足掌区和足跟区，足掌区和足跟区又分别分成9个子区，检索时对两张鞋印图片的每个子区分别提取特征并计算对应子区之间的相似度，由每个子区之间的相似度计算整体的相似度。刘家浩[14]采用了鞋印图片分区及分区有效性评价算法，将鞋印分为足掌区和足跟区，足掌区和足跟区又分别分成6个子区，在子区为有效分区时，才提取该分区的特征。Cui等[6]将鞋印按照3∶2的比例分成足掌与足跟两个语义区域分别提取特征，最后的鞋印相似度得分是两个区域相似度的加权和。Ma等[9]将鞋印图片分成上下两块分别通过卷积神经网络提取128维的特征向量，然后将两部分的特征融合为整体特征。

1.2 特征选择策略

通过一定的特征选择方法得到两幅鞋印图片相同遗留区域对应的特征，再计算特征之间的距离。Li等[15]计算鞋印图片的积分直方图，完整鞋印直接计算特征相似度，残缺鞋印则通过积分直方图在样本鞋印上寻找与残缺鞋印相近的区域，然后在该区域计算特征相似度。Kong等[16]对每幅鞋图片的整体、足掌、足跟三部分各提取320维的特征向量，形成960维的鞋印特征。在检索时所有的鞋印图像分为3种类型：完整的、只有足掌的、只有足跟的。计算相似度时如果两幅图片都是完整的，则使用鞋印特征的前320维；如果其中一幅图片属于足掌或者足跟类型，则使用足掌或者足跟对应的320维特征。

一种主流的方法是以鞋印分区策略来解决这一问题。将一幅鞋印图片，以3∶2的长度比分为Top块与Bottom块，然后两块区域分别提取特征。根据专家经验，由于足掌区包含了更多的花纹信息，所以在特征融合时Top块的特征权重大于Bottom块的权重。这一方法存在的问题是如果某一区块的鞋印花纹大面积缺失，两张图片相同区域之间的相似度会突然下降，影响结果。如图1所示，分区求相似度时，两张图片Top块相似度很高，但是Bottom块相似度为0。所以文献[6]中给两区块简单赋以固定权重再融合的方法实际效果不好。文献[4]中通过计算两区块的有效信息量和置信度，再通过设置阈值、预设相似度等一系列方法解决这一问题，效果理想但是方法复杂。分块提取意味着多次输入和多次输出，特别是在使用的卷积特征本身维度已经很高的情况下，分块提取会导致特征维度和计算量的爆炸式增长。基于以上原因，在使用卷积特征的条件下，引入SCDA方法解决残缺鞋印检索问题，取得了明显的提升效果。

图1 一种分块方法示例Fig.1 An example of a partitioning method

2 基于选择性卷积特征描述子融合的鞋印检索算法

2.1 SCDA

SCDA是由Wei等[1]于2017年提出的用于细粒度图像检索的方法。细粒度图像检索是由Xie等[17]于2015年提出的，与通用图像检索不同，细粒度图像检索要求查询到某一具体的子类，如待检索图片是边境牧羊犬的图片，则要求在不同品种的犬类图片中找到其中的边境牧羊犬图片。SCDA方法根据输入图片在卷积层的主要激活区域无监督定位图片中主要目标，筛选卷积特征，该方法在细粒度图像检索上取得了超越当时所有算法的成绩，在CUB200-2011、Standford Dogs、Oxford Flowers、Oxford Pets数据集上，Top1的识别率分别达到60.65%、74.95%、77.56%、88.19%。何甲[18]将SCDA方法应用于尘肺病医学影像分析；尹红等[19]将SCDA方法应用于花卉图像分类，实验结果均取得了明显提高。与SCDA类似的，Wei等[20]提出Mask-CNN用于细粒度图像识别，使用一个全卷积神经网络将图片分割为头部、躯干、背景三部分，得到主要目标的掩码图(Mask)。但是该方法需要人工标记关键点作为ground-truth训练分割图片的全卷积神经网络，与之相比SCDA方法的无监督定位更加便捷，所以本文没有使用Mask-CNN。

SCDA的原理为：将一张图片输入卷积神经网络，在某一卷积层输出维度为h×w×c的张量，其中h、w分别为特征图的高和宽，c为通道数，某一通道的特征图用Pn表示，将卷积层输出的张量记为P={Pn}(n=1,2,…,c)。该张量还可以看成由h×w个元胞组成，每个元胞是一个c维的卷积描述子，某一个卷积描述子用F(i,j)表示，将这些卷积描述子集合记为F={F(i,j)}(i=1,2,…,h;j=1,2,…,w), 其中(i,j)表示某个卷积描述子的坐标。输入图片经过卷积层后在每幅特征图上的激活区域均不相同，使得卷积神经网络能提取图片不同方面的特征。在这些特征图中有的激活区域对应图片中的待检索目标，有的对应图片中的背景，而SCDA方法的思路是尽管不同特征图的激活区域不同，但是如果大多数特征图均在某一区域激活，那么该区域应该对应图片中的主要目标而非背景。所以可以根据所有特征图反映出的主要激活区域筛选卷积特征，只保留与主要目标对应的卷积描述子，排除与背景区域对应的卷积描述子，卷积特征筛选流程如图2所示，把卷积层输出的张量沿着通道维度相加，能得到尺寸为h×w的融合图(aggregation map)，用A表示。融合图上每个位置的坐标为(i,j)，A(i,j)表示每个位置的值；计算融合图中所有位置的均值α；如果A(i,j)>α，则在该位置赋值1，否则赋值0，形成掩码图(mask map)，用M表示，其表达式为

图2 卷积特征筛选流程Fig.2 Pipeline of selecting convolutional feature

(1)

将掩码图M上采样恢复到原图大小并与输入鞋印图片叠加，发现该方法能够定位残缺鞋印的区域，如图2所示，在筛选卷积特征时使用掩码图M对卷积描述子集合F进行筛选，保留F与M中值为1位置对应的卷积描述子，得到筛选后的卷积描述子集合S为

S={F(i,j)|M(i,j)=1}

(2)

图3为使用SCDA方法对3种典型残缺模式(足跟残缺、足弓残缺、足掌残缺)的鞋印定位的结果。

2.2 算法框架

本文算法的核心思想是利用SCDA方法定位残缺鞋印的位置，筛选残缺鞋印花纹区域对应的卷积描述子，得到筛选后的卷积特征，进而提高残缺鞋印的检索精度。本文算法流程如图4所示，将嫌疑鞋印和样本鞋印图片输入鞋印数据集微调的VGG-16模型提取卷积特征，如果嫌疑鞋印是完整鞋印，则直接使用卷积神经网络卷积层输出的特征，如果嫌疑鞋印是残缺鞋印，则根据SCDA方法筛选其卷积特征，然后根据嫌疑鞋印的掩码图筛选样本鞋印的卷积特征和样本鞋印水平翻转图的卷积特征。每张嫌疑鞋印同时与样本鞋印、样本鞋印的水平翻转图比较特征距离，取最小值作为最终的特征距离。特征相似性度量选择Cosine距离。

图4 本文算法流程Fig.4 Pipeline of the proposed algorithm

2.3 用于特征提取的卷积神经网络

VGG-16是一种经典的卷积神经网络，其深层的网络结构和多组堆叠的小尺寸卷积核使得该网络具备很强的特征提取能力，特别是ILSVRC数据集预训练的VGG-16被广泛地应用于图像检索领域。为了进一步提高预训练模型在鞋印检索问题上的精度，文献[21]建立了一个432类共2 827幅鞋印图片组成的鞋印数据集，并扩充至432类共228 987幅图片，使用扩充后的数据微调预训练的VGG-16模型。微调时修改最后一层全连接层的输出维度并重新初始化该层参数，其余层保留原有参数。与直接使用预训练模型相比，微调后的VGG-16模型显著提高了检索精度，将该模型作为提取鞋印图片特征的卷积神经网络。

2.4 鞋印特征提取

首先将鞋印图片输入鞋印数据微调的VGG-16模型正向传播，并在卷积层conv5-1后添加一层大小2×2、步长为2的Max-pooling层输出7×7×512维的张量，然后提取鞋印图片的3种特征。

(1)conv-25088特征：将7×7×512的张量直接维展开后得到的25 088维的向量作为鞋印图片的特征，以下用“conv-25088”表示。

(2)Shoeprint-SCDA特征：将7×7×512维的张量根据SCDA方法计算掩码图M和筛选后的卷积特征描述子集合S，然后将S展开成1×m维的特征向量，得到鞋印图片的特征，以下用“Shoeprint-SCDA”表示。其中m为M中1值的个数与通道数c的乘积。

2.5 完整鞋印和残缺鞋印的分类检索

对于完整鞋印，使用SCDA方法反而降低了检索精度，所以对于完整鞋印仍使用conv-25088特征，只对残缺鞋印使用Shoeprint-SCDA特征。为了简化实验流程，采用一个简单的方法区分残缺鞋印和完整鞋印：计算鞋印长度与鞋印图片高度的比值，若该比值大于阈值β，则为完整鞋印，否则为残缺鞋印。实验中，阈值β设为0.7。在公安机关实际工作中，每一幅图片是否残缺可以由操作人员自行判断标记，甚至可以将完整鞋印的低辨识度区域擦除作为残缺鞋印检索，以提高结果准确性。

3 实验及结果分析

3.1 实验环境及配置

实验使用的操作系统是Windows10，显卡型号GTX1060，实验环境是MATLAB 2013a及深度学习框架caffe的matcaffe接口。

3.2 测试数据集

3.2.1 CSS-200数据集

该数据集包含200张嫌疑鞋印和5 000张样本鞋印，全部采用公安机关足迹系统中的犯罪现场鞋印，嫌疑鞋印既有完整鞋印也有残缺鞋印，所有图片均为犯罪现场鞋印经过标准化后的二值图。

3.2.2 Part-FID数据集

该数据集是筛选公开鞋印数据集FID-300中的残缺鞋印得到的数据集，称为Part-FID。FID-300包括300幅嫌疑鞋印1 175张样本鞋印，嫌疑鞋印均为犯罪现场鞋印，样本鞋印均为油墨捺印后扫描获得。筛选出300幅嫌疑鞋印中的全部残缺鞋印，所有图片均使用公安机关的足迹系统进行二值化处理，删除其中质量过低、背景干扰严重并且使用专业足迹系统仍不能有效处理的鞋印图片，得到85类共139张残缺嫌疑鞋印，样本鞋印的数量仍为1 175张。

3.3 结果与分析

3.3.1 CSS-200数据集上的实验

该实验使用本文基于选择性卷积特征描述子融合的鞋印检索算法在CSS-200上实验，同时与所有嫌疑鞋印，不论完整或者残缺全部使用conv-25088特征检索的结果进行比较。

如图5所示，本文算法与全部使用conv-25088特征相比，检索精度有了明显的提高。使用conv-25088特征，Top1%的识别率为52%，Top10%的识别率为75.5%；使用本文算法，Top1%的识别率为62.5%，Top10%的识别率为85.5%。将使用本文算法的检索结果与目前鞋印检索先进方法中的结果进行比较，如表1所示，本文算法Top1%和Top2%的识别率分别为92.5%和94.5%，达到了目前鞋印检索的先进水平。图6是部分鞋印使用conv-25088特征检索的前10位结果，图7是同样的鞋印使用本文算法检索的前10位结果，对比之后可以发现残缺鞋印的检索结果有了明显改善。

表1 本文算法与先进算法的结果比较

图5 CSS-200数据集上的实验结果Fig.5 The result of experiment on CSS-200 dataset

蓝线左侧为嫌疑鞋印；右侧为对应的前10位检索结果；绿色方框标识出正确的检索结果； 无标识则说明前10位均无正确结果图6 使用conv-25088特征Top10检索结果Fig.6 Retrieval results at Top10 using conv-25088

3.3.2 Part-FID数据集上的实验

该实验目的是测试算法在残缺鞋印检索上的表现，使用本文提出的基于选择性卷积特征描述子融合的鞋印检索算法，同时与所有嫌疑鞋印不论完整或者残缺全部使用conv-25088特征检索的结果进行比较。在表2中列出相关鞋印检索算法在完整FID-300数据集上的结果。

如表2所示，在Part-FID上使用conv-25088特征Top1%的识别率为39.57%，Top10%的识别率分别为74.82%；本文算法Top1%的识别率为42.5%，Top10%的识别率为82.01%。相关方法在全部FID-300数据集上的Top10%的识别率最高为89%，考虑到全部使用残缺鞋印进行测试，这表明本文算法在解决残缺鞋印检索问题上的有效性。综合CSS-200和Part-FID两个数据集的实验结果，使用本文算法能够明显提高残缺鞋印的检索精度。

蓝线左侧为嫌疑鞋印；右侧为对应的前10位检索结果；绿色方框标识出正确的检索结果； 无标识则说明前10位均无正确结果图7 本文算法top10检索结果Fig.7 Retrieval results at top10 using the proposed algorithm

表2 FID-300和Part-FID数据集检索结果

4 结论

为解决残缺鞋印的检索问题，引入SCDA方法筛选残缺鞋印的卷积特征，提出一种基于选择性卷积特征描述子融合的鞋印检索算法方法的鞋印检索算法，得到以下结论。

(1)实验结果表明，使用SCDA方法能够明显改善残缺鞋印的检索结果。

(2)目前本文算法适用于大部分残缺鞋印，但是对于遗留面积极小如只有足趾区的残缺鞋印还有待提高。虽然文献资料普遍认为卷积特征是一种局部特征，但实验结果表明，鞋印图片的卷积特征仍然是一种全局特征，这一特点使得目前使用的特征并不适用于面积极小、只能反映出局部花纹的残缺鞋印。

在今后工作中，将主要集中于两个方面的问题：一是遗留面积极小的残缺鞋印的检索问题；二是进一步训练用于提取特征的卷积神经网络，提高网络对于鞋印图片的识别能力。