基于MATLAB的证物还原技术的研究

韩海超，曾 英，吴亚玲，粟陶陶，蒋海锋，林 龙

（湖南城市学院 湖南 益阳 413000）

基于MATLAB的证物还原技术的研究

韩海超，曾 英，吴亚玲，粟陶陶，蒋海锋，林 龙

（湖南城市学院 湖南 益阳 413000）

文中提出了借助计算机基于MATLAB编程技术实现破碎文件（碎纸片）的证物复原方法，碎纸片证物的复原技术是图像处理和模式识别等领域一个较新的且非常实用的技术应用。应用技术手段对碎片的颜色，纹理，行距，形状等特征进行扫描和提取，然后通过计算机进行相应的处理，使其在尽可能少的人工干预情况下实现证物的复原。

灰度二值化；最小差值法；聚类分析；canny边缘检测；freeman轮廓提取

破碎文件的拼接复原在修复历史文献、复原司法物证、以及在获取军事情报等领域都有着非常重要的应用。传统上，破碎文件的拼接复原工作都是由人工完成，复原效果好，准确率较高，但效率很低，速度慢。尤其是当碎片数量巨大时，人工拼接就会很困难，短时间内很难完成任务。所以我们将借助计算机复原，虽然计算机复原的准确率不及人工高，但是可以大大减轻工作强度。

比较著名的“东德”事件，1989年12月4日，柏林墙被推倒的一个月后，东德埃尔福特市的一栋政府大楼内有关国家安全部秘密文件被毁掉，把文件撕成碎片塞进1.6万个褐色的麻袋里。之后为还原其证据，大约50名公务员用了8年时间费劲辛苦，将300个袋子里的文件恢复原貌，但是照这样的速度，要处理完余下的文件还得花费450年的时间。由此可见有关证物还原技术的研究是必要的，近些年全世界国家和地区都对其进行了研究，也取得了一定的进展。据报道，曾在2011年10月29日，美国国防部高级研究计划局 （DARPA）宣布了一场碎纸复原挑战赛。2013年9月我国举办的全国大学生数学建模竞赛，其B组题即是对碎纸片的复原，都旨在寻找到高效有效的算法，对处理后的碎纸屑进行复原。

1 问题假设

假设一张完整的碎纸片被分成若干份规则碎片或不规则碎片两种情况：

1）假设碎纸机在碎纸时不对碎纸片造成损坏；

2）假设碎纸片上的字迹清。

2 图像处理与算法

对于碎纸片等一些二维平面物体，可以利用数码相机、摄像机、扫描仪等设备获得碎片影像及部分相关数据。为了计算的效率，凸显目标的轮廓和特征，对图像进行灰度处理，获取图像独有的特征属性。所以图像特征的描述和提取是碎片匹配拼接的关键技术之一。常用的图像特征有纹理特征、颜色特征、边缘轮廓特征等。本文研究根据其规则与非规则图像碎片分别采用基于图像碎片边缘颜色特征和链码边缘轮廓的拼接技术。

本论文结合算法和实际情况，通过计算机技术辅助，大大的提高了工作效率，节约了人力资源。设计的总框图如下图1所示。

对图片进行灰度处理，然后进行二值化处理规定某一个阀值为T，当灰度处理后的像素值大于此阀值时取为1，并将其规定为白色，反之取0，规定其为黑色，得到灰度矩阵并用数学形态的方法消除孤立的点。

图1 总体设计框图Fig.1 The overall design diagram

运用Matlab软件中imread函数将所有图像转化为像素点矩阵形式，imread函数可以把图像以矩阵的形式读出，一般是0～255之间的数值，其中黑色为0，白色为225，这就是象素的灰度值。为了减小数据处理过程中的误差，需将矩阵中大于128的值化取作1，小于的值取作0。得到0-1化的矩阵。

3 图像的拼接

3.1 针对规则形状碎片的图像拼接

针对规则形状碎片，我们再进行基于数字矩阵之间列（或行）距离的图片应用最小差值法拼接复原模型。计算全部图片对应矩阵的列（或行）偏差值，得到所有碎纸片的排列拼接完整图形。

建立目标函数为：

观察图片被切割边缘的灰度值可以得到：被切割图片的两侧的灰度值基本一致，形成两个相似的列矩阵，相似程度越高的两列灰度值其所属的两张图片复原的概率就越大，这就是本文针对规则碎片提出的优先匹配方法最小差值法。

我们可以把图片的最右侧和最左侧的灰度值矩阵全部提取出来，比较其边缘相似度，可以记作Ak（i，1）和Ak（i，n），且对这两列矩阵进行对应行相减取绝对值最后求和，所求得的和越小两矩阵越相似，则图片被复原的概率就越大，即

此时差值求和后最小的图片即为第2张图片。由数学归纳法以此类推，即可求出第3、4、5……n张图片。

在工作和生活当中我们遇到的图形碎片会比较多而且复杂，仅仅依靠图片被切割边缘两侧的灰度矩阵相似度和最小差值法很难快速且完整将图片复原，而面对大量图片，我们需对其进一步优化，运用聚类分析方法进行匹配。依据其字体的大小、高度、宽度，图片切割的均匀性以及文字的行距、段落等同等特征。通过多次类聚分组做出图片其不同特征的类聚图，利用计算机及在较少的人工干预下将所有各类图形进行拼接。

聚类分析：聚类分析（cluster analysis）是一组将研究对象分为相对同质的群组（clusters）的统计分析技术。

可以用di，j表示图片与Xj之间距离，用Di，j表示通过类聚后某类Gi与Gj之间的距离。类Gi与Gj之间的距离最小则最相近，即Di，j=minGi∈Gi，G∫∈G∫，di，j，也可以根据重心距、行间距，段间距，非对角间距等文字特征定义不同的新类。

选取若干图片作为基点，计算每个图片与选取基点的距离，由最小差值法优先匹配，进行最初的分类，然后根据文字的行距特征，文字的行间和段落等最小距离，再进行第二次分类，以此类推重复类聚，如此动态类聚直到所有图片不再调整。此类聚方法分类迅速，占用计算机内存少，特别是当图片数量较大时，也可以根据其他文字特征进行更多的聚类，对图片更好的复原是非常有利的。复原效果图，如图2所示。

3.2 针对非规则形状碎片的图像拼接

针对非规则形状碎片，进行canny边缘检测，因为图像的边缘部分包含着图像的大量信息，图像边缘信息的提取与确定对图像场景的识别与理解提供重要的信息依据，也是图像被分割所存在的重要特征，边缘检测主要是图像的灰度变化的定位、检测和度量。应用canny边缘检测可以获取二值化图像的封闭边界区域。

通过canny边缘检测后我们需对其图像轮廓提取，在这里我们将采用Freeman链码数字图像轮廓提取，由Freeman在1961年提出的，根据二维图像中线条的不同走势方向，用｛0，1，…，7｝8个元素分别表示八邻域像素，由此可以用一串由｛0，1，…，7｝中的元素组成的链码近似的描述一个连续的平面线条图像。如果按圈绕行，则可以由Freeman链码的表示一幅二维图像的轮廓且该链码表示唯一。如图3所示，两个相邻点的连接，如果以一个点为基点，其连接有八种可能方向。每一个方向的连接都是一个向量，我们用Dx=｛D1，D2，D3，D4，D5，D6，D7，D8｝表示。以八个向量方向按“先下后上，先左后右”的顺序对二值化后的图像进行跟踪，每一个封闭的图形都可以用一串数字作为边界曲线链码的表示，该链码唯一确定。以跟踪到的第一个边缘点作为链码的起始点，然后按顺序跟踪搜寻该点四周八个不同方向上是存在边缘点，如果存在，则链码加长，并将该点标记避免重复扫描和匹配，然后，以此方式继续寻找边缘点进行连接直到再也找不出可用边缘点。如图4所示。以A″作为起始点其方向取值为1，按照“先下后上，先左后右”的跟踪原则，首先由A″的“左下”方搜索边缘点，找到A点，其方向取值为4，然后再以A点作为新的起始点在其“左下”方寻找到边缘点P″方向取值为4，因为P″点已经是边缘，其“左下”方已经没有图形边缘可搜索，则向P″点的“右下”方向寻找边缘点，找到边缘点P其方向取值为6，按照此方法不断寻找搜索最后回到A″，最终搜索路径结果为：A″-A-P″-P-B″-B-C″-C-A″方向链码为：1-4-4-6-5-0-2-0-2。我们对8方向链码进行一阶差分作为图像拼接时寻找相似的匹配序列，方向链码一阶差分后序列为：3-0-2-1-5-2-2-2。由于计算量比较大，我们也可以采用更多点的轮廓跟踪，对数据进行优化，可以使跟踪的整体速度得到提高。

图2 规则形状碎片复原效果图Fig.2 The rules of fragments restoring effect chart

对图形边缘轮廓进行数字链码提取后，我们需对图片进行匹配、拼接复原。在这里我们采用一种叫做最长公共子序列的方法，英文缩写为LCS（Longest Common Substring）。其定义为，给定一个序列S，如果该序列分别是两个或多个已知序列的子序列，并且是已知序列的最长公共子序列。通过此方法对一阶方差后的序列进行相似匹配，将拥有最长公共子序列的两张图像进行复原拼接。例如：

图3 Freeman8方向取值Fig.3 The direction of freeman8 value

图4 封闭曲线起始点链接Fig.4 The starting point of the curve closed link

差分序列X=［1，2，3，4，5，6］，Y=［0，1，2，4，5，］；已知序列S=［1，2，4，5］和Z=［2，4，5］，则S和Z序列都是X与Y的子序列，而S为最长公共子序列，因此说差分链码X和Y序列是相似的，所以我们将两个链码序列所属的图片进行拼接，以此类推，直到找到所有相似链码，在基于二维坐标系的旋转平移变换将图片拼接复原。且其图像轮廓曲线特征表示必须是旋转和平移不变（刚体变换）。其复原效果图如图5所示。

图5 非规则形状碎片复原效果图Fig.5 Irregular fragments restoring effect chart

4 结束语

本文对计算机图像处理领域进行了探究，旨寻找高效，快捷的图片拼接方法，从而实现证物的还原。本文方法可以摆脱以往的繁琐的，大量的工作，实现简单，可靠性强，通过计算机和信息手段完成一些很难完成的工作。

［1］罗智中.基于线段扫描的碎纸片边界检测算法研究［J］.仪器仪表学报，2011，32（2）:289-294.

［2］李利军，李云伟.基于图像灰度的拼接技术研究［J］.计算机与数字工程，2007，35（9）:128-130.

［3］贾海燕，朱良家，周宗潭，等.一种碎纸自动拼接中的形状匹配方法［J］.计算机仿真，2006，11:180-183.

［4］zhx19870705，聚类分析［EB/OL］http://wenku.baidu.com/view/ 02e3d-7c8050876323112125f.html.

［5］于万波.基于MATLAB的图像处理［M］.北京：清华大学出版社，2011.

［6］姚文君.基于freeman链码二维图像轮廓提取与匹配［J］.宁波技术学院学报，2006（5）:24-26.

［7］朱延娟，周来水，刘毅.二维非规则碎片匹配的算法［J］.计算机工程，2007，24（12）:7-9.

［8］潘荣江，孟祥旭，屠长河.一种基于LCS的物体图像碎片自动拼接方法.计算机学报，2005，28（3）:350-356.

［9］姜启源.数学建模（第三版）［M］.北京:高等教育出版社，2003.

［10］参加2013全国大学生数学建模竞赛，B组题.

［11］周晓明，马秋禾，肖蓉，等.一种改进的Canny算子边缘检测算法［J］.测绘工程，2008，17（2）:28-31.

Research on MATLAB reduction technology based on evidence

HAN Hai-chao，ZENG Ying，WU Ya-ling，SU Tao-tao，JIANG Hai-feng，LIN Long
（Hunan City University，Yiyang 413000，China）

This paper proposed by the aid of computer implementation of broken file based on the MATLAB programming technology（scraps）restoration method exhibits，scraps of paper evidence recovery technology is a new and very practical technology application field of image processing and pattern recognition.Application of technical means on pieces of color，texture，line spacing，scanning and extraction of shape feature，then the corresponding processing by computer，realize its evidence recovery in the artificial intervention as little as possible under the circumstances.

the gray value of the two；the minimum difference method；cluster analysis；canny edge detection；freeman contour extraction

TP99

A

1674－6236（2016）04-0186-04

2015-04-02 稿件编号：201504023

韩海超（1992—），男，内蒙古赤峰人。研究方向：电子信息与通信工程。