B题 碎纸片的拼接复原

B题  碎纸片的拼接复原 摘要 本论文研究基于文字信息的具有规则外部轮廓的碎纸片的拼接问题，以二值图像矩阵中向量间的欧氏距离来表示两个碎纸片的相似程度，距离越小相似度越大，建立求最短路的数学模型。 对于问题一，由于各条碎纸片的边缘轮廓都是规则的，所以本文从碎片上的文字信息出发，结合图片像素信息进行拼接复原。首先把图片信息转化成灰度像素矩阵，通过阀值将灰度像素矩阵转换成二值图像矩阵，用碎纸片m的二值图像矩阵的最后一个列向量和碎纸片n的二值图像矩阵的第一个列向量的欧氏距离表示两个碎片的相似程度，相似程度最高的进行拼接，从而完成图片的识别。 对于问题二，碎纸片是由纵切和横切得到的，其二值图像矩阵的维数只有180 72维，矩阵的每一行只有72列，反应的文字信息很少，并且有些碎片的横边界或是纵边界并没有切到文字，所以考虑全部像素点。然后利用二值像素矩阵行向量的第一次黑白跳变的位置将碎片分类，把原来位于同一行的碎片放在同一个集合中，然后用问题一的方法拼成一个横条。如果横条的边界有文字信息，将横条的二值像素矩阵旋转90度变成纵条，然后利用问题一的方法进行拼接；对于边界没有文字信息的横条，应该是从行间距处被切割，原图中相邻横条的边界拼接后正好是一个行间距的值，通过统计数据可知，一个行间距占用44行全1行向量，因此可以根据行间距的值进行拼接。 对于问题三，碎纸片有正反两面文字。且既有纵切又有横切，相当于碎片变成了418片，同样根据二值矩阵统计所有具有相同第一次黑白跳变的纸片，放入同一个集合，拼成22个横条。确定每个横条的始末位置。然后从第一位开始向右拼接横条，复员后第二位的碎片应该是集合中去掉第一位碎片后与第一位碎片相似度最高的碎片。以此类推，直到拼接到最后一张碎片。若把每一碎片看成一个节点，两碎片的相似度的倒数看成这两个节点相连后边上权值，同一节点不可能相连，任意节点到自身的权值设为一个很大的数，这样每个横条拼接的顺序就是从第一位到最后一位碎片最短路径的顺序。横条拼好后，用相同的方法恢复一面原图。如果横条边缘出现全1行向量，处理方法同上。再拼横条的过程中如果碎片纵向边缘存在全列向量，应该进行人工干预。 关键词：二值化 黑白跳变 欧氏距离 最短路径 一 问题重述 破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大时，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。现讨论以下问题： 1.对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达（见【结果表达 格式 pdf格式笔记格式下载页码格式下载公文格式下载简报格式下载 说明】）。 2.对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果表达要求同上。 3.上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果，结果表达要求同上。 二 模型假设 1． 各个碎纸片上的文字不会完全相同。 2． 每个碎片的边缘是规则的。 三 符号假设 1． 表示问题1中序号为 的碎纸片像素的灰度值； 2． 表示问题2中序号为 的碎纸片像素的灰度值； 3． 表示碎纸片m与碎片n的相似程度； 4． 表示碎纸片m的灰度图像矩阵的最后一个列向量和碎片n灰度图像矩阵的第一个列向量的欧氏距离； 5． 表示第 个块的加权有向图； 6． 表示第 个块中处于第 个位置的碎纸片。 四 问题分析 4.1 问题一的分析 对于问题一，本文考虑到各条碎纸片的轮廓都是规则的，具有相同的几何特征，不能从各条碎纸片的外部轮廓进行图片的拼接。通过观察碎纸片可知，每条碎纸片的边界处都会有文字被切到，所以本文从碎纸片上的文字出发，结合图片像素信息进行拼接复原。首先把图片信息转化成灰度像素矩阵，矩阵中的每一个元素是介于0到255的整数数值，0表示黑色，255表示白色，其它数值表示不同程度的灰色，有图片给出的只要是白底黑字的文字信息，通过阀值将灰度像素矩阵转换成二值像素矩阵，用碎纸片m的二值像素矩阵的最后一个列向量和碎片n二值像素矩阵的第一个列向量的欧氏距离表示两个碎片的相似程度，相似程度最高的进行拼接，从而完成图片的识别。 4.2 问题二的分析 对于问题二，碎纸片是既有纵切又有横切，其二值像素矩阵的维数只有180 72,，矩阵的每一行只有72列，反应的文字信息很少，并且有些碎片的横边界或是纵边界并没有切到文字，所以问题一中的解决方法不能直接用于本问题。 本文考虑到复原后位于同一行的碎片的二值像素矩阵行向量的第一次黑白跳变的位置应该相同，把原来位于同一行的碎片放在同一个集合中，然后用问题一的方法拼成一个横条。如果横条的边界有文字信息，将横条的二值像素矩阵旋转90度变成纵条，然后利用问题一的方法进行拼接；对于边界没有文字信息（即二值像素矩阵中的行向量中从边界向内至少有一个全是1的向量）的横条，应该是从行间距处被切割，原图中相邻横条的边界拼接后正好是一个行间距的值，通过统计数据可知，一个行间距占用44行全1行向量，因此可以根据行间距的值进行拼接。 4.3 问题三的分析 对于问题三，碎纸片有正反两面文字。且既有纵切又有横切，相当于碎片变成了418片，用问题二的方法根据二值矩阵统计所有具有相同第一次黑白跳变的纸片，放入同一个集合，准备拼成22个横条。但是由于数据量成倍增大，循环算法的复杂度变大。经统计可知部分碎片的二值矩阵的前10列或后10列为全1阵，考虑到页面的左右缩进，我们认为前十列为全1阵的二值矩阵的碎片应位于每一个横条的首位，同样后十列为全1阵的二值矩阵的碎片应位于每一个横条的最后位置，这样会就确定了每一个横条的始末位置。然后从第一位开始向右拼接横条，复员后第二位的碎片应该是集合中去掉第一位碎片后与第一位碎片相似度最高的碎片。以此类推，直到拼接到最后一张碎片。若把每一碎片看成一个节点，两碎片的相似度的倒数看成这两个节点相连后边上权值，同一节点不可能相连，任意节点到自身的权值设为一个很大的数，这样每个横条拼接的顺序就是从第一位到最后一位碎片最短路径的顺序。横条拼好后，用相同的方法恢复一面原图。如果横条边缘出现全1行向量，处理方法同4.2。再拼横条的过程中如果碎片纵向边缘存在全列向量，应该进行人工干预。 五 模型的建立与求解 5.1 问题一的模型建立与求解 5.1.1 图像的预处理 对于本文中的碎纸片，考虑到各个碎纸片的外部轮廓都是规则的，具有相同的几何特征，不利于图片的拼接，所以本文从碎纸片上的文字信息出发，通过人工识别，可以确定在复原图中位于最左端的碎纸片的序号，然后考虑该碎纸片的灰度像素矩阵的最后一个列向量，分别求出其和剩余碎纸片的灰度像素矩阵的最后一个列向量的相似程度，将相似程度最大的碎纸片与该碎纸片拼接，这样就完成了两条碎纸片的拼接，接下来用相同的方法寻找与第二条碎纸片的右边界相拼接的碎纸片，这样就完成了三条碎纸片的拼接，依次下来，可以完成19条碎纸片的拼接，得到碎纸片的复原图。 由于原图给出的是一个灰度图，在只含有文字的纸片中灰度图是为了实现反走样[1]，分辨率足够大时走样是肉眼观测不到的，因此可以将灰度图像[2]矩阵简化为为二值图像矩阵，下面介绍灰度图像和二值图像。 （1） 灰度图像与二值图像 灰度图像是一种离散图像，离散图像是指用一个数字序列表示的图像，该阵列中的每个元素是数字图像的最小单位，称为像素，每个像素对应一个灰度值，反应该点的亮度。灰度图像矩阵元素的整数取值范围通常是[0 255]， “0”表示纯黑色，“255”表示纯白色，中间的整数数字从小到大表示由黑到白的过渡色。 二值图像可以看成是灰度图像的一个特例，其二维矩阵仅有0、1两个值构成，“0”代表黑色，“1”代表白色。由于每一个像素（矩阵中每一元素）取值仅有0、1两种可能。并且二值图像[3]通常用于文字、线条图的扫描识别和掩膜图像的存储。所以二值图像适用于本文基于文字的碎纸片识别。 （2） 将灰度像素矩阵转化成二值像素矩阵 将灰度像素矩阵转化成二值像素矩阵最关键的一步是找出转化的阀值，基于灰度像素矩阵的特点，大多数灰度值是0或255，说明构成图像的两部分差别很大，所以本问题适合用最大类间方差法求阀值。 设图像有M个灰度值，取值范围在0~M-1，在此范围内选取灰度值t，将图像分成两组G0和G1,G0包含的像素的灰度值在0~t，G1的灰度值在t+1~M-1，用N表示图像像素总数， 表示灰度值为i的像素的个数。 已知：每一个灰度值出现的概率为 ；假设G0和G1两组像素的个数在整体图像中所占百分比为 ，两组平均灰度值为 ，可得 概率： 平均灰度值：                图像的总平均灰度为：      类间方差为：  将灰度像素矩阵中值是“0”的仍然用“0”表示，代表黑色，将值是“255”的用“1”代替，表示白色，将像素值处于“0”到“255”之间的数分别用“0”或“1”表示，利用最大类间方差法，算出图像二值化的最佳阀值是125，将碎纸片的灰度像素矩阵中值大于“0”且小于“125”的数用“0”代替，表示黑色，将碎纸片的灰度像素矩阵中值大于等于“125”且小于“255”的数用“1”代替，表示白色，这样就将一幅灰度图像转化成了一副仅用0、1表示的二值图像。 5.1.2 图像的模式识别 本论文中的模式识别就是依靠碎纸片边界上像素点的相似程度 来决定的，这里相似程度的大小用第m个碎片的最后一列列向量与第n个碎片的第一列列向量欧氏距离[4] 来表示，欧氏距离越小对应的相似程度就越高，相似程度越高拼接的可能性越大。 （1） 欧氏距离的介绍 欧氏距离表示在m维空间中两个点之间的真实距离。 n维欧氏空间是一个点集,它的每个点 可以表示为 ，其中 是实数，称为 的第 个坐标，因此两个点 和 之间的距离 来定义下面的公式： （1） （2）二值像素矩阵列向量的相似性计算 计算已拼接碎纸片（ ）的二值像素矩阵的最后一个列向量，与剩余碎纸片（ ）的二值像素矩阵的第一个列向量的欧氏距离，其 计算公式 六西格玛计算公式下载结构力学静力计算公式下载重复性计算公式下载六西格玛计算公式下载年假计算公式 如下： （2） 由于直接可以看出有左边界（即二值矩阵的前几列都是全1列向量），所以首先人工识别处位于原图中第一位的纵条和最后一条碎纸片，然后根据相似度最大依次循环用计算机识别出第2条到第19条碎纸片，然后把第19条碎纸片和人工选出来的最后一条碎纸片进行比较，结果一致，说明计算机对碎纸片的识别具有很高的可信度，利用这种方法，本文利用matlab程序(见附件程序1.1，1.2)得出附件1，附件2的结果，复原后的碎片序号排列如表1所示：