碎纸片的拼接复原(全国大学生数学建模大学国家级二等奖)

2013高教社杯全国大学生数学建模竞赛承诺书我们仔细阅读了《全国大学生数学建模竞赛章程》和《全国大学生数学建模竞赛参赛规则》（以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛网站下载）。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性。如有违反竞赛章程和参赛规则的行为，我们将受到严肃处理。我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。我们参赛选择的题号是（从A/B/C/D中选择一项填写）：B我们的参赛报名号为（如果赛区设置报名号的话）：13015所属学校（请填写完整的全名）：黑龙江八一农垦大学参赛队员(打印并签名)：1.周新臣2.周亚如3.史继男指导教师或指导教师组负责人(打印并签名)：徐艳日期：2013年9月16日赛区评阅编号（由赛区组委会评阅前进行编号）：2013高教社杯全国大学生数学建模竞赛编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：1B题：碎纸片的拼接复原摘要本文根据碎纸机破碎的纵切、横纵交错以及双面纸片的碎片文字特征，分别采用Hopfield网络法、遗传算法以及B-样条插值法建立了相应的数学模型，通过MATLAB、NetBeans等软件得出碎纸片正确的排列顺序，从而给出合理的碎片半自动拼接方法。对于问题一，即对于仅纵切的情形，我们首先将其分解成3个子问题：①对图像进行预处理；②对图像进行二值化处理；③将匹配的图像碎片拼接在一起。（1）在子问题①中，我们通过MALAB软件，分别对19张中、英文图片进行数字化处理，将其转化成数值在0-255之间的数字图像。（2）在子问题②中，采用Hopfield网络法，通过MALAB软件对已有的数字图像进行二值化处理，将其转化为0、1的数字图像。（3）在子问题③中，通过匹配算法找到相互匹配的图像，利用NetBeans软件编写程序得出正确的纸片排序，进而对碎片进行拼接。对于问题二，即对于既有纵切又有横切的情形，我们通过Sobel算子对图像碎片进行文字边缘提取，根据遗传算法得到最优逼近多边形的分界点为B-样条插值的控制点，得出碎片边缘文字的轮廓线的B-样条曲线，进而得到曲线的数学模型。通过计算每段曲线的曲率序列，利用动态时间规划的LCS算法得到最匹配的两个子序列，得到拼接的连接点，通过MALAB软件进行拼接。对于问题三，即双面打印的文件碎纸片拼接，对附件5中所给的数据运用MATLAB软件进行数字化处理，并得到BMP格式的数字图像。对得到的数字图像进行直方图均衡化处理，根据最大相关性原则，通过比较两幅图片的笔划走向趋势，得到匹配笔划最多的即为所求，循环此步骤，得到正确的纸片排序，最终借助MATLAB软件，实现对图片的拼接。本方法具有通用性，结合图像碎片的具体情况，可推广至其他领域，并根据其自身特点对碎片进行拼接复合，这对解决在考古研究、事故分析、工业自动装配等问题有很大帮助。关键词：碎纸片拼接；Hopfield网络；遗传算法；B-样条插值；MATLAB2一、问题重述在考古研究、事故分析、拼接游戏、工业自动装配等工作中经常需要把大量的物体碎片拼接成一个或几个完整的物体。在很多情况下，如果手工完成这些工作，不仅费时、费力，而且需要极大地耐性，还会对碎片造成二次损坏。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。建立相应的数学模型解决以下问题：1.对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，写出干预方式及干预的时间节点。2.对于碎纸机既纵切又横切的情形，设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，写出干预方式及干预的时间节点。3.上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果。二、问题分析2.1问题一的分析针对问题一，要将给定的来自同一页印刷文字的碎纸机破碎的纸片拼接复原，首先考虑将图像碎片进行预处理，即对图像碎片数字化，得到碎片的数字图像。其次将数字图像进行二值化处理，采用Hopfield网络法[6]，通过MATLAB软件实现这一过程。然后对图像碎片进行匹配，通过匹配算法找到相互匹配的图像碎片，建立相邻匹配最优化模型，利用NetBeans软件编写JAVA程序将相互匹配的图像碎片拼接在一起，得到最终的结果。2.2问题二的分析针对问题二，为有效的对碎纸机既纵切又横切的碎纸片进行拼接复原，由于碎纸机切割碎纸片边界比较整齐，所以考虑文字的特征。通过Sobel算子提取文字边缘，根据遗传算法获得B—样条插值[3]的控制点，计算每段曲线的曲率序列，利用动态时间规划的LCS算法得到最匹配的两个子序列，得到拼接点，利用MATLAB软件进行拼接。2.3问题三的分析针对问题三，为实现对双面打印文件的碎纸片的拼接，对附件5中所给的数据运用MATLAB软件进行数字化处理，并得到BMP格式的数字图像。然后对得到的数字图像进行直方图均衡化处理，在此基础上，再根据最大相关性原则，对比两幅图片的比划位置，得到得匹配比划最多的即为所求，循环此步骤，得到序列，最终借助MATLAB软件，实现对图片的拼接。3三、模型假设（1）假设微小误差可以忽略；（2）假设文字行与边界交点的个数相等；（3）假设连续匹配点间的距离误差可以忽略；（4）假设附件给出的图像碎片均真实有效。四、定义与符号说明符号说明i碎纸片二值化处理所得矩阵的行标j碎纸片二值化处理所得矩阵的列标m代表第m个矩阵n代表第n个矩阵𝑂𝑖𝑗原始图像𝐿𝑖𝑗二值图像𝑊𝑖𝑗矩阵平滑算子p平滑算子的归一化参数a逼近多边形的顶点数目C初始曲线B初始化染色体种群𝑆∗当前种群中最优的染色体g当前的遗传代数𝑔∗第一个找到最优染色体的遗传代数𝑁𝑖,s第i个子区间上的B样条函数𝑎𝑘第k个区间上的参数M模板矩阵g(𝑥,𝑦)直方图均衡化处理后的图像H(𝑘)累计概率函数K具体灰度级𝑓𝑘原始图像中第k级的灰度值P(𝑓𝑘)第k级灰度值在原始图像中所占的比例N原始图像的像素总个数𝑛𝑘原始图像中灰度值为k的像素个数Th图像的阈值4五、模型的建立与求解从所要解决的问题和对问题作出的假设出发，我们针对问题一、二、三、分别建立了模型Ⅰ：基于Hopfield网络模型；模型Ⅱ：相邻匹配最优化模型；模型Ⅲ：基于遗传算法及B-样条插值法模型；模型Ⅳ：基于文字特征的拼接模型。5.1问题一的建模及求解根据问题一的具体要求，本文将其分为三个步骤：（1）对图像碎片进行预处理，即对图像碎片数字化，得到碎片的数字图像。（2）采用Hopfield网络模型，通过MATLAB软件对图像进行二值化处理。（3）通过匹配算法找到相互匹配的图像碎片，建立相邻匹配最优化模型[1]，利用NetBeans软件编写JAVA程序将相互匹配的图像碎片拼接在一起。每一步骤具体求解过程如下：5.1.1对图像进行数字化处理图像数字化目的是将一幅图像以数字的形式进行表示，并且要做到既不失真又便于计算机进行处理。本文利用MATLAB软件对图像碎片进行数字化处理（具体程序详见附录），得到附件1与附件2中38张图像碎片的数字化处理结果。由于数据量较大，表1仅列出附件2中图片008的部分数字化结果（详细结果见附录）。表1部分数字化处理结果0142492552552552552552551510018525525525525525525542001072552552552552551880003025525525525525575000020725525525521613700012925525525510501450005225525523710122410001229255134010725535000152250261215255112000741630692552552040001478901032552552550001961302142552552550002550025525525525500025500255255255对碎片图像的数字化处理之后得到附件1与附件2中38张图片的矩阵。矩阵中边缘列数字全部为255的即为边缘图片，即矩阵中最左侧一列数字全部为255的图像碎片为原图像的最左侧碎片，矩阵中最右侧一列数字全部为255的图像碎片为原图像的最右侧碎片。55.1.2对图像进行二值化处理5.1.2.1模型Ⅰ的建立设𝑂𝑖𝑗(𝑖,𝑗=1,2,⋯𝑁)为原始图像，𝐿𝑖𝑗(𝑖,𝑗=1,2,⋯𝑁)为二值图像，则对原始图像进行二值化处理过程可转化为如下优化过程：min𝐿{∑∑[(𝑂𝑖𝑗−1𝑝∑∑𝑊𝑖;𝑚,𝑗;𝑘𝐿𝑚𝑘𝑁𝑘𝑁𝑚)2+(𝑂𝑚𝑎𝑥−𝐿𝑖𝑗)(𝐿𝑖𝑗−𝑂𝑚𝑖𝑛)]𝑁𝑗𝑁𝑖}(1)其中𝑂𝑚𝑎𝑥和𝑂𝑚𝑖𝑛分别是𝑂𝑖𝑗(𝑖,𝑗=1,2,⋯𝑁)中的最大值和最小值。𝑊𝑖𝑗(𝑖,𝑗=−𝑤0,−𝑤0+1,⋯0,1,⋯𝑤0−1,𝑤0)是确定的矩阵平滑算子，宽窗为2𝑤0×2𝑤0。𝑤0可根据原始图像的模糊程度选定。P定义为P=∑∑𝑊𝑖𝑗𝑤0𝑗;𝑤0𝑤0𝑖;𝑤0，它是平滑算子的归一化参数。由（1）式，二值化Hopfield网络的能量函数取作：E=∑∑[(𝑂𝑖𝑗−1𝑝∑∑𝑊𝑖;𝑚,𝑗;𝑘𝐿𝑚𝑘𝑁𝑘𝑁𝑚)2+𝐾(𝑂𝑚𝑎𝑥−𝐿𝑖𝑗)(𝐿𝑖𝑗−𝑂𝑚𝑖𝑛)]𝑁𝑗𝑁𝑖,(2)其中K为待定常数。将上式展开并整理有E=∑∑∑∑(1𝑝2∑∑𝑊𝑖;𝑚1,𝑗;𝑘1𝑊𝑖;𝑚2,𝑗;𝑘2𝑁𝑗𝑁𝑖)𝑁𝑘1≠𝑘2𝑁𝑘1𝑁𝑚1≠𝑚2𝑁𝑚1𝐿𝑚1,𝑘1𝐿𝑚2,𝑘2+∑∑*𝐾(𝑂𝑚𝑎𝑥+𝑂𝑚𝑖𝑛)−2𝑝∑∑𝑊𝑖;𝑚,𝑗;𝑘𝑂𝑖𝑗𝑁𝑗𝑁𝑖+𝐿𝑚𝑘−𝐾∑∑𝐿𝑚,𝑘2+𝐶𝑁𝑘𝑁𝑚𝑁𝑘𝑁𝑚,(3)经过代值化简处理得到该网络的动态方程C𝑑𝑈𝑚𝑘(𝑡)𝑑𝑡=∑∑𝑇𝑚𝑘,𝑚1𝑘1𝐿𝑚𝑘−𝑈𝑚𝑘(𝑡)𝑅𝑁𝑘𝑁𝑚+𝐼𝑚𝑘,𝐿𝑚𝑘(𝑡)=12(1+𝑡𝑎𝑛𝑕(𝜆𝑈𝑚𝑘(𝑡))(𝑂𝑚𝑎𝑥−𝑂𝑚𝑖𝑛)+𝑂𝑚𝑖𝑛),(4)原始图像以偏置电流的形式作为网络的输入，网络稳定后的输出即为所求的二值化图像，其中每个神经元的输出对应二值化图像的一个像素值。5.1.2.2模型Ⅰ的求解按照Hopfield网络法，通过MATLAB编程[2]得到经二值化处理后的图像数据，由于结果较大，正文只列出了部分二值化结果（见表2），详细结果在附件中给出。表2部分二值化处理结果0011111111001111111000111111100001111100000111110000011111010000111001000011101100001100111