碎纸片拼接

121数学学习与研究2014.11碎纸片拼接复原的数学模型◎杨武李博(江苏南京农业大学工学院210000)【摘要】本文对碎片的拼接复原问题，建立了碎纸片拼接模型，编写matlab 程序，利用人机交互指令实现碎片的快速拼接．对2013年“高教社杯”全国大学生数学建模竞赛的B 题中所给11x 19个碎片文件进行拼接．【关键词】碎片拼接模型；matlab ；灰度值矩阵；Kmeans 聚类；人机交互一、研究背景及意义近年来，大量政府机关、企事业单位采用碎纸机对废弃文件或失效的机密文件进行破碎，这种破碎方法产生的碎片多为规则的．这使得在进行破碎文件的复原拼接时，只能根据文字内容进行匹配，为此，本文考虑应用当前的计算机识别技术开发碎纸片的自动拼接技术，对所有碎片搜索和筛选，寻找能够在某种指标上匹配的碎片进行拼接．提高拼接复原效率，从而大大降低人工工作量和难度．对碎片自动拼接问题的研究，不仅具有广阔的应用前景，而且具有很强的理论意义．二、图像碎片预处理首先，利用matlab 图像处理功能对碎纸片进行图像预处理．即将碎纸片数字化，转化为图片文件的数据．即一个二维数组构成的灰度值矩阵，这个矩阵存储着一张碎纸片各个像素点的颜色值，其中255表示白色，0表示黑色，图片中颜色均处在黑白、或黑白之间，图片数字化后的数字范围在0 255之间．三、碎纸片拼接模型的假设1．假设碎片原文件都存在上、下、左、右的页边距，且边距大于行间距和列间距；2．假设相邻碎片间纸张信息的损失可以忽略不计；3．假设碎纸机是沿平行或垂直于文字的方向对纸张进行切割的．四、碎纸拼接模型的建立1．挑出每行最左边的图片：根据图片的边缘留有空白部分的特性，挑选出图片最左边存在空白部分的图片作为左边界的候选图片．方法实现：计算图片左边距留白宽度：即可用灰度值矩阵中左端竖列上全为255（即左侧完全空白）的连续列数度量，由matlab 检测出每张图片的留白宽度．留白宽度排序：对上面得到的留白宽度进行排列，取排在前面的11张图片作为拼接过程的起始碎片．2．图片按行分类：根据Kmeans 聚类算法，对碎片进行按行分类．分类实现：①先根据底端一行是否为纯空白将209幅图分为下端有纯空白行和下端有被截文字两类．②对于空白行一类，下端空白行数相同或相近的纸条属于原文件同一行；③对于下端有被截文字的一类，下端被截文字高度相同或相近的纸条属于原文件同一行．④分析确定好的最左端图片的特征，依此为11个聚类中心，利用matlab 程序分类．3．对同行碎片进行拼接①拼配原则———突变数将所有的碎片进行处理后得到灰度值矩阵，分别记作M i （i =1，…，n ）（n 为图片的数量）通过对每一张碎片的数据进行了分析，不难发现在每一张碎片上，同一行相邻两个点的像素值从0变为255或者从255变到0的比例仅有0．016%左右．将相邻两个像素值由0变到255或者由255变到0定义为一次突变．定义两张碎片的突变数如下：设Ｒi 为某张碎片M i 的最右侧一列像素值，L j 为另一张碎片M j 的最左侧一列像素值（Ｒi 和L j 均为180行的列向量），碎片M i 和M j 的突变数：T ij =∑180k =1flag （k ）ij ，flag （k ）ij =1Ｒ（k ）i －L （k ）j =2550Ｒ（k ）i －L （k ）j ＜{255，其中Ｒ（k ）i 表示向量Ｒi 的第k 个分量，L （k ）j 表示向量L j 的第k 个分量．②匹配过程以上面确定的最左边的碎片为起点，计算该碎片所在行的可能的碎片与其的突变数T．理论上T 值越小，两个图片的匹配的可能性最大，将T 进行由小到大的排序，在matlab 程序中让起始碎片优先与T 值最小的匹配，若匹配不成功再依次考虑T 值较大的，直至匹配成功．4．人工干预①人工干预时机：本文对209个已有碎片，分析发现若其余碎片与其的突变数仅有一个为0，则突变数为零的那个碎片一定与该碎片相匹配，一旦出现突变数均不为0，则需进行人工干预．②人工干预方法：为减少人工干预次数，做如下工作：1）计算碎片M i 灰度值矩阵最右一列Ｒi 与位于M i 行的其余碎片灰度值矩阵最左一列L j 的偏差平方和S 作为人工干预的指标：S =∑180i =1（Ｒi－L i ）2．2）对偏差平方和S 由大到小进行排序，将碎片的序号放入集合US 中，S 大的最有可能与碎片M i 相匹配③在matlab 程序中让碎片M i 依次与集合US 中的图片进行匹配，每次对两个图进行匹配时，令命令窗口弹出这两个图匹配在一起的图片，进行人工观察．通过对拼接处文字字形和语义的分析，人工检查该匹配是否合理．5．纵向拼接①观察11条已拼好的横切纸条，根据所有纸条的上边缘特征确定位于原文件顶端的横切纸条，并以该纸条为起始纸条．②根据起始纸条的下边缘灰度值特征，利用上述步奏拼出整张文件．五、模型的评价与改进1．模型的优点：模型采用突变数和偏差平方和作为评价函数评定碎片间邻边的相关度，高效而且实用．能大大减少人工干预的次数．2．模型的局限性：由于研究的是碎纸机产生的碎片．该模型只考虑了对多个相同的形状规则的碎片进行拼接，且当碎片的数量增加且单个碎片的文字覆盖率越小时，更易产生灰度分布情况相似的碎片，需要进行人工干预的次数会相应增多．六、结论本文对碎纸片的匹配原则和人工干预进行了探讨和研究，建立了一个可靠高效的数学模型，利用图片数字化后数值之间的分布规律和相关度引入突变值和偏差平方和作为评价指标，利用matlab 软件实现快速拼接．并为了提高拼接准确性，巧妙地使用人机交互指令进行人工的检测干预．【参考文献】［1］何鹏飞，等．基于蚁群优化算法的碎纸拼接．计算机工程与科学，2011，33（7）．［2］邓薇．MATLAB 函数速查手册．北京：人民邮电出版社，2010．［3］宋晓闯．基于灰度和几何特征的图像匹配算法研究．万方数据库，2013－09－13．。

碎纸片拼接复原的数学方法拼图游戏，一种看似简单却富含深度的游戏，给人们带来了无穷的乐趣。

然而，大家是否想过，这样的游戏其实与数学有着密切的？让我们一起探索碎纸片拼接复原背后的数学方法。

碎纸片拼接复原，其实就是一个计算几何问题。

在数学领域，欧几里得几何和非欧几里得几何是两个基本而又重要的分支。

欧几里得几何主要研究的是在平面上两点之间的最短距离，这是我们日常生活中常见的几何学。

而非欧几里得几何则研究的是曲面上的几何学，这种几何学并不符合我们日常生活中的直觉。

碎纸片拼接复原的问题就是一种非欧几里得几何问题。

在计算机科学中，图论是研究图形和网络的基本理论。

其中，图形遍历算法可以用来解决碎纸片拼接复原问题。

这种算法的基本思想是：从一点出发，尽可能多地遍历整个图形，并在遍历的过程中对图形进行重建。

对于碎纸片拼接复原问题，我们可以将每一张碎纸片看作是图中的一个节点，当两张碎纸片拼接在一起时，它们就形成了一个边。

通过这种方式，我们可以将所有的碎纸片连接起来，形成一个完整的图形。

在计算机科学中，碎纸片拼接复原问题被广泛应用于图像处理、数据恢复等领域。

例如，在数字图像处理中，如果一张图片被切割成若干块，我们可以通过类似的方法来恢复原始的图片。

在数据恢复领域，当一个文件被删除或格式化时，我们也可以通过类似的方法来恢复文件。

碎纸片拼接复原的问题不仅是一个有趣的拼图游戏，更是一个涉及计算几何、图论等多个领域的数学问题。

通过运用这些数学方法，我们可以有效地解决这个问题，从而更好地理解和应用这些数学理论。

在我们的日常生活中，我们经常会遇到一些破碎的物品，例如碎镜子、破碎的瓷器，或是碎纸片等。

这些物品的复原过程都需要一种科学的方法来帮助他们重新拼接起来。

这种科学方法就是碎纸片拼接复原技术。

碎纸片拼接复原技术是一种基于数学模型的方法，它通过比较碎纸片边缘的形状、纹理、颜色等特征，来找到碎纸片之间的相似性和关联性，从而将它们拼接起来。

纸张撕碎重新复原的方法
将纸张撕成小块后，可以试用以下方法重新复原：
1. 拼图法：根据纸张上的图案或文字的特征，将撕碎的纸张小块一一拼接在一起。

可以使用胶水或透明胶带将小块粘接在一起，直到整张纸张还原为完整的状态。

2. 粘贴法：将所有纸张小块按照纸张上的线条方向，粘贴在一张背景纸上。

根据纸张上的文字或图案特征，可以推测纸张的排列顺序。

3. 数字法：对每个纸张小块进行编号，然后根据编号重新排列纸张小块。

4. 计算机辅助法：使用扫描仪或相机将撕碎的纸张进行扫描或拍照，然后使用图像处理软件将图像还原，最后打印出完整的纸张。

请注意，纸张撕碎再复原的难度取决于撕碎的程度和纸张的特性。

有些纸张可能不易复原或需要特殊的技术手段，如复印纸、碎纸机处理后的纸张等。

碎纸拼接的原理碎纸拼接是一种将小碎纸片拼接成大型图案或图像的艺术手法。

它通常用于创作各种艺术品、手工制品、拼贴画等，也可以用于装饰室内空间、创意设计等领域。

碎纸拼接的原理主要包括选择纸片、设计构图、连接拼接、修整形状等几个关键步骤。

首先，选择纸片是碎纸拼接的基础。

纸片可以来自各种不同的来源，包括色纸、彩纸、报纸、零碎纸张等。

纸片可以有不同的颜色、质地、形状和大小，这样才能为碎纸拼接创造出丰富多样的效果。

选择纸片时，需要考虑图案或图像的要求以及拼接的布局。

其次，设计构图是碎纸拼接的关键。

设计构图需要考虑整体效果和视觉美感。

在设计中，可以运用各种构图原理如平衡、对称、重复、层次等，来达到艺术品或图像的理想效果。

构图时要注意元素之间的协调性和统一性，同时也要注意保留一些空白部分，以增强整体的效果。

连接拼接是碎纸拼接的核心步骤之一。

它决定了碎纸拼接作品的稳定性和持久性。

常见的拼接方法包括粘贴、缝合、编织等。

对于纸质较轻薄的纸片，可以使用胶水或胶带进行粘贴。

而对于较厚的纸片，则可以使用针线穿绕或编织的方法连接。

在拼接时，需要注意纸片之间的紧密结合，隐蔽连接处的处理以及整体的平稳性。

修整形状是使碎纸拼接作品更加完美的一步。

它涉及到对纸片轮廓进行修剪和整理，以使其符合拼接图案或图像的需求。

修整形状可以使用剪刀或刀具来进行精确的切割和雕刻。

这样可以使拼接作品的边缘更加平滑、整齐，并且与周围纸片相互衔接自然流畅。

除了以上的基本原理，还有一些注意事项需要考虑。

首先，在选择纸片时可以根据需要进行染色、染料处理或其他特殊工艺，以丰富图案的表现效果。

其次，拼接时可以尝试不同的排列组合和叠加方式，以创造出多样化的效果。

再次，在拼接作品的完成后，可以进行表面的涂饰、贴饰等装饰，增强艺术品的立体感和观赏性。

总之，碎纸拼接是一种富有创造力和艺术性的活动。

它利用碎片化的纸张进行拼接，通过选择、设计、连接和修整等步骤，创造出独特的艺术品。

1. 对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。

如果复原过程需要人工干预，请写出干预方式及干预的时间节点。

复原结果以图片形式及表格形式表达（见【结果表达格式说明】）。

用MATLAB 中的imread （）函数，把图片进行量化处理，得到对应能够反映出图像特性的矩阵。

每张图片是以72⨯1980的矩阵存在于matlab 软件中 量化即要求使用多大范围的数值来表示图像采样之后的每一个点。

量化的结果是图像能够容纳的颜色总数，它反映了采样的质量。

本文采用8位储存一个点，即相当于黑-白间可用0-255个状态进行描述，其中量化后的值越接近0，则表示该点的实际颜色越接近黑色；相反量化后的值越接近255，则表示该点的实际颜色越接近白色。

将19张碎纸片经matlab 数字化后得到19个72⨯1980的矩阵。

根据附件中碎纸片的编号顺序将19个矩阵合并为一个大小为)(19⨯721368⨯1980的矩阵，矩阵中的值，越接近0，则表示该值所对应点的实际颜色越接近黑色；相反该值越接近255，则表示该点的实际颜色越接近白色。

该矩阵如下A 所示：⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡212221212111=),(),(),(),(),(),(),(),(),(N M f M f M f N f f f N f f f A矩阵A 中各元素值即灰度满足条件为： ),(,),(N j M i j i f ≤≤1≤≤11≤≤0 （6.1.1）其中1980=M ，1368=N 。

假设第i 张纸片的第j 行第k 列数据为),(k j f i ，其中：⎩⎨⎧19≤≤172≤≤71-721980≤≤1)(i i k i j （6.1.2） 当71-72=i k 与i k 72=分别对应于第i 张纸片数字化后所对应矩阵的第一列与最后一列。

令)(,j w s i 为第i 张纸片的最后一列与第s 张纸片第一列第j 行数据的平方欧氏距离，该值为：271-72-72=)],(),([)(,s j f i j f j w s i s i （6.1.3）第一张碎纸片（未被纵切前最左边那张碎纸片）最左边边缘部分均为白色，经数字化处理后所对应矩阵的第一列数据值相同，在确定第一张后，采用平方欧氏距离。

承诺书我们认真阅读了《全国大学生数学建模比赛章程》和《全国大学生数学建模比赛参赛规则》（以下简称为“比赛章程和参赛规则” ，可从全国大学生数学建模比赛网站下载）。

我们完好理解，在比赛开始后参赛队员不可以以任何方式（包含电话、电子邮件、网上咨询等）与队外的任何人（包含指导教师）研究、议论与赛题有关的问题。

我们知道，剽窃他人的成就是违犯比赛章程和参赛规则的，假如引用他人的成就或其余公然的资料（包含网上查到的资料），一定依据规定的参照文件的表述方式在正文引用途和参照文件中明确列出。

我们郑重承诺，严格恪守比赛章程和参赛规则，以保证比赛的公正、公正性。

若有违犯比赛章程和参赛规则的行为，我们将遇到严肃办理。

我们受权全国大学生数学建模比赛组委会，可将我们的论文以任何形式进行公然展现（包含进行网上公示，在书本、期刊和其余媒体进行正式或非正式发布等）。

我们参赛选择的题号是（从A/B/C/D 中选择一项填写）： B我们的参赛报名号为（假如赛区设置报名号的话）：所属学校（请填写完好的全名）：楚雄师范学院参赛队员(打印并署名 ) ： 1.陈志明2.施明杰3.阮秀婷指导教师或指导教师组负责人(打印并署名 )：（论文纸质版与电子版中的以上信息一定一致，不过电子版中无需署名。

以上内容请认真查对，提交后将不再同意做任何改正。

如填写错误，论文可能被撤消评奖资格。

）日期： 3013年9月16日赛区评阅编号（由赛区组委会评阅行进行编号）：编号专用页赛区评阅编号（由赛区组委会评阅行进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国一致编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅行进行编号）：碎纸片的拼接还原算法及MATLAB实现纲要：关于只有纵切的情况，文章经过比较目前待拼碎片与节余碎片的信噪比psnr[1,3,4]的值来确立两碎片能否为毗邻碎片；拼接算法第一连续调用右拼函数直到拼接到原图右界限，而后连续调用左拼函数直到拼接到原图左界限，进而获得整幅还原图像；关于单面纵横交织切的情况，文章对第一采纳纵切拼接算法将碎片拼接成多幅横条图片，而后将各横条图片矩阵转置[2]，再次采纳纵切拼接算法拼接；两种情况的拼接，都存在人为参加；实考证明，我们的算法对纵切情况是有效的，对纵横切状况是可行的。