基于稀疏编码与反向索引的鞋印图像比对算法

李大湘，邱 鑫 ，刘 颖

（1. 西安邮电大学通信与信息工程学院，西安 710121；2. 电子信息现场勘验应用技术公安部重点实验室，西安 710121）

足迹作为犯罪现场中最常见的一种痕迹物证，在案件串并及法庭举证等工作中一直具有重要作用。但是，随着刑侦数字化与网络化技术的发展，鞋底库中的图像数量越来越多。当从犯罪现场采集到鞋印图像时，利用图像自动比对技术，在大规模鞋印库中快速而准确地查询到其他相似鞋印，为刑侦工作寻找破案线索，在当前“科技强警”工作中具有重要意义[1]。

针对鞋印图像快速查询应用需求，相关算法可分为三类：1）基于鞋印图像检索的方法，该类方法的基本思想是提取鞋印图像的全局或局部底层视觉特征，再结合机器学习或相似度量方法，以实现鞋印图像相似查找，例如文献[ 2]提出基于聚类的鞋印图像检索算法，该算法针对鞋印图像类别之间存在隔离带这一情况，设计一种K步稳定聚类算法以实现鞋印图像检索；文献[ 3]融合局部二值模式（LBP）纹理特征与局部敏感哈希(LSH)索引方法，提出一种大规模鞋印图像快速检索方法。2）基于鞋印图像分类的方法，该类方法的基本思想是对鞋印图像实现自动分类，以缩小排查范围而提高查找效率，如文献[ 4]提出一种基于卷积神经网络的鞋印分类算法，该算法在将CNN模型引入鞋印图像分类的基础上，针对网络中存在相似特征图的性质，设计一种去冗余连接的CNN改进模型，加快了网络收敛速度，也提高了分类精度；文献[ 5]提出一种基于语义的鞋印分类算法，该算法在鞋印图像底层视觉特征的基础上，还引入了语义信息，有效地提高了分类性能。3）基于鞋印图像匹配的方法，该类方法的基本思想是提取鞋印图像局部或关键点信息，给定查询样图直接在鞋印库进行相似比对，如文献[ 6]利用鞋印图像的尺度不变特征变换 (scale-invariant feature transform, SIFT)描述子，提出一种基于RANSAC 算法的图像匹配方法；除此之外，还有基于能量谱密度（power spectral density，PSD）特征[7]、Gabor纹理特征[8]的鞋印匹配算法，且在相应的测试集都具有一定的匹配精度。

在现勘鞋印图像比对实际应用中，鞋印图像存在的特点有：1）鞋印花纹结构种类很多，且同种花纹的鞋印样本很少；2）犯罪现场很难提取与拍摄到清晰而完整的鞋印图像；3）鞋印图像库中的图像总量很多。所以，基于机器学习的鞋印图像检索与分类方法无法预先定义完备的鞋印花纹类别而提前训练出性能优异的分类器，不具有通用性；而基于匹配的鞋印查询方法，没有考虑大数据集问题，即当库中的图像数量非常多时，若采用穷举比对的方法进行相似查找，效率非常低，不能满足实时性的应用需求。

针对上述问题及大规模鞋印图像快速比对应用需求，本文提出一种基于稀疏编码（sparse coding,SC）[9]与反向索引（reverted index, RI）[10]的鞋印图像快速比对算法，称之为SC-RI算法。该算法的主要思想是：首先，提取鞋印图像的SIFT局部特征，然后采用字典学习、稀疏编码与最大池化处理等方法，计算出鞋印图像的稀疏编码特征；最后，通过构建“词-图像矩阵”而设计反向索引结构。试验结果表明，真实采集的鞋印图像虽然整体上来说不完整，但只要存在局部清晰的花纹结构，就可以应用SC-RI算法简单而有效地实现比对查询。

1 鞋印图像局部特征提取

为了提高后续算法的稳定性与可靠性，鞋印图像在录入数据库时，在做局部特征提取之前，首先，按图1所示方法对鞋印图像进行直方图均衡化视觉增强、中值滤波与OSTU二值分割等预处理；然后，基于二值分割之后的图像，自动检测关键点并计算其SIFT描述子[6,10]，用于表示鞋印图像的局部结构特征。

图1 鞋印图像预处理方法与效果示意图Fig.1 Effect of preprocessing on shoeprint image

设IMG表示任一鞋印图像，对其采用SIFT方法检测到关键点数量为n个，则IMG的局部特征集记为：

表示第j个关键点的SIFT描述子。

2 CS-RI鞋印比对算法

设T={IMGi:i=1,2,...,N}表示鞋印图像库，其中N表示鞋印图像的总数量，对T中的每幅图像进行SIFT局部特征提取之后，设由所有SIFT描述子组成的数据集为：

从图2所示操作过程可见，虽然现勘中很难采集到完整而清晰的鞋印图像，但只要其存在局部清晰的花纹区域，本系统就可将其剪取下来，并进行中值滤波与二值分割等预处理，作为查询样图而实现鞋印比对查询。从图3所示的实现结果可见，排在第1、2与7的图像，都是“嫌犯鞋印库”中与之相对应的正确比对结果。本次比对耗时119.64 ms，电脑平台是：浪潮图像工作站，Win7操作系统（64位），8G RAM内存，Intel Xeon(R) 3.1G CPU处理器。

图2 鞋印图像比对操作流程（A：待比对的原始图像；B：剪切的目标图像；C：预处理之后的图像）Fig.2 Operational process of the shoeprint image comparison (A.original image for query; B. target image cut from the original; C.target image after preprocessing)

图3 鞋印图像比对查询结果Fig.3 Query results on comparing shoeprint images

在“以人查案”应用实例中：首先，打开嫌疑人鞋印图像，如图4A所示；然后，采用上述相同方法在图像中剪切局部清晰的花纹区域并进行预处理，如图4B所示；最后，点“比对识别”按钮（对应传统SIFT匹配与逐个穷举比对方法），得到图4C所示比对结果。

为了综合评估本文算法的比对速度与比对精度，选取“折波型、交织型、线条型、边块型与圆点型”等5种常见花纹结构，每种10个，共50个局部花纹结构作为比对样图，进行综合评估实验，其平均比对时间、Top10与Top20的正确率如表1所示。其中：平均比对时间是指50次比对的平均耗时，平均Top10或Top20正确率是指50次比对实验中，比对结果前10幅或前20幅图像中比对正确的图像总数除以150，这是因为：在鞋印库中大部分同类图像都存在3幅，每次比对过程中都希望那3幅图像均能排在前10或前20之中，即150（50×3）为真正正确图像的总数。

由表1中试验结果可见，本文利用鞋印图像的SIFT局部特征，再结合稀疏编码与反向索引技术而提出的CS-RI鞋印比对算法，其比对精度接近于传统SIFT匹配穷举比对方法，只要鞋印图像存在局部清晰的花纹结构，比对正确率均在90%以上，但其比对速度提高了140多倍。这说明CS-RI是非常有效的鞋印比对算法，其原因是：1）SIFT描述子是一种非常有效的图像局部特征提取方法，其不但能捕获丰富的图像底层视觉特征，而且还对图像旋转、尺度缩放、光照变化均具有不变性；2）通过字典学习与稀疏编码，能从鞋印图像中获取有意义的结构基元，最后得到的编码系数，能很好地描述鞋印图像中所包含的各种花纹信息，近些年，稀疏编码在图像语义分析问题已得到成功应用，且性能卓越。

图4 鞋印图像比对操作流程及比对结果（A：嫌犯鞋印原始图像；B：预处理后的目标区域；C：比对结果）Fig.4 Operational course of comparing shoeprint images and the result (A. original image of suspect; B. target image preprocessed;C. query result)

表1 比对精度与时间对比Table 1 Comparison of both the matching accuracy and used time

4 小结

针对刑侦中大规模鞋印图像快速查询应用需求，本文基于鞋印图像的SIFT局部特征，再结合稀疏编码与反向索引技术，提出了一种CS-RI鞋印图像快速比对算法，且利用VS2010+OpenCV编程环境，实现了所提算法而开发了一套鞋印比对测试系统，其主要工作是将SIFT特征、稀疏编码与反向索引技术用于鞋印比对问题，并进行了对比试验与分析。实验结果表明，CS-RI算法比对精度高且速度快，是一种非常有效的鞋印比对算法。在后续工作中，将在更大规模的残缺鞋印集中做进一步验证，由于鞋印比对在刑侦中具有重要应用价值，是一个值得进行深入研究的课题。