碎纸片的拼接还原研究

1、碎纸片的拼接复原摘要碎纸片的拼接复原是一门借助计算机，把大量碎纸片重新拼接成初始纸 张的技术。针对问题一，本文首先利用碎纸片图像灰度矩阵的边缘矩阵，建立了两 个碎纸片之间的匹配度函数，求得了每一张图片之间左右边缘匹配度矩阵。 然后根据左边边缘位置的碎片的左边空口部分最多的特点，确定了左边位置 的碎纸片。接着根据拼接碎纸片的拼接复原时，所有碎纸片匹配度之和取极 大值的原则，采用贪心算法，得到了所有碎纸片的初始位置，拼接复原了附 件1和附件2中纸片。针对问题二，由于附件3碎片数量太多，并且碎片的拼接复原，是一个 以碎纸片总匹配度为U标函数的组合优化问题。所以本文采用遗传算法将碎 纸片的编号作为基因

2、，并将基因均匀分成19段，按顺序每一段对应一个初 始纸片列位置，进行了求解。然后，根据边缘碎纸片某些边的空白部分多的 特征，对初始基因进行了优化。接着，根据碎纸片的黑色像素密度不同的特 点，将碎纸片分成三类，根据同类纸片优先匹配的原则，对遗传算法的运行 过程进行了优化，拼接复原了附件3和附件4中纸片。针对问题三，随着碎纸片量的增多，计算量急剧增加。在上述拼接复原 碎纸片的基础上，乂引进了同行位置碎纸片的上部（或下部）空白位置宽度 相近的聚类思想。先对每个类内部拼接，在合并所有类并做一次整体拼接。 由于时间有限，我们未能完成最后一次的整体的拼接，但我们会在比赛后继 续探究。关键词：边缘矩阵匹配度

3、函数遗传算法聚类一、问题重述碎片拼接实际用途已经越来越广泛，传统上拼接复原工作山人工完成， 碎片拼接的准确率较高，但效率很低。并且当碎片数量很大时，人工短时间 内拼接出来儿乎是不可能的。所以开发碎纸的拼接技术，以提高拼接复原效 率已成为越来越多人的期望。现在,在碎纸片是规则的情况下，题目要求我们 在以下条件建立碎纸片拼接复原模型和算法。1. 来自同一页印刷文字文件（中文、英文各一页）的碎纸机破碎纸片（仅 纵切）拼接复原，并将附件1和附件2复原。2. 对碎纸机既纵切乂横切文件的情形，将碎纸片拼接完整。3. 上面陈述的碎纸片是单面打印文件，从实际情况出发，将双面打印文件 的碎纸片拼接复原，并把附件

4、5的碎片数据给出拼接复原结果。二、问题分析题目要求我们根据附件给出bmp图片进行复原拼接。附件给出的bmp 图片，是由灰度矩阵和位图矩阵构成。bmp图片的灰度矩阵中单个像素的值 的范围是从0到255。对于标准的单色的bmp图片，灰度矩阵只有局部连续 的0和255o根据其局部连续性，我们知道如果一个文字符号被分割，则被 分割的部分可以拼接成一个完整的区域。我们就是跟据这个基本原理来实现 碎片的拼接。1对于附件1, 2对来自同一页印刷文字文件的碎片（仅纵切）拼接， 提取19张碎片的左右边缘矩阵，根据建立匹配度函数，计算匹配度的大小， 得到19x19的匹配度矩阵。然后根据左边边缘碎块，左边边缘空白多

5、的特征， 优先选出左边的碎块，接着根据碎片构成的完整图片的匹配度取最大值的原 则，利用匹配度矩阵，釆取贪心算法，即可以得到完整的图片。2对于附件3,4中，既纵切乂横切的209块碎片的情形，要复原图片， 不能用简单的贪心算法。由于拼接大量碎块的问题，实际上就是一个组合优 化的问题。所以本文面对这样一个组合优化问题上，用了遗传算法来求解。 但是，由于该问题的适应度函数对基因的约束性不是强制约束，所以，要在 遗传算法的基础上，根据边缘碎块的特征，对初始基因进行优化，然后根据 209碎块的像素密度的不同，可以将其聚成三类，对于特定的基因片段，只 能在相应的类里匹配，来减少程序执行时无效的过程，提高程序

6、效率。3对于附件5,双面文字的碎纸片拼接复原问题，可以在第二问的基础 上只需考虑将一面复原就行。但对于双面复原问题，单面有空白的碎片存在， 所以得在拼接较好的两面的基础上，人工对少量的单面空白碎片进行干预。三、模型假设假设在任意碎片中，沿着文字符号某一线性切割，则该线性部分只存在 于被分割两部分中的任意一部分；假设单面碎片中，被分割的碎片中都存在文字符号或者不完整文字符号；假设来自同一页英文图片中字母是均匀分布的；假设碎片对应的原文排版是规范的，整页文章字体，字号，间距，行距 等等都是相同的。四、模型准备4.1基于局部连续性边缘矩阵的线性变换算法根据向量模在平移坐标变换中具有不变性的特征，我们

7、给出了一种新的 碎片匹配算法，即基于局部连续性边缘矩阵的线性变换算法：门。该算法是基 于局部连续性原理为基础，或者说是单色位图（只有黑色和白色）bmp图片 以局部“0”形式连续存储。在计算机中，纯黑白的图片存储矩阵中只有“0”和 “255”两种数字表示。而且每个文字就是由儿个连续区域矩阵组成，如果一个 文字被分割，则被分割的部分笔画可以拼接成一个连续的完整区域。我们就 根据这个原理来实现碎片的拼接。4.1.1汉字的组成和特征在中国的汉字中，有八种基本笔画，点、横、竖、撇、捺、提、折、勾， 乂称“永”字八法。表1汉字基本笔画表基本笔画点横竖撇捺提折勾基本形状、1)AT11）汉字的数字特征；汉字是

8、非字母、非拼音化的文字，它的最小构成单 位是笔画，但它的笔画没有固定的表意。很多学者提出了可以根据笔画的6 种位置关系用数学方法企图将汉字表达出来。而且汉字结构的描述可转化 为网格单元Ay之间的关系运算。2）汉字的方块特征；汉字字形以方块为特征拼音文字的字母一般是线性 排列的，一个词的语音形式所包含音位的多少，决定书面词形的长短，所以 拼音文字的拼写长度是长短不一的。汉字则不然，一个汉字不论笔画多少， 都要构成一个方形体，大小也基本一致。汉字字形的方块特征早在甲骨文金 文时期就略具雏形，但不明显；隶变以后，汉字基本具备方形特征，但字形 略扁；楷书汉字方方正正。正式确立了汉字字形的方块特征。4.

9、1.2英文单词的组成和字母特征英文单词由52个大写和小写字母组成，对英文单词的分割，也就是对 字母分割。根据字母自身的特点我们认为52个字母可以分成以下三类，第一类：由“直线”组成的字母，例如H, T等；第二类：是由“曲线”构成的字母，例如D, O等；第三类：就是由直线和曲线构成的字母。如下表：表2字母分类表第一类AHEFLT 1XxYyZzMNVvIiKkWw第二类CcSsUuGgOomQqnea第三类BbrDdPPhRftJj42选择拼接的原理计算机在处理线性问题的效率一般高于非线性问题，而且在线性选择的 过程主要是以线性变换为主，其他变换为辅。从以上这八种传统笔画组成中 可以看出，“横”

10、，“竖”，“撇”，“捺”可以基于线性变换可得，而“提”，“折”, “勾”却不能曲简单的线性变换而得到。曲于计算机在处理线性问题要比处理 其他非线性问题效率高得多，所以我们选择其中具有线性变换笔画的“横”， “竖”，“撇”，“捺”来实现文字图片的拼接。对第一类英文单词完全可以类似 成汉字笔画中的“横”，“竖”，“撇”，“捺”，所以；而第二类基于圆或者环的 封闭原理，我们了解到如果一个字母被分割了，我们可以通过考虑被分割的 部分是否可以组合成一个圈，来判断是否能拼接。4.2.1基于线性变化的数学描述：1. “竖”的线性变换，也叫垂直变化。假设原样本点位置坐标（心，儿），若 给一个基本步长（0J）,

11、能够满足（my°+f）；则称为一次垂直变换；2. “横”的线性变换，也叫水平变换。同理，假设原样本点位置坐标（心儿）， 若给一个基本步长（r,0）,能够满足（勺+人儿）；则称为一次水平变换；3. “撇”的线性变换。图片像素高，文字图片在MATALB中笔划儿乎是由 多行多列的“0”组成，保证了“撇”的线性变换，而且使倾斜角接近于45度， 所以取其斜率为1,假设原样本点位置坐标（心,儿），若给一个基本步长（/,/）, 能够满足（x0+/,y0+r）；则称为一次“撇“线性变换；4“捺”的线性变换。类似于“撇的线性变换，而且倾斜角都接近于负45 度，所以取其斜率为-1,假设原样本点位置坐标（

12、心,儿），若给一个基本步长 （门），能够满足（xo+h-yo-t）；则称为一次“捺”线性变换；5 $ $ 50055-5-5002 2 2 25 5 5 5 550055002 2 2 25555555555555 5 55222222225559 5555 005S55-005555 2222 2 2 2 2555$ 5 5 5 5 0025252525JO252525255 5 5 5 5 5 5500550055002 2 2 2 2 255555555555555555555555522222222222223图1文字符号线性换图4.2.2基于圈的二次非线性变换圈的非线性变换（二次性变

13、换）只是对第二类英文字母使用。字母的圈 类比数学上的抛物线，曲线（圈）关于的X轴对称的变换方程为x= ay2+b, 关于y轴对称的变换方程为y二ax2+co开口的朝向与a的符号有关，而且a 的取值与文字图片的像素大小写有关。分别统计每一类字母的个数mi,字母总数是52个，根据前文的假设来 自同一页英文图片中字母是均匀分布的。我们得到：2x26(/ = 123)基于上述理论基础，我们根据字母线性变换为主，非线性变化为辅，对 碎片进行拼接实验。结果显示：表3线型运用概率线型种类第一类第二类第三类运用概率（p）0.440.310.25线性变换不仅简单而且效率也高，拼接碎片完成可能性很大，在我们做 的

14、儿个实验中，利用简单线性变换全部拼接完成。而基于圈的二次变换也只 能作为字母拼接的一个辅助手段，第三类在排列过程作用很小的，有可能对 某一中切割没有作用。图2文字符号的非线性变换五、模型的建立与求解5.1模型一的建立与求解根据汉字的组成特征和字母的分析以及bmp图片存储矩阵的方法，我们 将要拼接的图片，与所有的图片根据匹配度函数，进行匹配度计算，选择与 该图匹配度最大值的图片拼接。考虑到这组图片里中只有纵切(纵向分割， 不存在横向分割)，所以我们只采用除垂直变换外的其他三种线性变换。经过分析，我们认为对碎片拼接问题，就是求两图片间的匹配度问题。 首先根据附件一给出的图片，在MATALB中用im

15、read函数将图片转换成灰 度矩阵形式。每张bmp图片的灰度矩阵为imag/nx«,对该矩阵进行标准化 处理，使得图片黑色像素值为0,其它白色像素值为255。图片右边缘矩阵 为EdgL(:,end),左边缘矩阵式EdgR(l,:)。然后对要拼接图片的右边缘矩阵与 其他图片的左边缘矩阵进行匹配度计算，选择与该图匹配度最大值的图片拼 接。具体的计算方法如下：记录确定图片的右边缘矩阵中0(黑色像素的位置)的位置矩阵为 LocalR； 记录匹配图片左边缘矩阵中0的位置为localLo对LocalR, LocalL 作差集，得到Local：» 求出 LocalR , LoaclL ,

16、 Local的矩阵 长度， 分别为 Len(Local),Len(LocalR),Len(LoaclL)；求出拼接图片与其他图片的匹配度，取其右边缘矩阵和其他图片的 左边缘矩阵匹配度值最大的图片与之匹配。我们建立的匹配度函数如下:Len(LoaclL(i, j)1 Md(matchdegree) = Max(Len(Local(i),Len(LocalR(j)可以从公式得出：当碎片的左右边缘中黑色像素位置越重合时，左右位置集 合的差集大小趋近与空集，也就是匹配度函数趋近于1,反正匹配度函数趋 近于0,并且同意碎块的左右边缘匹配度为0。在MATALB中计算出拼接图片与其他图片的匹配度。得到的模型

17、匹配度 结果如下表所示：表4模型匹配度部分结果表00.450.540.170.370.870.470.6500.770.180.890.450.3300.4400.240.930.550.270.440.000.510.130.40.590.2610 : a:1a0 : 19 : : 0.930.40.380.1400.430.360.550.590.570.220.4300.460.270.260.460.250.360.460以下是针对给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵 切），建立碎纸片拼接复算法。5. 1. 1对汉字拼接的主要算法伪码步骤如下：Step 1：提取任意一幅图

18、，进行处理，是图片存储矩阵Imagi有两种数字，“0” 和“255”；Step 2：对图片左右边缘矩阵EdgL和EdgR进行判断，选择不全是最大值的 一边，转接第三步；Step 3：对EdgL （或EdgR）进行下列尝试变换：（1）水平变换：y = y。；（优先考虑，若成功，则进行steP4）；（2）“撇”变换；y = kx + b （其中，及角度为0到90度），若成功，则进 行 step4；（3）“捺”变换：y = -kx+b （其中K>0,及角度90到180度），若成功，则进行step 4；若以上三种都不成功，则换另一副图片执行第一步；Step 4：对剩余图片进行匹配度矩阵Md （

19、match degree ）进行计算，选择匹配 度最大的一幅图进行拼接（匹配度公式写进去）；Step 5：选择其他样本点，调回第Step 3步；并判断匹配度收敛性，若收敛 进行下一步操作；Step 6：在拼接好的图片上在选择一边返回第一步。Step 7：完成整个图片的拼接，输出拼接好的图片。5.1.2对英文单词拼接主要算法伪码如下对英文单词的变换稍比汉字的复杂一些，但是大多地方是相同的，只是 多加了一种变换方法而已。Step 1：提取任意一幅图,进行处理,是图片存储矩阵Imagi有两种数字，“0” 和“255”；Step 2：对图片左右边缘矩阵EdgL和EdgR进行判断，选择不全是最大值的 边

20、，转接第三步；Step 3：对EdgL （或EdgR）进行下列尝试变换：（1）线性变换（与汉字的线性变换完全一样）；若成功，跳到Step 4；（2）曲线的二次变换，（在变换之前先求出二次变换方程），若成功， 跳到step 4；（3）线性变换和曲线变换结合（这种变换不仅效率低，而且成功率也 不是很高。这种变换只有0.25的成功概率）（4）若以上三种都不成功，则换另一副图片进行以上尝试；Step 4：对剩余图片进行匹配度矩阵Md （ match degree ）进行计算，选择匹配 度最大的一幅图进行拼接（匹配度公式写进去）；Step 5：选择其他样本点，调回第Step3步；并判断匹配度收敛性，若收

21、敛进 行下一步操作；Step 6：在拼接好的图片上在选择一边返回第一步。5.1.3线性变换模型求解我们利用MATALB软件对上述匹配度进行求解（求解程序见附录一），在 运行10次程序后把汉字碎片拼接起来，得到的复原图片（见附录二），下图 是截取复原图片的部分。城上慈下溝淮古氷竽手姦吴公，人与容天但适,魂/ 漏 味断、后夜月羔藪娄衣巾莎零花°村里村北喑统t比衣有柳卖还松刃 抵.海袋锻审董.,沽晓近冉拢"胭硏溝与匀淡.偏向验选浓"小郑祚蚩- 篇强主.艾I日佬诗更有M鱼堪切叱 儿适奖敎知。自古相从怵务衍* 已何妨低幅。犬壷公宝作右阴"坐m人半弹.帘外:将無 双

22、醐母 坠.毎眼閩磁翠.炒参蛰距二戏卜4轻克态妍。：:象轻笼冏凤，寇沏波虑 液務双鹘兴兀睇不H家转认门前£1马。为询我劝幻去妖,从来自己忘tfL尘心消尽道心平。江南与琵北.何：张9 牡不您行烏阻“谁念累按襄王，何曾智云麻旧恨前次，心吾两无抵.讯思 斐知欲兇审抽心犹耳倩人道、一孟传语亠凤卷姝帘口上钩，菇函乱 '由.图3附件一复原图像图片拼接的序号是：表4附件一汉字拼接序号81412310216145913181 17170615从图上我们可以看出序号为6的图片是整体的最右边缘图片，实际上， 序号15的图片却在了最右端。而且，我们可以清楚看到序号12的图片拼接 是不对的。导致这样的

23、结果是：我们的算法主要是运用了“横”的线性变换， 而且，序号12和3的图片中横的笔画比较多，以致于在匹配的时候图片序 号为12和3的匹配度大于原配图片。所以才会出现图片12与3匹配，图片 15就单独分开的情况。我们用了同样的方法，对英文碎纸片进行拼接得到了完整的复原图片。 也就是说拼接起来的英文与原图片具有一致性。复原图片见（附录三）。中英文拼接结果对比，说明在复原过程中，计算机分析图像的能力是有 缺陷的，让计算机对碎片进行完全意义上的自动化拼接也儿乎不太可能。为 保证拼接的准确性，需要在拼接过程中加入人工干扰过程。人工干预主要在 计算机将算法运行结束后，根据少量有错误的地方，凭借人类的视觉观

24、察， 将错误的图片序号进行调整，最后得到的完整图片。52模型二：基于遗传算法建立拼接纵横切碎纸片模型对于既横切乂纵切的情形，我们可以看做是一次横切和一次纵切的结 果。由第一问切割后的图片局部连续性原理可知，在拼接的过程中，利用线 性变换和二次变换相结合，可以完成文字图片的拼接。对于横纵切割的情形， 我们可以先纵向（横向）拼接，再横向（纵向）拼接。按照这样的拼接方法, 则需要将拼接的图片需要与其它图片进行4盂次匹配计算，过程繁琐，花费 时间很多。所以在第二问中，本文采用启发式算法一遗传算法进行求解。然 后根据一组基因对应的就是一个完整图片的原则，对附件3和附件4给出的 209张图片按1-209进

25、行编码。在横纵切割的情况下，因为在拼接的过程中，只有被裁减过的边缘才能 提供有效信息，而其余大部分所提供的信息是没有意义的，很难被直接利用 71如下图所示一个基因序列：4123147191508118912210313080332021981513512731602031214212414477图4碎片的基因序列上图每个方格（图片J代表一个基因序列，因为每个基因具有相同的方向， 所以在对图片进行拼接复原时，只需要求图片A的右边缘矩阵和下边缘矩阵 与其他图片的左边缘矩阵和上边缘矩阵的适应度。当整体匹配度取得极大值 时，该基因序列对应的拼接成的完整图片也就越接近原图。5.2.1遗传算法简介遗传算法

26、（GA）是一种基于自然选择原理的寻优法，是模拟自然界中的 生命进化机制，在人工系统中实现特定tl标的优化。实质是通过群体搜索技 术，根据适者生存的原则逐代进化，最终得到最优解或准最优解遗传算法流程如图所示：图5遗传算法流程图根据遗传算法，我们运用MATALB软件求解出用遗传算法拼接的图片与 原来整个图片的适应度关系。遗传代数与整体适应度关系，如下图所示：从图上我们可以看出：当遗传的次数在300次以内，相应适应度比较大。 当遗传代数大于450次的时候，得到的适应度趋于平衡。这样算法就会陷入 一个局部最优解的情形。也就找到了适应度局部极大值的拼接图片，而不是 适应度全局最大值的拼接图片。当处理的文

27、字图片碎片很多时，传统算法计算量会快速的增长，而且求 出的结果容易陷入局部最优解。因此算法的优化是我们首要考虑的因素。5.2.2提取碎片边缘矩阵的初次优化边缘矩阵的初次优化主要思想是被分割后的文字在两部分边缘处具有 相同的聚集形态。所以，我们根据这一特征，对被分割的文字进行拼接。将 上下左右边缘矩阵的信息存储在矩阵EdgL, EdgR, EdgU和EdgD中。为了 计算方便，使数据量尽可能地减少，我们只提取了边缘的有效信息。在边缘 矩阵Edg中，用集合Local统计“0”簇集的个数并用集合LocalL, LocalR, LocalU, LocalD记录每个“0”簇集所在的位置。考虑到集合做差集

28、需要花 费大量时间，其时间复杂度为O（Max（”2,?2）,所以为了减少做差集的次数， 我们先利用Local和Local5进行对应比较，即对每个边缘集合进行长度判断， 若不相等，则不做差集，若相等在做差集，时间复杂度为0（/）,这样大大减 少了比较次数，提高了程序效率。若现有任意两幅图片的的边缘簇集集合 LocalL（x ,X2，., Xm），LocalL （yry2,yj对其做差集：Loc = LocalL -LocalL =（zzzj（1为集合LocalL中的元素减去其和LocalL中公共元素后的元素个数）；5.2.3边缘碎片的优先选择1）在附件给出的大量的图片中，处于整片文章边缘的碎片有

29、如下特征：2）每张边缘碎片中至少有一部分存在非“0”簇集（空白部分）；3）对应Local矩阵中至少会出现一个0 （即边缘碎片至少有一部分不能匹 配）；4）所对应边缘应该是一个非“0”簇集，而不会出现单列的最大值；（对碎片来说，只有空白边缘的宽度达到一定值，才能认为是边缘的碎片）；从边缘一点（x,y）到第一个文字的最近一点（Ary,）需平移某一个步长，这 个步长根据边缘做分割的个数进行多次调试，（本程序最终调整结果是左右 为10,上下为30,恰好出现和理论计算的边缘个数22和36个）。步长的取 值不同得到的碎片个数也不同，步长变换和满足碎片条件个数如下图：图7左边缘步长d选取与满足条件的可疑碎片

30、个数从上图我们可以知道：当步长d<4的范围时，可疑碎片的个数比较 大，随着步长的增大而减少。当4vdvll时，可疑碎片个数趋近于11。当 d>ll时，可疑碎片的个数急剧下降。根据图片显示的结果，我们知道左 边缘的碎片，就是图上显示的11个左边缘可疑碎片。从上图我们可以知道：当步长d<25的范围时，可疑碎片的个数比较大， 随着步长的增大而减少。当26<d<37时，可疑碎片个数趋近于22。当d>37时, 可疑碎片系数急剧下降。根据图片显示的结果，我们知道上边缘的矩阵，就 是图上显示的22个上边缘可疑碎片。利用提取边缘矩阵的初次优化后，找出至少满足边缘碎片的一个特

31、征的 碎片集合Pieceo在Piece矩阵对单个边缘碎片矩阵线性变换进行拼接。524优化的遗传算法求解组合优化问题通过优化后的遗传算法很快的找到了上下左右的可疑边缘碎片。如下表 所示：表5边缘可疑碎片序号表左疑块(L)71429384961718994125168右疑块(R)193744606175124142146177197312152329505558667290上疑块(T)929611913014214417918718919119359262833416171758690下疑块(U)941021031091 14115118120124126141206147152153154155

32、156166167186195197208注：所有表中碎片序号和附件图片序号一一对应我们将得到的可疑块作交集得到如下结果：L和T作交集得到14 49 71 89； R和U作交集得到：89 125；R和T做交集得到141； R和U做交集得到60 75 124 197。根据得到交集的可以初步确定整个图片的右上角一定是编号为141的图 片。然后，再通过人工干预可以得到整个图片的左上角为编号为49的碎图 片，左下角为编号为125的碎图片。最后，用优化的遗传算法求出图片A的 右边缘矩阵，下边缘矩阵与B图片的左边缘矩阵与上边缘矩阵的适应度。根 据适应度最大原理来拼接图片。用MATALB编程(见附录)求出的

33、汉字碎片 拼接编号如下表所示。复原后的中英文图片见附录四表6纵横切汉字复原结果的表格形式49546514318625719217811819 0951112928911881416119786769991699613 I796311616372617720523616810076621423041231471915017912 08619526187183814846162435811891291031301938816725891057471156831322001780332021981513317020585152165276014128315982!99!351273160203169

34、1343931511071151769434841839047121421241447711214997136164127584312513182109197161841101876610615021173157181204139145296411120159218 04837755544206101()4981791715972013151268174517001353569315701632J988865407366891461021541144015120715514018510811741011131941191235.2.5基于遗传算法序列的二次优化在拼接完边缘碎片后，对其他碎片进行

35、拼接。内部碎片的矩阵看起来大 多杂乱无章，但也呈现出来一定的特征。利用这些特征可以简化算法，提高 效率。1）邻接碎片具有相同的边缘密度ED （edge density）即：一个字被分割在两 个碎片中被切的笔画数相等。2）右边缘的相似特性：如果某一碎片右边缘矩阵出现了全是非“0”簇集， 则其右邻接碎片一定全是由非“0”构成的矩阵（文章的写作都是先左后 右）。3）上（下）边缘的相似性：如果某一碎片的上边缘矩阵EdgU （或下边缘矩阵EdgD），出现全是非“0”簇集，则其左邻接的也是有相同的特性。基于以上特征探究分析，在算法实现过程中，可以作为一个判断条件， 若存在满足以上特征的碎片，则适应度函数首

36、先考虑上述拼接是否合理，若 不合理直接进入下次优化。53基于聚类拼接复原模型经分析，本题是综合了既横割乂纵割以及单双面切割的情形，在一、二 问的基础上，对模型改进完善。曲于横纵切，双面乂有文字，所以碎片量就 会特别多。若用一、二问的算法，计算量很大，而且效率低下。双面切割的 情况下，我们只要把任意一面拼接完整，另一面也就拼好了。在这里，我们 选择文字或者说文字符号多的一面来拼接，文字多就能尽可能大的完成一页 的拼接，而文字少的页面，出现空白较多，而我们对空白的处理比较难。这 样拼接成功的概率就比较高。于是，在第三问中，我们建立了基于聚类思想 的拼接技术模型。5.3.1聚类拼接模型根据局部连续性

37、原理，可以优先局部拼接，减少碎片数量，再进行整体 拼接。选取其中任意一面的所有碎片进行聚类，使得类内相似程度汉高，类 间相似度比较低。在利用前面的线性变换和其他变换进行类内拼接，在拼接 的过程中，优先匹配右边缘，基于右边缘相似性原理。在拼接玩类内后并所 有的类，对整体再一次进行拼接。伪码描述：Center = n 聚集簇中心个数；While(!pi) 选择碎片进行分类；MInDistance(Pi,Center(i); 计算每个碎片与中心的距离;Add(Center,Pi);将pi碎片加入距离最小的簇中;For(!Tag) /Tag是判断标志；Center (1) = Sum(Distance

38、(Pi)/Len(Center(i);While(!n)对类内进行右边缘相似性拼接；If(EdgR != 255) 不为页边缘碎片，则存在其右邻接碎片；Match(E(lgR(i),EdgL(j);/i 和 j 碎片进行拼接Unlon(Center) 合并内部拼接后的簇集；Match(Union, flag); 最后对整体进行一次拼接，并返回是否完全匹 配标志flag,若为0匹配成功，否则不成功，利用反面信息进行调整；1、右边缘相似性原理解释：1) 若某一个碎片Pi,其右边缘有x个文字符号被分割，则其右邻接的 碎片pi +1)左边缘也应有x个文字符号被分割；2) 若某一碎片pi,其上边缘为空白

39、(或下边缘为空白)，则其所右邻接的所有碎片= / + 上边缘为空白(或下边缘为空白)；3) 若某一个碎片Pi,其右边缘为空白，则其不存在右邻接碎片。2、利用像素密度碎片分类原理对于一张给定的bmp碎片，图片像素大小为兀xy,黑色像素的数量为No像素密度为p = oxx y对于给定的排版规则的碎片，碎片字体和字号，间距都是一样的。如上 图a, b, c所示，a图的左右邻居碎片，应该也是一行，及像素密度应该和a 图相近，同理b图的左右邻居碎片，应该是二行，c图的左右邻居碎片，应 该三行。mmw tui>oftme-a图9air:tlybc分类标准图附件3给岀的碎片主要是上图的三种，及可以把所

40、有碎片分为三类。并 求取所有图片的像素密度0,根据典型一行，二行字符的碎片的像素密度， 求取出分类的阈值为0.067, 0.014oa,b,c类图片在我们的算法中运行的得到的结果如下图所示：a类效果图b类效果图C类效果图图10聚类部分结果图我们的算法在初始聚类过程有着很好的变现，然而时间有效，我们未能对附 件四和附件五的论文做出完整的拼接，但是，我们会在比赛后继续进行挖掘 完善的。六、模型的评价6.1模型的优点1. 算法简单，将碎图片拼接复原问题转换成求边缘矩阵间的匹配度。 将实际问题转化成数学上的问题。本题是一个求组合优化的问题，本文的求 解方法一遗传算法的优化，全局搜索能力强，且有并行计算

41、功能。2. 优化的遗传算法与局部连续性原理连用，提取碎片边缘矩阵。可以减少算法的复朵度。与聚类方法想连用，对纵横切的情况下，可以大大减少碎片的数量，提 高算法的运行效率。6.2模型的缺点1. 优化的遗传算法可以很好的对有规则的碎片进行拼接，但当碎纸片的形状 发生变化时，该算法将受到制约。2. 遗传算法很容易出现早熟收敛，搜索性能不高，不易达到全局收敛；七、参考文献1张春玉，王冰，基于向量模的坐标变换不变性的碎片匹配方法J,计算 机工程与应用,2010,46(12):176-179o2 孙星明，殷建平，陈火旺等汉字的数学表达式研究J 计算机研究与发 展,2002,39(6):707-711.3

42、Liang Tiancai, Qiu Zhiwen, Pi Youguo. Simple gridbaseci on cognitive mechanism and application research on description for structure of Chinese charactercThe/26th Chinese Control Conference Zhangjiajie : IEEE Computer Society, 2007: 6896934 孙星明，殷建平，陈火旺等，汉字的数学表达式研究J.计算机研究与 发展,2002,39(6):707-7115 戴军，符

43、史流，赵韦人,BMP图像数据提取在分析测试中的应用，计 算机与应用化学,2006,23(9):889-891 o6 程森林，李松强,郝满炉，印制板打孔最短路径的遗传算法实现J,计算 机工程与应用,2006,30:180-182o7 茹少峰，周明全，基于轮廓线匹配的2-D碎片拼接研究J,计算机应用于 与软件，2008,25(3):83-85八、附录附录1clcclearclose allA=imread(000 BMP');%A(A-=255)=0;% imshow(A)n = 19;m=length(A);for i=l:nz (: f :zi)=zeros(mfl);endfor j

44、 = 1:nif j<llsl='001;s2 = num2str(j-1) ;s3=' BMP' elsesl='O's2=num2str(j-1) ;s3=1 BMP 1; endArB=imread (strcat (sifs2 r s 3);A(A=255)=0;%imshow(A)z (: f : f j ) =A (: f1);y(: z j ) =A (:, end)；i f sum(z(:, :r j)-2 5 5)=0first= first,j;endendarrange r DD=matchp(z,y,n,first);sho

45、w (n,arrange)arrange=arrange-l;function new_ar range f new_D =deal (zz n r Df arrange) xx=unique(arrange(:z1);new_D=D;new_arrange=arrange;while length (xx)> = n-1D=D + 0 01;arrange=matchp(z z yz n z D);xx = unique(arrange ( :z1);new_D=D;new_arrange = arr ange;endendfunction arrange rDD=matchp(z z

46、 yz nz first)i=first;%first pictureq=first; m=length(q);p= lzi-li + lzn ;DD = zeros(nz n);while m<nD=；for j =pyn = y：r i)；localy=find(yn=0);zn=z (: z : j );localz = find (zn = = 0);mx=max(length(localy)r length(localz);mi=length(setdiff(localy,localz);de=(mx-mi)/mx;D=Dz de;DD(i,j)=de;DD(j,i)=de;e

47、ndi=p(max (D)= = D);p = setdif f (p,i);q=q/i；m=length(q);endarrange=q;endfunction ar range=matchq(z A yz n z D) arrange=;re=;for i=n:-1:2zn=z(:,:ri);localz=find(zn=0);for j=i-l:-l:lyn = y ( :r :z j) ;localy=find(yn = = 0);mx=max(length(localz) r length (localy); mi = length ( setdiff (localz zlocaly

48、); degree= (mx-mi)/mx;if degree>Dre=i,j;arrange=arrange;re;endendendclcclearclose allA=imread(000 BMP');A(A = 2 5 5)=0;imshow(A)n=19;D=0;m=length(A);for i=l:nz (: f :zi)=zeros(mfl);endfor j =1:nif j<llsl= ' 001 ;s2 = num2str(j-1) ;s3=1 BMP 1;elsesl='01;s2=num2str(j-1) ;s3=1 BMP 1;e

49、ndAzB=imread(strcat (si,s2 r s 3);A(A=255)=0;%imshow(A)z (: f : f j )(: f1);y(:, :, j ) =A (:, end)；endar range=matchp(z z yz n,D);new_arrange,new_D=deal(z fyz Dz arrange);function show (nz arrange)A=imread(1000 BMP');(P/q=size(A)；picture = zeros(pz n*q);i = l；for j =arrangeif j<llsl='001

50、;s2 = num2str(j-1) ;s3=! BMP' elsesl='O's2=num2str(j-1) ;s3=1 BMP 1; endArB=imread(strcat (sifs2 r s 3);A(A=255)=0;picture ( :r (i-1) *q+l:i*q)=A;i=i+l;imshow(picture)endend附录2披下加丸古井”人巧天验，:iS®r.爲夜:乃亂枝萩衣巾芳爱电村禺林北卿匕午衣古砂黄松刃 A.；#吸浪由堆:應霸從芍匀乞萤向醵辺敢，小幣飪躍-爲处込=3曰堆更祚单鱼M叨脸.儿邯憔欷知自舍相从休务 日.何妨任跆.茨奧云

51、/性女bl圭电人孚，科 ®.備眼MH"豐，廉烟法R 茨携双於IJUB不旧黛.酬认门的域日为it我妙阳余好.从来白 y.少心蒲厲週心矶 江瞬与确北，何tftj 蚊不増行。ie.王.也鲁修云。ib恨耐欢，心事沏无隸闱槽妾如微见齐灰心軟白，自人* 一宣伶曙.凤花冻由白上饥f»«l油. 吟搖祈枚.0B*»aw»e,归就覚时动.略5处»» 中輒几弄。19. Sili9»£ 凭兄长空万里，去无18脈御 楼魄飞东灿.冷混一火歛亂M宇尿»«*去.人江谢< 山知汛*鹅历历省可iWttjr

52、aa.W»W!Wt«中n地 不;&鮒，文比etawa云厲般，共山有眼依无假，待u » 家屯目芳竹说相思.目斷石杠石.商很黃能耒th且活h夕 人闭今古.艺1M喝血観冰姿自ftti%.鸭他时邀戒. 盘芳色阿毛么几SS五施过矣，空说坊圍亲.5和吴迈报專址®王角有问，» >A) IMft王生曲银曲，«PU«R».密电逢畅作吃剜J報枕印，印祇廉阳叱阳也4技观炭衣哄牧饨可侧Bit财I日.不T会瓷列年。茱黄仔朗？牛祓足UWL三更月测札规I «&# 水 as.凭酯耳依归企、w»«

53、utsaijex imia«s融齿余轶也 这一乐 气昧irt从禺ttwmm-sa.»«»处， 叶娴績先.t茅僉出片.SP*®ttL谡tUfllWt远31.E力竹 力软.甩戏笛多情丄恣头.枕影規此i枕伤安紙旧不去.XttW . 01 tt.话发云廉存d佥萍花*LfeE.人fi«tLSl»Mx人伐矗九幷着賤爾赵梧直谁怜蕪子加88融M附录3fair of face.The customer is always riglit East,内屮 homes best. Life's not all beer and skittl

54、es. The devil looks after his own. Manners rnaketh man. Many a mwlde nukz a muckle A mnn who is his tnvn lawyer has» a fool for his client.You can't make a $i)k pure from a sow'y ear. A3 thick a5 thieve. Clothe make the man. All thAt glisters i6 not gold. The pen is irdgjitier thdn sword, b fAir and wise and gcod and gay. Mike Jove not wan Devil take the hindmost The female o