2013关于数学建模B题,碎纸片拼接技术

2013高教社杯全国大学生数学建模竞赛 承  诺  书 我们仔细阅读了《全国大学生数学建模竞赛章程》和《全国大学生数学建模竞赛参赛规则》（以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛网站下载）。 我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 有关的问题。 我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。 我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性。如有违反竞赛章程和参赛规则的行为，我们将受到严肃处理。 我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。 （论文纸质版与电子版中的以上信息必须一致，只是电子版中无需签名。以上内容请仔细核对，提交后将不再允许做任何修改。如填写错误，论文可能被取消评奖资格。） 日期： 2013  年  9 月  16  日 赛区评阅编号（由赛区组委会评阅前进行编号）： 2013高教社杯全国大学生数学建模竞赛 编 号 专 用 页 赛区评阅编号（由赛区组委会评阅前进行编号）： 赛区评阅记录（可供赛区评阅时使用）： 评 阅 人                     评 分                     备 注                                           全国统一编号（由赛区组委会送交全国前编号）： 全国评阅编号（由全国组委会评阅前进行编号）： 碎纸片的拼接复原 摘  要 本文主要结合司法鉴定这一应用背景，对于给定的来自同一页印刷文字的碎纸机破碎纸片，建立模型，并对其进行拼接复原。 针对问题一：首先，拼接碎片前对碎片图像要进行灰度处理。其次，利用Matlab编程获取碎纸片边界特征，进而获取碎纸片内文字行方向、间距等文字行特征。再次，利用最小二乘原理对碎纸片边界进行差值处理，同时，对处理后的数据进行了筛选，剔除异常数据，筛选出最小数据。最后，对所筛选出的数据进行人工干预。 针对问题二：对于碎纸机既纵切又横切的情形，碎片内文字图像的个数是获取文字行方向的关键。首先，对碎纸片进行预处理，即对物体碎片灰度处理，得到碎纸片的数字图像；其次，利用算法进行碎纸片匹配，通过匹配算法找到相互匹配的碎纸片；最后进行碎纸片的拼接复原，将相互匹配的碎纸片拼接在一起，得到最终的结果。 针对问题三：由于该碎片数据是英文印刷文字双面打印文件的碎片数据，故首先对碎纸片进行灰度处理,拼接出复原图的边界，其次进行碎纸片的相互匹配，通过匹配算法找到相互匹配的碎纸片，接着进行拼接复原，最后对异常数据进行整理。 该题的关键是，建立稳定性模型，利用计算机编程，研究碎纸片的拼接复原，这些方法所得出的结果与实际情况较符合，因此我们可以对这些模型的应用作出一定的推广。但是由于数据量比较大，人工干预又占有一定的比重，所以在现实生活中还有一定的局限性。 关键词：拼接还原 灰度处理 筛选 匹配算法 人工干预 最小二乘法 一、问题重述 1.1问题背景 破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。 1.2问题提出 请讨论以下问题： 1. 对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达（见【结果表达 格式 pdf格式笔记格式下载页码格式下载公文格式下载简报格式下载 说明】）。 2. 对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果表达要求同上。 3. 上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果，结果表达要求同上。 二、模型假设 1、碎纸机切割图片是垂直的。 2、碎纸机切割的碎纸片大小相同、质地均匀。 3、所有的碎纸片由同一碎纸机切割。 4、每个附件中所有的碎纸片来自于同一页文字文件。 三、问题分析 3.1问题一的分析 问题一的关键在于建立碎纸片拼接复原模型以及算法。首先，对于附件1,2中的图片进行灰度处理，破碎图片仅为纵切，故将图片的边界进行差值和处理，匹配度最高的差值和为0，进而可以对所有数据进行筛选，最终得到复原图。 3.2问题二的分析 与问题一相比较，问题二中对碎纸片采取既纵切又横切的切割方式，而且相对于附件1,2，附件3,4的数据量比较大，但总体原理和问题一基本一致，只需在考虑纵切后再进行横切即可。 3.3问题三的分析 与问题一、二相比较，问题三中给出的附件5中图片来源于双面打印文件的碎片数据，并且数据量与上述相比更海量。所以本题首先考虑的是将大量数据导入到计算机中，然后将边界部分筛选出来，剩下的图片按照匹配算法进行进一步拼接，最后对异常数据进行人工干预即可。 四、建模过程 4.1问题一 4.1.1.1附件1建模过程 对附件1中的图片进行灰度处理，再进行差值、求和等运算，从而取出最匹配两张图片，以此循环、比较下去，从而得到匹配的排列顺序。具体Matlab程序见附件一。 4.1.1.2求解过程 c矩阵中第7行元素全部为0，为异常数据，所以首先进行c(7,:)=[]对数据进行筛选，接下来在Matlab中运行出的min(c)是1×18的矩阵，将得到的矩阵中的数字在原始的矩阵c（即还未提取第7行元素）中找到对应数字，进而找到该数字在矩阵中的序列，如第一个数字是第一列中第18个数，即18-1。第二个数字是第二列中第17个数，即17-2。依次类推，得到所有序列，即 18-1,17-2,11-3,16-4,2-4,5-6,1-7,12-8,13-9,6-10, 4-11,19-12,15-13,10-14,9-15,13-16,3-17,8-18,14-19. 由于图片序号从000开始，故进行人工干预，对所得到的数据对应各自减1，得到 17-0，16-1，10-2,15-3,1-3,4-5,0-6,11-7,12-8,5-9,3-10,18-11，  14-12,9-13,8-14,12-15,2-16,7-17,13-18， 对这19组数据进行排序即： 15-3-10-2-16-1-4-5-9-13-18-11-7-17-0-6； 然后对排序后剩余的两段数据12-8，14-12-15进行人工干预，最后可得到的正确顺序为： 08 14 12 15 03 10 02 16 01 04 05 09 13 18 11 07 17 00 06                                       复原图片见附录一； 4.1.2.1附件2建模过程 对于附件2，主要程序和附件一是相同的，需把程序中图片导入的路径中‘附件1’改为‘附件2’，在程序运行中，矩阵c中第5行元素全部为0，为异常数据，故将附件1中的‘c(7,:)=[]’语句需要修改为‘c(5,:)=[]’。具体程序见附件二。 4.1.2.2建模求解 c矩阵中第5行元素全部为0，为异常数据，所以首先进行c(5,:)=[]对数据进行筛选，接下来在Matlab中运行出的min(c)是1×18的矩阵，将得到的矩阵中的数字在原始的矩阵c（即还未提取第7行元素）中找到对应数字，进而找到该数在矩阵中的序列，如第一个数字是第一列中第12个数，即12-1。第二个数字是第二列中第6个数，即6-2。依次类推，得到所有序列，即 12-1,6-2,7-3,12-4,17-4,1-6,4-7,3-8,11-9,2-10,14-11,19-12,9-13, 10-14,13-15,12-16,18-17,15-18,16-19. 由于图片序号从000开始，故进行人工干预，对所得到的数据对应各自减1，得到 11-0，5-1，6-2,11-3,16-4,0-5,3-6,2-7,10-8,1-9,13-10,18-11，8-12,9-13,12-14,11-15,17-16,14-17,15-18， 对这19组数据进行排序即： 15-18-11-0-5-1-9-13-10-8-12-14-17-16-4； 然后对排序后剩余的两段数据 11-3-6-2-7，11-15进行人工干预，最后可得到的正确顺序为： 03 06 02 07 15 18 11 00 05 01 09 13 10 08 12 14 17 16 04                                       复原图片见附录二。 4.2问题二 4.2.1建立模型 为提高分析的准确性，假设碎纸片文字与文字之间有间隔，汉字宽度与高度比值1/3～3。这就意味着每个文字图像和与其他文字图像之间有空白点，文字图像宽度与高度比值1/3～3 之间。 碎片内文字图像经上述预处理后，首先碎片像素高度为H，每行的像素宽度保存在数组pntCnt(k),(k=1,2,3,…,H)内，每行的空白点数保存在数组blankCnt(k),( k=1,2,3,…,H)内,总的文字图像个数变量设为CharSum,文字行高度和变量为CharHeight,令他们的初值为0，即CharSum→0，CharHeight→0，则 文字图像个数和文字行高和可按下述算法计算： (1) k→0，表示从碎片最低点开始从上往下扫描。 (2) k←k+1，判断k＞H否，如果大于，结束，否则转（3）。 (3) 判断pntCnt（k）＜72否，也即判断该行碎片宽度是否小于72个像素宽度，如果小于，转（2），否则转（4）。 (4) 判断pntCnt（k）-blankCnt（k）＜5否，也即判断该行白点个数与该行像素点宽度的差是否在5范围内，小于5，表示该行是空白行，转（5），否则表示不是空白行，转（2）。 (5) 记下改行的序号 ，寻找下一个空白行号 ，判断 是否存在，如果存在，转（6），否则表示扫描到最高点，扫描过程结束。 （6）计算行 内的文字图像个数m，注意文字图像的宽度与高度（ ）的比值应是1/3～3之间，不在此比值范围的图像不应统计。 （7）判断m＞0否，大于则Charsum→Charsum+m，CharHeight→CharHeight+ ，转（8），如果m等于0，不累加文字总个数和文字行高度，也转（8），显然 行位置就是文字行的位置。 （8）K→ ，寻找下一个序号为 的空白行， 应该小于H，同时第 +1行不是空白点行，如果存在 ，则k→ -1，转（2），否则结束。 计算出文字图像个数总数Charsum和文字行高度CharHeight后，考虑到碎片内文字行高度和小于碎片像素高度，而碎片像素高度一般远小于10000，可以将这两个数按公式Charsum×10000+CharHeight合并成一个数，然后对合并数进行排序，这样能更有效地选取字数最多，行高和最小的目标方向。而对于本题的附件3，附件4中所有的图片都是宽度为72像素，高度为180像素的图片，所以做起来相对容易一些。 4.2.2建模求解 附件3的正确顺序为： 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                                       复原图片见附录三。 附件4的正确顺序为： 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                                       复原图片见附录四。 4.3问题三 模型建立以及建模的求解 由于该碎片数据是英文印刷文字双面打印文件的碎片数据，数据量多且所有数据不再同一面上，故首先对碎纸片进行灰度处理以便将图片转化为矩阵并得到复原图的边界，然后可以根据问题二的匹配算法进行建模，但是该图片最后拼接为正反面，程序所得到的序列不一定和实际相符，故人工干预进行最后的整理。 附件5的最后顺序为 136a 47b 20b 164a 81a 189a 29b 18a 108b 66b 110b 174a 183a 150b 155b 140b 125b 111a 78a 5b 152b 147b 60a 59b 14b 79b 144b 120a 22b 124a 192b 25a 44b 178b 76a 36b 10a 89b 143a 200a 86a 187a 131a 56a 138b 45b 137a 61a 94a 98b 121b 38b 30b 42a 84a 153b 186a 83b 39a 97b 175b 72a 93b 132a 87b 198a 181a 34b 156b 206a 173a 194a 169a 161b 11a 199a 90b 203a 162a 2b 139a 70a 41b 170a 151a 1a 166a 115a 65a 191b 37a 180b 149a 107b 88a 13b 24b 57b 142b 208b 64a 102a 17a 12b 28a 154a 197b 158b 58b 207b 116a 179a 184a 114b 35b 159b 73a 193a 163b 130b 21a 202b 53a 177a 16a 19a 92a 190a 50b 201b 31b 171a 146b 172b 122b 182a 40b 127b 188b 68a 8a 117a 167b 75a 63a 67b 46b 168b 157b 128b 195b 165a 105b 204a 141b 135a 27b 80a 0a 185b 176b 126a 74a 32b 69b 4b 77b 148a 85a 7a 3a 9a 145b 82a 205b 15a 101b 118a 129a 62b 52b 71a 33a 119b 160a 95b 51a 48b 133b 23a 54a 196a 112b 103b 55a 100a 106a 91b 49a 26a 113b 134b 104b 6b 123b 109b 96a 43b 99b                                       复原图片见附录五。 五、模型的评价与改进 1、模型评价 优点： （1）在求解第一问时，首先进行灰度处理。然后对碎纸片边界进行差值和处理，对所处理后的数据进行了筛选，最后对所筛选出的数据进行人工干预。充分保证了拼接的准确性。 （2）在求解问题二时，首先对碎纸片进行预处理，其次进行碎纸片匹配，最后进行碎纸片的拼接复原，本模型采用匹配算法具有良好的时效性、较强的系统性和关联性等特征，可以合理的对数据做出匹配。 （3）在求解问题三时，首先对碎纸片进行灰度处理,其次进行碎纸片的相互匹配，接着进行拼接复原，最后对异常数据进行整理。 （4）模型最大优点在于对原始数据灰度处理后, 采用匹配算法进行, 使之愈来愈完善, 具有很高的匹配精度和适度性在此基础上, 对模型作进一步讨论便可得到一系列可靠而实用的信息并且, 所得结论与客观事实很好地吻合, 从而进一步说明模型是合理的。 缺点： （1）进行灰度处理时，数据量大，对于导入数据需要一定的技巧。 （2）在求解某些模型时，为了使问题得到方便的解决，往往采用简化的手 段进行求解，因此求出的结果与真实值会存在一定的偏差。 （3）但是由于数据量比较大，人工干预又占有一定的比重，所以在现实生活中还有一定的局限性。 （4）自动化程度不够高，属于半自动拼接技术。 2、模型改进 在进行问题二，三时，由于时间有限，数据量大，内容繁琐，部分内容编不出程序来 ，希望通过我们的努力能建立出具有自动拼接能力的模型，主要突破口就是编程。进而把现在所建立的模型转化为全自动拼接模型，实现‘破镜重圆’的美好愿望。 6、参考文献 [1] 姜启源. 数学模型（第三版）[M]. 北京：高等教育出版社，1999. [2] 韩中庚. 数学建模方法及其应用（第二版）[M]. 北京：高等教育出版社，2009. [3]罗智中.基于文字特征的文档碎纸片半自动拼接 [4] 罗智中.基于线段扫描的碎纸片边界检测算法研究[J].仪器仪表学报，2011，32（2）：289-294. [5]付忠良;基于图像差距度量的阈值选取方法[J];计算机研究与发展;2001,05 附录 附录一 附件一复原图如下： 附录二 附件二复原图如下： 附录三 附件三复原图如下： 附录四 附件四复原图如下： 附录五 附件五复原图如下：