高教社杯数学建模比赛论文碎纸片的拼接复原.doc

碎纸片的拼接复原 摘要 破碎文件的拼接在司法物证复原、历史文献修复获取等领域都有重要的应用。随着计算机技术的发展，人们试图开发碎纸的自动拼接技术，以提高拼接效率。的列矩阵，即将纸片分成11条横条。再对横条进行拼贴得到整幅修复纸片。观察、并进行句法、语义逻辑性分析，如果不合适时进行人工干预。 对于问题三，是在问题二上的一个深化，首相，同样将a,b两个图转换为其灰度矩阵，之后得出418片纸片最左边全为空列的列数，最右边全为空列的列数，根据纸条在正反面规律可只最边条的为空列数是一个镜面对称问题，根据此性质选取处于边界的22张纸片，然后根据英文字母中间部分全充满的性质，利用画图工具来选取最边的22条中对应的处于同一行的18条，将纸条分成22类，最后将每一类仿照问题1方法按序拼成22条横向纸条，最后将22条横向纸条拼接一起，最后对纸条位置进行干预，分成两张。 关键词：碎片拼接；灰度矩阵；matlab； 一、问题重述 破碎文件的拼接在司法物证复原、历史文献修复获取等领域都有重要的应用。传统上，复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸的自动拼接技术，以提高拼接效率。对于给定的来自同一页的片（仅纵切），建立碎纸拼接算法，并针对附件1给出的数据进行复原对于碎纸机纵切横切的情形，模型和算法，并针对附件给出的数据进行复原。从现实出发，模型与算法 第i张碎纸片经matlab生成生成的灰度矩阵 定义i张碎纸片经matlab生成生成的对应的k行，j列，19层的灰度矩阵； 提取矩阵每i层最的第1列定义的新矩阵； 提取矩阵每i层最的最后1列定义的新矩阵； s 和的差的平方和； 第二问中由行间距筛选备选矩阵的筛选矩阵； 四、问题分析 对于问题一： 由于题目中所给的图片不存在破损，经碎纸机切割后，扫描入计算机的文件可近似看做是完美的矩形，因此可将图片导入matlab处理，得出其灰度矩阵，以此来表示碎纸片中字、残缺字的位置及分布。观察第一张纸条左边沿有较多的空白边，因此在灰度矩阵中挑选出第1列全等于255的矩阵的则为第一张纸条。 与此相对应，原来相对应的两张纸片A、B对应的灰度矩阵a的最右列和灰度矩阵b的最左列是可以完全吻合的，具有较高的相似度。采用此两列的差的平方和作为相似度判定依据，从后18个灰度矩阵的第一列依次与第一张纸片的灰度矩阵的最后一列作相似度比较，则差的平方和最小的值所在的列为第二张纸片。依次连接可得到修复图片矩阵，再由matlab生成修复图片。 照此模型对英文进行排序，来检验模型是否具有普适性。 对于问题二： 在此问题中，经碎纸机切割后存在碎至为一个11×19的矩阵，根据碎纸片特点，复原好位于第一列的纸片左端有较宽的白色边沿，因此将这11×19份碎纸片经matlab转化生成灰度矩阵后，对应的求出灰度矩阵的满足全等于255的列最多的矩阵，取前11张作为复原矩阵的第一列的11张纸片。然后，分别以这11张纸片为第一列，通过相同行行间距相同，进行筛选，每行选出40个灰度矩阵作为备选矩阵。以这通过按问题一的方法，依次进行拼接，得到11个的列矩阵，即将纸片分成11条横条。再对横条进行拼贴得到整幅修复纸片。观察、并进行句法、语义逻辑性分析，如果不合适时进行人工干预。 对于问题三： 在第二问的基础上，第三问进一步加深，且每片纸片a,b具体属于哪一面是不知道的，为一个处理两面全为英文的碎纸片修复问题。其基本思路在第二问上稍加优化，首先将存放a.bmp的图片b.bmp的图片用matlab处理得到两个矩阵，分别找出中每张纸片最左侧全为空白列数counta1,countb1,以及其最右侧全为空白的列counta2,countb2.。根据4列数来选取其中最适合的22片纸片作为原纸张两侧最右侧的那22张纸片，之后根据字母中间部分高度相同利用绘图板分别选取与22张最边对应的18条，然后将这18条按差的平方和大小依次排到成条，得到22张纸条，最后将22条按行排到一张纸，最后将那张纸拆分成两张。 五、模型的建立和求解 5.1 问题一的建模与求解 经观察检验附件中所给的图片不存在破损，经碎纸机切割后，文字的每一部分都会出现在分割后纸条片上，原来相连文字、标点被分割后，那么这两块的墨迹还可以对应上。首先将图片导入matlab处理，得出其灰度矩阵，根据对应灰度矩阵分布来确定碎纸片中字、残缺字的位置及分布。若A、B原为两相接的碎纸片，则 A、B对应的灰度矩阵a的最右列和灰度矩阵b的最左列具有较高的相似度，即a与b差的平方和是最小的。现选取纸条T，将纸条T的最左列t与其他所有纸条的最右列分别求其差方，得到与t差的平方和最小的即为与T最吻合的那一条，然后依次求直至所有纸条用完。 5.1.