碎纸片的拼接复原问题大学生数学建模全国一等奖论文.doc

1、碎纸片的拼接复原问题摘要 为解决碎纸片的拼接复原问题，我们通过定义差异度指数、高度差，建立0-1规划模型，使用聚类分析、MATLAB搜索算法和人工干预等相结合，得到了所有附件复原序号和复原图片。 针对问题一，首先提取附件1、2中所有碎片左侧和右侧边缘灰度，通过任意列碎片右侧和任意列碎片左侧的边缘灰度差值可以定义差异度指数，从而得到差异度特征矩阵，然后建立0-1规划模型，以第i张碎片右侧与第j张碎片左侧差异度最小为目标函数，以第i张碎片右侧与第j张碎片左侧是否相连为决策变量，以每张碎片右侧一定与某张碎片左侧相连、每张碎片左侧一定与某张碎片右侧相连为约束条件。算法为先提取任意张碎片边缘灰度值，得到差异度矩阵，带入规划模型中，通过LINGO软件找到中英文碎片的拼接方法，得到复原序号如表一、表二，从而得到出中文与英文复原图片。 表一:中文碎片的复原序号008014012015003010002016001004005009013018011007017000006 表二：英文碎片的复原序号00300600200701501801100000500100901301000801201401701

2、6004检验中英文碎片拼接复原顺序准确性，利用MATLAB搜索算法，可以得到中英文碎片拼接方法。结果表明两种方法得出的中英文复原顺序相同，复原图片相同，同时人工检验中英文复原图片中无明显语法、单词错误，证明复原图片准确。针对问题二，由于每张碎片有左侧、右侧和上侧、下侧，与问题一相同，可以定义两个差异度指数，建立双目标0-1规划模型。但由于差异度矩阵过大，决策变量复杂，我们又建立了改进的简化模型，定义高度差，运用聚类分析方法，按照高度不同将所有碎片分为18类，然后再以第j块碎片左侧与第i块碎片右侧的差异度最小为目标函数，以第i块碎片右侧与第j块碎片左侧是否相连为决策变量，以每块碎片右侧一定与某块碎片左侧相连、每块碎片左侧一定与某块碎片右侧相连，满足高度差阈值为约束条件，建立单目标0-1规划模型。算法为先提取任意块碎片边缘灰度值和高度，得到差异度矩阵，编程将中文碎片按高度分为18类，人工干预分为11行，再利用问题一中碎片纵向复原方法，得到中文复原序号，画出中文复原图片。（英文复原模型相似，仅高度差阈值不同）针对问题三，对于双面英文碎片的复原问题，我们提出了单词残缺程度的定义，定量的描述了英

3、文碎片的特征信息，构成了算法的核心内容，运用编程和人工干预将碎纸片分为11类，每类19个碎片，在此基础上利用前两问所建的0-1规划模型，再加上双面的一些约束条件，得到双面英文复原序号，并绘出英文双面复原图片。 关键词：差异度指数；0-1规划；LINGO软件；聚类分析；高度差；残缺程度； 一、问题重述破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。请讨论以下问题：1. 对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达。2. 对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干

4、预，请写出干预方式及干预的时间节点。复原结果表达要求同上。3. 上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果，结果表达要求同上。二、模型假设1.假设每个碎纸片上的字和字母都没有发生扭曲。2.假设每个碎纸片的形状和大小完全相同。3.假设每个碎纸片上灰度值的提取都是完全正确的值不等于255的都是黑点三、符号说明符号符号的含义差异度指数，表示第张碎片右侧和第张碎片左侧的差异度；表示第张碎片右侧第k个特征点的灰度值；决策变量，当=0时，表示第张碎片右侧和第张碎片左侧的不相连； =1时，表示第张碎片右侧和第张碎片左侧的相连；表示第j列碎片左侧与差异度最小的第i列碎纸片右侧相连；表示第块碎片右侧和第块碎片左侧的差异度；表示第块碎片下侧和第块碎片上侧的差异度； 表示第块碎片右侧第k个特征点的灰度值； 表示第块碎片下侧第k个特征点的灰度值；=0时，表示第张碎片右侧和第张碎片左侧的不相连；=1时，表示第张碎片右侧和第张

5、碎片左侧的相连； =0时，表示第张碎片下侧和第张碎片上侧的不相连； =1时，表示第张碎片下侧和第张碎片上侧的相连；高度差表示第i块碎片第一行文字中心到第i碎片上侧边缘的高度与第j块碎片第一行文字中心到第j碎片上侧边缘的高度之间的差值；四、问题一分析与模型建立、求解4.1问题一的分析问题一要求对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。参考文献1，由于每列中文和英文碎片都有左侧和右侧，需要考虑每一列碎片的左侧和右侧与其他列的左侧和右侧差异，每列碎片边缘灰度已知，通过任意列碎片右侧和任意列碎片左侧的差异值可以定义差异度指数（同一列碎片的左侧与右侧的差异度定义为无穷大），从而得到差异度特征矩阵。然后可以通过0-1规划模型，以第j张碎片左侧与第i张碎片右侧的差异度最小为目标函数，以第i张碎片右侧与第j张碎片左侧是否相连为决策变量，以每张碎片右侧一定与某张碎片左侧相连、每张碎片左侧一定与某张碎片右侧相连为约束条件（复原图片最左侧一定与最右侧的差异度最小），找到中文和英文碎片的拼接复原

6、顺序，MATLAB编程得到复原序号，从而得到出中文与英文复原图片。为了检验中文与英文碎片拼接复原顺序是否正确，建立了MATLAB搜索算法模型，可以得到中文与英文碎片拼接方法，MATLAB软件可以直接画出中文与英文复原图片。结果表明两种方法得出的中文与英文复原顺序相同，复原图片相同。同时人工检验出中文与英文复原图片中无明显语法、词语和单词错误，证明复原图片正确。4.2问题一的碎纸片拼接复原模型建立 先提取碎纸片边缘差异信息，再进行图片拼接复原，具体步骤如下: （1）提取信息：差异度指数 用差异度指数来衡量任意列右侧边缘与任意列左侧边缘差异。 定义差异度指数，表示第张碎片右侧和第张碎片左侧的差异度，为第i张碎片右侧与第j张碎片左侧的对应灰度值之差的绝对值的累和。公式如下： （1） 其中：表示第张碎片右侧第k个特征点的灰度值 表示第j张碎片右侧第k个特征点的灰度值说明： 和的值已知，将附件1和附件2中19张碎片数据带入MATLAB软件可以得到每张碎片的1980个灰度值； 从而得到差异度矩阵如下： (2) 通过MATLAB编程计算出具体值如下：表一：附件一中文任意碎片差异度差异度1列左侧2列左

7、侧3列左侧4列左侧5列左侧6列左侧7列左侧8列左侧9列左侧10列左侧j列左侧1列右侧Inf1309451161031414481009421119552566110609785949111118.2列右侧123423Inf1265891256523361610002711242311989593527111604.3列右侧127946114084Inf105035104745969281224149025682744101673.4列右侧10625312762995945Inf11333010691111130510320383887112810.5列右侧110732116398100076115677Inf2230011879210500657564104087.6列右侧120399113365105551124588114916Inf122693874658140324650.7列右侧84410106346744681140798670949380Inf62810080369.8列右侧111607113205109137136976102362111309107605Inf8462

8、9112936.9列右侧971811109651168891241121071147860111188398983Inf111394.10列右侧11148411862010928812147111806910447212446410150090152Inf.i列右侧.表二：附件二英文任意碎片差异度差异度1列左侧2列左侧3列左侧4列左侧5列左侧6列左侧7列左侧8列左侧9列左侧10列左侧j列左侧1列右侧Inf853108275276567795622436898542896008949089715.2列右侧68051Inf80085515747494710284586945719976792718356.3列右侧5829562297Inf40226645798885777825198236651169324.4列右侧669776386970269Inf781179226925277768838218572522.5列右侧3489739595546630Inf8305361675461435764150786.6列右侧5764919399767274548276087Inf79089699458075366210.7列右侧667477727719737517986301585575Inf714877492780436.

《碎纸片的拼接复原问题大学生数学建模全国一等奖论文.doc》由会员博****1分享，可在线阅读，更多相关《碎纸片的拼接复原问题大学生数学建模全国一等奖论文.doc》请在金锄头文库上搜索。