《文字碎片拼接复原的数学模型.doc》由会员分享，可在线阅读，更多相关《文字碎片拼接复原的数学模型.doc（55页珍藏版）》请在金锄头文库上搜索。
1、文字碎片拼接复原的数学模型摘要本文针对碎片的拼接复原问题,建立了一个拼接的最优化模型,对外形规则的碎片进行拼接以实现文本的复原.针对问题一,我们观察所给碎片的像素矩阵发现,相邻两像素点之间像素值发生0到255或255到0的现象极少（不超过0.5%）,我们称这种现象为突变,并引入突变指数（相邻两列突变的次数）。我们将问题归结为寻找19个碎片的一个排序，使得总突变指数最少的一个优化问题。利用用matlab编程，首先找出左侧空白最大的一个碎片作为左边界，依次寻找与每个碎片突变指数最小的碎片作为其右侧碎片进行横向拼接。求解得19个碎片的顺序，得出复原后的图片（见附录），再利用相邻边界处对应点像素强度差
2、的平方和应最小这一准则，算出复原后的碎片，发现两种方法得到结果相同。结果见表1-1，表1-2。针对问题二，同时出现纵切和横切时，观察所给碎片的像素矩阵发现，横向发生变异的概率仍极小，因此我们建立了一个与问题一中模型类似的最优化模型。求解时，先找出左侧空白最大的11个碎片作为左边界碎片，考虑到处于同一行的碎片其空白行位置应该是一致的，利用空白行位置将209个碎片分为11组，依次对这11个左侧碎片为起点进行横向拼接，得到11行图片。关于11行图片的纵向拼接，我们将数据转置后转化为横向拼接问题，并结合中文图片行距为28像素左右以及上侧下侧边距大于行间距原则得到纵向拼接次序。该问题的求解中需要人工干预
3、，干预时机为当前碎片与候选碎片突变指数大于0（利用该原则人工干预次数占总拼接次数的比例约为8.6%，说明我们人工干预的时机选择是比较好的）。对于英文图片拼接问题，由于英文不是方块字，我们无法利用空白行原则分组。对于该问题我们首先找出左侧边界碎片，其余碎片不分组，都作为候选方案横向拼接；然后用与中文相同的方法纵向拼接（区别在于英文行距为12像素左右）。针对问题三，对于双面英文碎片的拼接，我们将其视作418张碎片处理，先确定左侧边界碎片（24个，计算时发现两个无法拼接，删除后为22个），不对碎片分组，进行横向拼接，得到22行文字；然后按照问题二的算法纵向拼接，得到两个独立的图片，分别作为正面和反面
4、。结果见表3 表3关键字：碎片拼接 突变指数 优化模型一、问题重述在司法物证复原、历史文献修复以及军事情报获得领域，拼接破碎文件占着重要地位。纸片分正反面，碎纸机碎纸片也有横切和纵切两种方式。由于人工拼接存在效率低的局限性，应用计算机网络技术，可以实现自动拼接，以提高拼接复原效率。此题就三种情况依次讨论：（1）纵切单面文件，（2）纵横切单面文件，以及（3）纵横切双面文件，并依次建立碎纸机拼接复原模型和算法，同时可在复原过程中对其进行人工干预，对碎片数据进行拼接复原。二、问题分析问题一：先人为的从19张纸片中找出2张相邻的纸片，以找到的2张纸片为一组，多找几组，然后用matlab的图片处理功能，
5、将图片信息变成数字信息，观察每一组变成数字信息后的边界连接规律，以此规律为纸片间的拼接准则，找出任意一张纸片的左右相邻纸片，然后拼接出整张纸片。问题二：先用程序找出最左侧的11张纸片，如果程序给出的符合要求的纸片多余11张，我就可以通过人为干预的方式从以得结果挑出最有可能在最左侧的那些纸片，然后依次以这些纸片为第一张纸片，利用问题一的规律，找出它的右邻接纸片，找出整行的纸片。整行数据出来后，将整行数据的矩阵转置，再利用一的规律拼接，最后对于仍不能确定的行段进行人为干预，直至拼出完整的纸张。问题三：过程接近问题二，先找出最左侧的纸片，然后拼接出整行纸条，整行纸条转置，再利用一中规律，最后人为干预
6、拼接出整张纸，得出完整的纸片内容。三、模型假设1、 同一附录里的图片必须来自同一张纸上2、 被切割的纸片是规则的3、 横向切的方向要与纸张的上下边界平行，同样纵向要垂直4、 切割刀片的切割方向要与纸面垂直5、 纸张上的内容要符合语言规范，如不能出现语法错误，不能出现拼写错误，不能出现错误汉字四、重要说明及符号 本文中对碎片的编号方式为：000.bmp编号为1，001.bmp编号为2，以此类推进行编号。各符号均在正文出现处进行说明。五、模型的建立与求解5.1问题一的求解5.1.1第一子问题分析（中文图片拼接问题） 对于问题一，用matlab对碎片进行读取时发现，所有碎片都是像素为的灰度图像，每一
7、点的像素值为在0到255之间的整数（其中0表示黑色，非零值为黑色）。我们利用matlab的imread命令将19张碎片导入工作空间，得到19个的像素点矩阵，分别记作（注：我们在将碎片导入电脑后，为了用计算机处理方便，对碎片的编号进行了调整，000.bmp的数据记作，001.bmp的数据记作，以此类推）。为了的到正确拼接的标准，我们对对于每一张碎片的数据进行了分析。发现在每一张碎片上，同一行相邻两个点的像素值几乎不会直接从0变为255或者从255变到0。对每一个碎片的72列数据相邻两列像素值进行分析发现：由255变到0或者由0变到255的比例仅有0.016%左右。我们将相邻两个像素值由0变到25
8、5或者由255变到0定义为一次突变。基于以上分析，我们推测：在正确的拼接方案中，左边一张图片的最右边一列数据与右边一张图片的最左侧一列数据基本不会出现突变。我们定义两张碎片的突变指数如下：设为某张碎片的最右侧一列像素值，为另一张碎片的最左侧一列像素值（在问题一的数据组，和均为1980行的列向量），碎片和的突变指数，其中， （1）其中表示向量的第个分量，表示向量的第个分量。， 利用matlab统计出问题一汉字碎片的突变比例（代码见附录），结果如表1-1。表1-1：问题一汉字碎片突变比例分布表图片编号000001002003004005006007008009突变点的个数6724201812211
9、411144突变率（%）0.0480.0170.0140.0130.0090.0150.0100.0000.0070.031图片编号010011012013014015016017018突变点的个数218292286244144突变率（%）0.0010.0130.0210.0160.0060.0440.0310.0100.002其突变率柱形图如下：由附件一的图可以看出突变率最高为0.044%，突变率很低。由此，问题一可以归结为如下问题：寻找19个碎片的一个排列，使得总的突变指数最小。模型如下：其中为的全排列。问题一第一个子问题的求解：算法描述：1 计算每一个碎片左侧空白部分的宽度（即对应矩阵中
10、左侧非零数据的列数），得到第9个碎片左侧空白部分最宽，我们认为第9个碎片为复原后图片的最左侧部分。2 以第9个碎片为起点，计算其余碎片与第9个碎片的突变指数，取出其中突变指数最小的一个，即为应该跟第9碎片拼接在一起的碎片。3 以步骤2中选取的碎片为起点，继续计算其他碎片与其的突变指数，并挑出突变最小的一个为下一个碎片。重复此过程，直到19个碎片全部选中为止。我们利用matlab软件对上述算法进行编程（代码见附录），得到了问题一第一子问题的结果。碎片复原后的次序如下表：表1-2：基于附件一编号碎片的复原表91513164113172561014191281817复原后的图片见附录附录一。5.1.
11、2问题一第二子问题的求解 第二子问题与第一子问题类似，只是中文图片变成了英文图片，其求解方法是不变的。我们利用第一子问题的算法对第二子问题进行了求解。复原后的碎片次序如下表： 表1-3：基于附件二编号碎片的复原表47381619121621014119131518175复原后的图片见附录附录二。统计结果如表1-4、表1-5.表1-4,1-5中序号意义分别与表1-2,1-3相同。表1-4：附件一000-018碎片复原后突变指数分布表序号91513164113172561014191281817000000000000000100表1-5：附件二000-018碎片复原后突变指数分布表序号47381
12、619121621014119131518175000000000000000000我们也可根据另一准则进行拼图，引入两碎片拼接后的误差参数,对于,与其相连的矩阵的误差参数（其中为的左边界的第个数，为的右边界的第个数），以为目标函数建立一个优化模型，越小，两碎片越匹配，利用此准则用matlab搜索找出每一碎片的下一个碎片（代码见附录），得到的碎片顺序与相邻两碎片间的如表1-6，1-7，其中,表1-6与表1-7中序号分别与意义与表1-2,1-3相同。表1-6：基于附件一碎片复原后分布表序号915131641144292402849332157084034727214888069317256101
13、43512491195756146165224543720343209435602343818343128181712328272037462423257216514796239139033593515表1-7：基于附件二碎片复原后分布表序号47381619402160728890952694303496075518218291216210141132909332365422359754626331292665638416640458546469131518175302913337342332492269401621317542113013494关于碎片复原的推想：由模型一可知，对于只有黑白两
14、种颜色的灰度图像，相邻两像素点之间的像素强度出现变异现象的概率极小，推广到彩色图片，每种颜色之间都没有明显的界限，也就是说这种突变的现象更加不可能出现，我们可以利用这一个准则定义一个突变的标准，从而进行碎片的复原。5.2 第二问的分析与求解5.2.1第一子问题的分析与求解问题二第一个子问题要求对于一张中文文字图片既有横切又有纵切的情形进行复原。我们利用matlab软件读取碎片可得到209个18072的像素矩阵，分别记作。由于碎片间既可能横向拼接，又可能以纵向方式拼接。借鉴前一问的思想，我们定义了横向突变指数和纵向突变指数。为碎片和以横向方式拼接（在左，在右）时，的最右侧列向量与的最左侧列向量间的突变指数；为碎片和以纵向方式拼接（在上，在下）时，的最下侧行向量与的最上侧行向量间的突变指
