基于规则碎纸片文字特征的拼接复原算法

切碎文字图片拼接还原的算法设计与实现发布时间：2021-04-12T13:14:33.793Z 来源：《中国建设信息化》2020年24期作者：储成伟1 [导读] 对重要文件的拼接复原，传统上都由人工完成，拼接准确率虽然高但是效率很低。

储成伟11 武汉学院信息工程学院摘要：对重要文件的拼接复原，传统上都由人工完成，拼接准确率虽然高但是效率很低。

本文旨在建立模型，利用计算机编程加少量的人工干预实现碎纸片的拼接复原。

全等矩形破碎文字图片的拼接还原技术是一种特殊的图片拼接复原技术，它处理的图片具有明显几何规律而不能采用边沿几何形状识别拼接还原。

对于规律性较强的图片，先通过数据挖据，得到图片中所有文字占据连续像素行的平均行数，图片中两行文字间的间距（行距）占据的连续像素行的平均行数，以及每张图片所包含的文字和行距之间的交替规律即行信息向量，并对图片边沿进行二值化处理。

关键词：破碎图片；贪心算法；数据挖掘；模式识别依托武汉学院大学生创新训练项目，指导老师李丽容，湖北省教育科学规划课题-重点课题：2019GA066 1 引言破碎文件的拼接还原在复原司法物证、修复历史文献以及获取军事情报等领域都有着重要的应用。

一般地，由人工完成拼接复原，虽然准确率很高，但效率却低。

尤其是当有数量巨大的碎片时，采用人工拼接复原几乎不可能在短时间内完成。

随着计算机技术的发展，人们可以利用计算机实现破碎文件的自动拼接还原，以提高拼接复原效率，这样就可以把人从繁重的工作中解放出来，不再需要人工从大量碎纸堆中一块一块的比对寻找匹配的碎片，减轻了人的工作量和劳动强度，还能够让需求者在极短的时间内得到想要的结果，迅速准确的得到复原结果。

还原技术采用贪心算法，对图片进行拼接还原。

先从图片的行信息向量中筛选出所有可能成为第一行的图片，对这些图片的行信息向量进行聚类分析，得到第一行的所有图片的序号。

用同样的方法得到最左侧所有图片的序号，对这两个集合取交集，就得出了位于第一行第一列（左上角）的图片。

碎纸片的拼接复原摘要碎纸片的拼接复原是一门借助计算机，把大量碎纸片重新拼接成初始纸张的技术。

针对问题一，本文首先利用碎纸片图像灰度矩阵的边缘矩阵，建立了两个碎纸片之间的匹配度函数，求得了每一张图片之间左右边缘匹配度矩阵。

然后根据左边边缘位置的碎片的左边空白部分最多的特点，确定了左边位置的碎纸片。

接着根据拼接碎纸片的拼接复原时，所有碎纸片匹配度之和取极大值的原则，采用贪心算法，得到了所有碎纸片的初始位置，拼接复原了附件1和附件2中纸片。

针对问题二，由于附件3碎片数量太多，并且碎片的拼接复原，是一个以碎纸片总匹配度为目标函数的组合优化问题。

所以本文采用遗传算法将碎纸片的编号作为基因，并将基因均匀分成19段，按顺序每一段对应一个初始纸片列位置，进行了求解。

然后，根据边缘碎纸片某些边的空白部分多的特征，对初始基因进行了优化。

接着，根据碎纸片的黑色像素密度不同的特点，将碎纸片分成三类，根据同类纸片优先匹配的原则，对遗传算法的运行过程进行了优化，拼接复原了附件3和附件4中纸片。

针对问题三，随着碎纸片量的增多，计算量急剧增加。

在上述拼接复原碎纸片的基础上，又引进了同行位置碎纸片的上部（或下部）空白位置宽度相近的聚类思想。

先对每个类内部拼接，在合并所有类并做一次整体拼接。

由于时间有限，我们未能完成最后一次的整体的拼接，但我们会在比赛后继续探究。

关键词：边缘矩阵匹配度函数遗传算法聚类一、问题重述碎片拼接实际用途已经越来越广泛，传统上拼接复原工作由人工完成，碎片拼接的准确率较高，但效率很低。

并且当碎片数量很大时，人工短时间内拼接出来几乎是不可能的。

所以开发碎纸的拼接技术，以提高拼接复原效率已成为越来越多人的期望。

现在,在碎纸片是规则的情况下，题目要求我们在以下条件建立碎纸片拼接复原模型和算法。

1.来自同一页印刷文字文件（中文、英文各一页）的碎纸机破碎纸片（仅纵切）拼接复原，并将附件1和附件2复原。

2.对碎纸机既纵切又横切文件的情形，将碎纸片拼接完整。

基于文字信息的碎纸片拼接复原算法鲁嘉琪【摘要】The character characteristics of different paper pieces are analyzed in this paper. Several algorithms were deve-loped under reasonable assumptions,which synthesized multi-directional recursion,detection of space between ranks,character pattern recognition and artificial intervention when necessary,and successfully realized the recovery of torn paper pieces. The combination of various algorithms reduced the probability of error splicing effectively and improve the stability of the recovery file scheme. The experimental results after splicing show that the actual splicing effect of the scheme is very satisfactory.%基于不同碎纸片的文字特征进行分析，在合理假设下开发了多种算法，这些算法综合了多向递推、行列间距检测、字符模式识别与必要时的人工干预等多种手段，成功解决了碎纸片的拼接复原问题。

同时，多种算法相互结合也有效地降低了错误拼接的概率，提高了复原文件方案的稳定性。

拼接完成后的试验结果表明该方案的实际拼接效果非常理想。

【期刊名称】《现代电子技术》【年(卷),期】2014(000)004【总页数】4页(P28-31)【关键词】碎纸片拼接;文字信息;模式识别;文字特征分析【作者】鲁嘉琪【作者单位】中国政法大学，北京 102200【正文语种】中文【中图分类】TN911-34破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。

基于规则碎纸片文字特征的拼接复原算法承诺书我们仔细阅读了《全国大学生数学建模竞赛章程》和《全国大学生数学建模竞赛参赛规则》（以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛网站下载）。

我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。

我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。

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

如有违反竞赛章程和参赛规则的行为，我们将受到严肃处理。

我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。

我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B我们的参赛报名号为（如果赛区设置报名号的话）：所属学校（请填写完整的全名）：中国人民解放军第三军医大学参赛队员(打印并签名) ：1. 王家*2. 黄嘉*3. 邵*指导教师或指导教师组负责人(打印并签名)：周*（论文纸质版与电子版中的以上信息必须一致，只是电子版中无需签名。

以上内容请仔细核对，提交后将不再允许做任何修改。

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

）日期：年月日赛区评阅编号（由赛区组委会评阅前进行编号）：编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：基于规则碎纸片文字特征的拼接复原算法摘要目前对于碎纸片的拼接问题，大多数方法是基于不规则碎纸片的几何边缘特征进行拼接，而本题是基于规则碎纸片的文字特征进行的。

我们首先提取各碎纸片的像素边缘特征，然后通过寻找最大匹配率和少量人工干预，得到碎片拼接方案。

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

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

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

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

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

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

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

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

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

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

碎纸片的拼接复原模型摘要本文针对破碎纸片形状规则和碎片间无有效重叠区域等特点，选取了信息熵、差方和、欧氏距离、相关系数、互信息和灰色斜率关联度作为碎纸片之间的相似性判别准则，给出了碎纸片拼接复原模型和算法，解决了破碎纸片的拼接复原问题．对于问题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。

规则碎纸片的拼接复原模型摘要图像碎片复原技术是一项综合的并具有实用价值的研究课题,它的最终目的是要从大量的任意图像碎片中找出真正符合实际的匹配对,并根据这些匹配关系将相邻的图像碎片拼合起来重现图像的原貌。

图像碎片的复原工作是以实际碎片为参考依据进行的,建立能够准确描述实物的计算机模型是图像碎片复原工作的关键步骤之一,对碎片复原的后续工作有基础性的作用,模型建立的准确性和复杂性将影响到后续工作能否顺利进行下去。

本文利用边缘特征点匹配，相关系数，广度搜索法等方法建立了规则碎纸片的拼接复原模型。

对于问题一，我们利用边缘特征点匹配的方法，先提取边缘特征点的灰度矩阵，再寻找矩阵相似度最大的碎片实现匹配。

对于问题二，我们采用了基于文字特征的半自动拼接方法，通过找到相交点距离相等的最大个数来确定匹配图像。

对于问题三，我们提取了各边的像素作为灰度矩阵，用X ，Y ，H ，L 确定目标函数min d （,i j X Y ）=i j X Y -，min d （,i j H L ）=i j H L -，运用广度搜索算法找出最佳匹配项。

最后，本文还对模型推广进行了进一步讨论，分析了模型的优缺点，提出了改进模型的方法和思路。

关键词：图像拼接；规则碎片；图像复原；灰度矩阵；广度搜索算法；特征匹配；自动拼接；图像分割；匹配准则一．问题的重述破碎文件的拼接在司法物证复原、历史文献修复及军事情报获取等领域都有重要的应用。

传统拼接复原工作由人工完成，准确率较高，但效率很低。

随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。

碎纸自动拼接技术是图像处理与模式识别领域中的一个较新但是很典型的应用，它是通过扫描和图像提取技术获取一组碎纸片的形状、颜色等信息，然后利用计算机进行相应的处理从而实现对这些碎纸片的全自动或半自动拼接还原。

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

一种碎纸片自动拼接复原算法借助向量夹角模型，分析碎纸片间边界向量的关系，并在适当的人工干预下，提出一种碎片自动拼接复原算法。

仿真实例显示，该算法具有实现规则碎片自动拼接复原功能。

标签：向量夹角人工干预碎纸片拼接复原像素值碎纸片的拼接复原在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。

一般地，碎片拼接复原工作由人工完成，准确率较高，但效率低且工作量大。

特别是当碎片数量较多时，人工拼接很难在短时间内完成任务。

随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。

本文针对来自同一文件且形状大小相同的碎纸片（碎纸机破碎的纸片，形状大小相同。

且破碎文件的方式有两种：第一种是纵切；第二种是既纵切又横切），借助向量夹角模型，分析了碎纸片间边界像素值的关系，并提出一种碎片自动拼接复原算法，在Matlab平台下结合人工干预，实现了碎纸片的自动拼接。

三、仿真实例本文数据来源于中国数学建模网《2013年高教社全国大学生数学建模竞赛》B题附件。

附件1和附件2中碎片的破碎方式为纵切，故可由算法设计①中的步骤实现碎片的自动拼接复原。

表3-1-1列出了19张碎片间的最佳匹配度。

从表3-1-1中可以看出，碎片7与碎片9的匹配度为1，即碎片7的右边界向量和碎片9的左边界向量完全相等，但是算法设计①中第一步得到排序第一的碎片为碎片9，排序倒数第一的碎片为碎片7，因而得到附件1碎片的拼接顺序为：9→15→13→16→4→11→3→17→2→5→6→10→14→19→12→8→18→1→7即附件1中图片名称顺序为：008→014→012→015→003→010→002→016→001→004→005→009→013→018→011→007→017→000→006附件2类似附件1的方法，可按算法设计①能实现碎片的拼接复原附件。

附件3、附件4和附件5中碎片较多，所以相关数据也较多，按算法设计②能实现碎片的拼接复原，这里不再重述了。

基于角边特征的纸质碎片自动拼接复原算法纸质文件的碎片化是一种常见的情况，它可能产生于意外或者企图销毁纸质文件。

在这种情况下，对于需要原样留存或者还原的文件来说，就需要进行纸质碎片的拼接。

传统的拼接方法需要大量的人工干预，所以自动化的纸质碎片拼接技术变得越来越重要。

本文中所介绍的算法主要基于角边特征，即在拼接碎片的过程中利用碎片间的角或者边进行匹配。

下面详述这种算法的流程：1. 数据预处理在进行自动化拼接之前，需要预处理纸质碎片的原始数据。

这个步骤主要会包含以下几个过程：a. 扫描纸质碎片把纸质碎片扫描为数字图像。

b. 分割碎片对于每个纸质碎片，用图像分割算法进行分割为形状几乎一致的小片。

c. 提取特征点对于每个小片，通过角检测、边检测等算法提取其关键点和特征信息。

将分割后的碎片重新拼接成原始文档的过程可以分为两级匹配。

第一级是碎片之间的匹配，第二级是于大量数据集中匹配。

a. 碎片之间的匹配将两片待拼接的碎片中的特征点逐点配对，并计算它们之间的相似度，以求出它们之间的最佳匹配。

最佳匹配的可信度将根据特征点的数量、位置和相似度显示出来。

b. 大量数据集中的匹配在对大量数据集的拼接时，可以使用在之前所有已拼接的碎片上提取的特征点来匹配。

这个过程主要有以下两个步骤：1）基于广度优先算法和最小距离匹配策略，自动搜索与待拼接碎片相似的碎片。

2）将搜索到的待匹配碎片与待拼接碎片之间的特征点逐一配对，计算它们之间的相似度。

a. 确定碎片拼接的顺序：在特征点匹配的基础上，可以构建一个图形结构，找到一个合适的拼接顺序可以使得拼接成功的概率最大化。

b. 纸质碎片的拼接：利用拼接顺序，将碎片逐一拼接，同时可以用叠加的方式调整位置和旋转角度等误差，以使得整张纸质文件恢复到原始状态。

4. 纸质文档还原纸质文档还原是整个拼接过程中的最终目标。

在上述过程中的最后一步拼接完成后，将得到一张完整的纸质文档。

如果还原结果不够理想，可以反复调整拼接顺序、调整位置偏差以及旋转角度等因素，直到得到最终的还原结果。

基于角边特征的纸质碎片自动拼接复原算法
纸质碎片拼接复原是指通过对纸质碎片进行拼接，复原出原始图像或文本的过程。

在文化遗产保护、证据鉴定等领域具有重要的应用价值。

本文介绍一种基于角边特征的纸质碎片自动拼接复原算法，该算法能够自动识别碎片之间的拼接关系，并实现高效准确地拼接复原。

算法的基本思路是通过提取碎片之间的角边特征来确定它们之间的拼接关系。

具体而言，算法首先对每个碎片进行图像预处理，包括灰度化、二值化、边缘检测等操作，以提取出碎片的角边特征。

然后，算法对每对碎片计算它们之间的角度差和边缘特征相似度，并根据这些特征值来判断它们是否具有拼接关系。

算法通过遍历所有可能的拼接组合，选择最优的拼接方案，完成纸质碎片的复原。

在角边特征的提取过程中，算法采用了多种经典的图像处理方法。

算法对图像进行灰度化处理，将彩色图像转换为灰度图像。

然后，算法对灰度图像进行二值化处理，将图像转换为黑白二值图像。

接下来，算法通过边缘检测算法（如Sobel算子、Canny算子等）提取出碎片的边缘特征，以便后续计算角度差和边缘特征相似度。

在拼接复原的过程中，算法通过遍历所有可能的拼接组合，选择最优的拼接方案。

为了提高算法的效率，可以采用一些优化策略，比如动态规划、剪枝等。

在拼接复原的过程中，算法还可以利用一些先验信息，比如碎片的形状、纹理等，来辅助拼接的判断和优化。

科学技术创新基于M A T LA B 的碎纸片拼接复原技术研究唐巧玲陈佳(内江师范学院,四川内江641100)1概述碎纸片自动拼接技术是图像处理和模式识别领域中一种典型的新型应用,通过扫描成像技术获得一组被撕开的纸张的形状和颜色,再由计算机获取相应的信息,并通过计算机对这些纸张进行全自动或半自动复原的技术[1]。

本文主要研究由竖条型碎纸机粉碎的碎纸片,因此每个碎纸片的边缘是齐整的,所以无法利用碎纸片的轮廓形状得到有价值的信息,只能利用碎纸片边缘的所承载的色彩信息,来获取有价值的信息,再经过一系列的处理,进而实现碎纸片的拼接复原[6]。

本文利用MATLAB 提取碎纸片图片对象,将其看成一个集合,在水平方向对比两个碎纸片的相似度,选出相似度最高的两个碎纸片拼接成新的碎纸片,对已拼接完成的一侧停止比较,只比较另一侧,直至拼接完成为止。

然后对计算机处理的结果进行分析,提高其匹配率[7-8]。

2碎纸片拼接技术的原理2.1图像预处理碎纸片自动拼接复原技术是图像处理和模式识别领域中的典型应用,这一项技术通过扫描与图像提取技术来获取碎纸片的颜色和形状等有用的信息,之后再利用计算机对提取的信息进行进一步的处理,从而达到碎纸片的全自动复原或者半自动复原的目的。

在碎纸片拼接复原过程中,最重要的就是图像的预处理和碎纸片的匹配,图像预处理就是把碎纸片转化成计算机可以识别和处理的数据,而碎纸片匹配是在这些处理后的数据基础之上进行的。

本文首先运用MATLAB 软件对碎纸片做图像预处理:调用函数imread 使图片转化成灰度矩阵,该灰度矩阵的每个元素为0到255的整数。

不同的数字代表不同的灰度级或者亮度,其中数字0表示黑色,数值255表示白色,而每个矩阵中的各个数据表示其对应碎纸片的一个像素,这些数据就展示了碎纸片的数字特征信息,本文通过分析碎纸片提取出来的数字矩阵的灰度信息,发现矩阵的第一列和最后一列,然后将碎纸片边缘转化生成的数字特征信息进行处理,并对每个矩阵进行两两比较,就可以找出相邻的碎纸片。

碎纸片的拼接复原摘要破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。

但是人工完成效率很低，所以引入计算机复原，计算机虽然准确率不及人工高，但是可以大大减轻工作强度。

本论文主要是对纸张形状为矩形切割规范并且纸张上的文字标准的碎纸片的拼接复原的研究。

问题一：首先根据图片的灰度矩阵找出第一张（最左侧）图片，根据小差值优先匹配依次排出相邻图片。

碎纸片复原后的顺序如附件一、二所示。

问题二：首先根据图片的灰度矩阵最左侧n列灰度值求和最大，可找出第一列（最左侧）图片，共11张。

根据“行间”的位置特征作为凝聚点进行聚类分析，将所有图片分为11类，即11行。

应用小差值优先匹配将这每行的图片进行拼接，得到11个行图片，再次应用小差值优先匹配把这11个行图片拼接成完整的图片。

碎纸片复原后的顺序如附件三、四所示。

问题三：同问题二方法一致，找出第一列（最左侧）图片（正反两面共有22张图片），将这些“行间”的位置特征作为凝聚点进行聚类分析，所有的图片分为11“大行”，将这些图片配对的正反面进行上边缘“粘接”处理，按照小差值优先匹配将这每行的粘接形成的19图片（如图一所示）进行拼接，得到11个行图片之后，再次应用小差值优先匹配把这11个行图片拼接成完整的图片。

碎纸片复原后的顺序如附件五所示。

观察上述三个问题的处理方法可知，三个问题的解决办法主干思想完全相同，都是小差值优先匹配解决，并且清晰简练。

但是由于问题的逐渐深入和复杂程度的增加，仅靠这一个简单的方法并不能在实际中解决问题，于是增加约束条件减小搜索范围，如：找出“行间”位置，并作为凝聚点进行聚类分析，然后就可以很大程度上减小出错的概率。

关键词：聚类分析、MATLAB R2012a、小差值优先匹配、灰度矩阵1、问题重述破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。

传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。

课程设计论文基于结构特征的碎纸片的拼接复原问题基于结构特征的碎纸片的拼接复原问题摘要碎纸自动拼接技术是图像处理与模式识别领域中的一个典型的应用，该技术通过扫描和图像提取技术获取一组碎纸片的形状、纹理及内容等信息，然后利用计算机进行相应理解从而实现对这些碎纸片的全自动或半自动拼接还原。

针对问题一，考虑到纵切的碎纸片所含有的信息量较大，利用图像处理中的信号匹配方法，结合左右两个碎纸片的灰度像素矩阵的边缘特征，建立基于结构特征的灰度匹配模型，对英文字母制定了灰度相似的配准规则，使待拼接的碎纸片边缘的对应行像素之差的平方和最小；而结合中文字符的横笔结构特征，对中文字制定了“横笔”匹配相似度的配准规则，并给出了最终的碎纸拼接图和拼接次序，拼接的正确率是100%。

针对问题二，对于既纵切又横切的情形，每一个纸片的边缘所含的信息量相对较少，故对中、英文碎片的拼接复原需各自建模分析。

首先利用“分而治之”的思想，将一个难以直接解决的大问题，分割成一些规模较小的相同问题。

对于中文碎片拼接复原，根据中文的方块特点，给出了中文的文字结构特征向量及其边缘像素的特征向量。

根据这些结构特征向量对所有的碎纸片进行粗分类，在此基础上设计了基于边缘特征的匹配规则集，对每一行从左到右在进行细匹配。

利用等距序列图像的快速拼接技术拼出左边第一列，基于灰度匹配，将图像转化为二值图像并对每行进行最优匹配。

先按照行配准，然后再进行列配准，最终匹配出误差最小的图像；对于英文碎片复原同样采取人工干预粗分类，粗匹配后，采用神经网络算法对碎片图像训练、学习构建BP网络对英文字母进行匹配识别，结合剪枝定界法实现英文碎片的拼接复原。

发现每行匹配率为78.85%，整篇匹配率大约为68.73%。

针对问题三，由于碎片数据均为双面打印文件，文字特征相同，仅用问题二中的方法产生的误差太大，仍沿用粗分类特点通过神经网络拼接、灰度匹配修正、人工干预，结合等距序列拼接技术实现单面拼接，然后验证反面的正确性并修正。

一种基于文字特征的碎纸片拼接算法设计刘秋菊;陈平;王仲英【摘要】提出了一种解决碎纸片拼接复原的方法.该方法首先把边界文字连续点的数目作为文字特征,然后使用连续八连通对边界文字灰度特征进行提取,通过特征提取得到基于灰度特征的连续点数目特征矩阵,最后,通过位置排序得到碎片的排序结果.按照算法设计思想编写C语言程序并针对实际例子进行拼接实验,实验结果表明,该算法符合设计要求.【期刊名称】《实验室研究与探索》【年(卷),期】2016(035)011【总页数】4页(P110-113)【关键词】纸片拼接;文字特征;连续八连通;特征矩阵【作者】刘秋菊;陈平;王仲英【作者单位】郑州工程技术学院信息工程学院,河南郑州450044;济源职业技术学院信息工程系,河南济源459000;河南经贸职业学院技术科学系,河南郑州450018【正文语种】中文【中图分类】TP391碎片拼接问题是数字图像处理中常常研究的问题。

碎片文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用，因此，通过计算机建立对于破碎文件自动拼接和恢复的算法与模型，具有很重要的现实意义。

一般对于碎片的拼接，针对碎片的破碎方式可以采用不同的算法完成拼接。

对于只有纵切方式的碎片要完成拼接复原，不能采用一般的根据边界几何特征拼接文件的方法拼接文件，使用边缘的尖点特征、尖角特征、面积特征等几何特征，搜索与之匹配的相邻碎纸片并进行拼接，这种基于边界几何特征的拼接方法并不适用于边界几何都是规则的碎片的拼接[1-8]。

对于不同横截面的中英文的碎片，首先，需要提取碎片特征，利用抽取到的特征，建立线性规划目标函数模型，利用图论中的二分图，整数0-1规划等对特征计算，使用特征之间的相似度或者距离作为拼接指标进行碎片的拼接，同时考虑到计算机的自动拼接可能带来的误差，加入人为的干预，提高拼接的准确率。

对于只有纵切方式的碎片要完成拼接复原，首先，对灰度图像进行全局阈值的二值化，得到二值化后图像的灰度值，同一个字符的共同特点是在它相应的位置和相应的领域内能够找到相应的笔段[9-11]。

基于聚类的规则文档碎纸片拼接模型明巍;鹿秀丽【摘要】针对碎纸机破碎文档后的规则碎纸片拼接问题，通过对碎纸片上边缘的灰度向量将文档分为上边缘为空白和非空白区域两大类，再分别以上边缘非空白区高度和空白区高度作为聚类参数，将纸片分为若干簇，在每一个簇中利用相邻两张碎纸片左右边缘向量相似度来进行拼接，得到若干横条的纸片，然后以行距和横条间上下边缘相似度为参数来将若干横条拼接为完整文档。

%In this paper, a method that the paper fragments of rule document is reconstructed is provided .The paper fragments is divided into the upper edge of the blank and non -blank area into two categories by the gray vector on theedges .Respec-tively, the height of the upper edge of the blank and non -blank area as the clustering parameters is calculated .The paper fragments will be divided into several clusters .The reconstruction of paper fragments depends on computing the similarity of the left and right edges of adjacent pieces of paper in each cluster .After getting the number of bars of the paper , the paper fragments of rule document is reconstructed by computing the similarity between the top and bottom edges of the bar .【期刊名称】《湖北师范学院学报（自然科学版）》【年(卷),期】2014(000)003【总页数】4页(P79-82)【关键词】K-均值聚类;碎纸片;拼接模型【作者】明巍;鹿秀丽【作者单位】湖北师范学院数学与统计学院，湖北黄石 435002;黄石市中心医院信息部，湖北黄石 435002【正文语种】中文【中图分类】TP391.41破碎文件的拼接在文物碎片的自动修复、虚拟考古、故障分析以及计算机辅助设计、医学分析、司法物证恢复[1～2]等领域有着重要的应用。

碎纸片拼接复原的算法设计于静;朱家明;吴朝阳;赵天梅【摘要】文章针对碎纸机切割的碎纸片拼接复原问题,首先将碎纸片的图片批量导入Matlab7.0中,并对其进行矩阵数值化处理,根据纸张边缘留白的特点找出最左边的图片,再根据汉字和英文字母的笔画的连续性构建碎纸片边缘矩阵的像素差值最小化模型,依次向右匹配相邻的碎纸片,最终得到完整的复原图.【期刊名称】《成都师范学院学报》【年(卷),期】2015(031)005【总页数】4页(P102-105)【关键词】拼接复原;差值最小化模型;Matlab7.0【作者】于静;朱家明;吴朝阳;赵天梅【作者单位】安徽财经大学统计与应用数学学院,安徽蚌埠233030;安徽财经大学统计与应用数学学院,安徽蚌埠233030;安徽财经大学统计与应用数学学院,安徽蚌埠233030;安徽财经大学统计与应用数学学院,安徽蚌埠233030【正文语种】中文【中图分类】TP391破碎纸片的拼接在文物碎片自动复原、虚拟考古、故障分析以及计算机辅助设计、医学分析、司法物证恢复等领域有着重要的应用。

[1]当要拼接的碎纸片数量巨大时可以想象完全凭借人工的方法对碎纸片进行拼接复原是一件十分费时费力的事情，由于科技的发展，借助软件和算法就可以大大地减少工作量，比如利用特征区域块分割技术来实现图像的拼接。

用灰阶Sobel算子通过引入衰减因子对图像进行边缘检测得到不失真的灰阶边缘图,然后将灰阶边缘图进行三次样条插值处理,使特征区域块边缘的定位达到亚像素级,提高了图像边缘检测的精度,对碎纸片进行准确的定位从而完成拼接。

[2]诸如此类，很多方法都是针对不规则的碎纸片，对其轮廓特征进行分析[3]，然后完成拼接复原的过程。

对于碎纸机规则切割的碎纸片来说根据上述两种方法显然是行不通的，因为碎纸片的形状基本完全相同，那么只能根据碎纸片上的文字特征进行拼接[4]，而由于计算机不具有人的思维，不可以对文字或者字母是否可以衔接为完整的字或字母进行判别，那么考虑必须通过对碎纸片边缘文字特征的转化来完成对碎纸片的拼接复原过程[5]。