基于图像处理的碎纸片拼接数学模型分析
1.问题背景
目前碎纸的拼接工作大部分是靠人工的方式完成，但是当碎纸片的数量巨大的时候，要人工拼接完成就很困难了。国内对此技术的研究主要是集中于文物碎片的自动修复、虚拟考古、故障分析以及计算机辅助设计、医学分析等领域，除此之外，破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域也有只重要的应用。
常规的碎纸片拼接方法一般是基于碎纸片的边缘的形状特征比如尖点、尖角、面积等几何特征，再进行搜索与之相匹配的纸片从而完成拼接。但是这种基于纸片边缘几何特征的拼接方法，当存在许多边缘几何特征相似的纸片的情况下，这种拼接方法就不适用了，因此，本文重在建立一种基于纸片中文字特征的模型来完成碎纸片的拼接。
2.问题分析
碎纸片自动拼接技术是图象处理与模式识别领域中的一个较新但是很典型的应用，它是通过计算机扫描和图像提取技术获取一组碎纸片的形状、颜色、文字特征等信息，然后利用计算机进行相应的处理从而实现对这些纸片自动和半自动的拼接还原。碎纸片自动拼接技术的关键包括图像的预处理和匹配，其中预处理的目的是把碎纸片表示为适合于利用计算机处理的形式。预处理包括图像的获取和处理，对于边界特征明显的纸片可以进行边界检测，轮廓提取和表示。而纸片的匹配技术是碎纸自动拼接中关键之关键，即利用建立好的模型并设计出算法对纸片进行特征识别和自动拼接。
问题中的碎纸片由于具有同样的边缘几何特征，因此不能采用常规的靠提取碎片边缘尖点、尖角以及面积的方式来对不同的碎片进行区分。对于这类边缘相似的碎纸片拼接，理想的计算机拼接过程应与人工拼接过程类似，及拼接时不但要考虑待拼接碎纸片边缘是否匹配，还要判断碎片内的字迹断线或碎片内的文字内容是否匹配，然而由于理论和技术的限制，让计算机具备类似人那种识别碎片边缘的字迹断线、以及理解碎片内文字图像含义的智能几乎不太可能。但是，利用现有的技术，完全可以获取碎纸片内部及边缘的文字几何特征以及纸片不同部分的颜色等信息，在自动拼接时，只要寻找到具有相同边缘特征的纸片即可。因此，解决问题的关键是设计出合适的匹配算法和进行误差控制。
另一方面由于计算机数字分析图像能力的缺陷，让计算机对碎片进行完全意义上的自动化拼接是几乎不太可能的，为保证拼接的准确性，还需要在拼接过程中加入人工干扰过程。
3.模型综述
在碎纸片进行拼接之前我们要做的就是讲碎纸片使用扫描仪对纸质文档碎片进行处理，并输出BMP格式的原始图像。模型中我们先假设不存在边缘具有一模一样的文字特征的两张纸片，再对待拼接的碎纸片进行图像处理即二值化，转化为只含有0和1的矩阵，最后通过算法进行匹配找到对应的纸片。对于边缘相似的碎纸片的拼接，理想的计算机拼接过程不但要考虑拼接碎纸片边缘是否匹配，还要判断碎纸片内的字迹断线或碎片内的文字内容是否匹配，然而，由于理论和技术的限制，计算机要具备这样的人工智能还是很困难的，因此，还必须在相应的时间节点处加入人工干预。
4.假设条件
（1）假设不存在四个边界几何特征都一样的两张纸片。
（2）假设碎纸片当中只存在黑白两种颜色。
（3）假设正确拼接完成后的完整纸张的边界是全白的，即没有文字被切割。
（4）假设纸张内的文字行是平行且单一的。
（5）假设纸片内同一文字行的高度、间距是相等的。
5.模型的建立
二值图像是指每个像素不是黑就是白，其灰度值没有中间过渡的图像。二值图像一般用来描述文字或者图形，其优点是占用空间少，缺点是，当表示人物，风景的图像时，二值图像只能描述其轮廓，不能描述细节。这时候要用更高的灰度级。
二值图像中所有的像素只能从 0 和 1 这两个值中取，因此在 MATLAB 中，二值图像用 一个由 0 和 1 组成的二维矩阵表示。这两个可取的值分别对应于关闭和打开，关闭 表征该像素处于背景，而打开表征该像素处于前景。以这种方式来操作图像可以更容易识别出图像的结构特征。
建立将图片转化为二值化理想模型，方便进行数值处理。
在碎纸片拼接中，通过计算一张纸片边缘一列的向量，与另一张纸片最边缘一列的向量，比较相似度的大小，找出边缘最相似的矩阵进行拼接。同时，假设纸张内的文字行是平行且单一的，纸片内同一文字行的高度、间距是相等的，所以同一行碎纸片的上下空白高度具有类似的特征。
6.算法设计
（1）将每张图片先转化为矩阵，信息储存在矩阵中，再进行二值化处理，将每张图的信息储存在一个二维数组w（x，y）中。
（2）求出每张图字符距离上下边缘的距离，存在两个数组cal_up与cal_down中。
（3）先筛选出最左边或者最右边的可能图片，利用人工干预进行调整，排列出图片的第一列和最后一列，记录下正确的排序。
（4）从第一列的第一张图片开始向后拼接，求边缘相减的最小值，进行筛选，直至最后第一列的最后一张图片。最后检查图片是否正确，记录下正确的排序。
（5）从最后列的第一张图片开始向前拼接，直至最后第一列的最后一张图片，利用相同的算法，检查图片是否正确，记录下正确的排序。
（6）对于仍然缺失的图片进行人工干预，最终补充完全。
7.结论
本文所提出的基于碎纸片边界特征的拼接方法，巧妙利用图像处理技术，使问题分析更加明显，简化，便于计算。对于大量的图片，具有结合人工干预，效率较高。分析表明，当碎片总数量较少时，拼接计算工作量在允许范围内，如果对算法作些改进，拼接计算量可大幅度减少。 [科]
