招考信息

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

作者:admin 来源:原创 时间:2020年07月11日 06:41:46浏览:

  碎纸片的拼接复原问题 摘要 为解决碎纸片的拼接复原问题,我们通过定义差异度指数、高度差,建立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、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预,请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达。 2. 对于碎纸机既纵切又横切的情形,请设计碎纸片拼接复原模型和算法,并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预,请写出干预方式及干预的时间节点。复原结果表达要求同上。 3. 上述所给碎片数据均为单面打印文件,从现实情形出发,还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法,并就附件5的碎片数据给出拼接复原结果,结果表达要求同上。 二、模型假设 1.假设每个碎纸片上的字和字母都没有发生扭曲。 2.假设每个碎纸片的形状和大小完全相同。 3.假设每个碎纸片上灰度值的提取都是完全正确的值不等于255的都是黑点 三、符号说明 符号 符号的含义 差异度指数,表示第张碎片右侧和第张碎片左侧的差异度; 表示第张碎片右侧第k个特征点的灰度值; 决策变量,当0时,表示第张碎片右侧和第张碎片左侧的不相连; 1时,表示第张碎片右侧和第张碎片左侧的相连; 表示第j列碎片左侧与差异度最小的第i列碎纸片右侧相连; 表示第块碎片右侧和第块碎片左侧的差异度; 表示第块碎片下侧和第块碎片上侧的差异度; 表示第块碎片右侧第k个特征点的灰度值; 表示第块碎片下侧第k个特征点的灰度值; 0时,表示第张碎片右侧和第张碎片左侧的不相连; 1时,表示第张碎片右侧和第张碎片左侧的相连; 0时,表示第张碎片下侧和第张碎片上侧的不相连; 1时,表示第张碎片下侧和第张碎片上侧的相连; 高度差表示第i块碎片第一行文字中心到第i碎片上侧边缘的高度与第j块碎片第一行文字中心到第j碎片上侧边缘的高度之间的差值; 四、问题一分析与模型建立、求解 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编程计算出具体值如下 表一附件一中文任意碎片差异度 差异度 1列左侧 2列左侧 3列左侧 4列左侧 5列左侧 6列左侧 7列左侧 8列左侧 9列左侧 10列左侧 j列左侧 1列右侧 Inf 130945 116103 141448 100942 111955 25661 106097 85949 111118 ... 2列右侧 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 105551 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 104472 124464 101500 90152 Inf ... i列右侧 ... ... ... ... ... ... ... ... ... ... ... 表二附件二英文任意碎片差异度 差异度 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 77825 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 57731 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张碎片左侧是否相连为决策变量,以每张碎片右侧一定与某张碎片左侧相连、每张碎片左侧一定与某张碎片右侧相连为约束条件,建立0-1规划模型。 s.t 3 其中为决策变量,0时,表示第张碎片右侧和第张碎片左侧的不相连; 1时,表示第张碎片右侧和第张碎片左侧的相连; 4.3问题一中英文碎片拼接问题模型求解 模型求解算法如下 (1)运用MATLAB编程提取19列中文和英文碎片左侧和右侧的灰度值,计算出差异度指数,得到差异度矩阵,结果见表一和表二。 (2)运用LINGO11.0软件,将上述0-1规划问题的目标函数与约束条件带入LINGO软件中(附录一为中文碎片拼接复原LINGO算法,附录二为英文碎片拼接复原LINGO算法),结果如表三和表四。 (3)运用MATLAB编程(编程见附录三)得到中文和英文碎片的复原序号,结果见表五和表六,可以直接得到中文和英文复原图片,图片见附录四和五。 表三中文碎片连接方法 决策变量为1 X2,5 X1,7 X3,17 X4,11 X5,6 X6,10 X(7,9) X8,18 X9,15 X10,14 实际连接点 01-04 00-06 02-16 03-10 04-05 05-09 06-08 07-17 08-14 09-13 决策变量为1 X11,3 X12,8 X13,16 X14,19 X15,13 X16,14 X17,2 X18,1 X19,12 实际连接点 10-02 11-07 12-15 13-18 14-12 15-13 16-01 17-00 18-11 表四英文碎片连接方法 决策变量为1 X1,6 X2,10 X3,8 X4,7 X5,4 X6,2 X7,3 X8,16 X9,13 X10,14 实际连接点 00-05 01-09 02-07 03-06 04-03 05-01 06-02 07-15 08-12 09-13 决策变量为1 X11,19 X12,1 X13,15 X14,11 X15,18 X16,19 X17,5 X18,17 X19,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 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搜索算法模型 (4) 已通过MATLAB编程得到第i张碎片右侧和第j张碎片左侧的差异度,见表一与表二。对表一和表二按照列搜索,依次搜索找到与第j列碎片左侧相连的差异度最小的第i列碎纸片右侧(即),即第i列碎纸片右侧与第j列碎片左侧相连,对于每一列碎纸片需要搜索19次,共需要搜索361次,使用MATLAB搜索算法即可实现(编程见附录三 可以得到中文和英文碎纸片的连接方式,如下表 表七中文碎纸片连接方式 第i列右侧连接第j列左侧 017-000 016-001 010-002 015-003 001-004 004-005 000-006 011-007 000-006 005-009 第i列右侧连接第j列左侧 003-010 018-011 014-012 009-013 008-014 012-015 002-016 007-017 013-018 表八英文碎纸片连接方式 第i列右侧连接第j列左侧 011-000 005-001 006-002 000-003 016-004 000-005 003-006 010-008 002-007 001-009 第i列右侧连接第j列左侧 013-010 018-011 008-012 009-013 012-014 007-015 017-016 014-017 015-018 通过对比这两种模型得到的结果发现中文和英文碎片连接方式完全相同,两种方法得出的中文与英文复原顺序相同,复原图片相同。同时人工检验出中文与英文复原图片中无明显语法、词语和单词错误,证明中文和英文复原图片正确。 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类不同高度范围的中文碎片 高度(像素)00.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,176,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,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 高度(像素)的碎片编号 72 高度(像素)的碎片编号 90 高度(像素)的碎片编号 15 注此表中的碎片编号均比实际大1,由于MATLAB编程从1开始计数。 对18类中任意一类碎片运用MATLAB编程可以画出任意一行中文,举例如图二 图二某一类中文文字行排列 MATLAB编程画出18行中文,对每行中文出现的奇异碎片进行剔除。通过人工干预和问题一中纵向排列法,可以得到11行有顺序的中文,举例如图三 图三某一行有顺序的中文文字排列 干预的时间节点及干预方式如下 干预时间节点MATLAB编程排出18行后,对第18行的第14张碎片、第89张、第71张、第29张、第203张进行人工干预;将高度(像素)的第4行碎片人工干预。 干预方式将这五个块碎片分别带入剩下的12行中文中,将每个碎片左侧和右侧边缘灰度值这12行中文碎片的边缘灰度值进行比较,找到差异度最小的连接方式;将高度(像素)的第4行碎片按照边缘灰度人工干预成两行。 通过人工干预和MATLAB编程结合得到附件三中文碎片复原序号如下表 表十附件三中文碎片复原序号 49 54 65 143 186 2 57 192 178 118 190 95 11 22 129 28 91 188 141 61 19 78 67 69 99 162 96 131 79 63 116 163 72 6 177 20 52 36 168 100 76 62 142 30 41 23 147 191 50 179 120 86 195 26 1 87 18 38 148 46 161 24 35 81 189 122 103 130 193 88 167 25 8 9 105 74 71 156 83 132 200 17 80 33 202 198 15 133 170 205 85 152 165 27 60 14 128 3 159 82 199 135 12 73 160 203 169 134 39 31 51 107 115 176 94 34 84 183 90 47 121 42 124 144 77 112 149 97 136 164 127 58 43 125 13 182 109 197 16 184 110 187 66 106 150 21 173 157 181 204 139 145 29 64 111 201 5 92 180 48 37 75 55 44 206 10 104 98 172 171 59 7 208 138 158 126 68 175 45 174 0 137 53 56 93 153 70 166 32 196 89 146 102 154 114 40 151 207 155 140 185 108 117 4 101 113 194 119 123 (2) 英文碎片拼接复原模型结果 MATLAB变成可以按照高度不同将英文碎片分为22类,由于分类表格较大,将英文碎片分类表格作为附录6,。 对18类中任意一类碎片运用MATLAB编程可以画出任意一行英文,举例如图四 图四某一类英文文字行排列 可以画出18行中文,对每行中文出现的奇异碎片进行剔除。通过人工干预和问题一的纵向排列方法,可以得到11行有顺序的中文,举例如图五 图五某一行有顺序的英文排列 干预的时间节点及干预方式如下 干预时间节点MATLAB编程排出22行后,对第209块碎片、第8块、第62块、第180块、第5块进行人工干预;将高度(像素)的碎片与高度(像素)人工干预。 干预方式将这五个块碎片分别带入剩下的12行中文中,将每个碎片左侧和右侧边缘灰度值这12行中文碎片的边缘灰度值进行比较,找到差异度最小的连接方式,发现要把编号209的碎片归入高度(像素),把;将高度(像素)的碎片与高度(像素)人工干预成一行。 得到附件四英文碎片拼接复原复序号如下表 表十一附件四英文碎片复原序号 191 75 11 154 190 184 2 104 180 64 106 4 149 32 204 65 39 67 147 201 148 170 196 198 94 113 164 78 103 91 80 101 26 100 6 17 28 146 86 51 107 29 40 158 186 98 24 117 150 5 59 58 92 30 37 46 127 19 194 93 141 88 121 126 105 155 114 176 182 151 22 57 202 71 165 82 159 139 1 129 63 138 153 53 38 123 120 175 85 50 160 187 97 203 31 20 41 108 116 136 73 36 207 135 15 76 43 199 45 173 79 161 179 143 208 21 7 49 61 119 33 142 168 62 169 54 192 133 118 189 162 197 112 70 84 60 14 68 174 137 195 8 47 172 156 96 23 99 122 90 185 109 132 181 95 69 167 163 166 188 111 144 206 3 130 34 13 110 25 27 178 171 42 66 205 10 157 74 145 83 134 55 18 56 35 16 9 183 152 44 81 77 128 200 131 52 125 140 193 87 89 48 72 12 177 124 0 102 115 复原图片见附录七和附录八。 六、问题三分析与模型建立、求解 6.1问题三的分析 问题三要求解决双面打印文件的碎纸片拼接复原问题。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。要求设计相应的碎纸片拼接复原模型与算法,并就附件5的碎片数据给出拼接复原结果。根据问题二,根据单词的残缺程度给定运用MATLAB编程和人工干预将碎纸片分为11类,在此基础上对于建立0-1规划模型以第j块碎片右侧与第k块碎片左侧的差异度最小为目标函数,以第j块碎片右侧与第k块碎片左侧是否相连为决策变量(),以每块碎片右侧一定与某块碎片左侧相连(),每块碎片左侧一定与某块碎片右侧相连(),某块碎片a、b面一定与某块碎片a、b面中任意一面相连或不相连(或),为约束条件,建立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面中任意一面相连或不相连(或),为约束条件,建立0-1规划模型。 (13) 其中为决策变量,0时,表示第j张碎片右侧和第k张碎片左侧的不相连; 1时,表示第j张碎片右侧和第k张碎片左侧的相连; 按以上模型可将分成的11类分别按横向排好序,得到11个长纸条。然后回到第一问的模型,可将11个长纸条按纵向排好序,即可得到复原图片。 6.3问题三碎纸片拼接复原模型求解 6.3.1模型算法 (1) 首先根据英文字母的字体特征和书写特征对每块碎纸片进行分类。 1. 每个单词最多占一行,一行占三个格子; 经计算每块碎纸片大概可以容纳三个单词,每个单词占像素点为60 2. 定义每块碎纸片的上边缘单词的残缺程度 (14) 意义Q0或1,上边缘可容纳一个完整的单词。 Q越小,上边缘单词残缺程度越大。 以Q来表示每个碎片的特征。 3. 以上提供信息比较精细,将具有相同特征的分为一类,通过MATLAB编程和人工干预,可分为11类。其中 , , , , , , , , , 可以根据以上Q值结合人工干预可得分类,见下表 表十二附件五英文分类 Q1 164 047 020 029 081 189 110 125 108 066 078 018 183 150 155 136 147 111 140 Q2 193 159 073 021 163 130 016 031 053 177 146 202 092 190 050 035 019 171 201 Q3 205 145 082 118 015 101 071 048 062 052 023 129 119 160 095 009 033 133 051 Q4 175 039 097 132 072 093 034 161 198 181 199 087 206 173 194 083 156 11 169 Q5 103 196 112 106 055 100 113 096 049 026 099 091 104 006 123 054 134 043 109 Q6 142 024 057 102 208 064 154 179 012 028 114 017 158 058 207 013 197 184 116 Q7 187 200 086 138 131 056 94 084 137 061 186 045 121 038 030 143 98 153 042 Q8 040 122 182 068 127 188 075 128 117 167 165 008 067 046 168 172 063 195 157 Q9 060 152 147 079 059 014 124 036 120 022 089 144 025 044 178 005 192 010 076 Q10 002 203 162 041 139 070 166 149 151 001 088 170 065 191 037 090 115 107 180 Q11 135 204 141 000 027 080 074 085 176 126 003 185 069 004 077 105 032 007 148 4.对每一类运用0-1规划模型,结合MATLAB编程和人工干预进行排序,可以先将11行进行行排序,然后按照问题一列拼接复合模型排序。 6.3.2模型结果 表十三附件五单面英文复原序号 136b 047a 020a 164b 081b 189b 029a 018b 108a 066a 110a 147b 183b 150a 155a 140a 125a 111b 078b 005a 152a 147a 060a 059a 014a 079a 144a 120b 022a 124a 192a 025b 044a 178a 076b 036a 010b 089a 143b 200b 086b 187b 131b 056b 138a 045a 137b 061b 94b 98a 121a 038a 030a 042b 084b 153a 186b 083a 039b 097a 175a 072b 093a 132b 087a 198b 181b 034a 156a 206b 173b 194b 169b 161a 11b 199b 090a 203b 162b 002b 139b 070b 041a 170b 151b 001b 166b 115b 065b 191a 037b 180a 149b 107a 088b 013a 024a 057a 142a 208b 064b 102b 017b 012a 028b 154b 197a 158a 058a 207a 116b 179b 184b 114a 035a 159a 073b 193b 163a 130a 021b 202a 053b 177b 016b 019b 092b 190b 050a 201a 031a 171b 146a 172a 122a 182b 040a 127a 188a 068b 008b 117b 167a 075b 063b 067a 046a 168a 157a 128a 195a 165b 105a 204b 141a 135b 027a 080b 000b 185a 176a 126b 074b 032a 069a 004a 077a 148b 085b 007b 003b 009b 145a 082b 205a 015b 101a 118b 129b 062a 052a 071b 033b 119a 160b 095a 051b 048a 133a 023b 054b 196b 112a 103a 055b 100b 106b 091a 049b 026b 113a 134a 104a 006a 123a 109a 096b 043a 099a 附件五双面英文复原图片见附录九。 七、模型的评价与推广 7.1模型的优点 问题一中,纵切附件一和附件二中英文,每个碎纸条都比较长,提取的边缘灰度值包含纸片的信息比较多。因此每个碎纸片边缘上的区分度比较大。按边缘差异度优化计算时,对于中英文碎纸片复原都很成功。同时我们不仅建立了0-1规划模型运用LINGO软件求解此问题,还运用了MATLAB搜索算法检验了问题一的结果,发现两种方法得到的复原序列和复原图片完全相同。问题一中完全运用了MATLAB编程和LINGO软件,没有使用人工干预。 问题二中,需要横切和纵切数据,边缘上的灰度信息已明显难以区分两个不能拼在一起的碎纸片,直接用边缘差异度优化计算时即使对于汉语误差也较大,需要的人工干预比较多。因此在双目标0-1规划问题基础上,提出了改进和简化模型,根据汉字和英文的字体特征和书写特征提取不同的高度值,依据高度值进行分类后,在将分类结果运用第一问纵向优化计算时,拼接比较成功,人工干预比较少。这说明对于每个碎纸片提取的特征信息越多,拼接时人工干预的就越少,然而相应的会增加模型的复杂度。因此信息提取要合适。同时在问题二中考虑了中文和英文的轮廓不同,因此对英文碎片复原模型进行了改进。 问题三,提出了单词残缺度定义,定量的描述了英文碎片的特征信息,构成了算法的核心内容,很好的将纵横碎片快速有效的分类,为碎片的拼接复原提供了保障。 7.2模型的缺点 问题二中文和英文碎片的复原模型存在差异,但是我们仅通过改变高度差阈值,对中文和英文碎片进行了不同的分类,这个分类方式不够精确,需要进一步思考,找到更加合理的约束条件,对中文和英文碎片进行不同的分类。同时在英文拼接复原模型中,采用的人工干预过多,说明建立的英文拼接复原模型需要进一步改进。 问题三英文双面碎片,由于聚类分类不够完美,算法实现较困难,所以采用的人工干预较多,人工进行。 7.3模型的推广 碎纸片拼接复原模型可以推广到对文物古迹、破碎物体、司法物证复原、历史文献修复以及军事情报获等情况。 参考文献 [1]罗智中,基于文字特征的文档碎纸片半自动化拼接,计算机工程与应用,201205207页 ,2012年。 [2]龚纯,精通MATLAB最优化计算,北京电子

(来源:原创   admin)  

1.uedbet手机版app遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本网的原创文章,请转载时务必注明文章作者和"来源:uedbet手机版app",不尊重原创的行为uedbet手机版app或将追究责任;3.作者投稿可能会经uedbet手机版app编辑修改或补充。

阅读延展