碎纸片还原问题求解

纸片的拼接复原

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

问题的重述：首先，对于给定的来自同一页单面印刷文字文件的碎纸机破碎中、英文纸片〔仅纵切〕，建立碎纸片拼接复原模型和算法；其次，在第一问的根底上设计出单面印刷文件既纵切又横切的碎纸片拼接复原模型和算法；最后，对还有可能出现双面打印文件的既横切又纵切的碎纸片设计出相应的拼接复原模型与算法。

问题的分析：

本文运用碎纸片的自动拼接技术，对每个附件给出的碎片文字材料进行分析，获取图片所提供的像素信息，将其转化为矩阵，根据图像的像素矩阵值进行碎片拼接，用计算机去处理数据，拼接时不但考虑碎片边缘是否匹配，还要判断碎片内的字迹断线和文字内容是否匹配，此时需要在必要的时候进行一定的人工干预。

模型的假设及符号说明：1、假设碎纸机把一页印刷文字文件碎成形状规那么，大小一样的碎片，看做形状、大小相同的长方形.2、在碎纸过程中，只考虑文字被切开，不考虑文字笔画的丧失、碎片添加的任何痕迹等.3、假设文档碎片的文字的方向已经确定〔按照阅读标准确定，从左向左右，自上而下〕，不考虑碎片图像的旋转问题.4、图片在复原的过程中，不考虑图片像素的改变，只考虑碎片相对应的固定像素值的匹配问题.

符号说明

————相对应的像素绝对差值

——像素矩阵的像素值

————第i个碎片最后一列与第j个碎片第一列的图像矩阵值

和的差的绝对值

S,T分别代表图像各个像素的灰度值，i,j

代表各个像素的坐标

基于图像灰度的拼接方法简单简单易行，本文用差和法，其中分别代表图像各个像素的灰度值，代表各个像素的坐标.其值最小者所对应的位置为最正确的匹配位置.这里我们定义对应像素的灰度的绝对值之差然后求和，其计算文字图片像素与和所搜索的文字图片像素灰度值的距离：模型准备：模型建立与求解：

问题1的模型与求解：

步骤1确定像素矩阵

运用Matlab程序分别对附件1和附件2中所给出的19张

碎片图像进行像素矩阵计算，每个图都对应得到一个1980*72的像素矩阵.

步骤2确定左边第一列碎片通过Matlab程序筛选出每个像素矩阵的第一列像素值，运用Excel软件统计各列像素值等于255的个数.运算的结果如以下图：图1附件1碎片最左边像素为255的个数步骤3确定碎片顺序对于此题中出现的形状、大小一样的相邻两块碎片拼接，只需考虑两块碎片灰度的绝对差值.因此可运Matlab程序建立以下模型：对于待匹配的图像，像素矩阵像素的像素值，表示行数，为列数，其连接区域的相似度可由相对应的像素灰度绝对差值来衡量，即计算第1张图片的图像矩阵的最后一列的像素值与待匹配图片的图像矩阵的第一列的像素值的绝对差值的总和，计算公式如下：

下面先对附件1进行讨论，可通过Matlab程序进行计算得到它们相对应的像素差的绝对值，如下表的结果：表1附件1碎片008与其他碎片的相素差的绝对值表

附件1的拼接复原文件，拼接顺序如下表所示：

表2附件1文件的拼接顺序同理得到附件2的拼接复原文件，拼接顺序如下表所示：

表4附件2文件的复原拼接结果问题2的模型建立及求解

问题2拼接时要满足横向和纵向匹配，分两步进行，首先考虑横向拼接，运用Matlab程序对附件3给出的209个碎片图像进行像素矩阵计算，每个图像得到一个180*72的矩阵，刷选出209个碎片图像中每个像素矩阵的第一列像素矩阵和最后一列像素矩阵，即2个180*1的像素矩阵.然后对得到209个第一列像素矩阵和最后一列像素矩阵进行列求和.把上述的求和结果转换成一个209*209的矩阵：其中第i个碎片最后一列图像矩阵值和与第j个碎片第一列的图像矩阵值和的差的绝对值为矩阵中的元素(I,j=1,2….209)，比较筛选出矩阵中的第i行所有元素的最小的一个，那么说明第j个碎片的左边与第i个碎片的右边相匹配，这样就完成了附件3的横向拼接顺序，得到11个新的横条碎片.进行纵向拼接，对得到的所有新的横条碎片进行像素矩阵计算，用Excel软件统计各个新横条的像素矩阵中第一行数据中255的个数，得到个数最多的碎片是纵向拼接顺序的第一个.局部行拼接结果如下图图2附件3横向拼接复原图〔1〕图3附件3横向拼接复原图〔2〕

最后，由于只有11个横条，并且根据汉字的笔画特征，本文采取用人工干预的方式，对11个横条进行干预，逐一确定，最终得到到附件3的拼接复原结果：表5附件3局部拼接复原结果

问题三的求解：

用求绝对差的算法匹配点对，后期运用欧式距离进行检验匹配度.

步骤一

运用Matlab程序对418个碎片图像进行像素矩阵转换计算，得到418个180

*72的矩阵，提取所得每个像素矩阵的第一列像素矩阵和最后一列像素矩阵，即均为180*1的像素矩阵.

步骤二

对得到418个第一列像素矩阵和最后一列像素矩阵分别进行列求和，然后分别存放在矩阵D和Dt中，接下来用Dt的每一项依次减去D的每一项之后并求绝对值，得到一个矩阵M.

步骤三用matlab程序可以算出每一行〔列〕的最小值，并且反响出最小值所在的行数，此时认为左右像素矩阵的距离最小即为匹配度较高的左右相邻碎纸片.这样可以粗略得到关于文字行的关系，比较后初步得出局部用于拼接复原文件其中一面的180张碎纸片.运算结果局部如下表：

步骤四对418个碎片像素矩阵的第一列的白色边缘像素值255进行统计，然后统计分析各个图像的白色边缘区域大小，匹配出位于行首和行末的碎纸片.但是由于计算结果存在误差，此时需要通过人工干预进行区分判断，将筛选出的左右相邻碎纸片，运用行距分类以及组词成句的方法干预拼接成一碎片横条.例如其中的一行的排列结果如以下图4、图5所示：步骤五通过上述步骤，初步拼接出11个碎片横条，输出成图片，然后用Matlab读取这11张图的像素矩阵，运用同样的思路分析配准像素矩阵的第一行与最后一行，匹配度较高的应为相邻行，进而得出最终复原图像，局部排列顺序如下表所示：模型的评价：优点：从问题一到问题三、中文到英文由于难度的增加依次将模型进行改进，给出了严谨的说明过程，可认为模型对该类问题有很好的可用性。模型说明拼接过程中不需要人工干预是不可能的。缺点：本文对每张图片计算其像素矩阵值，计算量大，实时性不高.编程的不理想导致算法的图片匹配精确度不高和鲁莽性差，同时由于使用了冗余的代码使得执行速度偏低题目提供的附件碎纸片图都是均匀的横切或纵切，本文设计的模型与算法没有能够解决对于倾斜或选择的图片处理问题，拼接后导致的图像形变问题也没有涉及.模型的改进与推广：

为了增加系统的实时性、减少运行时间，可考虑两种根本思路是减少计算量或者提高计算机资源利用率.在编程过程中尽量考虑调用、循环语句，尽量防止冗余的代码，减少运行时间。