鞋印图像检索研究现状与发展趋势

刘 伟，姜乐怡，朱婷鸽，李 源，李大湘，刘 颖

(1.西安邮电大学 计算机学院, 陕西 西安 710121;2.痕迹检验鉴定技术公安部重点实验室,辽宁 沈阳 110854;3.西安邮电大学 电子信息现场勘验应用技术公安部重点实验室, 陕西 西安 710121；4.西安邮电大学 通信与信息工程学院, 陕西 西安 710121)

鞋印是案发现场中常见的一种物证痕迹，也是案件侦破中的重要线索[1-3]。统计数据表明，超过30%的盗窃案件现场都会发现有价值的鞋印痕迹[2]。刑事侦查中查询比对现场鞋印图像是串并案分析以及为诉讼提供物证的重要技术支撑[4-6]。随着信息技术快速发展和广泛应用，刑侦部门亟需面向大规模鞋印图像精确和高效的自动检索系统。

鞋印图像的复杂性主要表现在3个方面：一是案发现场鞋印图像可能呈现在各种各样的物理表面上；二是案发现场鞋印图像往往是不完整的，且包含大量噪声数据；三是鞋型生产厂家及型号众多，鞋印花纹类别数目较多、差异大。因此，鞋印图像检索是一个极具专业性的重要问题。

图像检索研究历经了基于文本的图像检索(Text-Based Image Retrieval，TBIR)和基于内容的图像检索(Content-Based Image Retrieval，CBIR)两个阶段。TBIR采用文本信息编码图像像素内容并进行文本匹配[7-8]。这种方法需要手工编码，无法实现图像自动分析与检索。CBIR基于图像像素内容，采用特征提取和机器学习技术，建立图像底层像素内容和图像高层语义之间的联系，从而实现图像的自动分析与检索[7-9]。图像检索理论和方法在国内外已有较多研究进展，而鞋印图像属于刑侦现勘图像，数据来源相对较特殊，研究相对较少[9]。本文拟从TBIR、底层视觉特征提取、高层语义学习、鞋印图像数据库、检索结果评价以及公安行业应用场景等方面对鞋印图像检索的研究现状进行综述，结合公安刑侦领域的实际需求，探讨鞋印图像检索技术的未来研究趋势。

1 基于文本的鞋印图像检索

早期对鞋印图像检索的研究，是利用TBIR方法。这种方法先采用文本编码对鞋印图像中的鞋掌区和鞋弓区等各个区域的花纹特征进行描述，然后将图像检索转换为文本检索，使用成熟的关系数据库技术对文本进行查询以匹配鞋印图像。显然，这种方式需要手工编码，不能实现自动检索，编码主观性对检索结果也有影响。此外，案发现场采集的鞋印图像往往是不完整的，且包含大量噪声数据，这会导致编码失效。国外对TBIR方法研究比较早，如Sawyer等[10]使用文本编码检索鞋印图像；文献[2]研究如何使用文本编码检索盗窃案嫌疑人的鞋印图像；文献[11]用文本编码可以检出案件现场鞋印的品牌和型号，并设计了相应的软件原型系统。国内也有类似研究，如文献[12-13]讨论了计算机技术在鞋印数据库管理方面的可行性，提出采用文本编码解决鞋印图像检索问题。

2 基于内容的鞋印图像检索

CBIR是目前鞋印图像检索的主流方法之一，其通过某种算法提取数据库图像的纹理和形状等低层特征，形成一个特征库，然后计算查询图像的特征并采用特征度量或机器学习方法与特征库进行匹配以寻找相似图像[7-9]。鞋印图像检索的CBIR方法框架示意图如图1所示。

图1 鞋印图像检索的CBIR方法框架

CBIR中的关键技术包括底层视觉特征提取和高层语义学习，而前者又分为全局特征和局部特征。

2.1 全局特征

利用全局特征算法处理整幅图像，可以得到表示图像像素内容的特征。Zhang等[14]使用Canny算子检测鞋印图像边缘信息，并构建了72柄的边缘方位直方图特征用于检索。Bouridane等[15]提出了一种基于分形迭代的鞋印图像特征提取与匹配方法，其对于图像旋转或平移具有一定的鲁棒性。AlGarni等[16]使用Hu不变矩形状特征用于鞋印图像检索。Patil等[17]通过Gabor全局特征和Radon变换，提出了一种旋转和亮度不变的鞋印图像匹配方法。Tang等[18]利用属性关系图(Attributed Relational Graph，ARG)描述鞋印图像中直线和圆等基本几何形状之间的相互位置关系，提出基于泥土搬运工算法(Earth Mover’s Distance，EMD)的鞋印图像距离(Footwear Print Distance，FPD)算法进行图像匹配。Kortylewski等[19]和Speir等[20]均采用了傅里叶变换特征的方法用于鞋印图像检索。Wang等[21]研究了具有全局不变性的小波-傅里叶变换特征在鞋印图像检索中的应用。Cui等[22]提出神经编码(Neural Code，NC)特征提取算法，分别计算脚掌和脚跟部分的NC特征并用于检索。柯少卿[23]提出一种针对鞋印图像的分块分类算法，采用灰度共生矩阵，以及在小波分解基础上构造的相邻尺度共生矩阵的Haralick统计量作为纹理特征，使用聚类分析完成鞋印图像分类。牛瑞娟[24]采用基于二维属性直方图的最大类间方差法对足迹图像进行分割并计算分割后图像面积、长宽比和紧实度等特征用于分类。刘家浩[25]提出基于Log-Gabor滤波器簇的纹理特征以及基于傅氏变换自配准性的投影傅氏幅度谱纹理特征用于鞋印图像检索。闵晓丰[26]利用图像频谱直方图寻找鞋印图像的特征线和特征圆以实现鞋底花纹分类。

上述研究表明，基于频域分析的全局特征，如小波、Gabor和傅里叶变换特征等更能表达鞋印图像内容的特征。但是，对取自案发现场的鞋印图像而言，其不完整且包含噪声，限制了全局特征的作用。

2.2 局部特征

为了处理案发现场鞋印图像不完整且包含噪声的问题，将尺度不变特征变换算子[27](Scale-Invariant Feature Transform，SIFT)等多种局部特征用于鞋印图像检索已取得了较好结果。局部特征算法先对图像进行分析，得到图像中包含丰富纹理或形状信息位置的一系列“兴趣点”，如目标轮廓，然后提取这些兴趣点周围的局部信息并将其整合形成特征。局部特征描述了图像中的不变属性，可以有效处理鞋印图像不完整、旋转和含噪声等问题。图2(a)和图2(b)分别为完整鞋印和案发现场不完整鞋印SIFT特征提取示意图。从图2可以看出，SIFT特征集中在边缘及纹理信息丰富的区域，有效地描述了鞋印图像内容。

图2 鞋印图像SIFT特征提取

针对案发现场采集的鞋印图像残缺不全及含有噪声的特点，Wei等[28]采用SIFT算子用于鞋印图像识别与检索。Luostarinen等[29]使用3个鞋印图像数据库，评估了几种鞋印图像识别算法的性能，得出局部特征性能较好。Su等[30]提出的MHL(Modified Harris-Laplace)和增强SIFT两种描述图像局部特征的算子，检索性能优于功率谱及边缘方向直方图等全局特征。Pavlou等人[31]采用最大极值稳定区域(Maximally Stable Extremal Regions，MSER)方法检测特征点，计算其SIFT特征，同样使用了局部特征用于鞋印图像检索。针对旋转的部分鞋印图像检索问题，Nibouche等人[32]提出利用SIFT特征描述图像内容，通过随机抽样一致(Random Sample Consensus，RANSAC)算法进行匹配，该方法在部分鞋印图像检索中取得了较好的结果。Richetelli等人[33]对比了傅里叶-梅林、相位关联以及SIFT特征加RANSAC算法匹配等方法用于鞋印图像分类的性能。Gwo等[34]提出关键点配准方法用于鞋印图像匹配。该方法首先将鞋印图像二值化，然后检测其中的轮廓点，选择稳定的轮廓点并使用曲线拟合方法生成鞋印左右两侧的边界线，关键点定义为左右两侧边界线上的凹点。最后，将鞋印图像分区为圆形区域并计算这些区域的Zernike矩特征，将其用于图像匹配。上述研究表明，局部特征在鞋印图像检索中的鲁棒性优于全局特征。

2.3 高层语义学习

由图1可知，得到鞋印图像特征后，采用度量函数或机器学习方法可寻找相似图像。早期的CBIR研究中，多采用距离函数如欧式距离计算查询图像特征与数据库图像特征之间的距离以得到匹配图像[16，28]。然而，“语义沟”[7-8]的存在，导致这种匹配方式的精度并不高。

为了改善此问题，机器学习方法被用于鞋印图像语义学习以提高检索精度。Geradts等[35]较早将机器学习方法用于鞋印图像分类与检索。通过分割鞋印图像的轮廓，计算其傅里叶变换特征，并使用3层神经网络对鞋的型号进行自动分类。Chazal等[36]利用傅里叶功率谱密度(Power Spectral Density，PSD)函数校正输入的倾斜鞋印图像，并将校正后的图像通过相关度计算确定他们之间的相似性以实现匹配。Alizadeh等[37]将稀疏表示方法引入鞋印图像检索与分类。Wang等[38]研究了流形排序方法在鞋印图像检索中的应用，并在包含10 096幅案发现场图像数据库上取得了较好的检索效果。Wu等[38]提出了一种融合样本邻居信息的相似性度量方法，采用混合特征在文献[39]中的数据库进行鞋印图像检索；王行行[40]提出了针对鞋底花纹图像的语义表达框架、图像整体性语义提取算法和局部性语义表达算法。舒莹莹[41]研究了基于聚类的鞋印图像检索算法。深度学习相对于传统的单隐层浅层学习，可进行多隐含层人工神经网络学习，将高维数据转换为低维编码，能更准确地描述数据，已在自然图像分类与检索中取得了巨大进展[42-43]，因此，很多研究将其用于鞋印图像检索。Kong等[44]使用预训练好的卷积神经网络(Convolutional Neural Nets，CNN)提取鞋印图像特征并提出多通道归一化交叉关联(Multi-Channel Normalized Cross-Correlation，MCNCC)方法用于相似性度量。Zhang等[45]先在ImageNet图像库上训练计算机视觉组(Visual Geometry Group，VGG)16网络，然后采用图像变换扩展数据库容量，改善了深度学习需要大样本数据进行训练的问题，提高了检索精度。Cui等[46]使用可去噪的深度信念网络(Deep Belief Network，DBN)提取案发现场鞋印图像的局部特征并采用空间金字塔匹配(Spatial Pyramid Matching，SPM)算法进行检索，在包含34 768幅图像数据库上的检索精度和检索速度上优于其他方法。Ma等[47]提出多部件加权卷积神经网络(Multi-Part weighted Convolutional Neural Network，MP-CNN)用于鞋印图像检索。该方法首先将鞋印图像沿垂直方向分为两个部件并使用系数共享的网络分别提取这两个部件的特征，然后计算各部分特征的权重矩阵并采用三元特征损失函数度量图像相似性。张弛[48]将卷积神经网络用于鞋印图像分类，研究了如何在小样本数据上训练分类模型，并在训练数据扩展、参数初始化和模型精简等3个方面进行研究。上述研究表明，深度学习方法在鞋印图像检索中也取得了一定的成功。深度模型提取的特征具有和局部特征类似的优点，即具有一定的鲁棒性。同时，深度方法避免了图像分割且不需要设计特征提取算法。

2.4 数据库及评价方法

鞋印图像检索研究的数据来源主要包括采集自案发现场的鞋印图像、使用足迹采集仪等设备采集的数据，以及鞋型生产厂家提供的数据，如图3所示。目前，鞋印检索公开的数据库较少，主要有公安部重点实验室所建成的鞋印图像数据库[9]，包含了555张案发现场鞋印图像和1 925张自行采集及合成的鞋印图像；Richetelli等人构建的混合数据库[33]，包含了100张高质量鞋印图像及172张作案现场图像，其中32张基于血迹和灰尘等不同媒介类型；FID-300鞋印图像数据库[49]，包含了1 175张图像。

图3 鞋印图像采集

鞋印图像检索结果评价方法主要包括查准率和查全率、归一化折损累积增益(Normalized Discounted Cumulative Gain，NDCG)、累积匹配特性曲线和AMS(Average Match Score)等4个指标。查准率是指系统返回的相似图像数占全部返回图像数的比例，查全率是指系统返回的相似图像数占全部相似图像数的比例，此外，查全率-查准率曲线也经常使用，即以查全率为横坐标，查准率为纵坐标所绘制的曲线。NDCG反映了一组查询图像检索性能的平均情况，对每一项的相关评分值除以排序值对应的递增的对数值，即折损值，再进行累加，并将结果进行归一化。累积匹配特性曲线适用于查询图像在参考数据库中只有一个相关记录的情况，主要通过描述前n%的累积匹配分数(Cumlative Match Score，CMS)得到，绘制曲线时，横坐标是排好序的图像数据集的前n%，纵坐标是累积匹配分数。AMS是在正确匹配目标图像之前需要进行比较的数据库类别的平均百分比。

2.5 公安刑侦领域的应用场景

鞋印图像检索研究来源于公安刑侦领域的应用需求。如马李芬[5]对入室作案现场残缺鞋印形成的原因进行了详细分析。孟小平等[4]提出了一种对同一个人穿不同鞋形成的足迹技术检验方法。通过对现场鞋印进行分析，可以反映出穿鞋人的行走习惯特性和脚型轮廓。高毅[52]提出一种利用不同种类鞋印长度推断身高差值的方法。基于采集的正常行走穿鞋样本与赤足样本图像，分析其差值数据，归纳总结出常见鞋种的差值系数从而推断身高范围。王彪等[6]分析了对不同花纹鞋印的同一认定方法，指出起落脚方向、压痕的凹凸形态和蹬痕方向等特点表现出来的形状、长宽及深浅(浓淡)等可作为同一认定的细节特征。

“电子信息现场勘验应用技术公安部重点实验室”团队在鞋印图像检索研究方面也取得了一定的进展[51-54]。文献[52]使用多示例学习(Multi-Instance Learning，MIL)模型进行鞋印图像检索以提高检索精度。文献[51，53-54]研究了大规模鞋印数据库中的检索实时性问题。文献[51]和文献[53]分别使用局部敏感哈希(Locality Sensitive Hashing，LSH)索引和反向索引以实现鞋印图像的快速检索。文献[54]针对公安部门鞋印图像数量不断增加的应用需求，提出一种基于词汇树的检索方法以实现数据库容量动态变化时的可伸缩检索。

3 鞋印图像检索未来研究趋势

结合图像检索技术的发展以及公安刑侦领域的实际应用需求，指出以下3点未来研究趋势。

1)结合刑侦领域专家经验设计鞋印图像检索系统。根据刑侦领域专家的经验，了解鞋印图像检索的实际需求，将其转化为计算机算法。只有这样才能真正将计算机技术应用到刑侦领域中，设计出可应用于刑侦实践的智能鞋印图像检索系统。

2)建立大规模鞋印图像数据库。在已有研究中，使用的鞋印数据库和公安实战要求有较大差距，不少研究工作仅使用数百幅鞋印图像进行实验。此外，目前公开的鞋印图像数据库较少，不利于同行之间的交流以及研究成果的评测。构建数十万甚至百万级规模的鞋印图像数据库，是鞋印图像检索研究的未来重要工作。

3)基于深度学习的检索算法设计。深度学习模型具有自动挖掘图像底层特征并避免繁难图像分割的优点，其在鞋印图像检索中的有效性也得到了证明[44-48]，未来可继续研究深度学习模型在鞋印图像检索中的应用。

4 结语

图像检索技术现已相当成熟，但由于鞋印图像的复杂性，鞋印图像检索仍然是一个极具挑战性的研究问题。通过总结鞋印图像检索技术的研究现状，为鞋印图像检索在公安刑侦领域内的应用指出了未来研究趋势。