数学建模国赛国家一等奖论文.pdf

第1期 破碎文件的拼接在司法物证复原、历史文献 修复以及军事情报获取等领域都有着重要应用。 传统的拼接复原由人工完成， 准确率较高， 但效率 很低。 特别是当碎片数量巨大， 人工拼接很难在短 时间内完成任务。 随着计算机技术的发展， 人们试 图开发碎纸片的自动拼接技术，以提高拼接复原 效率。文献1给出 5 个碎纸片实例， 对应三个复 原问题， 要求分别建立拼接复原模型和算法， 并完 成复原。 如果复原过程需要人工干预， 需写出干预 方式及干预的时间节点。 1问题一 一页单面印刷文字的文件被纵向切割成 19 条碎纸片， 按 018 编号， 且顺序打乱。附件 1、 附 件 2 1 给出中、 英文各一页文件的碎片图像， 要求 拼接复原。 1.1数字化图像处理 将图像分为有限个离散点 （x， y） ， 每个离散点 收稿日期：2014-09-12 作者简介：王智刚， 沈晔星， 郭羽涵均为参赛选手； 本文获 2013 年高教社杯全国大学生教学建模竞赛本科组全国一等奖， 指 导教师为邱中华。 破碎文件碎纸片的自动拼接复原 王智刚 a，沈晔星a，郭羽涵b，邱中华c （南京邮电大学a.通信与信息工程学院；b.电子科学与工程学院；c.理学院， 南京 210023） 摘 要： 针对文献1提出的三个问题， 讨论文件碎纸片的计算机自动拼接技术。利用像素点作数字 化图像处理， 引入图像梯度和碎片边缘特征差异度计算公式， 建立最短路径的规划模型， 对碎片进行 最优化匹配； 根据中英文字特点， 给出不同的碎片行特征确定方法， 据以解决聚类与纵向拼接。经过 LINGO 运行， 得到了 5 份碎片实例的拼接复原结果。 关键词：碎纸片拼接；数字化处理；最短路径；边缘特征；差异度；行特征；聚类 中图分类号：TP391.41 文献标志码：A文章编号：1008-5327（2015）01-0067-05 Splice Recovery of Broken File Fragments WANG Zhi-ganga, SHEN Ye-xinga, GUO Yu-hanb, QIU Zhong-huac (a.School of Communication and Information Engineering; b.School of Electronic Science and Engineering; c.School of Science, Nanjing University of Posts and Telecommunications, Nanjing 210023, China) Abstract： As for three questions presented by document1, the paper discussed the computer automatic splic ing technology of file fragments. Author processed digital image by using pixel, and introduced the image gra dient and difference degree calculation formula of fragment edge characteristic; then it established planning model with shortest path to optimally match fragments. The paper presented different methods to determine different fragments line characteristics according to characteristics of words in both English and Chinese. Fi nally, recovery results of five slice fragment instance were attained after LINGO operation. Key words: fragments splice; digital process; shortest path; edge characteristic; different degree; line charac teristics; cluster 29 1 Mar. 15 第29卷第1期 15年3月 ! 南通职业大学学报 UNIVERSITY doi:10.3969/j.issn.1008-5327.2015.01.017 67 南 通 职 业 大 学 学 报15年 都有特定的位置和灰度， 称为像素点 2 ， 图像的灰 度定义为二维离散函数 f（x， y） 。 利用 MATLAB 的 数字图像输入功能可建立函数 f（x， y） 。 由于图像并不只是黑和白，文字周围还存在 灰色部分，所以实际处理时，黑色像素点取数值 255， 灰色像素点根据灰度取值 2541， 白色像素 点取值 0。 取每张碎片左、 右两个边缘纵向上的像 素点 f（1， y） ， f（72， y） 作为该碎片的特征点。 1.2图像的梯度与匹配度 对图像的二维离散函数求导，可反映图像的 边缘特征。定义图像梯度 3， 4 为 G（x， y）= f（x + 1， y）- f（x， y） + f（x， y + 1）- f（x， y） ， 碎片 i 与碎片 j 的边缘特征差异度为 Rij= 1 n n y = 1 移Gi（k， y）- Gj（1， y）， 其中 n 为总行数。由此可得碎片之间的梯度差距 表 （Ri j）1919， 在除 Ri j= 0 以外的有效数据中， 最小 数值代表两碎片的图像梯度差距最小，匹配度最 高， 有可能是相邻的碎片。 1.3最短路径的规划模型 利用最短路径算法建立碎片匹配的最优化模 型。做出如下类比： 碎片间两两的边缘特征差异两两碎 片间的 “路径” ； 是否拼接该碎片是否 “经过” 该碎片。 引入 0-1 矩阵 （Bij）1919， 其中 Bij= 1 表示经过 该点， Bij= 0 表示不经过该点。 优化模型的目标函 数为经过所有碎片的路径最短，约束条件为路径 能够经过所有的碎片且每个碎片仅经过一次。 最短路径的数学模型为 5， 6 min f = 18 i = 0 移 18 j = 0 移RijBij s.t. 18 i = 0 移Bij= 1， 18 j = 0 移Bij= 1， Bij B ji= 0， 0i， j18， ij。 1.4模型求解 将图像数字化处理为像素点后，可以确定左 列特征点都为白点的碎片为第一片，此后基于图 像梯度和文字边缘特征， 根据上述最短路径模型， 用 LINGO 求解最优路径， 无需人工干预即可依次 确定碎片的最佳拼接顺序。 实际计算的结果：中文文件由左到右的复原 碎片编号为： 8， 14， 12， 15， 3， 10， 2， 16， 1， 4， 5， 9， 13， 18， 11， 7， 17， 0， 6。 英文文件由左到右的复原碎片编号为： 3， 6， 2， 7， 15， 18， 11， 0， 5， 1， 9， 13， 10， 8， 12， 1 4， 17， 16， 4。 按这一顺序拼接附件 1 和附件 2 的图片， 即 可得到中文文件和英文文件的复原图。 2问题二 一页单面印刷文字的文件被纵向又横向切割 成 1119209 块相同大小的矩形碎纸片，按 0 208 编号， 附件 3、 附件 4 1 给出中、 英文各一页文 件的碎片图像， 要求拼接复原。 2.1中文碎片的复原 2.1.1行特征及碎片的聚类 引入行特征： 从底部起， 取第一个纵向完整的 行到碎片下边缘的间距 （用像素点的个数表示） 为 该碎片的行特征 d， 如图 1 所示。 打印稿的行间距为 68 个像素点，所以应有 d68。 如果出现 d 68， 说明少了一到两行文字， 可减去 68 的整数倍， 使之恢复到 d0， 68。 由于附件 3 中的碎片及文字都是正向放置， 所以同一行向碎片的行特征应当一致，由此可以 按照行特征将碎片聚类。不过有些汉字的长度不 一样， 会使少部分同行碎片的行特征存在差异， 但 差异很小， 不会影响聚类。聚类结果为： d = 2， 9， 15， 21， 28， 33， 40， 46， 52， 58， 64， 共分为 11 类， 每类碎片的个数均为 19。 在该聚类的基础上，可用 1.3 节的最短路径 模型对每一类碎片实施行拼接。 2.1.2行碎片的纵向拼接 单张碎片像素为 72180， 即单张碎片纵向有 180 个像素点， 上下吻合拼接的两张碎片中， 会有 23 个完整的文字行。 设上、 下两个碎片的行特征 分别为 d0和 d， 则 d0+（180 - d） 恰好容下这些完 类比 类比 图1中文行特征 dd 68 第1期 整的文字行， 即 d0+（180 - d） 为 68 的整数倍， 由 此易找到各行的下一行碎片的行特征。 例如对于 d0= 2， 可找出 d = 46， 满足 （2 180 46） 68 2。由于同行文字的长度也会有 微小差别， 所以下片行特征也会有微小差别， 但不 影响对应关系。例如 d0= 9， 可找出 d = 52， 满足 （9 180 52） 68 2.012。各行的下片行特 征对应如下： 2 46， 9 52， 15 58， 21 64， 28 2， 33 9， 40 15， 46 21， 52 28， 58 33， 64 40。 该对应有循环性。然后用上下边缘特征差异 为 0 的后者作为拼接段落的开头。中文段落开头 行特征为 33，由上述对应关系递推拼得整个段 落。拼接复原的结果如表 1 所示。 表1中文文件复原拼接的碎片编号次序表 序号12345678910111213141516171819 14954651431862571921781181909511221292891188141 2611978676999162961317963116163726177205236 3168100766214230412314719150179120861952618718 4381484616124358118912210313019388167258910574 5711568313220017803320219815133170205851521652760 6141283159821991351273160203169134393151107115176 794348418390471214212414477112149971361641275843 812513182109197161841101876610615021173157181204139145 929641112015921804837755544206101049817217159 107208138158126681754517401375356931537016632196 1189146102154114401512071551401851081174101113194119123 2.2英文碎片的复原 2.2.1英文碎片的相对行特征 英文字母中存在 5 个特殊字母 g， j， p， q， y， 其 下方拖出一个尾巴，故不能沿用图 1 的中文碎片 行特征的确定方法。 模拟英文单词本， 对英文字符进行切割， 分为 上、 中、 下三个部分。分析英文单词的结构特征可 以发现， 每行字母中部 7225 像素部分的像素点 最为密集， 所以利用 7225 的长方形搜索框从碎 片底部以 1 个像素点为间隔向上移动覆盖，搜索 框覆盖区域有效点最多的地方即为字母中部， 如 图 2 所示。 设搜索框的下边界纵坐标为 d， 纵向长 h=25， 搜索模型为 max d + h - 1 y = d 移 72 x = 0 移f （x， y） ， s.t.0 d n - h + 1。 英文稿的行间距为 64 个像素点，所以应有 d64。 如果出现 d 64， 说明有空行， 或者搜索到 的密集区不在最后一行， 如图 3 所示。 这时可减去 64 的整数倍， 使之恢复到 d0， 64。 搜索得到的 d 并不整齐，故称之为相对行特 征， 聚类也要以范围分。聚类结果为 d = 6 10， 16 19， 26 31， 38 42， 50 52， 59 62，共分为 6 类， d = 50 52 的碎片个数为 19， 其他 5 类的碎片个数均为 38。 2.2.2英文碎片的拼接 用类似于 1.3 节的最短路径模型对每一类碎 片实施横向行拼接。同类碎片个数为 38， 说明有 两行碎片混在了一起， 部分碎片的边缘是白色， 此 类特殊碎片会被误连接， 由 LINGO 自动拼接的序 图2搜索框 图3锁定字母不在最后行 搜索框 上 部 下 部 中 部 王智刚， 等： 破碎文件碎纸片的自动拼接复原 69 南 通 职 业 大 学 学 报15年 列中出现这种特殊碎片， 其编号为： 202， 19， 171； 86， 134； 70， 201； 2， 143， 149， 28， 191； 20； 81， 159。 在序列中将这些碎片处的拼接断开，以人工 方式将这些片段进行移动拼接。 由于英文碎片的行特征不够明显，所以在纵 向拼接时， 主要考虑碎片上、 下边界的边缘特征差 异， 辅助考虑上、 下片行特征的递推关系。 碎片上、 下边界的边缘特征差异由下式给出： Rij= 1 n 72 19 y = 2 移Gi（y）- Gj（y）， Gi（y）= 2fi（180， y）- fi（179， y）- fi（180， y - 1） ， Gj（y）= 2fj（1， y）- fj（1， y - 1）- fj（180， y） 。 利用已成行碎片上、下边界的边缘特征差异 Rij先对行碎片进行拼接，具体方法与横向拼接 相同，对于边缘特征模糊的行碎片再辅助以行特 征的递推关系来确定位置。 英文碎片拼接复原的结果如表 2 所示。 表2英文文件复原拼接的碎片编号次序表 序号12345678910111213141516171819 11917511154190184210418064106414932204653967147 2201148170196198941131647810391801012610061728146 38651107294015818698241171505595892303746127 419194931418812112610515511417618215122572027116582 5159139112963138153533812312017585501601879720331 6204110811613673362071351576431994517379161179143 72082174961119331421686216954192133118189162197112 8708460146817413719584717215696239912290185109 91321819569167163166188111144206313034131102527178 1017142662051015774145831345518563516918315244 1181771282001315212514019387894872121771240102115 3问题三 一页印刷文字的双面打印文件被切割成 11 19209 块相同大小的矩形碎纸片，按 000a， 000b208a， 208b 编号， a， b 表示同一碎片的两个 面， 附件 5 1 给出一页英文双面打印文件的碎片 图像， 要求尝试拼接复原。 3.1依据相对行特征聚类碎片 对于英文字母，用相对行特征来表征碎片特 征。 附件 5 中的碎片无法直接按面分类， 但可以根 据同一碎片正、 反面的相对行特征一致， 先将同行 的碎片聚类。相对行特征的确定方法与 2.2 节一 致， 聚类结果为 d = 01， 811， 2023， 2833， 4044， 5254， 共分为 6 类， d = 5254 的碎片个数为 19， 其他 5 类的碎片个数均为 38。 3.2建立各行拼接的优化模型 碎片有正反面之分，同类碎片之间有四种拼 接方式： ia ja，ia jb，ib ja，ib jb。 设聚类后同行的碎片数为 p。在每种拼接方 式下，某一碎片与同行的每个碎片拼接都会产生 一个边缘特征差异度 Ri j， ia ja 和 ia jb 连接的边 缘特征差异最小分别为： min p i = 1 移 p j = 1 移Ria，jaB1ij+ p i = 1 移 p j =1 移Rib，jbB2ij， min p i = 1 移 p j = 1 移Ria，jbB1ij+ p i =1 移 p j =1 移Rib，jaB2ij。 ib ja 和 ib jb 连接的边缘特征差异最小与之 类似。 利用贪心算法进行拼接复原。 对于 a 面碎片， 若 an作为首片被拼接碎片， 可按照上面两个最小 化模型寻找同行碎片中边缘差异度最小的碎片 am （b m） 与之拼接， 再以 am （b m） 作为新的被拼接碎 片 an， 寻找对应的 am （b m） ， 依次递推。 由于存在左右边空白的特殊碎片，它与其他 存在白边的碎片能达到最优匹配，所以在用上述 模型自动拼接时， 需要进行人工监视， 当出现特殊 70 第1期 序号12345678910111213141516171819 1136a 047b 020b 164a 081a 189a 029b 018a 108b 066b 110b 174a 183a 150b 155b 140b 125b 111a 078a 2005b 152b 147b 060a 059b 014b 079b 144b 120a 022b 124a 192b 025a 044b 178b 076a 036b 010a 089b 3143a 200a 086a 187a 131a 056a 138b 045b 137a 061a 094a 098b 121b 038b 030b 042a 084a 153b 186a 4083b 039a 097b 175b 072a 093b 132a 087b 198a 181a34b156b 206a 173a 194a 169a 161b11a199a 5090b 203a 162a 002b 139a 070a 041b 170a 151a 001a 166a 115a 065a 191b 037a 180b 149a 107b 088a 6013b 024b 057b 142b 208b 064a 102a 017a 012b 028a 154a 197b 158b 058b 207b 116a 179a 184a 114b 7035b 159b 073a 193a 163b 130b 021a 202b 053a 177a 016a 019a 092a 190a 050b 201b 031b 171a 146b 8172b 122b 182a 040b 127b 188b 068a 008a 117a 167b 075a 063a 067b 046b 168b 157b 128b 195b 165a 9105b 204a 141b 135a 027b 080a 000a 185b 176b 126a 074a 032b 069b 004b 077b 148a 085a 007a 003a 10009a 145b 082a 205b 015a 101b 118a 129a 062b 052b 071a 033a 119b 160a 095b 051a 048b 133b 023a 11054a 196a 112b 103a 055a 100a 106a 091a 049a 026a 113b 134a 104b 006b 123b 109a 096a 043b 099b 碎片时， 中断递推过程， 取出特殊碎片进行人工的 移动、 拼接， 再恢复流程完成最后的优化复原。尽 量拼接出较长序列， 并由人工判定正确性， 再组合 之前被筛除的数据， 得出完整序列。 实际人工干预 拼接的碎片编号为： 158， 184； 55， 106； 119， 15， 132， 87， 173； 129， 17； 178， 147， 36， 137。 3.3行碎片的纵向拼接 英文碎片的纵向拼接