规则边缘的碎纸片拼接模型及软件开发王攀攀

朱晨杰　刘婷　余嘉宾　胡振旭　蒋素琼　何湘威

【摘 要】本文从数学模型的角度出发，对规则边缘的碎纸片拼接问题的行间拼接和分行聚类两个核心步骤进行了解决方案的描述。在行间拼接阶段具体建立了基于贪心算法的最优二叉树拼接模型和基于全局优化的TSP拼接模型；在分行聚类阶段则针对中文和英文不同的规则给出了基于空白信息特征和基于极值搜索的聚类模型。最后本文还对对应的拼接模型在MATLAB中GUI交互界面开发拼接软件的功能进行了具体的描述。

【关键词】最优二叉树拼接；TSP拼接；空白信息特征；极值搜索；拼接软件

【Abstract】From the angle of mathematical model， this paper described the two key steps of joining of regular edge paper piece， that is joining inside the row and clustering between rows.We established the optimal binary tree based on greedy algorithm and TSP model based on global optimization in the stage of former，and obtained Chinese and English piece cluster model based on the blank information features and extremum search respectively.In the end， the paper also describes the function of the corresponding join software in GUI interface of MATLAB.

【Key words】Optimal binary tree join； TSP join； Blank information features； Extreme search； Join software

0 前言

在公安的刑侦工作中，经常有破碎的证物需要被拼接还原，如碎纸片文字或图像等。这项工作若依赖于人力，是十分费时费力的，因此找到一种机器方法对这些碎片进行自动高效拼接是十分必要的。

国内外已有的计算机自动拼接软件或算法主要建立在边缘形状和图像信息的匹配上，这些算法对于拼接边缘形状不规则及图像信息较丰富的对象是比较有效的，但是对于经现代碎纸机处理的规则边缘形状打印纸片则识别度非常低。本文旨在建立数学模型对现代打印的规则大小的碎纸片的拼接过程进行科学的描述，以提高刑侦领域的工作效率。

1 拼接模型的建立

当然，近几年国内对此类问题的研究成果颇多，但都侧重于不同算法的正确率比较。而文本将重点描述该规则纸片拼接问题的数学模型建立及有针对性的分别给出中文、英文具体拼接函数。

在拼接前，我们利用MATLABA读取图片的像素信息，并考虑到提高算法的效率，对碎片的灰度矩阵进行二值化（1代表白色0代表黑色），得到相应的0-1矩阵数据。

1.1 行间排序的数学模型

本文从优化的角度，按贪心算法和全局优化依次给出两种模型来描述行间如何排序。

1.1.1 基于贪心算法的最优二叉树拼接模型

最优二叉树——表示对于一组带有确定权值的叶结点，构造的具有最小带权路径长度的二叉树（示意图见表1）。

基本思路：

Step1：将每张碎片视为一片叶子，两碎片间的贴合度视为合并树叶的指标。由给定的n个碎片组成集合F；

Step2：计算F中各碎片间两两贴合度矩阵A在A中选取最大贴合度所在的对应的碎片编号left、right，构造一棵新的二叉树，将两碎片拼接而成的新图片看做一个新的节点；

Step3：在集合F中删除碎片left、right，并将新建立的碎片树xin加入到集合F中；

Step4：重复Step2、Step3两步，当F中只剩下一个节点，即一张拼接图片时，这张即为拼接的结果。

1.1.2 基于全局优化的TSP拼接模型

记G=（V，E）为赋权图，V={v1，v2…vm}为碎片的顶点集，E=dijvi，vj∈V为各条碎片顶点相互连接组成的边集，此处即为各条碎片两两拼接的集合。每条边都存在与之相对应的权值，即相邻碎片拼接时的贴合度为dij，可构成n×n阶的矩阵，dij>0，dij=+∞，i，j∈V，并设

其中，i，j表示碎片编号；m表示碎片个数；S表示图G的碎片顶点的个数；基于以上分析，可建立碎片拼接优化模型，并直接应用Lingo或Matlab软件即可求解。

1.1.3 两种模型的比较分析

这两种模型都是基于对同一行的碎纸片的优化拼接，但前者是基于贪心思想的Huffman算法是一种局部优化，相比下应用旅行商问题的TSP规划算法则是一种全局优化。二者的收敛性和复杂度分析都具有良好的理论基础，能对拼接过程进行清晰而准确的数学描述，而不仅仅是一种算法的流程。

1.2 行聚类数学模型

在复杂的碎纸机形成的碎片中存在着既横切又纵切的情况，此时就需要先对碎片进行正确的分行，再应用前文的行间排序模型进行拼接。下面我们会根据中文和英文不同的特征采用两种模型来实现高效的行聚类。

1.2.1 基于空白特征信息的舍去及拆分的中文碎片行聚类模型

我们知道，如汉字“一”等字高明显偏短的汉字与标点符号“，。”和汉字“吉”中间有非常短的空白导致一个汉字的特征信息被分成两部分“士”与“口”等。所以接下来我们对提取到的图片信息进行预处理工作。

Step1：对于空白我们采取当空白小于12像素则忽略；

Step2：将被分割的汉字的特征信息进行了拼接处理，如“吉”字，他不再被记录成两部分信息而是一个整体，基于图片的分析，我们可得到正常汉字高为40并结合误差考虑所以我们将舍去黑像素高度小于25的特征信息（上述12、40及25都是一个指标，可以根据具体数据调试出合适的值）。

Step3：拆分的依据则主要是检测空白部分是否大于正常标准（通过对图片的分析我们可得知标准行间距约为30个像素）并规定如果大于32个像素则拆分（这里考虑到误差所以比标准行间距大2个像素）。

Step4：对上步得到的图片特征信息进行聚类。可按照将左、右边缘的图片作为该行的标准特征信息进行分行聚类，也可先将左右边缘的图片进行匹配，并合并相同行的特征信息，从而得到更精确的行的特征信息，再依据这个精确的行特征信息进行聚类。

1.2.2 基于极值搜索的英文碎片行聚类模型

如果要处理的是英文碎片，我们可知英文与中文字体提取特征信息的最大区别是在于中文字体大部分是方块形而英文是基于四线三格的印刷体，字高不定，因此中文碎片的行聚类模型并不适用于此。但是印刷体的四线三格的位置是一定的，所以我们可以根据图片的整体信息如上一行与下一行的相对位置和本行的文字特征结合起来确定四线三格的位置从而提取英文图片的特征信息。

对于英文图片我们依据上述将图片读入并二值化的图片数值化信息矩阵，统计每一行的白色像素点的个数，并将其从图相中描绘出来，如下所示（以第一张英文图片为例）。

从上面的趋势图中易知start1，end1与start2，end2两对点分别为原图中两行英文字的四线中的中间两根线，因为白色像素点最少，反映到图中便是曲线极速降低，故我们建立此曲线的极值搜索模型来确定四线的位置。

Step1：搜索所有的极小值。判断依据为p（x）<=p（x-1）且p（x）

Step2：然后在每个片段中找出相距为15-25之间的极小值点对，如果该片段中只有一组点对，则该点对即为我们要找的改行的标志对。如果该片段中多于一组点对符合条件我们则从中筛选出黑色像素聚集最多的点对成为该片段的标志对，数值体现为相加之和最小。

Step3：将上步得到的每个碎片的四线特征结合全局的角度调整误差，即可进行分行聚类。

2 在MATLAB软件GUI交互界面开发拼接软件

为提高用户体验，我们利用MATLAB实现GUI交互界面，旨在解决复杂的算法逻辑与简单快捷的使用之间的矛盾。现从以下几个模块分别阐述：

一键导入功能：只要将待排序的碎片扫描图放入一个文件夹内，即可按该导入按钮，找到文件夹的路径，将碎片导入到软件后台。

图片信息类型选择功能：不同的图片，对应的信息特征也不同，如中文字体和英文字体的拼接特征点不同，通过图片信息类型选择功能，可大大提高算法的效率，让本软件有针对性地采取相应的措施，对症下药。

算法选择功能：当碎片信息成功导入到后台，用户可自由选择拼接的算法，当然我们提供了一个默认算法，并针对相应的碎片信息智能计算出最优方案。

一键导出功能：将拼接好的图片按照用户指定的格式等信息导出到用户指定的位置方便用户对拼接结果的存储。

人工干预功能：当碎纸片拼接完成后，某些部位出现严重的偏差，人眼可直接看出时，我们提供人工干预的功能。只要用鼠标左击相应位置，并拖动图片到适当位置即可。大大提高了碎纸片拼接的精确度。

3 结语

本文从数学模型的角度出发，对规则边缘的碎纸片拼接问题的行间拼接和分行聚类两个核心步骤进行了有针对性的解决方案的描述，并对其应用功能的实现作了初步的实践说明。在碎片拼接的理论上是对规则边缘类别拼接的数学描述的空白补充，在拼接实践上也提供了一个可行简便的平台来实现该理论，未来就是在如何改进算法正确率及提高交互界面用户体验上进行进一步的探索。

【参考文献】

[1]Kenneth H.Rosen.离散数学及其应用[M].北京：机械工业出版社，2015，1.

[2]刘浩，韩晶.MATLAB R2014a完全自学一本通[M].电子工业出版社，2015，1.

[责任编辑：王楠]