《最新-碎纸片的拼接复原问题大学生数学建模全国一等奖论文精品.pdf》由会员分享，可在线阅读，更多相关《最新-碎纸片的拼接复原问题大学生数学建模全国一等奖论文精品.pdf（6页珍藏版）》请在三一文库上搜索。
1、碎纸片的拼接复原问题 摘要 为解决碎纸片的拼接复原问题，我们通过定义差异度指数、高度差，建立0-1 规划 模型，使用聚类分析、 MATLAB 搜索算法和人工干预等相结合，得到了所有附件复原序号 和复原图片。 针对问题一，首先提取附件1、2 中所有碎片左侧和右侧边缘灰度，通过任意列碎 片右侧和任意列碎片左侧的边缘灰度差值可以定义差异度指数，从而得到差异度特征矩 阵，然后建立 0-1 规划模型，以第 i 张碎片右侧与第 j 张碎片左侧差异度最小为目标函 数，以第 i 张碎片右侧与第 j 张碎片左侧是否相连为决策变量，以每张碎片右侧一定与 某张碎片左侧相连、每张碎片左侧一定与某张碎片右侧相连为约束条
2、件。算法为先提取 任意张碎片边缘灰度值，得到差异度矩阵，带入规划模型中，通过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 搜索算法，可以
3、得到中英文碎 片拼接方法。结果表明两种方法得出的中英文复原顺序相同，复原图片相同，同时人工 检验中英文复原图片中无明显语法、单词错误，证明复原图片准确。 针对问题二，由于每张碎片有左侧、右侧和上侧、下侧，与问题一相同，可以定义 两个差异度指数，建立双目标0-1 规划模型。但由于差异度矩阵过大，决策变量复杂， 我们又建立了改进的简化模型，定义高度差，运用聚类分析方法，按照高度不同将所有 碎片分为 18 类，然后再以第 j 块碎片左侧与第 i 块碎片右侧的差异度最小为目标函数， 以第 i 块碎片右侧与第 j 块碎片左侧是否相连为决策变量，以每块碎片右侧一定与某块 碎片左侧相连、每块碎片左侧一定与某
4、块碎片右侧相连，满足高度差阈值为约束条件， 建立单目标 0-1 规划模型。算法为先提取任意块碎片边缘灰度值和高度，得到差异度矩 阵，编程将中文碎片按高度分为18 类，人工干预分为 11 行，再利用问题一中碎片纵向 复原方法，得到中文复原序号，画出中文复原图片。（英文复原模型相似，仅高度差阈 值不同） 针对问题三，对于双面英文碎片的复原问题，我们提出了单词残缺程度的定义，定 量的描述了英文碎片的特征信息，构成了算法的核心内容，运用编程和人工干预将碎纸 片分为 11 类，每类 19 个碎片，在此基础上利用前两问所建的0-1 规划模型，再加上双 面的一些约束条件，得到双面英文复原序号，并绘出英文双面
5、复原图片。 关键词： 差异度指数； 0-1 规划； LINGO软件；聚类分析；高度差；残缺程度； 一、问题重述 破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重 要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当 碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图 开发碎纸片的自动拼接技术，以提高拼接复原效率。请讨论以下问题： 1. 对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片 拼接复原模型和算法，并针对附件1、附件 2 给出的中、英文各一页文件的碎片数据进 行拼接复原。如果复原过程需要人工干
6、预，请写出干预方式及干预的时间节点。复原结 果以图片形式及表格形式表达。 2. 对于碎纸机既纵切又横切的情形， 请设计碎纸片拼接复原模型和算法，并针对附 件 3、附件 4 给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要 人工干预，请写出干预方式及干预的时间节点。复原结果表达要求同上。 3. 上述所给碎片数据均为单面打印文件，从现实情形出发， 还可能有双面打印文件 的碎纸片拼接复原问题需要解决。附件 5 给出的是一页英文印刷文字双面打印文件的碎 片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5 的碎片数据给出拼 接复原结果，结果表达要求同上。 二、模型假设 1.假设
7、每个碎纸片上的字和字母都没有发生扭曲。 2.假设每个碎纸片的形状和大小完全相同。 3.假设每个碎纸片上灰度值的提取都是完全正确的值不等于255 的都是黑点 三、符号说明 符号符号的含义 ij C差异度指数，表示第i张碎片右侧和第j张碎片左侧的差异度； ik C 表示第i张碎片右侧第k 个特征点的灰度值； ij x 决策变量，当 ij x =0 时，表示第 i 张碎片右侧和第 j 张碎片左侧的不相连； ij x =1 时，表示第i张碎片右侧和第 j 张碎片左侧的相连； ij S 表示第 j 列碎片左侧与差异度最小的第i 列碎纸片右侧相连； ij L 表示第i块碎片右侧和第 j 块碎片左侧的差异度
8、； ij U表示第i块碎片下侧和第j块碎片上侧的差异度； ik L表示第i块碎片右侧第k 个特征点的灰度值； ik U表示第i块碎片下侧第k 个特征点的灰度值； ijij =0 时，表示第i张碎片右侧和第j张碎片左侧的不相连； ij =1 时，表示第i张碎片右侧和第j张碎片左侧的相连； ij ij =0 时，表示第 i 张碎片下侧和第 j 张碎片上侧的不相连； ij =1 时，表示第i张碎片下侧和第 j 张碎片上侧的相连； ij H 高度差表示第i 块碎片第一行文字中心到第i 碎片上侧边缘的高度 i H与第 j 块碎片第一行文字 中心到第 j 碎片上侧边缘的高度 j H 之间的差值； 四、问题
9、一分析与模型建立、求解 4.1 问题一的分析 问题一要求对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立 碎纸片拼接复原模型和算法，并针对附件1、附件 2 给出的中、英文各一页文件的碎片 数据进行拼接复原。参考文献1 ，由于每列中文和英文碎片都有左侧和右侧，需要考 虑每一列碎片的左侧和右侧与其他列的左侧和右侧差异，每列碎片边缘灰度已知，通过 任意列碎片右侧和任意列碎片左侧的差异值可以定义差异度指数（同一列碎片的左侧与 右侧的差异度定义为无穷大） ，从而得到差异度特征矩阵。 然后可以通过 0-1 规划模型，以第 j 张碎片左侧与第 i 张碎片右侧的差异度最小为 目标函数，以第 i
10、 张碎片右侧与第 j 张碎片左侧是否相连为决策变量，以每张碎片右侧 一定与某张碎片左侧相连、每张碎片左侧一定与某张碎片右侧相连为约束条件（复原图 片最左侧一定与最右侧的差异度最小），找到中文和英文碎片的拼接复原顺序，MATLAB 编程得到复原序号，从而得到出中文与英文复原图片。 为了检验中文与英文碎片拼接复原顺序是否正确，建立了MATLAB 搜索算法模型， 可以得到中文与英文碎片拼接方法，MATLAB 软件可以直接画出中文与英文复原图片。结 果表明两种方法得出的中文与英文复原顺序相同，复原图片相同。同时人工检验出中文 与英文复原图片中无明显语法、词语和单词错误，证明复原图片正确。 4.2 问题
11、一的碎纸片拼接复原模型建立 先提取碎纸片边缘差异信息，再进行图片拼接复原，具体步骤如下: （1）提取信息：差异度指数 用差异度指数来衡量任意列右侧边缘与任意列左侧边缘差异。 定义差异度指数 ij C，表示第 i 张碎片右侧和第j 张碎片左侧的差异度，为第i 张碎 片右侧与第 j 张碎片左侧的对应灰度值之差的绝对值的累和。公式如下： 时，当 时，当 ji jijiCC C k jkik ij 19.2, 1,19,.,2, 1, 1980 1 （1） 其中： ik C表示第 i 张碎片右侧第 k 个特征点的灰度值 jk C表示第 j 张碎片右侧第 k 个特征点的灰度值 说明： ik C和 jk
12、C的值已知，将附件1 和附件 2 中 19 张碎片数据带入 MATLAB 软件可以 得到每张碎片的 1980 个灰度值； 从而得到差异度矩阵如下： 19,19219119 1922212 1913121 . . . CCC CCC CCC ， ， ， (2) 通过 MATLAB 编程计算出具体值如下： 表一：附件一中文任意碎片差异度 ijC 差异度 ij C1列左侧2列左侧3列左侧4列左侧5列左侧6列左侧7列左侧8列左侧9列左侧10列左侧j 列左侧 1列右侧Inf 130945 116103 141448 100942 111955 25661 106097 85949 111118 . 2列
13、右侧123423 Inf 126589 125652 33616 100027 112423 119895 93527 111604 . 3列右侧127946 114084 Inf 105035 104745 96928 122414 90256 82744 101673 . 4列右侧106253 127629 95945 Inf 113330 106911 111305 103203 83887 112810 . 5列右侧110732 116398 100076 115677 Inf 22300 118792 105006 57564 104087 . 6列右侧120399 113365 1
14、05551 124588 114916 Inf 122693 87465 81403 24650 . 7列右侧84410 106346 74468 114079 86709 49380 Inf 62810 0 80369 . 8列右侧111607 113205 109137 136976 102362 111309 107605 Inf 84629 112936 . 9列右侧97181 110965 116889 124112 107114 78601 111883 98983 Inf 111394 . 10列右侧111484 118620 109288 121471 118069 10447
15、2 124464 101500 90152 Inf . i 列右侧. . . . . . . . . . . 表二：附件二英文任意碎片差异度 ij C 差异度ij C 1列左侧2列左侧3列左侧4列左侧5列左侧6列左侧7列左侧8列左侧9列左侧10列左侧j 列左侧 1列右侧Inf 85310 82752 76567 79562 24368 98542 89600 89490 89715 . 2列右侧68051 Inf 80085 51574 74947 102845 86945 71997 67927 18356 . 3列右侧58295 62297 Inf 40226 64579 88857 77
16、825 19823 66511 69324 . 4列右侧66977 63869 70269 Inf 78117 92269 25277 76883 82185 72522 . 5列右侧34897 39595 54663 0 Inf 83053 61675 46143 57641 50786 . 6列右侧57649 19399 76727 45482 76087 Inf 79089 69945 80753 66210 . 7列右侧66747 77277 19737 51798 63015 85575 Inf 71487 74927 80436 . 8列右侧70250 74580 74654 57
17、731 80914 92520 71274 Inf 75578 70757 . 9列右侧62506 63054 70142 40225 71430 80938 82310 68430 Inf 75775 . 10列右侧68901 70927 77477 53854 82123 97435 88703 84461 84145 Inf . i 列右侧. . . . . . . . . . . （2）中文和英文碎纸片拼接复原模型 以第 j 张碎片左侧与第 i 张碎片右侧的差异度最小为目标函数，以第 i 张碎片右侧 与第 j 张碎片左侧是否相连为决策变量，以每张碎片右侧一定与某张碎片左侧相连、每 张碎
18、片左侧一定与某张碎片右侧相连为约束条件，建立0-1 规划模型。 19 1 19 1 min ij ijijx C s.t 10 19,.,2, 1, 1 19,.,2, 1, 1 19 1 19 1 或 ij j ij i ij x ix jx (3) 其中： ij x为决策变量， ij x=0时，表示第 i 张碎片右侧和第j 张碎片左侧的不相连； ij x=1时，表示第 i 张碎片右侧和第j 张碎片左侧的相连； 4.3 问题一中英文碎片拼接问题模型求解 模型求解算法如下： （1）运用 MATLAB 编程提取 19 列中文和英文碎片左侧和右侧的灰度值，计算出差异 度指数，得到差异度矩阵，结果见
19、表一和表二。 （2）运用 LINGO11.0软件，将上述 0-1 规划问题的目标函数与约束条件带入LINGO 软件中（附录一为中文碎片拼接复原LINGO算法，附录二为英文碎片拼接复原LINGO 算 法），结果如表三和表四。 （3）运用 MATLAB 编程（编程见附录三）得到中文和英文碎片的复原序号，结果见 表五和表六，可以直接得到中文和英文复原图片，图片见附录四和五。 表三：中文碎片连接方法 决策变量为 1 X(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-04 00-06
20、 02-16 03-10 04-05 05-09 06-08 07-17 08-14 09-13 决策变量为 1 X(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-02 11-07 12-15 13-18 14-12 15-13 16-01 17-00 18-11 表四：英文碎片连接方法 决策变量为 1 X(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-05 0
21、1-09 02-07 03-06 04-03 05-01 06-02 07-15 08-12 09-13 决策变量为 1 X(11,19) X(12,1) X(13,15) X(14,11) X(15,18) X(16,19) X(17,5) X(18,17) X(19,12) 实际连接点10-18 11-0 12-14 13-10 14-17 15-18 16-04 17-16 18-11 得到连接方法以后，可以使用MATLAB 编程（见附录三）得到中文和英文碎片的复 原序号如下表： 表五: 中文碎片的复原序号 008 014 012 015 003 010 002 016 001 004
22、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 编程（附录四）可以直接拼接出中文和英文碎片复原图片，程序结果截 图如图一： 图一：复原图片程序结果截图 中文与英文碎片复原的图片见附录四和五。 复原过程不需要人工干预，可完全通过LINGO软件和 MATLAB 编程实现。 4.4 中文和英文碎片拼接复原方法检验 为了检验差异度指数和0-1 规划模型得出的复原顺序和复原图片的准确性，利用 MATLAB 搜索算法模型： ）（，取给定时，19,.,2, 119.2, 1,minjijCS ijij （4） 已通过 MATLAB 编程得到第 i 张碎片右侧和第j 张碎片左侧的差异度 ij C，见表一与 表二。对表一和表二按照列搜索，依次搜索找到与第j 列碎片左侧相连的差异度最小的 第 i 列碎纸片右侧（即 ij S） ，即第 i 列碎纸片右侧与第j 列碎片左侧相连，对于每一列 碎纸片需要搜索 19 次，共需要搜索 361 次，使用 MATLAB 搜索算法即可实现（编程见附 录三 ) 可以得到中文和英文碎纸片的连接方式，如下表： 表七：中文碎纸片连接方式