碎纸片还原问题求解

基于最小二乘法和分治算法的

碎纸片拼接复原

成员：沈旭东张郁哲吴鹏中国石油大学（华东）引言：

破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。碎纸片自动拼接复原技术现今可以归结到计算机视觉和模式识别领域内的问题。引言：

问题的重述：

首先，对于给定的来自同一页单面印刷文字文件的碎纸机破碎中、英文纸片（仅纵切），建立碎纸片拼接复原模型和算法；

其次，在第一问的基础上设计出单面印刷文件既纵切又横切的碎纸片拼接复原模型和算法；

最后，对还有可能出现双面打印文件的既横切又纵切的碎纸片设计出相应的拼接复原模型与算法。问题的分析：

对于碎纸片的拼接问题的解决，我首先想到的是可不可以考虑笔画连续性问题来进行求解，然后我就想到了关于运用函数连续性的证明？但是发现这好像行不通，然后查阅资料知道将照片数字化处理后得到灰度，用0表示黑色，1表示白色，可以考虑运用最小二乘法来进行匹配程度的表达。然后根据贪婪算法思想，每一步都取最优，对于可能会出现的不匹配情况结合人工干预进行调整。

模型的假设及符号说明：1、同一附件中的碎纸片来自于同一页文件，且未缺失；2、文章中同一行汉子均在同一条水平线上，没有倾斜，且字纵向上长度相同（“一”除外），英文字母大小在三条间距相同的横线间，且均占满所在的间隔。3、碎纸片表面光滑平整无磨损且无污点；4、假设破碎纸片边缘完好无缺损。

符号说明

碎纸片经matlab数字化得到1980x72的矩阵，矩阵中的值就是像素，取值在0-1，如图所示其中M=1980，N=1368. 当k=72i-71与k=72i分别对应于第张纸片数字化后所对应矩阵的第一列与最后一列。 令为第i张纸片的最后一列与第s张纸片第一列第行数据的平方欧氏距离，该值为模型准备：问题一：被纵切后碎纸片的拼接复原模型的求解

为了寻找已经确定好位置的第张碎纸片最相匹配的碎纸片,要求确定好位置的第i张碎纸片最后一列与其拼接碎纸片的第一列平方欧氏距离总和最小，数学表达式如下：

借助了贪婪算法的思想。现根据目标函数作最优选择，每做一次贪心选择就将未实现拼接的碎纸片集合。为未匹配碎纸片的集合。集合中碎纸片数量为：n=19-i。模型准备：拼接流程

问题二：被横、纵切后碎纸片的拼接复原模型的建立

（一）碎纸片的层次聚类问题二：被横、纵切后碎纸片的拼接复原模型的建立

（一）碎纸片的层次聚类 一幅黑白照片，它在水平与垂直方向上的亮度变化是连续的，在经过数字化后，即表现为它所对应矩阵的灰度值取值是连续的。进而可以了解到，若两张碎纸片位于复原文件中同几行时，那么其对应矩阵灰度值在纵向上分布近似。经观察测试，原始文档碎片具有下列特点：（1）字体大小：字体的最大高度和最大宽度一致。（2）切割的均匀性：同方向的切割线平行，图片大小均相等，沿纵横方向按直线切割。（3）文字的行距：文字的行间距等同，段落间距为定值。因此可以通过此特点先将图片进行数字化处理放入.xls文件中然后导入SPSS软件进行K型聚类分析（二）碎纸片类内拼接

在经过碎纸片的聚类后，假设将碎纸片分为了m类，第i类所含碎纸片数量为

，i的取值为

1-m。现需对这类碎纸片进行类内拼接。拼接规则借助模型一中碎纸片拼接模型目标函数。将209张碎纸片经matlab数字化后得到209个的矩阵。矩阵中的值，即像素，取值为0-1。其中该值越接近0，则表示该值所对应点的实际颜色越接近黑色；相反该值越接近1，则表示该点的实际颜色越接近白色。 碎纸片经matlab数字化得到1980x72的矩阵，矩阵中的值就是像素，取值在0-1，如图所示其中M=1980，N=1368. 当k=72i-71与k=72i分别对应于第张纸片数字化后所对应矩阵的第一列与最后一列。 令为第i张纸片的最后一列与第s张纸片第一列第行数据的平方欧氏距离，该值为模型准备：

为了寻找已经确定好位置的第张碎纸片最相匹配的碎纸片,要求确定好位置的第i张碎纸片最后一列与其拼接碎纸片的第一列平方欧氏距离总和最小，数学表达式如下：

借助了贪婪算法的思想。现根据目标函数作最优选择，每做一次贪心选择就将未实现拼接的碎纸片集合。为未匹配碎纸片的集合。集合中碎纸片数量为：n=11-i。模型准备：

(三)碎纸片块类间拼接

在经碎纸片聚类后，以及运用matlab编程加人工干预的方法拼接后，得到11块仅横向拼接的碎纸片块。现需对这11块仅横向凭借的碎纸片块进行块间拼接。

该11块仅横向拼接的碎纸片块与问题1中仅被纵向切割的碎纸片类似，根据碎纸片块上下边缘部分内容可将这11块碎纸片分为两种类型，其中第一种类型为上下边缘部分含有部分文字信息，第二种类型为碎纸片块上下边缘无文字全为空白。对于第一种碎纸片块可借助模型1仅纵切碎纸片拼接模型的方法，将该种类碎纸片实现拼接。而对于第二种碎纸片块而言，它相当于上面Ⅱ碎纸片类内拼接中我们所定义的无匹配碎纸片（即在评判条件为碎纸片间灰度值平方欧式距离最短的情况下，该碎纸片有多于1张碎纸片可与之匹配），现无法编程实现拼接过程，故引入人工干预过程。人工干预实现碎纸片拼接的原则为：段间文字的间距为一定值。问题三：被横、纵切后碎纸片的拼接复原模型的求解

我组成员通过研究讨论，认为问题三可被看成两份文件复原的问题，即问题二的叠加问题。通过讨论认为可先将碎片采用与问题二相同的标准进行聚类分析然后采用类内拼接的方法先将碎片平成横向条状，再通过类间的欧氏距离进行纵向拼接模型的评价：优点：

从问题一到问题三、中文到英文由于难度的增加依次将模型进行改进，可认为模型对该类问题有很好的可用性。并且大大的提高了文件复原拼接效率。缺点：