1、1碎纸片的拼接复合摘要本文研究不同方下式切割文件的碎纸片拼接的复原问题，其主要思想就是通过编写相关程序将纸片信息数据化，然后利用 Matlab 软件进行数据分析得到匹配度，最后仍然通过编写相关程序将纸片进行自动拼接。对于问题一中纵切文件， ，首先我们先将附件 1 所给的图片（以 000.bmp 为例）转化成二值图像；然后用 imread 读取 000.bmp 的第一列和最后一列的数值(都是 0 或者1，1 表示两幅碎纸片边界相匹配，否则为 0.)作为左右边界的颜色值；再把 000.bmp与其它任一图像的左(右)边界的进行匹配，最后把匹配度最高两幅图像分别放在000.bmp 左右两侧,作为合成图
2、像,合成图像的结果是否理想需要人工进行判断。匹配度计算方法说明: 假设 000.bmp 的右边界(1980*1 个元素)与 004.bmp 的左边界有 500 个相等,则 ppd(4)=500/1980。问题二中既纵切又横切文件，其纸片个数增加，我们需要处理(000.bmp-208.bmp)209 纸片上下左右四个边界的匹配度。建立 name 元胞矩阵存储文件，转化所有图形成二值图及提取上下左右四个边界的二值颜色部分，找出每幅图片左右最佳匹配的图及确定最佳匹配度。在此过程中，左右匹配可能会有出错的部分，出错表现在：第 i 幅图(右边)对应的最佳图 (的左边)还能匹配的图(右边)的个数 a 不为
3、 0.，这样由自动拼接所得的图片可能不准确。为此我们将个数 a 进行由小到大的排序，这样可,我们将观查到前 j 个值为 0,这说明这些值所对应的图(的右边)进行匹配时,出现错误的概率很低,可以进行自动拼接。拼接所得的行图片可能是完整的，也有可能是左右两端残缺的。从第 j+1 个图片起其 a 值不为 0，这时增加人工干预将剩余图片进行拼接。采取同样的方法找出每幅图片上下最佳匹配的图及确定最佳匹配度，实施相同的步骤实现上下的图片拼接。问题三中正反两面文件的拼接程序与问题二中相类似我们的所有算法都是基于像素点边缘匹配，优点是算法简单，对匹配图片进行了匹配概率统计，对可行性高的图片先计算机自动实现匹配
4、，残缺部分实现人工干预。缺点是对四个边缘都是白边的图片匹配错误率较高。关键字： 匹配度 Matlab 软件 拼接复原2一 问题重述1.1 问题背景人们在日常生活中有时会遇到需要拼接碎片的情况，如破碎的纸币或是拼图游戏等。事实上，拼接碎片的应用非常广泛，特别是在司法物证复原、历史文献修复以及军事情报的获取等领域都有着重要的应用。一般的拼接复原工作需由人工完成，但如果碎片的数量巨大的时候，人工拼接就有很大的难度，而且很有可能会造成物证或者文物的损坏，前东德情报机构“斯塔西”官员将大量绝密文件撕成 6 亿多块碎纸片后丢进16000 多个垃圾袋，德国政府委托一组档案专家共十五名工作人员，在八年的时间里
5、总共只拼凑了约 250 袋、共计 50 万张碎片。专家估计，按造这种速度，想要拼完全部碎片，将耗费 400 年时间。因此，如何快速而准确的将大量碎纸片拼凑完整，对于很多领域都是都是一个值得深入研究的问题。1.2 问题重述破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。请讨论以下问题：1. 对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切） ，建立碎纸片拼接复原模型和算
6、法，并针对附件 1、附件 2 给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达（见【结果表达格式说明】 ） 。2. 对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件 3、附件 4 给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果表达要求同上。3. 上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件 5 给出的是一页英文印刷文字双面打印文件的碎片数据。请尝试设计相应
7、的碎纸片拼接复原模型与算法，并就附件 5 的碎片数据给出拼接复原结果，结果表达要求同上。3二 问题分析2.1 问题一对于碎纸机仅纵切的情形，我们只需要寻找碎纸片左右两边的边界的最佳匹配度。题中要求我们分别将中文和英文的碎纸片进行拼接，对于中文和英文其纸片边界拼接方法相同。因此，我们首先进行碎纸片图像左右两边界的信息采集，然后编写具体的程序（及相应的算法）利用 Matlab 软件分别对中文和英文的不同碎纸片边界信息寻找最佳匹配度，最后根据边界匹配度的高度进行确定最佳的拼接复原方案，并且将拼接复原后的纸片根据其文字的可读性以及其正确定进行检验。最终给出拼接复原图片2.2 问题二对于碎纸机既纵切又横
8、切的情形，我们不但要考虑碎纸片左右两边的边界，还要考虑碎纸片上下两边界。我们采用类似于问题一的基本思想，对附录 3 和附录 4 给的中文、英文碎纸片的上下、左右匹配度进行分析。先寻找图片左右边界的最佳匹配度，再寻找图片上下边界的最佳匹配度，最终实现图片的拼接复原。2.3 问题三既纵切又横切有双面文字的文件，在进行图片的上下左右边界最佳匹配度的寻找时，要分别考虑正反两面，三、模型假设1、假设编辑的程序的准确度比较高，2、假设计算机自动实现匹配可行性高3、假设进行人工干预时的难度系数低四、符号说明相匹配的碎纸片个数n匹配碎纸片的总数m碎片边界的匹配度表示 name 元胞矩阵存储中的文件 ia表示相
9、匹配的图片序号ib4五、模型的建立5.1 模型一5.1.1 纵切中文文件碎片拼接复原对于切碎的纸片，要将它们拼接复原，其关键是要寻找纸片边界的最佳匹配度，具体操作如下（以 000.bmp 为例）：先把 000.bmp018.bmp 转化成二值图像,然后用 imread 读取 000.bmp 的第一列和最后一列的数值(都是 0 或者 1)作为左右边界的颜色值我们先将附件 1 所给的图片（以000.bmp 为例）转化成二值图像；然后用 imread 读取 000.bmp 的第一列和最后一列的数值(都是 0 或者 1，1 表示两幅碎纸片边界相匹配，否则为 0.)作为左右边界的颜色值；再把 000.b
10、mp 与其它任一图像的左(右)边界的进行匹配，最后把匹配度最高两幅图像分别放在 000.bmp 左右两侧,作为合成图像,合成图像的结果是否理想需要人工进行判断。匹配度计算方法说明: 假设 000.bmp 的右边界 (1980*1 个元素)与 004.bmp 的左边界有 500 个相等,则 ppd(4)=500/1980。 。大概流程图如下所示：图 片不匹配相匹配 n匹配总数 m匹配度 n（1）（0）图（1）通过软件的运行结果我们得到了每幅图的左、右两端的边界最佳匹配度的图像见表（1） 、 （2）右侧最佳匹配度表（1）序号 000 001 002 003 004 005 006 007 008
11、009匹配度 0.95 0.941 0.974 0.934 0.958 0.942 1 0.925 0.943 0.94相匹配的序号 006 004 016 010 005 009 008 017 014 013序号 010 011 012 013 014 015 016 017 0185匹配度 0.96 0.959 0.982 0.961 0.961 0.948 0.938 0.947 0.948相匹配的序号 002 007 015 018 012 003 001 000 011左侧最佳匹配度表（2）序号 000 001 002 003 004 005 006 007 008 009匹配度
12、0.947 0.938 0.96 0.948 0.941 0.958 0.95 0.959 1 0.942相匹配的序号 017 016 010 015 001 004 000 011 006 005序号 010 011 012 013 014 015 016 017 018匹配度 0.934 0.948 0.961 0.94 0.943 0.982 0.974 0.925 0.961相匹配的序号 003 018 014 009 008 012 002 007 013通过以上两个表格我们得到拼接复原序号表为：复原后序号排列表（3）复原后序号 008 014 012 015 003 010 002
13、 016 001 004复原后序号 005 009 013 018 011 007 017 000 006根据复原后的序号排列，又编辑了另外一个程序，将 000.bmp018.bmp 共 19 幅图片拼接在一起。比如说要把第 1 5 7 幅按从左到右的顺序合并起来，就可以运用以下程序进行拼接：a=imread(000.bmp);b=imread(004.bmp);c=imread(006.bmp);d=abc;imshow(d)同理要把 19 幅都拼接起来，就需运用相同的程序，其运行结果为：65.1.2 切英文文件碎片拼接复原此英文碎纸片拼接复原的方法和中文碎纸片的方法是一样的，也是编辑同样的
14、程序，利用 matlab 软件运行进而得出结果，如下：左端最佳匹配度表（4）序号 000 001 002 003 004 005 006 007 008 009匹配度 0.931 0.922 0.95 1 0.941 0.951 0.972 0.952 0.923 0.944相匹配的序号 011 005 006 004 016 000 003 002 010 001序号 010 011 012 013 014 015 016 017 018匹配度 0.95 0.95 0.96 0.97 0.93 0.92 0.94 0.94 0.9872 4 1 2 2 5 3 7 2相匹配的序号 013 0
15、18 008 009 012 007 017 014 015右端最佳匹配度表（5）序号 000 001 002 003 004 005 006 007 008 009匹配度 0.951 0.944 0.952 0.972 1 0.922 0.95 0.925 0.961 0.972相匹配的序号 005 009 007 006 003 001 002 015 012 013序号 010 011 012 013 014 015 016 017 018匹配度 0.923 0.948 0.932 0.952 0.932 0.982 0.941 0.943 0.954相匹配的序号 008 000 014
16、 010 017 018 004 016 011复原后序号排列表（6）复原后序号 003 006 002 007 015 018 011 000 005 001复原后序号 009 013 010 008 012 014 017 016 004得到复原的序号排列后，我们运用处理中文碎纸片的程序来拼接复原图形，如下：85.2 模型二5.2.1 即纵又横切中文碎纸片拼接复原对于碎纸机既纵切又横切的情形，我们要寻找图片上下左右四个方向的最佳匹配度：我们需要处理(000.bmp-208.bmp)209 纸片上下左右四个边界的匹配度。建立name 元胞矩阵存储文件，转化所有图形成二值图及提取上下左右四个边
17、界的二值颜色部分，找出每幅图片左右最佳匹配的图及确定最佳匹配度。我们此模型的实现分为三个步骤:步骤一:进行行拼接表 tt4 表示根据匹配度可以左右最佳匹配度的图片序号表 tt4图片序号匹配序号图片序号匹配序号图片序号匹配序号图片序号匹配序号图片序号匹配序号图片序号匹配序号图片序号匹配序号图片序号匹配序号1 138 28 61 55 66 82 190 109 118 136 13 163 97 190 12392 4 29 92 56 45 83 200 110 198 137 165 164 73 191 963 58 30 65 57 94 84 169 111 188 138 54 16
18、5 128 192 514 160 31 42 58 193 85 184 112 202 139 159 166 28 193 1795 102 32 52 59 184 86 153 113 150 140 146 167 33 194 896 93 33 197 60 169 87 196 114 195 141 186 168 26 195 1207 78 34 203 61 169 88 169 115 41 142 169 169 101 196 248 209 35 85 62 20 89 169 116 169 143 31 170 135 197 2699 106 36 82
19、 63 143 90 147 117 164 144 187 171 206 198 1710 106 37 169 64 117 91 48 118 147 145 78 172 60 199 1611 105 38 76 65 112 92 189 119 191 146 169 173 172 200 16912 23 39 149 66 169 93 181 120 124 147 169 174 158 201 1813 74 40 32 67 107 94 184 121 87 148 192 175 71 202 614 169 41 152 68 70 95 35 122 43
20、 149 169 176 46 203 19915 129 42 24 69 176 96 169 123 104 150 98 177 169 204 17016 134 43 125 70 100 97 132 124 169 151 22 178 21 205 14017 185 44 169 71 167 98 137 125 184 152 169 179 139 206 8618 169 45 207 72 157 99 173 126 14 153 166 180 51 207 1119 169 46 1 73 7 100 163 127 69 154 71 181 49 208
21、 15620 79 47 96 74 161 101 77 128 184 155 115 182 205 209 16921 176 48 185 75 169 102 114 129 4 156 141 183 11022 176 49 38 76 169 103 155 130 29 157 169 184 9123 169 50 55 77 169 104 122 131 194 158 182 185 11124 148 51 180 78 113 105 99 132 80 159 127 186 10925 36 52 108 79 169 106 169 133 201 160
22、 83 187 326 9 53 168 80 169 107 151 134 171 161 147 188 4127 2 54 57 81 34 108 116 135 40 162 25 189 142根据表 tt4 我们发现：第 i 幅图(右边)对应的最佳图 (的左边)还能匹配的图(右边)的个数 a 不为 0.，这样由自动拼接所得的图片可能不准确。为此我们将个数 a 进行由小到大的排序，这样可,我们将观查到前 j 个值为 0,这说明这些值所对应的图(的右边)进行匹配时,出现错误的概率很低,可以进行自动拼接。拼接所得的行图片可能是完整的，也有可能是左右两端残缺的。表 X 表示表 tt4
23、中与之相匹配图片出现的次数为 1表 X图片序号出现次数图片序号出现次数图片序号出现次数图片序号出现次数图片序号出现次数图片序号出现次数图片序号出现次数图片序号出现次数图片序号出现次数1 0 18 0 35 0 52 0 69 0 86 0 103 0 120 0 137 02 0 19 0 36 0 53 0 70 0 87 0 104 0 121 0 138 03 1 20 0 37 0 54 0 71 0 88 0 105 0 122 0 139 04 0 21 0 38 0 55 0 72 0 89 0 106 0 123 0 140 05 0 22 0 39 0 56 0 73 0 9
24、0 0 107 0 124 0 141 06 0 23 0 40 0 57 0 74 0 91 0 108 0 125 0 142 07 0 24 0 41 0 58 0 75 0 92 0 109 0 126 0 143 08 0 25 0 42 0 59 0 76 0 93 0 110 0 127 0 144 0109 0 26 0 43 0 60 0 77 0 94 0 111 0 128 0 145 010 0 27 0 44 0 61 0 78 0 95 0 112 0 129 0 146 011 0 28 0 45 0 62 0 79 0 96 0 113 0 130 0 147
25、012 0 29 0 46 0 63 0 80 0 97 0 114 0 131 0 148 013 0 30 0 47 0 64 0 81 0 98 0 115 0 132 0 149 014 0 31 0 48 0 65 0 82 0 99 0 116 0 133 0 150 015 0 32 0 49 0 66 0 83 0 100 0 117 0 134 0 151 016 0 33 0 50 0 67 0 84 0 101 0 118 0 135 0 152 017 0 34 0 51 0 68 0 85 0 102 0 119 0 136 0表 Y 表示表 tt4 中与之相匹配图片
26、出现的次数为不唯一表 Y图片序号出现次数图片序号出现次数图片序号出现次数图片序号出现次数图片序号出现次数图片序号出现次数153 1 163 1 173 2 183 30 193 30 203 30154 1 164 1 174 2 184 30 194 30 204 30155 1 165 1 175 2 185 30 195 30 205 30156 1 166 1 176 4 186 30 196 30 206 30157 1 167 1 177 4 187 30 197 30 207 30158 1 168 1 178 4 188 30 198 30 208 30159 1 169 1
27、179 4 189 30 199 30 209 30160 1 170 1 180 4 190 30 200 30161 1 171 1 181 30 191 30 201 30通过表 X 和表 Y 我们可以发现有 152 张图片出现的次数唯一，有 57 张图片的出现的次数不唯一，这样就会导致匹配时出现误差或错误因此我们先将出现次数为 0 的 152张图片进行拼接。具体实现思路：现将这 152 张的图片序号存入数组 a 中：name 元胞矩阵=1，3，4，207，208，选取 name 元胞矩阵中的第一个元素 ，1a在表 tt4 中寻找与之相匹配的图片 ，查表 tt4 看图片 是否在 name 元胞矩阵中，若ibib在其中，则继续在表 tt4 中与之相匹配的图片，并在 name 元胞矩阵中将其划去；若不在 name 元胞矩阵中则停止寻找，得到行拼接图序列，如此循环下去。我们建立如下流程图：
