搜索
1基于分治算法碎纸片的拼接复原模型摘要本文针对不同切割方式碎纸片的拼接问题，通过对图像数字化处理得到灰度矩阵，建立了复原模型并得到复原后的图像。针对单面仅纵切碎纸片的拼接问题，根据完整文件最左边部分无文字的特点，运用matlab编程可确定出第一张碎纸片。随后，根据贪婪算法的思想，以确定位置的碎纸片与剩余未拼接碎纸片相邻边缘灰度值的平方欧氏距离最短为目标函数，可逐步求得碎纸片的拼接顺序,进而将其复原.中文碎纸片顺序为：8、14、12、15、3、10、2、16、1、4、5、9、13、18、11、7、17、0、6；英文碎纸片顺序为：3、6、2、7、15、18、11、0、5、1、9、13、10、8、12、14、17、16、4。本问碎纸片拼接过程没有人工干预，实现了全自动化的拼接。对于既横切又纵切碎纸片拼接问题，本问采用分治算法的思想，先对中、英文碎纸片分别层次聚类分析，将最可能位于同一行的碎纸片归为同一类，其中中文碎纸片分为11类，英文碎纸片分为10类；再对分类后的碎纸片使用编程加人工干预的半自动拼接方式，得到11块仅横切的碎纸片块；最终对得到的11块仅横切的碎纸片块进行类间拼接，实现文件的复原。中文碎纸片第一列顺序为：49、61、168、38、71、14、94、125、29、7、89；英文碎纸片第一列顺序为：191、201、86、19、159、20、208、70、132、171、81。此问中有两次人工干预的过程，第一次位于类内拼接处，第二次位于类间拼接处。中文文件总共干预了33块，英文文件总共干预了40块。考虑双面碎纸片拼接问题时，本问延续了分治算法的思想。由于每张碎纸片含有正反两面，在聚类分析时，可将正反两面的灰度值相加为一列特征值作为它们是否可能位于同一行的依据，进而将双面碎纸片分为9类。再对这9类碎纸片使用编程加人工干预的半自动拼接方式，得到22块仅横切的碎纸片块；最终对这22块仅横切的碎纸片块进行类间拼接，实现文件的复原。复原后文件第1面第一列顺序为：136a、5b、143a、83b、90b、13b、35b、172b、105b、9a、54b；复原后文件第2面碎纸片第一列顺序为：78b、89a、186b、199b、88b、114a、146a、165b、3b、23b、99a。此问中有两次人工干预的过程，第一次位于类内拼接处，第二次位于类间拼接处。【关键词】：碎纸片复原贪婪算法平方欧氏距离分治算法层次聚类分析2一、问题重述破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。请讨论以下三个问题：问题一：对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达，表格为复原后碎片序号。问题二：对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果表达要求同上。问题三：上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果，结果表达要求同上。二、问题分析本文针对的是形状相似碎纸片的拼接问题，需提出相应的拼接模型与算法并对给定的碎纸片进行复原。常规文档碎纸片计算机拼接方法一般利用碎片边缘的尖点特征、尖角特征、面积特征等几何特征，搜索与之匹配的相邻碎纸片并进行拼接，根据题意可知，本文所研究的碎纸片形状相似，这种基于边界几何特征的拼接方法并不适用于边缘形状相似的碎纸片。碎纸片拼接时如果只利用碎片的边界特征，拼接效果并不理想。本文在实行拼接过程时，不但考虑了待拼接碎纸片边缘是否匹配，还考虑了碎片内字迹断线与文字是否匹配【3】。问题一是解决来自同一页且被纵向切断的碎纸片拼接问题。该问题本质上属于碎纸片组合优化问题。如何实现碎纸片的最优组合成为本问以及本文的一个难点。可考虑碎纸片内文字的特点。由于大多数文字文档的文字行方向和表格线方向平行且单一，如果碎片内的文字行或表格在碎片边缘断裂，那么与它相邻的碎纸片在边缘处一定有相同高度、相同间距的文字行或表格，凭此特征可以很容易地从形状相似的多碎片中挑选出相邻碎片。因文字行或表格线的高度特征、间距特征的识别比字迹断线识别和文字图像的理解实现起来要容易得多，利用碎片内文字行特征或表格特征拼接形状相似的碎纸片是可行的。运用贪婪算法的思想，现考虑以下的拼接过程：（1）根据碎纸片内文字特点找出第一张碎纸片，即该页的最左边那一张碎片；（2）根据第一张碎纸片，依次找出后面的碎纸片，直到组合完19张碎纸片。问题二是针对同一页但被横、纵向切断的碎纸片拼接问题。相对于第一问的不同，本问的碎纸片是即横切又纵切的情况，这增加了问题的难度。如果继续采用问题一中拼接碎纸片的步骤，在实现过程中会发现，要找出位于完整纸片最左边的碎纸片，将会无法实现。因为我们是根据完整纸片最左边内容为空白这一特征对碎纸片进行的筛选。但由于纸片被横、纵切，很有可能切断位置并未在文字上，而是位于文字间的空隙，这样本来位于复原后中间部分的纸片很有可能变为位于最左边的纸片，将会对碎纸片拼接复原带来错误。由于纸片被分为209张碎纸片，如果对其直接编程复原拼接，碎纸片数量3较大，难以实现。可引入分治算法的思想，将该问题分解为便于求解的子问题。考虑到图像在经过数字化后位于同一行的文字灰度值分布相似，可根据这一特点对碎纸片进行聚类分析。再由聚类分析的结果，实行类内拼接，最终人工微调，实现碎纸片的拼接复原。问题三是针对来自同一页但正反面均印有文字的碎纸片拼接问题，该问题可看成对前面两问的拓展。因此，在模型的建立和求解过程中，可以借助于前两问的模型。该问题相对于前两问的难点在于题目只给出了碎纸片的正反面内容，并未告知哪些碎纸片属于同一面。现在碎纸片数量为438张碎纸片，想要直接判别哪些碎纸片属于同一面难度较大。可考虑借助与问题二中将碎纸片聚类的思想，先将碎纸片进行分类，分类后在同一类内碎纸片互相拼接，结合人工干预，得到碎纸片拼接复原图并确定出碎纸片正反面。三、模型假设1、同一附件中的碎纸片来自于同一页文件，且未缺失；2、假设碎纸片模型为理想模型，碎纸片厚度为零；3、碎纸片表面光滑平整无磨损且无污点；4、假设破碎纸片边缘完好无缺损。四、符号说明符号含义),(kjfi碎纸片数字化后第i张纸片的第j行第k列数据，即该点灰度)(,jwsi第i张纸片的最后一列与第s张纸片第一列第j行数据平方欧氏距离R未匹配碎纸片的集合iD第i类碎纸片离差平方和五、建模前的准备图形的数字化【2】本文是根据碎纸片内文字行特征来进行判定碎纸片的拼接。故现在的关键是提取碎纸片内的文字信息。这就不得不提到matlab对图形的处理方法，即图形的数字化。图形的数字化是将连续色调的模拟图像经采样量化后转换成数字影像的过程。一幅图像可以定义为一个二维函数),(yxf，其中x和y是平面坐标，f在坐标点),(yx处的振幅称为图像在该点的亮度。黑白图像的亮度用灰度来表示，而彩色图像是由单个的二维图像组合而成的。图像的数字化过程如下面的流程图1所示：4图1图形的数字化流程图根据上图1图形数字化流程图，对以上步骤进行具体解释：（1）图形的采样图形的采样即要求要用多少点来描述一幅图像，采样结果质量的高低用图像的分辨率来衡量。简单来讲，对二维空间上连续的图像，在水平和垂直方向上等间距地分割成矩形网状结构所形成的微小方格称为像素点。一幅图像就被采样成有限个像素点构成的集合。本题中所给碎纸片为bmp格式，运用matlab程序读取后，该图像数字化为个像素点。（2）量化量化即要求使用多大范围的数值来表示图像采样之后的每一个点。量化的结果是图像能够容纳的颜色总数，它反映了采样的质量。本文采用8位储存一个点，即相当于黑-白间可用0-255个状态进行描述，其中量化后的值越接近0，则表示该点的实际颜色越接近黑色；相反量化后的值越接近255，则表示该点的实际颜色越接近白色。由破碎图片的数量可知，本题中的复原图像经过采样和量化后的结果是一个实数矩阵。由采样过程可知，该矩阵大小为。matlab中读入图像的数据类型为unit8，而在矩阵中使用的数据类型为double。因此，要把图像经相应程序读入后的矩阵中的值转换成double精度类型；如果不转换，在对unit8进行加减时会产生溢出。现一幅图像经过采样、量化与数据转换三个步骤后，该数字图像在matlab中可以很自然地表示为矩阵，如下面矩阵A所示：),(),(),(),(),(),(),(),(),(NMfMfMfNfffNfffA矩阵A中各元素值即灰度满足条件为：),(,),(NjMijif其中M，N。图形的采样量化开始图形灰度值矩阵5六、模型的建立与求解6.1被纵切后碎纸片的拼接复原模型本问是解决来自同一页且被纵向切断的碎纸片拼接问题。该问题本质上属于碎纸片组合优化问题。由于所给碎纸片形状相似，无法使用尖点特征、尖角特征、面积特征等几何特征来实现碎纸片的拼接。可考虑碎纸片内文字的特点。文字文档的文字行方向和表格线方向平行且单一，如果碎片内的文字行或表格在碎片边缘断裂，那么与它相邻的碎纸片在边缘处一定有相同高度、相同间距的文字行或表格，凭此特征可以很容易地从形状相似的多碎片中挑选出相邻碎片。因文字行或表格线的高度特征、间距特征的识别比字迹断线识别和文字图像的理解实现起来要容易得多，利用碎片内文字行特征或表格特征拼接形状相似的碎纸片是可行的。但考虑到计算机对图像拼接问题的缺陷，可在拼接过程中适当的加人工干预的过程。6.1.1被纵切后碎纸片的拼接复原模型的建立（一）碎纸片特征分析由于本问是根据碎纸片内相应的文字信息来进行拼接。碎纸片内文字信息包含字体的大小、高度以及亮度等内容。为了将碎纸片内文字的信息提取出来，对碎纸片进行数字化处理。该过程并不复杂，只需运用matlab相应的程序即可。在将图片输入到matlab中时，图片是以的矩阵存在于matlab软件中。每一点值的大小是由该点颜色所决定。经过数据的量化与转换后，该值大小为0-1。其中该值越接近0，则表示该值所对应点的实际颜色越接近黑色；相反该值越接近1，则表示该点的实际颜色越接近白色。（二）贪婪算法思想本问采用贪婪算法的部分思想，实现19张仅纵切碎纸片的拼接复原。贪婪算法是一种对某些求最优解问题的更简单、更迅速的设计技术。用贪婪法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，通过每一步贪心选择，可得到问题的一个最优解。本问根据碎纸片内文字特点找出第一张碎纸片，即该页的最左边那一张碎片。在找到第一张碎纸片后，运用贪婪算法的思想，在剩余18张碎纸片内求最优解，寻找与第一张碎纸片匹配的碎纸片；依此类推，逐步寻找第i张碎纸片的匹配纸片，直到19张碎纸片均被匹配。（三）平方欧氏距离定义将19张碎纸片经matlab数字化后得到19个的矩阵。根据附件中碎纸片的编号顺序将19个矩阵合并为一个大小为)(的矩阵，矩阵中的值，即像素，取值为0-1。其中该值越接近0，则表示该值所对应点的实际颜色越接近黑色；相反该值越接近1，则表示该点的实际颜色越接近白色。该矩阵如下A所示：),()