摘要

    鞋印是案件现场留下的主要线索，在案件侦破中起着十分重要的作用。传统的鞋印匹配算法是基于人工编码的，识别能力有限且对操作者依赖性强。本文提出了基于功率谱密度（PSD: power spectral density)和Zernike矩的鞋印匹配方法。针对捺印图片或现场获取的花纹清晰的鞋印图片，利用功率谱密度的相关系数实现匹配。针对背景复杂或花纹不清晰的现场鞋印图片，将鞋印用一系列不规则形状表示，通过插值对形状进行平移、尺度标准化，并将变换后的形状归一化到单位圆内计算各阶Zernike矩。利用Zernike矩重构原形状,依据各阶矩的重构能力进行特征选择，构成特征向量，最后通过特征向量间的加权欧式距离实现匹配。实验对400余幅真实的鞋印进行了测试，结果表明，识别率在86%以上，可有效地实现鞋印的匹配 。
关键词: 鞋印匹配；功率谱密度；Zernike矩；不变性；法庭科学

引言

    鞋印是案件现场的主要痕迹，它具有较好的稳定性，同指纹、DNA等一样具有身份认定的作用。相比于指纹，鞋印更容易在案件现场获取，是案件侦破中非常有价值的线索。刑侦人员主要采用人工比对的方法，即人工将犯罪现场获取的鞋印图片与库存的图片进行比对，从而实现案件的侦破。由于鞋印数量巨大，寻找一种基于计算机的自动比对方法十分必要，有利于减少人工操作量，提高比对的正确率，充分发挥鞋印在案件侦破中的作用。
    目前的鞋印匹配系统主要采用基于人工编码的方法[1-3]。即将市面上可见的各种鞋底图案人工制定一套编码标准，对不同的图案给予不同的编码，然后根据该标准对鞋印编码，进而实现鞋印识别。人工编码方法的缺点在于过分依赖于操作者，从而造成识别结果的误差。其次，鞋印种类繁多且日趋复杂，使鞋印匹配很难达到满意的效果。
    对于捺印图片或花纹清晰的现场鞋印图片本文选取功率谱密度（PSD: power spectral density）进行鞋印匹配[4]。该方法计算各鞋印图片的PSD值，并用其相关系数衡量两幅鞋印的相似度。现场鞋印图片多残缺不全，给图片的配准带来了很大的难度，而利用该方法既可以描述图片的纹理特征，也可以利用PSD的平移不变性和旋转变换的简易性避免烦琐的图片配准过程。而此方法的问题在于识别效果受背景干扰较大，因此对图片的预处理要求较高，当现场鞋印图片的背景信息复杂且难以和鞋印花纹分开时效果并不理想。
针对背景复杂或花纹不清晰的现场鞋印的匹配，本文提出了基于Zernike矩的鞋印识别方法。该方法从鞋印上提取形状进行识别，可以有效的避免人为误差、鞋印图案复杂度以及图片预处理的限制。矩特征是被广泛应用的形状特征之一，不变矩满足平移、缩放和旋转不变性，排除了形状的空间位置对识别结果的影响，因此被广泛地用于形状识别。Hu[6]最早提出了不变矩的概念，但由于Hu 矩存在的冗余量大以及非正交等缺点, Teague[7]引入了基于正交多项式的Zernike矩。Teh[8]比较了各种不变矩对噪声敏感性、信息冗余度和描述形状的能力，结果表明, Zernike 矩性能最好。因此本文选择Zernike 矩进行形状识别。Zernike的特征提取对形状没有任何要求，因此该方法适用于任何不规则图形。

基于PSD的鞋印匹配

 1 PSD的性质

 2  基于PSD的鞋印匹配方法

基于Zernike矩的鞋印匹配

 1  Zernike矩及其不变性

 2 鞋印特征的提取及匹配

    首先采用人工勾画的方法得到有匹配价值的形状信息如图1所示。

    为保证平移和尺度旋转不变性，对提取的形状进行标准化处理，如图2所示。以形心为中心作形状的最小外接正方形，并通过双线性插值将形状变换到统一大小。使用该方法可以同时完成平移和尺度标准化，并保证变换前后形状的纵横比例不变。对每一个标准化的形状，以形心为原点，如图2（c）建立极坐标系。
由式(8)—(10)容易计算得到形状的各阶Zernike矩。很显然，选取矩的阶数越高，对形状的反映越精确，但相应的增加了计算量，减低了匹配速度。

    Zenike矩的正交性使得各阶矩对形状表达的贡献是独立的，只要简单的将各阶矩与对应的Zernike多项式相乘后相加，即可得到重构形状。利用Zenike矩重构形状的简易性，可以通过比较重构形状和原形状的差异来评价各阶矩的形状表达能力，并以此为依据进行特征选择[9]。

实验结果与分析

    为测试本文提出的鞋印匹配方法的效果，我们从鞋印数据库中选取花纹清晰且花纹与背景易于分离的200幅鞋印图片采用基于PSD的方法进行实验，从其余不够清晰的图片中选取200余幅采用基于ZERNIKE矩的方法进行实验。

  1 基于PSD方法的鞋印匹配结果及分析

    为测试该方法的识别效果，我们从每幅鞋印图片中各截取5幅局部鞋印图片构成测试数据库，如下图所示：

    通过对200余幅鞋印的测试，识别率为86%。从实验结果看，该方法对花纹清晰，背景单一的鞋印图片有较好的识别效果。

 2  基于Zernike矩的鞋印匹配结果及分析

    我们从200余幅现场鞋印中分别勾画出如图5所示的形状以代表每幅鞋印，因此鞋印识别效果由形状识别决定。以下实验均以形状代替鞋印进行说明。
    实验一：不变性测试。
    由某一图形分别经旋转、平移和缩放三种变换得到一组测试图形。表1中s1为原形状，s2—s4由s1旋转得到，s5—s6由s1平移得到，s7—s9由s1 缩放得到，表中数据为形状间的两两距离。由实验结果可以看出，变换后图形间的距离相对较小，即该方法具有抗平移、旋转、尺度性能。
    实验二：形状识别测试。
    图5是一组不规则形状，各形状间的距离见表2。实验结果表明Zernike矩可以有效的将相似的不规则形状识别出来。在这组形状中，1—5相似，6、7、8相似，9与10相似，11与12相似。表2数据显示各组相似形状间的距离明显小于与其他形状的距离，因此可以实现有效区分,识别率为98%。
 

结论

    本文对鞋印匹配方法进行了研究。对于捺印和清晰的鞋印图片使用PSD方法进行匹配，该方法实现简单，人工干预较少。考虑到PSD方法的局限性，针对背景复杂花纹不够清晰的鞋印图片，本文提出了基于Zernike矩的鞋印匹配方法，该方法利用Zernike矩的识别能力和不变性，有效地将不变矩理论应用到鞋印识别领域，与传统的鞋印识别方法相比，适用范围广，可用于包含有任意不规则形状和复杂背景的鞋印识别，且将识别结果对操作者的依赖降到最低。此方法提高了鞋印比对的效率，充分发挥了鞋印在案件侦破工作中的作用。
 
参考文献

[1] G. Alexandre，“Computer Classification of the Shoeprint of Burglar Soles”, Forensic Science International, 1996, vol.82, pp.59-65.
[2] N. Sawyer, “ ‘SHOE FIT’ A computerised shoeprint database”, Institution of Electrical Engineers, UK，May 1995.
[3] Z.Geradts, J. Keijzer, “The image data REBEZO for shoeprint with developments for automatic classification of shoe outsole designs”, Forensic Science International, 1996, Vol. 82, pp21-31.
[4] Philip de Chazal, Richard B.Reilly, “Automated Processing of Shoeprint Images Based on the Fourier Transform for Use in Forensic Science”, IEEE Trans. on Pattern Analysis and Machine Intelligence, 2005, vol. 27,pp. 341-350.
[5] 王东峰，邹谋炎，“傅氏变换的自配准性质及其在纹理识别和图象分割中的应用”，中国图象图形学报，第8卷(A版) ，第2期，140-146页.
[6] Hu M K., “Visual pattern recognition by moment invariants”, IRE Trans on Info Theory, 1962, vol. IT-8, pp179-187.
[7] MR Teague, “Image analysis via the general theory of moments”, Journal of Optical Society of America, 1980, vol.70, pp920-930.
[8] C.H. Teh, R.T. Chin, “On image analysis by the methods of moments”, IEEE Trans. Pattern Analysis and Machine Intelligence, 1988, vol. 10, pp496-513.
[9]A.Khotanzad,Y.h.Hong, “Invariant Image Recognition by Zernike Moments”, IEEE Trans. on Pattern Analysis and Machine Intelligence, May, 1990, vol. 12, pp. 489-498.
[10]Kim, W.S, Kim Y.S, “A region-based shape descriptor using Zernike moments”, Signal Process, Image Commun. 16, 2000, pp95-102.
[11]王耀明，《图像的矩函数——原理、算法及应用》，上海，华东理工大学出版社，2002 .