《碎纸片拼接数学模型》由会员分享，可在线阅读，更多相关《碎纸片拼接数学模型（18页珍藏版）》请在金锄头文库上搜索。
1、【精品文档】如有侵权，请联系网站删除，仅供学习与交流碎纸片拼接数学模型.精品文档.碎纸片的拼接复原问题模型摘要本文研究的是碎纸片的拼接复原问题。针对碎纸不同的裁剪特点，我们运用相关性系数法、聚类分析法等建立不同的模型来解决不同裁剪特点和不同纸张的复原问题。针对问题一，我们利用图像数字化技术，借助MATLAB软件将题目中附件1，2所给的图片转化为灰度值矩阵，并作二值化处理，然后取出每个矩阵第一列和最后一列，采用相关系数分析的方法，计算每第一列和每最后一列相关系数，根据相关系数的大小确定相邻的图片，逐步确定各张图片的顺序，最后得到复原的图片。中文文档拼接的顺序为：8，14，12，15，3，10，2
2、，16，1，4，5，9，13，18，11，7，17，0，6，中文文档复原的结果见附录1；英文文档拼接的顺序为：3，6，2，7，15，18，11，0，5，1，9，13，10，8，12，14，17，16，4，英文文档复原结果见附录2。针对问题二，同样，在将图片二值化处理后，我们运用聚类分析法将纵横裁剪后的图片进行行分类，经过人工干预后，获得需要的矩阵尺寸，然后根据图片的特点运用图片的上下边界和左右边界进行二次匹配，直到找到大致正确的图片排序；同时在必要时，进行二次人工干预，直到获得正确的图片排序。关键词：碎纸片复原 图像数字化 相关性系数 聚类法 1 问题重述1.1 问题背景碎文件的拼接在司法物证
3、复原、历史文献修复以及军事情报获取等领域都有着重要的应用。然而，传统的拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。本题即是通过一些模型算法开展对碎纸自动拼接技术的研究，具有重要的现实意义。1.2 要解决的问题问题一：对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，要求写出干预方式及干预的时间节点。问题二：对于碎纸机既纵切又横切
4、的情形，要求设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。问题三：附件5给出的是一页英文印刷文字双面打印文件的碎片数据。要求设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果。2 模型的假设及符号说明2.1 模型的假设（1）假设碎纸机在碎纸时不对碎片造成损坏，可以拼接复原成完整的一页文字；（2）假设各碎纸片大小相等且规则；（3）假设同一页中，文字的种类、行间距和段落分布情况是相同的。2.2 符号的说明3 问题分析针对问题一，要求对来自同一页印刷文字文件的碎纸机破碎
5、纸片（仅纵切），建立碎纸片拼接复原的模型和算法。附件1和附件2的碎纸片是经过纵切而成，想要将图片进行还原，必须要在里面取出左右边缘的值，进而对碎纸图片的左右边缘进行匹配就可以还原图像。首先将图片进行图像化处理，获得图片的像素点灰度值矩阵，转化成计算机可以识别且量化的计算机语言，其次，取出每个灰度值矩阵的第一列和最后一列列向量形成新的矩阵，并对其进行二值化处理，最后计算矩阵两列的相关系数，相关性越高，说明这两块碎纸片匹配的概率就越大，最终得出图片复原的排列顺序，将碎纸片进行复原。针对问题二，附件3和附件4的碎纸图片是经过纵切和横切而成的，相对第一问而言，图片可以直接获取的信息就较少，如像素灰度矩
6、阵变小；如果采取同第一问一样的方法，对图片的匹配而言准确度大为降低，同时还会出现更多的重复匹配。所以要进行碎纸图片还原，首相应该对碎纸进行行分类或者列分类，这里我们选择行分类，同时根据碎纸片的特点，我们进行行内的左右边界匹配，以及对所得行模块进行相关性匹配，对于不能够找到最佳匹配的，我们进行人工干预，直到将整个图片进行复原。针对问题三，4 图片数据处理与分析 纵观整个题目，给出的附件均是一整幅图片的碎片集合。根据题目建模的相关要求，需要将图片转化为其像素点灰度矩阵，同时为了降低计算机的计算机的计算强度和为了整个题目的计算过程，我们将图片的像素点灰度矩阵归置为0-1矩阵，即图片的二值化过程。5
7、问题一的解答5.1 建模思路将图片导入MATLAB软件中对图片进行预处理，以获得图片的像素点灰度值矩阵，进而转化成矩阵之间相关性计算问题。矩阵的计算过程如下：首先，在获得灰度值矩阵后，提取每个矩阵的第一列与最后一列分别得到两个分别是第一列与最后一列的矩阵；其次，把得到的新的灰度值矩阵做二值化处理；再次，利用矩阵两列的相关性系数判断其匹配程度；最后完成图片的拼接复原顺序和输出复原图片。5.2 模型建立（1）分别读取19张图片的19个像素点的灰度值矩阵，分别将每个矩阵的第一列取出获得新的矩阵；同时分别将每个矩阵的最后一列取出获得新的矩阵；根据像素的特点，我们以一半像素为分界点，分别将这两个矩阵进行
8、二值化处理得到两个0-1值矩阵BF,BL，处理标准如下：其中， ，两个0-1矩阵的规模为。（2）计算两个碎纸片对应0-1矩阵左右两边的相关系数，相关性越高表明这两块碎纸片匹配的概率就越大。相关性系数的计算如下：其中，为各个边缘列的灰度值， 表示灰度值的均方值。（3）在匹配过程中加入了阈值指标，当两个碎纸片0-1矩阵相关度大于指标时两碎片有匹配可能，当拼接或有多种可能时需加入人工干预人工筛选出与之最匹配的碎片。根据汉字的特点，定义阈值为0.7，说明当相关系数大于0.7时，两列数据有强相关性，即两碎片匹配几率较大。对于英文文章的拼接复原，考虑到英文字符的特点，我们将临界匹配阈值设定为0.6，即当相
9、关性系数大于或等于0.6时，说明两列数据具有强相关性，即两碎片匹配几率较大。本文从相关系数表中提取系数大于阈值的各边缘的相关系数：表1：汉字纸片的阈值设定汉字碎片阈值相关性无相关性弱相关强相关表2：英文纸片的阈值设定汉字碎片阈值相关性无相关性弱相关强相关5.3模型的求解及结果分析根据以上模型，运用MATLAB软件编程（源程序见附录3、4），得到图片的拼接复原顺序，见表1和表2。中文文档复原结果见附录1，英文文档复原结果见附录2。表1：中文文档的图片复原排序8141215310216145913181171706表2：英文文档的图片复原排序3627151811051913108121417164
10、从中文、英文文档的复原结果可以看出，拼接后的图像字迹清晰，内容完整，说明本题的模型和算法能有效地实现纵切文档图像的拼接复原。 6 问题二的解答6.1建模思路： 对于纵横切的情形，在增加横切之后，两图片边界处共同信息量大大减少，故需要更进一步地挖掘可用信息，如图片的四个边界信息。纵观整个问题，我们作如下考虑：（1）用问题一的方法对图像进行预处理，分别构建反映中、英文文档行特征的特征向量以及确定需要扫描像素行的行数； （2）通过分别建立特征匹配模型，左右边界匹配模型，上下边界匹配模型三个模型，完成单页打印横纵切纸片匹配模型的构建；（3）对模型进行求解，特别的，特征匹配模型求解后加入人工干预，最后复
11、原出整个图片。6.2 模型建立6.2.1模型的准备（1）对于图像的处理，同第一问一样，我们使用MATLAB软件读取每张图片的灰度值矩阵，并进行二值化处理，转化为0-1值矩阵。（2）构建中文特征灰度条向量（聚类分析）特征灰度条是指记录图片中文字的行方向信息的列向量，建造特征灰度条的方法为：对于预处理后的图像，建造一个与碎片的图像行数一致的列向量，对图像中像素行进行扫描，若此行中有像素值为 0 的点，则将列向量中相同行处的值设为 0，否则设为 1。图 000.bmp 的特征灰度条如图 1 所示 图1 000.bmp及其灰度条特征灰度条的列向量为：便可得到每张碎纸片的特征灰度条。若某两张碎片的灰度条
12、相似程度达到精度要求，则它们就具有相同的图像行特征，位于原文件的同一行。（3）确定扫描像素行的行数扫描一幅图片的像素点，其自然的思路就是对第张图像的每一行进行扫描，得到每行的像素值。但在构造特征灰度条矩阵的时候，发现了一些特殊情况，如下图所示：图 特殊情况举例编号为008 和编号为 009的图片可以认为判断他们是左右相邻的，由于图片的下部是空白部分，在匹配过程中可能出现，重复匹配的情况，即原本不该归为一类的情况可能放在一起，为此我们根据图片与汉字的特点，我们在进行扫描时尽量扫描图片的三分之二的高度区域。这样可以减轻计算的复杂度，避免结果的冗余，提高结果的准确性。按照每张图片的像素矩阵尺寸，我们
13、设定的扫描行数定为120行。6.2.2 建立横纵切纸片匹配模型（1）.聚类分析模型 将碎片与碎片进行特征比较，（），即求碎片的特征列向量和碎片的特征列向量对应元素差的绝对值，再求和，得到特征值考虑到每个汉字或英文字母结构的差异性，位于同一行文字的高度可能会出现微小的偏差，很难出现特征灰度条相同（即）的情况，若取作为判断原则，那么原本位于同一行的两张图片可能因为这微小的偏差而归于不同的行集合中。取一个合适小的置信区间，若，则认为碎片与碎片来源于文件的同一行。（2）建立左右边界匹配模型本问中的左右边界匹配模型相对于第一问中的边界匹配模型而言，差异性在于问题一中的边界匹配模型是19条纵向大长条，信息
14、量大，而本问中是纵向小长条，信息量小。问题二中的左右边界矩阵为;（3）建立上下边界匹配模型将第张图篇的上、下边界处的元素分别存于矩阵的第一行、第二行中。即上下边界匹配模型中第k行的上下边界矩阵为：故模型的构建如下：1、 上边界匹配模型的构建将第行的上边界与第（）行的下边界进行上边界匹配，即求第行的边界矩阵的第一行与第行的边界矩阵的第二行对应列元素的差，再求差的绝对值的和将第行的上边界依次与其余的任意一行的下边界进行上边界匹配，得到个值：，通过比较，取这个值中的最小值，作为上边界匹配值。2、下边界匹配模型的构建将第行的下边界与第（）行的上边界进行下边界匹配，即求第行的边界矩阵的第二行与第行的边界
15、矩阵的第一列对应列元素的差，再求差的绝对值的和将第行的下边界依次与其余的任意一行的上边界进行下边界匹配，得到个值：，通过比较，取这个值中的最小值，作为上边界匹配值。3、最佳边界匹配模型的建立取第行，先与任意一行（）依次进行上匹配，求得，再与任意一行依次进行下匹配，取两者之间的最小值 对应的匹配方式即为第行与第行的最佳匹配方式。若，则说明第行上边接于第行的下边；，说明第行的下边与第行的上边相连。综上，我们构建的横纵切纸片匹配模型为：6.3 模型的求解（1）根据以上模型，运用MATLAB编程（源程序间附录），得到每行集合的碎片个数，附件3（中文）对应的15个行集合中碎片个数，如表所示：表4：15行中每行的碎片个数行集合的编号123456789101112131415碎图片的个数19191918151919193218161814由上表知道：包含19个碎图片行集合的个数有6个，编号分别为：1、2、3、6、7、8，这6个可以唯
