碎纸片的拼接复原论文

1、B、碎纸片的拼接复原摘要 碎纸片自动拼接技术是图像处理于模型识别领域中一个崭新但是很典型的应用，它是通过 扫描和图像提取技术获取一组碎纸片的形状、颜色等信息，然后利用计算机进行相应的处理过而实现对这些碎纸片的全自动或半自动拼接复原。1本文建立的模型是属于优化模型，通过对图像预处理，运用图像二值化（采用OTSU算法），边界提取配对法，matlab算法等方法进行碎纸片拼接处理。针对问题一，给定的来自同一页印刷文字文件的碎纸机仅纵切破碎的纸片，我们采用编程求解模型，其主要思想是:编写程序批量读取文件，在采用OTSU算法将每个图像二值化，在提取边界图像构成矩阵，运用边界配对法，再用matlab算法进行

2、求解。针对问题二，对于碎纸机既纵切又横切的碎纸片，先编写程序运用matlab算法及找出四个边界碎纸片，再利用matlab对其他碎纸片图像进行处理，获取文字行方向、高度、间距等文字行特征，最后编写程序用用matlab算法进行求解。针对问题三，对于双面英文切纵切又横切的碎纸片，我们要将a面b面双面进行研究对于同一图片我们需同时考虑两面边界值，然后再与问题二一样用matlab算法及人工干预找出四个边界碎纸片，再重复问题二的做法，就能实现双面图片的拼接。最后，我们在对结果进行分析的基础上说明了模型的优缺点，并对所建模型加以评价推广和改进，同时，进一步论述模型的实际意义。关键词：碎纸片，二值化，边界提取

3、配对，matlab算法一、问题重述1.1问题背景破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。1.2目标任务请讨论以下问题：1. 对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表

4、达（见【结果表达格式说明】）。2. 对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果表达要求同上。3. 上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果，结果表达要求同上。二、模型假设及符号说明2.1模型假设1、根据题意，假设碎纸机破碎纸片的字体是等高的，且破碎时是没

5、有损坏缺角的。2、假设题目所给的碎纸片在误差允许的范围内是有效的。3、假设计算机数字分析图像能力对碎纸片的处理是可行的。4、所有碎片上的文字的高度间距是一样的，行间距也是一样的。2.2 符号定义II【i】是指输入一到十九的矩阵。JJ【i】是指图片二值化之后得到的矩阵。C是指1到19副图各个矩阵首列之和三、问题分析对于文档纸碎片的拼接，常规一般使用碎片边界尖点特征、尖角特征、面积特征等几何特征特征，搜索与之匹配的相邻纸碎片并进行拼接。对于问题一由于在本题中所给的都为规则的碎纸片，所以将纸片先输入再进行二值化，得到图片的边界矩阵，调用一个matlab函数得到左边界全为1的图片，且此图片为文档的排头

6、。此时再重复调用一个matlab算法，根据像素最大配对原则便可以将两个图片拼接到一起，通过循环可以得到所有碎片拼接得出的图片。我们调用这个函数function c=cout0(a,b)t=size(a);c=0;for i=1:t if(abs(a(i)=b(i) 进行边界配对。（1为白，0为黑） c=c+1; 可以得到于某一张图还配对的左边的图片。同理可得出所有图片的与其配对的左边的图片，也就可以轻易得出图片的顺序，再用得出的顺序编写程序，运用matlab算法进行拼接复原，此问题就可得到解决。对于问题二 ，相对一复杂多了，我们先将图像输入再进行二值化处理，调用matlab算法及人工干预可得到

7、位于左上角第一个图片，然后在套用问题一中的matlab算法，得出所有可能位于第一列的图片，然后以左上角第一个图片为匹配基点，以此得出与其配对的图片，依次下去，就可以得出所有位于第一列的图片，继续运用matlab算法进行行匹配，就可得到所有图片的顺序，再用得出的顺序编写程序，运用matlab算法进行拼接复原，此问题也将得到解决。对于问题三，在二的基础上再加增加两个for循环，即再a面像素点的情况下还要考虑b面的。调用matlab算法对000a.bmp到208a.bmp和000b.bmp到208b.bmp输入并对其二值化，同时用matlab算法输出他们的边界矩阵，再第二问的程序下秩序同时满足a，b

8、 就能解决问题了。四、问题的模型建立及求解问题一：先对附件一和附件二中的图片重命名（将图片名的前置0都删去），并将图片的存放途径改为C:Documents and SettingsAdministrator桌面B附件1。然后再在用matlab软件批量读取文件，并存为（II）然后用再采用OTSU算法将每个图像二值化并储存在JJ中，再提取每个二值化图像后即（JJ）的边界，将边界构成边界矩阵。在边界矩阵中找到左边界相加的值为1980的图片，此图就为附件一的排头图片（程序详情见附录程序一）。再在matlab软件中输入附录程序二 可得出第一幅图与余下几幅图的右边界匹配度最大的那幅图。同理我们可通过附录程

9、序二可得：0.bmp的左边为17 2.bmp的左边为16.bmp 3.bmp的左边为15.bmp。 4.bmp的左边为1.bmp。 5.bmp的左边为4.bmp。 6.bmp的左边为0.bmp。 7.bmp的左边为11.bmp。 8.bmp为排头 9.bmp的左边为5.bmp。 10.bmp的左边为3.bmp。 11.bmp的左边为18.bmp。 12.bmp的左边为14.bmp。 13.bmp的左边为9.bmp。 14.bmp的左边为8.bmp。 15.bmp的左边为12.bmp。 16.bmp的左边为2.bmp。17.bmp的左边为7.bmp。 18.bmp的左边为13.bmp。8.bmp

10、为排头，以8.bmp为基准和由matlab程序运行出来得到的数据再经过人工处理可得碎纸顺序为8141215310216145913181171706。用表格为：8141215310216145913181171706然后通过imread（详情见附录程序三）语句按其顺序输出，就能得到我们所想要拼接的图片。对于附录二中的图片可套用一种的所有方法，然后改变对应图片粗村位置，将图片存放到c:program FilesMATLABR2007bwork。并将原来附件一中的图片移除。我们可以容易的知道它的碎纸顺序：3627151811051913108121417164同理可用imred语句按顺序输出，就能

11、得到我们想要拼接的图片问题二：1.对于附件三给定209张图片，我们先将图片重新命名（将图片名的前置0都删去）再通过C:Documents and SettingsAdministrator 桌面B附件3途径存放起来。在matlab中输入以下程序读取图片并将其二值化（采用OTSU算法（详情见附录程序表四）并用循环嵌套方式来输出上界和左边界上的所有矩阵值均为1的图片号。通过可知第15,30,50,63,72,90,126,136,144,169副图均可能是在第一个方格上。但由于在一格只有一张图片，此时程序无法准确的得出答案，所以需要人工干预。通过人工干预可以知道第五十副图在第一排第一列（即49.b

12、mp）。然后再输入附录程序五，以获取边界都为一的图片。得到十六个左边界都为一的图片7.bmp14.bmp29.bmp49.bmp61.bmp62.bmp67.bmp71.bmp80.bmp89.bmp94.bmp125.bmp135.bmp143.bmp168.bmp38.bmp我们分别这十六个图片二值化，输出它的上下边界矩阵，此时我们将范围缩小至十六，则可以开始与49bmp开始匹配，在matlab上输入程序达到匹配（详情见附录程序六）以得到能与49.bmp相匹配的图片。可得出49.bmp下面为61.bmp。同理可得：61.bmp下面为168.bmp下面为38.bmp下面为71.bmp下面14

13、.bmp下面为94.Bmp下面为125.bmp下面为29.bmp下面为7.bmp下面为89.bmp.在matlab中输入附录程序六：将forj=1:209 b=sum(ABj(:,1); if(b=180) j改为 for i=1:209 a=sum(ABi(1,:);if(a=72) i然后重复5操作可得第一行的序码为：同理可得碎纸片的拼接碎纸表：4954651431862571921781181909511221292891188141611978676999162961317963116163726177205236168100766214230412314719150179120861

14、952618718381484616124352118912210313019388167258910574711562313220017803320219815133170205851521652760141283159821991351273160203169134393151107115176943484183904712142124144771121499713616412758431251318210919716184110187661061502117315718120413914529641112015921804837755544206101049817217159720813

15、815812668175451740137535693153701663219689146102154114401512071551401851081174101113194119123 根据图片上的排序我们就能将碎片拼成图片同时英文版的可按照上面的方法得出序列号，序列号为：191751115419018421041806410641493220465396714720114817019619894113164781039120101261006172814626511072940158186982411715055958923037461271919493141881211261051551

16、141761821512257202711658215913911296313815353381231201758550160187972033120411081161367336207135157643199451737916117914320821749611193314216862169541921331181891621971127084601468174137195849172156962399122901851091321819569167163166188111144206313034131102527178171426620510157741458313455185635169

17、18315244817712820013152125140193878948721217712401021153、问题三的模型建立与求解：先对图片名进行修改即将前缀0 去掉，先将图片批量输入，再将图片二值化，载依次输出它们的像素值，直接输入算法（详情见附录程序七）得到图片的序号值。五、模型优缺点及改进解决此问题模型算法，通过编写程序，运用Matlab算法在加上必要的人工干预进行碎纸片的拼接复原，这种半自动拼接方法综合利用了计算机高速计算能力以及人的文字图像识别和理解能力，拼接效率比纯人工高，拼接准确性也好于纯计算拼接法。【2】在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。

18、但此类拼接复原碎纸片模型算法还是存在缺陷的，程序代码没有循环效果，需要多次修改重复运行，工作量大。操作起来有一些困难，我们在今后的学习中会继续的研究，希望编写出能够循环的程序语句，减少繁杂的操作。为今后此类对碎纸片拼接复原方法的推广使用做出重要意义。. 六、参考文献1贾海燕，碎纸自动拼接关键技术研究，工学硕士学位论文，2005.112罗智中，基于文字特征的文档碎纸片半自动拼接，2012.05.063陶波、于志伟、郑筱祥、图像的自动拼接J、中国生物医学工程报。1997,16（4）：29-354钟家强、王润生、基于边缘的图像配准改进算法J。计算机工程与科学.2001.23(6):25-29. 七、

19、附录一、附件一恢复所得图片为： 二、附件二恢复所得图片为：三、附件三恢复所的图片为： 四、附件四恢复所的图片为：五、附件五恢复所得图片为：本题一直使用的是matlab软件。附录程序一：II=cell(1,19);for i=1:19imageName=strcat(C:Documents and SettingsAdministrator桌面B附件1,num2str(i-1),.bmp);IIi = imread(imageName);endJJ=cell(1,19);for i=1:19th=graythresh(IIi); JJi=im2bw(IIi,th); end Ji=JJ1(:,1

20、) JJ1(:,72) JJ2(:,1) JJ2(:,72) JJ3(:,1) JJ3(:,72) JJ4(:,1) JJ4(:,72) JJ5(:,1) JJ5(:,72) JJ6(:,1) JJ6(:,72) JJ7(:,1) JJ7(:,72) JJ8(:,1) JJ8(:,72) JJ9(:,1) JJ9(:,72) JJ10(:,1) JJ10(:,72);Ji1=JJ11(:,1) JJ11(:,72) JJ12(:,1) JJ12(:,72) JJ13(:,1) JJ13(:,72) JJ14(:,1) JJ14(:,72) JJ15(:,1) JJ15(:,72) JJ16(:

21、,1) JJ16(:,72) JJ17(:,1) JJ17(:,72) JJ18(:,1) JJ18(:,72) JJ19(:,1) JJ19(:,72);Jii=Ji Ji1;for j=1:19C=sum(JJj(:,1)if(C=1980)jendend附录程序二：II=cell(1,19);for i=1:19imageName=strcat(C:Documents and SettingsAdministrator桌面B附件1,num2str(i-1),.bmp);IIi = imread(imageName);endJJ=cell(1,19);for i=1:19th=grayth

22、resh(IIi); JJi=im2bw(IIi,th); end Ji=JJ1(:,1) JJ1(:,72) JJ2(:,1) JJ2(:,72) JJ3(:,1) JJ3(:,72) JJ4(:,1) JJ4(:,72) JJ5(:,1) JJ5(:,72) JJ6(:,1) JJ6(:,72) JJ7(:,1) JJ7(:,72) JJ8(:,1) JJ8(:,72) JJ9(:,1) JJ9(:,72) JJ10(:,1) JJ10(:,72);Ji1=JJ11(:,1) JJ11(:,72) JJ12(:,1) JJ12(:,72) JJ13(:,1) JJ13(:,72) JJ14

23、(:,1) JJ14(:,72) JJ15(:,1) JJ15(:,72) JJ16(:,1) JJ16(:,72) JJ17(:,1) JJ17(:,72) JJ18(:,1) JJ18(:,72) JJ19(:,1) JJ19(:,72);Jii=Ji Ji1; c=zeros(1,19);for i=1:18I17=imread(17.bmp);I18=imread(0.bmp);I19=imread(6.bmp);I=I1,I2,I3,I4,I5,I6,I7,I8,I9,I10,I11,I12,I13,I14,I15,I16,I17,I18,I19;imshow(I)c(i)=cout

24、0(Jii(:,1),Jii(:,2*i+2);endC,I = max(c)再创建m-file此文件： function c=cout0(a,b)t=size(a);c=0;for i=1:t if(abs(a(i)=b(i) c=c+1; endend附录程序三：I1=imread(8.bmp);I2=imread(14.bmp);I3=imread(12.bmp);I4=imread(15.bmp);I5=imread(3.bmp);I6=imread(10.bmp);I7=imread(2.bmp);I8=imread(16.bmp);I9=imread(1.bmp);I10=imre

25、ad(4.bmp);I11=imread(5.bmp);I12=imread(9.bmp);I13=imread(13.bmp);I14=imread(18.bmp);I15=imread(11.bmp);I16=imread(7.bmp);I17=imread(17.bmp);I18=imread(0.bmp);I19=imread(6.bmp);I=I1,I2,I3,I4,I5,I6,I7,I8,I9,I10,I11,I12,I13,I14,I15,I16,I17,I18,I19;imshow(I)附件程序四：clcAA=cell(1,209);for i=1:209imageName=s

26、trcat(C:Documents and SettingsAdministrator桌面B附件3,num2str(i-1),.bmp);AAi=imread(imageName);endAB=cell(1,209);%将每个图像二值化储存为ABfor i=1:209th=graythresh(AAi);ABi=im2bw(AAi,th);endfor j=1:209 a=sum(ABj(1,:);%利用循环将j图片的上界矩阵值相加 b=sum(ABj(:,1); %利用循环将j图片的左边界矩阵值相加 if(a=72&b=180) j %输出上界和左边界矩阵值均为1的图片号 endend附录程

27、序五： clcAA=cell(1,209);fori=1:209imageName=strcat(C:DocumentsandSettingsAdministrator桌面B附件3,num2str(i-1),.bmp);AAi=imread(imageName);endAB=cell(1,209);fori=1:209th=graythresh(AAi);ABi=im2bw(AAi,th);endforj=1:209b=sum(ABj(:,1);if(b=180)jendend附录程序六： clcAA=cell(1,209);for i=1:209imageName=strcat(C:Docu

28、ments and SettingsAdministratorB3,num2str(i-1),.bmp);AAi=imread(imageName);endAB=cell(1,209);for i=1:209th=graythresh(AAi);ABi=im2bw(AAi,th);endAI=AA7(1,:) AA7(180,:) AA14(1,:) AA14(180,:) AA29(1,:) AA29(180,:) AA38(1,:) AA38(180,:) AA49(1,:) AA49(180,:) AA61(1,:) AA61(180,:);AI1=AA62(1,:) AA62(180,

29、:) AA67(1,:) AA67(180,:) AA71(1,:) AA71(180,:) AA80(1,:) AA80(180,:) AA89(1,:) AA89(180,:) AA94(1,:) AA94(180,:) AA125(1,:) AA125(180,:) AA135(1,:) AA135(180,:) AA143(1,:) AA143(180,:) AA168(1,:) AA168(180,:);AII=AI AI1;c=zeros(1,16);for i=1:16 c(i)=cout5(Jii(:,1),Jii(:,2*i+2);endC,I = max(c)并创一个fil

30、e文件存放命令：function c=cout1(a,b)t=size(a);1=5;for i=1:t if(abs(a(i)=b(i) c=c+1; endend程序附录七clear; I=imread(xingshi32.bmp); if(isgray(I)=0) disp(请输入灰度图像,本程序用来处理128 *128的灰度图像!); else if (size(I)=128,128) disp(图像的大小不合程序要求!); else H.color=1 1 1; %设置白的画布 figure(H);imshow(I); title(原图像); zeroImage=repmat(uin

31、t8(0),128 128); figure(H); %为分裂合并后显示的图设置画布 meansImageHandle=imshow(zeroImage); title(块均值图像); %设置分裂后图像的大小由于本图采用了128像素的图 blockSize=128 64 32 16 8 4 2; %设置一个S稀疏矩阵用于四叉树分解后存诸数据 S=uint8(128); S(128,128)=0; threshold=input(请输入分裂的阈值(0-1):);%阈值 threshold=round(255*threshold); M=128;dim=128; % 分裂主程序% while (dim1) M,N = size(I); Sind = find(S = dim); n