碎纸片的拼接复原
在人们的生活和工作中破碎文件的拼接复原都起着重要作用，但人工拼接的效率低下，为解决此问题，本文基于图像的数字化处理以及碎片文字的边缘特征和行特征，建立以碎片的匹配度为目标的单目标规划模型，实现文字文件碎片的拼接复原。本问题需要考虑横纵两种切碎方式，由于碎片的数量增多，碎片边缘特征相近的情况增多，所以考虑用文字的边缘特征和行特征共同表征文字特征，并将同一行特征的碎片先聚类分解、简化问题，再利用最短路径算法建立各行的最优拼接模型完成11行的横向拼接，最后根据行碎片的横向边缘特征的匹配度以及上下片碎片相对行特征的地推关系完成纵向拼接，实现文件复原。具体结果见正文部分。
【关键词】碎纸版 拼接 数字化处理
1 问题重述
破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。请讨论以下问题：
对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件给出的一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果表达要求同上。
2 问题分析
问题中的碎片考虑横纵两种切碎方式，由于碎片的数量增多且增加了上、下两个边缘，此时单以文字的左右边缘特征的匹配度来确定碎片的拼接顺序容易出错，所以考虑模拟人工拼接过程，不仅考虑碎片的边缘匹配，还考虑碎片的文字行特征，并将横向切与纵向切分层考虑。因为附件中的碎片及文字都是正向水平放置的，同一行碎片上的行间距，字与边界间的距离应当是几乎一致的，所以利用文字的行特征，先将同一行的碎片聚类。利用该行碎片的左、右边缘特征的匹配情况和最短路径算法建立优化模型将该行的碎片拼接，完成11行的横向拼接，最后根据吻合拼接的上片碎片与下片碎片的文字行特征的递推关系完成纵向拼接，实现文件的复原。
3 模型假设
（1）假设一页纸上的字体属性一致，包括字体、颜色、大小；假设一页纸上的字分辨率，亮度一致；
（2）假设切碎时不发生破损；
（3）假设文字图像不含噪声影响；
4 符号说明
（1）：图像数字化处理后的像素点；
（2）图像梯度；
（3）两片碎片的左、右边界的边缘差异度；
（4）两片碎片的上、下边界的边缘差异度；
（5）一片碎片上像素点的行数；
（6）一片碎片上像素点的列数；
（7）一行文字的纵向长及其与上方相邻行的行间距之和；
（8）碎片文字的行特征，即从碎片底部起，第一个纵向完整的行到碎片下边缘的间距；
（9）英文碎片的相对行特征；
（10）覆盖有效点最多的字母中部搜索框的上边界纵坐标；
（11）搜索框纵向长度；
（12）最短路径算法中代表是否经过的0-1矩阵；
（13）两两碎片间的路径矩阵；
5 模型建立与求解
5.1 数字化图像处理
将图像定义为一个二维离散函数，其中是空间坐标，在任意空间坐标上的图像的灰度为。和是有限的，离散的数值，每个点都有特定的位置和灰度，称为像素点 。利用MATLAB的数字图像输入功能建立函数。用数字代替像素点的灰度，另黑色为1，白色为0，以上即可用数字表示
在实际对碎片图像进行处理时，由于图像并不只是黑、白，文字周围还存在灰色部分，所以MATLAB在实际处理时，对黑色像素点取数值255，灰色像素点根据灰度取值254～1，白色像素点取值0。构成图片的数字矩阵。取每张碎片左、右两个边缘纵向上的像素点，作为该碎片的特征点.
5.2 基于文字边缘特征和图像梯度的碎片匹配的最优化模型
5.3 行特征的确定及碎片的聚类
中文文字行特征d ：
从底部起，取第一个纵向完整的行到碎片下边缘的间距为该碎片的行特征，具体为：
当碎片下边缘为文字时， 取两行文字间的行间距（用像素点的个数表示）
当碎片下边缘为空白时，取最下行文字所在行与碎片下边缘的间距（用像素点的个数表示）作为该碎片的文字行特征。
由于附件中的碎片及文字都是正向水平放置的，同一行向的文字的行特征应当是几乎一致的，由此可以按照文字行特征将碎片分类。又因为并不是所有汉字的长度都是一样的，会有少部分同行碎片的行特征存在差异，但差异不会很大，此处根据特征值分布情况取下列行特征聚类，附近值也聚于该类。
原文件是由11×19个碎片组成的，显然有几类不符合，且理论上最大行特征只有68个像素点，所以进一步考虑同行碎片中某些碎片比其他碎片少一行文字的情况。行特征出现超限是因为少了一到两行文字，为了消除不同行的影响，还需将原行特征减去68的整数倍（一行文字及行间距的68个像素点）进行归一化修正。
修正后的行特征，
其中为使能够满足的正整数。
5.4 基于文字行特征与边缘特征的碎片匹配最优化模型
5.4.1 依据文字边缘特征和最优路径算法建立各行拼接的最优化模型
由于附件中文件都被分割为11×19个碎片，而上表英文文件中的部分同类碎片个数为38，说明有两行碎片混在了同一类别中，同问题一，利用碎片间的边缘特征差异和最短路径算法建立优化模型。
建立最短路径的规划模型：
在用以上模型进行自动拼接时，可以找到拼接的最优路径，但由于部分碎片的边缘都是白色，此类特殊碎片会被误连在一起，所以在自动拼接完成后，扫描序列中的碎片，在序列中将这些碎片处的拼接断开，人工将这些片段进行移动拼接。
5.4.2 行碎片的纵向拼接
由2）已知各行文字行特征，通过分析可知：
（1）一行中文文字的纵向长及其与上方相邻行的行间距之和固定为68个像素点。
（2）单张碎片像素为72×180，即单张碎片纵向有180个像素点，一般有两个完整的，第三个被切割分到了下片碎片中，还有部分碎片有一个完整的，其他两个被切割分别分到上、下片碎片中。
（3）吻合拼接的两张碎片中，上片的能够补齐下片缺损的，使得下片有2到3个完整的
则吻合拼接的上、下两片碎片的文字行特征，应满足关系：
下片碎片的文字行特征
其中为满足的正整数。
根据此关系以及2）中各行的行特征，易找到各行的下片行碎片的行特征（由于同行文字的长度也会有微小差别，所以下片行特征的理论值也会有微小差别，此处取与理论值最近的行特征值作为实际值）。
中文文件各行的下片行特征具体如表1。
由上表可以得到一个行特征的循环，可以用上下边缘特征值为0的后者作为拼接段落的开头。中文段落开头行特征为33，由此拼得整个段落。
碎片上、下边界的边缘特征：
利用已成行碎片的上、下边界的边缘特征先对行碎片进行拼接，具体方法同左、右边界的边缘特征，对于边缘特征模糊的行碎片再辅助以行特征的递推关系来确定位置。
6 模型评价及推广
本文利用图像梯度简单有效的给出碎片文字边缘特征的匹配方法，以此建立单目标规划模型，针对仅纵向切碎的破碎文件能够高效的完成复原拼接工作。
对于横、纵切碎的情况，为了弥补由于切片较小且量多导致的边缘特征不明显的情况，增加考虑碎片的行特征，行特征越相似的碎片属于同行的可能性越大。利用聚类分析的思想，先利用行特征分类碎片，再利用最短路径算法完成各行的拼接，最后对11行碎条纵向拼接复原，分层递进的拼接方式，大大减少了不能自动定位的碎片数量，减少了人工的手动干预，使得整个文件的拼接复原更自动化、高效率。
根据本文的思想和模型，还可以推广完成更多，更一般情况的破碎文件复原，如：中英文混合文件，手撕碎片，混合字体文件等的拼接复原。
参考文献
[1]夏良正.数字图像处理[M].南京：东南大学出版社，1999.
[2]罗智中.基于文字特征的文档碎纸片半自动连接（A辑）[J].计算机工程与应用， 2012，48（5）：207-210.
[3]姜启源 谢金星 叶俊 .数学模型（第四版）[M].北京：高等教育出版社，2011（01）.
[4]韩中庚，数学建模方法及其应用[M].北京：高等教育出版社，2005（06）.
作者单位
南京邮电大学 江苏省南京市 210003
