完整的纸质文件为司法取证、刑事调查等任务提供了关键信息，取证现场的纸质文件可能面临着被碎纸机破坏的情况，利用图像处理技术对碎纸片进行拼接复原具有重要意义．本文研究对象是被碎纸机规则切割的中文文档．碎纸片边缘整齐，大小形状一致且颜色单一，无法从外观区分它们．随着切割次数的增多，碎纸片粒度变小，每份包含的信息也变得更少，拼接难度也更大．碎纸片拼接分为行间聚类、兼容性评估和行内拼接三个阶段．针对行间聚类阶段，文献[1]根据碎纸片的文字和空白分布特征进行聚类；文献[2]将首列的碎纸片作为聚类中心，提高了聚类准确性；文献[3]建立了字母数据库，基于数据库将字母的位置特征作为特征向量进行聚类．但是现有方法未考虑到异常碎纸片的处理．当文档存在未填充满的文字行，切割得到的碎纸片中会包含大面积的空白段，这类异常碎片会严重干扰聚类结果．针对兼容性评估阶段，文献[4]中的兼容性来自RGB像素方块上的欧几里得距离；文献[3]基于边缘向量间差值建立了代价函数用以衡量碎片间的兼容性．由于中文文字种类的多样性和文字结构的复杂性，仅利用其边缘像素信息无法准确的衡量碎纸片间的距离．针对行内拼接阶段，文献[3]将碎纸片拼接抽象为旅行商问题，并采用遗传算法进行求解；文献[5]提出了一种文化基因算法，基于碎片文字信息将算子引入到目标函数中．但是当碎片数量上升而粒度变小时，单纯采用启发式算法对碎纸片图像进行行内拼接，拼接精度难以令人满意．针对现有研究所忽视的问题，本研究提出了一种基于三元组网络和混合粒子群的碎纸拼接算法．主要贡献如下：针对行间聚类阶段出现的异常碎纸片，提出了一种基于自适应填充的高斯混合模型聚类算法，先对碎纸片向量填充再进行聚类；针对兼容性评估阶段处理的复杂文字信息，提出了一种基于三元组网络的成对兼容性评估模型，提取像素矩阵信息来评估距离；针对行内拼接阶段处理的数量众多的小碎片，基于兼容性评估得到的距离矩阵，提出了一种混合粒子群算法，实现了更加准确的拼接效果．1 碎纸片重建问题描述为简单起见，首先考虑单页仅纵切的文档重建．设向量P=[p1，p2，…，pn]表示对于单页文档仅纵向切割产生的碎纸片集．假设集合中每个元素的排列顺序决定了碎片在原始文档中的真实位置：p3在p2的右边，p1在p2的左边．二元组(pi，pj)代表第j个碎纸片在第i个碎纸片的后面，若j=i+1，则说明这个二元组是正样本对，否则就是负样本对．碎纸片重建问题的一个解可以表示为一个向量P中元素的排列πP=(pπ1,pπ2,…,pπn)，一个完全正确的重建序列就是对于πi=i，其中i=1，2，…，n．规则切割文档的重建可以被看作是一个基于成对兼容性评估的目标函数优化问题[6]．用一个代价函数c:P×P→R来评价两个碎纸片在按顺序并排放置时的成对兼容性．代价函数c(pi，pj)表示将碎纸片pj放在碎纸片pi右边的代价．当j=i+1时，(pi，pj)属于正样本对，c(pi，pj)值偏低；当j≠i+1时，(pi，pj)属于负样本对，c(pi，pj)值偏高．在碎纸片组合的序列中，通过搜索的方式找到一个最优的排列πP*，使得碎片排列的最终结果和原始文档一致．其中，代价函数值是搜索过程中输入的重要信息．搜索中目标函数F的值，由连续分组计算的代价函数值累计而成，即F(πP)=∑i=1n-1c(pπi,pπi+1)．(1)如果将每个碎纸片看作一个顶点，将两个碎纸片之间的拼接视为构建一条边，那么可以在图上进行建模求解，把这个图称作重组图．边的权重可以由两个碎纸片的代价函数值来确定，碎纸片的拼接问题就可以建模为在这个重组图上找到一条最短哈密顿路径，求解这个最优的组合序列就可以转化为寻找旅行商问题(TSP)中的最优路径[7]．TSP问题的表述如下：给定一组顶点和一组描述顶点间权值的边，求访问每个顶点一次的最小(或最大)权值路径．直接枚举所有可能的组合很困难，可以通过一些近似算法求解，比如遗传算法[8]．考虑规则横纵切割的碎纸片，将切割后的碎片排列表示为一个矩阵．比如，对于一个经过3次横向切割、2次纵向切割得到的文档碎片集合，它被表示为一个4行3列的矩阵P，P=p1,1p1,2p1,3p2,1p2,2p2,3p3,1p3,2p3,3p4,1p4,2p4,3．对于这样一个碎纸片集合，首先对其进行行间聚类，将未打乱状态下在二维平面处于同一行的碎纸片聚类到一起；然后对属于同一行的碎纸片，参考上述仅纵切的文档重建策略，计算两两碎纸片间的代价函数值，进行碎纸片的行内拼接．将同一行的碎纸片拼接完成后，可以得到若干条有序拼接的碎纸条，将这些碎纸条进行纵向拼接，得到最终的完整文档．2 行间聚类2.1　向量投影将整张碎纸片的图片作为输入数据，对像素矩阵直接进行聚类产生的计算量会导致程序运行缓慢，因此须要对像素矩阵降维处理同时又能保留其特征．对于中文文档碎纸片，其聚类的重要依据就是文字行和空白行的分布情况，因此可以将每张图片的像素矩阵在水平方向上投影为一个列向量，再利用算法进行聚类．首先将碎片图像转化为灰度图，然后从灰度图中提取出文本区域，并对文本区域进行二值化处理．令Ai为碎片pi的像素矩阵，矩阵规模为m×n．其中位于矩阵第j行第k列的像素点为Ai(j，k)．像素矩阵Ai在水平方向上的投影向量为Hi，矩阵第j行元素经过投影得到的向量元素为Hi(j)．对于Hi(j)，有Hi(j)=0    (∀k∈{0,1,⋯,n-1},Ai(j,k)=255);1    (∃k∈{0,1,⋯,n-1},Ai(j,k)255),向量投影示意图如图1所示．10.13245/j.hust.240203.F001图1向量投影示意图2.2　自适应填充算法由于在段落开始处的空格和段落结束处的空格，导致文本区域出现一些未填充满的文字行，切割得到的部分碎纸片会包含大面积的空白段．如图2所示，将这些包含大面积空白段的碎纸片称为空白碎纸片．区别于处在同一行中文字行和空白行分布正常的碎纸片，这些空白碎纸片缺失了分类时必要的特征信息．它们的存在将严重影响到聚类的效果，从而使得聚类结束后不得不采取人工干预的手段来调整聚类结果．10.13245/j.hust.240203.F002图2空白碎纸片基于此，本研究提出了一种自适应填充算法处理图像中的空白段．对于每个碎纸片，若首部开始出现了空白段，则从上至下检查每次出现的空白段是否大于正常的行距．若异常，则在空白段填充“1”来保证其和同一行的碎纸片文字分布特征相似．若尾部开始出现空白段，则从下往上重复类似的操作．算法1为自适应填充算法，填充结果见图3．10.13245/j.hust.240203.F003图3自适应填充结果算法1 自适应填充算法输入 pic_vector，row_pitch，char_height，top，bottom输出 结果向量ada_vector步骤1 将segment_len初始化为0．步骤2 从top开始往后扫描，判断pic_vector的值是否为0，若值为0，则统计0的连续出现次数，并保存到segment_len．步骤3 当segment_len≤row_pitch时，空白段长度正常，无须填充．当segment_lenrow_pitch时，空白段长度异常，须对空白段进行循环填充，在每次跳过一个row_pitch长度后，对空白段剩下的部分最多填充char_height长度．当剩余空白段长度小于row_pitch时跳出循环．步骤4 从bottom开始向前扫描，判断pic_vector的值是否为0，若值为0，则执行步骤2和3．步骤5 将处理后的pic_vector保存为ada_vector，并输出结果．算法1中：pic_vector为碎纸片经过降维得到的向量；row_pitch为行间距；char_height为字高；top为向量的首元素下标；bottom为向量的尾元素下标；ada_vector为经过填充后的结果向量；segment_len为产生的空白段长度．2.3　基于自适应填充的高斯混合模型聚类算法K-means聚类算法基于欧式距离构造目标函数，聚类形成的簇形状近似圆形，经过计算输出的是对应于类别的确定值．而高斯混合模型是多个高斯混合函数的线性组合，聚类形成的簇近似椭圆形，能拟合出更加特殊复杂的分布．且计算得到的是对应于类别的一系列概率值，携带的信息量更丰富，用概率值表示结果比确定值更加灵活[9]．高斯混合模型聚类算法的目标函数为L(D)=ln∏j=1npM(xj)=ln∑i=1maip(xj|μi,Σi),式中：PM(xj)为所有样本属于第j类的概率之和；ai为混合系数；p(xj|μi,Σi)为样本属于第j类的概率．为后续说明，将基于自适应填充的高斯混合模型聚类算法简称为APGMM．对于水平投影后得到的碎纸片向量，为避免特征信息缺失而造成聚类错误，先运用自适应填充算法对若干空白段进行填充．得到填充完的碎纸片向量后，再利用高斯混合模型聚类算法对碎纸片向量分行聚类．3 兼容性评估3.1　三元组损失对比损失仅仅约束类内距离尽量近而类间距离尽量远[10]，Google团队在对比损失基础上提出了三元组损失，进一步考虑了类内距离和类间距离的相对关系[11]．当构建训练集时，须每次从数据集中选取三个样本．首先从数据集随机选择一个样本作为锚点样本，然后从锚点样本所在类别中随机抽选一个样本作为正样本，最后从排除锚点样本所在类别中随机抽取一个样本作为负样本．三元组损失函数希望正样本在特征空间上接近锚点样本，同时负样本在特征空间上远离锚点样本，且正样本与锚点样本间的距离比负样本与锚点样本间的距离大一个间隔，如Ltriplet(Xa,Xp,Xn)=[da,p2+m-da,n2]+，(2)式中：Xa，Xp，Xn分别为锚点样本、与锚点样本同类的样本及与锚点样本异类的样本；da,p2为锚点样本和正样本在特征空间的距离；da,n2为锚点样本和负样本的距离；m为间隔．当构建碎纸片成对兼容性评估模型的训练集时，如图4所示，选取一张碎纸片作为锚点样本，与其右邻接的碎纸片作为正样本，除锚点样本和正样本的其他碎纸片都可选作负样本．把锚点样本和正样本称为正样本对，锚点样本和负样本称为负样本对．10.13245/j.hust.240203.F004图4样本示意图3.2　基于三元组网络的成对兼容性评估受到孪生网络的启发，一个三元组网络[12]由相同的基础神经网络的三个实例组成，三个实例共享网络的权重参数．当输入Xa，Xp，Xn时，网络将对样本进行特征提取得到特征向量N(Xa)，N(Xp)，N(Xn)．分别计算N(Xa)和N(Xp)，N(Xa)和N(Xn)的间距，得到正样本对间的欧氏距离d +和负样本对间的欧式距离d -．通过训练，让d +尽可能小，而d -尽可能大，且两个距离之间相差一个间隔．为了更好地衡量被切割的中文碎纸片对之间的距离，本研究提出了基于三元组网络的成对兼容性评估模型，它能充分利用碎片边缘像素矩阵的信息，实现距离区分．模型经过训练，提取碎纸片图像的边界部分进行投影，正样本对在度量空间的投影得到的特征向量预计会更加接近，而负样本对投影得到的特征向量会更远．此处的距离度量与兼容性成正比，可用距离函数来描述一对碎片的全局兼容性，式(1)中的成本函数为c(pi,pj)∝E(vi,vj)，其中：v*为碎纸片p*在度量空间投影得到的特征向量；E为距离度量函数．对于同一行碎纸片，两两为一对构成预测样本对．通过欧氏距离函数计算预测样本对之间的距离，可以得到一个度量成对碎纸片兼容性的距离矩阵．同一行碎纸片的距离矩阵将作为行内拼接中混合粒子群算法的适应度函数值．4 碎纸片拼接4.1　基于混合粒子群算法的碎纸片行内拼接遗传算法是一种全局优化算法，但实现过程复杂，涉及参数多，搜索速度较慢[13]．标准粒子群算法实现过程简单，使用参数少，收敛速度快，缺点是容易陷入局部最优解[14]．本研究提出一种基于混合粒子群的行内拼接算法，在标准粒子群算法的基础上引入遗传算法中的交叉和变异操作，并将兼容性评估阶段得到的距离矩阵作为粒子适应度值．粒子与个体极值和全局极值进行交叉，粒子自身进行变异，不容易陷入局部最优解；基于区分度明显的距离矩阵，粒子会更快的逼近最优值，达到快速搜索全局最优解的效果．编码．对粒子群中的每个粒子进行编码，采用整数编码的形式，每个粒子都是结果最优解的部分解，对于拼接问题，粒子群的规模即为被切割的碎纸片数，每个粒子代表着形状相同的碎纸片．计算适应度．将两张碎纸片之间的距离作为粒子的适应度值．借助本研究的兼容性评估方法，将成对的碎纸片图像输入到三元组网络的卷积结构中提取特征向量，再计算两个特征向量间的距离．处理同行碎纸片后将获得一个区分度明显的距离矩阵，每次迭代时在这个距离矩阵中更新当前最优粒子和历史最优粒子．交叉操作．将粒子分别与个体极值和当前全局极值交叉取较大值来进行更新．采用整数交叉的方式实现交叉操作．当通过交叉操作产生的新个体中包含重复编码的粒子时，用粒子个体中不包含的碎纸片编码代替重复的编码．变异操作．变异方法根据生成随机数大小采用三位互换方法或者两位互换方法．两位互换：随机产生两个变异位置，互换变异位置．三位互换：随机产生三个变异位置，互换变异位置．在迭代过程中，采用保留优秀个体策略，当新粒子适应度优于旧粒子才更新粒子．4.2　纵向拼接碎纸片在经过行内拼接后，得到的是长条状的碎纸条．碎纸条的纵向拼接同样要求根据各个碎纸条上下边缘信息，寻找最优的组合顺序，与TSP问题在求解过程中具有相似性，因此也可以运用混合粒子群算法进行纵向拼接．两类拼接采用的混合粒子群算法的主要差异在于适应度函数的构造．待拼接的碎纸条的拼接边缘状态有两种类别，一类在边缘处呈现空白，另一类在边缘处为非空白．对于两张待拼接的碎纸条，根据拼接边缘状态，分成两种情况：待拼接的两张碎纸条，至少有一张在拼接边缘位置为非空白(图5)；待拼接的两张碎纸条，其边缘位置均为空白(图6)．10.13245/j.hust.240203.F005图5拼接边缘非空白10.13245/j.hust.240203.F006图6拼接边缘空白对于第一类适应度，直接利用碎纸片拼接边缘的像素值，求出同一列位置上第一张碎纸片最后一行像素值和第二张碎纸片第一行像素值的欧氏距离，将这个距离作为混合粒子群算法的适应度值．定义第一张碎纸片的下边缘像素值为ai，第二张碎纸片的上边缘像素值为bi，适应度为f1=-∑i(ai-bi)2．可以发现当同一列的像素值越接近，这两张碎纸片越有可能邻接，距离越小，适应度越大．对于第二种情况，定义文字部分的行间距为D，第一张碎纸片下边缘的空白段高度为k1，第二张碎纸片上边缘的空白段高度为k2，适应度为f2=dk1+k2-D/D，式中d为常数，使得f2与f1在取值范围保持一致．5 实验与结果分析5.1　行间聚类实验聚类实验数据集为经过规则纵横切割的中文碎片数据集．数据集分为两类，第一类来自2013年全国大学生数学建模竞赛B题的附件3：1页纸被切为11×19个碎片，简称为数模B3数据集．第二类来自计算机生成的数据集：16页纸，每页被切为8×15个碎片；10页纸，每页被切为10×15个碎片，统称为生成数据集．通过纯度来评估提出的聚类算法的效果，纯度计算公式为P=(Ω,ℂ)=1Zmaxjωk⋂cj，(3)式中：Z为总样本数；Ω={ω1,ω2,…,ωk}为一个个聚类后的簇；ℂ={c1,c2,…,cj}为正确的类别；ωk为聚类后第k个簇中的所有样本；cj为第j个类别中真实的样本．P的取值范围为[0,1]，值越大表示聚类效果越好．选择ICNN行聚类算法[15]、K-means聚类算法[15]、碎纸片行分类算法[2]、启发式聚类算法[16]和标准的GMM聚类算法，与提出的APGMM算法在数模B3数据集上对比聚类效果．选择纯度作为聚类效果评价指标，结果表明：K-means算法的纯度为0.727，ICNN算法的纯度为0.818，标准GMM聚类算法的纯度为0.895，启发式聚类算法的纯度为0.951，碎纸片行分类算法的纯度为0.971，APGMM算法的纯度为1．在第二类生成数据集上，选用APGMM算法、K-means算法和确定初始聚类中心的K-means算法进行对比实验，其中初始聚类中心设置为首列编号．选择纯度作为评价指标，对比结果见表1．10.13245/j.hust.240203.T001表1生成数据集上的各算法聚类纯度算法16×8×1510×10×15K-means0.7880.694初始K-means0.8670.827APGMM0.9410.913对于规模较小的数模B3数据集，本文提出的APGMM算法能够实现完全准确的聚类，远领先于K-means算法和ICNN算法．APGMM算法对碎纸片空白段进行了自适应填充，相较于标准GMM聚类算法纯度也有10%左右的提升．当面对规模较大的生成数据集时，APGMM算法也能保持较高的准确率．相较于K-means算法，高斯混合模型形成的簇不仅是圆形，也可以是椭圆形，增加了算法的鲁棒性，提升了准确率．5.2　兼容性评估实验通过修改文档内容中字体大小、字体样式、字体粗细、行间距等特征，以及随机在行首加入空格生成空白段，来模拟不同样式的文本文档，并利用程序将这些文档的图片进行规则横纵切割，生成形状大小一致的中文碎纸片作为数据集．这些数据集被划分为训练数据集和验证数据集，其中训练数据集共3.96×104张图片，验证数据集共1.069 2×104张图片．用于兼容性评估的三元组网络模型由三个相同的卷积神经网络组成．如表2所示，模型具有相同的卷积架构．10.13245/j.hust.240203.T002表2模型卷积结构类型卷积核尺寸输入尺寸卷积层(Conv2d)5×5×321×156×60激活函数层(PReLU)1×132×152×56池化层(MaxPool2d)2×232×152×56卷积层(Conv2d)5×5×6432×76×28激活函数层(PReLU)1×164×72×24池化层(MaxPool2d)2×264×72×24卷积层(Conv2d)5×5×12864×36×12激活函数层(PReLU)1×1128×32×8池化层(MaxPool2d)2×2128×32×8全连接层(Linear)8 192×16128×16×4在模型训练阶段，批处理的大小被设置为128，训练、验证流程都迭代300次．模型使用随机梯度下降(SGD)从头开始训练，学习率设置为1×10-3．选用的损失函数为三元组损失函数，其中间隔值设置为1．训练三元组网络模型的过程中，在迭代次数超过150次后，训练损失稳定在0.014附近，验证损失在0.01附近．经过300次迭代，训练损失下降到0.014 3，验证损失下降到0.010 2．将三元组网络模型作为特征提取器对碎纸片图像提取得到特征向量，再通过欧氏距离函数计算预测样本对之间的距离，这个距离被用来度量成对碎纸片之间的兼容性．相较于利用边缘向量直接进行兼容性评估，像素矩阵包含更丰富的特征信息，同时三元组损失函数设置的间隔，将会使碎纸片正样本对距离与负样本对距离间有更大区分度．对于同一行碎纸片，计算两两碎纸片的特征向量将得到一个距离矩阵，这个矩阵将作为行内拼接中混合粒子群算法的适应度函数值．5.3　拼接实验在混合粒子群算法中，迭代次数设置为100，个体数目设置为2 000，粒子初始位置随机生成．采取整数编码的方式，每个粒子的位置向量代表同一行碎纸片的排列顺序．其中，以生成的随机数大小来决定变异的类型，大于等于0.5发生三位互换变异，小于0.5发生二位互换变异．对于行内拼接，须要在碎纸片组合的序列中，通过搜索的方式找到一个最优的排列πP*．令πP=(pπ1,pπ2,…,pπn)作为问题的一个解，则每一行的行内拼接准确率为δ(πP)=1n-1∑i=1n-1P((pπi,pπi+1)为正样本对)，最终形成完整文档共m行的拼接准确率，为每一行的行内拼接准确率之和的平均值．在计算机上生成的50份1×16共800块碎纸片图像上，将距离矩阵作为混合粒子群的适应度值，对比混合粒子群算法、贪心算法、遗传算法的行内拼接效果．对多行的行内拼接准确率求平均值，以平均准确率作为评估指标．结果表明，贪心算法和遗传算法平均准确率分别为50.6%和81.5%，而混合粒子群算法平均准确率达到了95.7%，远领先于经典算法和单一的进化算法．贪心算法考虑当前最佳的决策，容易在TSP问题中陷入局部最优解．而遗传算法在保持种群数量和迭代次数一致的情况下，收敛速度和求解精度远不如混合粒子群算法；在求解时间上，遗传算法也会更长．从实验结果来看，混合粒子群算法能够更快地逼近全局最优解．对于数模B3数据集的11×19共209张碎纸片，本文提出的拼接算法能达到100%的准确率．经过行间聚类和兼容性评估后，利用混合粒子群算法进行行内拼接和纵向拼接，能自动准确地根据碎片复原文档，得到复原文档如图7所示．10.13245/j.hust.240203.F007图7复原文档6 结语在行间聚类阶段，对于碎纸片进行自适应填充能够避免特征信息丢失带来的聚类结果错误，提高聚类准确率．在行内拼接阶段，利用三元组损失函数训练好的卷积结构将碎纸片图像投影到度量空间中，通过欧式距离函数计算得到区分度明显的距离矩阵．将距离矩阵作为粒子适应度值，混合粒子群算法提高了拼接的精度．经过实验验证，本文提出的破碎文档重建方法在碎纸片拼接复原工作上具有良好效果．