基于SACO算法的碎纸片拼接复原模型_杨凌.pdf

第 卷第期 年 月太 原 师 范 学 院 学 报（自然科学版）（）基于 算法的碎纸片拼接复原模型杨凌王琳琳刘冲冲苏思美（安徽财经大学 统计与应用数学学院，安徽 蚌埠 ）摘要破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用 文章基于灰度图像原理和欧氏几何理论，定义了列约束匹配准则，分别设计了基于列约束匹配准则的欧氏距离变换算法、类蚁群优化算法 ，建立了欧氏距离变换模型、类蚁群优化算法的碎片拼接等模型，对碎纸片的拼接复原问题进行了相应的求解 关键词碎纸片的拼接复原；列约束匹配准则；类蚁群优化算法；欧氏距离；文章编号 （）中图分类号 文献标识码引言常规文档碎纸片计算机拼接方法一般利用碎片边缘的尖点特征、尖角特征、面积特征等几何特征，搜索与之匹配的相邻碎纸片并进行拼接，这种基于边界几何特征的拼接方法并不适用于边缘形状相似的碎纸片，当然也不适用解决通过破碎机破碎纸片的拼接与复原问题碎纸机破碎纸片时，会产生很多形状相同的矩形碎纸片，所以在碎纸片拼接时如果只利用碎片的边界特征，并不能实现碎纸片的复原因此，对这类边缘相似的碎纸片的拼接，理想的计算机拼接过程应与人工拼接过程类似，即拼接时不但要考虑待拼接碎纸片边缘是否匹配，还要判断碎片内的字迹断线或碎片内的文字内容是否匹配 然而由于理论和技术的限制，让计算机具备类似人那种识别碎片边缘的字迹断线、以及理解碎片内文字图像含义的智能几乎不太可能 但是利用现有的技术，完全可以获取碎片文字图片的数字信息，拼接碎片时如利用这些信息并结合人工干预进行拼接，就能在保证准确率较高的前提下，提高拼接效率数据来源与模型假设 数据来源本文数据来源于 年高教杯全国大学生数学建模比赛题的个附件 模型假设）假设碎纸机切割的小碎片的大小相同且形状规则；）假设文件被切割后的所有碎纸片均齐全；）假设碎纸片正反两面的内容有差异；）假设碎纸片没有材质以及颜色方面的差异理论准备 匹配指标的确定对于碎纸机仅纵切文件所产生的碎纸片的拼接复原，关键在于明确匹配指标 根据灰度图像原理以及欧氏几何理论，可以定义列约束匹配准则如下：设有两个阶矩阵，（），（）将两矩阵分别按列分块如下：（，），（，）其中，分别表示矩阵的第列与矩阵的第列所作成的维列向量，且：收稿日期：作者简介：杨凌（），女，山东禹城人，安徽财经大学统计与应用数学学院副教授，主要从事数值计算与优化理论的研究（，），（，）定义称（）槡为向量与的距离，记为，即（）槡定义设矩阵（），且设 为矩阵的第行的最小值，则称的第列与的第列为最佳匹配的边界组合基于列约束匹配准则，可以对碎纸机破碎的纸片建立拼接复原模型和算法 算法设计算法基于列约束匹配准则下的欧式距离变换算法：）将 张图片转化为 个 阶矩阵，分别取每个矩阵的第一列和最后一列作矩阵（，）和（，），其中：为第张图片所对应矩阵的第一列所作成的 维列向量，为第张图片所对应矩阵的最后一列所作成的 维列向量；）计算向量与的距离：，；）对固定的，找出，的最小值，记为，即 则对应的第张图片与对应的第张图片即为最佳匹配的边界组合；）人工干预，运用排除法确定异常行所对应图片的最佳匹配边界；）根据计算机以及人工干预所选取的最佳匹配的边界组合，进行碎片拼接；）输出复原的图片时间节点：在碎纸片拼接过程中进行人工干预的时间节点是在算法的第三步之后进行，即在矩阵中出现异常行时进行人工干预，找出最佳碎纸片边界的最优匹配组合根据所设计的算法，建立欧氏距离变换模型，并利用 软件进行详细求解算法类蚁群优化算法（，）：）取一小碎版式，记为，其表示第张小碎条（序号为（），遍历其余的 张小碎片，依据算法，计算向量与的距离：，找出与横向匹配的所有碎片链；）将找出的横向匹配的碎片，依次进行横向扩展拼接，将其拼接成一横条，记为；）以横条为初始基点，以纵向为延展方向进行扩充，向上或向下寻找与其匹配的碎纸片，并将找到的匹配碎片与拼接成一张图片，记为；）重得以上操作，直至整张图片拼接完整；）人工干预：对图片中的空白处采用人工干预的方法，人工找出匹配的小碎片，并将找出的小碎片插入与其相匹配的空白处；）输出复原的图片根据所设计的算法，建立类蚁群优化算法的碎片拼接模型，并利用 软件进行详细求解碎纸片的拼接复原模型 基于类蚁群优化算法（，）的拼接复原模型碎纸机破碎的纸片，既可能有纵切又可能有横切的情形，为建立合理的模型，考虑先对所有碎纸片进行横向拼接，利用聚类的思想，将零散的碎纸片大致形成一些横条，再根据碎纸片连接的唯一性，以某些横条为基点，以纵向为延展方向进行扩充，向上或向下寻找与其匹配的碎纸片 当某个碎纸片所对应的上下两边均找不出与之对应的边界时，可以跳过这个基点在横条中寻找另一个碎纸片作为新的突破点，直至找不到新的路径进行扩充为止 最后，对于仍然存在的一些空白区域，通过人工干预用余下的零散的碎纸片便能轻易地填充，由此对纵横切碎纸片建立拼接复原模型和算法太 原 师 范 学 院 学 报（自然科学版）第 卷由于位图图像表示将图像中每一个像素点转换成一个数据，整幅图可视为一个数字矩阵 因此，可以先通过 软件编写循环程序将碎纸片图像读成矩阵的形式，由此即可得到各个图片的数据信息对于任一张图片与其他图片的匹配度的度量，选取欧氏距离进行计算，此时所求的的欧氏距离既包括碎纸条的左右两边，也包括其上下两边其次，对每张图片生成的矩阵提取该矩阵的第一列和最后一列，得到两个新矩阵 最后，利用 软件中的 命令求出首端矩阵的每一列与尾端矩阵对应的列的欧氏距离鉴于录入、提取和求解距离的原理一样，在 中所编写程序的命令相同，依据算法 类蚁群算法，利用 软件编写程序，直接输出最匹配边界对应图片序号，并将部分结果摘录如表所示表碎纸片的最匹配边界组表横向最匹配边界组纵向最匹配边界组 说明：这里只列出了碎纸条横向以及纵向能够匹配的最优匹配边界组其中，第张碎纸图片的第一列形成的矩阵为，用以表示其左边界；第张碎纸图片的最后一列形成的矩阵为，用以表示其右边界第张碎纸图片的第一行形成的矩阵为，用以表示其上边界；第张碎纸图片的最后一列形成的矩阵为，用于表示其下边界表示第张碎片（碎片序号为（）与第张碎片（碎片序号为（）有最优的横行匹配边界；表示第张碎片（碎片序号为（）与第张碎片（碎片序号为（）有最优的竖行匹配边界人工干预过程：根据所得出的最匹配的边界组合，先按照上述最优横竖匹配边界的组合顺序，按行对碎纸片进行拼接得到一些横条再按左右匹配边界的组合顺序对横条进行扩充例如，对已拼接完成的横条进行扩充，其示意图如图所示，拼接后的横条见图 图已经拼接完成的横条示意图图拼接完成的横条图在扩充过程中，可能会遇到以下两种状况：）通过对某一行某些元素作为基点按照某个方向进行筛选，均未能找到能继续扩充的下一张图片，此时应该改变找寻路径，或者改变方向，或者重新选取基点）通过对某一行所有元素作为基点按照某个方向进行筛选，发现均能与某一碎纸片（如碎纸片边界序号为）进行匹配，说明可能存在分段空行的情况，此时应该重新选取横条生成新的段落通过 软件将碎纸片图像读成矩阵的形式，再将这些按照最匹配边界的组合顺序放在一起以图片的形式输出，即可得到复原的图片 纵横切且双面打印文件碎纸片的拼接复原对于纵横切双面打印文件的碎纸片拼接复原问题，不仅要考虑怎样将这些无序散乱的碎纸片进行有序的排列组合，还需要考虑不同碎纸片正反两面的对应问题 可以将同一文件的正反两面近似看做将原文件扩展两倍后所形成的的一个大的新文件，所以附件中所给的纵横切碎片数据也就可以看做来自同一文件纵横切之后所产生的碎纸片 这样就将问题转化为样本容量扩大后的纵横切碎纸片的拼接复原问题，结合算法和算法，可以建立以下：基于欧式距离的拓展的类蚁群算法模型，对双面打印文件的碎纸片的拼接复原问第期杨凌等：基于 算法的碎纸片拼接复原模型题进行相应的求解先将图片信息写入 软件中，编写程序，计算出最优匹配边界组合，先摘录部分结果如表所示表碎纸片的最匹配边界组表横向最匹配边界组纵向最匹配边界组 通过 软件将图像读成矩阵的形式，再将这些按照最匹配边界的组合顺序放在一起以图片的形式输出，即可得到复原的图片结束语模型基于碎片的切割特征，给出了碎片的半自动拼接方法主要依据列约束准则以及类蚁群算法的碎片半自动拼接模型，该算法不依赖碎片的几何特征，容易实现，结合人工干预，碎片复原率可达 ，可信度很高参考文献：罗智中基于文字特征的文档碎纸片半自动拼接华东交通大学：机电工程学院，（）：何鹏飞基于蚁群优化算法的碎纸拼接控制科学与工程，（）：赵玉峰计算机图形学的发展及应用科技信息，（）：（，），（），；太 原 师 范 学 院 学 报（自然科学版）第 卷