数学建模B题论文-碎纸片的拼接复原模型.doc

碎纸片的拼接复原模型摘要 本文主要问题是将附件中的所给的碎纸片按照一定的方法拼接复原。通过一定的方法把碎纸片进行分组：题目给了四种类型的碎片，有长条形的，即全是竖切的中英文碎片，也有横竖都切的中文碎片，有横竖都切的单面英文碎片和横竖都切的双面英文碎片。对于中英文长碎纸片分组拼接的问题，我们直接通过观察法，按照文字和字母的结构很容易完成了拼接。对与中文横竖碎纸片拼接的问题，我们利用Matlab编程并加入人工干预。本文的主要拼接过程都是通过Matlab软件实现的，通过Matlab软件读取图片的信息，根据图像灰度的原理，图片包含着灰度信息，碎纸片左右的文字在纵切面上的灰度应该是完全对应的。但把所有图片的灰度拿出来匹配是很不现实的。于是我们想到可以通过灰度赋值，由于碎片中间文字的信息对于拼接是没有太大用途的，我们更关心左右切面的文字信息，即灰度信息。因此将纵切面上的灰度矩阵的第一列和最后一列单独抽出，形成矩阵，然后设定一定的算法，通过Matlab进行编程，相邻的两张碎纸片左右边缘信息匹配度非常高，其差值接近于0。编写的程序完全可以对所分的各组碎纸片进行拼接，而且效果非常明显。对于英文碎纸片问题，我们采用了同样方法的分组，只是按照上下切掉的英文部分所占四线格的比例进行分组，此分组方法分组快且相对准确。我们第二问中所编程序对英文碎纸片的拼接也完全适用。对于双面英文的情况，也是按照上述思想方法进行分组，只是工作量稍微大些。分组后我们也通过所编程序实现了双面英文的拼接复原。关键词：碎纸片；拼接；图像灰度；灰度矩阵；分组1、 问题重述 论题给出了5个附件反应了几种不同纸片破碎的情况，要求我们构建相应的碎纸片复原模型，以解决实际生活中出现的需要我们进行碎纸片复原的问题。首先进行简单情况的碎纸片复原，即附件1中和附件2中的仅纵切的中英文19个碎纸片。构建一个可以操作的拼接模型，将附件中的纵切纸片拼接。接着针对复杂的情况纸片拼接复原，构建一个简便的拼接模型将附件3和附件4中的横纵交切的208个碎纸片拼接复原。最后针对更一般的情况，利用改进的复原模型处理双面的纵横交接的碎纸片。2问题分析 碎片的拼接复原，通常的做法是人工识别碎片边缘的字迹断线、和理解碎片内文字含义，这样利用人工智能的方法虽然准确度高，但是当碎片的数量很大时，人工的效率就显得低，而且出错率会明显提高；而计算机拼接与复原图像，虽不及人工识别智能，但能充分发挥其运算量大，运算速度快的特点。 故本问题的目标就是利用附件中给的碎片数据，分单页纵切，单页横纵切，双页打印横纵切三种情况，把拼接复原问题抽象成一个明确完整的数学模型，利用计算机，并加以人工干预，复原出原图表。首先应当明确，本论题所给的碎纸片都来自同一张纸，所以下面的问题分析都是针对来自同一张纸的碎片复原问题，并且建立的逻辑以及构造的复原模型都是只针对这一特殊情况。更复杂的情况会在文章后面的模型评价里做简单的阐述，本文基于本题目问题的考虑就不做具体的分析了。2.1 仅纵切的单面碎纸片拼接复原分析问题一要求仅考虑单面纵切，建立来自同一页印刷文字文件的碎纸机破碎的纵切纸片拼接复原模型和算法。通过对附件1和附件2 给出的碎片数据图的观察，发现本题的碎片图像具有相对文字（汉字、英文）方向纵向规则剪开的特征，所以不适合基于碎片的边缘线建模，也不适合基于两幅图片的重合度建模。我们知道，这19个纸条来自同一个整体，必然反映整体的信息，而且这19个碎纸条又是从同一张纸被切开，所以它们之间也存在联系,同一个纸条，其左右边缘所反映的信息与其邻近的纸条高度匹配，我们可以根据打印文件的每行文件具有前后连续性，考虑先从读取文件数据入手，存储每幅图片对应的灰度值矩阵。依靠得到的灰度值矩阵，并利用相邻接左右边界差异不大这一特性作为依据来建立左右边界匹配模型，利用matlab编程来解决此问题，复原出图片的原始序列。2.2 纵横切的单面碎纸片拼接复原分析附件3和附件4给出了209个碎纸片，此题加入了横向切割，使得切割方式更加多样化和更接近实际。它相对于第一问而言，图片的信息量更小，图片的个数增多了一倍。图片总体不仅在纵向具有无序性，而且在横向也具有无序性。若仅采用问题一中的方法，定位约束太少，每个纸片对整个页面的信息承载量非常少，而每一张纸片可能有四个切口，所以可能会出现一个图片与多个图片最小差异度相等，导致该图片与多个图片相联系，纸片间的联系更加凸显，进一步模糊了碎片包含的页面信息，从而增加问题求解的难度。通过观察图片的平行切割特点，发现来自原文件同一行的文字切割后的图片一般在相同的行位置上。所以可以考虑，先进行行位置筛选，通过构建图片的特征列向量作为唯一标识，建立特征匹配模型，得到具有相同行特征的图片，聚成同一类。考虑到每类包含的图片个数不一致，可加入人工干预，对类的个数降维，使得行集合包含的碎片个数一致。而利用左右边界匹配模型可以确定同一行的图片的序列；可采用相同的原理，建立上下边界匹配模型来解决纵向图片的定序问题。这样一来，可以拼接出本问的原文件，完成问题二的求解。2.3 纵横切的双面碎纸片复原分析问题三在前两问的基础上，加入了双面打印这一条件。本问中图片的个数相较于问题二增大了一倍，附件5给出了个双面掺杂的碎纸片，较前两问复杂度更高，而且图片承载的有用信息则更加的小。由于从单面看问题二和问题三没有任何区别，所以可以采取相似的方法对问题三求解。但我们思考总结出如下两方面：一方面不能思维定势，也就是说所有编号中带有 a的图不一定都来自同一面，即有可能是碎纸片的正面也有可能是碎纸片的反面。另一方面如果采用问题二中相同的处理方法对附件5中所有的图片排序的话，可能会发生一个图片的匹配图片过多，或者出现将一个碎纸片的正反面归为同一类的错误。综合以上两方面的思考，但我们应该看到问题的实质，同一张碎纸片上的英文正反面字母切割的比例是完全相同的，我们在对问题三建立模型的时候，将双面打印的英文文档转化成两页不同的碎片进行各自拼接。问题三的求解过程的特点在于：先对一张碎纸片构建其对应的特征匹配模型，若得到另外一张碎纸片与这张碎纸片匹配，则随后对它们的反面进行匹配以检验，如若匹配不上，则加上人工干预的方法，对碎纸片进行拼接，直至最后得出完整的图片。思维导图3模型的假设 为了使得复杂的现实问题变得更容易处理，我们从现实中抽出了一些特殊的情况。所以我们给出如下模型合理性的假设：【1】假设碎纸片上的切口是横平竖直的（碎纸机的结果）；【2】假设碎纸片上的文字书写完整规范且正确；【3】假设附件所给碎纸片中不包含不属于该页纸的碎纸片；【4】假设正反两面的英文是按相同位置打印的，即切过以后正反两面所在的行是相同的，所切的字母也是同样比例的。【5】所有碎片中的文字颜色一致，且与背景颜色有较大反差。【6】所有碎片中的文字是从左至右、从上至下书写的。4 符号说明1、：表示第i张图片转化得到的灰度矩阵；2、：表示第i个图片灰度矩阵第m行n列对应的灰度值；3、：表示第i个图片灰度矩阵的第j列；符号符号意义第i张图片转化得到的灰度矩阵第i个图片灰度矩阵第m行n列对应的灰度值第i个图片灰度矩阵的第j列第j个图和第k个图之间的吻合参数（其含义在模型分析中说明），其中两张图片的吻合参数越小表示这两图吻合度越高4、 ：表示第j个图和第k个图之间的吻合参数（其含义在模型分析中说明），其中两张图片的吻合参数越小表示这两图吻合度越高；5 模型的建立与求解5.1 问题一5.1.1模型建立 基于假设5，我们可以先利用Matlab读取图片的灰度矩阵，图像经过数字化处理后，图像信息简化为像素矩阵，图片的匹配问题可以转化为图片边缘像素列的匹配问题。若两张图片可以匹配，则其拼接缝上各点的像素值会非常接近，其差值接近0。 当在接缝处两张图片的像素列匹配达到最优时，则可以将这两张图片拼接在一起。选取一张图片为基础，选取左右两端像素值最接近的图片与基准图片进行匹配，重复上述过程直至将所有图片拼接完毕。5.1.2 基于贪婪算法的纵切模型一的算法设计与求解（1）贪婪算法简介 当一个问题的状态空间很大时，穷举法计算量可能会太大，而贪婪算法的思想则是采取目前看来最接近解状态的选择方案，它是一种不追求最优解，只希望得到较为满意解的方法。贪婪算法常以当前情况为基础作最优选择，而不考虑各种可能的整体情况，贪婪算法采用逐步构造最优解的方法，一般贪婪算法将构造可行解的工作分阶段来完成，在每个阶段，选择那些在一定的标准下是局部最优的方案，期望各阶段的局部最优的选择带来整体最优，但更多的情况下，可能只是近似解，做出贪婪决策的依据为贪婪准则，而贪婪准则是实际环境中人民所采用的规则，也称为启发式方法。（2）贪婪算法步骤STEP1：确定要拼接的图片个数。STEP2：读取所有图片的灰度值，将图片数字化。STEP3：确定第一张图片，再依次确定与其相邻的下一张。 利用Matlab软件可以实现上述操作，程序见附录7。5.1.3 纵切碎纸片拼接复原模型一的实例验证1、中文碎纸片的拼接复原 附件1中所给的图片为扫描原纸张碎片后得到的BMP格式的图片，图片像素均为，使用matlab中的imread函数可以做出图片的灰度矩阵，举例如下（由于该像素图片转换后为的矩阵，论文中无法放置，所以仅简单举例说明，论文中若还出现庞大的矩阵，同本说明）：矩阵的中元素表示该位置图片的灰度，255表示为白，0为黑，图片中信息为黑白文字信息。将附件1中的19张图片做如上处理得到均为的矩阵，这里我们分别将每张图片的矩阵第1列和第72列提取出来做一新的二维边缘矩阵，它是的矩阵。通过对所有图片矩阵的分析可以发现、矩阵中均有一列为0，所以可以认为编号为006和008的图片为原完整文件的一端，在做题过程中无需考虑会存在其他白边与白边拼接的情况。利用5.1.2中建立的模型并利用设计的算法步骤进行求解， 可以得到中文的19张碎纸片的拼接顺序如表1所示，拼接复原图见下图。附件1拼接复原后完整图片表1.纵切中文碎纸片拼接顺序 2、英文碎纸片的拼接复原 得到的匹配顺序如表2所示，拼接复原图见附录2。将附件2的19张图片做5.1.3.1中处理得到均为的矩阵，这里我们分别将每张图片的矩阵第1列和第72列提取出来做一新的二维边缘矩阵，它是的矩阵。通过对所有图片矩阵的分析可以发现 、矩阵中均有一列为0，所以可以认为编号为003和004的图片为原完整文件的一端，在做题过程中无需考虑会存在其他白边与白边拼接的情况。做如上判断后解题过程同5.1.3.1。附件2拼接复原后完整图片表2.纵切英文碎纸片拼接顺序5.1.4对于拼接结果的分析在上述纵切碎纸片拼接复原模型的求解验证过程中没有用到人工干预，因为所给的碎纸片中没有出现在拼接缝处均为空白的情况，所以依据灰度的匹配程度大小，可以完成拼接。若在拼接过程中出现拼接缝处为空白的图片，则应暂时不予考虑，等到其他图片拼接完成后，再对其进行人工干预，在剩下的空缺处对其进行拼接。5.2问题二5.2.1 模型建立对于问题二，我们要同时考虑纵横切的碎纸片，首先确定每一行的第一列，然后利用人工干预的方法拼出11行，再利用问题一的算法，将这11行依次拼接得到完整的文件，即“聚片成行，聚行成页”。5.2.2 基于元胞数组算法的纵横切模型二的算法设计与求解（1） 元胞数组这是matlab中的特色数据类型，它不同于其它数据类型（如字符型，字符数组或者叫字符串，以及一般的算术数据和数组）。它特有的存取数据方法决定了它的特点，它有给人一种查询信息的感觉，可以逐渐追踪一直到所有的变量全部翻译成基本的数据信息。它的class函数输出就是cell（细胞之意）。matlab中用char(n)来定义，当然最基本的是包裹式定义，比如先定义了一个字符型的变量a，并赋值，然后定义一个长整型b，并赋值最后用大括号来打包裹c=a,b来形成元胞c，当然进一步可以将c再包裹进去如d=a,b,c,abc,123都是合法的。用cell函数创建元胞数组，创建的数组为空元胞。cell函数创建空元胞数组的主要目的是为数组预先分配连续的存储空间，节约内存占用，提高执行效率。（2） 元胞数组算法步骤STEP1：确定要拼接的图片个数。STEP2：读取所有图片的灰度值，将图片数字化。STEP3：确定第一张图片，然后寻找与其相接的下一张图片。直至将一行拼接完成。STEP4：按照STEP3的步骤，依次拼接完成11行，得到11张图片。STEP5：利用Matlab读取这11张图片的灰度值，再依据问题一的算法进行计算拼接。5.2.3纵横切碎纸片拼接复原模型二的实例验证1.中文碎纸片的拼接复原此问中同5.1.3中的图片处理方法，也需要将209张碎纸片进行同样的图像处理转化为灰度矩阵。根据结果知此问中的图片转化后的矩阵为的矩阵，列数由第一问中的1980变为180，虽然数量变少，但是图片数量由19张变为了209张。利用上述算法及人工干预，我们可依次得到11张图片，如下图3所示。图3.附件3部分图片 再利用5.1.2中建立的模型将这11张图片依次拼接，最终得到完整的图片，顺序如下表3。附件3完整图片 表3.纵横切中文碎纸片拼接顺序2. 英文碎纸片的拼接复原通过上述步骤可一次把相同行的纸片先拼接好，得到新的11张横行碎纸片，如下图4。这里拼接11张碎纸片的方法同5.2.3，不再重述，得到的结果顺序见下表4。图4.附件4部分图片附件4完整图片 表4.纵横切英文碎纸片拼接顺序5.3问题三的模型建立与求解 问题三要求在双面打印横纵切割的情况下，对碎纸片进行拼接复原。由于问题三较于问题二，加入了双面打印的这一个新的条件，故可知问题三的基本思路可与问题二大体相似。5.3.1模型的准备1.图像的数据读取与处理 利用matlab的imread读取每一张图片的灰度信息值，再将灰度信息值转换为0-1矩阵。2.构建正、反面特征矩阵利用问题二中英文灰度条的够将方法，先得到图片k的a面特征灰度条，再扫描特征灰度条，得到a面的特征列向量： 其中同理，得到b面的特征列向量：其中，5.3.2 建立双面纵横切纸片匹配模型1.建立两次特征匹配模型第一次特征匹配： 将碎片k的a面与碎片s（s=0,1208且sk）的a面进行特征比较，即求碎片k的a 面特征向量与碎片s的a面特征向量的对应元素之差，在对差的绝对值求和，得到特征值：再将碎片k的a面与碎片s（s=0,1208且sk）的b面进行特征比较，即求碎片k的a 面特征向量与碎片s的b面特征向量的对应元素之差，在对差的绝对值求和，得到特征值：取一个合适小的置信区间,若，则进行第二次特征匹配： 情况一（）：将碎片k的b面与碎片s（s=0,1208且sk）的b面进行特征比较, 即求碎片k的b 面特征向量与碎片s的b面特征向量的对应元素之差，在对差的绝对值求和，得到特征值：取一个合适小的置信区间,若，则认为碎片k与碎片s的匹配方式为k的a面与s的a面处于一面的同一行上，k的b面与s的b面处于另一面的同一行。 情况二：将碎片k的b面与碎片s（ s=0,1208且sk）的a面进行特征比较，即求碎片k的b面特征向量与碎片s的a面特征列向量的对应元素之差，再对差的绝对值求和，得到特征值：取一个合适小的置信区间,若，则认为碎片k与碎片s的匹配方式为k的b面与s的a面处于一面的同一行上，k的a面与s的b面处于另一面的同一行。2.建立左右边界匹配模型左右边界矩阵为：（1）右边界匹配模型的构建 将第k个图片的右边界与第s张（ s=0，1208且sk）图片的右边界进行左边界匹配，即求第k张图片边界矩阵的第一列与第s张图片边界矩阵的第二列对应行元素的差，再求差的绝对值的和：将第k个图片的左边界一次与其余的任意一张图片的右边界尽心匹配，得到n个值：，。通过比较，取这n个值中的最小值，作为左边界匹配值。（2）最佳边界匹配模型的建立 取第k个图片，先与任意一张图片s（ s=0，1208且sk）图片依次进行右边界匹配，求得，再与任意一张图片s（ s=0，1208且sk）图片依次进行左边界匹配，得，取两者的最小值：对应的匹配方式即为第k张图片与第s张图片的最佳匹配方式。若=，则说明第k张图片的右边接于第s张图片的左边，记做sk。综上，我们的左右边界匹配模型可以总结为：（3）建立上下边界匹配模型 将第k张图片的上，下边界出的元素分别存于（k=1,2,11）矩阵的第一行、第二行中。即上下边界匹配模型中第k行的上下边界矩阵为：模型的构建如下：1. 上边界匹配模型的构建 将第k行的上边界与第s(s=1,2,11且sk)行的下边界进行匹配，即求第k行的边界矩阵的第一行与第s行的边界矩阵的第二行对应列元素的差，再求差的绝对值的和：将第k行的上边界一次与其余的任意一行的下边界进行上边界匹配，得到n个值：，。通过比较，取这n个数的最小值，作为上边界匹配值。2. 下边界匹配模型的构建 将第k行的上边界与第s(s=1,2,11且sk)行的下边界进行匹配，即求第k行的边界矩阵的第一行与第s行的边界矩阵的第二行对应列元素的差，再求差的绝对值的和：将第k行的上边界一次与其余的任意一行的下边界进行上边界匹配，得到n个值：，。通过比较，取这n个数的最小值，作为上边界匹配值。3. 最佳边界匹配模型的建立 取第k行，先与任意一行s（s=1,2,，11且sk）依次进行上匹配，求得，再与任意一行s（s=1,2,，11且sk）依次匹配，取两者的最小值：对应的匹配方式即为第k行与第s行的最佳匹配方式。若=，则说明第k行上边接于第s 行的下边；=时，说明第k行的下边与第s行的上边相连接。综上，我们构建的横纵切纸片的匹配模型为：5.3.4 模型的求解（1）算法Step1：读取图片数据，构建矩阵；Step2：任取碎片i依次与其他碎片s进行二次特征匹配，确定出i与s的特征面来自原文件的同一行；Step3：重复step2，将附件中的图片聚类分析，将相同特征的图片放在同一行；Step4：必要时加入人工干预，将类的个数降维，并使得没类的图片个数相同。Step5：取统一行中的第i张碎片，将其依次与第1张碎片，第2张碎片，第n张碎片进行左右匹配，得到右边界匹配值，再依次进行左右边界匹配，得到左边界匹配值。比较右边界与左边界匹配值得大小，选择两者中最小值对应的匹配方式，将两张图片按匹配方式结合，视为一个整体。Step6：重复进行step5，直至确定出每行内部图片的排列顺序。Step7：取第i行，将其依次与第1行，第2 行，第n行进行上边界匹配，得到上边界匹配值，再依次进行下边界匹配，得到下边界匹配值。比较上下边界值的大小，选择两者中最小值所对应的匹配方式，将两张图片按匹配方式结合，视为一体。Step8：重复进行step7，直至确定出每行的上下位置，从而得到图片的原始序列。（2）算法的实现 根据上述模型的分类原则，通过Matlab编程（见附录），将附件5中的2209张图片进行了归类。程序计算出来的结果中总共含有36类，这里只选取其中的三类元素展示在表11中：表11 特征匹配后的聚类结果类1类2类3073045691237657062426579184135204851418086148126105176187121185881622031071661151701391801511919610999112100113103134106196在这36类中，每一类的元素个数参差不齐。这是需要人工干预，先从元素较少的类中挑出元素与其他累的图片进行比较，通过对比图片中的文字到上边界的距离，文字的含义及其文字内容等特征，将这些图片归入其他元素较多的类别，直至正、反面都有11类，每一类19个元素。利用左右边界匹配模型，对每一类中各个碎片进行横向排序，得到各类中图片的排列顺序。再利用上下边界匹配模型，求出类与类之间的排列顺序。结合碎片在行内的排列顺序以及类与类之间之间的排列，就可以得到碎片再原文中的原始位置，进而复原出图片。拼接后的顺序如下表5和表6。 附件5拼接复原正面图片 附件5拼接复原后反面图片 表5.碎纸片正面拼接顺序表6.碎纸片反面拼接顺序6 模型的评价与推广6.1模型的优点 通过对复原后图片的验证结果可以认为本论文中的碎纸片复原拼接模型对于本题有很高的可行性。对于中、英文两种情况，论文中按照从问题一到问题三、中文到英文的顺序依次改进模型。发现了中文需要人工干预较少，英文需要人工干预较多的规律，说明不同语言有各自的特性。对于计算机错