基于tsp规划模型的碎纸片拼接复原问题研究

《基于tsp规划模型的碎纸片拼接复原问题研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第３卷第２期数学建模及其应用Ｖｏｌ．３Ｎｏ．２２０１４年６月ＭａｔｈｅｍａｔｉｃａｌＭｏｄｅｌｉｎｇａｎｄＩｔｓＡｐｐｌｉｃａｔｉｏｎｓＪｕｎ．２０１４檺檺檺檺檺檺殣殣檺檺建模探索檺檺殣殣檺檺檺檺檺檺基于ＴＳＰ规划模型的碎纸片拼接复原问题研究李蕾１，麻思达２，潘博渊３（１．西北工业大学自动化学院，陕西西安７１００７２；２．西北工业大学材料学院，陕西西安７１００７２；３．西北工业大学软件与微电子学院，陕西西安７１００７２）摘要：引入差异度指标描述碎纸片图像边缘的匹配程度，以差异度最小为目标建立ＴＳＰ问题的数学模型，并按照指派模型求

2、解。设计“按行聚类－行内排序”算法，以降低算法的时间复杂度；同时，对字符进行聚类分析，并利用模式识别技术降低拼接的错误率，减少人工干预；通过纵切、纵横切、双面的中英文碎纸片的复原，验证了拼接模型和算法的准确性和有效性。关键词：碎纸片拼接复原；ＴＳＰ模型；指派模型；聚类分析；模式识别中图分类号：Ｏ２９文献标志码：Ａ文章编号：２０９５－３０７０（２０１４）０２－００１２－０６破碎文件的拼接常应用于司法物证复原、历史文献修复以及军事情报获取等重要领域，然而碎纸片信息量巨大，纯手工很难完成。随着计算机技术的发展，人们试图开发碎纸片的自动

3、拼接技术，以提高拼接复原效率。目前，碎纸片的拼接研究主要是利用碎纸片的特征，如边缘、文本格式相似性等，将问题化为旅行商问［１－２］题（ｔｒａｖｅｌｉｎｇｓａｌｅｓｍａｎｐｒｏｂｌｅｍ，ＴＳＰ）、０－１规划模型等，并运用贪心算法进行求解。本文对２０１３年全国大学生数学建模竞赛Ｂ题的３种碎纸片（纵切、纵横切和双面碎纸片）提出复原方法，以差异度最小为目标建立ＴＳＰ问题的数学模型，设计“按行聚类－行内排序”算法，并运用模式识别技术降低时间复杂度和拼接的错误率，从而减少人工干预。１旅行商问题模型１，当指派Ａｉ去完成Ｂｊ工作［３－４］设ｘｉ

4、ｊ表示Ａｉ完成Ｂｊ工作，并令ｘｉｊ＝｛，则ＴＳＰ问题的规划模型为：０，当不指派Ａｉ去完成Ｂｊ工作ｎｎｍｉｎδ∑∑ｒｉｊｘｉｊ，ｒｉｊ≥０ｉ＝１ｊ＝１ｎｓ．ｔ．∑ｘｉｊ＝１，ｉ＝１，２，…，ｎｊ＝１ｎ∑ｘｉｊ＝１，ｊ＝１，２，…，ｎ。ｉ＝１∑ｘｉｊ≤｜Ｓ｜－１，２≤｜Ｓ｜≤ｎ－２，Ｓ｛１，２，…，ｎ｝ｉ，ｊ∈Ｓｘｉｊ∈｛０，１｝，ｉ，ｊ＝１，２，…，ｎ其中，ｒｉｊ表示Ａｉ完成Ｂｊ工作的效率，由ｒｉｊ组成的方阵Ｒ＝（ｒｉｊ）ｎ×ｎ称为效率矩阵。由于ＴＳＰ问题是一个典型的ＮＰ完全问题，求解存在很大的难度。注意到第３个约束条件是保证最

5、优解只有一个环。如果不考虑该约束条件，ＴＳＰ问题的规划模型就化为了指派模型。当指派模型求出的最优解恰好只有１个环时，则其解即为ＴＳＰ问题规划模型的最优解。根据碎纸片拼接复原问题的特点，可以按照指派模型求解ＴＳＰ问题。收稿日期：２０１４－０３－２７通讯作者：李蕾，Ｅ－ｍａｉｌ：６４６４５２３６９＠ｑｑ．ｃｏｍ·１２·第３卷第２期数学建模及其应用Ｖｏｌ．３Ｎｏ．２Ｊｕｎ．２０１４本文通过对碎纸片边界像素的比较分析，定义碎纸片间的差异度δ为两块碎纸片邻边像素的灰度差的绝对值，以这个差异度最小为目标建立ＴＳＰ问题的数学模型，求解并给出拼

6、接方案。下面根据差异度δ给出纵切、纵横切、双面碎纸片的拼接模型和求解算法。２纵切碎纸片的拼接针对２０１３年全国大学生数学建模竞赛Ｂ题的纵切碎纸片的拼接复原问题，规定最左边一片为第０片，最右边一片为第１８片，每片碎纸片的像素是１９８０×７２，建立ＴＳＰ问题的规划模型：１８１８ｍｉｎδ＝∑∑ｒｉｊｘｉｊｊ＝０ｉ＝０１８ｓ．ｔ．∑ｘｉｊ＝１，ｊ＝１，２，…，１８ｉ＝０ｎ∑ｘｉｊ＝１，ｉ＝０，１，２，…，１７。ｊ＝１∑∑ｘｉｊ≤｜Ｓ｜－１，２≤｜Ｓ｜≤ｎ－２，Ｓ｛１，２，…，ｎ｝ｊ∈Ｓｉ∈Ｓ１，第ｉ片与第ｊ片邻接其中：ｘｉｊ＝，ｉ，ｊ

7、＝０，１，…，１８，ｉ≠ｊ，ｘｉｉ＝０；ｒｉｊ表示碎片ｉ和ｊ之间的差异度，定｛０，其他义为ｒｉｊ，ａｉ表示第ｉ片碎纸片的第ｋ行第ｌ列的像素点的灰度值，ｋ＝１，２，…，１９８０，ｌ＝１，ｉｊ＝｜ａｋ，７２－ａｋ，１｜ｋ，ｌ２，…，７２，ｒｉ０＝ｒ１８ｊ＝∞。利用Ｍａｔｌａｂ函数ｂｉｎｔｐｒｏｇ求解相应指派模型，得出纵切碎纸片的复原最优解：中文的碎纸片复原从左到右顺序为００８，０１４，０１２，０１５，００３，０１０，００２，０１６，００１，００４，００５，００９，０１３，０１８，０１１，００７，０１７，０００，００６；英文的碎纸片复

8、原从左到右顺序为００３，００６，００２，００７，０１５，０１８，０１１，０００，００５，００１，００９，０１３，０１０，００８，０１２，０１４，０１７，０１６，００４。值得注意是，该拼接过程无需人工干预。３纵横切碎纸片的拼接３．１模型建立２０８２０８对于２０８片