碎纸片的拼接复原问题大学生数学建模(一等奖论文).pdf

碎纸片的拼接复原问题 摘要为解决碎纸片的拼接复原问题，我们通过定义差异度指数、高度差，建立0-1规划 模型，使用聚类分析、MATLAB搜索算法和人工干预等相结合，得到了所有附件复原序号 和复原图片。针对问题一，首先提取附件1、2中所有碎片左侧和右侧边缘灰度，通过任意列碎 片右侧和任意列碎片左侧的边缘灰度差值可以定义差异度指数，从而得到差异度特征矩 阵，然后建立0T规划模型，以第i张碎片右侧与第j张碎片左侧差异度最小为目标函 数，以第i张碎片右侧与第j张碎片左侧是否相连为决策变量，以每张碎片右侧一定与 某张碎片左侧相连、每张碎片左侧一定与某张碎片右侧相连为约束条件。算法为先提取 任意张碎片边缘灰度值，得到差异度矩阵，带入规划模型中，通过LI NGO软件找到中英 文碎片的拼接方法，得到复原序号如表一、表二，从而得到出中文与英文复原图片。表一:中文碎片的复原序号008014012015003010002016001004005009013018011007017000006表二：英文碎片的复原序号003006002007015018011000005001009013010008012014017016004检验中英文碎片拼接复原顺序准确性，利用MATLAB搜索算法，可以得到中英文碎 片拼接方法。结果表明两种方法得出的中英文复原顺序相同，复原图片相同，同时人工 检验中英文复原图片中无明显语法、单词错误，证明复原图片准确。针对问题二，由于每张碎片有左侧、右侧和上侧、下侧，与问题一相同，可以定义 两个差异度指数，建立双目标0-1规划模型。但由于差异度矩阵过大，决策变量复杂，我们又建立了改进的简化模型，定义高度差，运用聚类分析方法，按照高度不同将所有 碎片分为18类，然后再以第j块碎片左侧与第i块碎片右侧的差异度最小为目标函数,以第i块碎片右侧与第j块碎片左侧是否相连为决策变量，以每块碎片右侧一定与某块 碎片左侧相连、每块碎片左侧一定与某块碎片右侧相连，满足高度差阈值为约束条件，建立单目标0-1规划模型。算法为先提取任意块碎片边缘灰度值和高度，得到差异度矩 阵，编程将中文碎片按高度分为18类，人工干预分为H行，再利用问题一中碎片纵向 复原方法，得到中文复原序号，画出中文复原图片。（英文复原模型相似，仅高度差阈 值不同）针对问题三，对于双面英文碎片的复原问题，我们提出了单词残缺程度的定义，定 量的描述了英文碎片的特征信息，构成了算法的核心内容，运用编程和人工干预将碎纸 片分为11类，每类19个碎片，在此基础上利用前两问所建的0-1规划模型，再加上双 面的一些约束条件，得到双面英文复原序号，并绘出英文双面复原图片。关键词：差异度指数；0-1规划；LI NGO软件；聚类分析；高度差；残缺程度;1一、问题重述破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重 要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当 碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图 开发碎纸片的自动拼接技术，以提高拼接复原效率。请讨论以下问题：1.对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片 拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进 行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结 果以图片形式及表格形式表达。2.对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附 件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要 人工干预，请写出干预方式及干预的时间节点。复原结果表达要求同上。3.上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件 的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎 片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼 接复原结果，结果表达要求同上。二、模型假设1.假设每个碎纸片上的字和字母都没有发生扭曲。2.假设每个碎纸片的形状和大小完全相同。3.假设每个碎纸片上灰度值的提取都是完全正确的值不等于255的都是黑点三、符号说明符号符号的含义差异度指数，表示第i张碎片右侧和第/张碎片左侧的差异度；Q表示第i张碎片右侧第k个特征点的灰度值；x.j决策变量，当x,7=o时，表示第i张碎片右侧和第j张碎片左侧的不相连；时，表示第i张碎片右侧和第j张碎片左侧的相连；Su表示第j列碎片左侧与差异度最小的第i列碎纸片右侧相连：Lij表示第i块碎片右侧和第j块碎片左侧的差异度；4表示第i块碎片下侧和第j块碎片上侧的差异度；稣表示第i块碎片右侧第k个特征点的灰度值；5k表示第i块碎片下侧第k个特征点的灰度值；%=o时，表示第i张碎片右侧和第j张碎片左侧的不相连；2%=i时，表示第i张碎片右侧和第j张碎片左侧的相连：AOu=o时，表示第i张碎片下侧和第j张碎片上侧的不相连：%=i时，表示第i张碎片下侧和第j张碎片上侧的相连；高度差表示第i块碎片第一行文字中心到第i碎片上侧边缘的高度与第j块碎片第一行文字 中心到第j碎片上侧边缘的高度H j之间的差值；四、问题一分析与模型建立、求解4.1问题一的分析问题一要求对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立 碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片 数据进行拼接复原。参考文献1,由于每列中文和英文碎片都有左侧和右侧，需要考 虑每一列碎片的左侧和右侧与其他列的左侧和右侧差异，每列碎片边缘灰度已知，通过 任意列碎片右侧和任意列碎片左侧的差异值可以定义差异度指数（同一列碎片的左侧与 右侧的差异度定义为无穷大），从而得到差异度特征矩阵。然后可以通过0T规划模型，以第j张碎片左侧与第i张碎片右侧的差异度最小为 目标函数，以第i张碎片右侧与第j张碎片左侧是否相连为决策变量，以每张碎片右侧 一定与某张碎片左侧相连、每张碎片左侧一定与某张碎片右侧相连为约束条件（复原图 片最左侧一定与最右侧的差异度最小），找到中文和英文碎片的拼接复原顺序，MATLAB 编程得到复原序号，从而得到出中文与英文复原图片。为了检验中文与英文碎片拼接复原顺序是否正确，建立了 MATLAB搜索算法模型，可以得到中文与英文碎片拼接方法，MATLAB软件可以直接画出中文与英文复原图片。结 果表明两种方法得出的中文与英文复原顺序相同，复原图片相同。同时人工检验出中文 与英文复原图片中无明显语法、词语和单词错误，证明复原图片正确。4.2问题一的碎纸片拼接复原模型建立先提取碎纸片边缘差异信息，再进行图片拼接复原，具体步骤如下：（1）提取信息：差异度指数用差异度指数来衡量任意列右侧边缘与任意列左侧边缘差异。定义差异度指数表示第，张碎片右侧和第/张碎片左侧的差异度，为第i张碎 片右侧与第j张碎片左侧的对应灰度值之差的绝对值的累和。公式如下：”1980C=X-cjk1=U,-,19,j=1,2.19,当，制时（）ij k=l8,当i=j时其中：品表示第i张碎片右侧第k个特征点的灰度值C用表示第j张碎片右侧第k个特征点的灰度值3说明：品和C的值已知，将附件1和附件2中19张碎片数据带入MATLAB软件可以得到每张碎片的1980个灰度值；从而得到差异度矩阵如下：通过MATLAB编程计算出具体值如下：表一：附件一中文任意碎片差异度G差异度G1列左侧2列左侧3列左侧4列左侧5列左侧6列左侧7列左侧8列左侧9列左侧10列左侧j列左侧1列右侧I nf13094511610314144810094211195525661106097859491111182列右侧123423I nf12658912565233616100027112423119895935271116043列右侧127946114084I nf1050351047459692812241490256827441016734列右侧10625312762995945I nf113330106911111305103203838871128105列右侧110732116398100076115677I nf22300118792105006575641040876列右侧120399113365105551124588114916I nf1226938746581403246507列右侧84410106346744681140798670949380I nf628100803698列右侧111607113205109137136976102362111309107605I nf846291129369列右侧971811109651168891241121071147860111188398983I nf11139410列右侧11148411862010928812147111806910447212446410150090152I nfi列右侧表二：附件二英文任意碎片差异度岫差异度G1列左侧2列左侧3列左侧4列左侧5列左侧6列左侧7列左侧8列左侧9列左侧10列左侧j列左侧1列右侧I nf8531082752765677956224368985428960089490897152列右侧68051I nf800855157474947102845869457199767927183563列右侧5829562297I nf402266457988857778251982366511693244列右侧669776386970269I nf7811792269252777688382185725225列右侧3489739595546630I nf83053616754614357641507866列右侧5764919399767274548276087I nf790896994580753662107列右侧667477727719737517986301585575I nf7148774927804368列右侧70250745807465457731809149252071274I nf75578707579列右侧6250663054701424022571430809388231068430I nf7577510列右侧689017092777477538548212397435887038446184145I nfi列右侧4（2）中文和英文碎纸片拼接复原模型以第j张碎片左侧与第i张碎片右侧的差异度最小为目标函数，以第i张碎片右侧 与第j张碎片左侧是否相连为决策变量，以每张碎片右侧一定与某张碎片左侧相连、每 张碎片左侧一定与某张碎片右侧相连为约束条件，建立0-1规划模型。19 19i=l j=2xu=1,J=1,2,.,19s.t X/=l,i=1,2,.,19=0或 1其中：勺为决策变量，%=0时，表示第，张碎片右侧和第j张碎片左侧的不相连；闯=1时，表示第，张碎片右侧和第j张碎片左侧的相连；4.3问题一中英文碎片拼接问题模型求解模型求解算法如下：（1）运用MATLAB编程提取19列中文和英文碎片左侧和右侧的灰度值，计算出差异 度指数，得到差异度矩阵，结果见表一和表二。（2）运用LI NGOH.0软件，将上述0-1规划问题的目标函数与约束条件带入LI NGO 软件中（附录一为中文碎片拼接复原LI NGO算法，附录二为英文碎片拼接复原LI NGO算 法），结果如表三和表四。（3）运用MATLAB编程（编程见附录三）得到中文和英文碎片的复原序号，结果见 表五和表六，可以直接得到中文和英文复原图片，图片见附录四和五。表三：中文碎片连接方法决策变量为1X(2,5)X(l,7)X(3,17)X(4,ll)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-0807-1708-1409-13决策变量为1X(ll,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(l,6)X(2,10)X(3,8)X(4,7)X(5,4)X(6,2)X(7,3)X(8,16)XX(10,14)实际连接点00-0501-0902-0703-0604-0305-0106-0207-1508-1209-13决策变量为1X(ll,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-1811-012-1413-1014-1715-1816-0417-1618-115得到连接方法以后，可以使用MATLAB编程（见附录三）得到中文和英文碎片的复 原序号如下表：表五:中文碎片的复原序号008014012015003010002016001004005009013018011007017000006表六：英文碎片的复原序号003006002007015018011000005001009013010008012014017016004用MATLAB编程（附录四）可以直接拼接出中文和英文碎片复原图片，程序结果截图如图一:Current Fol det：E:mt b|g 四I m Edit or Mdin_PrQ.m x Workspacei 璃-|1T|+rr|x 噫啜 qi%此模块是程序的主要执行程序2%通过调用写好的各个模块(子程序等)进行运算3%4%5%入数据并得到特征向量6%附件17 DATA1 TeZhenl _Lie TeZhenl _Hang=Dac8%附件29-DATA2 TeZhen2_Lie TeZhen2_Hang=Da(10%附件311-DATA3 TeZhen3_Lie TeZhen3_Hang=Da12%附件413-DATA4 TeZhen4_Lie TeZhen4_Hang=Dac14%附件澈特殊，所以需要使用新的行列函数15%附件516-DATA5_A DATA5.B TeZhen5_Lie_A TeZhe17 TeZhen5_Hang_B=DaoRuShuJu_AB(18%当，I”他闺，桓父曹方日吃一画国画匾电I St ack：rName 上 回 DATA1 叵DATA2 叵1DATA3 叵|DATA4 叵1 DATA5_AFigure 1Efe Edit View I nsert Tool s Deskt op Window Hefc口目 H 4|Q|X 踮 W|131 国|El献上层搂婆诚下佬淮古汴“毕手指吴云，人与X天嗔送，虎断后夜松江月满维瑟衣巾莎塞范村里村上响澡车,牛衣古柳卖黄 II.海宗珠登一生王.活璘近帝战.脑脂券与匀淡，偏向脸边浅.小郑春 常漏记，二南依旧能诗 更右舶鱼先切绘，儿军结微知自古t fl从休务 B,何妨孤唱才吟天香云至作吞胡“出中人半弊，帘外3?信深.双T年 BL饼限稳波后SI翠”舞用原“掌上身轻其态斜/理轻箓两凤，琴场 淡胡双冽为诋流解不归家.铤包门前过目“我劝离张妇去好，从来口己忘情“尘心消尽恒心平,江南与*北，W 处不耍行：用为PH：惟金案授就王，间时梦公南，旧恨前欺，心事也无融 里如带a丑由.s Am.-mat s,ixiwacra卜物.若再汨图一：复原图片程序结果截图中文与英文碎片复原的图片见附录四和五。复原过程不需要人工干预，可完全通过LI NGO软件和MATLAB编程实现。4.4中文和英文碎片拼接复原方法检验为了检验差异度指数和0-1规划模型得出的复原顺序和复原图片的准确性，利用 MATLAB搜索算法模型：S,7=面吗,)给定时,，取 1,2,.,19。=1,2,.,19)(4)已通过MATLAB编程得到第i张碎片右侧和第j张碎片左侧的差异度.，见表一与 表二。对表一和表二按照列搜索，依次搜索找到与第j列碎片左侧相连的差异度最小的 第i列碎纸片右侧（即匹），即第i列碎纸片右侧与第j列碎片左侧相连，对于每一列 碎纸片需要搜索19次，共需要搜索361次，使用MATLAB搜索算法即可实现（编程见附 录三）可以得到中文和英文碎纸片的连接方式，如下表：表七：中文碎纸片连接方式6表八：英文碎纸片连接方式第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-006010-008002-007001-009第i列右侧连接第j列左侧013-010018-011008-012009-013012-014007-015017-016014-017015-0180T规划模型清晰明了，同时运算简单，运算速度快。MATLAB搜索算法搜索次数较 多，运算速度慢一些，但结果准确。所以我们使用0-1规划模型解决问题一，使用MATLAB 搜索算法检验结果。五、问题二分析与模型建立、求解5.1问题二的分析问题二要求对于碎纸机既纵切又横切的情形，建立碎纸片拼接复原模型和算法，并 针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。由于209块 中文和209块英文碎片都有左侧、右侧和上侧、下侧，与问题一相同，可以定义两个差 异度指数。根据问题一得到双目标0-1规划模型，由于决策变量较复杂，这种模型不是 很易求解，矩阵太大，也不易计算，因此提出了改进模型。改进模型，定义高度差表示第i块碎片第一行文字中心到第i碎片上侧边缘的高度口与第j块碎片第一行文字中心到第j碎片上侧边缘的高度H j之间的差值。运 用聚类分析，给定高度差阈值，按照高度不同将所有碎片分为18类。然后再以第j块 碎片左侧与第i块碎片右侧的差异度最小和第i块碎片与第j块碎片高度差最小为双目 标函数，以第i块碎片右侧与第j块碎片左侧是否相连为决策变量佝（为 20）,以每209块碎片右侧一定与某块碎片左侧相连（24=1）,每块碎片左侧一定与某块碎片右侧 7=1209相连为约束条件，建立双目标0T规划模型。找到18类中英文碎片，结 7合MATLAB编程和人工干预，将18类碎片处理为H行碎片，再利用问题一中碎片纵向 复原的方法，得到中英文复原序号，从而MATLAB编程画出中文与英文复原图片。同时 人工检验出中文与英文复原图片中无明显语法、词语和单词错误，证明复原图片正确。5.2问题二碎纸片拼接复原模型建立5.2.1问题二碎纸片拼接复原初步模型先提取碎纸片边缘差异信息，再进行图片拼接复原，具体步骤如下：（1）提取信息：差异度指数用差异度指数来衡量任意块碎片右侧边缘与任意块碎片左侧边缘差异及任意块碎 片下侧边缘与任意块碎片上侧边缘的差异。定义差异度指数4和4/：4.表示第，块碎片右侧和第/块碎片左侧的差异度，为 第i块碎片右侧与第j块碎片左侧的对应灰度值之差的绝对值的累和。表示第，块碎 片下侧和第，块碎片上侧的差异度，为第i块碎片下侧与第j块碎片上侧的对应灰度值 之差的绝对值的累和。公式如下:|L,.,-Ljk,i=l,2,L,209,j=1,2,.,209,当iw/时8,当i=，时72=l，2L209,j=1,2,209,当 i w j时8,当=j时其中：4表示第i块碎片右侧第k个特征点的灰度值；Ljk表示第j块碎片右侧第k个特征点的灰度值；。次表示第，块碎片下侧第k个特征点的灰度值；Ujk表示第j块碎片上侧第k个特征点的灰度值；说明：Lik 卬和。次、的值已知，将附件3和附件4所有碎片数据带入MATLAB软 件可以得到每块碎片的左侧、右侧和上侧、下侧灰度值；从而得到两个差异度矩阵如下：4,2 4,209 乙2,2 乙2,2098U,2。1,209U 2,1 U 2,2 02,2090209,1 0209,2 0209,209(8)（2）中文和英文碎纸片拼接复原模型以第j块碎片左侧与第i块碎片右侧的差异度最小和第j块碎片上侧与第i块碎片 下侧的差异度最小为双目标函数，以第i块碎片右侧与第j块碎片左侧是否相连为决策 变量4（为2 0）和第i块碎片下侧与第j块碎片上侧是否相连为决策变量乩（民？0）,以每块碎片右侧一定与某块碎片左侧相连每块碎片下侧一定与某块碎片 j=l209上侧相连（24=D，任意两块碎片之间可能不相连、可能左右相连、可能上下相连/=1（%+441）为约束条件，建立双目标0-1规划模型。209 209f=l J=1209 209min i=l j=lr F 9 9 2,.,2,.12020 1b 一-%鸟 弓A-209z/=l209zl=l 209zJ=l209zl=l(9其中：%二0时，表示第，张碎片右侧和第，张碎片左侧的不相连;a.=l时，表示第，张碎片右侧和第j张碎片左侧的相连；从二0时，表示第，张碎片下侧和第，张碎片上侧的不相连;9国;1时，表示第，张碎片下侧和第j张碎片上侧的相连；此模型可以得到所有碎片的连接方式。5.2.2问题二中英文碎片拼接复原改进模型由于建立的初步模型有决策变量较复杂，而且两个差异度矩阵较大，用程序实现较 困难，因此在此提出改进模型，只使用一种决策变量，具体建模过程如下：（1）提取信息：差异度指数和高度差定义差异度指数4与初步模型定义相同，但改进模型中不在使用差异度指数,定义高度差表示第i块碎片第一行文字中心到第i碎片上侧边缘的高度区与第j 块碎片第一行文字中心到第j碎片上侧边缘的高度之间的差值。公式如下：H=Hi-Hi=1,2,.,209,j=1,2,.,209,当iwj时（色）ij 0,当i=j时（2）中文碎纸片拼接复原模型以第j块碎片左侧与第i块碎片右侧的差异度最小和第i块碎片与第j块碎片高度 差最小为双目标函数，以第i块碎片右侧与第j块碎片左侧是否相连为决策变量为209（%20）,以每块碎片右侧一定与某块碎片左侧相连每块碎片左侧一定 j=l209与某块碎片右侧相连（%=1）为约束条件，建立双目标0T规划模型。/=1209 209i=l j=209 209i=l j=l期II2O9XS.t1%=。或 1其中：%为决策变量，时，表示第，张碎片右侧和第，张碎片左侧的不相连;时，表示第，张碎片右侧和第j张碎片左侧的相连；10为了将双目标转化为单目标问题，可以给定高度差阈值0.5,给定高度范围给 所有碎片进行分类，共18类，可以将此模型简化，目标函数与约束条件如下：209 2091=1 j=l.%=l,z=1,2,.,209s“%=l,j=l,2,.,209（12）H.0.5a”=0或 1-J再结合人工干预可以得到所有碎片的连接方式。（3）英文碎纸片复原模型对附件四英文碎纸片建立复原模型与中文碎纸片模型基本相同，但由于中文是方块 字，同一行中文字上下侧边缘基本对齐，英文是非方块字，上下边缘的灰度值不大，因 此应该扩大改进模型的阈值，对英文碎片进行分类，可以将高度差阈值调节为 其余约束条件不变，从而得到所有碎片连接方式，得到复原序号。5.3问题二中英文碎片拼接复原模型求解5.3.1模型算法（1）找到每块碎纸片第一行文字中心到碎纸片上侧边缘的高度第一步：每块碎纸片带入MATLAB软件中可以得到一个像素点的灰度矩阵,将 每个矩阵归一化：_ fl 51（/:即3_BAAB 用 Q3_BA8At*l r-iTu_m-O X,，,一”工务 J U *）（*）1九2.0幻*x 3JE则2Q3：口工*15-I X）+11 X 会桑9 5.*BwamMit T 田 ma a-QS.TZMnrMTUMat MATA3）：ffl QS.BAfiA JgQ3JWl 卬 3 I rMfft I eoh&Kw JJfrifcw g d）U x X-a DQ 清泪斑斑，挥断柔肠寸。咀人间。背灯18?温抗尽残枚粉，香季阑珊芳草.客里风光，又过清明节。小院黄昏人忆别落红处处闻啼鬻,岁云暮，须早计，要褐裘。故乡归去千里，佳处辄迟留.我醉歌时君和，醉倒须君 MM Z.MU Q4.UM 0）,以每块碎片右侧一定与某块碎片左侧相连38 38每块碎片左侧一定与某块碎片右侧相连（2x=l），某块碎片a、b面 j=l k=i一定与某块碎片a、b面中任意一面相连或不相连（+”四）0）,以每块碎片右侧一定与某块碎1538 38片左侧相连（2Xj&=l）,每块碎片左侧一定与某块碎片右侧相连（2Xj%=1），某块 j=l 女=1碎片a、b面一定与某块碎片a、b面中任意一面相连或不相连或Xjk+Xj（j_i）l）,为约束条件，建立0-1规划模型。38 38min与X欣j=l k=l38Ex/*=1(/=1,38)k=l38Xxjk=1(%=1“，38)s.ti)l(j=1,3,5.,37)X成+Xj“T)l()=2,4,6”.,38)Xik=0或1(13)其中：X/&为决策变量，Xj%=0时，表示第j张碎片右侧和第k张碎片左侧的不相连；%7,=1时，表示第j张碎片右侧和第k张碎片左侧的相连；按以上模型可将分成的n类分别按横向排好序，得到n个长纸条。然后回到第一 问的模型，可将n个长纸条按纵向排好序，即可得到复原图片。6.3问题三碎纸片拼接复原模型求解6.3.1模型算法（1）首先根据英文字母的字体特征和书写特征对每块碎纸片进行分类。1.每个单词最多占一行，一行占三个格子；经计算每块碎纸片大概可以容纳三个单词，每个单词占像素点为602.定义每块碎纸片的上边缘单词的残缺程度：有残缺的单词所占像素点（）“一每个单词所占像素点意义：Q=0或1,上边缘可容纳一个完整的单词。Q越小，上边缘单词残缺程度越大。以Q来表示每个碎片的特征。3.以上提供信息比较精细，将具有相同特征的分为一类，通过MATLAB编程和人工干预,可分为H类。其中：01=0.3,Q2=0.5,Q3=0.47 Q4=0.83,Q5=0.75,Q6=0.8,Q1=0.9,（28=0.85,2=0.1,Qio=O.7,01=0.6716可以根据以上Q值结合人工干预可得分类，见下表：表十二：附件五英文分类Q116404702002908118911012510806607801818315015513614711114019150702161301030517142009190503011720Q2393130613762200591120140811011007040605021211160900031305Q35528511822399059331170309130709031619181908201719081516Q45972234181976343611910191110051011090402090910001205130410Q5362650369691463443914020510200615170102110115052001191811Q624728449284788737461820081313050813061804120303141504Q770681694471651803983204121806121807121116160006041617061915Q8022878587758768235706151407050112031202081402041700190107Q90279944602945485206Q10020160413071614150008170619030911101802321906911805170570Q113201400020807081712001806000710030014154107045663594752784.对每一类运用0-1规划模型，结合MATLAB编程和人工干预进行排序，可以先将11行 进行行排序，然后按照问题一列拼接复合模型排序。6.3.2模型结果表十三：附件五单面英文复原序号136b047a020a164b081b189b029 a018b108 a066 a110a147b183b150a155a140 a125a111b078b00515214706005901407914412002212419 2025044178076036010089aaaaaaaabaaabaababa1432000861871310561380451370619 4b9 8a121038030042084153186bbbbbbaabbaaabbab08303909 717507209 313208719 818103415620617319 4169161lib19 9abaabababbaabbbbab09 020316200213907004117015100116611506519 1037180149107088abbbbbabbbbbbababab01302405714220806410201701202815419 7158058207116179184114aaaabbbbabbaaaabbba03515907319 316313002120205317701601909 219 0050201031171146aabbaababbbbbbaaaba17附件五双面英文复原图片见附录九。172a122 a182 b040 a127a188a068b008b117b167 a075b063b067 a046a168a157 a128 a19 5a165b105204141135027080000185176126074032069004077148085007003abababbaabbaaaabbbb00914508220501510111812906205207103311916009 5051048133023babababbaabbababaab05419 611210305510010609 104902611313410400612310909 604309 9bbaabbbabbaaaaaabaa七、模型的评价与推广7.1模型的优点问题一中，纵切附件一和附件二中英文，每个碎纸条都比较长，提取的边缘灰度值 包含纸片的信息比较多。因此每个碎纸片边缘上的区分度比较大。按边缘差异度c优 化计算时，对于中英文碎纸片复原都很成功。同时我们不仅建立了 0-1规划模型运用 LI NGO软件求解此问题，还运用了 MATLAB搜索算法检验了问题一的结果，发现两种 方法得到的复原序列和复原图片完全相同。问题一中完全运用了 MATLAB编程和 LI NGO软件，没有使用人工干预。问题二中，需要横切和纵切数据，边缘上的灰度信息已明显难以区分两个不能拼在 一起的碎纸片，直接用边缘差异度优化计算时即使对于汉语误差也较大，需要的人工干 预比较多。因此在双目标0-1规划问题基础上，提出了改进和简化模型，根据汉字和英 文的字体特征和书写特征提取不同的高度值，依据高度值进行分类后，在将分类结果运 用第一问纵向优化计算时，拼接比较成功，人工干预比较少。这说明对于每个碎纸片提 取的特征信息越多，拼接时人工干预的就越少，然而相应的会增加模型的复杂度。因此 信息提取要合适。同时在问题二中考虑了中文和英文的轮廓不同，因此对英文碎片复原 模型进行了改进。问题三，提出了单词残缺度定义，定量的描述了英文碎片的特征信息，构成了算法 的核心内容，很好的将纵横碎片快速有效的分类，为碎片的拼接复原提供了保障。7.2模型的缺点问题二中文和英文碎片的复原模型存在差异，但是我们仅通过改变高度差阈值，对 中文和英文碎片进行了不同的分类，这个分类方式不够精确，需要进一步思考，找到更 加合理的约束条件，对中文和英文碎片进行不同的分类。同时在英文拼接复原模型中，采用的人工干预过多，说明建立的英文拼接复原模型需要进一步改进。问题三英文双面碎片，由于聚类分类不够完美，算法实现较困难，所以采用的人工 干预较多，人工进行。7.3模型的推广碎纸片拼接复原模型可以推广到对文物古迹、破碎物体、司法物证复原、历史文献 修复以及军事情报获等情况。参考文献:18 19 4韩忠庚，数学建模方法及其应用，北京：高等教育.，2005年。3李刚，MATLAB函数速查手册，北京：清华大学.，2013年。2龚纯，精通MATLAB最优化计算，北京：电子工业.，2009年。207页,2012年。1罗智中，基于文字特征的文档碎纸片半自动化拼接，计算机工程与应用，201205：附录一：运用LI NG011.0软件编程拼接复原中文碎片model：sets：right/1.19/;left/1.19/；links(right,left)：c,x；endsetsdata：!缶定义为8000000代表自身和自身不会边缘相连；enddatamin=sum(links:c*x)；for(left(j)：sum(right(i)：x(i,j)=1)；for(right(i)：sum(left(j)：x(i,j)=1)；end20附录二：运用LI NGO.0软件编程拼接复原英文碎片model：sets：right/1.19/；left/1.19/；links(right,left)：c,x；endsetsdata：!任定义为8000000代表自身和自身不会边缘相连；335738000030XOCOOOO800000。8000CO0enddatamin=sum(links：c*x)；for(left(j)：sum(right(i)：x(i,j)=1)；for(right(i)：sum(left(j)：x(i,j)=1)；end21附录三：MATLAB7.12.0(R2011a)编程得到主程序和多个子程序可求出附件一、附件二、附件三、附件四和附件五的中英文碎片的复原序号，搜索检验问题一模 型结果，对问题二中英文按高度分类且编程画出附件一、二、三和四中英文碎片 复原图片%Main Pro.m为此模块显程序的主要执行程序为通过调用写好的各个模块(子程序等)进行运算为运行条件：%将此程序、各个功能模块(m文件)及题目提供的附件文件夹放在同一个目录中，7.12.0(R2012a)中进行运算，使用“CD：工作目录、”命令切换上至工作目录，然后运行Main_Pro.m主程序%(为导入数据并得到特征向量%附件1DATAl=DaoRuShuJu 八附件 1 ,19);考附件2DATA2=DaoRuShuJu(，附件2 ,19);告附件3DATA3=DaoRuShuJu 八附件3 ,209);%附件4DATA4=DaoRuShuJu(，附件4 ,209);会附件5较特殊，所以需要使用新的行列函数%附件5DATA5_A DATA5_B=DaoRuShuJu_AB(，附件5 ,209);%为读入数据存储阵%load DATA.mat%上计算出连接数据%附件1cydHangl cydLiel=ChaYiDu(DATA1);cydZhil LianJiel=min(cydLiel)；为最小差异值及连接关系list_l=PaiXu(LianJiel,9)；figure；Ql_TuPian=HuiTu(list_l(2,:),DATA1);为绘制图像title附件1复原图I；imwritse(Ql_TuPian J问题:L_中文图片复原.png，)；为保存为png格式图像%附件2cydHang2 cydLie2=ChaYiDu(DATA2);22cydZhi2 LianJie2=min(cydLie2)；为最小差异值及连接关系l