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

碎纸片的拼接复原问题

摘要

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

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

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

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

片拼接方法。结果表明两种方法得出的中英文复原顺序相同，复原图片相同，同时人工检验中英文复原图片中无明显语法、单词错误，证明复原图片准确。

针对问题二，由于每张碎片有左侧、右侧和上侧、下侧，与问题一相同，可以定义两个差异度指数，建立双目标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）提取信息：差异度指数

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

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

??

???=∞≠==-=∑=时，当时，当j i j i j i C C C k jk ik ij 19...2,1,19,...,

2,1,1980

1

（1） 其中：ik C 表示第i 张碎片右侧第k 个特征点的灰度值 jk C 表示第j 张碎片右侧第k 个特征点的灰度值

说明： ik C 和jk C 的值已知，将附件1和附件2中19张碎片数据带入MATLAB 软件可以得到每张碎片的1980个灰度值； 从而得到差异度矩阵如下：

?

?

?

??

?

?

?????19,1921911919222121913

121.....................C C C C C C C C C ，，，，，，，， (2)

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

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

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

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

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

∑∑==19

119

1min i j ij ij x C

s.t ?????

????=====∑∑==1019,...,2,1,119,...,

2,1,1191

19

1或ij j ij i ij x i x j x (3)

其中：ij x 为决策变量，ij x =0时，表示第i 张碎片右侧和第j 张碎片左侧的不相连； ij x =1时，表示第i 张碎片右侧和第j 张碎片左侧的相连； 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）min=

,

=j

2,1

C

S

j

i

19

，

（

...

，

）

2,1

取

,...,

给定时，19

ij

ij

C，见表一与已通过MATLAB编程得到第i张碎片右侧和第j张碎片左侧的差异度

ij

表二。对表一和表二按照列搜索，依次搜索找到与第j列碎片左侧相连的差异度最小的

S），即第i列碎纸片右侧与第j列碎片左侧相连，对于每一列第i列碎纸片右侧（即

ij

碎纸片需要搜索19次，共需要搜索361次，使用MATLAB搜索算法即可实现（编程见附录三 )

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

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

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

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

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

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

5.1问题二的分析

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

改进模型，定义高度差ij H ，表示第i 块碎片第一行文字中心到第i 碎片上侧边缘的高度i H 与第j 块碎片第一行文字中心到第j 碎片上侧边缘的高度j H 之间的差值。运用聚类分析，给定高度差阈值，按照高度不同将所有碎片分为18类。然后再以第j 块碎片左侧与第i 块碎片右侧的差异度最小和第i 块碎片与第j 块碎片高度差最小为双目标函数，以第i 块碎片右侧与第j 块碎片左侧是否相连为决策变量ij α（0≥ij α），以每块碎片右侧一定与某块碎片左侧相连（1209

1=∑=j ij α），每块碎片左侧一定与某块碎片右侧

相连（1209

1

=∑=i ij α）为约束条件，建立双目标0-1规划模型。找到18类中英文碎片，结

合MATLAB 编程和人工干预，将18类碎片处理为11行碎片，再利用问题一中碎片纵向复原的方法，得到中英文复原序号，从而MATLAB 编程画出中文与英文复原图片。同时人工检验出中文与英文复原图片中无明显语法、词语和单词错误，证明复原图片正确。 5.2问题二碎纸片拼接复原模型建立 5.2.1问题二碎纸片拼接复原初步模型

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

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

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

?????=∞≠==-=∑=时，当时，当，，

j i j i j i L L L k jk ik ij 209...2,1,209,,2,1,180

1

L （5）

?????=∞≠==-=∑=时，当时，当j i j i j i U U U k jk ik ij 209

,...,2,1,2092,1,72

1

L

(6)

其中：ik L 表示第i 块碎片右侧第k 个特征点的灰度值； jk L 表示第j 块碎片右侧第k 个特征点的灰度值； ik U 表示第i 块碎片下侧第k 个特征点的灰度值； jk U 表示第j 块碎片上侧第k 个特征点的灰度值；

说明：ik L 、jk L 和ik U 、jk U 的值已知，将附件3和附件4所有碎片数据带入MATLAB 软件可以得到每块碎片的左侧、右侧和上侧、下侧灰度值； 从而得到两个差异度矩阵如下：

?

???

?

??

?????209,2092209120920922212209

12

111......

...

............

L L L L L L L L L ，，

，，，，，， (7)

?

?

?

??

?

?

?????209,209220912092092221220912

111.....................

U U U U U U U U U ，，

，，，，，， (8)

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

以第j 块碎片左侧与第i 块碎片右侧的差异度最小和第j 块碎片上侧与第i 块碎片下侧的差异度最小为双目标函数，以第i 块碎片右侧与第j 块碎片左侧是否相连为决策变量ij α（0≥ij α）和第i 块碎片下侧与第j 块碎片上侧是否相连为决策变量ij β（0≥ij β），以每块碎片右侧一定与某块碎片左侧相连（1209

1=∑=j ij α）、每块碎片下侧一定与某块碎片

上侧相连（∑==209

1

1i ij β），任意两块碎片之间可能不相连、可能左右相连、可能上下相连

（1≤+ij ij βα）为约束条件，建立双目标0-1规划模型。

∑∑==2091209

1min i j ij ij L α

∑∑==2091209

1

min i j ij ij U β

?????

?

?

?

?

?

???????==≥≥≤+====∑∑∑∑∑∑======209120912091209

1

209

1

209

1209209001209

,...,2,1,1209,...,2,1,1.i j ij i j ij ij ij ij ij i ij j ij j i t s βαβαβαβα (9)

其中：ij α=0时，表示第i 张碎片右侧和第j 张碎片左侧的不相连； ij α=1时，表示第i 张碎片右侧和第j 张碎片左侧的相连； ij β=0时，表示第i 张碎片下侧和第j 张碎片上侧的不相连；

ij β=1时，表示第i 张碎片下侧和第j 张碎片上侧的相连； 此模型可以得到所有碎片的连接方式。 5.2.2问题二中英文碎片拼接复原改进模型

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

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

?

??=≠==-=时，当时

，当，，j i j i j i H H H j i ij 0209...2,1,209,...,2,1, （10）

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

以第j 块碎片左侧与第i 块碎片右侧的差异度最小和第i 块碎片与第j 块碎片高度差最小为双目标函数，以第i 块碎片右侧与第j 块碎片左侧是否相连为决策变量ij α（0≥ij α），以每块碎片右侧一定与某块碎片左侧相连（1209

1=∑=j ij α），每块碎片左侧一定

与某块碎片右侧相连（1209

1

=∑=i ij α）为约束条件，建立双目标0-1规划模型。

∑∑==2091209

1

min i j ij ij L α

∑∑==2091209

1

min i j ij ij H α

??

??

?

????=====∑∑==10209,...,2,1,1209,...,2,1,1.2091

209

1或ij j ij i ij i j t s ααα (11)

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

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

∑∑==2091209

1min i j ij ij L α

??

???

????=≤====∑∑==105.0209,...,2,1,1209,...,2,1,1.2091

209

1或ij ij i ij j ij H j i t s ααα （12）

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

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

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

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

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

{

25525510211<==

ij ij s s s

第二步：对灰度矩阵1s 从上到下进行行搜索，找到每块碎片第一行文字的中心位置 第三步：通过MATLAB 软件编程（附录三）计算第i 块碎纸片第一行文字中心到碎纸片上侧边缘的高度i H 。

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

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

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

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

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

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

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

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

图三：某一行有顺序的中文文字排列 干预的时间节点及干预方式如下：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6.1问题三的分析

问题三要求解决双面打印文件的碎纸片拼接复原问题。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。要求设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果。根据问题二，根据单词的残缺程度给定运用MATLAB 编程和人工干预将碎纸片分为11类，在此基础上对于建立0-1规划模型:以第j 块碎片右侧与第k 块碎片左侧的差异度最小为目标函数，以第j 块碎片右侧与第k 块碎片左侧

是否相连为决策变量jk X （0≥jk X ），以每块碎片右侧一定与某块碎片左侧相连（1381

=∑=j jk X ），每块碎片左侧一定与某块碎片右侧相连（138

1

=∑=k jk X ），某块碎片a 、b 面

一定与某块碎片a 、b 面中任意一面相连或不相连（

1

)1(≤++j j jk X X 或

1

)1(≤+-j j jk X X ），

为约束条件，建立0-1规划模型。按以上模型可将分成的11类分别按横向排好序，得到11个长纸条。然后回到第一问的模型，可将11个长纸条按纵向排好序，即可得到复原图片。

6.2问题三碎纸片拼接复原模型建立 （1）提取信息

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

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

第三步：分好类后，将以上38张中属于同一块碎纸片的正反面相邻排在一起，如：

001a-001b-005a-005b-007a-007b......再重新编号，依次记为38 (1)

，，=j 。从第一步已提取的信息中，提取每一类中：

j Q (第j 张碎纸片的残缺值)

j c (第j 张碎纸片的右边缘灰度列向量)（38...1=j ）

k c (第k 张碎纸片的左边缘灰度列向量) （38...1=k

）

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

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

??

???=∞≠==-=∑=时，当时，当j k j k j j C C L t kt jt jk 180

2,1,180,,2,1,180

1

L L 以第j 块碎片右侧与第k 块碎片左侧的差异度最小为目标函数，以第j 块碎片右侧与第k 块碎片左侧是否相连为决策变量jk X （0≥jk X ），以每块碎片右侧一定与某块碎