搜索
碎纸片的拼接复原模型摘要本文运用灰度值转化、首尾数据比较、最短距离拼接、特征行对比、聚类分析等方法，研究单面纵切碎纸片文件、单面横纵切碎纸片中文文件、单面横纵切碎纸片英文文件和双面横纵切碎纸片英文文件的自动化拼接方法。针对问题一：将数据导入𝑚𝑎𝑡𝑙𝑎𝑏，利用𝑖𝑚𝑟𝑒𝑎𝑑将图片转换成灰度值，再转化成0-1矩阵，从中取出每张碎纸片首位列，利用绝对差值比较模型𝐷𝑖,𝑗=19∑︁𝑖=119∑︁𝑗=1|(𝐸(𝑘)𝑖,𝑗−𝐹(𝑘)𝑖,𝑗)|得到所有碎纸片之间的距离，将所有匹配度导入Lingo，利用旅行商模型取距离最短的碎纸片进行两两拼接，并导出图像。得到中文文件的拼接顺序为：008、014、012、015、003、010、002、016、001、004、005、009、013、018、011、007、017、000、006，英文文件的拼接顺序为：003、006、002、007、015、018、011、000、005、001、009、013、010、008、012、014、017、016、004。针对问题二：将数据导入matlab转化成0-1矩阵并使每列数据相加，根据碎纸片前5列二进制像素为0，后5列二进制像素不为0，找出第一列的11张碎纸片，通过模型𝑑𝑖,𝑗=180∑︁𝑖=1|(𝑏𝑖,𝑚−𝑏𝑖,𝑛)|计算第一列11张与剩余198张的距离，取距离最短的碎纸片进行一次聚类，再找出11张碎纸片同行碎纸片共同具有的的特征行，利用绝对差值比较模型和最短距离拼接模型对特征行进行求解，进行同类碎纸片间的拼接，得到二次拼接的结果，最后建立三维矩阵最短距离模型𝐷𝑖𝑗𝑘=11∑︁𝑖=11368∑︁𝑗=1|𝐴180𝑘,𝑗−𝐴180𝑖−179,𝑗|进行行与行之间的三次拼接。其中需在一次聚类、二次拼接和三次拼接可能出错处进行人工干预。根据人工干预次数得出中文文件拼接的准确率为90.99%，英文文件拼接的准确率为67.46%。关键词：绝对差值比较；最短距离模型；聚类分析；特征行对比；三维矩阵。1一、问题的重述破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。请讨论以下问题：1.对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达。2.对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。3.上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果。二、问题分析本题是一个碎纸片拼接的问题，由于人工拼接难度系数高，且浪费人力和时间，人们试图使用计算机自动拼接碎纸片，但由于目前的计算机技术难以全自动无误差进行匹配、拼接，我们需要在某几个时间点进行人工干预。本题分为三个小题，其中文件的形式分别为仅被纵切为19条碎纸片的中英文单面文件各一份，横纵切为11×19条碎纸片的中英文单面文件各一份和横纵切为11×19条碎纸片的中英文双面文件一份。我们需要建立模型分别对三个小题的文件进行拼接复原，并使采用人工干预的次数尽量减少，准确率尽量提高。1.问题一的分析：已有一份中文单面文件和一份英文单面文件，均被纵切为19条碎片，中文文件的每张碎片中均有27行的汉字，英文文件的每张碎片中均有29行的字母。因为图片由像素点组成，像素点可以转换成可运算的数据，我们的做题思路为：先将19张碎纸片分别转化成0∼255的灰度值矩阵，再将其转化分别成数据的矩阵，利用首尾数据拼接模型，将19个0-1矩阵的尾列数据逐个与其他矩阵的首列矩阵进行对比，取距离最短的进行两两拼接。2.问题二的分析：已有一份中文单面文件和一份英文单面文件，均为横切和纵切成11×19块的碎片，中文文件的每张碎片中均有2∼3行的汉字，英文文件的每张碎片中均有2∼3行的字母，可见行数较少，准确率会降低。由于第一列的前多列具有全空白的特征且后多列不空白的特征，我们的思路是:先从每个文件中找出首列所有碎纸片，再以第一列为基准进行每行碎纸片的分组和拼接。对于中文文件，我们根据行与行之间空白部分的位置进行一次聚类；对于英文文件，我们根据特征行的数据和位置进行一次聚类，再利用首尾数据拼接模型进行二次拼接，最后在碎纸片和碎纸片的行与列的三维矩阵中求最短距离得连接方式，得到行与行之间的连接。2三、模型的假设1.每一张碎纸片的边缘均光滑。2.同一文件的碎纸片大小、形状相同。3.同一文件的行间距相同，段落间距相同。4.文件中仅有黑色文字，无污渍或其他内容。5.所有图片不需要进行去噪处理。四、符号假设符号意义𝐵(𝑘)𝑖𝑗第k张碎片的𝑖×𝑗灰度值矩阵𝐴(𝑘)𝑖𝑗第k张碎片的𝑖×𝑗0-1数据矩阵𝑐𝑖𝑗所有碎纸片𝐸𝑖𝑗碎纸片首列的𝑖×𝑗0-1的数据矩阵𝐹𝑖𝑗碎纸片尾列的𝑖×𝑗0-1的数据矩阵𝐷𝑖𝑗碎纸片的𝑖×𝑗距离矩阵𝑎𝑖𝑗各行0-1数据之和的矩阵𝑏𝑖𝑗特征行的0-1矩阵𝑑𝑖𝑗特征行0-1矩阵差值的和五、模型的建立与求解5.1问题一：单面19条纵切碎纸片的拼接复原模型建立5.1.1图像的处理1.将19张碎片图像转化成灰度值矩阵：用𝑚𝑎𝑡𝑙𝑎𝑏的𝑖𝑚𝑟𝑒𝑎𝑑命令读取附件中每张碎片，将它们转化成灰度值，并以矩阵形式输出，得到矩阵𝐵𝑘:𝐵(𝑘)𝑖𝑗=⎛⎜⎜⎝𝐵(𝑘)1,1···𝐵(𝑘)1,𝑛.........𝐵(𝑘)𝑚,1···𝐵(𝑘)𝑚,𝑛⎞⎟⎟⎠1980×72,𝑘=1,2,···,192.将灰度值矩阵转化成0-1矩阵：通过𝐴(𝑘)𝑖𝑗=⎧⎨⎩1,𝑏(𝑘)𝑖𝑗≥1700,𝑏𝑘𝑖𝑗170,𝑘=1,2,···,19(1)3.得到碎纸片的首尾列矩阵：从𝑘=1,2,···,19的𝐴𝑖𝑗𝑘中分别取出第一列，放入矩阵𝐸𝑖𝑗,分3别取出第最后一列，放入矩阵𝐹𝑖𝑗，其中𝐸𝑖𝑗，𝐹𝑖𝑗均为1980×19的矩阵：𝐸𝑖𝑗=⎛⎜⎜⎝𝐴(1)1,1𝐴(2)1,1···𝑎𝐴(19)1,1𝐴(19)1,1...............𝐴(1)1980,1𝐴(2)1980,1···𝐴(18)1980,1𝐴191980,1⎞⎟⎟⎠𝐹𝑖𝑗=⎛⎜⎜⎝𝐴(1)1,72𝐴(2)1,72···𝐴(18)1,72𝐴(19)1,72...............𝐴(1)1980,72𝐴(2)1980,72···𝐴(18)1980,72𝐴(19)1980,72⎞⎟⎟⎠5.1.2首尾数据拼接模型的建立1.建立首尾差值比较模型：将第𝑚(𝑚=1,2,···,19)张碎片尾列数据依次与第𝑛(𝑛=1,2,···,19)张碎片首列数据进行比较，比较时采用模型：𝐷𝑖𝑗=19∑︁𝑖=119∑︁𝑗=1|(𝐸𝑖𝑗−𝐹𝑖𝑗)|(2)得出矩阵𝐷𝑖,𝑗:𝐷𝑖𝑗=⎛⎜⎜⎝𝐷1,1···𝐷1,19.........𝐷19,1···𝐷19,19⎞⎟⎟⎠其中矩阵的对角线代表𝑚=𝑛时的对比，在实际拼接时不存在碎纸片的尾列与自身首列拼接的情况，故人为将对角线取为极大值1000。2.建立最短距离拼接模型：以𝐷𝑖𝑗为决策变量，引入𝑥𝑖𝑗判断是否通过该距离，建立旅行商模型：𝑚𝑖𝑛19∑︁𝑖=119∑︁𝑗=1𝐷𝑖𝑗𝑥𝑖𝑗⎧⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎩19∑︁𝑗=1𝑥𝑖𝑗=1𝑖=1,2,...,19𝑗̸=𝑖19∑︁𝑖=1𝑥𝑖𝑗=1𝑗=1,2,...,19𝑖̸=𝑗𝑥𝑖𝑗=0,1𝑖,𝑗=1,2,...,19𝑢𝑖−𝑢𝑗+19𝑥𝑖𝑗≤18𝑖=1,2,...,19𝑗=2,...,19𝑖̸=𝑗𝑢𝑖𝑢𝑗≥0𝑖=1,2,...,19𝑗=2,...,19𝑖̸=𝑗(3)首先找出𝐷𝑖𝑗中数字0的位置(𝑥,𝑦)，则第𝑥张为首张碎片，第𝑦张为尾张碎片。再将矩阵𝐷𝑖𝑗导入𝐿𝑖𝑛𝑔𝑜中，将11张碎纸片的首位从第𝑥张到第𝑦张按照最短距离逐个连接。5.1.3首尾数据拼接模型的求解1.将第𝑚(𝑚=1,2,···,19)张碎片尾列数据依次与第1张、第2张、第3张...第19张碎片（除第𝑚张）的首列数据进行比较，得到19×19组首尾数据比较的值。42.找出𝐷𝑖,𝑗中数字0的位置(𝑥,𝑦)，则第x张为首张碎片，第y张为尾张碎片。3.从第𝑥张碎纸片开始，取第𝑚(𝑚=1,2,···,19)张碎片尾列与其他碎片首列数据比较值的最小值，则第𝑚张碎片与最小值对应碎片拼接，直至拼接至第𝑦张结束。拼接得到附录1碎片的顺序为：表1:附件1碎片拼接顺序表拼接得到附录2碎片的顺序为：表2:附件2碎片拼接顺序表5.2问题二：单面11×19横纵切碎纸片的拼接复原模型建立5.2.1图像的处理1.将209张碎片图像转化成灰度值矩阵：用𝑚𝑎𝑡𝑙𝑎𝑏的𝑖𝑚𝑟𝑒𝑎𝑑命令读取附件中每张碎片，将它们转化成灰度值，并以矩阵形式输出。2.将灰度值矩阵转化成0-1矩阵。3.通过将209张碎片0-1矩阵的每行数据相加，并放入同个矩阵𝑎𝑖𝑗中，𝑎𝑖𝑘=72∑︁𝑗=1𝐴𝑖𝑗(4)5若该行无文字，则该行数据相加为72，否则小于72，𝑎𝑖𝑗为180×209的矩阵：𝑎𝑖𝑗=⎛⎜⎜⎜⎜⎜⎜⎜⎝4672···72364372···7235...............7227···72727244···7272⎞⎟⎟⎟⎟⎟⎟⎟⎠4.将𝑎𝑖𝑗转化成0-1矩阵，根据𝑏𝑖𝑗=⎧⎨⎩1,𝑎𝑖𝑗=720,𝑎𝑖𝑗72(5)进行转化，转化后若该行无文字，则该行数据相加为1，否则为0。得到𝑏𝑖𝑗:𝐴𝑖𝑗=⎛⎜⎜⎜⎜⎜⎜⎜⎝01···1001···10...............10···1110···11⎞⎟⎟⎟⎟⎟⎟⎟⎠5.2.2特征行对比模型的建立1.利用第一列碎纸片均以多列白色开头，不以多列白色结尾，即前多列二进制像素均为1，后多列二进制像素不为1，找出第一列所有碎纸片11张。即选出满足：⎧⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎩5∑︁𝑗=1𝐴𝑖𝑗=90072∑︁𝑗=60𝐴𝑖𝑗̸=540(6)的碎纸片。2.对于中文文件，由于同行碎纸片中汉字的行与行间空白区域位置相同，根据𝑑𝑖𝑗=𝑘′∑︁𝑖=𝑘|(𝑏𝑖𝑚−𝑏𝑖𝑛)|(𝑚,𝑛=1,2,...,209)(7)依次计算第一列11张碎纸片与其他198张碎纸片特征行的距离，其中𝑘和𝑘′的选取以编号为007的碎纸片为例：图1:编号007碎纸片的特征行选取6编号007的碎纸片为该行的第一张，在𝐴𝑖𝑗中，它的同行碎纸片于第1行到第𝑘1行必为0，第𝑘1行到第𝑘2行必为1，第𝑘2行到第𝑘3行必为0，𝑘3以下的行可能为0也可能为1,故只需根据第1行到第𝑘3行的距离最短即可找出同行碎纸片；3.对于英文文件，每个英文字母在四线三格的中间一格均有较多分布：图2:英文字母在四线格中的分布故调整阈