碎纸片拼接复原(国一).doc

基于分治算法碎纸片的拼接复原模型 摘要 本文针对不同切割方式碎纸片的拼接问题，通过对图像数字化处理得到灰度矩阵，建立了复原模型并得到复原后的图像。 针对单面仅纵切碎纸片的拼接问题，根据完整文件最左边部分无文字的特点，运用matlab编程可确定出第一张碎纸片。随后，根据贪婪算法的思想，以确定位置的碎纸片与剩余未拼接碎纸片相邻边缘灰度值的平方欧氏距离最短为目标函数，可逐步求得碎纸片的拼接顺序,进而将其复原.中文碎纸片顺序为：8、14、12、15、3、10、2、16、1、4、5、9、13、18、11、7、17、0、6；英文碎纸片顺序为：3、6、2、7、15、18、11、0、5、1、9、13、10、8、12、14、17、16、4。本问碎纸片拼接过程没有人工干预，实现了全自动化的拼接。 对于既横切又纵切碎纸片拼接问题，本问采用分治算法的思想，先对中、英文碎纸片分别层次聚类分析，将最可能位于同一行的碎纸片归为同一类，其中中文碎纸片分为11类，英文碎纸片分为10类；再对分类后的碎纸片使用编程加人工干预的半自动拼接方式，得到11块仅横切的碎纸片块；最终对得到的11块仅横切的碎纸片块进行类间拼接，实现文件的复原。中文碎纸片第一列顺序为：49、61、168、38、71、14、94、125、29、7、89；英文碎纸片第一列顺序为：191、201、86、19、159、20、208、70、132、171、81。此问中有两次人工干预的过程，第一次位于类内拼接处，第二次位于类间拼接处。中文文件总共干预了33块，英文文件总共干预了40块。 考虑双面碎纸片拼接问题时，本问延续了分治算法的思想。由于每张碎纸片含有正反两面，在聚类分析时，可将正反两面的灰度值相加为一列特征值作为它们是否可能位于同一行的依据，进而将双面碎纸片分为9类。再对这9类碎纸片使用编程加人工干预的半自动拼接方式，得到22块仅横切的碎纸片块；最终对这22块仅横切的碎纸片块进行类间拼接，实现文件的复原。复原后文件第1面第一列顺序为：136a、5b、143a、83b、90b、13b、35b、172b、105b、9a、54b；复原后文件第2面碎纸片第一列顺序为：78b、89a、186b、199b、88b、114a、146a、165b、3b、23b、99a。此问中有两次人工干预的过程，第一次位于类内拼接处，第二次位于类间拼接处。 【关键词】：碎纸片复原 贪婪算法 平方欧氏距离 分治算法 层次聚类分析 一、问题重述 破碎文件的拼接在司法物证复原、历史文献修复获取等领域都有重要的应用。传统上，复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸的自动拼接技术，以提高拼接效率。对于给定的来自同一页的片（仅纵切），建立碎纸拼接算法，并针对附件1给出的数据进行复原对于碎纸机纵切横切的情形，模型和算法，并针对附件给出的数据进行复原。从现实出发，模型与算法 碎纸片数字化后第张纸片的第行第列数据，即该点灰度 第张纸片的最后一列与第张纸片第一列第行数据平方欧氏距离 未匹配碎纸片的集合 第类碎纸片离差平方和 五、建模前的准备 图形的数字化【2】 本文是根据碎纸片内文字行特征来进行判定碎纸片的拼接。故现在的关键是提取碎纸片内的文字信息。这就不得不提到matlab对图形的处理方法，即图形的数字化。 图形的数字化是将连续色调的模拟图像经采样量化后转换成数字影像的过程。，其中和是平面坐标，在坐标点处的振幅称为图像在该点的亮度。黑白图像的亮度用灰度来表示，而彩色图像是由单个的二维图像组合而成的。图像的数字化过程如下面的流程图1所示： 图1 图形的数字化流程图 根据上图1图形数字化流程图，对以上步骤进行具体解释： （1）图形的采样 图形的采样即要求要用多少点来描述一幅图像，采样结果质量的高低用图像的分辨率来衡量。简单来讲，对二维空间上连续的图像，在水平和垂直方向上等间距地分割成矩形网状结构所形成的微小方格称为像素点。一幅图像就被采样成有限个像素点构成的集合。本题中所给碎纸片为bmp格式，运用matlab程序读取后，该图像数字化为个像素点。 （2）量化 量化即要求使用多大范围的数值来表示图像采样之后的每一个点。量化的结果是图像能够容纳的颜色总数，它反映了采样的质量。本文采用8位储存一个点，即相当于黑-白间可用0-255个状态进行描述，其中量化后的值越接近0，则表示该点的实际颜色越接近黑色；相反量化后的值越接近255，则表示该点的实际颜色越接近白色。 由破碎图片的数量可知，本题中的复原图像经过采样和量化后的结果是一个实数矩阵。由采样过程可知，该矩阵大小为。matlab中读入图像的数据类型为unit8，而在矩阵中使用的数据