陈伟卿，于 跃，兰 胤，黄日辉，张 翼，靳跃群，冯 海，刘威恒，姜福鑫

（1.大连恒锐科技股份有限公司，辽宁 大连 116085；2.广州市公安局刑事技术所，广州 510440）

鞋外底损伤特征是指大底在坚硬锐利的客体上踩踏、蹬踢、磕碰形成的硬伤，这些特征出现的位置、形状、大小和深浅具有随机性，特定性好[1]，是鞋印鉴定的主要依据。花纹裂缝特征，是鞋在穿用过程中由于受到外力的影响，导致鞋底局部材料缺失形成的一类损伤特征，在鞋印上呈现为连续花纹的中断。该特征常发生在较细的花纹上。引起花纹材料缺失的原因和物质特性不同，裂缝特征的大小和位置也因此具有较高的随机性，在直线型、波折型鞋印的鉴定中，这类特征的识别和特征之间相符程度的比较起到非常关键的作用。

实际鞋印鉴定和相关的科研工作中，特征的辨识主要由人工进行。国内外学者对随机特征（即细节特征）的检测和描述进行了一系列尝试。Yekutieli等[2]开发了专门的特征绘制工具，采用人工交互方式实现特征边界的描绘：首先围绕随机特征使用多边形标画出特征范围，对多边形内图像使用交互的二值化操作，得到初始边界，以此为基础，对边界进行人工的增、删、改操作，得到特征的最终边界，建立特征数据库，进行鞋印随机特征稀有性的量化研究；随后同机构的Shor等[3]利用该数据库验证了在实际案例中，使用他们提出的统计方法得到的量化结果，与传统的专家鉴定结论之间具有相关性。美国西弗吉尼亚大学Speir的团队[4-5]做了大量的工作，对1 300只鞋进行了随机特征检验，用于对不同鞋在相同位置上出现相似形状的随机特征的可能性分析。实验数据准备中，使用Photoshop软件中的铅笔工具，纯手工对鞋印图像中反映出来的随机特征进行描绘。上述两种方法均较为繁琐和耗时，特征位置的标识和特征边界的绘制不可避免受到操作人员经验的制约和其他人为因素影响。王新年等[6]将随机特征分为角型和斑点型两类，分别使用Harris角点检测器和Hessian检测器实现特征的位置（中心点坐标）检测，但未能标识出特征范围。刘珞晰[7]对84只鞋大底跟部的人造缺损特征进行了跟踪研究，使用Photoshop的磁性套索工具对鞋印上的缺损进行标划，用笔刷工具涂红标划的缺损，进而使用FIJI1.0软件对缺损特征进行测量描述，使用支持向量机对缺损进行训练和分类测试，实验结果表明缺损特征有较好的特定性。

可见，目前国内外研究机构已经开始了对随机穿用特征的特定性、稳定性的定量化基础性研究。特征检测是这些研究的基础。当前研究通常仅进行随机特征的位置检测，或借助工具使用人工交互方式进行手动特征标注，不能满足自动、快速、准确地检测特征的要求。因此本文提出一种基于嫌疑人鞋印图像花纹裂缝特征的自动检测算法，针对局部鞋印图像，利用图像处理技术，根据花纹的走向，自动检测出花纹裂缝特征所在区域，用于后续鞋印鉴定工作，或用于基于特征的量化研究中。

1 花纹裂缝特征自动检测算法

算法由图像预处理、连通域分析、花纹切分、花纹段配对、裂缝特征区域检测与标识等主要步骤组成，算法流程图如图1所示。

图1 算法流程图Fig.1 Flowchart of the algorithm

图像预处理包括图像二值化和中值滤波等，以分割出鞋印图像的花纹，并去除噪声影响；连通域分析即将图像分为互不相连的花纹集合，每个花纹为一个连通区域；花纹切分是将交叉花纹或走向改变的花纹，切分为方向单一的花纹段；花纹段配对，即对花纹段进行两两分组，根据各花纹段的走向和相对位置关系，判断其是否由同一花纹断裂所产生，即两者之间的空隙是否为一个裂缝特征；对于配对成功的一组花纹段，进行裂缝特征区域的检测，并用圆形在原图中标识出其所在区域，即完成裂缝特征的检测与标识。算法的输入为一局部图像，整幅足迹图像可首先进行分块，对每块图像调用该算法进行特征检测。

花纹裂缝特征示例如图2。图中显示一波浪型花纹鞋印的前掌部分，在从上到下第4条花纹的中间位置，及第6条花纹的左侧位置，分别有一处连续花纹的断裂，即裂缝特征（如图中红色圆所示）。

图2 花纹裂缝特征示例Fig.2 Exampled rift characteristics of a shoeprint pattern

1.1 连通域分析

连通域是指图像中具有相同像素值且位置相邻的前景像素点组成的图像区域，连通域分析（connected component analysis）[8]是指将图像中的各个连通域找出并进行标记的过程。对于二值图，选取一个前景像素点作为种子，在其八邻域内，将与种子相邻的前景像素合并到同一个像素集合中，最后得到的像素集合即为一个连通区域。

对给定的鞋印二值图像进行连通域分析，可将其中的花纹分为不同的花纹集合，便于进行后续的裂缝特征所在区域的检测。图3给出了一花纹图像的连通域分析示例，其中，图3a为鞋印图像的某一局部；图3b为使用最大类间方差法[9]对图3a进行阈值化后得到的二值图像，其中前景像素为白色；图3c为图3b经过连通域分析后得到的4个花纹集合，分别由红色、黄色、浅蓝色和蓝色表示。

1.2 花纹切分

鞋底花纹类型中，除了常见的平行直线类花纹，还常存在各种波折型、网格型花纹。本文提出的裂缝特征检测方法，主要依据花纹的走向进行，因此需要首先对交叉型或波折型等复杂花纹进行切分，形成一系列走向单一的花纹段。

对图像中每个花纹，计算其复杂度。给定阈值T，若复杂度小于T，则视为简单花纹；若复杂度大于或等于T，则视为复杂花纹，需进行切分，转化为系列简单花纹，也称花纹段。

1.2.1 复杂花纹判定

花纹复杂度定义如下：

其中密实度为平面几何形状描述中常用的参数，定义为：

一个花纹的凸包是指包含其所有前景像素的最小的凸多边形[10]。花纹的面积为前景像素个数之和，凸包面积为凸包内包含的像素总个数。

图4为图3c所示各花纹的复杂度分析，根据经验，复杂度阈值T取经验值0.35。可见，图4a、4c为简单花纹，图4b、4d为复杂花纹，需进行花纹切分。注意，对于图4c这类与区域边界相连的简单花纹，由于其区域较小且与其它花纹距离较远，不再进行后续的计算。

图3 连通域分析（a：鞋印局部图像；b：二值图；c：连通域）Fig.3 The connected component analysis (a: local shoeprint image; b: binary-formatted image; c: the connected components)

图4 花纹复杂度分析（a：0.1342；b：0.3703；c：0.1645；d：0.5104）Fig.4 Analysis into the complexity of shoeprint patterns (a: 0.1342; b: 0.3703; c: 0.1645; d: 0.5104)

1.2.2 基于边界到边界方向距离的复杂花纹切分

简单花纹无需进行切分处理，直接进行配对即可。对于复杂的花纹，则需要进行切分，即根据其中包含的多个单方向花纹的走势，将其切分成多个不同方向、互相独立的花纹段。本文采用边界到边界方向距离（boundary-to-boundary orientation distance，BBOD）算法，实现复杂花纹的切分。

BBOD算法[11]常用于汉字字符的笔画分析中。其基本原理如下：

1）首先将0°~180°均匀量化成K个方向（本文K＝60）；

2）对花纹区域中的每个像素，分别计算经过该点的K个方向的直线与该像素所属花纹区域边界相交的两个边界点之间的距离，得到一个1×K维的方向距离矢量；

3）以角度为横轴，方向距离为纵轴，可得该像素点的BBOD曲线；

4）计算BBOD曲线的所有波峰，并将波峰对应的量化方向作为通过该点的切线方向。

图5a为一鞋印局部图像二值图，图5b为图5a右侧交叉花纹某点（左图红色星号所示）处的BBOD曲线。从图中可见，该点的切线方向为150°（水平向右为x轴正方向，逆时针方向角度为正）。

图5 BBOD曲线（a：鞋印局部二值图像；b：BBOD曲线）Fig. 5 BBOD plotting (a: binary-formatted image of local shoeprint pattern; b: BBOD curve about the indicated red star in this Fig.’s a)

基于上述方法求得复杂花纹上各点的切线方向，具有相同切线方向的点组成的连通区域即为该复杂花纹拆分出的花纹段。BBOD曲线具有2个以上波峰的像素，对应于2个或以上花纹的交叉位置，将同时被放在对应量化方向的花纹段中。图6为一花纹切分示例，其中图6a为鞋印局部二值图像，对其中的复杂花纹使用上述切分方法，得到箭头右侧两组不同方向的花纹段。

图6 复杂花纹切分（a：二值图；b：子图1；c：子图2）Fig.6 Splitting the complex pattern (a: binary-formatted image; b/c: the sub-image 1/2 from splitting)

1.3 花纹段配对

经过上述复杂花纹判定和对复杂花纹的切分之后，得到了所有的简单花纹段。接下来将根据这些花纹段的位置及形态，进行疑似裂缝的判定，即对所有简单花纹段，分别进行两两组合，根据其走势、宽度和空间关系判定它们是否为同一花纹断裂而形成。如果是，则配对成功，这两个花纹段将作为一组保留，以进行后续的裂缝特征检测。

本文提出了基于投影的花纹段配对方法。对于直线型花纹，裂缝后所形成的两个花纹段走向一致，即二者在同一条直线（共线）；波折型的花纹，在折角处断裂时，所形成的两个花纹段呈一定角度（相交）。根据这一规律，对一组花纹段的组合，可通过如下方法判断其是否由一个完整花纹中断形成，完成配对：

1）分别计算两花纹骨架[12]，判断骨架线是否共线或相交。如果满足条件，则继续。

2）生成以候选的两个花纹段为前景的二值图像BW1。

3）分别计算两个花纹段的宽度w1和w2，如果两宽度差绝对值大于较小宽度的0.5倍，则视为原鞋底设计中的两个不同花纹，非由同一花纹中断形成，不能配对，否则，继续。

4）计算两个花纹段的质心，及两质心连线与图像水平方向的夹角θ，将二值图旋转角度θ，得到二值图BW2。

5）统计BW2在水平方向的投影直方图，该直方图若存在两个波峰，且波峰距离小于一定阈值，则认为当前候选花纹段为同一个花纹中断而成，即两花纹段之间空隙为一裂缝特征。考虑到鞋底花纹设计中，相邻花纹之间的沟槽宽度通常不大于花纹阳纹本身的宽度，为避免将沟槽视为裂缝特征引起误检，此处阈值最大可设为1.5倍花纹宽度。

仍以前面的局部图像为例说明简单花纹的配对过程，具体如图7所示。图7a为鞋印局部二值图，对其中复杂花纹切分后形成如图6所示的2组不同方向的子图，以子图1为考察对象，可见共有3个直线型花纹段（图7b），任取两组，可有3种组合：（1，2）、（1，3）、（2，3）。其中前2个组合均不满足共线或相交要求，故仅需对（2，3）的组合进行配对判断。二者形成的二值图BW1如图7c所示；分别求得两段花纹的质心（图7d），计算质心连线与图像水平方向的夹角；并按照该角度旋转生成图像BW2，如图7e所示；对BW2进行垂直投影，并按最大值归一化，投影结果如图7f的蓝色曲线所示，为了避免噪声影响，对垂直投影进行二值化，小于一定阈值（图中阈值为0.35，对应红色虚线）的视为0，否则为1，得到图中的红色阶跃曲线，及曲线的两个峰点P1和P2；两点的距离小于花纹宽度，故图7c中这组花纹段配对成功。

图7 花纹段配对（a：区域图像；b：切分子图；c：待配对；d：质心连线；e：旋转图像；f：垂直投影）Fig.7 Having the correlating segments matched in pairs (a: original local image; b: sub-image after splitting; c: pairs to be matched; d:joining segments with centroids; e: the image after rotation; f: vertical projection)

花纹宽度的计算方法：使用形态学方法计算花纹的骨架，对骨架上的每个点，计算过该点的骨架法线与花纹边界的两个交点，两交点的欧氏距离即为该骨架点处的花纹宽度，取所有骨架点花纹宽度的均值，作为整个花纹的宽度。

1.4 裂缝特征检测

裂缝特征检测是指对配对花纹段进行处理，确定它们之间的缺失部分（即裂缝特征）的位置和范围，并以适当大小的圆形将该部分标识出来的过程。包括如下步骤：1）裂缝特征中心的确定；2）裂缝特征范围的确定；3）裂缝特征的标识。

对于组成一个裂缝特征的两个花纹段，其花纹方向上最近的两端之间的空隙即为裂缝特征，因此，可分别计算两个花纹段的骨架，取两条线距离最近的两个端点的连线的中点，作为裂缝特征的中心。裂缝特征的范围用以裂缝中心为圆心、以花纹宽度为半径的圆进行标识。图8中，a为待检测裂缝特征的花纹图像；b中红线为配对花纹段的骨架，蓝线为两骨架最近点的连线，红色圆圈为检测到的裂缝中心点；c为某骨架点处花纹宽度的计算示意，图中的蓝线和红线分别为该花纹段的边界和骨架，绿色为骨架某点处骨架线的法线，两个红色小圆为法线与边界交点；d为检测结果，裂缝特征用红色圆标识。

图8 特征区域检测与标识（a：原图；b：特征中心；c：花纹宽度；d：特征标识）Fig.8 Detection and labelling of characteristic site (a: original image; b: characteristic center; c: pattern width; d: labelled characteristic site)

2 实验

前文介绍了对于给定的图像区域，自动进行裂缝特征检测的算法。为了验证算法的有效性，首先进行实验图像的采集，然后使用本文提出的方法，进行裂缝特征检测实验。

2.1 实验图像采集

首先，使用大连恒锐科技股份有限公司研制的足迹采集系统3.1进行鞋印图像的采集。共收集经一定时间穿用的平底鞋180双，由原穿用者亲自穿着，按照采集方法，采用正常行走的姿势踏过采集面板，采集得到动态的数字化鞋印，每只鞋共采集5枚，分辨率为300 DPI。其次，由具有一定检验经验的人员对这些鞋印进行初筛，选择有个别特征反映的鞋印作为备选鞋印，若每只鞋有多枚鞋印入选，则只选其中1枚，最后得备选鞋印33枚；对备选鞋印进行裂缝特征人工检验，截取裂缝特征所在的局部图像，作为实验图像，共计70张。

为了与算法结果对比，人工对这些实验图像进行特征标记（共标记特征80个），作为算法性能的评价基础。

2.2 实验结果与分析

为了测试算法的性能，在实验图像上应用上述算法进行自动裂缝特征检测，并使用客观指标进行评价。

部分有代表性花纹的实验结果如图9所示。图9a为复杂的网格型花纹上的裂缝特征检测示例，从左至右分别为鞋印局部图像原图、经预处理和对其中复杂花纹切分后形成的子图1和子图2、配对成功的一组配对花纹、检测结果；图9b为包含多个裂缝特征的直线型花纹检测示例，从左至右分别为原图、3组配对成功的花纹、检测结果，可见3个裂缝特征均得到了正确检测；图9c为波折型花纹的裂缝特征，从左至右分别为原图、配对花纹、检测结果。该特征发生在转折处，也被正确检测。

图9 多种类型花纹的裂缝特征检测实例（a：网格型花纹；b：直线型花纹；c：波折型花纹）Fig.9 Detection of rift characteristics with several shoeprint patterns (a: grid pattern; b: multiple-characteristic line pattern; c: wave pattern)

采用特征检出率进行算法性能的客观评价。检出率是指实验数据中的裂缝特征被算法正确检出的比例，即：

检出率＝正确检出的特征数目／特征总数目 （3）

对于检测出的特征，根据交并比是否大于设定阈值来判断其是否正确。记检测出的特征标识圆为Cd，对应的人工标记圆为Cg，二者的交并比（intersection over union，IOU）为：

其中等号右边式子的分子表示两个圆交集的面积，分母表示两个圆并集的面积。若IOU>0.5，则认为检测正确。

实验图像中人工标记裂缝特征80个，算法正确检出特征70个，检出率为87.5%，各特征对应的IOU值如表1，小于阈值的如黑体部分所示。

表1 检测结果IOU值Table 1 IOU (intersection over union) values from detection into characteristics

图10给出了部分漏检的结果示例，其中红色圆标记的是检测结果，蓝色圆是漏检的特征。算法漏检的主要是位于图像边缘的裂缝特征，由于组成这些特征的花纹段较小且位于图像边缘，在预处理阶段被过滤掉，导致后续无法参与配对。

图10 漏检示例Fig.10 Characteristics (indicated with blue circle) missed of detection (for exampling)

当前算法主要是在给定的鞋印区域图像上进行，完整鞋印需先进行分块，再对每一块图像调用检测算法完成检测。实验结果表明，算法能够帮助检验人员对裂缝特征进行定位。

后续研究中，需研究鞋印自动分块的方法，以及尝试使用重叠分块的方式降低由于特征位于块边缘而漏检的概率。

3 结论

本文对鞋印图像随机特征的识别进行了研究，提出了一种基于复杂花纹切分的裂缝特征的自动检测方法。实验结果表明，算法能够正确检出常见直线型、波折型、网格型等类型花纹上的裂缝特征。对于相对复杂的整幅鞋印图像，可对其进行分块，对每块图像使用本文方法进行块内裂缝特征的自动检测，后续研究将致力于鞋印中相似花纹的分块处理。本文方法可有效降低鉴定中这类特征检测对人员经验的依赖，消除人为因素的影响，为下一步特征的客观比较奠定基础。