下载文档原格式
碎纸片的拼接复原 2013全国数学建模竞赛——碎纸片拼接复原导读：就爱阅读网友为您分享以下“2013全国数学建模竞赛——碎纸片拼接复原”的资讯，希望对您有所帮助，感谢您对的支持!2013高教社杯全国大学生数学建模竞赛重庆工商大学姜木北小组作品编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）碎纸片的拼接复原摘要目前，“碎片拼接复原”技术在司法物证复原、历史文物修复及社会生活各项领域扮演着重要角色，对于碎片数量特别巨大而人工又难以在短时间内完成碎片拼接时，要找到一种高效快捷的自动拼接方法已变得尤为重要。
本文针对只有中英文的碎片拼接问题，综合分析了从单一的纵切到纵横切以及纵横切双面碎片这三个不同的情况，提出了碎片拼接复原的解决方案.在问题一中，对于仅有“纵切”且数量相对较少的碎纸片，我们基于边缘去噪和采用构建碎纸图片的左右边缘二值矩阵提取相似度分析的方法，再通过两张图片左右相似度匹配排序，得到附件1和附件2中的碎纸排序（见表2和表3），并运用Matlab的图像处理工具箱，按排列顺序导入碎纸片得到相应拼接结果（见附录附件一）.在问题二中，由于碎纸片数量相对较多，同时存在横切和纵切的情况，在问题一的基础上增加了碎纸片的上下边缘相似度匹配。
在进行人工干预，找到第一张起始碎纸片作为匹配起点后，我们基于索贝尔算子的原理，对碎纸片灰度值进行边缘相似度的旋转检测和比较匹配，最后进行二叉树搜索排序（见表4和表5）。
对附件3和4的碎纸图片拼接出的结果详见附录中的附件二.在问题三中，由于碎纸片是两面的并且碎纸片数量更多，若采用第二问的求解方案则加大了求解难度同时也存在较大误差。
因此，我们基于蚁群算法（ACA）的SIFT特征点匹配原理来求解。
先提取碎纸图片特征点，然后基于蚁群算法的最优化快速比对匹配，最后基于ACA的搜索排序对碎纸片拼接。
2013高教社杯全国大学生数学建模竞赛B题碎纸片的拼接复原首先分析问题：对于第一问分析如下对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。
如果复原过程需要人工干预，请写出干预方式及干预的时间节点。
求matlab图像拼接程序clear;I=imread('xingshi32.bmp');if(isgray(I)==0)disp('请输入灰度图像,本程序用来处理128 *128的灰度图像!');elseif (size(I)~=[128,128])disp('图像的大小不合程序要求!');elseH.color=[1 1 1]; %设置白的画布figure(H);imshow(I);title('原图像');zeroImage=repmat(uint8(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 (dim>1)[M,N] = size(I);Sind = find(S == dim);numBlocks = length(Sind);if (numBlocks == 0)%已完成break;endrows = (0:dim-1)';cols = 0:M:(dim-1)*M;rows = rows(:,ones(1,dim));cols = cols(ones(dim,1),:);ind = rows + cols;ind = ind(:);tmp = repmat(Sind', length(ind), 1);ind = ind(:, ones(1,numBlocks));ind = ind + tmp;blockValues= I(ind);blockValues = reshape(blockValues, [dim dim numBlocks]);if(isempty(Sind))%已完成break;end[i,j]=find(S);set(meansImageHandle,'CData',ComputeMeans(I,S));maxValues=max(max(blockValues,[],1),[],2);minValues=min(min(blockValues,[],1),[],2);doSplit=(double(maxValues)-double(minValues))>threshold;dim=dim/2;Sind=Sind(doSplit);Sind=[Sind;Sind+dim;(Sind+M*dim);(Sind+(M+1)*dim)];S(Sind)=dim;end对于第二问于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。
碎纸片的拼接复原摘要碎纸片的拼接复原是一门借助计算机，把大量碎纸片重新拼接成初始纸张的技术。
针对问题一，本文首先利用碎纸片图像灰度矩阵的边缘矩阵，建立了两个碎纸片之间的匹配度函数，求得了每一张图片之间左右边缘匹配度矩阵。
然后根据左边边缘位置的碎片的左边空白部分最多的特点，确定了左边位置的碎纸片。
接着根据拼接碎纸片的拼接复原时，所有碎纸片匹配度之和取极大值的原则，采用贪心算法，得到了所有碎纸片的初始位置，拼接复原了附件1和附件2中纸片。
针对问题二，由于附件3碎片数量太多，并且碎片的拼接复原，是一个以碎纸片总匹配度为目标函数的组合优化问题。
所以本文采用遗传算法将碎纸片的编号作为基因，并将基因均匀分成19段，按顺序每一段对应一个初始纸片列位置，进行了求解。
然后，根据边缘碎纸片某些边的空白部分多的特征，对初始基因进行了优化。
接着，根据碎纸片的黑色像素密度不同的特点，将碎纸片分成三类，根据同类纸片优先匹配的原则，对遗传算法的运行过程进行了优化，拼接复原了附件3和附件4中纸片。
针对问题三，随着碎纸片量的增多，计算量急剧增加。
在上述拼接复原碎纸片的基础上，又引进了同行位置碎纸片的上部（或下部）空白位置宽度相近的聚类思想。
先对每个类内部拼接，在合并所有类并做一次整体拼接。
由于时间有限，我们未能完成最后一次的整体的拼接，但我们会在比赛后继续探究。
关键词：边缘矩阵匹配度函数遗传算法聚类一、问题重述碎片拼接实际用途已经越来越广泛，传统上拼接复原工作由人工完成，碎片拼接的准确率较高，但效率很低。
并且当碎片数量很大时，人工短时间内拼接出来几乎是不可能的。
所以开发碎纸的拼接技术，以提高拼接复原效率已成为越来越多人的期望。
现在,在碎纸片是规则的情况下，题目要求我们在以下条件建立碎纸片拼接复原模型和算法。
1.来自同一页印刷文字文件（中文、英文各一页）的碎纸机破碎纸片（仅纵切）拼接复原，并将附件1和附件2复原。
2.对碎纸机既纵切又横切文件的情形，将碎纸片拼接完整。
碎纸片的拼接复原模型
邓方清;邓小安
【期刊名称】《数学学习与研究：教研版》
【年(卷),期】2016(000)022
【摘要】针对碎纸片的拼接复原问题,本文从边缘像素矩阵入手,通过对该矩阵数据的标准化处理、求取像素平均值、定义像素255的频率、矩阵分块等方法,运用相关的匹配度算法分析,建立了纵切又横切的碎片拼接复原模型.
【总页数】2页(P154-155)
【作者】邓方清;邓小安
【作者单位】[1]广东工业大学,广东广州510006;[2]广东石油化工学院,广东茂名525000
【正文语种】中文
【中图分类】TP391.41
【相关文献】
1.基于数字图像的碎纸复原模型与算法--2013年全国大学生数学建模B题碎纸片的拼接复原问题
2.碎纸片的拼接复原模型及其算法研究
3.基于线性规划的碎纸片拼接复原模型
4.TSP规划模型在文本碎纸片拼接复原问题中的应用
5.基于聚类分析与欧氏距离模型的碎纸片拼接复原
因版权原因，仅展示原文概要，查看原文内容请购买。
数学建模中的碎纸片拼接复原要点研究基于模拟退火算法与系统聚类法，文章首先依次介绍了仅纵切、既有横切又有纵切、双面打印三种情形下的碎纸片拼接复原要点，然后对全文进行了总结与展望。
标签：碎片；拼接；复原；模拟退火算法；系统聚类法碎纸片拼接复原工作在诸多领域中有着极其重要的应用，如历史文物的考证、司法鉴定以及情报获取等。
在计算机技术发展起来之后，传统的人工复原方式导致效率低下的弊端日益凸显，因此，通过数学建模的方法得到碎纸片自动拼接复原模型以提高拼接效率显得尤为重要，已有文献对此做了一些研究[1-3]。
文章以2013年全国大学生数学建模竞赛B题为例，基于模拟退火算法与系统聚类分析，依次介绍仅纵切、既有横切又有纵切、双面打印三种情形下的碎纸片拼接复原要点。
1 仅纵切的碎纸片拼接复原要点步骤6：降温。
选定降温系数θ（一般取为接近1的数）进行降温，即用θT 取代T，从而得到新的温度。
步骤7：算法终止条件。
用选定的终止温度Te，判断退火过程是否结束。
若T<Te，算法结束并输出当前的状态。
这样，由于碎纸片较大，图片信息较明显，因此不需要人工干预，复原率可达100%。
附件2中的英文图片可类似处理。
2 有横、纵切的碎纸片拼接复原要点对于既有横切又有纵切的碎纸片拼接复原，若利用上一问的方法直接对全部的209张图片进行拼接，一方面必然会导致算法运行效率大大降低；另一方面，由于区分各图片间边界差异的灰度值信息较少，易导致拼接时重码率高而复原率低。
因此，我们采用的方法是，首先提取出所有图片的行特征；然后对209张图片建立行聚类模型，对各行聚类依据上一问的方法将其中图片重排；最后对排好序的各行类似的作横向排序即可将碎片拼接复原。
具体的步骤如下：第一步，提取图片的行特征。
利用Matlab读入图片，将每张图片转化为一个180*72的灰度值矩阵；再用Matlab可计算出中文字符高为40像素点，行间距为31像素点。
第二步，建立行聚类模型。
碎纸片的拼接复原数学模型的构建摘要院本文讨论在碎纸机以不同方式破碎纸片的情况下建立碎纸片的拼接复原模型，以解决碎片数量巨大时人工拼接的难题，本文建立了三个具有针对性的模型。
模型一：方差分析法下的碎纸片拼接模型。
在以纵切方式破碎纸片的情况下，提取碎纸片左右边缘的灰度列向量，利用碎纸片边缘处为单边同宽空白区域的特殊性对碎纸片进行定位，再利用方差分析法和欧式距离解决了纵切碎纸片的拼接复原问题。
模型二：文字行间距一致性的碎纸片拼接模型。
以纵横方式破碎纸片，利用同行文字行间距一致性的主要特性可解决横向碎纸片的拼接复原问题，简化了模型，将离散的像素灰度矩阵平均化处理，进而利用欧氏距离对碎纸片进行匹配，得到了碎纸片复原后的完整图片。
模型三：二值化Otsu 算法的碎纸片拼接复原模型。
本文从双面纵横破碎纸片的问题出发，建立了纸片二值化Otsu 法拼接模型，先对碎纸片分组预处理，为将复杂模型简单化，再利用全局阈值方法中典型的Otsu 法求取碎纸片的最佳阈值，以该阈值对碎纸片中所含灰度值信息进行划分实现二值化处理，将边缘区域明显化，利用统计学方法求取拼接后的纸片间成功匹配的像素点占纸片边缘的概率，最终双面纵横破碎纸片的拼接复原问题得以解决。
Abstract: This paper discusses the construction of splicing scrap recovery model under the condition of shredder breaking paper intopieces in different ways, so as to solve the problem of artificial splicing when there is a great amount of pieces. This paper establishes threecorresponding model.Model One: Paper Scrap Splicing Model under Analysis of Variance.Shredding paper through longitudinal mode, the paper selects the gray scraps of paper around the edge extraction column vector,locates the paper scrap by using edge of paper scraps as blank area with same width, then solves the problem of reconstruction of thelongitudinal cutting paper splicing through analysis of variance method and Euclid Distance.Model Two: Paper Scrap Splicing Model with Consistency of Text Line Spacing.Shredding paper through vertical and horizontal mode, its main characteristics of peer text line spacing consistency can solve theproblem of reconstruction of splicing transverse paper scraps, simplifies the model, processes the pixel matrix of discrete in average andmatches the paper scraps through Euclid Distance and then gets the complete picture of paper scrap afterrecovery.Model Three: Paper Scrap Splicing Model Based on Binaryzation Otsu Algorithm.This paper firstly expounds the double side's vertical and horizontal mode, establishes the paper scrap splicing model based onbinaryzation Otsu algorithm. The paper firstly does preconditioning for paper scraps into groups, simplifies the complex model, and then getsthe optimal threshold of the paper scraps by using typical Otsu algorithm of global threshold method. The paper classifies the gray valueinformationof paper scraps through this threshold to realize binaryzation processing, specifies the edge area, evaluates the probability ofsuccessful matching pixels on edge of splicing paper, and finally solves the mosaic and restoration problems of double side's vertical andhorizontal mode.关键词院离散；方差分析；置信区间；阈值；Otsu 算法Key words: discrete；analysis of variance；confidence interval；threshold；Otsu algorithm中图分类号院TQ018 文献标识码院A 文章编号院1006-4311（2014）25-0238-031模型一考虑以为空间拼接情况，为了获取拼接图像所必须的数据，文章以像素为单位离散所得碎片：利用VC++使用了Windows.H 头文件并调用RGB 等结构定义获得不同像素点的g 值[1]，生成了多个灰度矩阵。
碎纸片的拼接复原摘要本文利用MATLAB软件将附件图像数字化，把图像转化为灰度矩阵进行处理。
问题一，本文利用边缘匹配模型和灰度匹配模型对碎纸片的边缘作分析。
基于，边缘部分的黑白分布越相近，两者相连的可能性越高的原理，得到附件1的排序是008，014，012，015，013，010，002，016，001，004，005，009，013，018，011，007，017，000，006 。
附件2的排序是003，006，002，007，015，018，011，000，005，001，009，013，010，008，012，014，017，016，004。
问题二，本文首先按行将小块进行分类，以简化模型。
在附件3中，将碎纸片分组，对分完组后的碎纸片采用字体矩形模型，实现同行间排序，将得到的行再通过匹配模型，从而拼出原文。
而对于附件4，本文建立四线格位置模型，将碎纸片进行分组。
计算过程中发现部分标号基线相同，但却与不同的行对应匹配，此时进行人工干涉。
然后运用行内匹配模型，对同行间的碎纸片排序。
附件3、附件4的排序结果见附录一。
关键词：灰度矩阵，匹配模型,相关性分析,三线格基线,人工干涉,最优化一.问题重述破碎文件的拼接一直以来都以人工为主，其准确度较高，但效率较为低下，不能承担短时间内完成巨大数量的碎片拼接任务，遏制了在司法物证复原、历史文献修复以及军事情报获取等领域的进一步发展。
随着计算机技术的发展，我们尝试运用计算机软件来实现对破碎文件的迅速拼接。
现问题如下：（1）、对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。
如果复原过程需要人工干预，请写出干预方式及干预的时间节点。
复原结果以图片形式及表格形式表达。
（2）、对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。
