1、1说明：本范例格式与附件 2 中格式略有不同，参赛队可综合参考碎纸片的拼接复原张三，计科 N131，15024316397（656397）李四，计科 N132，15024317789（657789）王五，工管 N141，15024318899（658899）摘 要本文研究的是碎纸片的拼接复原问题，分别对碎纸机仅纵切、既纵切又横切单页文件以及纵横切双面文件三种情形，建立碎纸片拼接模型和算法，实现对碎纸片的拼接复原。问题一中，仅考虑纵切单面文件的情形。首先，将 19 张碎纸片导入 matlab 软件得到 19 个 1980*72 的灰度值矩阵，对图像进行二值化处理。考虑到原文件最左端有一部分空白，
2、故原文件中最左端碎纸片的编号为 008。然后，引入吻合度指标，将吻合度最大作为目标，建立单目标规划模型，采用逐步迭代拼接的方法，寻找右邻碎纸片，最后，得到了中英文碎纸片的复原图。例如，中文复原图碎纸片从左到右的排列顺序（仅列出前 5 张）编号为 008、014、012、015、003。复原过程不需要人工干预。问题二中，考虑碎纸机既纵切又横切的情形。首先，同问题一类似，对附件 3、附件 4 中的纵横切碎片数据进行处理，确定 11 个最左边碎纸片，例如中文的最左边碎纸片编号为 007、014、168 等。然后，对于中、英文文件碎片，分别采用了聚类分析和标准基线对准方法进行分类。利用问题一的模型，进
3、行拼接求解。由于纵横切导致得到的碎纸片数很多，计算机不能保证吻合度最大的右邻矩阵是匹配的，因此需要人工干预，例如，编号为 007 的碎片所在行，迭代到第 9 次时需要做一次人工干预。最后，仿照问题（1）的思路，考虑各行拼接复原图上下行之间的吻合度，从而实现了整个的拼接复原过程。例如中文复原图第一行中的前 5 个纸片的编号分别为007、208、138、158、126。问题三中，拼接过程，既要保证正面匹配，也要保证反面匹配。首先需要确定原文件中 22 个最左端碎纸片，选取最左端碎纸片作为起点，按行进行拼接。根据问题（2）对英文字母特点分析，以四线格的中心线到碎片顶端的距离作为标准，对 418 张碎
4、片进行分类，以吻合度最大作为目标建立数学模型。搜索右邻碎片时，优先在同一类别内部局部进行，直到找到匹配的右邻矩阵为止，最终得到双面打印文件的复原图，例如其中一面第一行前 5 列编号为 136a,047b,020b,164a,081a，另一面第一行前 5 列编号为 078b,111b,125a,140a,155a。最后对模型的优缺点进行评价，并对在实际情况中的打印文件可能出现噪音等情况进行了讨论。关键词： 拼接复原；吻合度；灰度值；人工干预21 问题重述1.1 问题背景破碎文件的拼接复原问题，是计算机视觉、图像分析和模式识别中一个突出难题。它被应用到很多领域，如司法物证复原、历史文献修复以及军事
5、情报获取等。传统中，拼接工作大部分都是靠人工的方式完成，虽然准确率较高，但是效率却很低。特别是当碎片数量巨大，人工拼接很难及时完成任务。随着网络时代计算机技术的发展，人们开始尝试开发碎片的自动拼接技术，以提高拼接复原效率。1.2 问题提出为了研究碎纸片的拼接复原技术，需要讨论以下问题：1.对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切） ，建立碎纸片拼接复原模型和算法，并针对附件 1、附件 2 给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达。 2.对于碎纸机既纵切又横切的情形，请设计碎纸片拼接
6、复原模型和算法，并针对附件 3、附件 4 给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果表达要求同上。3.上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件 5 给出的是一页英文印刷文字双面打印文件的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件 5 的碎片数据给出拼接复原结果，结果表达要求同上。2 问题分析题目要求我们解决破碎机的拼接复原问题 。针对碎纸机对单页文件仅纵切、既纵切又横切以及对双面文件的破碎三种情形，建立碎纸片拼接模型和算法，实现对破纸片的拼接
7、复原。对于问题（1） ，题目要求我们仅考虑碎纸机纵切同一页文字文件的情形，建立碎纸片拼接复原模型。首先，通过对碎纸片外形等相关分析，得到适用于边缘相似的碎纸片的拼接复原模型。然后，利用图像二值化处理的方法实现拼接，由 0-1 变量找到最左边纸片，其次引入吻合度的概念，找出剩余 18 张纸片中与最左边纸片吻合度最大的纸片，最后加入人工干预，找到与最左边纸片最匹配的纸片，以此推类，从而完成整个的拼接复原过程，其主要分析思路如下（图 1） ；边缘吻合度 二值化处理人工干预拼接复原内容匹配图 1 拼接复原过程对于问题（2） ，题目要求我们对于破碎机既纵切又横切的情形，设计碎纸片的拼接复原模型和算法。首
8、先，根据问题一的模型，分别找到中、英文的11张最左边碎纸片。然后，计算所有碎纸片的特征列向量，由它们特征列向量的关系进行聚类。接着，3通过问题（1）的方法，让最左边碎纸片先在自身的类别搜索，若找不到匹配的纸片则跳出类别继续搜索，进而得到11张一行拼接复原图。最后，接着仿照问题（1）的思路，考虑各行拼接复原图相邻上下行的吻合度，加上人工干预操作，从而实现整个的拼接复原过程。对于问题（3） ，本题要求我们对纵横切碎片双面文件进行拼接，考虑到既要保证正面匹配，也要保证反面匹配。首先需要寻找最左端碎纸片，考虑到英文字母的物理特征，于是虚拟一个基线进行对准分类，以吻合度最大作为指标，利用问题一模型，直到
9、找到匹配的右邻矩阵为止，并最终得到了双面打印文件的复原图。3 模型假设与符号说明3.1 模型的假设（1）假设纸张上的信息都是真实有效的；（2）假设纸张上的边界整齐、行距规范，无特殊情况；（3）假设人工干预是理性的，即正确有效的。3.2 符号的说明：图像的底的像素总个数；m：图像的高的像素总个数；n：左端碎片灰度值矩阵经二值化后第 行末列；()ai i：右端灰度值矩阵经二值化后第 行首列的取值；kb： 和 的取值关系；,D()ikbi：第 张剩余碎纸片和左边碎纸片的吻合度；(kW：剩余 张碎纸片可以进行模拟搭配；s：吻合度；表示矩阵 第 行第 列的灰度值；ijRij表示矩阵 二值化后第 行第 列
10、的取值；Bij：碎纸片的特征列向量；iF：左端碎纸片；A：剩余要进行搜索的左端碎纸片；k：相邻两碎纸片文字与自身顶端距离相等的行数；v：像素点的个数， 。g10,2g4 模型的准备4.1 手动处理由于题目给定的碎纸片没有固定的摆放方位，所以在建立拼接复原模型之前，我们先对碎纸片字体朝向进行手动处理，即把所有碎纸片的字体朝向摆正，也就是说我们的拼接模型建立在纸片字体上下方位正确的基础之上。4.2 灰度值计算 1对于每一张碎纸片，可以理解为一个二维阵列，阵列的元素值称为灰度值。灰度值的范围是（0-255） ，当灰度值为 255 时，为最亮的白色，为 0 时为黑色。灰度图像4能反映整幅图像的整体和局
11、部的色度和亮度等级的分布和特征。 为了计算每张纸片的灰度值，把附件中的所有图片导入 matlab 软件，可以把图像转化为矩阵，图像大小和矩阵大小是一样的。图像的最小分辨单元是像素，每个图像有 个像素， 代表图像的底的像素总个数， 代表图像的高的像素总个数，总共mn n有 个像素单元， 处的值代表图像中该点的灰度值。由此，总共可以得到大(,)mn小为 的若干矩阵。4.3 二值化处理 2由于一幅图像可能包括文字、背景还有噪声等等，根据灰度值矩阵可知，文字灰度值的大小不一，为了更好地区分黑色文字和白色背景，这里设定一个全局的阈值 ，T用 将图像的灰度值分成两部分，若该图像的灰度值矩阵为 ,对矩阵 进
12、行二值化处T R理：025ijij TB（1）其中， ， 表示矩阵 第 行第 列的灰度值， 表示矩1,2.,.injmijRijijB阵 二值化后第 行第 列的取值。将矩阵 中大于等于 的灰度值设定为白色，小于R T的灰度值设定为黑色。T5 模型的建立与求解5.1 问题（1）的模型建立与求解5.1.1 拼接复原模型的建立本题所有碎纸片几何形状均为规则的矩形，因此仅利用碎纸片的几何边界特征并不能达到拼接效果。为此，对这类边缘相似的碎纸片的拼接，拼接时主要考虑的是碎片内的字迹断线或碎片内文字图像内容是否匹配。拼接复原时可以采用枚举拼接复原的方法，若仅考虑纵切，即 19 张碎纸片共有种拼接方案，通过
13、人工干预识别即可得到最终的拼接方案。但这种枚举拼接的方法19A要重复 次，数量级为 ，无论是计算机模拟枚举还是人工识别，都是不现实的。170为此，本题提出了一个改进的拼接复原模型，既能保证答案的精确度，又大大缩短了运算时间。1.改进的拼接模型的原理：（1）先找到位置在原图像最左边的碎纸片；（2）将这张碎纸片的最右端边缘与其他碎纸片的最左端边缘进行比较，找出一个最适合该碎纸片的右邻碎纸片；（3）以右邻碎纸片为对象，重复原理（2） ，即可得到一幅拼接复原图。该模型引入图像二值化处理的方法，结合0-1变量，提出了吻合度的概念，寻找出吻合度最大的右邻碎纸片。但是由于计算机无法确定右邻碎纸片与左边碎纸片
14、的是否内容匹配，如果出现吻合度最大而内容上不匹配的情况，此时应添加人工干预，人工干预时选择吻合度次优的碎纸片代替上一个右邻碎纸片，直到找到内容匹配的右邻碎纸片为止，最终可以得到完整的碎纸片拼接复原图。以下列出具体的算法步骤：2.原图像最左边碎纸片5因为当灰度值为 255 时为最亮的白色，0 时为黑色，考虑到最左边的纸片会留出一部分空白边距，于是对 19 个 的碎纸片矩阵进行全局搜索，找到第一列中灰度19872值均为 255 或者出现 255 的次数最多的矩阵，该矩阵所对应的的碎纸片即为最左边碎纸片。3.约束条件：0-1 变量拼接复原要求原图像相邻的两张碎纸片尽可能吻合，因此，左边碎纸片的右端边
15、缘与右边碎纸片的左端边缘尽可能相似。在计算机模拟时，可以将灰度值矩阵进行二值化处理后的作边缘比较，这里引入了一个 0-1 变量 ，即：D1,(), 1,2.0kaibDki in（2）其中， 表示左端碎片灰度值矩阵经二值化后第 行末列， 表示右端灰度值()ai i()kbi矩阵经二值化后第 行首列的取值, 表示 和 的取值关系。当 时，(,)ki()akb()kaib取为 1，表示两者取值相等，反之 取 0。(,)Dki ,6开始输入 19 张碎纸片的灰度值矩阵i=1找左边边界碎纸片计算吻合度提取出吻合度最大的碎纸片两纸片是否匹配拼接这两个碎纸片i=i+1（）YNi18人工干预，提取吻合度次优
16、碎纸片输出完整的复原图像结束NY二值化处理图 1 流程图4.目标函数由于切割的随机性，并不能保证原图像任意相邻两张碎纸片的边缘完全相同，因此，这里提出吻合度指标，用于寻找最吻合的相邻两张碎纸片。它的计算公式是：1980(,)(,)1,2.kiWabDkis（3）其中， 表示第 张剩余碎纸片和左边碎纸片的吻合度， 代表灰度值矩阵(,)kWab n行数， 表示剩余 张碎纸片可以进行模拟搭配。ss综合以上，得到以下数学模型：71980max(,)(,),)0,2.;2,.kiWbDkiDii s或（4）由于计算机无法确定右邻碎纸片与左边碎纸片内容是否匹配，如果出现吻合度最大而内容上不匹配的情况，则应
17、添加人工干预，即选择吻合度次优的右邻碎纸片代替上一个右邻碎纸片，直到找到内容匹配的纸片为止，以此类推，最终可以得到完整的碎纸片拼接复原图。其简明流程图如图 1 所示。5.1.2 拼接复原模型的求解根据拼接复原模型的算法步骤，我们首先对附件 1、2 中每张纸片对应的灰度值矩阵进行二值化处理，这里把全局的阈值 取为 255，此时矩阵的取值只有 0 和 255 两种T情况，分别表示黑色和白色。接着对 19 个 的碎纸片矩阵进行全局搜索，找到9807第一列中灰度值均为 255 或者出现 255 的次数最多的矩阵，该矩阵所对应的的碎纸片即为最左边碎纸片，本题中中、英文碎片的最左边纸片分别为 008.bm
18、p 和 003.bmp。在找到最左边纸片后，需要比较最左边碎纸片的右端边缘与剩余 18 张碎纸片的左端边缘之间的吻合度。为了方便计算，这里取出中文最左边碎纸片 008.bmp 和任意一张碎纸片 011.bmp，计算两者的吻合度。首先需要取出 008.bmp 灰度值矩阵二值化后最后一列的数值，以及任意一张碎纸片 011.bmp 灰度值矩阵二值化后第一列的数值，画出碎纸片 008.bmp 右端边缘二值直方图和碎纸片 011.bmp 左端边缘二值直方图（图 2 和图 3）：0 200 400 600 800 1000 1200 1400 1600 1800 200005010015020025030
19、0 之之之008.bmp之之之之之之之之之之之之之之之之之之之之图 2 碎纸片 008.bmp 右端边缘二值直方图80 200 400 600 800 1000 1200 1400 1600 1800 2000050100150200250300 之之之011.bmp之之之之之之之之之之之之之之之之之之之之图 3 碎纸片 011.bmp 左端边缘二值直方图其中纵坐标表示的是二值化后的灰度值，横坐标表示的是碎纸片的高。得到这两张纸片的二值直方图后，利用 0-1 变量比较两列数值的关系，如果在任意相同行中列的数值相等，则赋予 1 变量，否则赋予 0 变量。通过计算，得到两者在相同行中列数值相等的次
20、数为 1518。接下来计算两张碎纸片的吻合度 ，由公式（3） ，W可以很快算得两者的吻合度为 0.767。同样的方法，我们可以得到剩余 18 张碎纸片与 008.bmp 的吻合度（见表 1）：表 1 中文图像最左边碎纸片与其他碎纸片吻合度碎纸片名（*.bmp） 0 1 2 3 4 5 6吻合度 0.762 0.746 0.712 0.705 0.737 0.799 0.727 碎纸片名（*.bmp） 7 8 9 10 11 12 13吻合度 0.750 0.827 0.718 0.735 0.767 0.745 0.700 碎纸片名（*.bmp） 14 15 16 17 18 * *吻合度 0
21、.923 0.767 0.723 0.725 0.792 * *从表 1 可以看出，碎纸片 014.bmp 与 008.bmp 的吻合度最大，达到 0.9232，说明014.bmp 的左端边缘与 008.bmp 右端边缘有 92.32%的灰度值是相同的。综上，求解出完整的复原图，其 matlab 程序见附录 2（程序 1） ，拼接复原的图片形式见附录 1（图片 1） ，表格形式表达如下（见表 2）：表 2 中文复原图碎纸片排序表列数 1 2 3 4 5 6 7序号 008 014 012 015 003 010 002列数 8 9 10 11 12 13 14序号 016 001 004 00
22、5 009 013 0189列数 15 16 17 18 19 * *序号 011 007 017 000 006 * *因此，中文复原图碎纸片从左到右的排列顺序为008.bmp、014.bmp、012.bmp、015.bmp、003.bmp、010.bmp、002.bmp、016.bmp、001.bmp、004.bmp、005.bmp、009.bmp、013.bmp、018.bmp、011.bmp、007.bmp、017.bmp、000.bmp、006.bmp。根据同样的方法，我们还可以求出英文复原结果的图片形式见附录 1（图片 2）和表格形式（见表 3）：表 3 英文复原图碎纸片排序表列数
23、 1 2 3 4 5 6 7序号 003 006 002 007 015 018 011列数 8 9 10 11 12 13 14序号 000 005 001 009 013 010 008列数 15 16 17 18 19 * *序号 012 014 017 016 004 * *因此，英文复原图碎纸片从左到右的排列顺序为003.bmp、006.bmp、002.bmp、007.bmp、015.bmp、018.bmp、011.bmp、000.bmp、005.bmp、001.bmp、009.bmp、013.bmp、010.bmp、008.bmp、012.bmp、014.bmp、017.bmp、0
24、16.bmp、004.bmp。由于本题中碎纸片的数量较少，且面积相对较大，即相邻矩阵之间的文字内容相关性很大，所以在拼接复原过程中，我们仅凭吻合度这一指标就完成了碎纸片的拼接复原工作，在复原过程中并没有进行人工干预的操作。5.2 问题（2）的模型建立与求解本题在问题一的基础上，考虑碎片机既纵切又横切的情形。问题一中仅需考虑两个灰度值矩阵相邻列之间的吻合度，而问题二不仅需要考虑两个灰度值矩阵相邻列之间的吻合度，还需要考虑它们相邻行的吻合度。5.2.1 模型的建立这里给出该拼接复原模型的原理：（1）根据问题一的模型得到 11 副一行拼接复原图；（2）为每一副一行拼接复原图寻找最适合的上邻和下邻复原
25、图，最后通过人工干预，即可得到一幅完整的拼接复原图。由于问题一模型的算法存在一定的局限性，它更适用于仅纵切或仅横切，而且碎纸片的高度较大的情况，对于问题一来说，需要求解 171 次吻合度，程序运行效率较高，如果把该算法直接引用到问题二，算法的复杂度将增加 170 多倍，人工干预的次数将大大增加。由此，我们考虑将问题一的算法进行改进。为了缩小计算吻合度时的搜索范围，提高拼接复原模型的效率，本题利用了聚类的思想，因为对于一段打印文字而言，文字总是出现在一定的行范围内，所有根据这一特征，对碎纸片进行了聚类。5.2.1.1 中英文各自分类（1）中文分类聚类分析同样利用问题（1）的思路，得到 209 张
26、碎纸片的灰度值矩阵，并进行二值化。为了反映碎纸片的文字特征，引入了一个列向量 ：F10121807(,.),.TiijjFffR（5）其中， 表示碎纸片灰度值矩阵的灰度值， 表示该碎纸片的特征列向量，用于ijRi聚类分析。聚类得到类的个数对模型的算法效率有一定的影响。如果类的个数较少，则不能有效地减低算法的复杂度；如果类的个数较多，则会由于个别碎纸片分类的错误而导致寻找该碎纸片时复杂度大大增加，因此，这里需要选用一个恰当的类别个数，从而大大降低算法的复杂度。（2）英文分类按基线位置分类相邻匹配的两个碎纸片，若左端碎纸片文字行数为 行，且每行文字中心距离该k碎纸片顶端距离是 ，则右端碎纸片中至少
27、有 1 行文字中心与自身顶端距离和某个kL相等，即kL,(,),12,.0kvIABks（6）其中， 为左端碎纸片， 为剩余要进行搜索的左端碎纸片， 为相邻两碎纸片Ak v文字与自身顶端距离相等的行数，一般为 1 或 2 或 3。5.2.1.2 分类后的拼接复原 按行拼接完整部分图首先利用问题一中的算法求解，找到中、英文复原图的 11 张最左边碎纸片，判断最左边碎纸片所属的类别，然后在各自的类别中继续利用问题一的方法，即结合吻合度和内容匹配情况，寻找出与每一个最左边碎纸片拼接的右邻碎纸片。如果在自己的类别中搜索不到符合条件的碎纸片，此时便跳出该类别，寻找其它类别中与最左边碎纸片吻合度最大的纸片，继续重复以上步骤，最终得到 11 副一行拼接复原图。根据问题（1）的思想，提出了基于 0-1 规划的数学模型：目标函数：吻合度最大（7）180(,)(,)1,2.kiWabDkis约束条件：相邻匹配的两个碎纸片，左端碎纸片的右端边缘与右端碎纸片的左端边缘的灰度值是否相等，用 0-1 变量 表示1,(), 1,2.0kaibki in（8）因此，该单目标规划模型可以写为：
