下载文档原格式
基于分治算法碎纸片的拼接复原模型摘要本文针对不同切割方式碎纸片的拼接问题，通过对图像数字化处理得到灰度矩阵，建立了复原模型并得到复原后的图像。
针对单面仅纵切碎纸片的拼接问题，根据完整文件最左边部分无文字的特点，运用matlab编程可确定出第一碎纸片。
随后，根据贪婪算法的思想，以确定位置的碎纸片与剩余未拼接碎纸片相邻边缘灰度值的平方欧氏距离最短为目标函数，可逐步求得碎纸片的拼接顺序,进而将其复原.中文碎纸片顺序为：8、14、12、15、3、10、2、16、1、4、5、9、13、18、11、7、17、0、6；英文碎纸片顺序为：3、6、2、7、15、18、11、0、5、1、9、13、10、8、12、14、17、16、4。
本问碎纸片拼接过程没有人工干预，实现了全自动化的拼接。
对于既横切又纵切碎纸片拼接问题，本问采用分治算法的思想，先对中、英文碎纸片分别层次聚类分析，将最可能位于同一行的碎纸片归为同一类，其中中文碎纸片分为11类，英文碎纸片分为10类；再对分类后的碎纸片使用编程加人工干预的半自动拼接方式，得到11块仅横切的碎纸片块；最终对得到的11块仅横切的碎纸片块进行类间拼接，实现文件的复原。
中文碎纸片第一列顺序为：49、61、168、38、71、14、94、125、29、7、89；英文碎纸片第一列顺序为：191、201、86、19、159、20、208、70、132、171、81。
此问中有两次人工干预的过程，第一次位于类拼接处，第二次位于类间拼接处。
中文文件总共干预了33块，英文文件总共干预了40块。
考虑双面碎纸片拼接问题时，本问延续了分治算法的思想。
由于每碎纸片含有正反两面，在聚类分析时，可将正反两面的灰度值相加为一列特征值作为它们是否可能位于同一行的依据，进而将双面碎纸片分为9类。
再对这9类碎纸片使用编程加人工干预的半自动拼接方式，得到22块仅横切的碎纸片块；最终对这22块仅横切的碎纸片块进行类间拼接，实现文件的复原。
基于多约束条件的中文碎片拼接复原算法设计摘要：文章对纵横切中文碎纸片的拼接复原问题进行了分析，对碎片图像进行数字化处理，采用灰度相似性比较的方法，利用循环遍历的思想匹配碎片；接着对图像进行二值化降噪处理，去除干扰元素，考虑到传统匹配算法下存在多种匹配、错误匹配、重复匹配的问题，设计基于多种约束条件的中文碎片拼接算法；最后利用编程实现得到完整的复原图形，该算法提高了碎片拼接复原效率和精准度。
关键词：碎片复原；相似性比较；多约束；匹配模型传统破碎文件的拼接复原工作需由人工完成，效率很低。
随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。
本文对2013高教社杯全国大学生数学建模竞赛B题中提出的碎纸片拼接复原问题进行研究，主要研究纵横切中文碎纸片的拼接复原问题。
1 灰度值的相似性比较1.1 提取边缘灰度值①在得到所有图像的灰度值矩阵后，提取每组矩阵左边缘的灰度值，根据左边缘的灰度值的特点，判断该图像是否为第一张图片，若左边缘灰度值均为255（全白），则表示该列无文字信息，即可确定复原的第一张图片。
②提取第一张图像灰度值矩阵的右边缘灰度值，并与其他图像的左边缘灰度值作相似性比较，确定与之匹配的图像。
1.2 欧氏距离比较矩阵边缘灰度值相似性欧氏距离（Euclid Distance）也称欧几里得距离，是一个通常采用的距离定义，它是在维空间中两个点之间的真实距离。
在二维空间中的欧氏距离则为两点之间的直线段距离，其表达如下：d=■在确定灰度值相似性时，根据欧氏距离最短的准则，对于一张分辨率为m×n 的数字图像，用欧氏距离法确定出的的表达式为：d=■其中i=1，2……19，且i≠k，k表示要匹配的图片序号。
1.3 循环遍历搜索根据欧氏距离最小原则的相似性比较，匹配出与第一张图片相匹配的图像，然后将该图像作为待匹配的图像，寻找下一张与之匹配的图像，利用循环遍历搜索的方法，得到匹配顺序。
碎纸片拼接复原的数学方法拼图游戏，一种看似简单却富含深度的游戏，给人们带来了无穷的乐趣。
然而，大家是否想过，这样的游戏其实与数学有着密切的？让我们一起探索碎纸片拼接复原背后的数学方法。
碎纸片拼接复原，其实就是一个计算几何问题。
在数学领域，欧几里得几何和非欧几里得几何是两个基本而又重要的分支。
欧几里得几何主要研究的是在平面上两点之间的最短距离，这是我们日常生活中常见的几何学。
而非欧几里得几何则研究的是曲面上的几何学，这种几何学并不符合我们日常生活中的直觉。
碎纸片拼接复原的问题就是一种非欧几里得几何问题。
在计算机科学中，图论是研究图形和网络的基本理论。
其中，图形遍历算法可以用来解决碎纸片拼接复原问题。
这种算法的基本思想是：从一点出发，尽可能多地遍历整个图形，并在遍历的过程中对图形进行重建。
对于碎纸片拼接复原问题，我们可以将每一张碎纸片看作是图中的一个节点，当两张碎纸片拼接在一起时，它们就形成了一个边。
通过这种方式，我们可以将所有的碎纸片连接起来，形成一个完整的图形。
在计算机科学中，碎纸片拼接复原问题被广泛应用于图像处理、数据恢复等领域。
例如，在数字图像处理中，如果一张图片被切割成若干块，我们可以通过类似的方法来恢复原始的图片。
在数据恢复领域，当一个文件被删除或格式化时，我们也可以通过类似的方法来恢复文件。
碎纸片拼接复原的问题不仅是一个有趣的拼图游戏，更是一个涉及计算几何、图论等多个领域的数学问题。
通过运用这些数学方法，我们可以有效地解决这个问题，从而更好地理解和应用这些数学理论。
在我们的日常生活中，我们经常会遇到一些破碎的物品，例如碎镜子、破碎的瓷器，或是碎纸片等。
这些物品的复原过程都需要一种科学的方法来帮助他们重新拼接起来。
这种科学方法就是碎纸片拼接复原技术。
碎纸片拼接复原技术是一种基于数学模型的方法，它通过比较碎纸片边缘的形状、纹理、颜色等特征，来找到碎纸片之间的相似性和关联性，从而将它们拼接起来。
一种基于文字特征的碎纸片拼接算法设计刘秋菊;陈平;王仲英【摘要】提出了一种解决碎纸片拼接复原的方法.该方法首先把边界文字连续点的数目作为文字特征,然后使用连续八连通对边界文字灰度特征进行提取,通过特征提取得到基于灰度特征的连续点数目特征矩阵,最后,通过位置排序得到碎片的排序结果.按照算法设计思想编写C语言程序并针对实际例子进行拼接实验,实验结果表明,该算法符合设计要求.【期刊名称】《实验室研究与探索》【年(卷),期】2016(035)011【总页数】4页(P110-113)【关键词】纸片拼接;文字特征;连续八连通;特征矩阵【作者】刘秋菊;陈平;王仲英【作者单位】郑州工程技术学院信息工程学院,河南郑州450044;济源职业技术学院信息工程系,河南济源459000;河南经贸职业学院技术科学系,河南郑州450018【正文语种】中文【中图分类】TP391碎片拼接问题是数字图像处理中常常研究的问题。
碎片文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用，因此，通过计算机建立对于破碎文件自动拼接和恢复的算法与模型，具有很重要的现实意义。
一般对于碎片的拼接，针对碎片的破碎方式可以采用不同的算法完成拼接。
对于只有纵切方式的碎片要完成拼接复原，不能采用一般的根据边界几何特征拼接文件的方法拼接文件，使用边缘的尖点特征、尖角特征、面积特征等几何特征，搜索与之匹配的相邻碎纸片并进行拼接，这种基于边界几何特征的拼接方法并不适用于边界几何都是规则的碎片的拼接[1-8]。
对于不同横截面的中英文的碎片，首先，需要提取碎片特征，利用抽取到的特征，建立线性规划目标函数模型，利用图论中的二分图，整数0-1规划等对特征计算，使用特征之间的相似度或者距离作为拼接指标进行碎片的拼接，同时考虑到计算机的自动拼接可能带来的误差，加入人为的干预，提高拼接的准确率。
对于只有纵切方式的碎片要完成拼接复原，首先，对灰度图像进行全局阈值的二值化，得到二值化后图像的灰度值，同一个字符的共同特点是在它相应的位置和相应的领域内能够找到相应的笔段[9-11]。
碎纸片的拼接复原分析最终引言碎纸片的拼接复原是一项有趣且具有挑战性的任务。
无论是为了还原重要文件还是拼接有意义的图像，我们都需要使用各种技巧和方法来完成这项任务。
本文将介绍一种基于分析的碎纸片拼接复原方法，通过对碎纸片的形状、颜色和纹理等特征进行分析，最终达到拼接复原的目标。
碎纸片的特征提取在进行碎纸片的拼接复原之前，首先需要提取碎纸片的特征。
这些特征包括碎纸片的形状、颜色和纹理等。
形状特征提取为了提取碎纸片的形状特征，可以通过计算碎纸片的边界和角度来获得。
首先，使用图像处理技术，如Canny边缘检测算法，将碎纸片的边缘提取出来。
然后，使用霍夫变换来检测碎纸片的直线和角点，从而计算出角度和边界。
颜色特征提取碎纸片的颜色特征可以通过计算图像的颜色直方图来得到。
颜色直方图表示了图像中每个颜色的像素数量。
我们可以使用像素级别的颜色分布来比较不同碎纸片的颜色特征，并找到相似的碎纸片来进行拼接。
纹理特征提取碎纸片的纹理特征可以通过计算图像的纹理描述符来得到。
纹理描述符是用于描述图像纹理的数值特征。
其中，最常用的纹理描述符包括灰度共生矩阵（GLCM）和局部二值模式（LBP）。
通过计算碎纸片的纹理描述符，我们可以比较不同碎纸片之间的纹理相似度，并选择相似的碎纸片进行拼接。
碎纸片的拼接策略在完成碎纸片特征提取后，接下来需要制定碎纸片的拼接策略。
拼接策略将基于碎纸片的特征相似度和拼接的整体目标来确定。
相似度匹配根据碎纸片的形状、颜色和纹理特征，我们可以计算两个碎纸片之间的相似度。
一种常用的相似度计算方法是使用余弦相似度，它衡量两个向量之间的夹角。
通过计算碎纸片之间的相似度，我们可以找到最相似的碎纸片来进行拼接。
拼接顺序在进行碎纸片的拼接时，需要制定一个拼接顺序。
一种常用的策略是首先选择与已拼接部分最相似的碎纸片进行拼接，然后逐渐增加已拼接部分的面积，直到最终完成拼接。
拼接约束为了保证拼接的准确性，我们需要制定一些拼接约束。
基于文字特征和边缘特征的文本碎纸片拼接刘赐德;黄志祥;管一弘;赵建军【期刊名称】《信息技术》【年(卷),期】2018(000)001【摘要】For the hand-cut irregular pieces of paper scraping pieces of recovery,the basic characteristics of shredding paper was analyzed and this paper puts forward the splicing method based on character features and edge features.Firstly,the shredded image is preprocessed,and then the characters and edge features of the image are extracted.The corner matching algorithm was used to splice the boundary shredding sheet by using the edge features,and the whole splicing was accomplished by using the character feature.%针对手撕无规则的文本碎纸片拼接复原,分析了碎纸片的基本特征,提出了基于文字特征和边缘特征的拼接方法.先对碎纸片图像进行预处理,再对图像的文字特征和边缘特征进行提取.利用边缘特征,使用角点匹配算法拼接边界碎纸片,利用文字特征完成整个碎纸片的拼接.【总页数】5页(P20-23,28)【作者】刘赐德;黄志祥;管一弘;赵建军【作者单位】昆明理工大学理学院,昆明650504;上海大学理学院,上海200436;昆明理工大学理学院,昆明650504;昆明理工大学理学院,昆明650504【正文语种】中文【中图分类】TP391.41【相关文献】1.基于灰度及文字行位置的碎纸片拼接优化模型 [J], 孙魏;伍度志2.基于分层聚类的仅横纵切碎中文纸片拼接分类 [J], 熊保平;祝丽华3.一种基于文字特征的碎纸片拼接算法设计 [J], 刘秋菊;陈平;王仲英4.基于文字特点的碎纸片拼接技术探究 [J], 王玉霞;夏望红;林泓亮;肖响文5.基于文字边缘信息的碎纸片拼接 [J], 郝凯锋因版权原因，仅展示原文概要，查看原文内容请购买。
碎纸片的拼接复原摘要本文研究了碎纸片的复原问题。
对已有的碎纸片，我们利用Matlab求碎纸片边各侧边线的灰度值，通过最小偏差平方和法进行碎纸片间的相互匹配，中间加入人工干预进行筛选，将附件中的碎纸片全部还原。
之后，我们将该方法进行推广，可用以处理更复杂形状碎图片的的还原问题。
对问题一：首先假定附件一所给仅纵切的碎纸片的行文方向与各碎纸片两侧边线垂直，在此基础上先人工干预，根据碎纸片的剪切规范，甄选出原始图片的第一张和最后一张碎纸片，编号分别为008和006。
其次通过Matlab求出图片边线处各小网格点的灰度值，采用最小偏差平方和法，对编号008碎片右边线处的灰度值和其它碎纸片的左边线处的灰度值进行对应网格点的数值匹配，找到最匹配的碎纸片。
附件二碎片的处理进行了类似处理，给出的复原图片见附表4。
对问题二：附件三文本既纵切又横切，同样我们假设所给附件三中碎纸片的行文方向与碎纸片的上下左右边线分别平行或垂直。
在问题一的算法基础上，通过Matlab求出各碎纸片的4条边线的边界灰度值，然后利用最小偏差平方和法，对上下左右四边进行灰度值匹配，当结果多个时，我们进行了人工干预。
附件四依照附件三的方法类似处理，最终的复原见附表7和附表9。
对问题三：附件五中的图片既纵切又横切而且是正反面。
我们参照问题一、二的处理方法，加入反面的灰度值测算，随机选择一张碎纸片与其他碎纸片进行遍历匹配，得出4张匹配的碎纸片后，以这4张碎纸片为下一起点，扩张匹配，最终给出的复原图见附表12。
为适应更一般的情形，我们在模型改进部分，给出了当碎纸片的文字行文方向与碎纸片两侧边线不垂直时的处理方法（只处理了边线为直线的情形）。
首先是通过测算出的碎纸片灰度值确定出碎纸片的边缘线，其次定出碎纸片边缘线附近网格点的灰度值，最后完成边线的的匹配。
关键词：人工干预灰度矩阵灰度值最小偏差平方和法一问题重述1.1问题背景纸片文字是人们获取和交换信息的主要媒介，尤其是在计算机技术飞速发展、数码产品日益普及的今天。
大学生数学建模竞赛优秀论文关于碎纸片自动拼接的数学模型摘要本文针对生活中破碎文件的拼接难度大，效率低等现象，从题目所给的情形出发，利用计算机软件把碎纸片图像转化为数字图像，综合运用matlab 软件中的数字图像处理方法，建立了以图与图之间的相似程度为基准的数学模型。
这个模型的评价标准很简单，就是相似度函数的值。
通过比较图像与图像之间的相似度函数的值的大小，就可以得出碎纸片的具体拼接序列。
对于问题（1），首先，用matlab 软件的imread 函数对图像的进行读取，得到数据矩阵为),(y x F i 。
其次，根据模型的假设（1），找到最右端的碎纸片，并记为),(1y x F 。
然后，以数据矩阵),(y x F i 为基础，引入相似度函数)(b sim ，并求 出相似度函数值。
最后，用matlab 工具箱中的sort 函数把所得到的相似度函数值进行排序，所得到的相似度函数值最小的图像即为与最右端的碎纸片匹配的图像。
如此重复18次，即可得附件1的中文图像的排列序号，结果如表1所示。
同理可得附件2的英文图像排列序号，结果如表2所示。
复原结果图片见论文附件的图1和图2。
对于问题（2），同样先找到最右端的11张图像和最上方的19张图像，根据图像的页边距特性确定原图像右上角的第1张图像。
利用问题（1）的算法可得最右端的11张图像和最上方的19张图像的排列序号。
然后，在问题（1）的算法的基础上，利用图像中的文字的固定间距去改进算法，缩小搜索范围，并在拼接完一行后显示一次结果，由于近似距离计算公式与人主观视觉差异，所以需要人机交互调整结果。
如此重复18次，即可得附件3的中文图像的排列序号，结果如表3所示。
同理可得附件4的英文图像排列序号，结果如表3所示。
对于问题（3），与问题（2）相似，只是碎纸片由单面变为双面。
因此在匹配图像时，引入两重相似度函数)(Q sim ，以确保正反两面能同时匹配。
同时每匹配5张图像显示一次结果，以增加人工干预次数。
碎纸片的拼接复原数学模型的构建摘要院本文讨论在碎纸机以不同方式破碎纸片的情况下建立碎纸片的拼接复原模型，以解决碎片数量巨大时人工拼接的难题，本文建立了三个具有针对性的模型。
模型一：方差分析法下的碎纸片拼接模型。
在以纵切方式破碎纸片的情况下，提取碎纸片左右边缘的灰度列向量，利用碎纸片边缘处为单边同宽空白区域的特殊性对碎纸片进行定位，再利用方差分析法和欧式距离解决了纵切碎纸片的拼接复原问题。
模型二：文字行间距一致性的碎纸片拼接模型。
以纵横方式破碎纸片，利用同行文字行间距一致性的主要特性可解决横向碎纸片的拼接复原问题，简化了模型，将离散的像素灰度矩阵平均化处理，进而利用欧氏距离对碎纸片进行匹配，得到了碎纸片复原后的完整图片。
模型三：二值化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]，生成了多个灰度矩阵。
2013-高教社-全国大学生数学建模获奖论文-碎纸片的拼接和复原2013高教社杯全国大学生数学建模竞赛承诺书我们仔细阅读了《全国大学生数学建模竞赛章程》和《全国大学生数学建模竞赛参赛规则》（以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛网站下载）。
我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。
我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。
我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性。
如有违反竞赛章程和参赛规则的行为，我们将受到严肃处理。
我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。
我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B 我们的参赛报名号为（如果赛区设置报名号的话）： S15076 所属学校（请填写完整的全名）：河南理工大学参赛队员 (打印并签名) ：1. 祝红祥2. 程港3. 王金强指导教师或指导教师组负责人 (打印并签名)：（论文纸质版与电子版中的以上信息必须一致，只是电子版中无需签名。
以上内容请仔细核对，提交后将不再允许做任何修改。
如填写错误，论文可能被取消评奖资格。
）日期：年月日赛区评阅编号（由赛区组委会评阅前进行编号）：2013高教社杯全国大学生数学建模竞赛编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：碎纸片的拼接复原摘要破碎文件的复原有着重要的意义以及实用价值。
传统上，人们只能靠手工完成，效率十分低。
当碎片数量过于庞大时，甚至无法完成。
碎纸片的拼接复原模型摘要本文针对破碎纸片形状规则和碎片间无有效重叠区域等特点，选取了信息熵、差方和、欧氏距离、相关系数、互信息和灰色斜率关联度作为碎纸片之间的相似性判别准则，给出了碎纸片拼接复原模型和算法，解决了破碎纸片的拼接复原问题．对于问题1，引入信息熵来衡量每个碎片含有的信息量，将熵值最小的碎片确定为印刷文字文件的第一列；利用差方和计算出第1列右端与其余碎片左端的相似程度，求得碎纸片之间的最佳匹配组合，借助Matlab软件成功实现了附件1和附件2的碎片拼接复原．对于问题2,通过计算每个碎片的信息熵，找到印刷文字文件第一列的11个碎片；再利用互信息和相关系数评价碎纸片之间的相似性程度，确定出碎片间的上下位置关系，得到了印刷文字文件的第一列；然后利用欧氏距离作为相似性测度，进一步进行碎片间的粗拼接．若某个碎纸片与多个碎片的欧氏距离相等，则利用灰色斜率关联度进行碎纸片间的细拼接，借助Matlab软件完成了对附件3和附件4给出的碎片拼接复原．对于问题3，基于模糊聚类方法，粗略地确定出每个碎片的正面和反面；然后利用问题2的算法对已分类的正面碎纸片进行拼接复原；针对无法复原的碎纸片，借助Matlab 软件和最优搜索算法进行人工干预，确定出附件5文件正面的拼接复原；根据碎片数据编号的命名规则，在正面碎片数据的拼接复原结果中填充对应编号的反面碎片数据，实现了附件5文件反面的拼接复原．最后，对碎纸片的拼接复原模型和算法进行了分析和展望．关键词：破碎纸片的拼接复原；信息熵；差方和；互信息；欧氏距离；灰色斜率关联度；模糊聚类1. 问题重述破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用．传统上，拼接复原工作需由人工完成，准确率较高，但效率很低．特别是当碎片数量巨大，人工拼接很难在短时间内完成任务．随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率，需解决以下几个问题：问题1，考虑对于给定的来自同一页印刷文字文件仅纵切的破碎纸片的拼接复原模型和算法，并针对B 题附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原．如果复原过程需要人工干预，还需要写出干预方式及干预的时间节点．并就附件1和附件2的碎片数据给出拼接复原结果．问题2，考虑对于碎纸机既纵切又横切的情形，设计出碎纸片拼接复原模型和算法，并针对B 题附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原．如果复原过程需要人工干预，请写出干预方式及干预的时间节点．并就附件3和附件4的碎片数据给出拼接复原结果．问题3，则需要考虑更一般的情形，即考虑有双面打印文件的碎纸片拼接复原问题．对B 题附件5给出的是一页英文印刷文字双面打印文件的碎片，设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果．2. 模型假设(1) 碎纸片的切割是等间距的，忽略切割碎纸片时由机器工作所产生的摩擦误差； (2) 碎片切缝处的图像灰度平滑；(3) 碎片在缩放的情况下，像素点保持稳定； (4) 碎片上的文字只显示黑白两种颜色．3. 符号说明N ：每张碎片像素点的数目；ij a 、ij b ：图像A 、B 在()j i ,的像素值；),(B A SSD ：A 与B 的差方和；)(a h A ：图像A 中第a 个灰度级的像素个数与总的像素个数之比；)(ab h AB ：图像A 中第a 个灰度级和图像B 中第b 个灰度级的像素对数与两幅图像总的像素对数之比；)(A H 、)(B H ：图像A 和B 各自含有的信息量；)(AB H ：两幅图像A 和B 的联合信息熵；ij d ：两幅图像A 和B 的欧式距离；ij a 、ij b ：图像A 和B 在 ()j i ,位置的像素值； a ：图像A 像素值的平均值；),(B A C :两幅图像A 和B 的相关系数；)(a P A 、)(b P B ：碎片边缘概率密度； )(ab P AB ：两碎片A 和B 的联合概率密度；);(B A I :两碎片A 和B 的互信息；)(t X :系统特征函数；)(t Y i :相关因素函数；tt x ∆∆)(:系统特征函数)(t X 在t 到t t ∆+的斜率； tt y i ∆∆)(:相关因素函数)(t Y i 在t 到t t ∆+的斜率； )(t x ∆：系统特征函数在t 到t t ∆+的增量；)(t y i ∆：相关因素函数在t 到t t ∆+的增量； x ：系统特征函数的均值；i y ：相关因素函数的均值；)(t i ξ：)(t X 与)(t Y i 在t 时刻的灰色斜率关联系数；D ：对称距离矩阵；i ε：)(t X 与)(t Y i 在t 时刻的灰色斜率关联度．4. 问题分析由于文章以行书写，只有段首段尾有空白，切缝处恰好以列之间的空白或笔画出断开的概率较小，在拼接碎纸片前需要对B 题附件1—5的碎片内图像进行二值化处理，进而获取由0和1组成的矩阵．扫描后的图像有亮的图像和暗的背景组成，由于光照、拍摄角度等因素，一幅图像往往包括文字、背景还有噪声等．如果从多值的数字图像中直接提取目标，最常用的方法就是设定阈值T ，用T 将图像的数据分为两部分：大于T 的像素群和小于T 的像素群．由于5个附件中的文字显示都是黑白颜色，因此先调用Matlab 软件中的im2bw()对每个碎纸片进行二值化图像预处理，然后综合利用图像的相似性测度寻找高精度的匹配碎片，从而实现整个印刷文字文件的复原．5. 模型的建立与求解5.1 问题1的求解5.1.1 模型的建立差方和利用两幅图像对应位置的差方和均值表示图像之间的相似程度，定义为[1]，∑-=ij21),(）（ij ij NB A SSD b a (1) 式中，N 为每幅图像像素点的数目，ij a 和ij b 分别是图像A 和B 在()j i ,位置的像素值．当两幅图像正好可拼接时，),(B A SSD 值最小．差方和计算的时间复杂度为()2N O ．信息熵反映了图像含有的信息量大小．信息熵越小，图像包含的信息量越小，往往空白区域越多，其定义为[2-4]：∑=aA A a h a h A H )(log )()( (2)其中，)(a h A 表示图像A 中第a 个灰度级的像素个数与总的像素个数之比． 5.1.2 拼接复原算法附件1和附件2中碎纸片的切割方式只有纵切一种，假设碎片的总数为n 个．考虑到纵切的特殊性，给出如下的拼接复原算法：步骤1 计算每一个碎纸片)1(n i A i ≤≤的信息熵)(i A H ，并确定出熵值最小的一个碎片n i i A H 1)}(min{=为印刷文字文件的第1列；步骤2 计算第1列图像A 的右边与其余1-n 个碎片)1,1(≠≤≤j n j A j 的左边的差方和),(1j A A SSD ，确定出与第1列图像差方和最小的碎片为印刷文字文件的第2列；步骤3 重复步骤2，依次继续，直到找到印刷文字文件的n 列为止． 5.1.3 问题1的求解借助Matlab 软件对以上拼接复原算法进行仿真，得到如下结果： (1) 附件1中的中文文件复原结果表1 附件1中19个碎片的信息熵从表1可以看出，19个碎片所包含的信息量中，第008碎片的信息熵最小，因此第008碎片是附件1中的中文文件的第1列．表2 附件1中19个碎片之间差方和最小的配对碎片表从表2可以得到附件1中的中文文件复原结果，如下表所示：表3 附件1中文件的拼接复原结果表附件1中的中文文件复原图结果见附录1．(2)附件2中的英文文件复原结果表4 附件2中19个碎片的信息墒从表4可以看出，所有19个碎片所包含的信息量中，第003碎片的信息墒最小，因此第003碎片是附件2文件的第1列．表5 附件2中19个碎片之间差方和最小的配对碎片表从表5可以得到附件2的英文文件复原结果，如下表所示表6 附件2英文件的拼接复原结果表附件2中英文文件的复原结果图见附录2．5.2 问题2的求解5.2.1 模型的建立由于互信息测度是从图像的统计信息出发，既不需要两幅图像的灰度关系，也不需要图像进行预处理，因此成为目前广泛使用的图像配准相似性测．在图像配准过程中，如果两幅图像精确匹配，互信息达到最大．联合熵定义如下[5]：)(log )()(,ab h ab h AB H AB ba AB ∑= （3）其中)(ab h AB 表示图像A 中第a 个灰度级和图像B 中第b 个灰度级的像素对数与两幅图像总的像素对数之比．互信息定义为)()()();(AB H B H A H B A I -+= (4)欧氏距离被视为两个图像的相似程度，距离越近就越相似，其定义为∑-=2)(ij ijij b ad (5)相关系数是标准化的协方差函数，当两幅图像的灰度之间存在线性畸变时，仍能较好的评价两幅图像之间的匹配性程度．图像的相关系数1),(≤B A C ,它是两幅图像A 和B 特征点之间近似程度的一种线性描述．如果),(B AC 越接近于1，两幅图像的相似程度越大，越近似于线性关系．选择相关系数中最大的相关系数所对应的特征点为这个点的匹配特征点．当两幅图像可匹配时，相关系数达到最大值．相关系数定义如下[7-9]：2/122))(*)(()(*)(),(∑∑∑----=b b a a b b a bB AC ij ij ijij ij(6)两幅图像相关系数计算的时间复杂度为)(2N O ,其中N 为每幅图像像素点的数目． 灰色斜率关联度的基本思想是根据待拼碎片的特征曲线（称系统特征函数）与参照碎片的特征曲线（称相关因素函数）的相似程度来判断其联系是否紧密，曲线越接近，关联度就越大，反之就越小．灰色斜率关联度的定义为[10]：∑-=-=11)(11n t i i t n ξε (7) 其中，t t y yt t x x t t x x tt x x t i i ∆∆-∆∆+∆∆+∆∆+=)(*1)(*1)(*11)(*11)(ξ (8)为灰色斜率关联系数．(7)、(8)式中)(t X 为系统特征函数，)(t Y i ()m i ,,2,1 =为相关因素函数（对应于参照碎片的特征曲线），∑==nt t x n x 1)(1，)()()(t x t t x t x -∆+=∆,t t x ∆∆)(为系统特征函数)(t X 在t 到t t ∆+的斜率, ∑==nt i i t y n y 1)(1，)()()(t y t t y t y i i i -∆+=∆, t t y i ∆∆)(为相关因素函数)(t Y i 在t 到t t ∆+的斜率．对于灰色斜率关联系数)(t i ξ公式(8)有如下性质[11-13]：(1) 任意的系统特征函数)(t X 与相关因素函数)(t Y i 的灰色斜率关联系数满足：1)(0≤<t i ξ，m i ,,2,1 =；(2) 灰色斜率关联系数)(t i ξ满足对称性；(3) 灰色斜率关联系数)(t i ξ只与)(t X 与)(t Y i 的几何形状有关，与相对位置无关； (4) )(t X 与)(t Y i 的斜率越接近，灰色斜率关联系数)(t i ξ就越大；(5) )(t X 与)(t Y i 在t 到t t ∆+的变化速度相同时，它们的斜率相等，这时1)(=t i ξ； 由上述公式及性质可知，灰色斜率关联系数反映了两曲线在某一点的变化率的一致程度，而灰色斜率关联度则是整个区间上灰色斜率关联系数的平均值．灰色斜率关联度i ε具有下列性质： (1) 10≤<i ε；(2) i ε只与)(t X 与)(t Y i 的变化率有关，而与它们的空间相对位置无关； (3) 当)(t X 与)(t Y i 变化率相同时， 1=i ε； (4) )(t X 与)(t Y i 的变化率越接近， i ε就越大；5.2.2 拼接复原算法附件3和附件4中碎纸片的切割方式有纵切和横切两种，假设碎片的总数为n 个（m ⨯k 个碎片组成整个原图），具体的拼接复原算法如下：步骤1 计算每一个碎纸片)1(n i A i ≤≤的信息熵)(i A H ，并确定出熵值最小的m 个碎片n i i A H 1)}(min{=为印刷文字文件的第1列的m 个碎片；步骤2 计算步骤1找到的m 个碎片的上半部图像和下部分图像之间互信息和相关系数，确定出m 个碎片的上下位置关系，得到印刷文字文件的第1列；步骤3 计算第1列中m 个碎片右边与其它碎片左边的欧氏距离，得到碎片之间关于欧氏距离的矩阵n m M ⨯；在矩阵n m M ⨯中，第i 行的值ij d 表示第i 个碎片与第j 个碎片之间的欧氏距离．步骤4 在n m M ⨯中，计算第)1(m i i ≤≤行的最小值i min ；若n m M ⨯中i min 在第i 行出现的次数为1且对应的列标为j ，则第i 个碎片和第j 个碎片是最佳匹配组合；若i min 在第i 行出现的次数为大于1，则进行步骤5.步骤5 i m i n 在i 行中出现的次数为大于1，则计算第i 个碎片的右边图像与其余碎片左边图像的灰色斜率关联度)1(n f if ≤≤ε，记灰色斜率关联度最大的值ih ε对应的列为k ；若第k 个碎片在步骤4的最佳匹配组合中没有出现，那么第i 个碎片和第k 个碎片是最佳匹配组合；若第k 个碎片已在步骤4的最佳匹配组合中出现过，选择灰色斜率关联度仅次于ih ε)(ih iy εε<的值对应的列y ；若第y 个碎片在步骤4的最佳匹配组合中没有出现，则第i 个碎片和第y 个碎片是最佳匹配组合，否则继续寻找第i 个碎片的最佳匹配碎片，直止找到满足斜率关联度最大且在以前的最佳匹配组合中没出现条件的碎片．步骤6 重复以上步骤，直到所有的碎片找到最佳的匹配组合为止．按照最佳匹配组合的关系将所有碎片链接起来，并在第1列中出现的碎片位置出换行，便可对文件的所有碎片数据进行拼接复原． 5.2.3 问题2的求解运行matlab 软件对以上算法进行仿真，得到如下的结果．(1) 附件3中的中文文件复原结果表7 附件3中碎片的排列序号附件3中文件的最终复原图见附录4．(2) 附件4中的英文文件复原结果附件4的复原结果表格形式如下表所示：表8 附件4中碎片的排列序号附件4中文件的最终复原图见附录6．5.3 问题3的求解5.3.1 模型的建立模糊聚类分析是一种将样本或者变量分类的统计方法，基于物以类聚的思想，它根据样本数量计算样本之间的距离（相似程度），按距离的大小，将样本或变量逐一归类，关系密切的类聚到一个小的分类单位，使同一类的对象之间具有较高的相似度，然后逐步扩大，使得关系疏远的类聚合到一个大的分类单位，知道所有的样本或变量都累计完毕．模糊聚类分析法常用的距离为绝对值距离和欧式距离，其中，欧氏距离在聚类分析中用的最广．计算流程如下[14-15]：(1) 将n 张碎纸片分为n 类，取其中一个碎纸片右侧一列和另外任意碎纸片左侧一列作为样本，两个样本之间的距离构成一个对称距离矩阵⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=00021221112 n n n n d d d d d d D (2) 选择)0(D 中的非对角线上的最小元素，设这个最小元素是pq D ，此时{}p P x G =与{}q q x G =的距离最近，将q P G G 和合并成一个新类{}q P r G G G ,=．在)0(D 中消去q P G G 和所对应的行与列，并加入由新类r G 与剩下的其他未聚合的类间的距离所组成的新的距离矩阵)1(D ，它是n-1阶方阵；(3) 从)1(D 出发重复(2)的做法得)2(D ，再由)2(D 出发重复上述步骤，直到碎纸片聚成一个整体，聚类完成． 5.3.2 拼接复原算法附件5的碎片均为双面，假设碎片的总数为n 个（m ⨯k 个碎片组成整个原图的正面），具体的拼接复原算法如下：步骤1 基于模糊聚类分析法的思想，借助Matlab 软件编程将所有碎片区分粗分为正面和反面两大类；步骤2任选某一大类的碎片，利用问题2的拼接复原算法对该类的碎片进行拼接复原；步骤3 对无法拼接的碎片进行人工干预，直至所有的最碎片找到最佳的匹配组合为止．将所有的碎片进行链接，可复原文件的原图．根据碎片编号的命名规则，如果一面的原图复原成功，选择原图每个碎片对应序号的反面，可直接拼接复原出反面的原图．5.3.3 问题3的求解运行matlab软件对以上算法进行仿真，得到如下的结果．(1)附件5中的文件正面复原结果附件5中的文件正面复原结果见表9.附件5中文件正面的复原结果中间图见附录7．附件5中文件正面的复原结果中间图见附录8．对附录8中的碎片49a、161b、108b、045b、021a、042a、048b、180b、041b、202b和175b进行人工干预，得到附录9。
承诺书我们仔细阅读了《全国大学生数学建模竞赛章程》和《全国大学生数学建模竞赛参赛规则》（以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛网站下载）.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题.我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出.我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性.如有违反竞赛章程和参赛规则的行为，我们将受到严肃处理.我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）.我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B 我们的参赛报名号为（即电子文件名）： B0813 所属学校（请填写完整的全名）：广西师范大学参赛队员 (打印并签名) ：1. 杨凯2. 周志恒3. 陈锦丽指导教师或指导教师组负责人 (打印并签名)：日期2013年 9 月16日赛区评阅编号（由赛区组委会评阅前进行编号）：编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：纸片的拼接复原摘要碎纸自动拼接复原技术现今可以归结到计算机视觉和模式识别领域内的问题，它在司法物证复原、历史文献修复等重要领域都起着重要的作用.本文主要分析了文字的拼接技术，通过研究碎纸片内的像素矩阵和文字行特征特点，提出了基于文字图形的半自动拼接算法.对于问题1中的这种单面的仅纵向切碎的文字文件，通过Matlab程序分析附件中每个碎片的像素矩阵，确定拼接的第一个碎片（自左向右拼接），再根据两列像素矩阵的像素绝对差的和来确定相邻碎片的编号，从而得到完整的拼接方案.例如文字文件的拼接结果如下表所示：对于问题2中既纵切又横切的碎纸片，在问题一的基础上，充分考虑横向匹配和纵向匹配的要求，运用Matlab程序筛选最左列碎片成分，经过适当的人工干预根据文字行特征将所剩碎片进行行分类，大大提高拼接效率，得到意想的效果.例如文字文件的拼接结果如下表所示：对于问题3，在前两问的基础上，建立筛选附件5碎片图的优化模型，通过Matlab 编程，使用附件给的418张碎纸片图，将最终复原图划分为11个碎片横条区域，降低了拼接复原难度以及所需时间.最终复原结果见附录.最后，分析了所建立模型的优缺点以及推广，评价了文字碎纸片的拼接和复原实际情况.关键词文字图形碎片半自动拼接像素灰度 MATLAB程序一问题的重述碎纸自动拼接复原技术是计算机视觉和模式识别领域内的问题.它在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用.传统意义上的拼接复原工作需由人工完成，准确率较高，但效率非常低，特别是当碎片数量巨大时，人工拼接很难在短时间内完成任务.随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率.本文主要讨论：首先，对于给定的来自同一页单面印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，同时对题目中的附件1和附件2给出的中、英文各一页文件的碎片数据进行拼接复原.其次，对于同样是单面印刷文件既纵切又横切的情形，在第一问的基础上设计出碎纸片拼接复原模型和算法，对附件3和附件4给出的中、英文各一页文件的碎片数据进行拼接复原.最后，联系现实中的情况，对还有可能出现双面打印文件的碎纸片进行拼接复原.在前两问的基础上，设计出相应的碎纸片拼接复原模型与算法，并附件5中双面打印文件的碎片数据给出拼接复原结果.在上述复原过程中，由于计算机的识别可能会出现偏差，那么就需要在拼接过程中进行必要的人工干预，在适当的时候我们会用干预的方式给出复原过程.并最终以图片形式及表格形式完成给出复原结果.具体结果在附件中给出.二问题的分析破碎文件的复原，最直接及最精确的就是人工拼接，但是当碎片的数量巨大时，人工方式就显得效率低下，所以就考虑把破碎文件运用计算机技术来帮助人们进行破碎文件的复原，让计算机在这个过程中发挥主要作用，但是用计算机处理，又不是百分之一百完美，因此在适当的时候也需要进行人工干预.本文运用碎纸片的自动拼接技术，对每个附件给出的碎片文字材料进行分析，尽可能减少人工干预，本文给出的图像数据均为形状、大小一样的规则长四边形，由于形状的一致性，所以在拼接时如果只考虑利用碎片的边界特征，直接拼接，显然效果不理想.考虑到使用计算机的拼接过程应该与人工拼接过程是相类似的，即拼接时不但考虑碎片边缘是否匹配，还要判断碎片内的字迹断线和文字内容是否匹配.然而根据现在已有的技术，实现计算机智能识字是几乎不可能的.但是我们可以获取图片所提供的像素信息，将其转化为矩阵，根据图像的像素矩阵值进行碎片拼接，用计算机去运行处理数据，可以想象其拼接效率无疑比单纯利用边界特征的方法好很多.以下是对各问题的详细分析：针对问题1，对附件1和附件2提供的数据，每页纸被切为19条碎片，对于这种单面的仅纵向切碎的文字文件，我们仅考虑碎片左右两侧的拼接.首先，在转换中发现，像素图片矩阵的值是介于0到255之间的一个像素矩阵，随着像素矩阵值的增加，我们发现随着像素矩阵数值的增大，所代表的区域越来越浅，最后255这个数值，代表了白色区域.其次，对于问题1中的附件1和附件2图片，由于仅纵向切碎的文字文件，仅考虑碎片左右两侧的拼接.需运用Matlab程序分别对附件1和附件2中的19个碎片计的像素矩阵，筛选出每个算其像素矩阵，将每个附件中19条图像转换成19个198072像素矩阵的第一列像素矩阵值，然后运用Excel软件统计各列像素值等于255的个数，可以粗略的认为所含255个数最多的列所对应的碎片则是拼接顺序中的左边第一条（如果有必要进行人工干预，但是本文第一问没有进行人工干预）.接下来从左边开始选取第二条碎片，关于第二条待匹配的碎片，用先确定的第一条像素矩阵的最后一列，对其进行数值求和，然后将剩下的18个像素矩阵中的第一列和最后一列矩阵进行分别求和.将首先确定的最左边第一条矩阵中的最后一列矩阵与求出的18个像素矩阵中的第一列矩阵分别进行做差，然后将差值取绝对值，这样就可以得出，如果差值越小，其重叠的相似度也应该相对越高.这样可筛选得出相似度较高的碎片，即与第一个碎片相匹配，该碎片位于拼接顺序的第二条，确定第二条后，再用第二条的最右边矩阵并以此类推，逐一从左到右查询碎片，直到碎纸片的复原结果.针对问题2，在问题1的基础上，继续对所给的附件3和附件4进行分析.针对附件3和附件4的特点，附件3和附件4给出了碎片既横切又纵切的中英文图像，那么在拼接时就有两方面的考虑，既要满足横向匹配，又要满足纵向匹配.那么我们就考虑在问题解决中可以分为两步进行，首先考虑横向拼接，一旦横向拼接完成了，纵向拼接自然相对就好解决了.根据碎片像素矩阵特征和行距特征将其分类，再结合问题1的方法将各类碎片进行匹配，即可得到11个碎片横条.接着考虑纵向拼接，使用Matlab程序对得到的新的横条碎片进行像素分析，比较像素矩阵中第一行数据中255的个数，个数最多的碎片即是原文件的第一行，依次类推，同样的方法即可知道具体的排列顺序，从而得到碎纸片复原的结果.针对问题3，在问题1和问题2的基础上，继续对所给的附件5进行分析.实际生活中存在很多双面打印的文件，这些双面文件的碎纸片混合在了一起，当对其进行拼接复原时，首先要判断同一面的文字碎片，然后再进行拼接.附件5给出了碎片既横切又纵切的英文文字图像，那么在拼接时依旧有两方面的考虑，既要满足横向匹配，又要满足纵向匹配.首先考虑横向拼接，转换得到180x72的像素矩阵，这些是介于0到255之间的一个像素矩阵，随着图片的增加，相应的增多转换得到的像素矩阵，在问题2的基础上继续进行检验所给的碎纸片图，运用Matlab读取了418张碎片图后，将每张碎片转换得的像素矩阵的第一列以及最后一列各自取出，通过程序进行验证，可以算出匹配度高的相邻碎片，此时进行一次人工干预，拼接出位于同一行的碎片横条；接着考虑纵向拼接，运用Matlab程序对得到的新的横条碎片进行像素分析的提取，配准各个横条的像素矩阵的第一行与最后一行的相关度，综合分析碎纸片上英文之间的行距，进而确定拼接的碎片横条位于哪一行，得到最终的复原结果.综上所述，以上三个问题的解决流程可用下面的流程图表示：图2 问题解决流程图三模型假设准备与符号说明3.1模型的假设1、假设碎纸机把一页印刷文字文件碎成形状规则，大小一样的碎片，看做形状、大小相同的长方形.2、在碎纸过程中，只考虑文字被切开，不考虑文字笔画的丢失、碎片添加的任何痕迹等.3、假设文档碎片的文字的方向已经确定（按照阅读标准确定，从左向左右，自上而下），不考虑碎片图像的旋转问题.4、图片在复原的过程中，不考虑图片像素的改变，只考虑碎片相对应的固定像素值的匹配问题.3.2 模型准备不规则几何文档碎纸片计算机拼接的方法一般利用碎片边缘的尖角特征、尖点特征、面积特征等一些几何特征，搜索与之匹配的相邻碎纸片进行拼接，这种基于边界的几何特征的拼接方法并不适用于边缘的形状相似的碎纸片.对于这类边缘相似的碎纸片的拼接问题，理想的计算机拼接的过程与人工拼接的过程类似，即拼接时不仅要考虑拼接碎纸片的边缘是否匹配，还要判断碎纸片内的文字字迹断线或文字内容是否匹配，但是由于理论和技术的限制，让计算机具备类似于人的的那种识别碎纸片边缘字迹断线、以及理解碎纸片内文字图像的含义的智能几乎是不太可能的.但是利用现在已有的技术，完全可以获取到碎纸片文字所在行的几何特征信息，如文字行的行高及间距等信息.如果利用这些信息进行碎纸片拼接，其拼接的效率就比单纯利用边界的几何特征方法更好.根据本文题设要求，经考虑分析，本文采取转换矩阵数组元素拼接的技术对破碎的文字文档进行拼接复原.由于计算机数字分析图像能力方面的存在一定的缺陷，让计算机对碎纸片进行完全意义上的自动化拼接页几乎是不太可能，为保证其拼接的准确性，需要在拼接的过程中加入一定的人工干扰过程.一般来说，先利用计算机搜索出于目标碎纸片相匹配的未拼接碎纸片，并根据匹配的程度按顺序到得待选的碎纸片，然后人为地进一步分析结果进行舍弃或拼接待选碎纸片[3].一页文字文件的碎片拼接复原相当于全景图的生成技术，而相邻图像的配准及拼接是该技术的关键.图像的拼技术一般分为基于图像特征的方法和基于图像灰度的方法.特征提取的方法通常涉及大量的几何与图像形态学的计算，计算量大，没有一般的模型可遵循，但需要针对不同的应用场景来选择各自适合的特征，所提取的图像特征包括更高层的语义信息，基于特征的方法具有尺度不变性和放射不变形.然而基于图像灰度的拼接方法简单简单易行，并且其数字统计模型以及收敛速度、定位精度等均具有定量的分析和研究结果，此类方法得到了广泛的应用.本文中的文字图像中文字区域的文字结构相对单一，并可能出现相同或相似的字符，因此文字容易出现匹配出现误差.对于文字左右拼接的情况，可以对图片中划分的每行文字进行分析处理，通过提取文字图片的边缘像素矩阵，得到文字出现在图片边缘的那一行高，进一步对一行行的文字拼接复原，这也有利于获取更精确的配准结果.基于文字的图像灰度的方法不需要提取文字图像的相应的特征，只以两幅图像相连接部分对应的像素灰度的相似性准则来寻找图像的匹配位置.待匹配的图像，首先求出图像中最左边一列的像素矩阵值之和，和最右边一列像素矩阵之和。
关于碎纸机中碎纸片拼接复原的研究王 晨 曾 骞（山东大学，济南山东 250100）【摘 要】碎纸片的拼接复原在司法鉴定，历史研究等众多领域中都具有极其重要的作用。
针对条状和粒状碎纸机碎纸的拼接复原问题进行分析、建模，讨论单面及双面打印碎纸片复原的情况。
用扫描技术提取出碎纸片的像素矩阵，将图像信息转化为数字信息，并将取出的像素矩阵转化为0-1矩阵，对碎纸片边界进行分析、分类、匹配。
其中，根据矩阵之间的相关程度进行聚类，边界的匹配程度以欧式距离加以度量。
另外，0-1矩阵的使用减少了计算量，提高了匹配准确性和匹配效率。
【关键词】像素矩阵；欧式距离；相关程度；聚类分析【中图分类号】TP391.41【文献标识码】A【文章编号】1008-1151(2014)03-0015-03The research on the reversion of paper fragments which are in paper shredderAbstract: The reversion of paper fragments plays an important role in forensic identification, historical research and other fields. We present reversion models on this question and discuss two cases of the reversion of paper fragments, single-sided print and double-face print. We use scan technique to pick up pixel matrices and translate image information into figure information. We translate these matrices into 0-1 matrices , then analyse and match the boundary of paper fragments. According to the degree of correlation between pixel matrices and c luster analysis, we classify these matrices. Also, we use Euclid Distance to measure the degree of matching. Besides, the usage of 0-1 matrices decreases the amount of calculation and increase the efficiency of matching.Key words: Pixel matrices; Euclid distance; degree of correlation; cluster analysis1 引言碎纸片的拼接复原技术在司法鉴定，破案侦查，历史研究等领域有着广泛的作用。
