2013年高教社杯全国一等奖论文碎纸片的拼接复原.pdf

2013 高教社杯全国大学生数学建模竞赛高教社杯全国大学生数学建模竞赛 承承 诺诺 书书 我们仔细阅读了全国大学生数学建模竞赛章程和全国大学生数学建模竞赛参 赛规则（以下简称为 “竞赛章程和参赛规则” ， 可从全国大学生数学建模竞赛网站下载） 。 我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网 上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。 我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或 其他公开的资料（包括网上查到的资料） ，必须按照规定的参考文献的表述方式在正文 引用处和参考文献中明确列出。 我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性。如有 违反竞赛章程和参赛规则的行为，我们将受到严肃处理。 我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展 示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等） 。 我们参赛选择的题号是（从a/b/c/d中选择一项填写） ： 我们的参赛报名号为（如果赛区设置报名号的话） ： b 所属学校（请填写完整的全名） ： 20007002 参赛队员 (打印并签名) ：1. 长沙理工大学 2. 赵然 3. 苗富 指导教师或指导教师组负责人 (打印并签名)： 罗迎迎 （论文纸质版与电子版中的以上信息必须一致，只是电子版中无需签名。以上内容 请仔细核对，提交后将不再允许做任何修改。如填写错误，论文可能被取消评奖资格。） 谭艳祥 日期： 2013 年 9 月 16 日 赛区评阅编号（由赛区组委会评阅前进行编号）： 2013 高教社杯全国大学生数学建模竞赛高教社杯全国大学生数学建模竞赛 编编 号号 专专 用用 页页 赛区评阅编号（由赛区组委会评阅前进行编号）： 赛区评阅记录（可供赛区评阅时使用）： 评 阅 人 评 分 备 注 全国统一编号（由赛区组委会送交全国前编号）： 全国评阅编号（由全国组委会评阅前进行编号） 1 碎纸片的拼接复原碎纸片的拼接复原 摘要 碎纸片的拼接复原在司法物证复原、 历史文献修复以及军事情报获取等领域都有着 重要的应用。考虑到本题均为规则形状的碎纸片拼接问题，本文建立了基于内容的拼接 模型，分别建立了基于 ostu 法的边缘识别，相关匹配模型，中英文不同的聚类模型以 及基于启发式遗传算法的优化拼接模型。 首先建立了基于 ostu 法分别识别了中英文字符高度和空白处的行高， 分别以中英 文字符的高度为主体， 行高为背景， 以最大类间差为目标函数， 找到目标与背景的边界， 以自适应阈值进行二值化。得到中文字符点阵的高度为 41，行高为 30，英文主体字符 点阵高度为 25，行高为 38. 针对问题一，建立相关匹配模型，以空白左边界为识别条件，确定起始页边面，将 起始页右边边界与剩余碎纸片集中所有纸片的左边界进行匹配， 以水平等位灰度误差和 为目标函数，将拼接成功的最小误差纸片记为新的起始页，依照该方法，利用 matlab 完全自动的实现完整的图片复原（耗时分别为：0.38s，0.43s） 。具体结果见附录一、二。 可执行的源程序代码见附件。 针对问题二，考虑到中英文字符的差异，建立不同的聚类算法。以文字行的对齐程 度为分类函数，分别将 209 个碎纸片聚类 11 类，每类包含 19 个元素，手工对聚类结果 进行微调，得到准确的聚类结果，然后采用问题一的相关匹配方法，得到较优解。建立 基于启发式遗传算法的优化模型，以较优解为初始种群，进行选择，交叉，变异，利用 matlab 编程经过若干次循环得到最优解，具体结果见附录三。可执行的源程序代码 见附件。 针对问题三，由于附件五中的未明确 a,b 面的正反面，无法直接进行匹配，但是由 于正反面也是一张纸的两面，因此两边有相同的行分割情况。即两者的剪动处在行上的 位置是一样因此再将 209 张将纸张进行分类时使用正反面参与计算， 以行高的拟合度来 进行行分类时，首先可以先选取 00a.bump-208a.bmp 的图片进行行分类，总共分为 11 类，每类有 19 张。由于聚类效果具有一定的误差，需要经过手动干预进行调节。最后 根据分类情况在全局四个方向上采用问题二中的英文排序算法，利用 matlab 编写相 应程序，在备选图片与目标图片进行匹配时，要同时计算正反两面的吻合度。具体结果 见附录四。可执行的源程序代码见附件。 关键字：关键字：ostu 法，相关匹配，聚类模型，遗传算法 2 一、一、 问题重述问题重述 破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重 要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当 碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图 开发碎纸片的自动拼接技术，以提高拼接复原效率。请讨论以下问题： 1. 对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切） ，建立碎纸片 拼接复原模型和算法，并针对附件 1、附件 2 给出的中、英文各一页文件的碎片数据进 行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结 果以图片形式及表格形式表达（见【结果表达格式说明】 ） 。 2. 对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附 件 3、附件 4 给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要 人工干预，请写出干预方式及干预的时间节点。复原结果表达要求同上。 3. 上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件 的碎纸片拼接复原问题需要解决。 附件 5 给出的是一页英文印刷文字双面打印文件的碎 片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件 5 的碎片数据给出拼 接复原结果，结果表达要求同上。 二、二、 问题分析问题分析 2.1 概论概论 文本文件的修复与拼接在日常生活中有着广泛应用。但目前碎纸片拼接工作多数依 赖手动。通常，对于不规则形状的二维碎纸片，可以根据碎片边缘的几何信息，如尖角 特征，面积特征，形状特征等，进行拼接。 本题一个规则形状的碎纸片拼接复原的问题，是图像处理与模式识别领域一个典型 问题，需要采取基于内容，即像素灰度值的的拼接方法。根据碎纸的边缘像素信息、纸 片内容的行数，行高及行的位置信息，纸片内容的纹理趋势等，相应地采取对应边缘的 优化拼接，行数、行高及行位置信息的匹配聚类等方法。使得尽可能的拼接契合。问题 3 的特点在于，不同的大小，语言内容的纸片包含了不同数量的特征信息。难点在于要针 对包含不同信息量的图像建立不同的聚类模型， 优化目标函数。 具体步骤包括。（见表 1） 表 1 碎纸片的拼接复原步骤 1）信息获取:图像特征信息提取。 2）预处理：对获取特征信息进行规范化等各种处理。 3）特征提取与选择：将识别样本构造成便于比较、分析的描述量即特征向量。 4）分类器设计：将训练样本提供的信息变为判别函数或优化目标函数。 5）图像拼接决策：对样本特征分量按判别函数的计算结果进行分类，拼接 注：对特征信息量较大的图像可以省略分类过程，直接进行图像拼接 三、三、 模型假设模型假设 1、 假设计算机软件读取的图像信息，即所得灰度数据真实可靠。 2、 假设每个文字所占网格均相同，即每个汉字横纵向所占的基准网格长宽相同。 3、 假设无论是纵切和横切不存在任何图像缺失和破损。 4、 假设文字边缘的渐进灰度值宽度大致相同。 5、 假设图像不存在一定的灰度失真和几何形变。 四、四、 符号说明符号说明 符号符号 符号说明符号说明 leftb_ 图像的左边界矩阵 rightb_ 图像的右边界矩阵 error 相关拼接函数 gradient 梯度顺序集 ),( 21 xxf 类间差 se 搜索集 efit 被选择概率 series 待排序集 4 五、五、 模型的建立与求解模型的建立与求解 5.1 5.1 模型的准备模型的准备 5.1.1 5.1.1 基于基于 ostuostu 法的行高，字符高度的确定法的行高，字符高度的确定 根据排版规则，每一张图片上的同种字符点阵都具有固定的行高和字符高度，且每 一行字符点阵的高度和行高均相等，且平行。因此首先确定纸张的行高和字符高度对后 文的字符识别及碎纸片分类具有重要意义。 首先将附件一 19 张碎纸片，不考虑顺寻直接拼接成一张完整图片（见图 1），得到 像素为 19801368 的图像，即一个 19801368 的矩阵，记为 w,并求其行和 p。 图 1 对于 w 矩阵，得到每一行和，其具体意义可理解为每一行像素点纵轴方向上投影的 叠加，即同一行的元素投影被叠加在一起。 由于同行的字符点阵高度及行高相同， 因为通过行高曲线的变化即可确定字符点阵 及行高的具体值。考虑到字符行高的边界处可能会有一些噪声，因此可以通过进行二值 化，即将图像上的像素点的灰度值设置为 0 或 255，也就是将整个图像呈现出明显的只 有黑和白的视觉效果。本文主要采用最大类间方差法（ostu 法）这种自适应阈值的二值 化处理方法，即将字符点阵高度设置为背景，行高设置为目标，阈值的设定尽可能使两 者之间的差异最大。 本文定义区别目标主体与背景的指标如下： 平均单位像素： 5 b m i i o m i i m xp m xp b o = = 1 1 )( )( 背景单位平均像素 目标单位平均像素 其中mmm bo =+，依次分别表示目标像素点的个数，背景像素点的个数和总像素 个数，p 表示各点的像素。 目标函数（平均单位像素之差尽可能大） ： )( )()()( ),( 21 ),(),0( 12 ),( 21 2121 xmx xpxp xx xp xxf mxi i xi i xxi i + + = 约束条件： mxx 21 0 即在固定像素范围内找到 x1，x2 的位置，从而确定阈值，进行二值 化。 （见图 2） 图 2 将所有得到的目标与背景，及字符点阵的高度与行高求平均值，最终得到中文字符 点阵的高度为 41，行高为 30，英文主体字符点阵高度为 25，行高为 38. 6 注：英文的主体字符表示如下红色阴影部分的行高： 5.25.2 问题一问题一 针对问题一，对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），一共 产生了 19 条破碎纸片，每条碎纸片的像素尺寸为 192072。通常对于切点两端的像素 点通常具有一定的相关性（见图 3）。 图 3 如图一所示，假设位于图像中央的的黑色竖线为图片切线，可以发现对于非文字或 字母边界处的水平、 竖直、 空白或者斜线中心附近切点的左右两边图片的像素灰度相同， 只有在文字或字母笔画的边缘（灰度渐变处）或者呈一定角度的笔画切点左右像素的灰 度会有一定的差别，因此建立相关匹配拼接模型，对于问题一是一种行之有效的解决策 略。具体步骤如下（见图 4）： 7 图4 问题一的算法步骤 5.2.1 5.2.1 数据获取数据获取 使用 matlab 读取图片。 在 matlab 中， 碎纸片以灰度图的形式存储， 按 256 阶灰度， 对应每一像素点介于白黑之间的等级。因此就问题一而言，本文首先得到了十九个 192072 的矩阵，矩阵的每个元素为 8 位的无符号整形数据，取值范围从 0 到 255。 5.2.2 5.2.2 特征提取特征提取 由问题一的分析，对于相邻的碎片，图像边缘的一列像素点具有一定的相似性，因 此分别提取 19 个碎纸片的左右边界，得到所有碎纸片左右边界矩阵: 左边界矩阵 ),.,(_ ;_,.,_,_ 192021 1921 iiii bbbleftb leftbleftbleftbleftb = = 其中矩阵leftb_的每一列向量对应着每一碎纸片的左边界特征向量。 右边界矩阵 ),.,(_ ;_,.,_,_ 192021 1921 iiii bbbrightb rightbrightbrightbrightb = = 其中矩阵rightb_的每一列向量对应着每一碎纸片的左边界特征向量。 5.2.3 5.2.3 相关匹配模型的建立与求解相关匹配模型的建立与求解 问题一基于灰度的相关匹配模型的思想是，首先根据边界特征向量所提供的信息， 识别整张图像最左边的起始纸片，记为 i。然后将剩余所有图像的左边界特征向量与 i 的右边特征向量进行误差比对，找到最合适的拼接图像，记为，按照此方法，依次用 剩余图像的左边界与上一图像的右边界进行匹配，最终拼接复原出完整图像。 一、起始纸片的确定一、起始纸片的确定 根据排版规则，由于起始纸片的左边一段一般会留白处理，因此该段对每一碎纸片 的左边提取 192010 的子矩阵，一个同样大小，记元素值均为 255 的矩阵为单位矩阵， 将该 19 个子矩阵与单位矩阵进行比较，其公式如下： 8 19e .19 .255101920 ),(),()( 10 1 1920 1 大误差。个矩阵与单位矩阵的最为 个碎纸片的子矩阵为 的单位矩阵、元素均为为 m i jiijimke ji k = = 找到 e 的最小值，该子矩阵 m 对应的的碎纸片即为起始纸片。 二、二、纸片的拼接纸片的拼接 在确定了起始纸片的位置之后，将起始纸片记为 i,开始对剩余的纸片依次进行拼 接。 首先建立被搜索集： 1821 ,.,sssse = 其中se表示剩余被搜索的纸片，其下标仅用于计数，并无图像实际序号。 然后根据已经提取的左右边界矩阵leftb_ ， rightb_，建立相关匹配拼接函数，其公 式如下： ）（1920,.,2 , 1)(_)(_)( )( 1 = = jjrightbjleftbjerror selength i isi 其中 i s leftb_表示剩余集se中 i s的左边界特征向量。 i rightb_表示起始纸片的右边界特征向量。 )(selength表示剩余集se的元素个数。 通过计算找到误差的最小值，即边界相似度最高的边缘，于是将找到的ses min 记 为 i,即为新的起始纸片，从而将ses min 从se中剔除，继续以上步骤进行拼接，直到 剩余集se为空集，此时表明拼接结束。 该过程可以实现全自动地拼接，得到原纸片。 5.2.4 5.2.4 模型的结果模型的结果 根据已建立的模型编写 matlab 程序进行求解，因为每一条中英文碎纸条边界的特 征向量包含 1920 个像素点，像素点数量足够多，对于非文字或字母边界处的水平、竖 直、空白或者斜线中心附近切点的左右两边图片的像素灰度相同，只有在文字或字母笔 画的边缘（灰度渐变处）或者呈一定角度的笔画切点左右像素的灰度会有一定的差别。 9 因此足够多的特征信息可以忽略后者误差的影响，无论是中文还是英文字符，实现动态 全自动的碎片拼接， 其结果如下(见表 2， 图 5， 图 6)。 本方法对于较大的碎纸片精度高， 速度快，且全自动，无需手动干预。 表表2 2 中文字符拼接结果中文字符拼接结果（程序运行时间（程序运行时间 0.38s0.38s） 位置序号 1 2 3 4 5 6 7 8 9 纸片序号 9 15 13 16 4 11 3 17 2 10 11 12 13 14 15 16 17 18 19 5 6 10 14 19 12 8 18 1 7 英文字符拼接结果英文字符拼接结果（程序（程序运行时间运行时间 0.43s0.43s） 位置序号 1 2 3 4 5 6 7 8 9 纸片序号 4 7 3 8 16 19 12 1 6 10 11 12 13 14 15 16 17 18 19 2 10 14 11 9 13 15 18 17 5 注： 纸片序号为编码序号， 对应纸片文件序号需-1， 例如纸片序号10= 009.bmp 。 图 5 中文全自动拼接过程图 图 6 英文全自动拼接过程图 5.3 5.3 问题二问题二 10 针对问题二， 根据附件 3,4 的中文图片， 同有 209 张碎纸片， 其尺寸信息为 18072 个像素点，与第一问不同，第二问的碎纸片是经由纵切及横切得到的，每块碎纸片所包 含的灰度像素信息大大减少，单纯按照第一问的边界匹配搜索效果较差，特别是英文字 符中的qpodca,等极为相似，因此单纯靠全局的边界搜索很难解决拼接问题。 观察碎纸片情况可以发现，同一行的纸片，再撕碎之后，无论是行高还是字符高度 都会高度平行，因此本文采用先聚类，后组类间拼接成行，再由行拼接成复原原图片的 策略。具体步骤如下（见图 7）： 图 7 问题二的算法步骤 其中值得注意的是，由于中文与英文字符的特点具有较大差异，因此需要制定不同 的聚类策略，具体参见模型的建立。 在聚类模型中，本文的分类策略将中文，英文字符各自分成 11 类，其中每类包含 19 个元素，即各自分成了十九行。 接着，本文进行行内配对，由于 18072 的碎纸片纵向仅包含 72 个边缘像素特征， 因此直接采用问题一的相关匹配模型误差较大，因此本文将该问题转化为以优化问题， 由于解空间较大，采用基于启发式遗传算法进行求解。最终得到拼接好顺序的行向量， 此时得到 11 个像素点总数为 1801368 行向量， 即其上下边界共包含 1368 个特征信息， 但考虑到横切可能全为空白格的特殊情形，因此启发式遗传算法再次进行优化，最终得 到拼接复原的原图。该方案采用由点到行，由行到面的渐进策略，觉有较好的条理性， 同时手动干预的次数较少，具有较高的实际价值和可移植性。 5.3.1 5.3.1 数据获取数据获取 11 使用 matlab 读取图片。 在 matlab 中， 碎纸片以灰度图的形式存储， 按 256 阶灰度， 对应每一像素点介于白黑之间的等级。因此就问题二而言，本文首先得到了 209 个 18072 的矩阵。 5.3.2 5.3.2 模型的建立模型的建立 一、一、中文字符聚类模型的建立与求解中文字符聚类模型的建立与求解 由于 209 个碎纸片是由纵切和横切形成的，对于横切的情形(以一特殊横切为例， 见图 8)。 v 图 8 横切图示例 根据排版的特点，中文汉字一般处于一个固定的点阵中。因此本文从行高，字符高 度，以及第一段空白行的位置等信息来聚类，使在处于同一行的元素可以归于一类。在 问题的准备中，我们已经得到了中文的字符高度为 41，行高为 30.经过仔细观察可以发 现如果两碎纸片同属于一行，那么只要由纸片的上方向下，第一行的文字完全对齐，那 么后面的文字行亦可对齐。 因此我们考虑建立由文字行到第一个完整中文字符的距离比 对。 这其中包括两种情形（见图 9，图 10）. 图 9 常规情形 情形一：均切到字或均未切到字，且 a，b 两块均非首行缩进碎纸片（如图 9 所示） h1 h2 12 因此可以直接通过匹配从纸张上边界到第一个完整字的距离实现行的匹配。 图 10 特殊情况 情形二：有一边或两边未切到字，左边为首行缩进碎纸片，右边正常（如图 10 所 示），此时我们可以发现左右两碎纸片到第一个完整中文字符的高度相等，均为 h2。 因此从这两种情形均可以通过测量到第一个完整字符的距离来实现。 而且由于行高 相同均为 30，因此只需一行平行，其他行也同时平行，不需要再继续检测。 对于每张碎纸片上行高和字高的确定， 采用模型的准备中提到的基于最大类间差法 （ostu 法来实现）。先按行像素点进行求和，其公式为： 再按照模型准备中的方法进行基于最大类间差法进行自适应的二值化， 从而较为精 确地确定边界情况。再计算每张碎片从上边界到第一个完整文字的距离。（见图 11）。 h1 h2 13 图 11 行像素求和及二值化图像 得到所有 209 张碎纸片的上边界到第一个完整文字的距离 h 后通过相似性检验， 来 聚类。根据得到的 209 距离 h，首先进行从大到小的排序。设得到的顺序集为： 20921 ,.,ererererror = 先计算误差梯度，得到误差梯度集（顺序相邻两元素之间的误差）： 20821 ,.,grgrgrgradient = 本文将 209 个碎纸片分成 11 类，每类 19 个元素，聚类的分类函数为： 类：表示第kk igrmin i k = 11 1 )(: 该分类函数找到了所有分类方式中使每一类的误差和最小。 该聚类方法主要利用了同行函数之间，行距的一致性，计算上边界到第一个完整文 字的距离，其中涉及到基于最大类间差法（ostu）的进行图像分割的算法。得到了分割 情况后，将具体的聚类问题转化为一个简单的优化问题，使得聚类方法的误差最小，从 而实现分类。该方法实现的全自动，无人工干预聚类，只需要在聚类结束后，对聚类结 果进行分析与检验。 二、二、英文字符聚类模型的建立英文字符聚类模型的建立 14 与中文字符不同，英文字符本身不具有整齐的排布规律，而使问题变得复杂。因此 英文字符的聚类方式与中文不同，具体而言以单词 pad 为例(见图 12）。 图 12 由图 12 可以看出，p 的下红线以下部分，d 的上红线以上部分均不是英文字符主体 行高（英文字符主体行高由模型准备中确定）的组成部分，因此需要编写新的算法来识 别英文字符真正的行高。 经过仔细观察不难发现图像的像素值在字符主体中的变化较大， 即像素波动方差较 大。以 pad 为例（见图 12） 图 12 从图中可直观的看出经过非主体的 0，6 直线的像素变化只有 1 次，经过主体的直 线 1,2,3,4,5 像素变化次数分别为 4,6,5,6,6，次因此可以直观地发现主体与非主体字 符之间像素变化频率有较大差异。 针对该种特异性，我们建立英文字符的聚类模型。 对于像素为 18072 的点阵信息，首先为了克服英文字符边界灰度的渐变性，因此 采用二值化处理： = 255, 1 255, 0 像素值 像素值 那么对于任意一幅点阵图的任意一行像素点可表示为： (.1,1.10,0,0,11,0.0,.) 定义每一行像素点的零子段数， 级像素点为 0 的个数， 因此按行计算成每个纸片 180 个零子段的个数（见图 13）。 15 图 13 图 14 经过观察，本文发现零子段是的个数近似于一个正态分布，因此我们根据 3 原则 进 行 切 割 ， 由p （ -x+ ） =68.3%p （ -2x+2 ） =95.4%p （-3x+3）=99.7%， 描述正态分布资料数据分布的离散程度， 越大， 数据分布越分散， 越小，数据分布越集中。根据此我们可以分割出主体字段的高度， 当 -x+ 时为主体宽度。（以图063.bmp为例，见图） 聚类方法与中文字符聚类方法相似，比较两图像到第一个完整主体英文字符的距 离。 三、三、基于启发式遗传算法的优化模型基于启发式遗传算法的优化模型 对于聚类模型得到的聚类结果，本文将其其转化为全局的优化模型，对于得到的经 过微调的完美聚类结果，首先采用问题一的相关边界匹配法得到一个较优解，然后建立 基于启发式遗传算法的优化模型进行求解。 得到聚类结果后，同一行有十几个碎纸片，将其拼接成一条的实质一个双向的 tsp 问题，需要找到一个左右边界相接的误差函数值就是相邻纸片的距离，因为左右相接的 误差是不同的，因此可以看做一个双向通路，且起点终点已知的双向 tsp 问题，且经过 同类中所有的纸片。 本文利用启发式遗传算法解决该问题。 （1）编码策略 本文采用实数编码，根据已经得到的次优解，将已经拼接复原成功的相邻纸片打 包， 生成待排序集：,., 21k seseseseries = ， 随机生成一个新的排列即为一个新解。 该顺序即为解的编码。 （2）目标函数 16 ）（1920,.,2 , 1)(_)(_)(:min )( 1 = = jjrightbjleftbjerror selength i isi 即按照该种排序方式，相邻两个碎纸片的边缘误差值最小。 （3）约束条件 生成的解排列内元素不重复。 （4）交叉策略 首先随机选取连个已得序列， 根据交叉概率确定是否交叉， 随机产生变异点位置 （以 序列 l1，l2 为例，见图 15）。 图 15 （5）变异策略 对于给点序列，首先根据变异概率确定是否变异，随机产生变异点个数，找到变异 点位置，与该序列中另一点互换，从而得到新序列。 （6）选择策略（轮盘选择） 首先根据目标函数确定适应度： 为被选择概率 的目标函数值为 )(ef )( )(/ )()( )(/1)( i ii iii ii xit xxobject xfxfxefit xobjectxf = = 目标函数值越小，被选择的概率越大。 17 经过以上若干代选择-交叉-变异可以得到最终的最优排序，即为最优解。遗传算法 步骤（见图 16）。 图 16 遗传算法流程图 以上算法只需对聚类结果进行手动微调，具有较好的自动性。 5.5.3 3. .3 3 模型的结果模型的结果 一、中文字符聚类结果 18 二、英文字符排序结果 三、中文拼接结果 中文的拼接结果 049 054 065 143 186 002 057 192 178 118 190 095 011 022 129 028 091 188 141 061 019 078 067 069 099 162 096 131 079 063 116 163 072 006 177 020 052 036 168 100 076 062 142 030 041 023 147 191 050 179 120 086 195 026 001 087 018 038 148 046 161 024 035 081 189 122 103 130 193 088 167 025 008 009 105 074 071 156 083 132 200 017 080 033 202 198 015 133 170 205 085 152 165 027 060 014 128 003 159 082 199 135 012 073 160 203 169 134 039 031 051 107 115 176 094 034 084 183 090 047 121 042 124 144 077 112 149 097 136 164 127 058 043 125 013 182 109 197 016 184 110 187 066 106 150 021 173 157 181 204 139 145 029 064 111 201 005 092 180 048 037 075 055 044 206 010 104 098 172 171 059 007 208 138 158 126 068 175 045 174 000 137 053 056 093 153 070 166 032 196 089 146 102 154 114 040 151 207 155 140 185 108 117 004 101 113 194 119 123 19 四、英文拼接结果 英文拼接结果 191 075 011 154 190 184 002 104 180 064 106 004 149 032 204 065 039 067 147 201 148 170 196 198 094 113 164 078 103 091 080 101 026 100 006 017 028 146 086 051 107 029 040 158 186 098 024 117 150 005 059 058 092 030 037 046 127 019 194 093 141 088 121 126 105 155 114 176 182 151 022 057 202 071 165 082 159 139 001 129 063 138 153 053 038 123 120 175 085 050 160 187 097 203 031 020 041 108 116 136 073 036 207 135 015 076 043 199 045 173 079 161 179 143 208 021 007 049 061 119 033 142 168 062 169 054 192 133 118 189 162 197 112 070 084 060 014 068 174 137 195 008 049 172 156 096 023 099 122 090 185 109 132 181 095 069 167 163 166 188 111 144 206 003 130 034 013 110 025 027 178 171 042 066 205 010 157 074 145 083 134 055 018 056 035 016 009 183 152 044 081 077 128 200 131 052 125 140 193 087 089 048 072 012 177 124 000 102 115 五、图像复原结果见附录三。 5.3 5.3 问题三问题三 由于附件五中无法明确正反两面的相对位置，而无法直接进行匹配，但是由于正反 面也是一张剪纸的两面，因此两边有相同的行分割情况。 即两者的剪动处在行上的位置是一样因此再将209张将纸张进行分类时使用正反面 参与计算，以行高来进行行分类时，对最后的分类效果是 没有影响的。 因此可以先选取 00a.bump-208a.bmp 的图片进行行分类， 总共分为 11 类，每类有 19 张。 其次，在对每一行中的 19 张进行列排序时，仅仅使用问题三种的英文排序算法即 可， 唯一不同的是， 在备选图片与目标图片进行匹配时， 要同时计算正反两面的吻合度， 若因此除了增加了 1 倍的计算量之外，其他的和问题二中没有什么区别。 最后，值得一提的是，由于后面的列排序是在航排序的基础上进行的，因此行排序 的效果与否将直接影响后面的结果。因此在使用分类算法进行分类时，应当适当引入人 工干预，以保持行分类的行分类的正确性。 具体的算法与步骤 step1，选取 00a.bump-208a.bmp 进行行分类。分成 11 类。 step2，对每一类，进行列排序。具体上就是对每类找出左边界片段，作为拼接的 起点，然后依次从剩下的纸张中（包括该类中的 a，b 两类图片）分别计算与目前的片 段进行边界像素点的取差的绝对值的和，选择最小的作为新的片段起点。直到拼接到长 度为 19. 20 step3，然后，从剩下的 19 个，按照 step2 的步骤进行。 step4，将 11 组行拼接完成之后，在计算这 11 张条形图片中，分别计算图片下边 的像素点，和剩下的图片的上边像素点，计算差的绝对值的和，取最小。 step5，检查图片,如果图片完整无缺，则结束，否则人工干预。 5.3.1 5.3.1 模型的求解模型的求解 利用 matlab 编写程序得到结果，源代码见附件！ 正面编码顺序表格： 136a 047b 020b 164a 081a 189a 029b 018a 108b 066b 110b 174a 183a 150b 155b 140b 125b 111a 078a 005b 152b 147b 060a 059b 014b 079b 144b 120a 022b 124a 192b 025a 044b 178b 076a 036b 010a 089b 143a 200a 086a 187a 131a 056a 138b 045b 137a 061a 094a 098b 121b 038b 030b 042a 084a 153b 186a 083b 039a 097b 175b 072a 093b 132a 087b 198a 181a 034b 156b 206a 173a 194a 169a 161b 011a 199a 090b 203a 162a 002b 139a 070a 041b 170a 151a 001a 166a 115a 065a 191b 037a 180b 149a 107b 088a 013b 024b 057b 142b 208b 064a 102a 017a 012b 028a 154a 197b 158b 058b 207b 116a 179a 184a 114b 035b 159b 073a 193a 163b 130b 021a 202b 053a 177a 016a 019a 092a 190a 050b 201b 031b 171a 146b 172b 122b 182a 040b 127b 188b 068a 008a 117a 167b 075a 063a 067b 046b 168b 157b 128b 195b 165a 105b 204a 141b 135a 027b 080a 001a 185b 176b 126a 074a 032b 069b 004b 077b 148a 085a 007a 003a 009a 145b 082a 205b 015a 101b 118a 129a 062b 052b 071a 033a 119b 160a 095b 051a 048b 133b 023a 054a 196a 112b 103b 055a 100a 106a 091b 049a 026a 113b 134b 104b 006b 123b 109b 096a 043b 099b 反面编码顺序表格： 078b 111b 125a 140a 155a 150a 183b 174b 110a 066a 108a 018b 029a 189b 081b 164b 020a 047a 136b 089a 010b 036a 076b 178a 044a 025b 192a 124b 022a 120b 144a 079a 014a 059a 060b 147a 152a 005a 186b 153a 084b 042b 030a 038a 121a 098a 094b 061b 137b 045a 138a 056b 131b 187b 086b 200b 143b 199b 011b 161a 169b 194b 173b 206b 156a 034a 181b 198b 087a 132b 093a 072b 175a 097a 039b 083a 088b 107a 149b 180a 037b 191a 065b 115b 166b 001b 151b 170b 041a 070b 139b 002a 162b 203b 090a 114a 184b 179b 116b 207a 058a 158a 197a 154b 028b 012a 017b 102b 064b 208a 142a 057a 024a 013a 146a 171b 031a 201a 050a 190b 092b 019b 016b 177b 053b 202a 021b 130a 163a 193b 073b 159a 035a 165b 195a 128a 157a 168a 046a 067a 063b 075b 167a 117b 008b 068b 188a 127a 040a 182b 122a 172a 003b 007b 085b 148b 077a 004a 069a 032a 074b 126b 176a 185a 000b 080b 027a 135b 141a 204b 105a 023b 133a 048a 051b 095a 160b 119a 033b 071b 052a 062a 129b 118b 101a 015b 205a 082b 145a 009b 099a 043a 096b 109a 123a 006a 104a 134a 113a 026b 049b 091a 106b 100b 055b 103a 112a 196b 054b 图像复原结果见附录 4. 21 六、模型评价六、模型评价 6.1 6.1 模型的优点模型的优点 第一，在建模中，我们创造性利用各个字体具有一致的行高这一特性，建立了 基于行高的行分类模型， 在行分类的基础之上， 在对问题进行分析可以使问题更加简便。 第二，在进行边界衔接匹配时，由于匹配时仅仅选择了最小的，因此没有考虑全局 最优，本文中利用遗传算法在原来排序的基础上，进行排序，可以更接近最优解。 第三，在短片段特征码较少匹配成功率低的情况下，创新性地运用字体宽度以及字 体间距的完整性大幅较少匹配次数，提高匹配精度，在中文拼接上非常接近最优解。 6.2 6.2 模型的缺点模型的缺点 在第二问的行分类算法， 由于汉字和英语单词本身的复杂性， 难以考虑完全的情况， 设计万能的算法，因此在行分类中不能实现全自动， 仍需要引入人工干扰。另外分类 后对同一行内较短的片段进行衔接匹配时，衔接匹配边较短导致彼此之间的特征太少， 匹配效果差。 6.3 6.3 模型的改进模型的改进 针对于当边界较短时，匹配的特征较少时，人们无法难以匹配。人们可以在除了挖 掘边缘像素点连续这一特性，还应当从图片边缘的斜率入手这样可以提高匹配的准确 度。在进行行分类时，可以结合列排序。 七、参考文献七、参考文献 1萧树铁.大学数学实验m.北京:高等教育出版社.1999. 2姜启源,谢金星,叶俊.数学模型m.北京:高等教育出版社.1987. 3薛山.matlab 基础教程m.北京:清华大学出版社.2011. 22 附录附录 附录一：附录一： 附件一、二复原后顺序表格附件一、二复原后顺序表格 中文字符拼接结果中文字符拼接结果（程序（程序运行时间运行时间 0.38s0.38s） 位置序号 1 2 3 4 5 6 7 8 9 纸片序号 9 15 13 16 4 11 3 17 2 10 11 12 13 14 15 16 17 18 19 5 6 10 14 19 12 8 18 1 7 英文字符拼接结果英文字符拼接结果（程序运行时间（程序运行时间 0.43s0.43s） 位置序号 1 2 3 4 5 6 7 8 9 纸片序号 4 7 3 8 16 19 12 1 6 10 11 12 13 14 15 16 17 18 19 2 10 14 11 9 13 15 18 17 5 注： 纸片序号为编码序号， 对应纸片文件序号需-1， 例如纸片序号10= 009.bmp 。 23 附录二：附录二： 附件附件 1 的结果：的结果： 24 附件附件 2 的结果：的结果： 25 附录三：附录三： 附件三复原后的顺序表格：附件三复原后的顺序表格： 中文的拼接结果 049 054 065 143 186 002 057 192 178 118 190 095 011 022 129 028 091 188 141 061 019 078 067 069 099 162 096 131 079 063 116 163 072 006 177 020 052 036 168 100 076 062 142 030 041 023 147 191 050 179 120 086 195 026 001 087 018 038 148 046 161 024 035 081 189 122 103 130 193 088 167 025 008 009 105 074 071 156 083 132 200 017 080 033 202 198 015 133 170 205 085 152 165 027 060 014 128 003 159 082 199 135 012 073 160 203 169 134 039 031 051 107 115 176 094 034 084 183 090 047 121 042 124 144 077 112 149 097 136 164 127 058 043 125 013 182 109 197 016 184 110 187 066 106 150 021 173 157 181 204 139 145 029 064 111 201 005 092 180 048 037 075 055 044 206 010 104 098 172 171 059 007 208 138 158 126 068 175 045 174 000 137 053 056 093 153 070 166 032 196 089 146 102 154 114 040 151 207 155 140 185 108 117 004 101 113 194 119 123 附件三的复原图像：附件三的复原图像： 26 附件四复原后的表格附件四复原后的表格 英文拼接结果 191 075 011 154 190 184 002 104 180 064 106 004 149 032 204 065 039 067 147 201 148 170 196 198 094 113 164 078 103 091 080 101 026 100 006 017 028 146 086 051 107 029 040 158 186 098 024 117 150 005 059 058 092 030 037 046 127 019 194 093 141 088 121 126 105 155 114 176 182 151 022 057 202 071 165 082 159 139 001 129 063 138 153 053 038 123 120 175 085 050 160 187 097 203 031 020 041 108 116 136 073 036 207 135 015 076 043 199 045 173 079 161 179 143 208 021 007 049 061 119 033 142 168 062 169 054 192 133 118 189 162 197 112 070 084 060 014 068 174 137 195 008 049 172 156 096 023 099 122 090 185 109 132 181 095 069 167 163 166 188 111 144 206 003 130 034 013 110 025 027 178 27 171 042 066 205 010 157 074 145 083 134 055 018 056 035 0