碎纸片的拼接复原问题
摘要
为解决碎纸片的拼接复原问题，我们通过定义差异度指数、高度差，建立0-1规划模型，使用聚类分析、MATLAB搜索算法和人工干预等相结合，得到了所有附件复原序号和复原图片。
针对问题一，首先提取附件1、2中所有碎片左侧和右侧边缘灰度，通过任意列碎片右侧和任意列碎片左侧的边缘灰度差值可以定义差异度指数，从而得到差异度特征矩阵，然后建立0-1规划模型，以第i张碎片右侧与第j张碎片左侧差异度最小为目标函数，以第i张碎片右侧与第j张碎片左侧是否相连为决策变量，以每张碎片右侧一定与某张碎片左侧相连、每张碎片左侧一定与某张碎片右侧相连为约束条件。算法为先提取任意张碎片边缘灰度值，得到差异度矩阵，带入规划模型中，通过LINGO软件找到中英文碎片的拼接方法，得到复原序号如表一、表二，从而得到出中文与英文复原图片。 表一:中文碎片的复原序号
008 014 012 015 003 010 002 016 001 004 005 009 013 018 011 007 017 000 006 表二：英文碎片的复原序号
003 006 002 007 015 018 011 000 005 001 009 013 010 008 012 014 017 016 004 检验中英文碎片拼接复原顺序准确性，利用MATLAB搜索算法，可以得到中英文碎片拼接方法。结果表明两种方法得出的中英文复原顺序相同，复原图片相同，同时人工检验中英文复原图片中无明显语法、单词错误，证明复原图片准确。
针对问题二，由于每张碎片有左侧、右侧和上侧、下侧，与问题一相同，可以定义两个差异度指数，建立双目标0-1规划模型。但由于差异度矩阵过大，决策变量复杂，我们又建立了改进的简化模型，定义高度差，运用聚类分析方法，按照高度不同将所有碎片分为18类，然后再以第j块碎片左侧与第i块碎片右侧的差异度最小为目标函数，以第i块碎片右侧与第j块碎片左侧是否相连为决策变量，以每块碎片右侧一定与某块碎片左侧相连、每块碎片左侧一定与某块碎片右侧相连，满足高度差阈值为约束条件，建立单目标0-1规划模型。算法为先提取任意块碎片边缘灰度值和高度，得到差异度矩阵，编程将中文碎片按高度分为18类，人工干预分为11行，再利用问题一中碎片纵向复原方法，得到中文复原序号，画出中文复原图片。（英文复原模型相似，仅高度差阈值不同）
针对问题三，对于双面英文碎片的复原问题，我们提出了单词残缺程度的定义，定量的描述了英文碎片的特征信息，构成了算法的核心内容，运用编程和人工干预将碎纸片分为11类，每类19个碎片，在此基础上利用前两问所建的0-1规划模型，再加上双面的一些约束条件，得到双面英文复原序号，并绘出英文双面复原图片。
关键词：差异度指数；0-1规划；LINGO软件；聚类分析；高度差；残缺程度；
1
一、问题重述
破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。请讨论以下问题：
1. 对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达。
2. 对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果表达要求同上。
3. 上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果，结果表达要求同上。
二、模型假设
1.假设每个碎纸片上的字和字母都没有发生扭曲。 2.假设每个碎纸片的形状和大小完全相同。
3.假设每个碎纸片上灰度值的提取都是完全正确的值不等于255的都是黑点
三、符号说明
符号 Cij Cik 符号的含义 差异度指数，表示第i张碎片右侧和第j张碎片左侧的差异度； 表示第i张碎片右侧第k个特征点的灰度值； 决策变量，当xij=0时，表示第i张碎片右侧和第j张碎片左侧的不相连； xij xij=1时，表示第i张碎片右侧和第j张碎片左侧的相连； Sij Lij 表示第j列碎片左侧与差异度最小的第i列碎纸片右侧相连； 表示第i块碎片右侧和第表示第i块碎片下侧和第j块碎片左侧的差异度； j块碎片上侧的差异度； Uij Lik Uik 表示第i块碎片右侧第k个特征点的灰度值； 表示第i块碎片下侧第k个特征点的灰度值； ?ij ?ij=0时，表示第i张碎片右侧和第j张碎片左侧的不相连；
2
?ij=1时，表示第i张碎片右侧和第j张碎片左侧的相连； ?ij Hij ?ij=0时，表示第i张碎片下侧和第j张碎片上侧的不相连； ?ij =1时，表示第i张碎片下侧和第j张碎片上侧的相连； 高度差表示第i块碎片第一行文字中心到第i碎片上侧边缘的高度Hi与第j块碎片第一行文字中心到第j碎片上侧边缘的高度Hj之间的差值； 四、问题一分析与模型建立、求解
4.1问题一的分析
问题一要求对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。参考文献[1]，由于每列中文和英文碎片都有左侧和右侧，需要考虑每一列碎片的左侧和右侧与其他列的左侧和右侧差异，每列碎片边缘灰度已知，通过任意列碎片右侧和任意列碎片左侧的差异值可以定义差异度指数（同一列碎片的左侧与右侧的差异度定义为无穷大），从而得到差异度特征矩阵。
然后可以通过0-1规划模型，以第j张碎片左侧与第i张碎片右侧的差异度最小为目标函数，以第i张碎片右侧与第j张碎片左侧是否相连为决策变量，以每张碎片右侧一定与某张碎片左侧相连、每张碎片左侧一定与某张碎片右侧相连为约束条件（复原图片最左侧一定与最右侧的差异度最小），找到中文和英文碎片的拼接复原顺序，MATLAB编程得到复原序号，从而得到出中文与英文复原图片。
为了检验中文与英文碎片拼接复原顺序是否正确，建立了MATLAB搜索算法模型，可以得到中文与英文碎片拼接方法，MATLAB软件可以直接画出中文与英文复原图片。结果表明两种方法得出的中文与英文复原顺序相同，复原图片相同。同时人工检验出中文与英文复原图片中无明显语法、词语和单词错误，证明复原图片正确。 4.2问题一的碎纸片拼接复原模型建立
先提取碎纸片边缘差异信息，再进行图片拼接复原，具体步骤如下: （1）提取信息：差异度指数
用差异度指数来衡量任意列右侧边缘与任意列左侧边缘差异。
定义差异度指数Cij，表示第i张碎片右侧和第j张碎片左侧的差异度，为第i张碎片右侧与第j张碎片左侧的对应灰度值之差的绝对值的累和。公式如下：
?198019,j?1,2...19，当i?j时?Cik?Cjk,i?1,2,...,Cij??? （1） k?1??，当i?j时?其中：Cik表示第i张碎片右侧第k个特征点的灰度值 Cjk表示第j张碎片右侧第k个特征点的灰度值
3