论文部分内容阅读
【摘要】针对文献修复中均匀碎片，以特征位置为基准，采用K-means算法进行聚类分析，对于每一类碎片运用贪心算法不断地取匹配度最高的碎片进行拼接，逐步自动复原整个文献。经计算机仿真证明：此方法能实现文献的快速拼接，有效地提高物证修复，碎片复原的工作效率。
【关键词】聚类分析；匹配度；贪心算法；均匀碎片；特征
0.引言
破碎文件的拼接在司法物证复原?、历史文献修复以及军事情报获取等领域都有着重要的应用。目前在文件碎片复原这一领域，国内研究涉及到的都只是不规则的碎片[1-4]，碎片物理性质、几何形状、颜色、纹理等外在特征都无疑给拼接复原的工作带来了便利[5]。但是在实际应用中，并不是所有的碎片都存在易于区分的外在特征，虽然计算机有超强的计算能力，但目前很难对碎片边缘上的文字分布走势特征进行智能地识别，均匀规则的碎片复原就会遇到难点。
对于来自同一页印刷文字文件的均匀破碎纸片（以2013年全国大学生数学建模竞赛B题所给的中英文碎片为例[6]），这些碎片形状大小规则，计算机显然无法从利用碎片外在特征进行匹配。仔细分析这些碎片，可以发现碎片上文字呈现的特征规律，不同碎片上的文字出现的位置特征是不一样的，利用碎片上文字的位置特征，对碎片先按行聚类，对每一类碎片的边缘灰度进行分析比对，运用贪心算法的处理思想每次都将灰度相似度最高的碎片拼接在一起，辅之以少量的人工干预，最后即可逐步自动拼接完成整个文档。计算机仿真实验证明，上述拼接方法快速有效，在处理均匀碎片的拼接问题上能发挥出巨大的作用。
1.假设及数据的预处理
为了能比较好地去阐述拼接模型，现做出以下假设：
（1）所有的碎纸片大小一致、形状规则、边缘整齐。
（2）原中英文文献页边距、行距不变，字符间隔、大小保持不变。
将图像转化为对应的像素矩阵存放在计算机中，矩阵中的元素称为像素，像素的取值在0到255之间，所有的碎片和矩阵都是一一对应。
2.聚类分析
碎片的数量庞大，如跳过聚类直接进行拼接，被拼接碎片要与剩余所有的拼接碎片逐一进行比对，效率低，出错率高。将所有的碎片先按行进行聚类，再拼接，是提高正确率的必要先行过程。
2.1 特征位置的选取
行间聚类，首先必须找出同一行碎片之间的相同点以及不同行碎片之间的差异，仔细分析这些碎片，可从文字位置特征入手。
中英文的书写习惯是按行从左往右，从上往下，拥有相同的行距。每一个碎片上的文字都会出现在不同的位置，在此将这些位置称为该碎片的特征位置。图中中文碎片只可能在非阴影区域出现文字，非阴影区域也就称为碎片的特征位置。对于英文碎片，由于英文字母是以四线三格为标准进行书写，不同于中文汉字的田字格，在特征位置上的选取有一定的差异，此取两行之间的行距空白区域作为特征位置。
以碎片之间特征位置的差异为基础可建立数学模型所需要的距离指标，我们认为两个碎片的特征位置相同或相近，这两个碎片的距离越小，被归为一类的可能性越大。基于此距离指标，采用K-means算法对中英文碎片进行聚类。
2.2 K-means算法的应用
K-means聚类算法是由Steinhaus 1955年、Lloyd 1957年、BallHall 1965年、McQueen 1967分别在各自的不同的科学研究领域独立的提出[7-9]，该算法的核心思想是找出K 个聚类中心使得每一个数据点和与其最近的聚类中心的距离和最小化。该方法采用某个空间距离作为评价相似程度的指标，然后确定评价聚类划分结果质量的准则函数，在给出初始聚类中心点后，用迭代法找出使准则函数取极值的最好聚类划分结果。该算法能对大型数据集进行高效分类，收敛速度快，在现实中应用广泛。具体流程如下：
（1）从碎片集中任意选取最左边一列的11碎片作为基准点，赋给初始的聚类中心。
（2）对碎片集中的每个碎片样本点，计算其与各个聚类中心的距离，并记录与其距离最小的聚类中心的编号label：
（3）重新计算k个聚类中心：
（Nj为label为j的样本数量）
重复步骤2和步骤3，直到达到最大迭代次数，聚类中心不再改变为止。
利用上述K-means算法对2013年全国大学生数学建模竞赛B题所给的英文碎片进行聚类可快速而精准得到如下11个分组，如表1所示（中文碎片聚类结果不再赘述）。
对每一个类中的碎片进行拼接，减少了拼接过程中的比对次数，提高了效率，还降低了出错的概率。K-means算法对中英文碎片的准确聚类，为后续基于贪心算法的碎片拼接提供了有力的支持。
3.基于贪心算法的碎片拼接
3.1 匹配度指标的提出
文献碎成两半，在断裂处的颜色也应该大致相同，具有一定的连贯性。利用碎片边缘颜色的连贯性和对应碎片矩阵在首（尾）行、首（尾）列元素的一致性，可给出碎片拼接匹配标准。假设任给两个碎片对应的灰度矩阵分别为，定义这两个碎片之间的匹配度为：
（RNo为矩阵的列数，start为首列序号1，end为最末尾一列的序号）
同理，在从上往下进行拼接时，匹配度为如下表达式：
（CNo为矩阵A的行数，start为首行序号1，end为最末尾一行的序号）
匹配度即为两个碎片矩阵在拼接处行（列）向量的欧氏距离和的倒数。关于这一指标，这里说明几点：
①匹配度相对于两个矩阵而言，一个矩阵不存在匹配度。
②匹配度数值越大，则认为两个矩阵的匹配度越高。
③匹配度这一指标的优劣直接受CNo/RNo和矩阵数量K的影响，因为在参与计算的矩阵的行数CNo或列数RNo越多，匹配度最高的矩阵为正确的匹配矩阵的概率就越大，出现差错的概率越小；以及矩阵的个数越少，出错的概率也会越小。 由匹配度指标来衡量碎片之间的匹配程度，是可行可靠，易于计算的。
3.2 贪心算法的运用
贪心算法（Greedy algorithm）[10]是一种求某些问题最优解的更简单、更迅速的方法。它省去了为找最优解要穷尽所有可能而必须耗费的大量时间，根据当前状态做出在当前看来是最好的选择，然后再去求解做出这个选择后产生的相应的子问（下转第186页）（上接第183页）题。每做一次贪心选择就将所求问题简化为一个规模更小的子问题，最终可得到问题的一个整体最优的拼接方案[12]。
根据匹配度这一指标，每一类碎片拼接完成之后，若使得所有拼接处的匹配度的和最大，则这就是一个全局最优的拼接。但是碎片的组合数量以阶乘的复杂度递增，对每一种组合都计算器匹配度的和，时间开销巨大。利用贪心算法的思想，将整体最优组合分解为多个局部最优，大幅减少计算次数，即可得出最优的拼接方案。
按照上述流程，对每一类碎片集以贪心算法按照最优匹配度法则进行拼接完成后，发现有4类碎片拼接完全正确的。只需对其他的7类碎片实行1到3次人工干预，即可拼接出所有类别的碎片。例如图3为实际拼接结果：
11类碎片行内拼接完成之后，得到11个新碎片，再次运用上述方法进行行间拼接，即可复原整个文件。整个拼接过程分为行间聚类，行内拼接，行间拼接3步，在合理的聚类和拼接算法的支持下，实现了碎片的自动拼接复原。
4.结语
本文研究了一种基于聚类分析和贪心算法的均匀碎片拼接模型，详细地介绍了先按照特征位置进行间聚类，后依靠匹配度指标进行拼接的过程步骤，有效地解决了均匀中英文碎纸片的拼接复原问题。充分利用了碎片中的文字分布规律，在横切和纵切同时存在的情况下，极大地简化了拼接过?程，提高了匹配的准确性。为减少拼接过程中的计算量，模型中引进少量的人工干预。如果不考虑拼接计算量等因素，我们仍可改进算法，将部分人工干预过程转化为计算机智能算法实现，从而完全由计算机自主拼接碎片。
参考文献
[1]王坚.非规则碎片拼合关键技术研究[D].南京：南京航空航天大学，2007：10-12.
[2]郑蓓蓓，郭立本.改进的遗传算法应用于碎片拼接[J].计算机与现代化，2011（5）：15.
[3]Justino E，Oliveira L S，Freitas C.Reconstructing shredded documents through feature matching[J].Forensic science international，2006，160（2）：140-147.
[4]Lin H Y，Fan-Chiang W C.Reconstruction of shredded document based on image feature matching[J].Expert Systems with Applications，2012，39（3）：3324-3332.
[5]王轩.碎片拼接[D].浙江大学，2011：1-12.
[6]教育部高等教育司、中国工业与应用数学学会m2013年高教社杯全国大学生数学建模竞赛赛题，网址：http：//www.mcm.edu.cn/problem/2013/2013.html.
[7]王千，王成，冯振元等.K-means 聚类算法研究综述[J].电子设计工程，2012，20（7）：21-24.
[8]周丽娟，王慧，王文伯等.面向海量数据的并行 KMeans 算法[J].华中科技大学学报（自然科学版），2012（1）.
[9]孙吉贵，刘杰，赵连宇.聚类算法研究[J].软件学报，2008，19（1）：
48-61.
[10]柴婷婷，齐璐，孙斌.浅析贪心算法[J].中国科技博览，2011（20）：182.
基金项目：中南财经政法大学经济管理实验教学项目 （No：21431230312）。
【关键词】聚类分析；匹配度；贪心算法；均匀碎片；特征
0.引言
破碎文件的拼接在司法物证复原?、历史文献修复以及军事情报获取等领域都有着重要的应用。目前在文件碎片复原这一领域，国内研究涉及到的都只是不规则的碎片[1-4]，碎片物理性质、几何形状、颜色、纹理等外在特征都无疑给拼接复原的工作带来了便利[5]。但是在实际应用中，并不是所有的碎片都存在易于区分的外在特征，虽然计算机有超强的计算能力，但目前很难对碎片边缘上的文字分布走势特征进行智能地识别，均匀规则的碎片复原就会遇到难点。
对于来自同一页印刷文字文件的均匀破碎纸片（以2013年全国大学生数学建模竞赛B题所给的中英文碎片为例[6]），这些碎片形状大小规则，计算机显然无法从利用碎片外在特征进行匹配。仔细分析这些碎片，可以发现碎片上文字呈现的特征规律，不同碎片上的文字出现的位置特征是不一样的，利用碎片上文字的位置特征，对碎片先按行聚类，对每一类碎片的边缘灰度进行分析比对，运用贪心算法的处理思想每次都将灰度相似度最高的碎片拼接在一起，辅之以少量的人工干预，最后即可逐步自动拼接完成整个文档。计算机仿真实验证明，上述拼接方法快速有效，在处理均匀碎片的拼接问题上能发挥出巨大的作用。
1.假设及数据的预处理
为了能比较好地去阐述拼接模型，现做出以下假设：
（1）所有的碎纸片大小一致、形状规则、边缘整齐。
（2）原中英文文献页边距、行距不变，字符间隔、大小保持不变。
将图像转化为对应的像素矩阵存放在计算机中，矩阵中的元素称为像素，像素的取值在0到255之间，所有的碎片和矩阵都是一一对应。
2.聚类分析
碎片的数量庞大，如跳过聚类直接进行拼接，被拼接碎片要与剩余所有的拼接碎片逐一进行比对，效率低，出错率高。将所有的碎片先按行进行聚类，再拼接，是提高正确率的必要先行过程。
2.1 特征位置的选取
行间聚类，首先必须找出同一行碎片之间的相同点以及不同行碎片之间的差异，仔细分析这些碎片，可从文字位置特征入手。
中英文的书写习惯是按行从左往右，从上往下，拥有相同的行距。每一个碎片上的文字都会出现在不同的位置，在此将这些位置称为该碎片的特征位置。图中中文碎片只可能在非阴影区域出现文字，非阴影区域也就称为碎片的特征位置。对于英文碎片，由于英文字母是以四线三格为标准进行书写，不同于中文汉字的田字格，在特征位置上的选取有一定的差异，此取两行之间的行距空白区域作为特征位置。
以碎片之间特征位置的差异为基础可建立数学模型所需要的距离指标，我们认为两个碎片的特征位置相同或相近，这两个碎片的距离越小，被归为一类的可能性越大。基于此距离指标，采用K-means算法对中英文碎片进行聚类。
2.2 K-means算法的应用
K-means聚类算法是由Steinhaus 1955年、Lloyd 1957年、BallHall 1965年、McQueen 1967分别在各自的不同的科学研究领域独立的提出[7-9]，该算法的核心思想是找出K 个聚类中心使得每一个数据点和与其最近的聚类中心的距离和最小化。该方法采用某个空间距离作为评价相似程度的指标，然后确定评价聚类划分结果质量的准则函数，在给出初始聚类中心点后，用迭代法找出使准则函数取极值的最好聚类划分结果。该算法能对大型数据集进行高效分类，收敛速度快，在现实中应用广泛。具体流程如下：
（1）从碎片集中任意选取最左边一列的11碎片作为基准点，赋给初始的聚类中心。
（2）对碎片集中的每个碎片样本点，计算其与各个聚类中心的距离，并记录与其距离最小的聚类中心的编号label：
（3）重新计算k个聚类中心：
（Nj为label为j的样本数量）
重复步骤2和步骤3，直到达到最大迭代次数，聚类中心不再改变为止。
利用上述K-means算法对2013年全国大学生数学建模竞赛B题所给的英文碎片进行聚类可快速而精准得到如下11个分组，如表1所示（中文碎片聚类结果不再赘述）。
对每一个类中的碎片进行拼接，减少了拼接过程中的比对次数，提高了效率，还降低了出错的概率。K-means算法对中英文碎片的准确聚类，为后续基于贪心算法的碎片拼接提供了有力的支持。
3.基于贪心算法的碎片拼接
3.1 匹配度指标的提出
文献碎成两半，在断裂处的颜色也应该大致相同，具有一定的连贯性。利用碎片边缘颜色的连贯性和对应碎片矩阵在首（尾）行、首（尾）列元素的一致性，可给出碎片拼接匹配标准。假设任给两个碎片对应的灰度矩阵分别为，定义这两个碎片之间的匹配度为：
（RNo为矩阵的列数，start为首列序号1，end为最末尾一列的序号）
同理，在从上往下进行拼接时，匹配度为如下表达式：
（CNo为矩阵A的行数，start为首行序号1，end为最末尾一行的序号）
匹配度即为两个碎片矩阵在拼接处行（列）向量的欧氏距离和的倒数。关于这一指标，这里说明几点：
①匹配度相对于两个矩阵而言，一个矩阵不存在匹配度。
②匹配度数值越大，则认为两个矩阵的匹配度越高。
③匹配度这一指标的优劣直接受CNo/RNo和矩阵数量K的影响，因为在参与计算的矩阵的行数CNo或列数RNo越多，匹配度最高的矩阵为正确的匹配矩阵的概率就越大，出现差错的概率越小；以及矩阵的个数越少，出错的概率也会越小。 由匹配度指标来衡量碎片之间的匹配程度，是可行可靠，易于计算的。
3.2 贪心算法的运用
贪心算法（Greedy algorithm）[10]是一种求某些问题最优解的更简单、更迅速的方法。它省去了为找最优解要穷尽所有可能而必须耗费的大量时间，根据当前状态做出在当前看来是最好的选择，然后再去求解做出这个选择后产生的相应的子问（下转第186页）（上接第183页）题。每做一次贪心选择就将所求问题简化为一个规模更小的子问题，最终可得到问题的一个整体最优的拼接方案[12]。
根据匹配度这一指标，每一类碎片拼接完成之后，若使得所有拼接处的匹配度的和最大，则这就是一个全局最优的拼接。但是碎片的组合数量以阶乘的复杂度递增，对每一种组合都计算器匹配度的和，时间开销巨大。利用贪心算法的思想，将整体最优组合分解为多个局部最优，大幅减少计算次数，即可得出最优的拼接方案。
按照上述流程，对每一类碎片集以贪心算法按照最优匹配度法则进行拼接完成后，发现有4类碎片拼接完全正确的。只需对其他的7类碎片实行1到3次人工干预，即可拼接出所有类别的碎片。例如图3为实际拼接结果：
11类碎片行内拼接完成之后，得到11个新碎片，再次运用上述方法进行行间拼接，即可复原整个文件。整个拼接过程分为行间聚类，行内拼接，行间拼接3步，在合理的聚类和拼接算法的支持下，实现了碎片的自动拼接复原。
4.结语
本文研究了一种基于聚类分析和贪心算法的均匀碎片拼接模型，详细地介绍了先按照特征位置进行间聚类，后依靠匹配度指标进行拼接的过程步骤，有效地解决了均匀中英文碎纸片的拼接复原问题。充分利用了碎片中的文字分布规律，在横切和纵切同时存在的情况下，极大地简化了拼接过?程，提高了匹配的准确性。为减少拼接过程中的计算量，模型中引进少量的人工干预。如果不考虑拼接计算量等因素，我们仍可改进算法，将部分人工干预过程转化为计算机智能算法实现，从而完全由计算机自主拼接碎片。
参考文献
[1]王坚.非规则碎片拼合关键技术研究[D].南京：南京航空航天大学，2007：10-12.
[2]郑蓓蓓，郭立本.改进的遗传算法应用于碎片拼接[J].计算机与现代化，2011（5）：15.
[3]Justino E，Oliveira L S，Freitas C.Reconstructing shredded documents through feature matching[J].Forensic science international，2006，160（2）：140-147.
[4]Lin H Y，Fan-Chiang W C.Reconstruction of shredded document based on image feature matching[J].Expert Systems with Applications，2012，39（3）：3324-3332.
[5]王轩.碎片拼接[D].浙江大学，2011：1-12.
[6]教育部高等教育司、中国工业与应用数学学会m2013年高教社杯全国大学生数学建模竞赛赛题，网址：http：//www.mcm.edu.cn/problem/2013/2013.html.
[7]王千，王成，冯振元等.K-means 聚类算法研究综述[J].电子设计工程，2012，20（7）：21-24.
[8]周丽娟，王慧，王文伯等.面向海量数据的并行 KMeans 算法[J].华中科技大学学报（自然科学版），2012（1）.
[9]孙吉贵，刘杰，赵连宇.聚类算法研究[J].软件学报，2008，19（1）：
48-61.
[10]柴婷婷，齐璐，孙斌.浅析贪心算法[J].中国科技博览，2011（20）：182.
基金项目：中南财经政法大学经济管理实验教学项目 （No：21431230312）。