碎纸片的拼接复原模型.docVIP

碎纸片的拼接复原模型 摘要 本文研究碎片纸的拼接复原问题。 对于问题一，我们先将附件一、二给出的所有图片进行数字化，再进行二值化，然后利用“偏差法”计算两张图片相邻边缘二值列向量的偏差度。通过这样依次做偏差，得到偏差度最小者为相邻接的两张图片，由此可以逐步复原所有碎片。 中文复原结果如下表所示： 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组，每组19个碎片。分组的方法主要采用的是相关系数法和行间距法。分好组后，我们采用先左右后上下的拼接方法进行复原拼接。同一组的左右拼接方法是类似于问题一采用的方法；上下拼接的方法是：对于左右拼好的11块进行分类，分成两类，一类是文字有被横切割的，一类是文字没有被横切割的。先将有文字被切割的块，利用偏差值进行上下拼接。对于没有文字被切割的块利用行间距进行上下拼接。 对于问题二的英文拼接问题，我们找出 52个字母的大、小写的二值矩阵模板，依次用模板及相关匹配值检测出各张图的相应的最大匹配值，进行上下左右四个方向的拼接，而后在适当的人工干预即可复原所有碎片。 对于问题三，我们利用问题二得到的模板，然后对每幅图都进行正反面检测，当图片的a，b两面的匹配度之和最大时，我们认为此时的图片为最佳匹配图片。以此类推，每次均以得到的模板匹配字母有被切割的图片，得到最佳匹配图片，直至将所有字母有被切割的图片匹配完为止，然后人工干预，将剩余的字母会被切割的图片匹配完为止。 关键词：数值化 二值化 拼接 偏差值 相关系数 一、问题重述 破碎文件的拼接在司法物证复原、历史文献修复获取等领域都有重要的应用。传统复原工作由人工完成，准确率高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成。随着计算机技术的发展，开发碎纸的自动拼接技术，以提高拼接效率。 1. 对于给定的来自同一页的片（仅纵切），建立碎纸拼接算法，并针对附件1给出的数据进行复原 2. 对于碎纸机纵切横切的情形，模型和算法，并针对附件给出的数据进行复原。 3. 上述所给碎片数据均为单面打印文件，从现实出发，模型与算法 （一）模型假设 1.假设所有碎片纸张平整，规格一致、边缘整齐，字迹清晰。 2.假设图片经过碎片机切割经扫描后文字（英文字母）笔画没有变形。 3.假设图片经过碎片机切割后的图片的躁声比较微小。 4.假设图片经过碎片机纵切和横切后分成了19列整齐的碎片。 5.假设图片中文字的相邻两行的行间距一样。 6.假设图片中文章开头的第一列与左边的边界的距离都相等，且最左边及最右边一列 的文字均没有被切割。 7. 假设图片中同一行的的文字所占的行高都相同。 （二）符号说明 表示第张图片最右侧一列第i行的二值数字 表示为第张图片最右侧一列第i行的二值数字 表示为第张图片最右侧一列与第张图片最左侧一列的偏差值 表示为第张图片最右侧一列与其余图片的最左侧一列最小偏差值 （三）问题分析 针对中英文碎片纵切即碎片呈条状的情况。根据假设1，我们认为纵切碎片是规格化的，图像中的字迹是工整清晰的，忽略纸张中个别污点，把图像理想化成一张黑白图像。我们采用数学语言与软件相结合的方法，把图像导入matlab中进行数字化，将所有图片的像素点提取为向量并将其二值化为0,1。转换成数学语言，利用碎片边缘呈现的数字特征进行匹配拼接，假设出一个可以表示匹配程度的量，根据这个量进行逐次匹配。最开始我们从实际出发，认为纸张是有页边距的，也就是说我们可以从图像集中尝试着找出纸张的左边缘碎片和右边缘碎片，因为这两张具有最明显的特征，即左右边缘的文字均没有被切割，如果可以找到这样的碎片图像，我们就能以左边缘图像为首张图片再根据数字特征进行匹配。以此类推，直至找出正确的顺序。 （四）模型的建立与求解 第一步，我们找出首尾的两幅图片。即我们需要人工找到最左边和最右边的两幅图片，根据假设8，这张图片第一列文字左边部分没有被切割（中文图片的首尾分别为编号008,006，英文图片的首尾分别为编号003,004）。 第二步，我们将图片数值化。即用matlab将每一幅中文图片的像素点读入为（灰度）数值距阵A（距阵中的每一个元素都是介于0：255的整数）。 第三步，图片的数值距阵二值化。图像大小为1980行72列，在逻辑上将图像分为1980*72个点，对最左边一列从上至下取各格的值，超过一定阈值的设为1，未超过的设为0（有的格中既有黑色笔画也有白色底色，用阈值控制）。我们选定一个合适的阈值125并利用