1、 规则碎纸片的拼接复原模型 摘要 图像碎片复原技术是一项综合的并具有实用价值的研究课题 ,它的最终目的是要从大量的任意图像碎片中找出真正符合实际的匹配对 ,并根据这些匹配关系将相邻的图像碎片拼合起来重现图像的原貌。 图像碎片的复原工作是以实际碎片为参考依据进行的 ,建立能够准确描述实物的计算机模型是图像碎片复原工作的关键步骤之一 ,对碎片复原的后续工作有基础性的作用 ,模型建立的准确性和复杂性将影响到后续工作能否顺利进行下去。 本文利用边缘特征点匹配，相关系数，广度搜索法等方法建立了规则碎纸片的拼接复原模型。 对于问 题一，我们利用边缘特征点匹配的方法，先提取边缘特征点的灰度矩阵，再寻找矩阵相
2、似度最大的碎片实现匹配。 对于问题二，我们采用了基于文字特征的半自动拼接方法，通过找到相交点距离相等的最大个数来确定匹配图像。 对于问题三，我们提取了各边的像素作为灰度矩阵，用 X， Y， H， L 确定目标函数 min d（ ,ijXY） = ijXY ， min d（ ,ijHL） = ijHL ， 运用广度搜索算法找出最佳匹配项。 最后，本文还对模型推广进行了进一步讨论，分析了模型的优缺点，提出了改进模型的方法和思路。 关键词：图像拼接；规则碎片；图像复原；灰度矩阵；广度搜索算法；特征匹配；自动拼接；图像分割；匹配准则 一问题的重述 破碎文件的拼接在司法物证复原、历史文献修复 及军事情报
3、 获取等领域都有重要的应用。传统 拼接 复原工作由人工完成，准确率较高，但效率很低。随着计算机技术的发展，人们试图开发碎纸 片 的自动拼接技术，以提高拼接 复原 效率。碎纸自动拼接技术是图像处理与模式识 别领域中的一个较新但是很典型的应用，它是通过扫描和图像提取技术获取一组碎纸片的形状、颜色等信息，然后利用计算机进行相应的处理从而实现对这些碎纸片的全自动或半自动拼接还原。请讨论以下问题： 1. 对于给定同一页 印刷文字文件 的 碎纸机破碎纸 片（仅纵切），建立碎纸 片拼接 复原模型和 算法，并针对附件 1、附件 2 给出的 中、英文各一页文件的碎片数据进行 拼接 复原 。每页纸被切为 19 条
4、碎片。如果复原过程要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达，将碎片序号按复原后顺序填入 1 19 的 表格。 2. 对 于碎纸机 既 纵切 又 横切 的情况 ， 请设计碎纸片拼接复原 模型和算法，并针对附件 3、附件 4 给出的 中、英文各一页文件的碎片 数据进行 拼接 复原。 每页纸被切为 11 19 个碎片。 如果复原过程要人工干预，表达要求同上，将碎片序号按复原后顺序填入 11 19 的 表格。 3. 上述所给碎片数据均为单面打印文件，还可能有双面打印文件的碎纸片拼接复原问题要解决。附件 5 给出一页英文印刷文字双面打印文件的碎片数据。 每页纸被切为
5、11 19 个碎片，每个碎片有正反两面。 每一碎片对应两个文件，共有 2 11 19 个文件 。请尝试设计相应的碎纸片拼接复原 模型 与算法 ，并就附件5 的碎片数据给出拼接复原结果，表达要求同上，将碎片序号按复原后顺序填入两个 11 19 的 表格。（以上若不能确定复原位置的碎片，可不填入上述表格，单独列表。） 二 模型的假设 1. 假设纸片上的文字都是完整的。 2. 假设扫描过程中图像不失真，保持清晰度。 3. 假设纸面上除了文字外无其他杂点黑点。 4. 假设切割过程中纸片没有损坏。 5. 假设切割后的纸片不是歪斜的。 6. 假设原图的左边（起始碎片的左边）与原图的右边（终始碎片的右边）边
6、界线为白色。 7. 假设原始图像本身的内容是连续的具有意义的。 8. 假设所有的碎片中都存在相互匹配的 碎片。 9. 假设所有碎片都在一次扫描下完成。 三 符号说明 iA ：第 i 个碎片 ijX ：纵向切割时，碎片的灰度矩 X :横纵切割时，碎片左边的灰度矩 Y : 横纵切割时，碎片右边的灰度矩 H : 横纵切割时，碎片上边的灰度矩 L ：横纵切割时，碎片下边的灰度矩 11 22i j i jXX：灰度矩11ijX与22ijX的相关系数 四模型的建立与求解 5.1.1 问题一的分析 如果是一个整体分裂成的两个碎片 ,那么两个碎片裂口对应的部分的颜色 (对灰度图像而言 ,就是灰度信息 )会有很
7、强的相关性 ,这是碎片间除了轮廓外信息外最重要的信息之一。由于碎片的轮廓是完全一致的，我们只考虑碎片裂口对应的部分颜色对图像匹配的影响。完 成图像碎片匹配过程后 ,相互匹配的图像碎片就被找到了 ,同时也得到了图像碎片的匹配段 ,并在碎片间建立了对应的匹配信息表 ,并记录了构成匹配对的匹配线段的相关信息如匹配起始点终止点等。接下来的工作就是将相互匹配的图像碎片拼接起来 ,恢复图像的原 貌。 5.1.2 问题一的模型建立 设碎片 iA 的 每条边的灰度矩为 L ， 1 2 3, , , .ij lX x x x x ， i=1,2, 19,j=1 或 2，lx =0 或 1。 i 代表第 i 个碎
8、片， j=1 表示碎片左边， j=2 表示碎片右边， lx =0 代表黑色， lx =1 代表白色。由于每个碎片的左边只能与另一个碎片的右边相匹配，此时两向量之间的相关系数可表示为 1 1 2 21 1 2 21 1 2 2( , )( ) ( )i j i ji j i jXXi j i jCo v X XD X D X 1 1 2 2 1 1 1 1 2 2 2 2( , ) ( ) ( )i j i j i j i j i j i jCo v X X E X E X X E X 采用相关系数这一测度可以测量两个描绘子之间的相似性 ,如果已知用于比较多个描绘子 ijX ， 就可以计算出各个
9、描绘子之间的相互关系 ,并找出最大相关系数max 11 2 2i j i jXX。 灰度矩相似性最高的两条边 ,就可以作为真正的匹配边 ,同时可以排除掉其他干扰匹配对。 5.1.3 问题一的模型求解 首先通过碎纸片左右边界线是否为单一色（白色）找出起始碎片和终止碎片，将拥有与起始碎片右边相似度最高的边的碎片作为起始匹配图像，运用迭代法将剩余碎片匹配拼接。利用 matlab 软件求得 i从 1到 19时max 11 2 2i j i jXX相对应的 ijX匹配图像，将复原后匹配碎片的顺序列入下表： 碎片 顺序 8 14 12 15 3 10 2 16 1 4 5 9 13 18 11 7 17
10、0 6 表一：附件 1的复原结果 碎片 顺序 3 6 2 7 15 18 11 0 5 1 9 13 10 8 12 14 17 16 4 表二：附件 2的复原结果 5.1.4 问题一的模型结果的分析与检验 经过灰度矩的相关系数匹配，模型一最终精确的拼接复原了碎纸片。在拼接过程中并没有进行人工干预， 使得计算工作更为简便。但是对于较为复杂的图像，纯粹地依靠计算机寻找匹配图像时，一般只能找到匹配图像的一个区域，并不能唯一确定具体的结果，从而增大误差。 5.2.1 问题二的分析 问题二中不仅有纵向切割还有横向切割，碎片切割的复杂化，使得按照问题一的模型，不能让计算机自动地完成拼接过程。 在此文中，
11、对这类边缘相同的碎纸片的拼接，理想的计算机拼接过程应与人工拼接过程类似，拼接时不需要考虑待拼接碎纸片边缘形状是否匹配，但要判断碎片内的字迹断线或碎片内的文字内容是否匹配，然而由于理论和技术的限制，让计算机具备类似人那 种识别碎片边缘的字迹断线、以及理解碎片内文字图像含义的智能几乎不太可能。但是利用现有的技术，完全可以获取碎片文字所在行的几何特征信息，比如文字行的行高、文字行的间距等信息，拼接碎片时如利用这些信息进行拼接，其拼接效率应该比较好。 由于此文字文档的文字行方向为单一水平方向，如果碎片内的文字行在碎片边缘断裂，那么与它相邻的碎纸片在边缘处一定有相同高度、相同间距的文字行，凭此特征可以很
12、容易地从形状相似的多碎片中挑选出相邻碎片。因文字行的高度特征、间距特征的识别比字迹断线识别和文字图像的理解实现起来要容易得多，利用 碎片内文字行特征拼接形状相似的碎纸片理论上是可行的。 另一方面由于计算机数字分析图像能力的缺陷，让计算机对碎片进行完全意义上的自动化拼接也几乎不太可能，为保证拼接的准确性，需要在拼接过程中加入人工干扰过程。一般而言拼接碎片时先利用计算机搜索与目标碎片匹配的未拼接碎片，并根据匹配程度按顺序显示待选碎片，我们再根据人脑进一步分析结果舍弃或拼接待选碎片。这种半自动拼接方法综合利用了计算机高速计算能力以及人的文字图像识别和理解能力，拼接效率比纯人工高，拼接准确性也好于纯计
13、算机拼接法。 5.2.2 问题二的模型建立 为 提高模型的准确性，假设汉字宽度与高度比值 1/33。这意味着每个文字图像与其他文字图像之间有空白点，文字图像宽度与高度的比值在 1/33 之间，如果碎片内有英文单词，应将英文单词图像拆分成类汉字图像，即将英文单词图像分割成宽度与高度近似的类汉字图像。 每个碎片像素高度 H=180，宽度 w=72。碎片文字行的方向为水平方向，先将两个碎片按文字行方向（水平方向 ） 线位置对齐 , 然后计算文字行方向线与碎片边界的交点与处于同一水平位置的另一个碎片交点的距离 id 。如果碎片没 有对齐，则距离相等的连续点的个数比对齐位置的距离相等连续点的个数要少，即
14、距离相等的连续点的个数越多，图像越匹配。由于各碎片边缘都为垂直线（或水平线），因此距离相等等价于相同高度下（或宽度）点的像素相同。设 X,Y,H,L 分别为碎纸片的左右上下边的 0-1 灰度矩阵，函数 F（ iX ， jY ）表示对应 1llxy的对数，目标函数为 maxF（ iX ， jY ）， maxF（ iH ， jL ）。 5.2.3 问题二的模型求解 （ 1）根据边界灰度矩阵 iX =0， iH =0，从候选碎片中筛选出起始碎片 1A ； （ 2）计算该碎片上（或下）边界与未接碎片下边界（或上边界）可 能拼接位置处的距离相等的连续点的个数； （ 3）将距离相等的连续交点个数按升序排列
15、，按升序依次显示未拼接碎片，人工选择碎片并拼接到计算机屏幕上； （ 4）判断是否完成本列碎片的拼接，如果继续拼接，转（ 2），否则转（ 5）； = （ 5）以第一列为起始碎片，进行 11 次下面步骤循环； （ 6）计算该碎片左（或右）边界与未接碎片右边界（或左边界）可能拼接位置处的距离相等的连续点的个数； （ 7）将距离相等的连续交点个数按升序排列，按升序依次显示未拼接碎片，人工选择碎片并拼接到计算机屏幕上； （ 8）判断是否完成本行碎片的拼接，如 果继续拼接，转（ 6），否则结束此次循环。 将复原后匹配碎片的顺序列入下表：（注：加黑序号为人工筛选序号） 表三：附件 3 的复原结果 191 7
16、5 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 121 22 57 202 71 165 82 159 139 1 129 63 138 153 53 38 123 120 175
17、 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 14 128 3 159 82 199 135 12 73 160 203 169 134 39 31 51 107 115 176 94 34 84
18、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 198 71 156 83 132 200 17 80 33 202 198 15 133 1
19、70 205 85 152 165 27 60 89 146 102 154 114 40 151 207 155 140 185 108 117 4 101 113 194 119 123 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 51 179 120 86 195 26 1 87 18 38 148 46 161
20、24 35 81 189 122 103 130 193 88 167 25 8 9 105 74 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 的复原结果 5.2.4 问题二的模型结果的分析与检验 该模型采用了基于边界交点距离的碎片半
21、自动拼接算法，该算法不依赖于碎片几何特征，实现简单，可靠性比较好。 对于碎片文字是汉字的碎片，该模型能更精确地找出匹配碎片的图像，而对英文碎片，搜索的精度略低，人工筛选工作量稍大。 该半自动拼接算法最终求得的复原图像符合实际情况，且拼接计算工作量在允许范围内，效果显著。 5.3.1 问题三的分析 较之问题一和问题二的碎片数据是单面打印文件，问题三研究的是在横纵切割的基础上加上正反面碎片的双 面打印文件，显得更为复杂。在碎片数量增加一倍的情况下，若单纯地以匹配条件去寻找匹配对象，则工作量会很大。所以我们想到引进一种搜索算法，可以使搜索到的匹配对象范围更为精准，从而缩小工作量，尤其是人工筛选的工作
22、量。经过研究，决定采用广度搜索算法，在此基础上，又考虑到之前提取碎片边缘像素点，将之化为 0-1 灰度矩，有失图像的真实性，便决定提取碎片原有的像素作出灰度矩，而再用广度搜索算法搜索满足匹配条件的碎片对象，从而更为精准迅速地得出结果。 5.3.2 问题三的模型建立 设 X,Y,H,L 为边界的实际灰度矩， d（ ,ijXY） = ijXY ， d（ ,ijHL） = ijHL ，目标函数为 min d（ ,ijXY）， min d（ ,ijHL）。 5.3.3 问题三的模型求解 对于一个给定的 iX ，利用广度搜索算法求出 min f（ ,ijXY）时的 jY ，从而确定碎片 iA 的最优匹配
23、碎片 jA ，再经由人工最终确定 iA 的匹配图像。将所求碎片复原序号填入下表： 136a 047b 020b 005b 152b 147b 143a 200a 086a 083b 039a 097b 090b 293a 162a 013b 024b 057b 035b 159b 073a 172b 122b 182a 105b 204a 141b 009a 145b 082a 054a 196a 112b 表五：附件 5 碎片正面复原结果 表六：附件 5 碎片反面复原结果 5.3.4 问题三的模型结果的分析与检验 由于本模型中采用的灰度矩是对各边像素的真实提取，并且运用了广度搜索算法搜索最优
24、匹配项，使得该模型的效率得到了提高，能在可接受的时间范围内求得匹配结果。 尽管已在问题二的基础上对模型进行了改进，仍不能脱离人工干预实现计算机的全自动化，在碎片数量多的情况下会有较大的工作量。 五模型的改进与推广 本文对算法的计算工作量进行了分析，分析表明，对大多数碎片的实际碎纸片，拼接计算工作量在允许范围内，如果对算法作些改进 ，拼接计算量可大幅度减小。 本文虽然对二维图像碎片复原方法的关键技术进行了研究 ,但依然还有很多地方需要进一步深入探讨。本文主要针对规则碎片的特征提出了基于边缘特征点的复原算法 ,对特征点的利用可以推广到任意不规则碎片类型 ,但还需进一步研究。另外 ,由于本文只是针对
25、灰度图像进行了实际研究并取得了较好效果 , 理论上讲 ,彩色图像和灰度图像适用于同样的方法 ,但彩色图像包含了更丰富的内容信息 ,无论是算法研究还是在实证研究方面都还有很大的研究空间 ,有更强的实用性 ,也具有更大的挑战性。本文主要针对二维规则碎片 ,应用前景受限 ,如果能把二维的工作扩展到三维空间 ,将会有更加广泛的应用空间。 将规则碎片推广到针对多边形碎片复原的复原匹配算法，由于多边形碎片的特殊性 ,综合利用了多边形碎片的形状和灰度特征进行匹配 ,这是整个算法的关键 ,也是创新点。 图像碎片复原问题除了上边提到的以外 ,还可以推广到很多其他领域 ,比如 ,破碎的艺术品复原 ,破碎的纸币复原
26、 ,公安机关破案中的破碎证物复原等等。从理论上讲 ,图像碎片复原技术的核心技术是碎片匹配拼接问题 ,是模式识别技术的一个新发展 ,超出了传统模板匹配的局限 ,对这个问题的深入研究将促进机器识别 ,计算机视觉等 相关领域的发展 ,开辟模式识别新的应用领域。因此 ,不管从理论角度还是从实践角度来看 ,本课题的相关研究工作都具有积极的意义。 六模型的优缺点分析与评价 虽然我们进行实验仿真所涉及的纸片数量不多，但是它充分表明了所进行的碎纸拼接复原技术研究的可行性。 虽然文中所用算法在实验中取得了比较好的效果 ,但还需挖掘潜力 ,进一步优化。因此，如何减少错误匹配的数量，提高效率，增加适应性，也是下一步
27、的工作重点。 在实际应用中，由于设备等条件的限制，一次处理往往不能完全完成拼接任务。因此，必须开发合理的数据库，以充分利用 每次拼接得到的结果。 虽然在进行简单拼接复原的时候，计算机可以满足要求，但是在实际应用中，通常会涉及对大量纸片数据进行管理和处理工作。目前，我们主要还是以实现功能为主，下一步必须优化程序结构，改善用户界面，提高程序的交互能力，真正实现快速有效的计算机辅助碎纸 自动拼接复原系统。 本文对碎纸自动拼接进行了研究，在前人研究的基础上寻找一些新的研究方法进行研究，或者是对一些传统的方法进行应用与改进，可进行深入探讨，将其应用于计算机辅助碎纸自动拼接中，以取得很好的效果。 参考文献 1曹弋， MATLAB 教程与实训 ，北京，机械工业出版社， 2012 年 2盛骤，概率论与数理统计第四版，北京，高等教育出版社， 2008 年 3邓薇， MATLAB 函数速查手册，北京，人民邮电出版社， 2010年 4姚泽清，全国大学生数学建模竞赛赛题与优秀论文评析（ 2005 年 -2011 年 B题），北京，国防工业出版社， 2012 年 5贾海燕，碎纸自动拼接关键技术研究， 2005年 6先毅，图像碎片复原方法的研究， 2010 年 7楼兵军，基于区域的图像匹配算法的关键技术研究， 2006 年 附件 附录一： 附件 1 的复原图
