引用本文
张庆时, 汤澄清, 和焕胤. 基于Matlab的鞋底损伤特征分类算法[J].刑事技术, 2020,45(4):371-375
ZHANG Qingshi, TANG Chengqing, HE Huanyin. Matlab-based Algorithm to Classify Shoe-soles’ Damaged Characteristics[J]. Forensic Science and Technology,2020,45(4): 371-375  
Doi: 10.16467/j.1008-3650.2020.04.008
Permissions
Copyright©2020, 《刑事技术》编辑部
《刑事技术》编辑部
基于Matlab的鞋底损伤特征分类算法
张庆时1, 汤澄清1, 和焕胤2
1.中国刑事警察学院,沈阳110035
2.上海市公安局杨浦分局刑事科学技术研究所,上海200090

第一作者简介：张庆时,男,安徽合肥人,硕士在读,研究方向为刑事科学技术。E-mail: 867919527@qq.com

基金资助: 中国刑事警察学院研究生创新能力提升项目（2019YCZD03）
摘要

目的 对鞋底经常出现的三角形、线/曲线、圆形、不规则形四种随机损伤特征进行准确分类,以便后续对鞋底损伤特征的量化研究。方法 提出了每个特征的形状由三角形度、线性度、圆形度构成的三维向量决定,对三角形度、线性度、圆形度设置适当的阈值,在分类识别时三维向量的元素和设定的阈值比较得出特征的具体形状。结果 利用Matlab软件编制了三角形度、线性度、圆形度的计算程序和阈值比较程序,运行结果表明在提前设定的阈值下通过比较每个形状的三种形度可以实现对形状特征的分类识别,与人工分类识别结果的对比体现了计算机识别的准确率,也体现了计算机识别的定量化优势。结论 基于Matlab编写的分类识别程序能够达到正确区分损伤特征和量化损伤特征的目的。

关键词: 痕迹学; 形状特征; 阈值; Matlab; 分类识别
中图分类号:DF794.1 文献标志码:A 文章编号:1008-3650(2020)04-0371-05
Matlab-based Algorithm to Classify Shoe-soles’ Damaged Characteristics
ZHANG Qingshi1, TANG Chengqing1, HE Huanyin2
1. Criminal Investigation Police University of China, Shenyang 110035, China
2. Criminal Science and Technology Research Institute of Yangpu Branch of Shanghai Public Security Bureau, Shanghai 200090, China
Abstract

Objective There are four common characteristic damages appearing randomly in the forms of triangle, line/curve, circle and irregularity with the soles of shoes, implying high value and research significance for identification of shoes’ soleprints. This paper tries to accurately classify them so as to establish one quantitative approach to the soles’ damaged characteristics.Methods Each of the four characteristic damaged forms (triangle, line/curve, circle and irregularity) was defined with the proposed conceptual three-dimensional vectors of triangularity, linearity and circularity. With setting the appropriate threshold of each constituent element of the vectors, Matlab software was selected to calculate the achieving extent of triangularity, linearity and circularity from each damaged form so that the four different damaged characteristics were gauged.Results Through Matlab software to compile the calculation and comparison programs for determination of triangularity, linearity and circularity, the results from the programs performing showed that the four damaged characteristics were quantitatively classified into one certain specific form of them. Such a program-specified comparison excels what human attains in both the accuracy and quantification, especially in the recognition of triangular characteristics. However, limitations were also present from the program-specified comparison with the line/curve identification, showing lower score for the curve.Conclusion Matlab-based classification program can correctly both distinguish and quantify the damaged characteristics.

Key words: traceology; characteristic form; threshold; Matlab; classification and recognition

足迹在犯罪现场的出现率和提取率很高, 能够反映出犯罪嫌疑人的大量个人信息[1]。当前足迹检验有4种比较方法：直观比对法、方位比对法、划线构图法、重合比对法, 这4种方法是基于检验人员的个人经验对特征的形象比较[2]。随着信息化和大数据时代的到来, 司法鉴定也开始向数字化方向发展。在量化研究的大趋势下, 似然比和其他统计方法开始进入法庭科学从业人员的视野。似然比等方法应用于鞋印检验的前提是对鞋底可能产生的特征进行分类和概率统计。本文尝试对鞋印检验中常用的损伤特征进行分类实现量化特征以便后续研究。目前国内关于鞋底损伤特征研究较少, 没有明确的分类并且叫法不一, 单大国等[3]将这类特征叫做一次性磨损特征并大致分为沟痕、小坑、缺口、裂口、孔洞等。季峻[4]将这一类特征称为细小损伤特征, 并且将该类特征分为点状、线状、坑洼状、印压状四类。国外的相关研究较多并且将这类特征称作随机获得特征（randomly acquired characteristics, RAC）, Damary[5]将该类特征分为划痕、孔洞、缺角、裂痕、附着物、羽状物和图案缺失七类。Speir[6]和Richetelli[7]将这类特征分为线/曲线、圆形、三角形和不规则形四类。综合比较当前的分类结果, 我们将随机损伤特征按照Speir的四分法进行图形分类程序设计, 以满足量化检验和似然比等方法的需求。

1 前期图像处理和程序设计思路
1.1 前期图像处理

采用垂直拍照的方式获取原始图像（图1a）, 用photoshop中的磁性套索工具选中损伤特征然后填充黑色获得一副新的图片（图1b）, 利用Matlab中的rgb2gray函数将这两幅图片灰度化后用imsubtract函数相减获得只有随机特征的灰度图（图1c）。

图1 图像前期处理Fig.1 Image preprocessing

前期处理后的图像是灰度图像, 可以用来计算三角形度。但是计算线性度和圆形度需要二值图像, 图像二值化可以采用阈值分割法。设置一定的阈值, 当图像的像素值低于阈值时赋值为0, 否则赋值为1得到二值图像。

1.2 程序设计思路

分别计算随机损伤特征的三角形度、线性度、圆形度获得一个三维特征向量, 在特定的阈值下比较这三个数值的大小得到特征的形状, 流程如图2所示。

图2 程序设计流程图Fig.2 Principle and route of program design

1.2.1 三角形度（T）

Rosin[8]提出了利用图像中心矩特征计算三角形度的方法。图像的矩特征是以各阶矩描述图像灰度统计特征的方法, 具有旋转、平移、尺度不变等特性, 因此矩函数在图像处理中得到广泛的应用[9]。

一幅M× N的数字图像f (x, y), 其p+q阶几何矩mpq、中心矩μ pq为：

$m_{pq}=\sum^{M}_{x=1}\sum^{N}_{y=1}x^{p}y^{q}f(x, y)$ (1)

$\mu_{pq}=\sum^{M}_{x-1}\sum^{N}_{y-1}(x-x_{0})^{p}(y-y_{0})^{q}f(x, y)$ (2)

其中f (x, y)是图像像素组成的密度函数。当式(3)中的I等于1/108时, 任何类似三角形的形状都可以仿射变换成一个直角三角形[10]。

$I=\frac{\mu_{20}\mu_{02}-\mu^{2}_{11}}{\mu^{4}_{00}}$ (3)

其中, μ 20、μ 02、μ 11是图像的二阶中心矩, μ 00是图像的零阶矩。根据式(4)可以将三角形度标准化在0和1之间[8]。

$T=\left\{\begin{aligned}108I & & I≤ \frac{1}{108} \\ \frac{1}{108I} & & I> 108 \end{aligned} \right.$ (4)

1.2.2 线性度（L）

Park[10]提出了利用形状特征的长度和宽度之比来确定图形是否为线形或曲线形, 设图形的长度为, 宽度为, 如图3a所示, 其中是图形在主轴方向的最大长度, 是主轴方向上图形的最大宽度, 当比大得多时, 图形可归为线/曲线类。因为几何图形的最小外接矩形是唯一的, 所以它在一定程度上描述了该图形的几何特性, 即线性图形的长宽也可以通过最小外接矩形获得[11]。图3b中是矩形的长度, 是矩形的宽度, 当矩形的长宽比很大或很小时可认为图形为线/曲线类。

图3 图形示意图（a:长宽; b:最小外接矩形）Fig.3 Schematic for definition of forms (a: length and width; b: the minimum-circumscribed rectangle)

本文采用最小外接矩形的方法获得图形的长度和宽度, 具体步骤如下。

第一步：利用Matlab中的连通域标记函数bwlabel寻找二值图像中的连通区域并对像素值不同的区域进行类别标签, 主要有4连通和8连通。4连通是指一个像素在上、下、左、右和其他像素都相连。8连通指一个像素在上、下、左、右、左上、左下、右上、右下都和其他像素相连。

第二步：利用minboundrect函数求最小外接矩形并返回矩形的四个顶点坐标, 该函数可以按面积和边长两种方式计算最小外接矩形, 有些matlab版本不是自带minboundrect函数则需要在使用前先定义该函数。

第三步：将矩形的顶点坐标带入欧式距离公式即可得出矩形的长度和宽度并计算长宽比。

1.2.3 圆形度（R）

圆形度可以用圆形度公式得出[12]。

$R=\frac{4\pi· A}{C^{2}}$ (5)

其中, A是损伤特征的面积, 即二值图像中损伤特征的像素点总数; C是损伤特征的周长, 即二值图像中目标区域边界的长度。显然标准圆的圆形度为1。先使用bwlabel函数对二值图像不同像素值的区域进行标注, 再使用度量图像区域属性函数regionprops对图像添加包含该区域的最小矩形并标注数字、寻找重心, 计算面积、周长, 最后将面积和周长代入公式(5)计算出圆形度。

1.2.4 设计阈值

根据Speir[6]给出的不同形状的三角形度、线性度、圆形度三者之间的关系, 结合本文的线性图像长宽获取方式得出如下阈值：1）三角形的三角形度大于等于0.8且圆形度小于0.8。2）线/曲线的线性度大于5或小于0.2且三角形度小于0.8。3）圆形的圆形度大于等于0.8。4）不符合以上三类标准的归为不规则形。

2 程序和识别结果

程序代码一共分为前期图像处理、图像二值化、计算三角形度、线性度、圆形度、设置阈值识别结果6部分, 具体程序设计见补充材料S1。识别结果如图4所示, 每个图形特征的三角形度、线性度、圆形度与设定的阈值比较后可以实现很好的分类效果。各图形下方三维向量H=[T L R]的三个元素分别为：T是三角形度、L是线性度、R是圆形度。

图4 分类识别结果Fig.4 Resultant classification and recognition with computer programs

3 讨论

从25只鞋底共采集了88个损伤特征进行计算机分类, 其中线/曲线类特征出现8次, 圆形特征出现19次, 三角形特征出现13次, 不规则形出现48次。可以看出在全部损伤特征中不规则形特征数量最多, 线/曲线类最少, 计算机分类识别结果如图5所示。占比高的特征稀有性要低于占比低的特征, 因此对特征进行分类统计后可以大致评价特征的稀有程度。

图5 计算机对损伤特征的分类结果Fig.5 Classification of the damaged characteristics run out from computer programs

为了探究计算机对特征的分类结果与人工分类结果的相似与区别, 将统计的88个损伤特征进行了人工识别。3位志愿者（以下简称1号、2号、3号）参与了特征的分类, 结果见表1。

表1 特征人工识别分类结果 Table 1 Manual attainable recognition and classification

3位志愿者事先并不清楚计算机识别的原理, 均是根据自己的经验和对各个特征形状的认识在互不交流的情况下进行分类。从表1中可以初步看出不同志愿者的分类结果有差异, 与计算机分类结果也有区别, 如图6所示。

图6 计算机与人工分类结果比较Fig.6 Comparison of classification from computer programs against that with manual operation

从图6中可以看出3位志愿者对线/曲线的认识基本相同, 但是对圆形、三角形、不规则形的认识存在差异。由于每个人对各种形状的敏感度不同, 导致人工分类结果不能统一。人工分类结果与计算机分类结果相同点都是不规则形损伤特征最多, 原因可能是特征形状分类不够细致, 将不属于线/曲线、圆形、三角形的特征都归为不规则形导致该类特征数量明显多于其他特征。计算机对线/曲线的统计结果明显少于人工分类。因为线性度是由矩形的长宽比决定的, 而图7这类线性特征用最小外接矩形计算线性度时存在长宽比明显大于或小于实际长宽之比的情况。如图所示特征计算出的线性度为0.5没有达到线/曲线类的阈值, 因此被判定为不规则形, 而人工分类将其归类为线/曲线。在接下来的研究中可以针对此问题进行算法优化或者将该类特征单独分为一类, 例如角形特征等。

图7 计算机识别困难的线性特征Fig.7 Linearity difficult to recognize through computer

人工分类与计算机分类的结果还有一个不同点：计算机对圆形和三角形的识别明显高于人工分类。原因是分类依据不同, 人工进行分类依据的是个人经验, 而计算机分类依据的是三角形度、线性度和圆形度。故对于图8a所示特征, 有两位志愿者认为是线形一位认为是三角形。计算机将其归为三角形, 因为该特征的三角形度为0.91, 大于设定的阈值。仔细观察不难发现该特征确实更接近于三角形, 只不过两个底角非常大并且底边很短类似于图8b的三角形。对于这种不能明显分类的形状特征, 人工分类时出现了不同结果。

图8 人工分类出现分歧的三角形特征Fig.8 Ambiguous triangularity unable to classify by human

4 结论

本文对鞋底产生的随机损伤特征进行分类, 运用Matlab设计程序将随机损伤特征分为三角形、线/曲线、圆形和不规则形四类。其中三角形度通过图像中心矩特征获得; 线性度通过图像最小外接矩形的长宽比获得; 圆形度用图像的面积和周长通过圆形度公式计算获得。图像处理结果表明通过这三个形度可以实现对特征形态的分类, 具体总结如下：

1）本文的分类算法能够准确识别特征形状并进行分类, 每个特征从三角形度、线性度、圆形度三个方面度量特征形状, 实现了对特征的定量化描述, 能够解决不同人凭经验判断导致的结果不统一问题。

2）为后续探究似然比等概率统计方法用于检验鉴定提供了研究基础, 对特征进行分类统计也可以更好地评价不同形状特征的价值。

3）本文还存在特征分类不够细致、算法需要优化等问题。接下来应该在统计大量损伤特征的基础上对特征进行更为细致的分类, 对算法也进行相应的优化。

补充材料

本文补充材料见：http://www.xsjs-cifs.com/CN/volumn/home.shtml。

参考文献
[1] 汤澄清, 桑伟波, 姬瑞军, 等. 蹬痕形成和变化的生物力学基础研究[J]. 中国人民公安大学学报(自然科学版), 2019(2): 8-11.
(TANG Chengqing, SANG Weibo, JI Ruijun, et al. A biomechanical study on the formation and change of press-mark[J]. Journal of People’s Public Security University of China (Science and Technology), 2019(2): 8-11. ) [本文引用:1]
[2] 戴恒山, 沈笛, 丁祥军. 足迹证据文书的法律构造[J]. 中国刑警学院学报, 2018, 145(5): 97-100.
(DAI Hengshan, SHEN Di, DING Xiangjun. Legal construction of footprint evidence documents[J]. Journal of Criminal Investigation Police University of China, 2018, 145(5): 97-100. ) [本文引用:1]
[3] 单大国. 刑事科学技术[M]. 北京: 高等教育出版社, 2016.
(SHAN Daguo. Criminal science and technology[M]. Beijing: Higher Education Press, 2016. ) [本文引用:1]
[4] 季峻. 鞋印检验中细小损伤特征及其运用[J]. 刑事技术, 1986(4): 34-36.
(JI Jun. The characteristics and application of small damage in footprint test[J]. Forensic Science and Technology, 1986(4): 34-36. ) [本文引用:1]
[5] DAMARY N K, MANDEL M, WIESNER S, et al. Dependence among rand omly acquired characteristics on shoeprints and their features[J]. Forensic Science International, 2018, 283: 173-179. [本文引用:1]
[6] SPEIR J A, RICHETELLI N, FAGERT M, et al. Quantifying rand omly acquired characteristics on outsoles in terms of shape and position[J]. Forensic Science International, 2016, 266: 399-411. [本文引用:2]
[7] RICHETELLI N, NOBEL M, BODZIAK W J, et al. Quantitative assessment of similarity between rand omly acquired characteristics on high quality exemplars and crime scene impressions via analysis of feature size and shape[J]. Forensic Science International, 2017, 270: 211-222. [本文引用:1]
[8] ROSIN P. Measuring shape: ellipticity, rectangularity, and triangularity[J]. Machine Vision & Applications, 2003, 14(3): 172-184. [本文引用:2]
[9] 朱亚旋, 张小国, 陈刚. 基于图像纹理与矩特征的转子绕线检测研究[J]. 测控技术, 2018(2): 19-24.
(ZHU Yaxuan, ZHANG Xiaoguo, CHEN Gang. Research on rotor winding detection based on image texture and moment[J]. Measurement & Control Technology, 2018(2): 19-24. ) [本文引用:1]
[10] PARK U, JAIN A K. Face matching and retrieval using soft biometrics[J]. IEEE Transactions on Information Forensics & Security, 2010, 5(3): 406-415. [本文引用:2]
[11] 林玉池, 崔彦平, 黄银国. 复杂背景下边缘提取与目标识别方法研究[J]. 光学精密工程, 2006(3): 509-514.
(LIN Yuchi, CUI Yanping, HUANG Yinguo. Study on edge detection and target recognition in complex background[J]. Optics and Precision Engineering, 2006(3): 509-514. ) [本文引用:1]
[12] 牛立聪, 孙香花, 左晓宝. 基于Matlab图像处理的砂石颗粒圆形度计算方法[J]. 混凝土, 2012(1): 15-17.
(NIU Licong, SUN Xianghua, ZUO Xiaobao. Circularity calculation of sand and stone particles based on Matlab image processing[J]. Concrete, 2012(1): 15-17. ) [本文引用:1]