2013B碎纸拼接问题(转)

1基于旅行商规划模型的碎纸片拼接复原问题研究摘要本文分别针对RSSTD(ReconstructionofStripShreddedTextDocument）、RCCSTD(Reconstructionofcross-cutShreddedTextDocument)和Two-SidesRCCSTD三种类型的碎纸片拼接复原问题进行了建模与求解算法设计。首先我们对于RSSTD问题，建立了基于二值匹配度的TSP模型，并将其转化为线性规划模型，利用贪心策略复原了该问题的中文和英文碎片；然后对于RCCSTD问题，由于中英文字的差别，我们分别建立了基于改进误差评估的汉字拼接模型和基于文字基线的误差评估的英文字拼接模型，并利用误差评估匹配算法，复原了该问题的中文和英文碎片；随后我们针对正反两面的RCCSTD问题，利用基线的概念将正反两面分行，转化为RCCSTD问题，并复原了该问题的英文碎片。最后，我们对模型的算法和结果进行了检验和分析。◎问题一：我们针对仅纵切的情况，首先将图像进行数字化处理，转换为了二值图像，然后得到各图像的边缘，并计算所有碎片与其他碎片边缘的匹配程度。然后，根据两两碎片之间的匹配程度建立了TSP模型，并将其划归为线性规划模型。最终，我们根据左边距的信息确定了左边第一碎片，随后设计了基于匹配度的贪心算法从左向右得到了所有碎片的拼接复原结果。结果表明我们的方法对于中英文两种情况适用性均较好，且该过程不需要人工干预。◎问题二：我们针对既纵切又横切的情况，由于中英文的差异性，我们在进行分行聚类时应采用不同的标准。首先根据左右边距的信息确定了左边和右边的碎片，随后分别利用基于改进误差评估的汉字拼接模型和基于文字基线的误差评估模型，将剩余的碎片进行分行聚类，然后再利用基于误差评估的行内匹配算法对行内进行了拼接，最终利用行间匹配算法对行间的碎片进行了再拼接，最终得到了拼接复原结果。对于拼接过程中可能出现误判的情况，我们利用GUI编写了人机交互的人工干预界面，用人的直觉判断提高匹配的成功率和完整性。◎问题三：我们针对正反两面的情况，首先根据正反基线信息，分别确定了左右两边的碎片，然后利用基线差值将其两两聚类，聚类以后其正反方向也一并确定，随后我们将其与剩余碎片进行分行聚类，最终又利用行内匹配和行间匹配算法得到了最终拼接复原结果。其中，对于可能出现的误判情况，我们同样在匹配算法中使用了基于GUI的人机交互干预方式，利用人的直觉提高了结果的可靠性和完整性。关键字：碎片复原、TSP、误差评估匹配、基线误差、人工干预2一、问题重述破碎文件的拼接复原工作在传统上主要需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。请讨论以下问题：1.对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达。2.对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。3.上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果。二、问题分析破碎文件的拼接复原工作，传统人工处理准确率高，但是效率低。随着计算机技术的发展，本问题试图寻找碎纸片的自动拼接方法。本文的碎片均为矩形，且大小一样，这就给碎片的拼接带来了困难，因为难以利用碎片的轮廓信息，从而只能利用碎片边缘的图像像素信息来进行拼接。对于问题一，给出了纵切的19条碎纸片，碎片为1980*72，总切线的像素点较多，并且碎纸片的数量较少，从效率出发，可以直接考虑纵切条上的像素统计信息。为了衡量匹配程度，需要建立误差评估函数。本文考虑采用TSP模型，将碎纸片作为节点，将误差评估函数的值作为节点之间的权值，寻找最优解。在本问题的情况下，中英文的差别并无太大影响。对于问题二，由于给出的数据是横纵切的中英文碎片，碎片大小为180*72，各208张。因为碎纸片的数量较多，直接匹配则为NP问题中的无法用多项式解决的问题，所以先将行分组匹配完成后再把各行拼接起来。本问题主要解决：1）如何正确高效分组；2）如何准确高效拼接。考虑到中文和英文在字形和印刷结构上的不同，需要定义不同的特征向量去描述中文和英文的碎纸片上的信息。文字各行的位置和间距将作为重要的分组依据。在问题一的基础上，由于每个碎纸片的边缘像素较少，为了充分利用包含信息，误差评估函数的定义将会比问题一中更加细化。行之间的拼接将会利用边缘像素和间距匹配。在本问题中，中英文3的基线选择方法将会有很大不同。对于问题三，在问题二的基础上，加入了正反面信息，碎纸片的形状并没有改变。因此，需要在问题二的误差评估函数的基础上，综合考虑正反面的匹配误差。分组的方法与行间的拼接方式与问题二基本相同。综上所述，本问题可以看做是TSP问题，碎纸片为节点，误差评估函数值为边的权值，寻求最优解的问题。三、模型假设1.假设需要复原的碎片是来自同一张纸，且对于该张纸具有完备性。2.假设同一页中，文字的种类、行间距和段落分布情况是相同的。四、符号说明ijkm碎片i和碎片j第k行之间的匹配度ijM碎片i和碎片j之间的匹配度dtb由上边缘向下像素点由黑过度到白的距离dbb由下边缘向上像素点由黑过度到白的距离dtw由上边缘向下像素点由白过度到黑的距离dbw由下边缘向上像素点由白过度到黑的距离(,)hcij碎片i和碎片j之间左右边缘误差评估值(,)hcij碎片i和碎片j之间左右边缘相对误差评估值(,)wcpq行片段之间上下边缘的误差评估值4五、模型建立与求解文件碎片拼接主要有两类不同的技术标准：（1）ReconstructionofStripShreddedTextDocuments(RSSTD)碎片的长度和原始文件的长度相等，同时所有碎纸片都是等宽的长方形。（2）ReconstructionofCross-cutShreddedTextDocument(RCCSTD)所有的文件碎片都是长方形且大小相等，但其长度小于原始文件的长度。问题一为典型的RSSTD问题，我们通过分析碎纸片文字的行特征，建立了一种基于匹配度的求解模型，下面就对该模型的建立进行详细的讨论。5.1问题1——基于匹配度的RSSTD问题研究为了便于对图像数据进行分析，我们首先需要对其进行数字化处理以及文字行特征的提取，而后再建立基于匹配度的模型。5.1.1图像数字化处理图像的数字化处理主要包括以下几个方面：（1）二值化处理由于纵切碎纸片的长度特征（碎片长度与原始文件长度相等），其边缘像素点信息量丰富。因此我们采取二值化而非灰度对图像进行了处理，进一步简化了算法的复杂度，得到每条碎片像素大小为721980（长宽），像素点值取{0,1}，其中0和1分别表示颜色的黑与白。（2）edge矩阵的建立edge[i,j]为192的矩阵，储存每一条碎片的边缘像素点信息。其中i表示碎片的编号，j=0表示左侧边缘像素点信息，j=1表示右侧边缘像素点信息。例如，edge[0,0]储存001号碎片左侧边缘像素点信息。（3）count矩阵的建立根据edge[i,j]矩阵，我们可以计算得到一个192的count[i,j]矩阵，该矩阵储存每一条碎片边缘取值为0的像素点的数量。例如，count[0,0]=350表示001号碎片左侧边缘共有350个黑色像素点。（4）shredwithblankleft的选取根据count矩阵，若edge[i,0]=0，那么我们就认为该碎片在原始文件中处于5最左端，即为选取的shredwithblankleft。（5）碎片行特征的提取由于原始文件文字行特征明显，因此我们需要提取碎片的行特征（其具体的原因见匹配度的定义）。首先确定碎片顶端取值为0的像素点的位置，以此作水平线为上边界，依次向下取w为行宽（这里取w=40pixels以保证能容纳每一个文字）直至下边缘，得到每条碎片的行数为{n1,n2,…,n19}；然后取n=max{n1,n2,…,n19}作为最终确定的行数，并以该条碎片的行化方式为标准对每一条碎片进行行化；最终每一条碎片被划分为28行。每条碎片维护着以下的特征数据表：表1碎片i特征数据表k123„2728nklni1lni2lni3l„ni27lni28lnkrni1rni2rni3r„ni27rni28r其中，k为行号；nkl为第k行左侧边缘取值为0的像素点的数量，nkr为第k行右侧边缘取值为0的像素点的数量；nikl为第i条碎片第k行左侧边缘取值为0的像素点的数量。5.1.2匹配度的定义为了衡量两个碎片之间的匹配程度，我们定义匹配度Mij作为评价的标准，其计算公式如下：min(,)max(,)ikrjklijkikrjklnnmnn1nijijkkMm其中，n为总的行数（如28n）；ijkm表示碎片i和碎片j第k行之间的匹配度；ijM表示碎片i和碎片j之间的匹配度。这里我们不选择通过统计碎片边缘总黑色像素点的数量来计算两碎片之间的匹配度，而是通过计算两碎片行匹配度来间接计算其匹配度，原因在于：①若以总的边缘黑色像素点计算匹配度，行与行之间的差异性无法体现，匹配结果误差过大；②通过行匹配度计算碎片之间的匹配程度，更加充分的挖掘了碎片边缘的信息，更为精确。65.1.3基于TSP问题的模型建立与求解5.1.3.1模型的建立根据匹配度的定义，我们可以计算得到19个碎片两两之间边缘的匹配度，现可将问题化简为：已知起始碎片和其他碎片之间的匹配度，寻找一序列使得碎片之间总的匹配度达到最大。如右图所示：（1）为简化问题，我们引入空白碎片0，同样可计算得到空白碎片与其他碎片的匹配度；（2）其中节点表示碎片，有向线段长度表示费用wij，且wij=1-Mij，箭头所指方向表示前一条碎片右侧边缘到后一条碎片左侧边缘。如①→②表示1号的碎片右侧边缘与2号碎片左侧边缘的费用；（3）现要求寻找一条回路遍历所有的节点使得费用达到最小。通过分析，可以发现这是一典型的TSP问题。为解决上述问题，我们建立模型如下：假设图中存在Hamilton回路，有n个节点，图中(i,j)边的权重为wij，设决策变量为xij=1说明弧(i,j)进入到Hamilton回路中，则线性规划模型可表达[6]为：(,)(,)(,)min11{0,1},(,)ijijijEijijEjijiEijwxxxxijEOnlyOneCircle求解该问题就是求解该线性规划问题的最优解。5.1.3.2模型的求解为了进一步求解上述模型，我们设计的算法如右图所示：（1）将所有碎片放入地址池中；（2）选出左侧全为白色像素点的碎片作为基准碎片，记为si，并将其从碎片池中剔除；选择shredwithblankleft，记该碎片为si，并将其从碎片池中剔除依次计算si的右侧边缘与碎片池中其他碎片sj左侧边缘的匹配度Mij判断碎片池是否为空将所有碎片构成一碎片池选取与si匹配度Mij最大的碎片st作为其右侧的碎片，记该碎片为si，并将其从碎片池中剔除NY得到正确的拼接顺序结束开始012345...图1问题示意图图2算法流程图7（3）依次计算si右侧边缘与地址池中其他碎片sj左侧边缘的匹配度Mij；（4）选择匹配度最大的碎片st作为碎片si的右侧碎片，并将其记为si，从碎片池中剔除该碎片；（5）重复（3）~（4）步直至碎片池为空。由于该算法使用统计量构建匹配度，很好的避免了中英文之间的差异性，适用性较好，在实际的应用中都收到了很好的效果。最终可以得到附件1与附件2中碎片的正确序列如下所示：表2附件