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

碎纸片的拼接复原问题

摘要

为解决碎纸片的拼接复原问题，我们通过定义差异度指数、高度差，建立0-1规划模型，使用聚类分析、MATLAB搜索算法和人工干预等相结合，得到了所有附件复原序号和复原图片。

针对问题一，首先提取附件1、2中所有碎片左侧和右侧边缘灰度，通过任意列碎片右侧和任意列碎片左侧的边缘灰度差值可以定义差异度指数，从而得到差异度特征矩阵，然后建立0-1规划模型，以第i张碎片右侧与第j张碎片左侧差异度最小为目标函数，以第i张碎片右侧与第j张碎片左侧是否相连为决策变量，以每张碎片右侧一定与某张碎片左侧相连、每张碎片左侧一定与某张碎片右侧相连为约束条件。算法为先提取任意张碎片边缘灰度值，得到差异度矩阵，带入规划模型中，通过LINGO软件找到中英文碎片的拼接方法，得到复原序号如表一、表二，从而得到出中文与英文复原图片。

表一:中文碎片的复原序号

表二：英文碎片的复原序号

检验中英文碎片拼接复原顺序准确性，利用MATLAB搜索算法，可以得到中英文碎片拼接方法。结果表明两种方法得出的中英文复原顺序相同，复原图片相同，同时人工检验中英文复原图片中无明显语法、单词错误，证明复原图片准确。

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

针对问题三，对于双面英文碎片的复原问题，我们提出了单词残缺程度的定义，定量的描述了英文碎片的特征信息，构成了算法的核心内容，运用编程和人工干预将碎纸片分为11类，每类19个碎片，在此基础上利用前两问所建的0-1规划模型，再加上双面的一些约束条件，得到双面英文复原序号，并绘出英文双面复原图片。

关键词：差异度指数；0-1规划；LINGO软件；聚类分析；高度差；残缺程度；

一、问题重述

破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。请讨论以下问题：

1. 对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达。

2. 对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果表达要求同上。

3. 上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果，结果表达要求同上。

二、模型假设

1.假设每个碎纸片上的字和字母都没有发生扭曲。

2.假设每个碎纸片的形状和大小完全相同。

3.假设每个碎纸片上灰度值的提取都是完全正确的值不等于255的都是黑点

三、符号说明

四、问题一分析与模型建立、求解

4.1问题一的分析

问题一要求对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。参考文献[1]，由于每列中文和英文碎片都有左侧和右侧，需要考虑每一列碎片的左侧和右侧与其他列的左侧和右侧差异，每列碎片边缘灰度已知，通过任意列碎片右侧和任意列碎片左侧的差异值可以定义差异度指数（同一列碎片的左侧与右侧的差异度定义为无穷大），从而得到差异度特征矩阵。

然后可以通过0-1规划模型，以第j张碎片左侧与第i张碎片右侧的差异度最小为目标函数，以第i张碎片右侧与第j张碎片左侧是否相连为决策变量，以每张碎片右侧一定与某张碎片左侧相连、每张碎片左侧一定与某张碎片右侧相连为约束条件（复原图片最左侧一定与最右侧的差异度最小），找到中文和英文碎片的拼接复原顺序，MATLAB编程得到复原序号，从而得到出中文与英文复原图片。

为了检验中文与英文碎片拼接复原顺序是否正确，建立了MATLAB搜索算法模型，可以得到中文与英文碎片拼接方法，MATLAB软件可以直接画出中文与英文复原图片。结果表明两种方法得出的中文与英文复原顺序相同，复原图片相同。同时人工检验出中文与英文复原图片中无明显语法、词语和单词错误，证明复原图片正确。

4.2问题一的碎纸片拼接复原模型建立

先提取碎纸片边缘差异信息，再进行图片拼接复原，具体步骤如下:

（1）提取信息：差异度指数

用差异度指数来衡量任意列右侧边缘与任意列左侧边缘差异。

定义差异度指数，表示第张碎片右侧和第张碎片左侧的差异度，为第i张碎片右侧与第j张碎片左侧的对应灰度值之差的绝对值的累和。公式如下：

（1）

其中：表示第张碎片右侧第k个特征点的灰度值

表示第j张碎片右侧第k个特征点的灰度值

说明：和的值已知，将附件1和附件2中19张碎片数据带入MATLAB软件可以得到每张碎片的1980个灰度值；

从而得到差异度矩阵如下：

(2)

通过MATLAB编程计算出具体值如下：

表一：附件一中文任意碎片差异度

表二：附件二英文任意碎片差异度

（2）中文和英文碎纸片拼接复原模型

以第j张碎片左侧与第i张碎片右侧的差异度最小为目标函数，以第i张碎片右侧与第j张碎片左侧是否相连为决策变量，以每张碎片右侧一定与某张碎片左侧相连、每张碎片左侧一定与某张碎片右侧相连为约束条件，建立0-1规划模型。

s.t (3)

其中：为决策变量， =0时，表示第张碎片右侧和第张碎片左侧的不相连；

=1时，表示第张碎片右侧和第张碎片左侧的相连；

4.3问题一中英文碎片拼接问题模型求解

模型求解算法如下：

（1）运用MATLAB编程提取19列中文和英文碎片左侧和右侧的灰度值，计算出差异度指数，得到差异度矩阵，结果见表一和表二。

（2）运用LINGO11.0软件，将上述0-1规划问题的目标函数与约束条件带入LINGO软件中（附录一为中文碎片拼接复原LINGO算法，附录二为英文碎片拼接复原LINGO算法），结果如表三和表四。

（3）运用MATLAB编程（编程见附录三）得到中文和英文碎片的复原序号，结果见表五和表六，可以直接得到中文和英文复原图片，图片见附录四和五。

表三：中文碎片连接方法

表四：英文碎片连接方法

得到连接方法以后，可以使用MATLAB编程（见附录三）得到中文和英文碎片的复原序号如下表：

表五:中文碎片的复原序号

表六：英文碎片的复原序号

用MATLAB编程（附录四）可以直接拼接出中文和英文碎片复原图片，程序结果截图如图一：

图一：复原图片程序结果截图

中文与英文碎片复原的图片见附录四和五。

复原过程不需要人工干预，可完全通过LINGO软件和MATLAB编程实现。

4.4中文和英文碎片拼接复原方法检验

为了检验差异度指数和0-1规划模型得出的复原顺序和复原图片的准确性，利用MATLAB搜索算法模型：

（4）

已通过MATLAB编程得到第i张碎片右侧和第j张碎片左侧的差异度，见表一与表二。对表一和表二按照列搜索，依次搜索找到与第j列碎片左侧相连的差异度最小的第i列碎纸片右侧（即），即第i列碎纸片右侧与第j列碎片左侧相连，对于每一列碎纸片需要搜索19次，共需要搜索361次，使用MATLAB搜索算法即可实现（编程见附录三 )

可以得到中文和英文碎纸片的连接方式，如下表：

表七：中文碎纸片连接方式

表八：英文碎纸片连接方式

通过对比这两种模型得到的结果发现：中文和英文碎片连接方式完全相同，两种方法得出的中文与英文复原顺序相同，复原图片相同。同时人工检验出中文与英文复原图片中无明显语法、词语和单词错误，证明中文和英文复原图片正确。

0-1规划模型清晰明了，同时运算简单，运算速度快。MATLAB搜索算法搜索次数较多，运算速度慢一些，但结果准确。所以我们使用0-1规划模型解决问题一，使用MATLAB搜索算法检验结果。

五、问题二分析与模型建立、求解

5.1问题二的分析

问题二要求对于碎纸机既纵切又横切的情形，建立碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。由于209块中文和209块英文碎片都有左侧、右侧和上侧、下侧，与问题一相同，可以定义两个差异度指数。根据问题一得到双目标0-1规划模型，由于决策变量较复杂，这种模型不是很易求解，矩阵太大，也不易计算，因此提出了改进模型。

改进模型，定义高度差，表示第i块碎片第一行文字中心到第i碎片上侧边缘的高度与第j块碎片第一行文字中心到第j碎片上侧边缘的高度之间的差值。运用聚类分析，给定高度差阈值，按照高度不同将所有碎片分为18类。然后再以第j块碎片左侧与第i块碎片右侧的差异度最小和第i块碎片与第j块碎片高度差最小为双目标函数，以第i块碎片右侧与第j块碎片左侧是否相连为决策变量（），以每块碎片右侧一定与某块碎片左侧相连（），每块碎片左侧一定与某块碎片右侧相连（）为约束条件，建立双目标0-1规划模型。找到18类中英文碎片，结合MATLAB编程和人工干预，将18类碎片处理为11行碎片，再利用问题一中碎片纵向复原的方法，得到中英文复原序号，从而MATLAB编程画出中文与英文复原图片。同时人工检验出中文与英文复原图片中无明显语法、词语和单词错误，证明复原图片正确。

5.2问题二碎纸片拼接复原模型建立

5.2.1问题二碎纸片拼接复原初步模型

先提取碎纸片边缘差异信息，再进行图片拼接复原，具体步骤如下:

（1）提取信息：差异度指数

用差异度指数来衡量任意块碎片右侧边缘与任意块碎片左侧边缘差异及任意块碎片下侧边缘与任意块碎片上侧边缘的差异。

定义差异度指数：表示第块碎片右侧和第块碎片左侧的差异度，为第i块碎片右侧与第j块碎片左侧的对应灰度值之差的绝对值的累和。表示第块碎片下侧和第块碎片上侧的差异度，为第i块碎片下侧与第j块碎片上侧的对应灰度值之差的绝对值的累和。

公式如下：

（5）

(6)

其中：表示第块碎片右侧第k个特征点的灰度值；

表示第j块碎片右侧第k个特征点的灰度值；

表示第块碎片下侧第k个特征点的灰度值；

表示第j块碎片上侧第k个特征点的灰度值；

说明： 、和、的值已知，将附件3和附件4所有碎片数据带入MATLAB软件可以得到每块碎片的左侧、右侧和上侧、下侧灰度值；

从而得到两个差异度矩阵如下：

(7)

(8)

（2）中文和英文碎纸片拼接复原模型

以第j块碎片左侧与第i块碎片右侧的差异度最小和第j块碎片上侧与第i块碎片下侧的差异度最小为双目标函数，以第i块碎片右侧与第j块碎片左侧是否相连为决策变量（）和第i块碎片下侧与第j块碎片上侧是否相连为决策变量（），以每块碎片右侧一定与某块碎片左侧相连（）、每块碎片下侧一定与某块碎片上侧相连（），任意两块碎片之间可能不相连、可能左右相连、可能上下相连（）为约束条件，建立双目标0-1规划模型。

(9)

其中： =0时，表示第张碎片右侧和第张碎片左侧的不相连；

=1时，表示第张碎片右侧和第张碎片左侧的相连；

=0时，表示第张碎片下侧和第张碎片上侧的不相连；

=1时，表示第张碎片下侧和第张碎片上侧的相连；

此模型可以得到所有碎片的连接方式。

5.2.2问题二中英文碎片拼接复原改进模型

由于建立的初步模型有决策变量较复杂，而且两个差异度矩阵较大，用程序实现较困难，因此在此提出改进模型，只使用一种决策变量，具体建模过程如下：

（1）提取信息：差异度指数和高度差

定义差异度指数与初步模型定义相同，但改进模型中不在使用差异度指数，定义高度差，表示第i块碎片第一行文字中心到第i碎片上侧边缘的高度与第j块碎片第一行文字中心到第j碎片上侧边缘的高度之间的差值。公式如下：

（10）

（2）中文碎纸片拼接复原模型

以第j块碎片左侧与第i块碎片右侧的差异度最小和第i块碎片与第j块碎片高度差最小为双目标函数，以第i块碎片右侧与第j块碎片左侧是否相连为决策变量（），以每块碎片右侧一定与某块碎片左侧相连（），每块碎片左侧一定与某块碎片右侧相连（）为约束条件，建立双目标0-1规划模型。

(11)

其中：为决策变量， =0时，表示第张碎片右侧和第张碎片左侧的不相连；

=1时，表示第张碎片右侧和第张碎片左侧的相连；

为了将双目标转化为单目标问题，可以给定高度差阈值，给定高度范围给所有碎片进行分类，共18类，可以将此模型简化，目标函数与约束条件如下：

（12）

再结合人工干预可以得到所有碎片的连接方式。

（3）英文碎纸片复原模型

对附件四英文碎纸片建立复原模型与中文碎纸片模型基本相同，但由于中文是方块字，同一行中文字上下侧边缘基本对齐，英文是非方块字，上下边缘的灰度值不大，因此应该扩大改进模型的阈值，对英文碎片进行分类，可以将高度差阈值调节为，其余约束条件不变，从而得到所有碎片连接方式，得到复原序号。

5.3问题二中英文碎片拼接复原模型求解

5.3.1模型算法

（1）找到每块碎纸片第一行文字中心到碎纸片上侧边缘的高度

第一步：每块碎纸片带入MATLAB软件中可以得到一个像素点的灰度矩阵，将每个矩阵归一化：

第二步：对灰度矩阵从上到下进行行搜索，找到每块碎片第一行文字的中心位置

第三步：通过MATLAB软件编程（附录三）计算第i块碎纸片第一行文字中心到碎纸片上侧边缘的高度。

（2）确定高度差阈值，给定18个高度范围，进行聚类分析，将209块碎片按照每块碎片第一行文字中心到碎片上侧边缘的高度分为18类，结果见表九。

（3）对每一类碎片，运用MATLAB软件画图，可以画出18行文字，对每行文字出现的奇异碎片进行剔除。通过人工干预，可以得到11行文字。

（4）对这11行文字，运用问题一算法，进行纵向拼接复原，在此基础上通过人工干预将11行文字进行调试和拼接，可以得到附件三和附件四中英文的复原序号和复原图片。

5.3.2模型结果

（1）附件三中文碎片拼接复原模型结果

表九：18类不同高度范围的中文碎片

注：此表中的碎片编号均比实际大1，由于MATLAB编程从1开始计数。

对18类中任意一类碎片运用MATLAB编程可以画出任意一行中文，举例如图二：

图二：某一类中文文字行排列

MATLAB编程画出18行中文，对每行中文出现的奇异碎片进行剔除。通过人工干预和问题一中纵向排列法，可以得到11行有顺序的中文，举例如图三：

图三：某一行有顺序的中文文字排列

干预的时间节点及干预方式如下：

干预时间节点：MATLAB编程排出18行后，对第18行的第14张碎片、第89张、第71张、第29张、第203张进行人工干预；将高度（像素）=的第4行碎片人工干预。

干预方式：将这五个块碎片分别带入剩下的12行中文中，将每个碎片左侧和右侧边缘灰度值这12行中文碎片的边缘灰度值进行比较，找到差异度最小的连接方式；将高度（像素）=的第4行碎片按照边缘灰度人工干预成两行。

通过人工干预和MATLAB编程结合得到附件三中文碎片复原序号如下表：

表十：附件三中文碎片复原序号

（2）英文碎片拼接复原模型结果

MATLAB变成可以按照高度不同将英文碎片分为22类，由于分类表格较大，将英文碎片分类表格作为附录6,。

对18类中任意一类碎片运用MATLAB编程可以画出任意一行英文，举例如图四：

图四：某一类英文文字行排列

可以画出18行中文，对每行中文出现的奇异碎片进行剔除。通过人工干预和问题一的纵向排列方法，可以得到11行有顺序的中文，举例如图五：

图五：某一行有顺序的英文排列

干预的时间节点及干预方式如下：

干预时间节点：MATLAB编程排出22行后，对第209块碎片、第8块、第62块、第180块、第5块进行人工干预；将高度（像素）=的碎片与高度（像素）=人工干预。

干预方式：将这五个块碎片分别带入剩下的12行中文中，将每个碎片左侧和右侧边缘灰度值这12行中文碎片的边缘灰度值进行比较，找到差异度最小的连接方式，发现要把编号209的碎片归入高度（像素）=，把；将高度（像素）=的碎片与高度（像素）=人工干预成一行。

得到附件四英文碎片拼接复原复序号如下表：

表十一：附件四英文碎片复原序号

复原图片见附录七和附录八。

六、问题三分析与模型建立、求解

6.1问题三的分析

问题三要求解决双面打印文件的碎纸片拼接复原问题。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。要求设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果。根据问题二，根据单词的残缺程度给定运用MATLAB编程和人工干预将碎纸片分为11类，在此基础上对于建立0-1规划模型:以第j块碎片右侧与第k块碎片左侧的差异度最小为目标函数，以第j块碎片右侧与第k块碎片左侧是否相连为决策变量（），以每块碎片右侧一定与某块碎片左侧相连（），每块碎片左侧一定与某块碎片右侧相连（），某块碎片a、b面一定与某块碎片a、b面中任意一面相连或不相连（word/media/image82_1.png或word/media/image83_1.png），为约束条件，建立0-1规划模型。按以上模型可将分成的11类分别按横向排好序，得到11个长纸条。然后回到第一问的模型，可将11个长纸条按纵向排好序，即可得到复原图片。

6.2问题三碎纸片拼接复原模型建立

（1）提取信息

第一步：提取每个碎纸片的残缺程度和正面和反面的边缘灰度值，如下：

表示第张碎纸片面的左边缘，表示第张碎纸片面的右边缘；

表示第张碎纸片面的右边缘， 表示第张碎纸片面的右边缘；

第二步：对个碎纸片，先根据单词的残缺程度进行分类。（把同一张碎纸片的正反面看成两张不同的碎纸片），再进行人工干预，最终可以分成11类，其中每类包括38张碎纸片（通过观察可以得到每张碎片a面和b面的单词残缺程度相同，因此每类中必包括19张碎纸片的正反面）

第三步：分好类后，将以上38张中属于同一块碎纸片的正反面相邻排在一起，如：001a-001b-005a-005b-007a-007b......再重新编号，依次记为。从第一步已提取的信息中，提取每一类中：

(第张碎纸片的残缺值)

(第张碎纸片的右边缘灰度列向量)（）

(第张碎纸片的左边缘灰度列向量) （）

（2）附件五碎纸片拼接复原模型

首先根据问题一定义表示表示第j张碎片右侧和第k张碎片左侧的差异度，为第j张碎片右侧与第k张碎片左侧的对应灰度值之差的绝对值的累和。公式如下：

以第j块碎片右侧与第k块碎片左侧的差异度最小为目标函数，以第j块碎片右侧与第k块碎片左侧是否相连为决策变量（），以每块碎片右侧一定与某块碎片左侧相连（），每块碎片左侧一定与某块碎片右侧相连（），某块碎片a、b面一定与某块碎片a、b面中任意一面相连或不相连（word/media/image82_1.png或word/media/image83_1.png），为约束条件，建立0-1规划模型。

（13）

其中：为决策变量， =0时，表示第j张碎片右侧和第k张碎片左侧的不相连；

=1时，表示第j张碎片右侧和第k张碎片左侧的相连；

按以上模型可将分成的11类分别按横向排好序，得到11个长纸条。然后回到第一问的模型，可将11个长纸条按纵向排好序，即可得到复原图片。

6.3问题三碎纸片拼接复原模型求解

6.3.1模型算法

（1）首先根据英文字母的字体特征和书写特征对每块碎纸片进行分类。

1.每个单词最多占一行，一行占三个格子；

经计算每块碎纸片大概可以容纳三个单词，每个单词占像素点为60

2.定义每块碎纸片的上边缘单词的残缺程度：

（14）

意义：Q=0或1，上边缘可容纳一个完整的单词。

Q越小，上边缘单词残缺程度越大。

以Q来表示每个碎片的特征。

3.以上提供信息比较精细，将具有相同特征的分为一类，通过MATLAB编程和人工干预，可分为11类。其中：

， ， ， ， ， ， ， ， ，

可以根据以上Q值结合人工干预可得分类，见下表：

表十二：附件五英文分类

4.对每一类运用0-1规划模型，结合MATLAB编程和人工干预进行排序，可以先将11行进行行排序，然后按照问题一列拼接复合模型排序。

6.3.2模型结果

表十三：附件五单面英文复原序号

附件五双面英文复原图片见附录九。

七、模型的评价与推广

7.1模型的优点

问题一中，纵切附件一和附件二中英文，每个碎纸条都比较长，提取的边缘灰度值包含纸片的信息比较多。因此每个碎纸片边缘上的区分度比较大。按边缘差异度优化计算时，对于中英文碎纸片复原都很成功。同时我们不仅建立了0-1规划模型运用LINGO软件求解此问题，还运用了MATLAB搜索算法检验了问题一的结果，发现两种方法得到的复原序列和复原图片完全相同。问题一中完全运用了MATLAB编程和LINGO软件，没有使用人工干预。

问题二中，需要横切和纵切数据，边缘上的灰度信息已明显难以区分两个不能拼在一起的碎纸片，直接用边缘差异度优化计算时即使对于汉语误差也较大，需要的人工干预比较多。因此在双目标0-1规划问题基础上，提出了改进和简化模型，根据汉字和英文的字体特征和书写特征提取不同的高度值，依据高度值进行分类后，在将分类结果运用第一问纵向优化计算时，拼接比较成功，人工干预比较少。这说明对于每个碎纸片提取的特征信息越多，拼接时人工干预的就越少，然而相应的会增加模型的复杂度。因此信息提取要合适。同时在问题二中考虑了中文和英文的轮廓不同，因此对英文碎片复原模型进行了改进。

问题三，提出了单词残缺度定义，定量的描述了英文碎片的特征信息，构成了算法的核心内容，很好的将纵横碎片快速有效的分类，为碎片的拼接复原提供了保障。

7.2模型的缺点

问题二中文和英文碎片的复原模型存在差异，但是我们仅通过改变高度差阈值，对中文和英文碎片进行了不同的分类，这个分类方式不够精确，需要进一步思考，找到更加合理的约束条件，对中文和英文碎片进行不同的分类。同时在英文拼接复原模型中，采用的人工干预过多，说明建立的英文拼接复原模型需要进一步改进。

问题三英文双面碎片，由于聚类分类不够完美，算法实现较困难，所以采用的人工干预较多，人工进行。

7.3模型的推广

碎纸片拼接复原模型可以推广到对文物古迹、破碎物体、司法物证复原、历史文献修复以及军事情报获等情况。

参考文献：

[1]罗智中，基于文字特征的文档碎纸片半自动化拼接，计算机工程与应用，201205：207页 ，2012年。

[2]龚纯，精通MATLAB最优化计算，北京：电子工业出版社，2009年。

[3]李刚，MATLAB函数速查手册，北京：清华大学出版社，2013年。

[4]韩忠庚，数学建模方法及其应用，北京：高等教育出版社，2005年。

附录一：运用LINGO11.0软件编程拼接复原中文碎片

model:

sets:

right/1..19/;

left/1..19/;

links(right,left):c,x;

endsets

data:

!值定义为8000000代表自身和自身不会边缘相连;

c=

;

enddata

min=@sum(links:c*x);

@for(left(j):@sum(right(i):x(i,j))=1);

@for(right(i):@sum(left(j):x(i,j))=1);

end

附录二：运用LINGO11.0软件编程拼接复原英文碎片

model:

sets:

right/1..19/;

left/1..19/;

links(right,left):c,x;

endsets

data:

!值定义为8000000代表自身和自身不会边缘相连;

c=

;

enddata

min=@sum(links:c*x);

@for(left(j):@sum(right(i):x(i,j))=1);

@for(right(i):@sum(left(j):x(i,j))=1);

end

附录三：MATLAB7.12.0（R2011a）编程得到主程序和多个子程序可求出附件一、附件二、附件三、附件四和附件五的中英文碎片的复原序号，搜索检验问题一模型结果，对问题二中英文按高度分类且编程画出附件一、二、三和四中英文碎片复原图片

%%Main_Pro.m

%此模块是程序的主要执行程序

%通过调用写好的各个模块（子程序等）进行运算

%运行条件：

% 将此程序、各个功能模块(m文件)及题目提供的附件文件夹放在同一个目录中，

%在Matlab 7.12.0 (R2012a)中进行运算，使用“CD:\工作目录\”命令切换

%至工作目录，然后运行Main_Pro.m主程序

%%

%{

%导入数据并得到特征向量

%附件1

DATA1=DaoRuShuJu('\附件1\',19);

%附件2

DATA2=DaoRuShuJu('\附件2\',19);

%附件3

DATA3=DaoRuShuJu('\附件3\',209);

%附件4

DATA4=DaoRuShuJu('\附件4\',209);

%附件5较特殊，所以需要使用新的行列函数

%附件5

[DATA5_A DATA5_B]=DaoRuShuJu_AB('\附件5\',209);

%}

%读入数据存储阵

%load DATA.mat

%%

%

%%

%计算出连接数据

%附件1

[cydHang1 cydLie1]=ChaYiDu(DATA1);

[cydZhi1 LianJie1]=min(cydLie1); %最小差异值及连接关系

list_1=PaiXu(LianJie1,9);

figure;

Q1_TuPian=HuiTu(list_1(2,:),DATA1); %绘制图像

title('附件1复原图');

imwrite(Q1_TuPian,'问题1_中文图片复原.png'); %保存为png格式图像

%附件2

[cydHang2 cydLie2]=ChaYiDu(DATA2);

[cydZhi2 LianJie2]=min(cydLie2); %最小差异值及连接关系

list_2=PaiXu(LianJie2,4);

figure;

Q2_TuPian=HuiTu(list_2(2,:),DATA2); %绘制图像

title('附件2复原图');

imwrite(Q2_TuPian,'问题2_英文图片复原.png'); %保存为png格式图像

%附件3

[cydHang3 cydLie3]=ChaYiDu(DATA3);

[cydZhi3_Lie LianJie3_Lie]=min(cydLie3); %整体最小差异值及连接关系

[cydZhi3_Hang LianJie3_Hang]=min(cydHang3); %整体最小差异值及连接关系

%综合分类

[Q3_AAAA Q3_AAAB Q3_AABA Q3_AABB Q3_ABAA Q3_ABAB Q3_ABBA Q3_ABBB...

Q3_BAAA Q3_BAAB Q3_BABA Q3_BABB Q3_BBAA Q3_BBAB Q3_BBBA Q3_BBBB]...

=TeZhenFenLei(DATA3);

%特征向量提取

Q3_TeZheng=DanYuanXiangLiang(DATA3);

%计算特征向量之间的差异度

Q3_TeZhengChaYiDu=TeZhengChaYiDu(Q3_TeZheng);

%分类特征差异度

Q3_FenLeiTeZhengChaYiDu=TeZhengChaYiDu_FenLei(Q3_TeZhengChaYiDu,5);

%顶部特征向量重心计算，筛选

[Q3_DingBu_TeZheng Q3_DingBu_List]=DingBuZhongXin(Q3_TeZheng,29);

%开始排序

%使用人工干预机器排序后结果保存在Q3_Result中

%绘制图像

figure;

Q3_TuPian=DrawFullPage(Q3_Result,DATA3);

title('附件3复原图');

imwrite(Q3_TuPian,'问题3_中文图片复原.png'); %保存为png格式图像

%附件4

[cydHang4 cydLie4]=ChaYiDu(DATA4);

[cydZhi4_Lie LianJie4_Lie]=min(cydLie4); %最小差异值及连接关系

[cydZhi4_Hang LianJie4_Hang]=min(cydHang4); %最小差异值及连接关系

%综合分类

[Q4_AAAA Q4_AAAB Q4_AABA Q4_AABB Q4_ABAA Q4_ABAB Q4_ABBA Q4_ABBB...

Q4_BAAA Q4_BAAB Q4_BABA Q4_BABB Q4_BBAA Q4_BBAB Q4_BBBA Q4_BBBB]...

=TeZhenFenLei(DATA4);

%特征向量提取

Q4_TeZheng=DanYuanXiangLiang(DATA4);

%计算特征向量之间的差异度

Q4_TeZhengChaYiDu=TeZhengChaYiDu(Q4_TeZheng);

%分类特征差异度

Q4_FenLeiTeZhengChaYiDu=TeZhengChaYiDu_FenLei(Q4_TeZhengChaYiDu,5);

%顶部特征向量重心计算，筛选

[Q4_DingBu_TeZheng Q4_DingBu_List]=DingBuZhongXin(Q4_TeZheng,29);

%开始排序

%使用人工干预机器排序后结果保存在Q4_Result中

%绘制图像

figure;

Q4_TuPian=DrawFullPage(Q4_Result,DATA4);

title('附件4复原图');

imwrite(Q4_TuPian,'问题4_英文图片复原.png'); %保存为png格式图像

%附件5

DATA5=[DATA5_A DATA5_B]; %数据进行合并计算

Q5_TeZheng=DanYuanXiangLiang(DATA5); %提取特征向量

[Q5_DingBu_TeZheng Q5_DingBu_List]=DIngBuZhongXin(Q5_TeZheng,40);

ca=DingBuZhongXin2(DATA5_A);

cb=DingBuZhongXin2(DATA5_B);

com=[ca cb];

[Q5_SRT Q5_SRT_List]=Q5_GP_SORT(com);

%%

%%DaoRuShuJu.m

function DATA=DaoRuShuJu(file_path,file_num)

%此模块负责将目录下制定数量bmp图像数据导入Matlab中，并保存变量

%存储的数据的编号也是按照{图片名称+1}的升序排列的

file_path=strcat(cd(),file_path); %文件所在的文件夹,文件数量(从0开始编号)

if(file_num)<1

error('文件数不能小于1');

end

for i=1:file_num

if(i<=10)

p='00';

elseif(i<=100)

p='0';

else

p='';

end

dat{i}=strcat(file_path,p,num2str(i-1),'.bmp'); %建立文件夹的树结构

end

for i=1:length(dat) %批量读入数据

W=imread(dat{i}); %使用元胞数组存储各文件中的内容。

DATA{(i)}=W; %数据文件保存至数据结构体

end

end

%%DaoRuShuJu_AB.m

function [DATA_A DATA_B]=DaoRuShuJu_AB(file_path,file_num)

%此模块负责将目录下制定数量bmp图像数据导入Matlab中，并保存变量

%存储的数据的编号也是按照【图像面{图片名称+1}】的升序排列的

%为减少运算复杂度，将数据拆分为A面、B面分别为相关变量

file_path=strcat(cd(),file_path);

%文件所在的文件夹,文件数量(从0开始编号)

if(file_num)<1

error('文件数不能小于1');

end

for i=1:file_num

if(i<=10)

p='00';

elseif(i<=100)

p='0';

else

p='';

end

dat_a{i}=strcat(file_path,p,num2str(i-1),'a','.bmp');

%建立文件夹的树结构

dat_b{i}=strcat(file_path,p,num2str(i-1),'b','.bmp');

end

%读取A面

for i=1:length(dat_a) %批量读入数据

W=imread(dat_a{i}); %使用元胞数组存储各文件中的内容。

DATA_A{(i)}=W; %数据文件保存至数据结构体

end

%读取B面

for i=1:length(dat_b) %批量读入数据

W=imread(dat_b{i}); %使用元胞数组存储各文件中的内容。

DATA_B{(i)}=W; %数据文件保存至数据结构体

end

%%ChaYiDu.m

function [sHang sLie]=ChaYiDu(data)

%此函数实现计算各特征行(tHang)、各特征列(tLie)的差异度

%运算结果保存在我们的差异度矩阵里面

%列，第i列右列和第j列的左列的差异度(已包含任意两个列)

bottom=length(data{1}(:,1));

right=length(data{1}(1,:));

for i=1:length(data)

for j=1:length(data)

if(i==j)

%自身距离为无穷

sLie(i,j)=+inf;

else

sLie(i,j)=sum(abs(int32(data{i}(:,right))-int32(data{j}(:,1))));

end

end

end

%行，第i行右行和第j行的左行的差异度(已包含任意两个行)

for i=1:length(data)

for j=1:length(data)

if(i==j)

%自身距离为无穷

sHang(i,j)=+inf;

else

sHang(i,j)=sum(abs(int32(data{i}(bottom,:))-int32(data{j}(1,:))));

end

end

end

end

%%PaiXu.m

function PaiLie=PaiXu(lianjie,left_side)

%此函数实现对查找得的关系列表进行排序

%同时返回排列

%%

%排序

%从左边缘开始排序,排序结果为【序号-1】,因为数据的编号为000开始的

%生成数组

ws=[1:length(lianjie);lianjie];

for k=1:length(lianjie)

PaiLie(1,k)=k; %数据号码编号

PaiLie(2,k)=ws(1,left_side)-1; %号码对齐

left_side=ws(1,left_side);

%查找索引

for j=1:length(ws(2,:))

if (ws(2,j)==left_side)

left_side=j;

break;

end

end

end

end

%%HuiTu.m

function Grf=HuiTu(list,data)

%此函数实现对排序数据进行数据绘图操作，返回图像数据

GP=[];

for i=1:length(list(1,:))

GP=[GP data{list(1,i)+1}];

end

Grf=GP;

imshow(GP);

end

%%TeZhenFenLei.m

function [AAAA AAAB AABA AABB ABAA ABAB ABBA ABBB...

BAAA BAAB BABA BABB BBAA BBAB BBBA BBBB]...

=TeZhenFenLei(data)

%%

%此模块负责将数据进行分类

%分类依据为每个数据单元的顶面、底面、和两个侧面

%共可以将数据分为8个类别

%AAA{顶行,底行,左侧,右侧}……{A},有点，{B},无点

i_aaaa=1;

i_aaab=1;

i_aaba=1;

i_aabb=1;

i_abaa=1;

i_abab=1;

i_abba=1;

i_abbb=1;

i_baaa=1;

i_baab=1;

i_baba=1;

i_babb=1;

i_bbaa=1;

i_bbab=1;

i_bbba=1;

i_bbbb=1;

right=length(data{1}(1,:)); %数据宽度

bottom=length(data{1}(:,1)); %数据高度

%{

for i=1:length(data)

%提取矩阵特征边缘数据

TeZhen_Hang{(i)}=[data{i}(1,:)' data{i}(bottom,:)'];

TeZhen_Lie{(i)}=[data{i}(:,1) data{i}(:,right)];

end

%}

%%

%整体排列

[A B]=FenLeiX(data,1:length(data),1);

%%

[AA AB]=FenLeiX(data,A,2);

[AAA AAB]=FenLeiX(data,AA,3);

[AAAA AAAB]=FenLeiX(data,AAA,4);

[AABA AABB]=FenLeiX(data,AAB,4);

[ABA ABB]=FenLeiX(data,AB,3);

[ABAA ABAB]=FenLeiX(data,ABA,4);

[ABBA ABBB]=FenLeiX(data,ABB,4);

%%

[BA BB]=FenLeiX(data,B,2);

[BAA BAB]=FenLeiX(data,BA,3);

[BAAA BAAB]=FenLeiX(data,BAA,4);

[BABA BABB]=FenLeiX(data,BAB,4);

[BBA BBB]=FenLeiX(data,BB,3);

[BBAA BBAB]=FenLeiX(data,BBA,4);

[BBBA BBBB]=FenLeiX(data,BBB,4);

%%

end

%%DanYuanXiangLiang.m

function TeZhenXiangLiang=DanYuanXiangLiang(data)

%此函数实现计算各个数据矩阵的特征单元向量

%用于元素特征比较时使用

%%

for i=1:length(data)

w=data{i};

for j=1:length(w(:,1))

for k=1:length(w(1,:))

if(w(j,k)~=255)

w(j,k)=1;

else

w(j,k)=0;

end

end

end

TeZhenXiangLiang{i}=sum(w')';

end

for i=1:length(TeZhenXiangLiang)

for j=1:length(TeZhenXiangLiang{i})

if(TeZhenXiangLiang{i}(j)~=0)

TeZhenXiangLiang{i}(j)=1;

end

end

end

end

%%TeZhengChaYiDu.m

function tChaYiDu=TeZhengChaYiDu(data)

%此函数实现对于提取出来的特征向量阵集合求出差异度矩阵

for i=1:length(data)

for j=1:length(data)

if(i==j)

tChaYiDu(i,j)=+inf;

else

tChaYiDu(i,j)=sum(abs(data{i}-data{j}));

end

end

end

end

%%TeZhengChaYiDu_FenLei.m

function CC=TeZhengChaYiDu_FenLei(TZchayidu,wucha)

%此功能提取出计算得到的特征向量差异阵的值的变化状况

%误差由用户给定

for i=1:length(TZchayidu(:,1))

k=1;

for j=1:length(TZchayidu(1,:))

if(TZchayidu(i,j)<=wucha)

CC(i,k)=j;

k=k+1;

end

end

end

end

%%DingBuZhongXin.m

function [TeZhen list]=DingBuZhongXin(tz_data,hangshu)

%此函数计算特征向量集合中的的顶端像素重心

%函数返回特征数据和分类数据

bottom=length(tz_data{1}(:,1));

for i=1:length(tz_data)

for j=1:bottom

if(tz_data{i}(j)==1)

for k=j:bottom

if tz_data{i}(k)==0

break;

end

end

break;

end

end

TeZhen(i)=(k+j)/2;

end

%%

%统计数据

p=0;

%检验需要的行数

if(hangshu<1)

hangshu=1;

end

step=max(TeZhen)/hangshu; %计算误差阈值

for i=0:step:max(TeZhen)

k=2;

p=p+1;

list(p,1)=i;

for j=1:length(TeZhen)

if(TeZhen(j)>i-step && TeZhen(j)<=i)

list(p,k)=j;

k=k+1;

end

end

%%{

if(length(list(:,1))>1)

if(p>1 && list(p,2)==0) %防止产生空行

p=p-1;

end

end

end

%}

end

%%DrawFullPage.m

function GDT=DrawFullPage(list,data)

%此函数通过对查询list矩阵，根据data绘制位图图像

%返回数据的拼合数据矩阵

GDT=[];

for i=1:length(list(:,1))

line=[];

for j=1:length(list(i,:))

line=[line data{list(i,j)+1}];

end

GDT=[GDT' line']';

end

imshow(GDT);

end

%%FenLeiX.m

function [cls_A cls_B]=FenLeiX(data,list,type)

%此函数实现对已给列表的数据进行特征值分类

%type决定类型{1顶行;2底行;3左侧;4右侧}

%list为所给的参量表（参数表中包含待分类的数据,一维数据）

%分类依据为特征值的列或者行中是否存在非白色(255)点

%cls_A第一类(存在),cls_B第二类(不存在)

%%

right=length(data{1}(1,:)); %数据宽度

bottom=length(data{1}(:,1)); %数据高度

k=1;

l=1;

cls_A=[];

cls_B=[];

%%

%顶行

if(type==1)

cmp=ones(1,right)*255;

for i=1:length(list)

w=data{list(i)}(1,:);

flag=false;

for j=1:length(w)

if cmp(j)~=w(j)

flag=true;

break;

end

end

if (flag==true)

cls_A(k)=list(i);

k=k+1;

else

cls_B(l)=list(i);

l=l+1;

end

end

elseif(type==2)

%%

%底行

cmp=ones(1,right)*255;

for i=1:length(list)

w=data{list(i)}(bottom,:);

flag=false;

for j=1:length(w)

if cmp(j)~=w(j)

flag=true;

break;

end

end

if (flag==true)

cls_A(k)=list(i);

k=k+1;

else

cls_B(l)=list(i);

l=l+1;

end

end

elseif(type==3)

%%

%左侧

cmp=ones(bottom,1)*255;

for i=1:length(list)

w=data{list(i)}(:,1);

flag=false;

for j=1:length(w)

if cmp(j)~=w(j)

flag=true;

break;

end

end

if (flag==true)

cls_A(k)=list(i);

k=k+1;

else

cls_B(l)=list(i);

l=l+1;

end

end

elseif(type==4)

%%

%右侧

cmp=ones(bottom,1)*255;

for i=1:length(list)

w=data{list(i)}(:,right);

flag=false;

for j=1:length(w)

if cmp(j)~=w(j)

flag=true;

break;

end

end

if (flag==true)

cls_A(k)=list(i);

k=k+1;

else

cls_B(l)=list(i);

l=l+1;

end

end

else

error('错误，输入的type参数1~4');

end

end

%%PaiXu2.m

function LS=PaiXu2(list,cyd_data,start_id)

%此函数通过使用已知的差异度数据和关系列表，对于整体数据进行【行】排序操作

%提取出特征数据阵

flag=false; %转向标识符，false,向右搜索；true,向左搜索

LS=[]; %排序表

for i=1:length(list)

for j=1:length(list)

DT(i,j)=cyd_data(list(i),list(j));

end

end

%计算最佳相似度排列方法

id=start_id;

for i=1:length(list)

if(flag==false)

[~, id]=min(DT(id,:));

LS=[LS list(id)];

else

[~, id]=min(DT(:,id));

LS=[list(id) LS];

end

%%{

%查找索引重复

%出现重复代表数据应当进行反向搜索排序了

if flag==false %减少运算的判断

for j=1:length(LS)

for k=j:length(LS)

if ((LS(j)==LS(k)) && (j~=k))

LS(i)=[];

i=i-1;

flag=true;

id=start_id;

break;

end

end

if flag==true

%减少运算量

break;

end

end

end

%}

end

end

%%Q5_GP_SORT.m

function [SRT lst]=Q5_GP_SORT(TeZheng)

%像素首次出现点

for i=1:length(TeZheng)

for j=1:length(TeZheng{i}(:,1))

if(TeZheng{i}(j,1)~=0)

list(i)=j;

break;

end

end

end

lst=list;

%计算阈值范围

for i=1:length(list(1,:))

if(list(1,i)<20)

list(2,i)=(list(i)+40)/60;

elseif(list(1,i)>20 && list(1,i)<40)

list(2,i)=(list(i)/60);

end

end

yuzhi=0.05;

%阈值分类

for i=1:length(list(1,:))

p=3;

for j=1:length(list(1,:))

if(abs(list(2,i)-list(2,j))

SRT(i,1)=list(2,i);

SRT(i,2)=i;

SRT(i,p)=j;

p=p+1;

end

end

end

end

%%DingBuZhongXin2.m

function TeZhen=DingBuZhongXin2(data)

%此函数计算集合中的的顶端像素重心

%进行数据统一化，得到样品第一个满足数据阈值条件的数据阵

%计算特征值矩阵

for i=1:length(data)

w=data{i};

for j=1:length(w(:,1))

for k=1:length(w(1,:))

if(w(j,k)~=255)

w(j,k)=1;

else

w(j,k)=0;

end

end

end

TeZhen{i}=sum(w')';

end

end

附录四：问题二按高度不同对附件四英文分类表

附录五：附件一中文碎纸片的复原图片

附录六：附件二的英文碎纸片的复原图片

附录七： 附件三中文碎片复原图片

附录八：附件四英文碎片复原图片

附录九：附件五双面英文复原图像

本文来源：https://www.2haoxitong.net/k/doc/9610938891c69ec3d5bbfd0a79563c1ec4dad76b.html