《2013年数学建模B题》由会员分享，可在线阅读，更多相关《2013年数学建模B题（41页珍藏版）》请在金锄头文库上搜索。
1、.word格式.摘要本文主要对碎纸片的拼接复原问题进行研究。在matlab软件中用imread()读取碎片数据，得到灰度矩阵，分别运用特征点配准、归一化互相关和adaboost算法，通过matlab软件编写程序，实现了碎纸机破碎纸片的拼接复原。针对问题一，首先（以附件1中的碎纸片为例）将19张碎纸片图像进行预处理，获取文件文字信息，然后利用计算机语言将碎片的文字问题转化成灰度问题，通过matlab编程比较两两碎纸片之间灰度值的大小，得出较完整的文字文件复原图。附件1的处理办法对附件2仍然适用。最后通过人工干预方式，将原程序进行优化，得到来自同一页印刷文件的碎纸片（仅纵切）拼接复原图。针对问题二
2、，首先根据图像预处理流程图，可以提取出附件3、附件4的图像特征点，依据图像特征点配准方法，引入相关系数来处理两两图片特征之间的关系，根据相关系数的大小得到两两组合的匹配对。然后通过分析结果，发现存在伪匹配对，采用归一化互相关方法对结果进行优化，运用Best- First搜索算法进行全局匹配，最后通过手动拼图对结果进行检验。针对问题三，根据附件5给出的是一页英文印刷文字双面打印文件的碎片数据，可以把双面的209张碎纸片看成单面打印的418张碎纸片。首先用matlab软件编写程序，可以从418张中把左边缘有明显空白特征的22张图片找出，将22张碎片拼成两列，分别以这两列为基准，然后把剩下的碎纸片运
3、用adaboost算法，对所给的图像边缘数据点的集合进行T轮筛选，得到初步的两张单面的碎纸片复原图。最后根据数据点位置的对应关系（如000a对应000b），通过人工干预的方式进行位置调整，得到附件5的一张双面拼接复原图。关键字：灰度值 特征点配准方法 Best-First搜索算法 adaboost算法 一、问题重述破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。请讨论以下问题
4、：1. 对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达（见【结果表达格式说明】）。2. 对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果表达要求同上。3.上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解
5、决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果，结果表达要求同上。【数据文件说明】(1) 每一附件为同一页纸的碎片数据。(2) 附件1、附件2为纵切碎片数据，每页纸被切为19条碎片。(3) 附件3、附件4为纵横切碎片数据，每页纸被切为1119个碎片。(4) 附件5为纵横切碎片数据，每页纸被切为1119个碎片，每个碎片有正反两面。该附件中每一碎片对应两个文件，共有21119个文件，例如，第一个碎片的两面分别对应文件000a、000b。【结果表达格式说明】复原图片放入附录中，表格表达格式如下：(1) 附件1、
6、附件2的结果：将碎片序号按复原后顺序填入119的表格；(2) 附件3、附件4的结果：将碎片序号按复原后顺序填入1119的表格；(3) 附件5的结果：将碎片序号按复原后顺序填入两个1119的表格；(4) 不能确定复原位置的碎片，可不填入上述表格，单独列表。二、问题分析2.1问题背景碎纸自动拼接技术是图像处理与模式识别领域中的一个较新但是很典型的应用，它是通过扫描和图像提取技术获取一组碎纸片的形状、颜色等信息，然后利用计算机进行相应的处理从而实现对这些碎纸片的拼接与还原。目前，在国际上德国等发达国家对破碎文件的自动修复技术已经进行了相当长时间的研究。而在国内，还没有类似的研究成果问世。因此，结合碎
7、纸片自动拼接在司法技术鉴定中的应用这一背景，把计算机视觉和识别模式结合起来，对未来拼接技术的发展具有重要意义。2.2问题一的分析为了将给定的来自同一页印刷文件的碎纸片（仅纵切）拼接复原，首先根据每张碎纸片的标号，运用排列组合算法，理论上计算出碎纸片的全部组合数。然后利用matlab软件编程，在一定的约束条件下，得出碎纸片（仅纵切）拼接复原图。 2.3问题二的分析要解决文件既被横切又被纵切的复原问题，需要在问题一的基础上进行解决。根据问题一可以发现图像特征点是解决碎纸片拼接复原的一项重要指标，基于图像的特征点配准方法，首先是要尽可能准确地提取出图像的特征点，然后用matlab软件对所得到的特征点
8、进行编程输入，得出每一张碎纸片的特征点所对应的灰度值，而后引入相关系数处理两两特征点的灰度值之间的关系，运用Best- First搜索算法进行全局匹配。2.4问题三的分析对于问题三，根据附件5给出的是一页英文印刷文字双面打印文件的碎片数据，为了简化拼接过程，可以把双面有内容的209片碎纸片看成单面打印的418片碎纸片。首先从418张中把左边缘有明显空白特征的22张图片找出，在问题一的基础上，将22张碎片拼成两列，分别以这两列为基准，然后把剩下的碎纸片利用adaboost算法，通过比较碎片权重的大小排出结果。排出结果后按照打印机打印原理将两部分进行比较，观察正反面上碎片的编码是否匹配（如000a
9、对应000b），若正反面上的编码不匹配，则通过人工干预的方式进行位置调整，最后得到附件5的双面拼接复原图。三、模型假设1.假设打印机状态良好，打印出正常文件；2.假设碎纸机切出的纸片轮廓清晰，边缘完整；3.假设忽略碎纸机工作时产生的细小误差；四、符号说明符号说明19种碎纸片全排列的总和分类器序列指示不等号方向的参数;表示特征的阈值表示特征值正样本数量负样本数量初始化样本权值误差估计五、模型建立与求解5.1模型一的建立与求解5.1.1模型的建立与求解要对给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切）进行复原与拼接，将给定的19张碎纸片进行全排列，得出多种排列，即：种。因为数据量太大，首先
10、对所给的碎纸片进行一次图像的预处理，预处理的目的是将碎纸片表示为适合于计算机进行处理的形式。流程图如下：图像获取分析图像信息的特征获取图像中的信息图1 图像预处理流程图通过运用matlab软件，利用计算机语言，如图1中-1代表白色即没有文字，图1中的图形表示为逗号，图2中的数字代表像素，255代表黑色。（具体见图1、2）图1. 局部计算机语言图图2.按灰度显示的部分数字化图形运用matlab软件编得程序（见附录一）得出较完整的排列顺序如下（见表1），得到碎纸片的文字复原图见图3：图3.比较完整的文字复原图由图3明显看出：得出的排列结果存在一定的误差，002号碎纸片所在位置不是最优的，需要将结果
11、进一步的优化。5.1.2模型的优化经过分析附录一中的程序（以中文为例）可知;根据PicData=Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8 Q9 Q10 Q11 Q12 Q13 Q14 Q15 Q16 Q17 Q18 Q19 ; % 中文排序。按排好的顺序输出会出现错位的现象，从而引入人为干预方式，将程序进行优化，通过观察的方式，手动将Q1与Q2的位置互换，即：PicData=Q2 Q1 Q3 Q19 Q4 Q5 Q6 Q7 Q8 Q9 Q10 Q11 Q12 Q13 Q14 Q15 Q16 Q17 Q18 Q19 ; % 中文排序。运行得到优化后的文字文件拼接复原图（见附录二），借由上面
12、中文程序出现的问题，通过人工干预的方式，手动将附件2的程序进行修改，运行出正确的图像及排列顺序（排列顺序和文件复原图见附录二）。5.2模型二的建立与求解5.2.1模型的建立与求解要解决文件既被横切又被纵切的复原问题，根据问题一中处理仅被纵向切割复原问题的方案，可以发现图像的特征是解决碎纸片拼接复原的一项重要指标，基于图像的特征点配准方法。首先是要尽可能准确地提取出图像的特征点，提取特征点的流程图如下（见图4）：输入图像观察检测边界提取特征点集特征点匹配图4.提取特征点的流程图运用matlab软件对所得到的特征点进行编程输入，得出每一张碎纸片的特征点所对应的灰度值。任意在待匹配图片中选一个图片，
13、以该图片特征点为中心，在剩余的待匹配图片中寻找对应匹配点，匹配的依据就是计算两幅待匹配图片特征点间的相关系数。因此引入相关系数，依据特征点邻域灰度值的互相关系数为匹配原则进行匹配。借助特征点匹配算法建立两两图片间的相关系数表达式： （其中，是相关系数，是相关度的大小，和分别为两幅待配准图像中特征点相关窗内像素的灰度值）1）根据上式，分别在参考图像和待配准图像中以每一个特征点为中心取一个大小的相关窗，然后以参考图像中的每个特征点为参考点在待配准图像中寻找对应匹配点。利用Matlab编取部分程序如下：clear alla=Qi Qj;%输入矩阵m,n=gray(a);fori=1:n forj=1
14、:n cc(:i-1)*n+j)=xcorr(a(:,i),a(:,j); end endend2） 由上述程序可解得两两图像间相关系数的最大值，在进行特征点匹配时可选取最大相关系数所对应的特征点作为该参考点的匹配点。5.2.2模型的优化经过对上述方法得出的结果的观察和分析，可以发现通过上述方法匹配之后的得到匹配对中仍存在伪匹配对，如何去除这些伪匹配对是整个图像配准的关键环节。因此，可以用归一化互相关的方法对上述模型进行优化。该方法同上述方法类似，只是在计算相关系数时进行了归一处理，建立归一化互相关模型：（其中和分别表示图像特征点灰度值的平均值）根据上述关系式，利用Matlab进行编程计算，得
15、到各匹配对间相关系数的大小，然后引入Best-First搜索算法进行全局匹配得到最后最优的结果。流程图5如下：输入两两组合的匹配按相关系数的大小排列匹配对最佳匹配对集合完整的复原图（最优解）图5 Best-First搜索算法流程图通过matlab软件编的程序得到如下结果（见表1）：表1 附件3的复原图表格049054065143186002157192178118190095011022129028091188141061019078067069099162096131079063116163072006177020052036168100076062142130041023147191050179120086195026001087018038
