CUMCM2013-碎纸片的拼接复原(全国一等奖)

1碎纸片的拼接复原张旭萌(数学与应用数学)、崔宇(数学与应用数学)、顾尔健（计算机科学与技术）（全国一等奖）摘要本文针对碎纸片拼接问题不同的规模和难度，制定了贪心策略，模拟退火，合成启发式等多样的算法策略，并利用分类思想，化繁为简，大大增加了算法效率；同时本文兼顾到问题求解的时间、人工干预时机和“距离”函数的选择，并人性化的开发了具有实用功能的计算机软件，并以此对问题进行拓展。首先，我们类比经典的TSP问题的数学模型建立过程，删除“返回起始点”的限制条件，并利用0-1规划思想建立了简洁的模型。在距离函数的选择上，本文以“实用性”为原则，舍弃了贝叶斯分类器等复杂的函数，而选择了实验效果较好的绝对值距离和欧氏距离，同时利用统计最优解和次优解的区分度对这两种距离函数做出了评价。对于问题一，在该模型的基础之上，利用贪心策略即可直接搜索出最基本问题的排列顺序。对于问题二这样规模更大，更复杂的情况，本文采用了分类思想，利用碎片的行特征，如行高，文字相对坐标等，将其划分到各个行，形成若干个子问题分别求解，最后再将解得的行进行合并。对于中文碎片，本文巧妙的提取碎片文字中心，从而确定出一个中心位置，以此为标准进行划分，无需人工干预就将所有碎片划分到了11个行。之后，利用模拟退火算法对每一个行的排列进行求解优化，最后人为进行结果的调整。而英文碎片的特征信息相对更少，考虑到英文字母的特点，本文利用灰度值密度确定碎片特征位置坐标，并以此作为划分的依据；由于英文碎片在行相对坐标上有重叠，并没有像中文纸片那样被直接划分成11个行，我们放弃了模拟退火算法，以局部优化的方式，代替了全局优化，采用更灵活的合成启发式算法，对每一次成功的拼接的碎片进行保留，同时记录失败的拼接，防止重复搜索，并设置函数判别阀值，在合适的时机由人去判别是否拼接，拼接效率较好。对于问题三中双面有字的碎片，求解问题二的方法也同样适用。本文额外设计了一种关联算法，在碎片一面拼接时同时将背面拼接好，减少了拼接次数。在此之外，我们额外对纸片的识别，如中英文纸片的区分，两张混杂在一起的纸片拼接，模式匹配等方面进行了拓展研究，并制作了简单易用的软件，使得人工干预更为方便，模型的实用性更强。本文的特色在于人性化的考虑，在成功解决问题的基础之上，利用合理的分类，高效的优化算法，大大降低了人为干预的次数，而在不得不介入人为干预的情况下，又设计出友好的程序软件，方便了人们的使用。关键词：灰度矩阵TSP问题相似性测度模拟退火算法合成启发式算法2一.问题重述与分析破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。1.1问题一的重述与分析问题一中所给出的文字图片文件仅是通过对原文件纵切形成的，要求通过建立碎纸片拼接复原模型和算法对所有图片进行排序恢复原文件。碎纸片的边缘信息可以反映该图片的特征，因此我们首先可以提取出图片的边缘信息，由于文件仅纵切，边缘处所保留的信息较多，可以不考虑中英文字的区别，取边缘信息相似的图片进行拼接可对原文件进行复原。1.2问题二的重述与分析问题二中所给出的文字图片相比较问题一来说又对图片进行了横切，我们考虑解决本题的方法依然是通过对两两图片边缘的信息进行比较，但是在加入了横切之后使得图片过小，边缘信息缺失过多可能导致拼接的结果并不是很理想，因此，我们在问题二中需要考虑对图片提取文字特征，通过文字特征按行进行分类，再对各行中的图片进行比较拼接。1.3问题三的重述与分析问题三中所给出的碎片为双面英文文字的横纵切碎片，所以可以设计一种关联算法，将同一碎片的a面与b面联系起来，只要一面拼接好，另一面就自动拼接好。二.模型假设1.假设所有附件中给出的碎纸片图像不存在重叠部分；32.假设文件中的碎纸片没有缺失；3.假设全部碎纸片形状相同且规整。三.符号说明及名词定义四.模型的建立4.1碎纸片的预处理首先用MATLAB软件读取附件中每张碎纸片图像的灰度信息1，利用MATLAB自带的imread函数可将其自动转化为灰度矩阵：nklllllllllLijiijjk,,2,1212222111211，其中，j表示每张图像横向有j个像素点，i表示每张图像纵向有i个像素点。符号说明ijijlijdkXtYh每张碎片纵向有i个像素点每张碎片横向有j个像素点ji,处图象的灰度值两碎纸片边缘灰度的偏差距离任意纸片的右特征向量任意纸片的左特征向量中文碎片中心位置的高度4且，任意像素点的灰度值l的范围在255,0，白色为255，黑色为0。同时，我们定义：TiklllX12111为第k张碎纸片图像的右特征向量，TijjjklllY21为第k张碎纸片图像的左特征向量。考虑到实际情况，一页纸左右两端通常会有留白，所以在kL中取一个mi阶子矩阵，得到：nklllllllllPimiimmk,,2,1212222111211，其中，m根据实际情况人为定义，且nm1。我们对全部子矩阵内的灰度值进行比较，白色255l出现次数最多的子矩阵所对应的碎纸片即为最左端的纸片。同理，可以确定最右端的纸片。4.2类比TSP问题的0-1规划模型TSP问题2（旅行商问题），是最基本的路线问题，该问题是在寻求单一旅行者由起点出发，通过所有给定的需求点之后，最后再回到原点的最小路径成本。类比TSP问题，我们将每一张图片当作旅行中需经过的一点，以两图片边缘灰度信息的偏差距离作为路径成本，与原问题不同的是碎纸片拼接不需要返回原点。对于n张碎纸片，定义0-1整数型变量1ijx表示，第i张纸片拼接在第j张纸片的左边，否则0ijx。特别的，根据4.1中碎纸片的预处理，很容易可以找到端点处的纸片，我们将最左端纸片的序号定为1，最右端纸片的序号定为n。则，可建立最短路径0-1规划模型，表达式如下：5;min11jixdZninjijij.,,1,,1;,,1,,1;1,0;,0.211nijixnjjixjxnixstnjijniijijij其中，ijd表示i号纸片与j号纸片边缘拼接处灰度值的偏差距离。4.3基于模式相似性测度的偏差距离模型模式识别中最基本的研究问题是样品与样品之间或类与类之间相似性测度3的问题，我们采用近邻准则判断两张碎纸片图像边缘灰度信息的相似性，将任意纸片nkk的右特征向量kX作为模板，用其他每一张纸片的左特征向量tY模板做比较，观察与哪个与模板最相似，就是模板的近邻，即t纸片排在k纸片的右边。计算模式相似性测度的距离算法有欧式距离、马氏距离、夹角余弦距离等，针对中英文文本，我们分别测试了不同的距离算法：绝对值距离：nwtwkwtkijyxYXd1欧式距离：nwtwkwtktkTtkijyxYXYXYXd122)()()(马氏距离：)(12tkTtkijijYXSYXDdikTkkXXXXNS1))((11ikkXNX11夹角余弦距离：tktTktkYXYXYXScos),(距离函数的选择并非一成不变，可根据不同的情况选择合适的距离函数。6五.模型的求解5.1问题一的求解Matlab有着强大的图像读取分析能力，在得到图像的灰度矩阵后，我们提取出所需的特征向量，即灰度矩阵第一列及最后一列，通过4.1中的方法确定放在最左端及最右端的图片，从最左端的图片(序号设为1)开始，采用贪心策略（即每一步均保证局部最优化，找出左特征向量与前一张图像右特征向量最匹配的碎片图像）并选取合适的距离函数进行比较。4.3提出了绝对值距离、欧式距离、马氏距离和夹角余弦距离等多种距离函数，此外还可以用到人工智能和模式识别领域中的分类器（如贝叶斯分类器，神经网络分类器等）。但是我们通过实践对比后发现，对于本题，大多数复杂的距离函数，并不能增加识别效果。因此，我们只考虑采用绝对值距离和欧式距离作为之后算法中的距离函数。并作出以下图象作出识别效果评价：绝对距离在中文识别中的效果评价图欧式距离在中文识别中的效果评价图图1纸片特征匹配中最优解区分度对比（横坐标为进行匹配的纸片序号，纵坐标为匹配距离）当我们对中文碎纸片进行匹配时，采用绝对距离及欧氏距离作为距离函数都具有较好的区分度。从图像上可以看出，采用欧式距离，使得每张纸片的期望拼接对象，与潜在会引起匹配错误的次优匹配对象具有更大的区分度，所以，一般情况下，采用欧式距离作为距离函数会使得匹配效果更好，有趣的是，在作英文内容的纸片匹配时，情况相反。因此，在之后的算法中，我们将更灵活的使用这两种距离函数，而不会固定为一种。最终得到的附录一及附录二的图片排序表格如下所示：最优解最优解次优解次优解7008014012015003010002016001004005009013018011007017000006表1附录一复原结果表003006002007015018011000005001009013010008012014017016004表2附录二复原结果表5.2问题二的求解5.2.1通过提取文字行特征对图片进行分类相比较问题一的碎片，问题二中碎片存在的问题有：1.图片太小使得图片边缘信息缺失过多，无法只通过提取边缘灰度信息的方法进行比较拼接。2.图片数量过多，使用全局优化耗时过大，因此，我们在求解问题二的过程中，首先根据文字的行特征对碎纸片进行分类，将原本位于同一行的碎纸片分为一类。这样，就将问题二转化成了问题一。5.2.1.1对中文文本的分类按照汉字的书写（打印）习惯，每一个字都是居中的，即同行文字的中心是处于同一水平线上的。所以，我们提取出每一张碎纸片上第一行完整文字的中心位置的信息，相同的即为一类。例如：图2附件三000如图2所示，图像顶端到第一行完整文字顶端的距离为1h，图像顶端到第一行完整文字底端的距离为2h。则文字的高度为12hhh，221hhh即为图像顶端到第一行完整文字的中心的距离，我们把它称为中心位置高度。1h2h8特别的，我们考虑到如图3的情况：图3附件三014与128显然，附件三中的碎片014与128应为同一行，但是由于碎片014包含段首空格，按照上述方法提取行特征信息得到的中心位置高度为221hhh，而碎片128的中心位置高度为221hhh。这时，比对两张碎片的中心位置就会判断它们不属于同一类，显然错误。因此，我们加入判定条件：当图像顶端到第一行完整文字顶端的距离1h大于一个行高a与字高b的和时，用bahh1表示该图像顶端到第一行完整文字顶端的距离。则中心位置为22212hbahhhh。5.2.1.2对英文文本的分类由于英文字母要按照四线三格书写，并不对称，所以同行不同字母的中心不在一条水平线上，故不能采用与中文文本一样的方法确定中心位置。通过观察可知，通常在四线三格的第二条线与第三条线处像素点的密度最大，所以我们定义四线三格的第三条线为碎片的一个特征位置。例如：图4附件四1442h1h2h1h42513679如图4，读取附件四中碎片144的灰度信息，可以据此作出灰度密度图像，如图5：图5.附件四144灰度密度图像分析可知，图4中的各极值点对应的即为四线三格的第二条线与第三条线。则可确定图像的特征位置。5.2.2基于模拟退火算法的中文碎片优化通过分类，我们最终可以划分出11类碎片，再对于每一类中的图片采用求解问题一的方法进行第一次排列作为一个初始解，再使用模拟退火算法4对初始解进行优化。中文碎片求解步骤如图6：图6中文碎片拼接步骤模拟退火法8765求解组合最优化问题的基本思想