碎纸片拼接数学模型.doc

《碎纸片拼接数学模型.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、碎纸片的拼接复原问题模型摘要本文研究的是碎纸片的拼接复原问题。针对碎纸不同的裁剪特点，我们运用相关性系数法、聚类分析法等建立不同的模型来解决不同裁剪特点和不同纸的复原问题。针对问题一，我们利用图像数字化技术，借助MATLAB软件将题目中附件1，2所给的图片转化为灰度值矩阵，并作二值化处理，然后取出每个矩阵第一列和最后一列，采用相关系数分析的方法，计算每第一列和每最后一列相关系数，根据相关系数的大小确定相邻的图片，逐步确定各图片的顺序，最后得到复原的图片。中文文档拼接的顺序为：8，14，12，15，3，10，2，16，1，4，5，9，13，18，11，7，17，0

2、，6，中文文档复原的结果见附录1；英文文档拼接的顺序为：3，6，2，7，15，18，11，0，5，1，9，13，10，8，12，14，17，16，4，英文文档复原结果见附录2。针对问题二，同样，在将图片二值化处理后，我们运用聚类分析法将纵横裁剪后的图片进行行分类，经过人工干预后，获得需要的矩阵尺寸，然后根据图片的特点运用图片的上下边界和左右边界进行二次匹配，直到找到大致正确的图片排序；同时在必要时，进行二次人工干预，直到获得正确的图片排序。关键词：碎纸片复原图像数字化相关性系数聚类法1问题重述1.1问题背景碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取

3、等领域都有着重要的应用。然而，传统的拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。本题即是通过一些模型算法开展对碎纸自动拼接技术的研究，具有重要的现实意义。1.2要解决的问题问题一：对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，要求写出干预方式及干预的时间节点。问题二：对于碎纸机既纵切又横切的情形

4、，要求设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。问题三：附件5给出的是一页英文印刷文字双面打印文件的碎片数据。要求设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果。2模型的假设及符号说明2.1模型的假设（1）假设碎纸机在碎纸时不对碎片造成损坏，可以拼接复原成完整的一页文字；（2）假设各碎纸片大小相等且规则；（3）假设同一页中，文字的种类、行间距和段落分布情况是相同的。2.2符号的说明3问题分析针对问题一，要求对来自同一页印刷文

5、字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原的模型和算法。附件1和附件2的碎纸片是经过纵切而成，想要将图片进行还原，必须要在里面取出左右边缘的值，进而对碎纸图片的左右边缘进行匹配就可以还原图像。首先将图片进行图像化处理，获得图片的像素点灰度值矩阵，转化成计算机可以识别且量化的计算机语言，其次，取出每个灰度值矩阵的第一列和最后一列列向量形成新的矩阵，并对其进行二值化处理，最后计算矩阵两列的相关系数，相关性越高，说明这两块碎纸片匹配的概率就越大，最终得出图片复原的排列顺序，将碎纸片进行复原。针对问题二，附件3和附件4的碎纸图片是经过纵切和横切而成的，相对第一

6、问而言，图片可以直接获取的信息就较少，如像素灰度矩阵变小；如果采取同第一问一样的方法，对图片的匹配而言准确度大为降低，同时还会出现更多的重复匹配。所以要进行碎纸图片还原，首相应该对碎纸进行行分类或者列分类，这里我们选择行分类，同时根据碎纸片的特点，我们进行行的左右边界匹配，以及对所得行模块进行相关性匹配，对于不能够找到最佳匹配的，我们进行人工干预，直到将整个图片进行复原。针对问题三，4图片数据处理与分析纵观整个题目，给出的附件均是一整幅图片的碎片集合。根据题目建模的相关要求，需要将图片转化为其像素点灰度矩阵，同时为了降低计算机的计算机的计算强度和为了整个题目的计

7、算过程，我们将图片的像素点灰度矩阵归置为0-1矩阵，即图片的二值化过程。5问题一的解答5.1建模思路将图片导入MATLAB软件中对图片进行预处理，以获得图片的像素点灰度值矩阵，进而转化成矩阵之间相关性计算问题。矩阵的计算过程如下：首先，在获得灰度值矩阵后，提取每个矩阵的第一列与最后一列分别得到两个分别是第一列与最后一列的矩阵；其次，把得到的新的灰度值矩阵做二值化处理；再次，利用矩阵两列的相关性系数判断其匹配程度；最后完成图片的拼接复原顺序和输出复原图片。5.2模型建立（1）分别读取19图片的19个像素点的灰度值矩阵，分别将每个矩阵的第一列取出获得新的矩阵；同时分

8、别将每个矩阵的最后一列取