君，已阅读到文档的结尾了呢~~
碎纸片的拼接复原
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
碎纸片的拼接复原
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer--144.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口当前位置： >>
碎纸片拼接论文
碎纸片的拼接复原模型摘 要本文运用左右边界匹配、图片特征匹配、上下边界匹配等方法研究单页打印纵切纸 片、单页打印横、纵切纸片以及双页打印横、纵切纸片的拼接与复原问题。 针对问题一，首先对图像进行数据处理，读取图片的灰度信息，构建灰度矩阵，从 而将二维图片数值化。接着，提取出矩阵的第一列与最后一列，存储在图片的左右边界 矩阵中， 通过建立两张图片的左右边界匹配度模型，探究图片的左右邻接关系。计算 结果为：汉字图片从左到右依次为：008、014、012、015、003、010、002、016、001、 004、005、009、013、018、011、007、017、000、006，英文的排序结果为：003、006、 002、007、015、018、011、000、005、001、009、013、010、008、012、014、017、 016、004。 问题二，利用 matlab 软件的 imread 依次读取图片的灰度信息，存入图片的特征列 向量中，并将此列向量作为行特征的唯一标识，建立图片的特征匹配模型，将列向量元 素差异最小的图片聚类，中文确定出 15 类，英文归为 16 类。然后通过人为干预，实现 类的合并， 使每类中的图片个数相同， 将中英文都聚成 11 类， 每一类包含 19 张图片。 构建行内图片的左右边界匹配模型，最终确定出每类内部图片的排序；然后再做列位置 筛选，建立每行上下边界匹配模型，得出在各行的上下位置序列，经过两层筛选，得出 原文件图片序列。最后，视人工干预后的最终结果为正确答案，检验未加入人工干预计 算机排序结果，得到中文的拼接正确率为 90.4%，英文的拼接正确率为 65.1%。 对于问题三，建立两次特征匹配模型将图片聚类，即首先任取一碎片的一面依次与 其他碎片的两个面分别作第一次特征匹配，寻得与该面特征匹配程度高的另一碎片一 面，再将这两个碎片的另一面做第二次特征匹配，在两者匹配很好的前提下，探求出两 片的确定面属于同一类。加入人工干预，对类的个数降维，并保证每类中图片的数量相 同。再利用问题二中的模型构建方法，通过左右边界匹配模型的求解、上下边界匹配模 型的构建方法，完成了本问的研究。最后，我们从问题二的模型多增加一层特征匹配约 束可得到问题三的模型这一角度出发，得出了模型三的拼接精度更高这一结论。 本文综合各种匹配方法，根据问题的深入，对匹配模型加以不断的改进，结合 matlab 编程、word 拼图等手段，对碎纸片的拼接复原做了逐步深入分析，并给出了基 于边界灰度、 图片行特征灰度的匹配模型。 在文章的最后对模型的适用范围做出了推广， 在实际应用中有较大的参考价值.关键词：碎纸片 拼接图像 灰度 灰度矩阵 分组 元胞数组一 问题重述1论题给出了 5 个附件――反应了几种不同纸片破碎的情况，要求我们构建相应的碎 纸片复原模型，以解决实际生活中出现的需要我们进行碎纸片复原的问题。首先进行简 单情况的碎纸片复原，即附件 1 中和附件 2 中的仅纵切的中英文 19 个碎纸片。构建一 个可以操作的拼接模型， 将附件中的纵切纸片拼接。 接着针对复杂的情况纸片拼接复原， 构建一个简便的拼接模型将附件 3 和附件 4 中的横纵交切的 208 个碎纸片拼接复原。最 后针对更一般的情况，利用改进的复原模型处理双面的纵横交接的碎纸片。二 问题分析碎片的拼接复原，通常的做法是人工识别碎片边缘的字迹断线、和理解碎片内文字 含义，这样利用人工智能的方法虽然准确度高，但是当碎片的数量很大时，人工的效率 就显得低，而且出错率会明显提高；而计算机拼接与复原图像，虽不及人工识别智能， 但能充分发挥其运算量大，运算速度快的特点。 故本问题的目标就是利用附件中给的碎片数据，分单页纵切，单页横纵切，双页打 印横纵切三种情况，把拼接复原问题抽象成一个明确完整的数学模型，利用计算机，并 加以人工干预，复原出原图表。 首先应当明确，本论题所给的碎纸片都来自同一张纸，所以下面的问题分析 都是针对来自同一张纸的碎片复原问题，并且建立的逻辑以及构造的复原模型都是只针 对这一特殊情况。更复杂的情况会在文章后面的模型评价里做简单的阐述，本文基于本 题目问题的考虑就不做具体的分析了。2.1 仅纵切的单面碎纸片拼接复原分析问题一要求仅考虑单面纵切， 建立来自同一页印刷文字文件的碎纸机破碎的纵切纸 片拼接复原模型和算法。 通过对附件 1 和附件 2 给出的碎片数据图的观察， 发现本题的 碎片图像具有相对文字（汉字、英文）方向纵向规则剪开的特征，所以不适合基于碎片 的边缘线建模，也不适合基于两幅图片的重合度建模。我们知道，这 19 个纸条来自同 一个整体，必然反映整体的信息，而且这 19 个碎纸条又是从同一张纸被切开，所以它 们之间也存在联系,同一个纸条，其左右边缘所反映的信息与其邻近的纸条高度匹配， 我们可以根据打印文件的每行文件具有前后连续性，考虑先从读取文件数据入手，存储 每幅图片对应的灰度值矩阵。依靠得到的灰度值矩阵，并利用相邻接左右边界差异不大 这一特性作为依据来建立左右边界匹配模型，利用 matlab 编程来解决此问题，复原出 图片的原始序列。2.2 纵横切的单面碎纸片拼接复原分析附件 3 和附件 4 给出了 209 个碎纸片，此题加入了横向切割，使得切割方式更加多 样化和更接近实际。 它相对于第一问而言， 图片的信息量更小， 图片的个数增多了一倍。 图片总体不仅在纵向具有无序性， 而且在横向也具有无序性。 若仅采用问题一中的方法， 定位约束太少，每个纸片对整个页面的信息承载量非常少，而每一张纸片可能有四个切 口，所以可能会出现一个图片与多个图片最小差异度相等，导致该图片与多个图片相联 系，纸片间的联系更加凸显，进一步模糊了碎片包含的页面信息，从而增加问题求解的 难度。通过观察图片的平行切割特点，发现来自原文件同一行的文字切割后的图片一般 在相同的行位置上。所以可以考虑，先进行行位置筛选，通过构建图片的特征列向量作2为唯一标识，建立特征匹配模型，得到具有相同行特征的图片，聚成同一类。考虑到每 类包含的图片个数不一致，可加入人工干预，对类的个数降维，使得行集合包含的碎片 个数一致。 而利用左右边界匹配模型可以确定同一行的图片的序列； 可采用相同的原理， 建立上下边界匹配模型来解决纵向图片的定序问题。这样一来，可以拼接出本问的原文 件，完成问题二的求解。2.3 纵横切的双面碎纸片复原分析问题三在前两问的基础上，加入了双面打印这一条件。本问中图片的个数相较于问 题二增大了一倍，附件 5 给出了 2 ?11?19 ? 418 个双面掺杂的碎纸片，较前两问复杂度 更高，而且图片承载的有用信息则更加的小。由于从单面看问题二和问题三没有任何区 别，所以可以采取相似的方法对问题三求解。但我们思考总结出如下两方面：一方面不 能思维定势， 也就是说所有编号中带有 a 的图不一定都来自同一面， 即有可能是碎纸片 的正面也有可能是碎纸片的反面。另一方面如果采用问题二中相同的处理方法对附件 5 中所有的图片排序的话，可能会发生一个图片的匹配图片过多，或者出现将一个碎纸片 的正反面归为同一类的错误。综合以上两方面的思考，但我们应该看到问题的实质，同 一张碎纸片上的英文正反面字母切割的比例是完全相同的，我们在对问题三建立模型的 时候，将双面打印的英文文档转化成两页不同的碎片进行各自拼接。问题三的求解过程 的特点在于：先对一张碎纸片构建其对应的特征匹配模型，若得到另外一张碎纸片与这 张碎纸片匹配，则随后对它们的反面进行匹配以检验，如若匹配不上，则加上人工干预 的方法，对碎纸片进行拼接，直至最后得出完整的图片。思 维 导 图三 模型的假设3为了使得复杂的现实问题变得更容易处理，我们从现实中抽出了一些特殊的 情况。所以我们给出如下模型合理性的假设： 【1】假设碎纸片上的切口是横平竖直的（碎纸机的结果）； 【2】假设碎纸片上的文字书写完整规范且正确； 【3】假设附件所给碎纸片中不包含不属于该页纸的碎纸片； 【4】假设正反两面的英文是按相同位置打印的，即切过以后正反两面所在的行是 相同的，所切的字母也是同样比例的。 【5】所有碎片中的文字颜色一致，且与背景颜色有较大反差。 【6】所有碎片中的文字是从左至右、从上至下书写的。四 符号说明符号 符号意义 第 i 张图片转化得到的灰度矩阵 第 i 个图片灰度矩阵第 m 行 n 列对应的灰度值 第 i 个图片灰度矩阵的第 j 列 第 j 个图和第 k 个图之间的吻合参数（其含义在模型分析中说明）， 其中两张图片的吻合参数越小表示这两图吻合度越高AiP{i}m,nP{i}( j )? j ,k五 模型的建立与求解5.1 问题一5.1.1 模型建立基于假设 5，我们可以先利用 Matlab 读取图片的灰度矩阵，图像经过数字化处理 后， 图像信息简化为像素矩阵， 图片的匹配问题可以转化为图片边缘像素列的匹配问题。 若两张图片可以匹配，则其拼接缝上各点的像素值会非常接近，其差值接近 0。? ?| p(i)m,n ? p(j)m,n |?i , j ? ? | p{i}k ,72 ? p(j)k ,1 |k ?1min ? ? A[i],A[i ?1]i ?1184当在接缝处两张图片的像素列匹配达到最优时，则可以将这两张图片拼接在一起。 选取一张图片为基础，选取左右两端像素值最接近的图片与基准图片进行匹配，重复上 述过程直至将所有图片拼接完毕。5.1.2 基于贪婪算法的纵切模型一的算法设计与求解（1）贪婪算法简介 当一个问题的状态空间很大时，穷举法计算量可能会太大，而贪婪算法的思想则是 采取目前看来最接近解状态的选择方案，它是一种不追求最优解，只希望得到较为满意 解的方法。贪婪算法常以当前情况为基础作最优选择，而不考虑各种可能的整体情况， 贪婪算法采用逐步构造最优解的方法，一般贪婪算法将构造可行解的工作分阶段来完 成，在每个阶段，选择那些在一定的标准下是局部最优的方案，期望各阶段的局部最优 的选择带来整体最优，但更多的情况下，可能只是近似解，做出贪婪决策的依据为贪婪 准则，而贪婪准则是实际环境中人民所采用的规则，也称为启发式方法。 （2）贪婪算法步骤 STEP1：确定要拼接的图片个数。 STEP2：读取所有图片的灰度值，将图片数字化。 STEP3：确定第一张图片，再依次确定与其相邻的下一张。 利用 Matlab 软件可以实现上述操作，程序见附录 7。5.1.3 纵切碎纸片拼接复原模型一的实例验证1、中文碎纸片的拼接复原 附件 1 中所给的图片为扫描原纸张碎片后得到的 BMP 格式的图片，图片像素均为1980 ? 72 ，使用 matlab 中的 imread 函数可以做出图片的灰度矩阵 Ai ，举例如下（由于该像素图片转换后为 1980 ? 72 的矩阵，论文中无法放置，所以仅简单举例说明，论文中 若还出现庞大的矩阵，同本说明）：? 255 255 0 ? ? ? Ai ? ? 255 220 150 ? ? 255 0 0 ? ? ?矩阵的中元素表示该位置图片的灰度，255 表示为白，0 为黑，图片中信息为黑白 文字信息。将附件 1 中的 19 张图片做如上处理得到均为 1980 ? 72 的矩阵，这里我们分 别将每张图片的 Ai 矩阵第 1 列和第 72 列提取出来做一新的二维边缘矩阵 Bi ，它是1980? 2 的矩阵。通过对所有图片矩阵的分析可以发现 B 6 、 B 8 矩阵中均有一列为 0，所以可以认为编号为 006 和 008 的图片为原完整文件的一端，在做题过程中无需考虑会存 在其他白边与白边拼接的情况。 利用 5.1.2 中建立的模型并利用设计的算法步骤进行求解，1980 1?i ?19,i ? 9,i ?t2?9,i ?min? | p{t }k ?12 k ,72? p{i}k ,1 |5?t i ?2,1980 1?i ?19,i ?9,i ?t2min? | p{t }k ?1 1980 k ?12 k ,72? p{i}k ,1 |?t?tj ?1,i?1?i ?19,i ?9,i ? t2 ,...i ?t j ?1min? | p{t ? | p{tk ?1j ?1 k ,72}? p{i}k ,1 |? j 1i 7 ,1980 1?i ?19,i ?9,i ?t2 ,...i ? t17min17 k ,72}? p{i}k ,1 |可以得到中文的 19 张碎纸片的拼接顺序如表 1 所示，拼接复原图见下图。附件 1 拼接复原后完整图片6表 1.纵切中文碎纸片拼接顺序2、英文碎纸片的拼接复原 得到的匹配顺序如表 2 所示， 拼接复原图见附录 2。 将附件 2 的 19 张图片做 5.1.3.1 中处理得到均为 1980 ? 72 的矩阵，这里我们分别将每张图片的 Ai 矩阵第 1 列和第 72 列 提取出来做一新的二维边缘矩阵 Bi ，它是 1980 ? 2 的矩阵。通过对所有图片矩阵的分析 可以发现 B 3、B 4 矩阵中均有一列为 0， 所以可以认为编号为 003 和 004 的图片为原完整文件的一端，在做题过程中无需考虑会存在其他白边与白边拼接的情况。 做如上判断后解题过程同 5.1.3.1。附件 2 拼接复原后完整图片 表 2.纵切英文碎纸片拼接顺序75.1.4 对于拼接结果的分析在上述纵切碎纸片拼接复原模型的求解验证过程中没有用到人工干预，因为所给的 碎纸片中没有出现在拼接缝处均为空白的情况，所以依据灰度的匹配程度大小，可以完 成拼接。若在拼接过程中出现拼接缝处为空白的图片，则应暂时不予考虑，等到其他图 片拼接完成后，再对其进行人工干预，在剩下的空缺处对其进行拼接。5.2 问题二5.2.1 模型建立对于问题二，我们要同时考虑纵横切的碎纸片，首先确定每一行的第一列，然后利 用人工干预的方法拼出 11 行，再利用问题一的算法，将这 11 行依次拼接得到完整的文 件，即“聚片成行，聚行成页”。5.2.2 基于元胞数组算法的纵横切模型二的算法设计与求解（1）元胞数组 这是 matlab 中的特色数据类型，它不同于其它数据类型（如字符型，字符数组或 者叫字符串，以及一般的算术数据和数组）。它特有的存取数据方法决定了它的特点， 它有给人一种查询信息的感觉， 可以逐渐追踪一直到所有的变量全部翻译成基本的数据 信息。它的 class 函数输出就是 cell（细胞之意）。matlab 中用 char(n)来定义，当然 最基本的是包裹式定义，比如先定义了一个字符型的变量 a，并赋值，然后定义一个长 整型 b，并赋值?最后用大括号来打包裹 c={a,b}来形成元胞 c，当然进一步可以将 c 再包裹进去如 d={a,b,c,'abc',123}都是合法的。 用 cell 函数创建元胞数组， 创建的数 组为空元胞。cell 函数创建空元胞数组的主要目的是为数组预先分配连续的存储空间， 节约内存占用，提高执行效率。 （2）元胞数组算法步骤 STEP1：确定要拼接的图片个数。 STEP2：读取所有图片的灰度值，将图片数字化。 STEP3：确定第一张图片，然后寻找与其相接的下一张图片。直至将一行拼接完成。 STEP4：按照 STEP3 的步骤，依次拼接完成 11 行，得到 11 张图片。 STEP5：利用 Matlab 读取这 11 张图片的灰度值，再依据问题一的算法进行计算拼 接。85.2.3 纵横切碎纸片拼接复原模型二的实例验证1.中文碎纸片的拼接复原 此问中同 5.1.3 中的图片处理方法，也需要将 209 张碎纸片进行同样的图像处理转 化为灰度矩阵。根据结果知此问中的图片转化后的矩阵为 72 ?180 的矩阵，列数由第一 问中的 1980 变为 180，虽然数量变少，但是图片数量由 19 张变为了 209 张。利用上述 算法及人工干预，我们可依次得到 11 张图片，如下图 3 所示。图 3.附件 3 部分图片再利用 5.1.2 中建立的模型将这 11 张图片依次拼接，最终得到完整的图片，顺序 如下表 3。附件 3 完整图片9表 3.纵横切中文碎纸片拼接顺序2. 英文碎纸片的拼接复原 通过上述步骤可一次把相同行的纸片先拼接好，得到新的 11 张横行碎纸片，如下 图 4。这里拼接 11 张碎纸片的方法同 5.2.3，不再重述，得到的结果顺序见下表 4。图 4.附件 4 部分图片附件 4 完整图片10表 4.纵横切英文碎纸片拼接顺序5.3 问题三的模型建立与求解问题三要求在双面打印横纵切割的情况下，对碎纸片进行拼接复原。由于问题三较 于问题二，加入了双面打印的这一个新的条件，故可知问题三的基本思路可与问题二大 体相似。5.3.1 模型的准备1.图像的数据读取与处理 利用 matlab 的 imread 读取每一张图片的灰度信息值，再将灰度信息值转换为 0-1 矩阵。 2.构建正、反面特征矩阵 利用问题二中英文灰度条的够将方法，先得到图片 k 的 a 面特征灰度条，再扫描特征灰 度条，得到 a 面的特征列向量：(k ) ) (k ) (k ) T Da ? (d1(,k a , d 2,a ,...,d m,a )?0, 第k张图片的第i行元素之和&M ) 其中 d i(,k a ? ? ?1, 第k张图片的第i行元素之和 ? M同理，得到 b 面的特征列向量：(k ) (k ) (k ) (k ) T Db ? (d1,b , d2, b ,..., dm,b )?0, 第k张图片的第i行元素之和&M ) 其中， di(,k b ? ? ?1, 第k张图片的第i行元素之和 ? M5.3.2 建立双面纵横切纸片匹配模型1.建立两次特征匹配模型 第一次特征匹配： 将碎片 k 的 a 面与碎片 s（s=0,1?208 且 s≠k）的 a 面进行特征比较，即求碎片 k(k ) (s) 的 a 面特征向量 Da 与碎片 s 的 a 面特征向量 Da 的对应元素之差，在对差的绝对值求11和，得到特征值 Rka,,sa ：) (s) Rka,,sa ? ? | di(,k a ? di , a | i ?1 m再将碎片 k 的 a 面与碎片 s（s=0,1?208 且 s≠k）的 b 面进行特征比较，即求碎片 k 的(k ) (s) a 面特征向量 Da 与碎片 s 的 b 面特征向量 Db 的对应元素之差， 在对差的绝对值求和，得到特征值 Rka,,sb ：) (s) Rka,,sb ? ? | di(,k a ? d i ,b | i ?1 mRlk ? min ? Rka,,sa , Rka,,sb ?取一个合适小的置信区间 ?c, d ? ,若 Rlk ??c, d ? ，则进行第二次特征匹配：l 情况一（ Rk ? Rka,,sa ）：将碎片 k 的 b 面与碎片 s（s=0,1?208 且 s≠k）的 b 面进行(k ) (s) 特征比较, 即求碎片 k 的 b 面特征向量 Db 与碎片 s 的 b 面特征向量 Db 的对应元素之差，在对差的绝对值求和，得到特征值 Rkb,,sb ：Rb ,b k ,s ) (s) ? ? | di(,k b ? d i ,b | i ?1 mb,b 取一个合适小的置信区间 ? e, f ? ,若 Rk , s ??e, f ? ，则认为碎片 k 与碎片 s 的匹配方式为 k的 a 面与 s 的 a 面处于一面的同一行上，k 的 b 面与 s 的 b 面处于另一面的同一行。 情况二 ? Rkl ? Rka,,sb ? ：将碎片 k 的 b 面与碎片 s（ s=0,1?208 且 s≠k）的 a 面进行特(k ) (s) 征比较，即求碎片 k 的 b 面特征向量 Db 与碎片 s 的 a 面特征列向量 Db 的对应元素之b, a 差，再对差的绝对值求和，得到特征值 Rk ,s ：m) (s) Rkb,,sa ? ? | di(,k b ? di , a | i ?1b,a 取一个合适小的置信区间 ? e, f ? ,若 Rk , s ??e, f ? ，则认为碎片 k 与碎片 s 的匹配方式为 k的 b 面与 s 的 a 面处于一面的同一行上，k 的 a 面与 s 的 b 面处于另一面的同一行。 2.建立左右边界匹配模型 左右边界矩阵为：12B(k )(k ) (k ) ? c1,1 ? c1,72 ? (k ) (k ) ? ?c c ? ? ? 2,1 2,72 ? ? ? ?c ( k ) c ( k ) ? ? 180,1 180,72 ?（1）右边界匹配模型的构建 将第 k 个图片的右边界与第 s 张（ s=0，1?208 且 s≠k）图片的右边界进行左边 界匹配，即求第 k 张图片边界矩阵的第一列与第 s 张图片边界矩阵的第二列对应行元素 的差，再求差的绝对值的和―― Pkl, s ：k) Pkl, s ? ? | ci(,1 ? ci(,sn) | i ?1 m将第 k 个图片的左边界一次与其余的任意一张图片的右边界尽心匹配， 得到 n 个值： Pkl,1 ，Pkl,2 ，? Pkl,n 。通过比较，取这 n 个值中的最小值，作为左边界匹配值。Pkl, s ? min ? Pkl,1 , Pkl,2 , , Pkl,n ?（2）最佳边界匹配模型的建立 取第 k 个图片，先与任意一张图片 s（ s=0，1?208 且 s≠k）图片依次进行右边界 匹配，求得 Pkr, s ，再与任意一张图片 s（ s=0，1?208 且 s≠k）图片依次进行左边界匹 配，得 Pkl, s ，取两者的最小值：Pk* ? min ? Pkl, s , Pkr, s ?Pk* 对应的匹配方式即为第 k 张图片与第 s 张图片的最佳匹配方式。若 Pk* = Pkr, s ，则说明第 k 张图片的右边接于第 s 张图片的左边，记做 s→k。 综上，我们的左右边界匹配模型可以总结为：Pk* ? min ? Pkl, s , Pkr, s ?Pkr, s ? min Pkr,1 , Pkr,2 ,m?, Pkr,n ?s) Pkr, s ? ? | ci(,kn) ? ci(,1 | i ?1Pkl, s ? min Pkl,1 , Pkl,2 ,m?, Pkl,n ?k) Pkl, s ? ? | ci(,1 ? ci(,sn) | i ?113（3）建立上下边界匹配模型 将第 k 张图片的上，下边界出的元素分别存于 E ( k ) （k=1,2,?,11）矩阵的第一行、 第二行中。即上下边界匹配模型中第 k 行的上下边界矩阵为：E?k ?(k ) ? c1,1 ? ? (k ) ?c ? 2,1 (k ) ? c1, n ? (k ) ? c2, n ?模型的构建如下： 1. 上边界匹配模型的构建 将第 k 行的上边界与第 s(s=1,2,?,11 且 s≠k)行的下边界进行匹配，即求第 k 行 的边界矩阵的第一行与第 s 行的边界矩阵的第二行对应列元素的差，再求差的绝对值 的和―― Qku, s ：n(k ) (s) Qku,s ? ? | c1, j ? cm, j | j ?1将第 k 行的上边界一次与其余的任意一行的下边界进行上边界匹配， 得到 n 个值： Qku,1 ，Qku,2 ，?， Qku,n 。通过比较，取这 n 个数的最小值，作为上边界匹配值。Qku, s ? min ?Qku,1 , Qku,2 , , Qku,n ?2. 下边界匹配模型的构建 将第 k 行的上边界与第 s(s=1,2,?,11 且 s≠k)行的下边界进行匹配，即求第 k 行 的边界矩阵的第一行与第 s 行的边界矩阵的第二行对应列元素的差，再求差的绝对值 的和―― Qkd, s ：n(k ) (s) Qkd,s ? ? | cm , j ? cl , j | j ?1将第 k 行的上边界一次与其余的任意一行的下边界进行上边界匹配， 得到 n 个值： Qkd,1 ，Qkd,2 ，?， Qkd,n 。通过比较，取这 n 个数的最小值，作为上边界匹配值。Qkd, s ? min ?Qkd,1 , Qkd,2 ,14, Qkd,n ?3. 最佳边界匹配模型的建立 取第 k 行，先与任意一行 s（s=1,2,?，11 且 s≠k）依次进行上匹配，求得 Qku, s ，* 再与任意一行 s（s=1,2,?，11 且 s≠k）依次匹配， Qk 取两者的最小值：* Qk ? min Qku, s , Qkd,s ??* * 对应的匹配方式即为第 k 行与第 s 行的最佳匹配方式。若 Qk = Qku, s ，则说明第 k 行上 Qk * 边接于第 s 行的下边； Qk = Qkd, s 时，说明第 k 行的下边与第 s 行的上边相连接。综上，我们构建的横纵切纸片的匹配模型为：* Qk ? min Qku, s , Qkd,s ??Wk , s ? ? | di( k ) ? di( s ) | ? ? a, b ?i ?1mQku, s ? min ?Qku,1 , Qku,2 ,n, Qku,n ?(k ) (s) Qku,s ? ? | c1, j ? cm, j | j ?1Qkd, s ? min ?Qkd,1 , Qkd,2 ,n, Qkd,n ?(k ) (s) Qkd,s ? ? | cm , j ? cl , j | j ?1（1）算法 Step1：读取图片数据，构建矩阵； Step2：任取碎片 i 依次与其他碎片 s 进行二次特征匹配，确定出 i 与 s 的特征面来 自原文件的同一行； Step3：重复 step2，将附件中的图片聚类分析，将相同特征的图片放在同一行；15Step4：必要时加入人工干预，将类的个数降维，并使得没类的图片个数相同。 Step5：取统一行中的第 i 张碎片，将其依次与第 1 张碎片，第 2 张碎片，…，第 n 张碎片进行左右匹配，得到右边界匹配值，再依次进行左右边界匹配，得到左边界匹配 值。比较右边界与左边界匹配值得大小，选择两者中最小值对应的匹配方式，将两张图 片按匹配方式结合，视为一个整体。 Step6：重复进行 step5，直至确定出每行内部图片的排列顺序。 Step7：取第 i 行，将其依次与第 1 行，第 2 行，…，第 n 行进行上边界匹配，得 到上边界匹配值， 再依次进行下边界匹配， 得到下边界匹配值。 比较上下边界值的大小， 选择两者中最小值所对应的匹配方式，将两张图片按匹配方式结合，视为一体。 Step8：重复进行 step7，直至确定出每行的上下位置，从而得到图片的原始序列。（2）算法的实现 根据上述模型的分类原则，通过 Matlab 编程（见附录），将附件 5 中的 2×209 张 图片进行了归类。程序计算出来的结果中总共含有 36 类，这里只选取其中的三类元素 展示在表 11 中：表 11 特征匹配后的聚类结果类1 0 7 84 85 30 86 45 69 1 2类2 37 65 70 6 24 99类3 26 100 57 91105 121 88107 115139 151 96103 106 134 196135 141 148 204 80 126176 185 162 166 170 187 203180 191 109 112 113在这 36 类中，每一类的元素个数参差不齐。这是需要人工干预，先从元素较少的 类中挑出元素与其他累的图片进行比较，通过对比图片中的文字到上边界的距离，文字 的含义及其文字内容等特征，将这些图片归入其他元素较多的类别，直至正、反面都有 11 类，每一类 19 个元素。 利用左右边界匹配模型，对每一类中各个碎片进行横向排序，得到各类中图片的排 列顺序。再利用上下边界匹配模型，求出类与类之间的排列顺序。结合碎片在行内的排 列顺序以及类与类之间之间的排列，就可以得到碎片再原文中的原始位置，进而复原出 图片。拼接后的顺序如下表 5 和表 6。16附件 5 拼接复原正面图片附件 5 拼接复原后反面图片表 5.碎纸片正面拼接顺序表 6.碎纸片反面拼接顺序六 模型的评价与推广6.1 模型的优点通过对复原后图片的验证结果可以认为本论文中的碎纸片复原拼接模型对于本题有17很高的可行性。对于中、英文两种情况，论文中按照从问题一到问题三、中文到英文的 顺序依次改进模型。发现了中文需要人工干预较少，英文需要人工干预较多的规律，说 明不同语言有各自的特性。 对于计算机错误匹配的结果，论文中在问题二与问题三种给出了详细的人工干预的 时机与方法，通过模型说明不需要人工干预是不可能的。从问题一到问题三、中文到英 文由于难度的增加依次将模型进行改进，给出了严谨的说明过程，可认为模型对该类问 题有很好的可用性6.2 模型的缺点论文中的模型仅适合规则碎纸片黑白信息的复原问题，不能解决不规则碎纸片的复 原与非黑白信息的复原。人工干预占总过程时间的比例相对较高(35%)，对于数据量大 的碎纸片复原问题，人工干预可能会花掉大部分时间。 对于信息量少的图片，即像素小的图片匹配精度低，效率差。所以，此模型适用于 拼接信息量大的图片。6.3 模型的推广由于题目中所给的碎片是高度规则的，而现实生活中很少出现这种状况，所以模型 应该朝着实现不规则边缘碎片拼接和减少人工干预次数的方向改进和发展。当碎片边缘 不规则时，则应考虑边缘几何因素。结合像素因素仍能得到较为独立完整的局部碎片， 在经过人工处理，得到整个图形。 本文建立的图片拼接法不仅适用于碎纸片的拼接问题，还可应用于其他方面，比如 陶瓷的拼接复原等问题，分别将陶瓷碎片看成文中的字片，通过 Matlab 读取瓷片本身 的花纹特征来求其匹配矩阵，以此来进行全局搜索复原。七 参考文献[1]Matlab 元胞数组 /view/3515302.htm?fr=aladdin [2]姜启源 谢金星 《数学模型》 [3]龚纯 王正林 《精通 Matlab 最优化计算》 [4]罗智中，基于文字特征的文档碎纸片半自动拼接，计算机工程与应用，48（5）： 207-210，2012 年。 [5]陈杰，MATLAB 宝典，北京：电子工业出版社，2012 年。 [6]张志涌 杨祖樱等《Matlab 教程 R2012a》 [7]张桂华 冯艳波 陆卫东，图像处理的灰度化及特征区域的获取，《齐齐哈尔大 学学报》，2007 年 04 期18[8]Matlab 贪婪算法 /link?url=-88d5Lkcq6jzqkqxWaeUqa2Y2rIimMGoVt-Mkg2Q4r4 y_9r8zgjkLbTAaXqMuk5tho6ShhO3sOjkzxxtshjiO87dWsmiy89L_K9cTRoP4PG [9]章毓晋，图像处理，北京，清华大学出版社，2012 年。19}