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

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

2、差异度矩阵，带入规划模型中，通过lingo软件找到中英文碎片的拼接方法，得到复原序号如表一、表二，从而得到出中文与英文复原图片。 表一:中文碎片的复原序号008014012015003010002016001004005009013018011007017000006 表二：英文碎片的复原序号003006002007015018011000005001009013010008012014017016004检验中英文碎片拼接复原顺序准确性，利用matlab搜索算法，可以得到中英文碎片拼接方法。结果表明两种方法得出的中英文复原顺序相同，复原图片相同，同时人工检验中英文复原图片中无明显语法、单词错误

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

4、为11行，再利用问题一中碎片纵向复原方法，得到中文复原序号，画出中文复原图片。（英文复原模型相似，仅高度差阈值不同）针对问题三，对于双面英文碎片的复原问题，我们提出了单词残缺程度的定义，定量的描述了英文碎片的特征信息，构成了算法的核心内容，运用编程和人工干预将碎纸片分为11类，每类19个碎片，在此基础上利用前两问所建的0-1规划模型，再加上双面的一些约束条件，得到双面英文复原序号，并绘出英文双面复原图片。 关键词：差异度指数；0-1规划；lingo软件；聚类分析；高度差；残缺程度； 一、问题重述破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工

5、作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。请讨论以下问题：1. 对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达。2. 对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干

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

7、决策变量，当=0时，表示第张碎片右侧和第张碎片左侧的不相连； =1时，表示第张碎片右侧和第张碎片左侧的相连；表示第j列碎片左侧与差异度最小的第i列碎纸片右侧相连；表示第块碎片右侧和第块碎片左侧的差异度；表示第块碎片下侧和第块碎片上侧的差异度； 表示第块碎片右侧第k个特征点的灰度值； 表示第块碎片下侧第k个特征点的灰度值；=0时，表示第张碎片右侧和第张碎片左侧的不相连；=1时，表示第张碎片右侧和第张碎片左侧的相连； =0时，表示第张碎片下侧和第张碎片上侧的不相连； =1时，表示第张碎片下侧和第张碎片上侧的相连；高度差表示第i块碎片第一行文字中心到第i碎片上侧边缘的高度与第j块碎片第一行文字中心到

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

9、张碎片右侧与第j张碎片左侧是否相连为决策变量，以每张碎片右侧一定与某张碎片左侧相连、每张碎片左侧一定与某张碎片右侧相连为约束条件（复原图片最左侧一定与最右侧的差异度最小），找到中文和英文碎片的拼接复原顺序，matlab编程得到复原序号，从而得到出中文与英文复原图片。为了检验中文与英文碎片拼接复原顺序是否正确，建立了matlab搜索算法模型，可以得到中文与英文碎片拼接方法，matlab软件可以直接画出中文与英文复原图片。结果表明两种方法得出的中文与英文复原顺序相同，复原图片相同。同时人工检验出中文与英文复原图片中无明显语法、词语和单词错误，证明复原图片正确。4.2问题一的碎纸片拼接复原模型建立

10、先提取碎纸片边缘差异信息，再进行图片拼接复原，具体步骤如下: （1）提取信息：差异度指数 用差异度指数来衡量任意列右侧边缘与任意列左侧边缘差异。 定义差异度指数，表示第张碎片右侧和第张碎片左侧的差异度，为第i张碎片右侧与第j张碎片左侧的对应灰度值之差的绝对值的累和。公式如下： （1） 其中：表示第张碎片右侧第k个特征点的灰度值 表示第j张碎片右侧第k个特征点的灰度值说明： 和的值已知，将附件1和附件2中19张碎片数据带入matlab软件可以得到每张碎片的1980个灰度值； 从而得到差异度矩阵如下： (2) 通过matlab编程计算出具体值如下：表一：附件一中文任意碎片差异度差异度1列左侧2列左

11、侧3列左侧4列左侧5列左侧6列左侧7列左侧8列左侧9列左侧10列左侧j列左侧1列右侧inf1309451161031414481009421119552566110609785949111118.2列右侧123423inf1265891256523361610002711242311989593527111604.3列右侧127946114084inf105035104745969281224149025682744101673.4列右侧10625312762995945inf11333010691111130510320383887112810.5列右侧1107321163981000761

12、15677inf2230011879210500657564104087.6列右侧120399113365105551124588114916inf122693874658140324650.7列右侧84410106346744681140798670949380inf62810080369.8列右侧111607113205109137136976102362111309107605inf84629112936.9列右侧971811109651168891241121071147860111188398983inf111394.10列右侧1114841186201092881214711180

13、6910447212446410150090152inf.i列右侧.表二：附件二英文任意碎片差异度差异度1列左侧2列左侧3列左侧4列左侧5列左侧6列左侧7列左侧8列左侧9列左侧10列左侧j列左侧1列右侧inf853108275276567795622436898542896008949089715.2列右侧68051inf80085515747494710284586945719976792718356.3列右侧5829562297inf40226645798885777825198236651169324.4列右侧669776386970269inf781179226925277768838

14、218572522.5列右侧3489739595546630inf8305361675461435764150786.6列右侧5764919399767274548276087inf79089699458075366210.7列右侧667477727719737517986301585575inf714877492780436.8列右侧70250745807465457731809149252071274inf7557870757.9列右侧6250663054701424022571430809388231068430inf75775.10列右侧689017092777477538548212

15、397435887038446184145inf.i列右侧. （2）中文和英文碎纸片拼接复原模型以第j张碎片左侧与第i张碎片右侧的差异度最小为目标函数，以第i张碎片右侧与第j张碎片左侧是否相连为决策变量，以每张碎片右侧一定与某张碎片左侧相连、每张碎片左侧一定与某张碎片右侧相连为约束条件，建立0-1规划模型。 s.t (3)其中：为决策变量，=0时，表示第张碎片右侧和第张碎片左侧的不相连； =1时，表示第张碎片右侧和第张碎片左侧的相连；4.3问题一中英文碎片拼接问题模型求解模型求解算法如下： （1）运用matlab编程提取19列中文和英文碎片左侧和右侧的灰度值，计算出差异度指数，得到差异度矩阵，

16、结果见表一和表二。 （2）运用lingo11.0软件，将上述0-1规划问题的目标函数与约束条件带入lingo软件中（附录一为中文碎片拼接复原lingo算法，附录二为英文碎片拼接复原lingo算法），结果如表三和表四。 （3）运用matlab编程（编程见附录三）得到中文和英文碎片的复原序号，结果见表五和表六，可以直接得到中文和英文复原图片，图片见附录四和五。表三：中文碎片连接方法决策变量为1x(2,5)x(1,7)x(3,17)x(4,11)x(5,6)x(6,10)x（7,9）x(8,18)x(9,15)x(10,14)实际连接点01-0400-0602-1603-1004-0505-0906

17、-0807-1708-1409-13决策变量为1x(11,3)x(12,8)x(13,16)x(14,19)x(15,13)x(16,14)x(17,2)x(18,1)x(19,12)实际连接点10-0211-0712-1513-1814-1215-1316-0117-0018-11表四：英文碎片连接方法决策变量为1x(1,6)x(2,10)x(3,8)x(4,7)x(5,4)x(6,2)x(7,3)x(8,16)x(9,13)x(10,14)实际连接点00-0501-0902-0703-0604-0305-0106-0207-1508-1209-13决策变量为1x(11,19)x(12,1)

18、x(13,15)x(14,11)x(15,18)x(16,19)x(17,5)x(18,17)x(19,12)实际连接点10-1811-012-1413-1014-1715-1816-0417-1618-11得到连接方法以后，可以使用matlab编程（见附录三）得到中文和英文碎片的复原序号如下表： 表五:中文碎片的复原序号008014012015003010002016001004005009013018011007017000006表六：英文碎片的复原序号003006002007015018011000005001009013010008012014017016004 用matlab编程（附

19、录四）可以直接拼接出中文和英文碎片复原图片，程序结果截图如图一： 图一：复原图片程序结果截图 中文与英文碎片复原的图片见附录四和五。 复原过程不需要人工干预，可完全通过lingo软件和matlab编程实现。4.4中文和英文碎片拼接复原方法检验 为了检验差异度指数和0-1规划模型得出的复原顺序和复原图片的准确性，利用matlab搜索算法模型： （4） 已通过matlab编程得到第i张碎片右侧和第j张碎片左侧的差异度，见表一与表二。对表一和表二按照列搜索，依次搜索找到与第j列碎片左侧相连的差异度最小的第i列碎纸片右侧（即），即第i列碎纸片右侧与第j列碎片左侧相连，对于每一列碎纸片需要搜索19次，共

20、需要搜索361次，使用matlab搜索算法即可实现（编程见附录三 )可以得到中文和英文碎纸片的连接方式，如下表：表七：中文碎纸片连接方式第i列右侧连接第j列左侧017-000016-001010-002015-003001-004004-005000-006011-007000-006005-009第i列右侧连接第j列左侧003-010018-011014-012009-013008-014012-015002-016007-017013-018表八：英文碎纸片连接方式第i列右侧连接第j列左侧011-000005-001006-002000-003016-004000-005003-00601

21、0-008002-007001-009第i列右侧连接第j列左侧013-010018-011008-012009-013012-014007-015017-016014-017015-018 通过对比这两种模型得到的结果发现：中文和英文碎片连接方式完全相同，两种方法得出的中文与英文复原顺序相同，复原图片相同。同时人工检验出中文与英文复原图片中无明显语法、词语和单词错误，证明中文和英文复原图片正确。0-1规划模型清晰明了，同时运算简单，运算速度快。matlab搜索算法搜索次数较多，运算速度慢一些，但结果准确。所以我们使用0-1规划模型解决问题一，使用matlab搜索算法检验结果。五、问题二分析与模

22、型建立、求解 5.1问题二的分析问题二要求对于碎纸机既纵切又横切的情形，建立碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。由于209块中文和209块英文碎片都有左侧、右侧和上侧、下侧，与问题一相同，可以定义两个差异度指数。根据问题一得到双目标0-1规划模型，由于决策变量较复杂，这种模型不是很易求解，矩阵太大，也不易计算，因此提出了改进模型。 改进模型，定义高度差，表示第i块碎片第一行文字中心到第i碎片上侧边缘的高度与第j块碎片第一行文字中心到第j碎片上侧边缘的高度之间的差值。运用聚类分析，给定高度差阈值，按照高度不同将所有碎片分为18类。然后再以

23、第j块碎片左侧与第i块碎片右侧的差异度最小和第i块碎片与第j块碎片高度差最小为双目标函数，以第i块碎片右侧与第j块碎片左侧是否相连为决策变量（），以每块碎片右侧一定与某块碎片左侧相连（），每块碎片左侧一定与某块碎片右侧相连（）为约束条件，建立双目标0-1规划模型。找到18类中英文碎片，结合matlab编程和人工干预，将18类碎片处理为11行碎片，再利用问题一中碎片纵向复原的方法，得到中英文复原序号，从而matlab编程画出中文与英文复原图片。同时人工检验出中文与英文复原图片中无明显语法、词语和单词错误，证明复原图片正确。5.2问题二碎纸片拼接复原模型建立5.2.1问题二碎纸片拼接复原初步模型

24、先提取碎纸片边缘差异信息，再进行图片拼接复原，具体步骤如下: （1）提取信息：差异度指数 用差异度指数来衡量任意块碎片右侧边缘与任意块碎片左侧边缘差异及任意块碎片下侧边缘与任意块碎片上侧边缘的差异。定义差异度指数：表示第块碎片右侧和第块碎片左侧的差异度，为第i块碎片右侧与第j块碎片左侧的对应灰度值之差的绝对值的累和。表示第块碎片下侧和第块碎片上侧的差异度，为第i块碎片下侧与第j块碎片上侧的对应灰度值之差的绝对值的累和。 公式如下：（5） (6)其中：表示第块碎片右侧第k个特征点的灰度值； 表示第j块碎片右侧第k个特征点的灰度值； 表示第块碎片下侧第k个特征点的灰度值； 表示第j块碎片上侧第k个

25、特征点的灰度值；说明： 、和、的值已知，将附件3和附件4所有碎片数据带入matlab软件可以得到每块碎片的左侧、右侧和上侧、下侧灰度值； 从而得到两个差异度矩阵如下： (7) (8)（2）中文和英文碎纸片拼接复原模型以第j块碎片左侧与第i块碎片右侧的差异度最小和第j块碎片上侧与第i块碎片下侧的差异度最小为双目标函数，以第i块碎片右侧与第j块碎片左侧是否相连为决策变量（）和第i块碎片下侧与第j块碎片上侧是否相连为决策变量（），以每块碎片右侧一定与某块碎片左侧相连（）、每块碎片下侧一定与某块碎片上侧相连（），任意两块碎片之间可能不相连、可能左右相连、可能上下相连（）为约束条件，建立双目标0-1规划

26、模型。 (9)其中：=0时，表示第张碎片右侧和第张碎片左侧的不相连； =1时，表示第张碎片右侧和第张碎片左侧的相连； =0时，表示第张碎片下侧和第张碎片上侧的不相连； =1时，表示第张碎片下侧和第张碎片上侧的相连； 此模型可以得到所有碎片的连接方式。5.2.2问题二中英文碎片拼接复原改进模型由于建立的初步模型有决策变量较复杂，而且两个差异度矩阵较大，用程序实现较困难，因此在此提出改进模型，只使用一种决策变量，具体建模过程如下：（1）提取信息：差异度指数和高度差定义差异度指数与初步模型定义相同，但改进模型中不在使用差异度指数，定义高度差，表示第i块碎片第一行文字中心到第i碎片上侧边缘的高度与第j

27、块碎片第一行文字中心到第j碎片上侧边缘的高度之间的差值。公式如下： （10）（2）中文碎纸片拼接复原模型以第j块碎片左侧与第i块碎片右侧的差异度最小和第i块碎片与第j块碎片高度差最小为双目标函数，以第i块碎片右侧与第j块碎片左侧是否相连为决策变量（），以每块碎片右侧一定与某块碎片左侧相连（），每块碎片左侧一定与某块碎片右侧相连（）为约束条件，建立双目标0-1规划模型。 (11)其中：为决策变量，=0时，表示第张碎片右侧和第张碎片左侧的不相连； =1时，表示第张碎片右侧和第张碎片左侧的相连； 为了将双目标转化为单目标问题，可以给定高度差阈值，给定高度范围给所有碎片进行分类，共18类，可以将此模型

28、简化，目标函数与约束条件如下： （12） 再结合人工干预可以得到所有碎片的连接方式。（3）英文碎纸片复原模型 对附件四英文碎纸片建立复原模型与中文碎纸片模型基本相同，但由于中文是方块字，同一行中文字上下侧边缘基本对齐，英文是非方块字，上下边缘的灰度值不大，因此应该扩大改进模型的阈值，对英文碎片进行分类，可以将高度差阈值调节为，其余约束条件不变，从而得到所有碎片连接方式，得到复原序号。5.3问题二中英文碎片拼接复原模型求解5.3.1模型算法（1）找到每块碎纸片第一行文字中心到碎纸片上侧边缘的高度第一步：每块碎纸片带入matlab软件中可以得到一个像素点的灰度矩阵，将每个矩阵归一化： 第二步：对灰

29、度矩阵从上到下进行行搜索，找到每块碎片第一行文字的中心位置第三步：通过matlab软件编程（附录三）计算第i块碎纸片第一行文字中心到碎纸片上侧边缘的高度。（2）确定高度差阈值，给定18个高度范围，进行聚类分析，将209块碎片按照每块碎片第一行文字中心到碎片上侧边缘的高度分为18类，结果见表九。（3）对每一类碎片，运用matlab软件画图，可以画出18行文字，对每行文字出现的奇异碎片进行剔除。通过人工干预，可以得到11行文字。（4）对这11行文字，运用问题一算法，进行纵向拼接复原，在此基础上通过人工干预将11行文字进行调试和拼接，可以得到附件三和附件四中英文的复原序号和复原图片。5.3.2模型结

30、果（1）附件三中文碎片拼接复原模型结果表九：18类不同高度范围的中文碎片高度（像素）=0+0.5的碎片编号无高度（像素）=的碎片编号6，11,38,45，49,56,59，60,65,76,93,高度（像素）=的碎片编号9，10，25，26，36，39，47，75，82，89，104，106，123，131，149，162，168，190，194高度（像素）=的碎片编号1，8，33，35，43，44，46，48，54，57，69，71，78，85，91，94，95，98，113，122，125，127，128，137，138，139，145，150，154，159，165，167，175，17

31、6，184，197，209高度（像素）=的碎片编号7，20，21，37，53，62，64，68，70，73，79，80，97，100，117，132，163，164，178高度（像素）=的碎片编号16，18，28，34，61，81，84，86，133，134，153，157，166，171，199，201，203，206高度（像素）=的碎片编号17,22,111,146,158,182,183,185,188,205高度（像素）=的碎片编号14,67，107,110,126,140,151,174,198高度（像素）=的碎片编号5,41,102,103,109，114,115,118,120,

32、124,141,147,152,155,156,186,195,208高度（像素）=的碎片编号2,19,24,27,31,42,51,63,77,87,88,101,121,143,148,169,180,192,19高度（像素）=的碎片编号4，13,32,40,52,74,83,108,116,129,135,136,160,161,170,177,200高度（像素）=的碎片编号204高度（像素）=的碎片编号30高度（像素）=的碎片编号3,23,29,50,58,66,92,119,130,142,144,187,191,193高度（像素）=的碎片编号12,55,96,179,189高度（像

33、素）=的碎片编号72高度（像素）=的碎片编号90高度（像素）=的碎片编号15注：此表中的碎片编号均比实际大1，由于matlab编程从1开始计数。对18类中任意一类碎片运用matlab编程可以画出任意一行中文，举例如图二： 图二：某一类中文文字行排列 matlab编程画出18行中文，对每行中文出现的奇异碎片进行剔除。通过人工干预和问题一中纵向排列法，可以得到11行有顺序的中文，举例如图三： 图三：某一行有顺序的中文文字排列干预的时间节点及干预方式如下：干预时间节点：matlab编程排出18行后，对第18行的第14张碎片、第89张、第71张、第29张、第203张进行人工干预；将高度（像素）=的第4

34、行碎片人工干预。干预方式：将这五个块碎片分别带入剩下的12行中文中，将每个碎片左侧和右侧边缘灰度值这12行中文碎片的边缘灰度值进行比较，找到差异度最小的连接方式；将高度（像素）=的第4行碎片按照边缘灰度人工干预成两行。 通过人工干预和matlab编程结合得到附件三中文碎片复原序号如下表： 表十：附件三中文碎片复原序号495465143186257192178118190951122129289118814161197867699916296131796311616372617720523616810076621423041231471915017912086195261871838148461

35、612435811891221031301938816725891057471156831322001780332021981513317020585152165276014128315982199135127316020316913439315110711517694348418390471214212414477112149971361641275843125131821091971618411018766106150211731571812041391452964111201592180483775554420610104981721715972081381581266817545174

36、0137535693153701663219689146102154114401512071551401851081174101113194119123（2） 英文碎片拼接复原模型结果 matlab变成可以按照高度不同将英文碎片分为22类，由于分类表格较大，将英文碎片分类表格作为附录6,。 对18类中任意一类碎片运用matlab编程可以画出任意一行英文，举例如图四： 图四：某一类英文文字行排列 可以画出18行中文，对每行中文出现的奇异碎片进行剔除。通过人工干预和问题一的纵向排列方法，可以得到11行有顺序的中文，举例如图五： 图五：某一行有顺序的英文排列干预的时间节点及干预方式如下：干预时间节点

37、：matlab编程排出22行后，对第209块碎片、第8块、第62块、第180块、第5块进行人工干预；将高度（像素）=的碎片与高度（像素）=人工干预。干预方式：将这五个块碎片分别带入剩下的12行中文中，将每个碎片左侧和右侧边缘灰度值这12行中文碎片的边缘灰度值进行比较，找到差异度最小的连接方式，发现要把编号209的碎片归入高度（像素）=，把；将高度（像素）=的碎片与高度（像素）=人工干预成一行。得到附件四英文碎片拼接复原复序号如下表：表十一：附件四英文碎片复原序号1917511154190184210418064106414932204653967147201148170196198941131

38、647810391801012610061728146865110729401581869824117150559589230374612719194931418812112610515511417618215122572027116582159139112963138153533812312017585501601879720331204110811613673362071351576431994517379161179143208217496111933142168621695419213311818916219711270846014681741371958471721569623991

39、229018510913218195691671631661881111442063130341311025271781714266205101577414583134551856351691831524481771282001315212514019387894872121771240102115复原图片见附录七和附录八。 六、问题三分析与模型建立、求解6.1问题三的分析 问题三要求解决双面打印文件的碎纸片拼接复原问题。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。要求设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果。根据问题二，根据单词的残缺程度给定运用ma

40、tlab编程和人工干预将碎纸片分为11类，在此基础上对于建立0-1规划模型:以第j块碎片右侧与第k块碎片左侧的差异度最小为目标函数，以第j块碎片右侧与第k块碎片左侧是否相连为决策变量（），以每块碎片右侧一定与某块碎片左侧相连（），每块碎片左侧一定与某块碎片右侧相连（），某块碎片a、b面一定与某块碎片a、b面中任意一面相连或不相连（或），为约束条件，建立0-1规划模型。按以上模型可将分成的11类分别按横向排好序，得到11个长纸条。然后回到第一问的模型，可将11个长纸条按纵向排好序，即可得到复原图片。6.2问题三碎纸片拼接复原模型建立（1） 提取信息第一步：提取每个碎纸片的残缺程度和正面和反面的边

41、缘灰度值，如下： 表示第张碎纸片面的左边缘，表示第张碎纸片面的右边缘； 表示第张碎纸片面的右边缘， 表示第张碎纸片面的右边缘；第二步：对个碎纸片，先根据单词的残缺程度进行分类。（把同一张碎纸片的正反面看成两张不同的碎纸片），再进行人工干预，最终可以分成11类，其中每类包括38张碎纸片（通过观察可以得到每张碎片a面和b面的单词残缺程度相同，因此每类中必包括19张碎纸片的正反面）第三步：分好类后，将以上38张中属于同一块碎纸片的正反面相邻排在一起，如：001a-001b-005a-005b-007a-007b.再重新编号，依次记为。从第一步已提取的信息中，提取每一类中：(第张碎纸片的残缺值)(第张

42、碎纸片的右边缘灰度列向量)（）(第张碎纸片的左边缘灰度列向量) （） （2）附件五碎纸片拼接复原模型 首先根据问题一定义表示表示第j张碎片右侧和第k张碎片左侧的差异度，为第j张碎片右侧与第k张碎片左侧的对应灰度值之差的绝对值的累和。公式如下： 以第j块碎片右侧与第k块碎片左侧的差异度最小为目标函数，以第j块碎片右侧与第k块碎片左侧是否相连为决策变量（），以每块碎片右侧一定与某块碎片左侧相连（），每块碎片左侧一定与某块碎片右侧相连（），某块碎片a、b面一定与某块碎片a、b面中任意一面相连或不相连（或），为约束条件，建立0-1规划模型。 （13） 其中：为决策变量，=0时，表示第j张碎片右侧和第k

43、张碎片左侧的不相连； =1时，表示第j张碎片右侧和第k张碎片左侧的相连； 按以上模型可将分成的11类分别按横向排好序，得到11个长纸条。然后回到第一问的模型，可将11个长纸条按纵向排好序，即可得到复原图片。6.3问题三碎纸片拼接复原模型求解6.3.1模型算法（1） 首先根据英文字母的字体特征和书写特征对每块碎纸片进行分类。1. 每个单词最多占一行，一行占三个格子； 经计算每块碎纸片大概可以容纳三个单词，每个单词占像素点为602. 定义每块碎纸片的上边缘单词的残缺程度： （14）意义：q=0或1，上边缘可容纳一个完整的单词。 q越小，上边缘单词残缺程度越大。 以q来表示每个碎片的特征。3. 以上

44、提供信息比较精细，将具有相同特征的分为一类，通过matlab编程和人工干预，可分为11类。其中：， ， ， ， ， ， ， ， ，可以根据以上q值结合人工干预可得分类，见下表：表十二：附件五英文分类q1164047020029081189110125108066078018183150155136147111140q2193159073021163130016031053177146202092190050035019171201q3205145082118015101071048062052023129119160095009033133051q41750390971320720930341

45、6119818119908720617319408315611169q5103196112106055100113096049026099091104006123054134043109q6142024057102208064154179012028114017158058207013197184116q71872000861381310569408413706118604512103803014398153042q8040122182068127188075128117167165008067046168172063195157q9060152147079059014124036120022

46、089144025044178005192010076q10002203162041139070166149151001088170065191037090115107180q111352041410000270800740851761260031850690040771050320071484.对每一类运用0-1规划模型，结合matlab编程和人工干预进行排序，可以先将11行进行行排序，然后按照问题一列拼接复合模型排序。6.3.2模型结果表十三：附件五单面英文复原序号136b047a020a164b081b189b029a018b108a066a110a147b183b150a155a140a125a111b078b005a152a147a060a059a014a079a144a120b022a124a192a025b044a178a076b036a010b089a143b200b086b187b131b056b138a045a137b061b94b98a121a038a03