碎纸片的拼接复原数学模型1

碎纸片的拼接复原数学模型摘要首先对图片进行灰度化处理，然后转化为0-1二值矩阵，利用矩阵行（列）偏差函数，建立了基于最小二乘法的碎纸片拼接数学模型，并利用模型对图片进行拼接复原。本文主要研究了规则碎纸片的拼接复原问题。首先利用二值法、环形像素点匹配等算法建立基于像素点数值匹配模型，然后利用MATLAB软件对碎纸片像素点进行数字化处理，得到各碎纸片的像素点数值矩阵，再利用MATLAB软件编程进行矩阵特征优化匹配得到复原图。针对问题一，当两个数字矩阵列向量的偏差函数最小时，对应两张图片可以左右拼接。经计算，得到附件1的拼接结果为：9,15,13,16,4,11,3,17,2,5,6,10,14,19,12,8,18,1,7附件2的拼接结果为:4,7,3,8,16,19,12,1,6,2,10,14,11,9,13,15,18,17,5针对问题二：本文采用聚类分析方法建立优化模型。将所有图片的像素转化为矩阵，其次采用人工干预的方式找出第一行第一张碎纸片，然后将所有图片灰度二制化，将灰色像素值转化为黑色像素值，然后由上至下找出黑白像素的分界线，根据分界线位置的差异值最小聚合出第一行所有的图片，同理聚合出第一列所有的图片，将第一行所有图片利用问题一的拼接算法求解出第一行图片拼接顺序。以第一行第一张碎纸片下侧像素点与其他碎纸片上侧像素点像素匹配差异值最小为目标函数，依次穷举第一列所有的碎纸片，从而找出第二行第一张碎纸片。根据第一行排好顺序的碎纸片以及第二行第一张碎纸片，采用上下侧边缘像素匹配以及左右侧边缘匹配，依次找出并排列好第2行，其他行依理重复步骤（2）、（3）即可。完成匹配后，进行适当的人工干预即可确定碎纸片的复原图。（见附录3、4图11，图12）。最后，本文对所建模型的优点和缺点进行了客观的评价，认为本文研究的结果在图像拼接问题中有一定的参考价值。关键词：灰度处理，图像二值化，最小二乘法，聚类分析，碎纸片拼接一、问题重述碎纸片的拼接复原技术在司法鉴定、历史文献修复与研究、军事情报获取以及故障分析等领域都有着广泛的应用。近年来，随着德国“斯塔西”文件的恢复工程的公布，碎纸文件复原技术的研究引起了人们的广泛关注。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。对于一页印刷文档，针对不同的破碎方法，讨论下列三个问题：（1）将给定的一页印刷文字文件纵切，建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。（2）对于碎纸机既纵切又横切的情形，设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。（3）对于双面打印文档，研究如何进行碎纸片的拼接复原问题。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。要求尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果。二、模型的基本假设1、待拼接的碎纸片来自同一页印刷文字文件。2、待拼接复原的碎纸片是规整的矩形。3、模型中的碎纸片长度、宽度和面积都相等。4、附件中照片都是同标准拍摄。三、符号说明表1符号说明符号符号说明Gray灰度值r红色g绿色b蓝色A,B矩阵iD裁截距(=1,2,,209)iia裁截文字长度(=1,2,,209)iib行间距(=1,2,,209)iic裁截空白距离(=1,2,,209)iid字体高度(=1,2,,209)i四、问题分析将不规则的文档碎纸片进行拼接，一般是利用碎纸片的边缘曲线，尖点、尖角、面积等几何特征，搜索与之匹配的相邻碎纸片。但对于边缘形状相似的碎纸片，这种基于边界几何特征的拼接方法失效，拼接时不但要考虑待拼接碎纸片边缘是否匹配，还要判断碎片内的字迹断线或碎片内的文字内容是否匹配。本问题给定的碎纸片有以下几个特点：1、每一张碎纸片都是规整的矩形；2、所有的碎纸片的长度、宽度都相等，形状是完全一样的；3、每一张碎纸片里都包含着文字（汉字、英文），不存在空白的碎纸片；4、不同的碎纸片之间没有重叠部分。由于碎纸片的形状相同，因而不能针对碎纸片的几何特征建立数学模型；碎纸片间无重叠，也不能利用图像融合技术进行图像配准。根据上述分析，我们考虑将图片进行数字化处理，根据每张碎纸片上的边缘文字特征进行匹配，也就是利用图片边缘文字的像素进行最优化匹配。五、模型的建立与求解5.1问题一的建模与算法由于碎纸片本身不具有体现其拼接特性的数字特征，我们需要将其数字化、矩阵化，将问题转化为矩阵之间的相关性。5.1.1图片的灰度处理为了对碎纸片进行数字化，我们将图像进行灰度处理，取出图像中每一个像素点的灰度值。通过MATLAB的imread函数读入灰度图，dither函数转化为二值图，进一步得到图像数据０－１矩阵，每张图片对应一个198072的灰度矩阵。5.1.2图片的二值化处理将图片进行灰度处理以后，每个像素的灰度值介于0~255之间。灰度值不能直接用于文字图片的拼接，还须进行二值化处理。将图片放入直角坐标系，规定：若点的像素灰度值大于或等于T，该点用数值1表示，并将其设定为白色；若点的像素灰度值小于T，该点用数值0表示，并将其设定为黑色。由此得到像素点的二值化函数：1,(,),(,)0,(,),GrayxyTwxyGrayxyT其中，T为预先设定的全局灰度阈值。于是，每张图片的灰度矩阵转化为下列198072的0,1数字矩阵：1117219801198072aaAaa,其中1,1,0,0.ija代表空白的像素点代表有文字的像素点5.1.3最小二乘法1、图片左右拼接的数学模型设,AB分别表示左右放置的两张图片对应的数字矩阵，定义前一个矩阵的最后一列与后一个矩阵的第一列之间的偏差函数为：其中，(,72),(,1)AiBi分别表示矩阵,AB第72列和第1列的元素。对于给定的矩阵A，若存在矩阵B，使得A与B之间的偏差函数(,)fAB达到最小，则称A与B可以匹配，此时A与B对应的图片可以左右拼接。2、图片上下拼接的数学模型类似地，设,CD分别表示上下放置的两张图片对应的数字矩阵，定义上面矩阵的最后一行与下面矩阵的第一行之间的偏差函数为：其中，(1980,),(1,)CjDj分别表示矩阵,CD第1980行和第1行的元素。对于给定的矩阵C，若存在矩阵D，使得C与D之间的偏差函数(,)hCD达到最小，则称C与D可以匹配，此时C与D对应的图片可以上下拼接。我们称上述基于数字矩阵之间列（或行）距离的图片拼接模型为最小二乘法拼接复原模型。5.1.4算法与求解（一）算法思想第一步，对附件中的19幅图片分别进行灰度处理，然后取灰度阈值T=125，进行二值化，得到19个0,1数字矩阵，即图片的数字化。第二步，对上述19个数字矩阵进行检测，若存在一个矩阵的最左侧一列元素全是1，根据破碎图片的特点，则该图片即为从左边起第一张碎纸片，记为。第三步，计算1A与其余18张图片对应矩阵的列偏差值。若存在2A，使得12(,)fAA达到最小，则2A即位第二张图片。重复上述的步骤，依次得到所有碎纸片的排列，即可拼接成完整图片。（二）附件1、2的拼接复原结果附件1和附件2的拼接顺序如下表：（附件1的算法程序见附录一，复原图片见附录二；附件2的算法程序见附录三，复原图片见附录四）表2附件1拼接顺序91513164113172561014191281817表3附件2拼接顺序473816191216210141191315181755．2问题二模型的建立与求解5.2.1问题二分析该问题的目标是建立最合适的碎纸片拼接复原模型和算法来复原既纵切又横切的图片。问题二与问题一的区别在于碎纸片的切割由纵切变成了既有纵切又有横切的，所以问题一采用的人工干预找出第一张图片及简单地通过前后两张碎纸片的偏差值进行排列会产生相当大的误差，因此我们拟采用聚类分析方法建立优化模型来拼接附加3和附加4中的碎纸片。（1）我们人工干预选出一组上侧留有空白的图片作为备选图片，以及选取一张左侧跟上侧都留有空白的图片作为拼接的第一张图片，其次将选取的第一张图片为基准采用相应的拼合算法不断的向左向下匹配下一张图片。对于碎纸片上的文字处理可采取以下方式：图1：附录3碎纸片文字像素处理图首先用Matlab中的imread（）函数读取图片，将图片像素转化为相应的矩阵，其次将矩阵中处于0~255之间的数值所在的行的全部数值转化为0（即将所有灰色像素点转换为黑色像素点，并将其所在的行全部转化为黑色像素点），然后由上至下找出黑白像素的分界线，并依次将第一张图片的分界线与其他图片的分界线进行差异匹配，从而分类聚合出第一行所有的图片。（2）利用问题一中的拼接算法，以第一张图片右侧边缘像素点与第一行所有图片左侧边缘像素点像素匹配差异值最小为目标函数，建立优化模型，从而排列出第一行所有图片的顺序。（3）同理，将剩余图片像素矩阵中处于0~255之间的数值所在的列的全部数值转化为0，然后由左至右找出黑白像素的分界线，并依次将第一张图片的分界线与其他图片的分界线进行差异匹配，从而分类聚合出第一列所有的图片。（4）改进问题一中的算法，以第一张图片下侧边缘像素点与第一列所有图片上侧边缘像素点像素匹配差异值最小为目标函数，建立优化模型，从而确定出第二行第一张碎纸片，然后将第二行第一张碎纸片的右侧边缘像素点与待排图片左侧边缘像素点以及与上一行中对应图片下侧边缘像素点与待排图片上侧边缘像素点的像素匹配差异值最小为目标函数，建立优化模型，依次穷举出所有未排序的图片，找出第二行第一张碎纸片。其他行碎纸片依照此理类推即可排出顺序。（5）所有图片匹配完成后，对于拼接错误的图片进行相应的人工干预即可求得最后的图像复原图。5.2.2问题二模型准备（1）图片像素的量化和图片贴近度考虑到要根据图片之间的像素贴近度进行匹配，需要用Matlab软件将碎纸片像素量化，将像素分布转化为相应的数据。为此，我们采用了imread（）函数，将各图片转化成由像素构成的矩阵，方便了matlab对图片匹配的处理操作。图片贴近度用以描述两张图片的相近程度，主要由两张图片的像素决定。两张图片像素匹配差异值越小，图片贴近度越高；反之，图片贴近度越低。（2）图片聚类分析方法数学建模中，研究对样品或指标分类的一种多元统计方法，是依据研究对象的个体的特征进行分类的方法。聚类分析的基本思想是认为我们研究的样本或指标之间存在着程度不同的相似性。于是根据一批样本的观察指标，具体找出想死程度较大的样本聚为一类，关系密切的聚到一个小的分类单位，关系疏远的聚到一个大的分类单位，直到所有样本聚合完毕。这样就形成了一个个类，大大减少了数据处理的难度。在图片拼接过程中，将碎纸片图像量化得到的矩阵中数值处于0~255（白色的像素值为255，黑色的像素值为0）之间的数所在的行或列中所有的数值全部转化为0，找出黑白像素的分界线，根据分界线的匹配度进行聚合分类。5.2.3问题二模型的建立图2：问题二模型求解流程图（1）碎纸片预处理预处理的目的是将待处理物体表示为适合于计算机处理的形式。对于碎纸片来说，就是将其像素化、数字化，为此，我们利用Matlab软件中的imread（）函数对碎纸片进行量化，由于题目中所给的碎纸片图像分辨率都是198072，所以我们将每张碎纸片都转换成了的198072矩阵。（2）碎纸片聚类分析及匹配在碎纸片聚类过程中，首先将所有图片得到的像素矩阵灰度二制化，将灰色像素值转化为黑色像素值，由上至下找出黑白像素分界线，根据上侧跟左侧都留有白的特性人工干预找到第一张图片，然后以与第一张图片黑白像素分界线与其他图片黑白像素分界线差异值最小为目标函数建立优化模型，目标函数如公式（1）所示。.目标函数如下:我们根据分界线位置的差异值最小，对碎片预处理得到的像素矩阵，聚类分析得到第一行所有的图片，同样运用聚合分析的思想得到第一列所有的图片，根据问题一的匹配方