1基于聚类的规则文档碎纸片拼接模型摘要：摘要：本文针对碎纸机破碎文档后的规则碎纸片拼接问题，提取碎纸片的颜色特征，通过 对碎纸片上边缘的灰度向量将文档分为上边缘为非空白区域和上边缘为空白区域两大类， 再分别以上边缘非空白区高度和空白区高度作为聚类参数，将纸片分为若干簇，在每一个 簇中利用相邻两张碎纸片左右边缘向量相似度高来进行拼接，得到若干横条的纸片，然后 以行距和横条间上下边缘相似度为参数来将若干横条拼接为完整文档。1. 引言破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着 重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别 是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人 们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。破碎文档的自动拼接问题 是计算机视觉和模式识别领域内的一个问题，是通过计算机处理，获取碎纸片的形状、 颜色等内容信息，然后利用这些内容信息对碎纸进行自动拼接，恢复碎纸原始的内容。本文主要针对碎纸机破碎后的规则文档碎纸片的拼接问题，提出了一种基于 k-均 值聚类1-3的碎纸片拼接模型。通过提取碎纸片边缘特征进行聚类，将纸片分为若干簇， 在每一个簇中利用相邻两张碎纸片左右边缘向量相似度高来进行拼接，得到若干横条 的纸片，然后以行距和横条间上下边缘相似度为参数来将若干横条拼接为完整文档。 本文提出的基于聚类的规则文档碎纸片拼接模型减少了边缘向量相似度的计算次数， 提高了算法的效率。由于主要解决碎纸机破碎文件后的规则文档碎纸片问题，现将算法前提假设如下：假设文档是黑字白底文档。 假设碎纸机对文档的切割都是垂直和水平方向的，即碎纸片都是长方形纸片。 假设所有碎纸片的长和宽均相等。 假设文档碎纸片恰好能拼成一张完整的文档。2. 特征提取假设一共有 MN 张破碎的纸片，每张碎片的大小为。对每一张碎片用灰度矩mn 阵表示如下：(1,2,3,)kA kMN 111212122212,0,255,1,1, nn kijmmmnaaa aaaAaimjnaaa L L L L MMMMMMMM L L中 中中 中由于每张碎纸片分为白色区域和非白色区域，为了方便计算将碎纸片进行二值化处理，白色区域的灰度值置位 0，非白色区域的值置为 1，得到对应的布尔矩阵表示如下：(1,2,3,)kB kMN 21112121222120,127 ,1,1, 1,127nijn kij ijmmmnbbb abbbBbimjnabbb L LL LMMMMMMMML L中 中中 中提取每张碎纸片上下左右四个边缘向量，分别用表示如,(1,2,)kkkku dlr kN L L下：11121311231112311123,knkmmmmnkmknnnmnubbbbdbbbblbbbbrbbbb L LL LL LL L若为零向量，则认为碎纸片的上边缘为空白区域，设上边缘空白区域的高度向量ku12,upblanknHHUBlankHUBlankHUBlank L L若不为零向量，则认为碎纸片的上边缘为文字区域，设上边缘文字区域的高度向ku量12,upwordnHHUWordHUWordHUWord L L同理可得到1212121212,nnnnndownblankdownwordleftblankleftwordrightblankrHDBlankHDBlankHDBlankHDWordHDWordHDWordWLBlank WLBlankWLBlankWLWord WLWordWLWordWRBlank WRBlankWRBlankHHWWWW L LL LL LL LL L12,nightwordWRWord WRWordWRWord L L通过矩阵列向量和行向量中连续 0 和连续 1 的个数的统计，并对他们的个数取众数，kB得到每一行文字的高度、行距、宽度和字间距.wordHlineDwordWwordD3. 拼接方法根据同一横条的碎片的上边缘一般同属于空白区域或同属于非空白区域，并且空白区域高度或非空白区域高度基本相同的特点。本文设计了一种先通过空白区域高度或非空白区域高度进行聚类，得到有可能属于同一横条的碎片的集合，然后再计算边缘向量相似度来调整碎片的位置关系的算法。33.1 基于 k-均值聚类的碎纸片划分方法通过对碎纸片的特征提取，得到上边缘是空白的碎片计算其空白区域的高度向量，上边缘是非空白的碎片计算其非空白区域12,upblanknHHUBlankHUBlankHUBlank L L的高度向量。分别对和进行 k-均12,upwordnHHUWordHUWordHUWord L LupblankHupwordH值聚类，得到可能属于同一横条的碎片的簇。下面以为例来描述 k-均值聚类算法。upwordH取定中的 k 个数据作为聚类中心对象，所代表的簇是由upwordH12,km mmLimiC中以为最近中心对象的数据构成的集合。则 k-均值聚类是找 k 个中心对象upwordHim，使得目标函数12,km mmL.1(,)(,)12likli iHwordCf mmmdist Hwordmk L L最小，其中表示到的距离。(,)lidist Hword mlHwordim算法：算法：k-均值。均值。输入：结果簇的数目 k，包含 n 个对象的数据集。upwordH输出：k 个簇的集合，使得所有对象与其最近中心对象的距离之和最小。12,kC CCL 初始化 k 个簇的中心对象集合，令，12,km mmL1min()upwordHm ，任意选取，且。max()upwordkHm 21,kmmL(1,)ijmmi jkij且 repeat 根据簇中对象的均值，将每个对象分配到最相似的簇； 更新簇均值，即重新计算每个簇中对象的均值； until 不再发生变化；3.2 碎纸片拼接模型由 k-均值聚类得到 k 个簇的集合，根据进行聚类的特征，可以初步认12,kC CCL为每一个聚类来自同一横条。对每个一个簇中的图片进行横向拼接。iC建立最优化模型，计算簇内的每张碎纸片的左右边沿向量，的相差度的最小iCirjld4值，即目标函数 ( ) |( ,1,00)ijijMin drli jMNijrl且且且则当相差度的值最小时，这两张碎纸片的匹配度最高。d由于簇中可能存在一些并不属于同一横行的碎纸片被误判在同一簇中，所以设定经iC验阈值 。若，则不进行碎纸片的横向拼接。( )Min d若，则计算00ijrl且( ,1,)ijwordWRBlankWLBlanksimDi jMNij且其中，.,irightblankjleftblankWLBlankWRBlankWW设定经验阈值，若，则进行拼接，否则不进行拼接。sim水平拼接完成后，得到 M 横条的碎纸片，记.12,MIL LLL计算 I 中每一张横条的上下边沿向量,的相差度的最小值，即iujddis目标函数 () |( ,1,00)ijijMin disudi jMNijud且且且则当相差度的值最小时，这两张横条的匹配度最高。dis若，则计算横条的上边缘空白区域的高度和下边缘空白区域00ijrl且iLHUBlank的高度jLHDBlank( ,1,)ijlineLHUBlankHDBlanksimLDi jMNij且设定经验阈值，若，则进行拼接，否则不进行拼接。sim4. 模型计算和分析将规则文档纵横切碎片，被切为 1119 个碎纸片。利用 Matlab7.0 完成碎纸片的特征提取和拼接算法。提取每张碎纸片的特征数据，根据和两个特征向量，upblankHupwordH利用 k-均值聚类的算法划分碎纸片，分别得到 5 个簇和 6 个簇，共 11 个簇，与水平切文档的横条数相同。对簇内的碎纸片左右边缘向量作差，进行碎纸片的相似度比较，得到每一横条的拼接。最后通过文字高度特征和行距的特征对横条进行拼接，整个文档就拼接完成了。在碎纸片的拼接过程中，会出现一些误拼接的情况，这些情况需要人工干预。5如下图 1 和图 2，列举了两种误拼接的情况。图 1 出现误拼接的原因是文字被分割的位置刚好将一个文字分成了在两个碎纸片的边缘向量的颜色相反的情况，显然，计算图1（b）中的两张碎纸片的左右边缘向量的差值会比较大，相反图 1（a）中的两张碎纸片的左右边缘向量的差值比较小，这样就引起了误拼接。图 2 出现误判的原因主要是文字被分割的位置刚好在两个字之间的间隙，图 2（a）和图 2（b）的两张碎纸片的左右边缘向量的差都等于 0，从而引起误拼接。碎纸片拼接过程中虽然存在一定的误拼接，但是总体来看，误拼接的情况是有限的。定 义误拼率来评价模型，如下式100%误拼接碎纸片数误拼率总碎纸片数本文模型的误拼率控制在 20%左右，所以本文的碎片拼接模型具有比较高的效率。5. 结束语本文在应用上有一定的局限性，主要因为本文的研究对象是关于规则文档的规则 分割的碎纸片，而且本文主要是从文档的特征如行距、文字之间的间隙等对碎纸片进 行拼接。文字本身的特征使用的较少，即使使用的文字的高度，宽度也是由文档特征 统计得到的。推广到不规则的分割的拼接是这一应用的方向，在不规则分割碎纸片的 拼接中将更多的从模式识别的角度对文字本身的结构特征提取和从语义的进行拼接4-6。6. 参考文献1Jiawei Han,Micheline Kamber,Jian Pei.数据挖掘概念与技术M.北京：机械工 业出版社，2012：291-320. 2吴景岚，朱文兴.基于 k 中心点的迭代局部搜索聚类算法J.计算机研究与发展，2004,41(10):246-252. 3王春风，唐拥政.结合近邻和密度思想的 K-均值算法的研究J.计算机工程应用， 2011，47(19):147-149. 4罗智中.基于线段扫描的碎纸片边界检测算法研究J.仪器仪表学报，2011，32(2):a.误拼接误拼接b.正确拼接正确拼接图图 1.1.人工干预情况人工干预情况一a.误拼接误拼接b.正确拼接正确拼接图图 2.2.人工干预情况人工干预情况二6289-293. 5罗智中.基于文字特征的文档碎纸片半自动拼接J.计算机工程与应用， 2012，48(5):207-210. 6朱延娟，周来水.二维非规则碎片的匹配算法J.计算机工程，2007，33(24):7-9.