基于0-1规划碎纸片的拼接复原分析模型摘要本文是对碎纸片的拼接复原问题进行分析。通过提取碎片间的边缘灰度特征和文字行位置特征差异,建立以总体差异程度的最小范数值为目标函数的0-1规划模型，运用MATLAB软件进行求解，配合少量人工干预，可实现单面与双面文件既被纵切又被横切后的碎纸片的二维拼接复原的目标。我们先将题目中给出的附件一至附件五的碎纸片进行分析，对三个问题进行算法分析和建立数学模型，解决碎片复原中的三个问题。对于问题一，由于是单面文件且大小相同的碎片，利用MATLAB软件将各碎纸片分别转化为其灰度值矩阵，得出两碎纸片左右边缘灰度值向量差异与文字行位置的差异。最后再建立一个优化模型进行复原过程的修复，建立模型一，使复原率尽量达到100%。对于问题二，我们采用0-1规划拼接模型分析，方法和问题一的处理方法相同，并提出利用欧氏距离和贪婪算法进行模型求解，同时利用由碎片组成的文件数据进行模拟仿真处理，配合少量人工干预，可实现单面既被纵切又被横切后的碎纸片的二维拼接复原的目标，建立模型二。经过显示，复原效果较好。对于问题三，我们在问题一和问题二的0-1规划拼接模型的基础上充分利用双面文本的特征信息，建立碎片的MATLAB中的聚类算法模型，这样可大大提高复原率，建立模型三。配合少量人工干预，实现双面文件既被纵切又被横切后的碎纸片的二维拼接复原的目标。最后，我们对于问题三的基础上自行构造碎片进行拼接复原，用来检验与评价本文的算法与模型。要尽量使得对三种不同特点碎片复原的人工干预次数较少尽可能实现碎片复原的全自动化。关键词：0-1规划模型优化模型仿真处理贪婪算法聚类算法一、问题重述破碎文件的拼接在物证司法复原、历史文献修复以及军事情报获取等领域都有着重要的应用。随着计算机技术的发展，提高拼接复原效率的碎纸片自动拼接技术被试图开发，讨论问题如下：1.对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达。2.对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，复原结果表达要求同上。3.上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。并就附件5的碎片数据给出拼接复原结果。二、问题分析问题一是对被纵切的碎片还原的问题，考虑到碎片的拼接问题是找到碎片与碎片之间最好的排列问题，利用MATLAB软件将各碎纸片分别转化为其灰度值矩阵，得出两碎纸片左右边缘灰度值向量差异与文字行位置的差异，最后再建立一个优化模型进行复原过程的修复。问题二是对既被纵切又被横切的碎片还原。先考虑纵切，对一些在同一行的碎片可用问题一的拼接策略解决。再考虑到横切，我们采用0-1规划拼接模型分析，我们可以将拼接好的碎片用拼接策略拼接起来得到最终的还原纸张。并提出利用贪婪算法进行模型求解，同时利用由碎片组成的文件数据进行模拟仿真处理问题三是对双面碎片的还原，我们可以用解决问题二的方法得到一些拼接好的碎片行，用类似问题一的方法将碎片行拼接起来，但此时由于碎片有正反面之分，所以我们在0-1规划拼接模型的基础上充分利用双面文本的特征信息，建立碎片的聚类算法模型，这样可大大提高复原率。三、模型假设1.所有碎纸片来自同一张纸片。2.所有碎纸片能够拼成一张完整的纸片。3.所有碎片尺寸大小相等，边缘轮廓为规则的矩形。4.所有碎片中的文字颜色一致，且与背景颜色有较大反差。5.所有碎片中的文字是从左至右、从上至下书写的。6.所碎片都已摆放端正，即碎片中的文字端正。四、定义与符号说明序列符号符号说明1二值化后矩阵2后侧的图片矩阵3左侧图片矩阵数减右侧图片矩阵数之差4横纵矩阵的的匹配值5碎片左右上下欧氏距离6W总体欧氏距离7a,b行列8上端裁截处裁接的字体长度9行间距10图片上端文字与切割线之间的空白距离11字体高度12梯度算子（用于形态边界的提取）五、模型的建立与求解5.1问题一的分析与求解5.1.1.对问题的分析问题一是对仅被纵向剪切单面印刷文字的碎...