Matlab在碎片拼接模型中的算法实现

《Matlab在碎片拼接模型中的算法实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、万方数据第26卷第1期2014年2月宁德师范学院学报(自然科学版)JournalofNingdeNormalUniversityfNan咖lScience)V01．26№．1Feb．2014Manab在碎片拼接模型中的算法实现宰林美芳，范培源，薛志民，陈省江(宁德师范学院数学系，福建宁德352100)摘要：针x,f2013年全国大学生数学建模竞赛B题，研究Matlab在规则文档碎片图像拼接复原中的算法设计与实现．关键词：Matlab；碎片拼接；数学建模中图分类号：0245文献标识码：A文章编号：2095．2481(2014)01-00

2、69．02破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用．传统的拼接复原工作需由人工完成，准确率较高，但效率很低，特别是当碎片数量巨大，人工拼接很难在短时间内完成任务．随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率．2013年全国大学生数学建模竞赛B题正是这样的背景下产生．本文主要针对2013年全国大学生数学建模竞赛B题，研究Matlab在规则文档碎片图像拼接复原中的算法设计与实现1单面纵切碎片拼接模型对原文档单面打印且被纵切成19条同样大小的碎纸条的情况f11，用(石，y

3、)表示19张碎片中任意两张，Y放置在菇的左边，设e(x，)，)为(髫，，，)的匹配度，建立单面纵切碎片向右拼接模型如下：模型1XO与帕向右拼接当且仅当right(xo，舶)：e(知，yo)=inf{e(xo，y)ly取遍非X0的18张碎片)．同理可以建立单面纵切碎片向左拼接模型如下：模型2Xo与Yo向左拼接当且仅当left(xo，如)=e(知，yo)=inf{e(xo，yo)k取遍非粕的18张碎片}．2单面纵切碎片拼接模型的算法设计与实现步骤1图像预处理圆用Maflab中的imread命令将全部图片转化为计算机可识别是数据，得到19个

4、1980"72的二维数据矩阵菇o，轧⋯，,X18；步骤2计算匹配度任取两种图片‰与yo，相应的数据矩阵也记为Xo与3"o，设矩阵xo的第l列和最后一列分别为戈口和茗6，矩阵如的第l列和最后一列分别为弘和拍，那么定义right(xo，yo)旬(xb，^ya)，left(xo，yo)--d(xa，yb)，其中d(a，b)=∑I妒6iI，Ⅱ=(％⋯，翰)7，b=ibl，．一，6。)j显然匹配度的值越小说／=1明匹配度越大．步骤3匹配算法131采用遍历搜索法，将全部碎片分为已标号和未标号两部分，分别用称为已标集E和未标集只首先根据左页边距固定

5、的特征，确定出第一张碎片轧则E=扛，】；然后，假设已经拼复了n张碎片，且按顺序依次放在指标集雎k1，．一，石J，固定碎片z。的右边列向量，遍历搜索未标集F，提取出收稿日期：2013—12—15作者简介：林美芳(1991一)，女，在读本科生，E—mail：454875546@qq．corn．通讯作者：陈省江(1984-)，男，讲师，E-mail：ehentrent@126．corn’基金项目：福建省大学生创新创业训练计划项目(No．2013103980005)万方数据·70·宁德师范学院学报(自然科学版)2014年2月所有未标碎片的最左

6、边列向量，逐一计算与碎片‰的最右边列向量的匹配度，匹配度最大者放入指标集，记为‰，．如果未标集F为空集，则算法结束．步骤4匹配算法的实现(1)图像处理程序段．先将【l】中的附件1下载到Matlab安装根目录下work文件夹，然后将图片重命名，按顺序从0到18，最后执行程序：fori：1：19imageName=strcat('E：LMATLAB7＼work＼附件1V,num2str(i一1)，，．bmp，)；％将B题附件1的图片读出a1(：，：，i)=imread(imageName)；％将读出的图片转化为数据，1980"72"19矩

7、阵end；datal=double(a1)；％将字符型矩阵a1转化为双精度型savedatal％将数据a1保存(2)确定最左边的图片，根据文档含有页边距的特征，编写程序如下：clc，clear；,％清屏，清除变量10addatal．mat％下载数据a---datal；％简化变量的书写order=-[]；．％将来用于存放图片的次序，这里要确定第1个数fori=1：19％在19张碎图片中循环d(i)=sum(sum(255-a(：，[1：51，i)))；％利用左边页边距均为空白的特征，空白值为255endorder(1)=find(d==

8、min(d))一1％d值最小者为所求的图片(3)确定匹配顺序：order(1)=order(1)+l；％因为附件1的图片编码从0开始，但程序编码从l开始pnow=order(1)；％pnow为指针位置p=zeros(1，