下载文档原格式
基于灰度像素理论的碎纸片拼接方法摘要常规的二维碎片拼接技术一直受到科研领域重视，它在司法鉴定、文物修复、图像处理等领域有着广泛的应用。
本文研究的是二维碎片拼接技术中最典型的文档类碎纸片拼接问题。
基于文档纸片色彩明确、方向一致、无重叠等特点，利用灰度理论对问题作出解决。
通过图形扫描得到图像，然后通过二值化，Sobel[]3梯度算进行预处理，并运用皮尔逊相关性度量及方差分析算法进行匹配，以实现对纸片进行还原。
本文通过MATLAB程序模型，以及图片像素灰度理论实现文档碎片的重新拼接。
对于问题1，应用图像处理技术中的灰度理论建立了灰度模型I。
在对得到灰度模型进行Sobel梯度边缘化预处理的方法进行模型改进，建立了边缘灰度模型II。
然后借助于皮尔逊相关系数算法和MATLAB软件，对附件中所提供的碎片进行排列拼接。
对于问题2，采用化归思想，将二维问题渐变为一维问题。
首先归纳碎片特征运用MATLAB软件对碎片进行同行分类，得到11行19列的元素；采用方差分析算法和人工干预对各行中元素进行排列，得到11条横切的图形；采用方差分析算法和人工干预对其进行排列，得以还原。
本文的亮点在于对各行中元素采用方差分析算法进行左侧到右侧匹配后，同时增加了右侧到左侧的匹配检验，大大减少了人工干预的工作。
关键字：灰度理论；皮尔逊相关系数算法；Sobel梯度边缘化；方差分析算法；人工干预一、问题的重述问题一、对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。
如果复原过程需要人工干预，请写出干预方式及干预的时间节点。
复原结果以图片形式及表格形式表达。
问题二、对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。
如果复原过程需要人工干预，请写出干预方式及干预的时间节点。
毕业论文声明本人郑重声明：1．此毕业论文是本人在指导教师指导下独立进行研究取得的成果。
除了特别加以标注地方外，本文不包含他人或其它机构已经发表或撰写过的研究成果。
对本文研究做出重要贡献的个人与集体均已在文中作了明确标明。
本人完全意识到本声明的法律结果由本人承担。
2．本人完全了解学校、学院有关保留、使用学位论文的规定，同意学校与学院保留并向国家有关部门或机构送交此论文的复印件和电子版，允许此文被查阅和借阅。
本人授权大学学院可以将此文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本文。
3．若在大学学院毕业论文审查小组复审中，发现本文有抄袭，一切后果均由本人承担，与毕业论文指导老师无关。
4.本人所呈交的毕业论文，是在指导老师的指导下独立进行研究所取得的成果。
论文中凡引用他人已经发布或未发表的成果、数据、观点等，均已明确注明出处。
论文中已经注明引用的内容外，不包含任何其他个人或集体已经发表或撰写过的研究成果。
对本文的研究成果做出重要贡献的个人和集体，均已在论文中已明确的方式标明。
学位论文作者（签名）：年月关于毕业论文使用授权的声明本人在指导老师的指导下所完成的论文及相关的资料（包括图纸、实验记录、原始数据、实物照片、图片、录音带、设计手稿等），知识产权归属华北电力大学。
本人完全了解大学有关保存，使用毕业论文的规定。
同意学校保存或向国家有关部门或机构送交论文的纸质版或电子版，允许论文被查阅或借阅。
本人授权大学可以将本毕业论文的全部或部分内容编入有关数据库进行检索，可以采用任何复制手段保存或编汇本毕业论文。
如果发表相关成果，一定征得指导教师同意，且第一署名单位为大学。
本人毕业后使用毕业论文或与该论文直接相关的学术论文或成果时，第一署名单位仍然为大学。
本人完全了解大学关于收集、保存、使用学位论文的规定，同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、扫描、数字化或其它手段保存或汇编本学位论文；学校有权提供目录检索以及提供本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有关部门或者机构送交论文的复印件和电子版，允许论文被查阅和借阅。
关于碎纸片自动拼接的数学模型摘要本文针对生活中破碎文件的拼接难度大，效率低等现象，从题目所给的情形出发，利用计算机软件把碎纸片图像转化为数字图像，综合运用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张图像显示一次结果，以增加人工干预次数。
碎纸片的拼接复原摘要碎纸片的拼接复原是一门借助计算机，把大量碎纸片重新拼接成初始纸张的技术。
针对问题一，本文首先利用碎纸片图像灰度矩阵的边缘矩阵，建立了两个碎纸片之间的匹配度函数，求得了每一张图片之间左右边缘匹配度矩阵。
然后根据左边边缘位置的碎片的左边空白部分最多的特点，确定了左边位置的碎纸片。
接着根据拼接碎纸片的拼接复原时，所有碎纸片匹配度之和取极大值的原则，采用贪心算法，得到了所有碎纸片的初始位置，拼接复原了附件1和附件2中纸片。
针对问题二，由于附件3碎片数量太多，并且碎片的拼接复原，是一个以碎纸片总匹配度为目标函数的组合优化问题。
所以本文采用遗传算法将碎纸片的编号作为基因，并将基因均匀分成19段，按顺序每一段对应一个初始纸片列位置，进行了求解。
然后，根据边缘碎纸片某些边的空白部分多的特征，对初始基因进行了优化。
接着，根据碎纸片的黑色像素密度不同的特点，将碎纸片分成三类，根据同类纸片优先匹配的原则，对遗传算法的运行过程进行了优化，拼接复原了附件3和附件4中纸片。
针对问题三，随着碎纸片量的增多，计算量急剧增加。
在上述拼接复原碎纸片的基础上，又引进了同行位置碎纸片的上部（或下部）空白位置宽度相近的聚类思想。
先对每个类内部拼接，在合并所有类并做一次整体拼接。
由于时间有限，我们未能完成最后一次的整体的拼接，但我们会在比赛后继续探究。
关键词：边缘矩阵匹配度函数遗传算法聚类一、问题重述碎片拼接实际用途已经越来越广泛，传统上拼接复原工作由人工完成，碎片拼接的准确率较高，但效率很低。
并且当碎片数量很大时，人工短时间内拼接出来几乎是不可能的。
所以开发碎纸的拼接技术，以提高拼接复原效率已成为越来越多人的期望。
现在,在碎纸片是规则的情况下，题目要求我们在以下条件建立碎纸片拼接复原模型和算法。
1.来自同一页印刷文字文件（中文、英文各一页）的碎纸机破碎纸片（仅纵切）拼接复原，并将附件1和附件2复原。
2.对碎纸机既纵切又横切文件的情形，将碎纸片拼接完整。
碎纸片的拼接复原分析最终引言碎纸片的拼接复原是一项有趣且具有挑战性的任务。
无论是为了还原重要文件还是拼接有意义的图像，我们都需要使用各种技巧和方法来完成这项任务。
本文将介绍一种基于分析的碎纸片拼接复原方法，通过对碎纸片的形状、颜色和纹理等特征进行分析，最终达到拼接复原的目标。
碎纸片的特征提取在进行碎纸片的拼接复原之前，首先需要提取碎纸片的特征。
这些特征包括碎纸片的形状、颜色和纹理等。
形状特征提取为了提取碎纸片的形状特征，可以通过计算碎纸片的边界和角度来获得。
首先，使用图像处理技术，如Canny边缘检测算法，将碎纸片的边缘提取出来。
然后，使用霍夫变换来检测碎纸片的直线和角点，从而计算出角度和边界。
颜色特征提取碎纸片的颜色特征可以通过计算图像的颜色直方图来得到。
颜色直方图表示了图像中每个颜色的像素数量。
我们可以使用像素级别的颜色分布来比较不同碎纸片的颜色特征，并找到相似的碎纸片来进行拼接。
纹理特征提取碎纸片的纹理特征可以通过计算图像的纹理描述符来得到。
纹理描述符是用于描述图像纹理的数值特征。
其中，最常用的纹理描述符包括灰度共生矩阵（GLCM）和局部二值模式（LBP）。
通过计算碎纸片的纹理描述符，我们可以比较不同碎纸片之间的纹理相似度，并选择相似的碎纸片进行拼接。
碎纸片的拼接策略在完成碎纸片特征提取后，接下来需要制定碎纸片的拼接策略。
拼接策略将基于碎纸片的特征相似度和拼接的整体目标来确定。
相似度匹配根据碎纸片的形状、颜色和纹理特征，我们可以计算两个碎纸片之间的相似度。
一种常用的相似度计算方法是使用余弦相似度，它衡量两个向量之间的夹角。
通过计算碎纸片之间的相似度，我们可以找到最相似的碎纸片来进行拼接。
拼接顺序在进行碎纸片的拼接时，需要制定一个拼接顺序。
一种常用的策略是首先选择与已拼接部分最相似的碎纸片进行拼接，然后逐渐增加已拼接部分的面积，直到最终完成拼接。
拼接约束为了保证拼接的准确性，我们需要制定一些拼接约束。
碎纸片的拼接复原摘要本文研究了碎纸片的复原问题。
对已有的碎纸片，我们利用Matlab求碎纸片边各侧边线的灰度值，通过最小偏差平方和法进行碎纸片间的相互匹配，中间加入人工干预进行筛选，将附件中的碎纸片全部还原。
之后，我们将该方法进行推广，可用以处理更复杂形状碎图片的的还原问题。
对问题一：首先假定附件一所给仅纵切的碎纸片的行文方向与各碎纸片两侧边线垂直，在此基础上先人工干预，根据碎纸片的剪切规范，甄选出原始图片的第一张和最后一张碎纸片，编号分别为008和006。
其次通过Matlab求出图片边线处各小网格点的灰度值，采用最小偏差平方和法，对编号008碎片右边线处的灰度值和其它碎纸片的左边线处的灰度值进行对应网格点的数值匹配，找到最匹配的碎纸片。
附件二碎片的处理进行了类似处理，给出的复原图片见附表4。
对问题二：附件三文本既纵切又横切，同样我们假设所给附件三中碎纸片的行文方向与碎纸片的上下左右边线分别平行或垂直。
在问题一的算法基础上，通过Matlab求出各碎纸片的4条边线的边界灰度值，然后利用最小偏差平方和法，对上下左右四边进行灰度值匹配，当结果多个时，我们进行了人工干预。
附件四依照附件三的方法类似处理，最终的复原见附表7和附表9。
对问题三：附件五中的图片既纵切又横切而且是正反面。
我们参照问题一、二的处理方法，加入反面的灰度值测算，随机选择一张碎纸片与其他碎纸片进行遍历匹配，得出4张匹配的碎纸片后，以这4张碎纸片为下一起点，扩张匹配，最终给出的复原图见附表12。
为适应更一般的情形，我们在模型改进部分，给出了当碎纸片的文字行文方向与碎纸片两侧边线不垂直时的处理方法（只处理了边线为直线的情形）。
首先是通过测算出的碎纸片灰度值确定出碎纸片的边缘线，其次定出碎纸片边缘线附近网格点的灰度值，最后完成边线的的匹配。
关键词：人工干预灰度矩阵灰度值最小偏差平方和法一问题重述1.1问题背景纸片文字是人们获取和交换信息的主要媒介，尤其是在计算机技术飞速发展、数码产品日益普及的今天。
碎纸片的拼接复原问题摘要为解决碎纸片的拼接复原问题，我们通过定义差异度指数、高度差，建立0-1规划模型，使用聚类分析、MATLAB搜索算法和人工干预等相结合，得到了所有附件复原序号和复原图片。
针对问题一，首先提取附件1、2中所有碎片左侧和右侧边缘灰度，通过任意列碎片右侧和任意列碎片左侧的边缘灰度差值可以定义差异度指数，从而得到差异度特征矩阵，然后建立0-1规划模型，以第i张碎片右侧与第j张碎片左侧差异度最小为目标函数，以第i张碎片右侧与第j张碎片左侧是否相连为决策变量，以每张碎片右侧一定与某张碎片左侧相连、每张碎片左侧一定与某张碎片右侧相连为约束条件。
算法为先提取任意张碎片边缘灰度值，得到差异度矩阵，带入规划模型中，通过LINGO软件找到中英文碎片的拼接方法，得到复原序号如表一、表二，从而得到出中文与英文复原图片。
表一:中文碎片的复原序号表二：英文碎片的复原序号片拼接方法。
结果表明两种方法得出的中英文复原顺序相同，复原图片相同，同时人工检验中英文复原图片中无明显语法、单词错误，证明复原图片准确。
针对问题二，由于每张碎片有左侧、右侧和上侧、下侧，与问题一相同，可以定义两个差异度指数，建立双目标0-1规划模型。
但由于差异度矩阵过大，决策变量复杂，我们又建立了改进的简化模型，定义高度差，运用聚类分析方法，按照高度不同将所有碎片分为18类，然后再以第j块碎片左侧与第i块碎片右侧的差异度最小为目标函数，以第i块碎片右侧与第j块碎片左侧是否相连为决策变量，以每块碎片右侧一定与某块碎片左侧相连、每块碎片左侧一定与某块碎片右侧相连，满足高度差阈值为约束条件，建立单目标0-1规划模型。
算法为先提取任意块碎片边缘灰度值和高度，得到差异度矩阵，编程将中文碎片按高度分为18类，人工干预分为11行，再利用问题一中碎片纵向复原方法，得到中文复原序号，画出中文复原图片。
（英文复原模型相似，仅高度差阈值不同）针对问题三，对于双面英文碎片的复原问题，我们提出了单词残缺程度的定义，定量的描述了英文碎片的特征信息，构成了算法的核心内容，运用编程和人工干预将碎纸片分为11类，每类19个碎片，在此基础上利用前两问所建的0-1规划模型，再加上双面的一些约束条件，得到双面英文复原序号，并绘出英文双面复原图片。
碎纸片的拼接复原数学模型的构建摘要院本文讨论在碎纸机以不同方式破碎纸片的情况下建立碎纸片的拼接复原模型，以解决碎片数量巨大时人工拼接的难题，本文建立了三个具有针对性的模型。
模型一：方差分析法下的碎纸片拼接模型。
在以纵切方式破碎纸片的情况下，提取碎纸片左右边缘的灰度列向量，利用碎纸片边缘处为单边同宽空白区域的特殊性对碎纸片进行定位，再利用方差分析法和欧式距离解决了纵切碎纸片的拼接复原问题。
模型二：文字行间距一致性的碎纸片拼接模型。
以纵横方式破碎纸片，利用同行文字行间距一致性的主要特性可解决横向碎纸片的拼接复原问题，简化了模型，将离散的像素灰度矩阵平均化处理，进而利用欧氏距离对碎纸片进行匹配，得到了碎纸片复原后的完整图片。
模型三：二值化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软件，首先对图像进行数据化处理和标准化处理。
一：只有纵切情况，且所有的切口都切到了字，建立差和法检验模型，应用枚举法，用MATLAB计算任意两张碎纸片灰度矩阵中最左、最右列灰度值的差方和，将差方和最小的两张碎纸片拼接在一起.中间不经过人工干预。
最后得到中英文碎纸片的排列顺序，从左到右依次为：中文：08,14,12,15,03,10,02,16,01,04,05,09,13,18,11,07,17,11,06;英文：03,06,02,7,15,18,11,00,05,01,09，13,10,08,12,14,17,16,04。
二：首先对中英文碎纸片分别提取行间距相同和英文字符三线分割后空白带宽相同的特征，根据这些特征我们初步筛选出可能处于同一“行”的碎纸片，为了不与原文中书写的字的“行”发生误会，我们称其为组，然后分别依次进行“组内调整和组间拼接”工作。
中文文件拼接复原过程中采用差方法计算出关联度，然后利用改进的匈牙利算法选出全局中的局部最佳拼接，再结合人工干预，实现组内拼接和组间拼接；英文文件拼接复原与中文的略有不同，首先分析图像选出可能成为最左边的碎纸片，采用以相关系数法，，从而从左向右拼接，最后完成拼接复原。
下面分别选取中英文碎纸片拼接复原后的第一行碎纸片的序号作为样品。
按照从左到右的顺序：中文：49，54，65，143，186，2，57，192,178,118,190,95,11,22,129,28,91,188,141；英文：191，75,11，154,190,184,2,104,180,64,106,4,149,32,204,65,39,67,147。
三：考虑到问题二中对英文碎纸片的拼接所提取的特征在大量数据时会产生分组效果不佳的问题，采用新的方法重新提取行间距特征：靠近碎片底端最近的一行中完整字母集中分布的最低点到碎纸片底端的距离。
并在求解模型基础上通过定义匹配错误率。
建立利用双面打印文件的其中一面作为拼接面，另一面作为验证面对分组结果交叉检验的拼接检验交互模型，从而有效完成并验证拼接双面打印文件的拼接复原任务。
关键字：差方法匈牙利算法相关系数行间距特征拼接检验交互模型1一、问题重述破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。
当碎片数量巨大，人工拼接很难在短时间内完成任务。
随着计算机机术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。
1. 对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件 1、附件 2给出的中、英文各一页文件的碎片数据进行拼接复原。
如果复原过程需要人工干预，请写出干预方式及干预的时间节点。
复原结果以图片形式及表格形式表达。
2. 对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。
如果复原过程需要人工干预，请写出干预方式及干预的时间节点。
复原结果表达要求同上。
3. 上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。
附件 5给出的是一页英文印刷文字双面打印文件的碎片数据。
请尝试设计相应的碎纸片拼接复原模型与算法，并就附件 5的碎片数据给出拼接复原结果，结果表达要求同上。
二、问题分析本题属于图像处理类问题。
可以采用 MATLAB工具处理图像的灰度矩阵或二值矩阵。
问题一，问题要求我们复原碎纸机仅在纵切情况下破碎的纸片，分析附件中所给的碎纸片图像，发现经纵切后，所有的碎纸片纵切都有被切开的字，碎片没有只有空白的接口，而且碎纸片复原后上、下、左、右边框为白色。
于是可以先找出所有纵切碎片中左边框或右边框为空白碎片的个数。
在确立左边框后采用差和法依据该碎片右边界与其他碎片左边界的相关程度进行匹配拼接。
问题二，与问题一不同，问题二中既有纵切又有横切，常规的差和法不能满足碎片多，相关程度比较小的问题二的求解要求。
此外，中英文的特征差别在碎片变小时也会逐渐突出，因此，文字特征提取、参考点的选取以及如何建立模型计算图片边界相似程度和求解至关重要。
由于碎片中字与字之间有固定间距，可以采用合理的方法构建间距特征提取模型确定各行包括的碎片，对于行内 19 个碎片利用相关性检测得出表征碎片左右边界的相关系数大小是一种有效解决问题的方法。
匈牙利算法是解决图论问题中的常用算法，此处对匈牙利算法加以改进可以方便的调整各行内碎片的连接形式。
在确定各行碎片连接形式后再考虑上下边框、段间间距等因素进行行间的排列。
问题三，在第二问的基础上要求我们实现双面打印文件碎纸片的拼接复原，考虑到问题二中针对英文碎纸片的拼接所提取的特征，沿用问题二的求解思路，将英文碎纸片中的字母分割成三格，计算各格之间的比例关系即像素长度，从而确定英文字体的行间距。
据此特征检测碎纸片之间的匹配程度，并加以拼接，我们考虑利用双面打印文件的其中一面作为拼接面，另一面作为验证面完成复原工作及对复原结果的检验。
三、基本假设1、假设碎片是理想的，没有遗失和磨损2、假设图像数值化像素采样误差可以忽略3、假设正反面文字是对齐的4、假设对于同一个文件行间距是固定的5、假设边距大于段间距，段间距大于行间距6、假设人工干预不会导致错误的结果四、符号说明D 最佳匹配值Xj每行中某个碎纸片灰度矩阵的最右列yj每行中某个碎纸片灰度矩阵的最左列mi各行中第 i 个碎纸片二值矩阵中全为零的行pj每行某碎纸片二值矩阵中第 j 个行的所有值N 误差度量值d 左边距，单位：像素W 匹配准确率K 一次分组后拼接面与检验面重复的碎纸片个数V 一次分组后拼接面与检验面包含的碎纸片个数五、图像的预处理5.1数值化由于目前的计算机只能处理数字信号，我们得到的照片，图纸等原始信息都是连续的模拟信号，必须将图像进行预处理，即把连续的图像信息转化为数字形式。
可以把图像看作是一个连续变化的函数，这就要经过数字化的采样与量化。
图像采样就是按照图像空间的坐标测量该位置上像素的灰度值。
方法如下：对连续图像f(ݔ, ݔ)进行等间隔采样在(ݔ, ݔ)平面上，将图像分成均匀的小网格，每个小网格的位置可以用整数坐标表示，于是采样值就对应了这个位置上网格的灰度值。
若采样结果每行像素为 M个，每列像素为 N个，则整幅图像对应一个 M*N 数字矩阵。
这样就获得了数字图像中关于像素的两个属性：位置和灰度。
位置有采样点的两个坐标确定，也就对应了网格的行和列，而灰度表明了该像素的明暗程度。
应用 MATLAB 可以自然的得到如下形式的数字矩阵：g(1,1) ⋯g(1, N)g = [ ⋮⋱⋮]g(, 1) ⋯g(M,N)矩阵中的元素称为像素，每个像素都有x 和y 两个坐标，表示其在图像中的位置，其值称为灰度值，对应原始模拟图像在该点处的亮度。
量化后的灰度值代表了相应的色彩浓淡程度，本题中我们使用 256 色灰度等级，“0”表示纯黑色，“255”表示纯白色，中间的整数数字从小到大表示由黑到白的过渡色。
5.2标准化将图像数值化后的灰度值采用 256 灰度等级，“0”表示纯黑色，“255”表示纯白色。
由于图像在获取中灰度值将受影响，故我们需要对图像进行标准化。
六、问题一6.1模型的建立1.灰度相关匹配理论依据：如果是一个整体分裂成的两个碎片，那么两个碎片裂口对应的部分的颜(对灰度图像而言，就是灰度信息)会有很强的相关性，这是碎片间除轮廓信息外最重要的信息之一。
灰度矩距离最短的两条边之间的相似性最高，相似度最大的两边可以作为匹配边，同时排除其他干扰匹配对。
问题一中我们采用如下差方和公式：MD = min ∑(xj−yj )2j=1其中ݔ表示单个碎纸片图像的灰度矩阵的最右列，ݔ表示其余任意一个碎纸片图像的灰度矩阵中的最左列，D为最佳匹配值。
2.模型流程图分析附件中所给的碎纸片图像，发现经纵切后，所有的碎纸片纵切都有被切开的文字，碎片没有只有空白相接的接口，而且碎纸片复原后上、下、左、右边框为白色，于是可以根据灰度值的大小判断出纵切碎片中左边框和右边框。
如在确立左边框后采用差和法，依据该碎片右边界与其他碎片左边界的相关程度进行匹配拼接。
可建立如下的模型流程图：6.2模型的求解及结果1.求解过程第一步：图像预处理，应用 MATLAB 软件将碎纸片图像转变为 19 个 1980*72 灰度矩阵。
矩阵中元素值为 0 至 255，代表由黑到白的颜色变化，其中，“0”表示纯黑色，“255”表示纯白色。
第二步：取出每个灰度矩阵的最左边一列，判断该列元素值是否全为 255，若其值全为 255，即其最左边全为空白，则说明此碎纸片应在原文件的最左边。
第三步：以上述碎纸片的右边界为依据，根据如下公式计算其他碎纸片左边界与之的最小差方和 D1980D = min ∑ (xj−yj)2j=1得到其排列顺序，从左到右依次为8，14，12，15，03，10，02，16，01，04，05，09，13，18，11，07，17，00，06。
由于在仅有纵切情况下中英文打印文件字体特征基本相同，可以采用相同的采取方法，因此此方法也同样适用于处理附件 2 中的英文文件碎纸片。
2.求解结果表 1：中文碎片复原顺序表格：08 14 12 15 03 10 02 16 01 04 05 09 13 18 11 07 17 00 06表 2：英文碎片复原顺序表格03 06 02 07 15 18 11 00 05 01 09 13 10 08 12 14 17 16 04图 1，中文拼接复原图片图 2，英文拼接复原图片6.3模型的结果分析1. 准确率因为所给的碎片是一列一列的，所以我们只需要验证第一行是对的就可以说明拼接结果的正确的。
对于中文碎片拼接后第一行为“城上层楼叠巘。
城下清淮古汴。
举手揖吴云，人与暮天俱远。
魂断。
”出自宋代大词人苏轼的《如梦令●题淮山楼》，根据内容判断拼接是正确的。
对于英文碎片拼接后通过阅读其内容，可以确定拼接是正确的。
所以，对于在这一问中我们建立的模型是准确可行的。
2.不需人工干预的原因分析(1)文件仅纵切，且均切割到文字，所以各列有较大的相关性，匹配成功率较高。
(2)最左边为空白的碎纸片只有一个，且容易确定。
(3)匹配过程中最小差方和 D可唯一确定。
七、问题二7.1中文文件碎纸片的拼接复原7.1.1问题分析问题二，与问题一不同，问题二中既有纵切又有横切，常规的逐个比对不能满足碎片多，相关程度比较小的问题二的求解要求。
因此，文字特征提取、参考点的选取以及如何建立模型计算图片边界相似程度和求解至关重要。
