基于进化计算的碎纸拼接重构算法研究

党悦晨， 李 婉， 周 强

（陕西科技大学a.电气与控制工程学院；b.电子信息与人工智能学院，西安710021）

0 引 言

二维碎片的拼接重建，在考古［1］、刑侦以及人民币修复［2-3］等问题上都有着广泛的应用。当面对基于少量，规则碎片的简单拼接问题上，可以通过人工比对的方法进行手动拼接，较为准确的还原出碎片的原始形状。但实际所需要进行拼接的碎片不仅形状不规则，且数量庞大。这时，如果单纯依靠人工的方式将其复原不仅耗时耗力且在碎片已经严重破损的基础上易造成2 次损坏。随着计算机以及图形学技术的飞速发展，各类图像处理算法也在不断地优化，出于保护碎片，同时提高复原效率的目的，提出利用计算机进行辅助实现碎纸片的自动拼接［4-5］。

目前，在二维碎片拼接方面，国内外已有大量学者进行了相关研究。针对规则碎片，文献［6-7］中通过建立基于0-1 规划的拼接模型来实现拼接。文献［8-9］中在对碎片的聚类分析上做了一定的工作。以上的研究对于规则碎片的拼接重建均取得较好的效果，能够实现准确并快速拼接，但并不适用于非规则碎片。

针对非规则碎片。文献［10］中提出了一种比对碎片边缘边长以及灰度互相关的方法来实现匹配，该方法简单快速，容易实现，但通常情况下碎片的边缘轮廓复杂，若仅用边缘边长这一特征值对其进行描述未免过于单薄，且当获取碎片图像时，若因光照等外界环境因素的影响而形成的相邻碎片图像色彩差异，则无法使用灰度互相关法。故该方法仅适用于极少数较为理想情况下的碎片拼合。文献［11］中所提出基于角度的粗匹配以及基于角边长的细匹配在拼接速度上有显著的提高，但因过度依赖角点寻找的准确度，使得鲁棒性较低，且最终的拼接结果精度较低。文献［12］中采用基于弧长-累计转角图的分析方法进行局部匹配，再提出使用蚁群算法，即利用局部匹配所产生的候选对来构建搜索图，通过信息素的传递实现全局拼接。该方法通过正反馈的过程将系统向最优解的方向不断引导，具有较强的鲁棒性，但存在收敛速度过慢，易陷入局部最优解的问题；文献［13］中在最终拼接部分使用改进的遗传算法，利用优胜劣汰的进化过程来克服传统拼接技术回溯性高的问题，但因其在每一次进化当中都将当前最优匹配对进行融合，故易受局部最优的影响，无法实现遗传算法基于全局进行最优解寻找的优越性。

针对以上所存在的问题，本文提出基于进化计算的碎纸拼接重构算法，旨在改进传统拼接的基础上，结合自然计算，克服需要严格把控外界环境、角点精准度要求过高以及易受局部最优解影响等问题，提高拼接重建的准确性和鲁棒性。在特征提取阶段，提出将Primal Sketch模型所得到的稀疏表示应用至目标物体边缘轮廓的提取，因边缘线段所具有方向性，故可便利于后续转向角特征的计算。两两匹配阶段，遍历采样点对齐算法，有效地实现碎片间的匹配对寻找，得到两两匹配数据库。拼接阶段采用进化计算，通过设置高效合理的编码方式，借助迭代实现进化，最终逼近最优解。因进化计算具有良好的全局搜索能力，避免陷入局部最优解的“死循环”当中，该算法可以有效地实现二维碎片的拼接重建。

1 基于Primal Sketch的特征提取

1.1 Primal Sketch预处理

根据Guo等［14］在Marr的计算视觉理论基础上提出的Primal Sketch模型，一幅完整的图像可以分为可素描部分以及不可素描部分。其中可素描部分去掉了目标区域的纹理信息，用一组包含语义的有向线段来表示出位置结构信息，即对图像进行由点和线构成的稀疏表示［15］。其实现方式是由图1（a）所示的滤波器字典中的基元作为检测器去对图像中的点和线目标进行匹配，并在对应位置使用图1（b）中的符号进行标记，得到Primal Sketch特征信息。

图1 滤波器字典以及标记符号

因Primal Sketch特征所具有独特的语义，故通常将该方法用作目标识别［16］或图像降噪［17-18］。本文通过利用其所提取的显著结构信息，得到目标区域的边缘轮廓，并利用边缘线段所具有的方向性，结合改进后的弧长-累计转角图的方法，实现特征提取与特征表示。

以图2 所示的原始图像为例，若使用传统的Canny算子进行边缘检测，仅能得到一组如图3（a）所示离散的点，并未包含任何结构语义信息，故对于后续的特征提取操作还需进行一系列烦琐的处理，如角点的寻找。基于Primal Sketch的特征提取所得到的是一组有向线段组成的封闭多边形，其具有的独特语义，可以提取出素描线段的位置信息以及方向信息，同时具有更强的抗噪性以及稀疏性，如图3（b）所示。

1.2 转向角特征的提取

借助于Primal Sketch特征提取所得到的具有方向信息的边缘线段，通过对弧长-累计转角图的特征提取方法进行改进［19］，将碎片的边缘轮廓表示成一组以转向角为元素的特征集合，并以此作为基础进行后续的碎片间特征比对。

图2 原始图像

图3 Canny算子与PrimalSketch比对

相比于文献［19］中所提出的基于φ-s分析法中对每一段边的长度以及相邻边之间的角度变化进行独立计算，再依次设置为X 和Y 轴，将两个度量信息合并为同一条曲线，将曲线转化为直方图的形式进行比对。本文在此基础上进行改进，采取将两个度量信息融合为一组可直接进行比对的一维特征串集合的方法。

图4 转向角特征表示示意图

以图4 所示的部分边缘线段为例：图中，向量a、b、c、d为组成边缘轮廓的有向线段，以其中两段边缘线段b和c为例，通过计算出当前线段与其前一相邻线段之间的夹角θ1=〈a，b〉、θ2=〈b，c〉，以此值作为特征值对两线段的第一个相交顶点以及线段上的全部采样点个数为代表的具体特征串形式{…，θ1，…，θ1，θ2，…，θ2，…}。其中，特征串所包含的连续元素值相同的个数即表征为该边缘线段的长度。

改进后的方法以一维特征串集合的表示形式代替直方图的建立，降低了数据维数，提高后续遍历比对中的算法效率。该算法实现简单，且具有平移旋转不变性。即便存在有噪声点，也因其角度差值过小或线段长度过短而被忽略，故具有强鲁棒性。

2 匹配碎片数据库的建立

对于全部待拼接碎片，以排列组合的形式得到任意两个碎片为一组的所有可能，称为匹配碎片。匹配碎片数据库的建立分为3 个步骤：①匹配段的寻找。提出遍历采样点对齐算法，寻找到待匹配碎片对应的最优匹配段。②按照所得到的最优匹配结果对碎片对进行几何变换，使匹配段部分重合。③根据拼接结果，对碎片对进行基于面积差值以及长度匹配值的拼接匹配度度量。

2.1 匹配段的寻找

对于2 个真正匹配的碎片而言，在其匹配段部分的转向角变化必然是一致的，为寻找出该匹配片段，本文提出遍历采样点对齐算法，即通过使用遍历的方式，依次以一个碎片上的每一个单位采样点为起点，与另一碎片的固定起始点进行对齐，进行差值比对。当转向角集合的差值在误差阈值内的个数为最多时则为最佳匹配，同时，得到最佳匹配段的坐标信息。

算法的具体步骤如下：

选取长度较长的碎片记作seg_A，长度较短的记作seg_B。取seg_A的方向为顺时针，seg_B 的方向为逆时针。

固定seg_B保持不动，将seg_A 从第1 个采样点开始依次作为匹配的起点，同时截取与seg_B 相等的长度和其进行比对。完成一次比对，seg_A 向左移动一个采样间隔的单位，直到seg_A 的所有采样点均被遍历到作为起始点与seg_B 的第1 个点对齐进行比对。其匹配过程的算法思想如图5 所示。

由于碎片的边缘轮廓是封闭图形，故在进行比对时，当seg_A移动到比对长度小于seg_B的长度时，需要将seg_A的首部移动拼接到尾部，以始终保持seg_

A与seg_B的比对长度相同。其移动拼接示意图，如图6 所示。

图5 匹配过程

图6 移动拼接

对于每一次遍历得到的比对段，计算其特征间的差值，得到多个特征差值集合。同时计算出集合中元素值在阈值内的个数，选取个数最多的情况为该碎片对的最佳匹配，并找到该情况下连续元素值在阈值内的片段为最佳匹配段。提取最佳匹配段首尾两点的坐标，记为位置信息。统计最佳匹配段所包含采样点的个数，得到长度信息记为匹配长度度量函数其中：i、j为两个进行匹配段寻找的碎片编号。特征差值比对如图7 所示，其中abs 即比对后所得的特征差值集合。在理想情况下，匹配段的特征差值为0，故在此用数值0 表示元素值在阈值内的情况。

图7 特征差值比对

2.2 匹配碎片的拼接

得到碎片的匹配信息后，使用平移矩阵

式中，rotateangle为旋转角度。

对碎片进行操作，实现碎片间的两两拼合。矩阵形式如式（1）、（2）。

平移距离以及旋转角度的选取原则如图8 所示。

图8 移动参数选取

2.3 拼接碎片的匹配度度量

通过建立匹配碎片数据库，来对碎片对之间拼接的优劣情况进行度量。数据库的内容包含匹配面积度量函数以及匹配长度度量函数。

式中：arearepeat为面积叠加值；areaspace为面积空隙值；areai、areaj分别为碎片i与碎片j的独立面积。

S(i，j)的值越大，其匹配效果越差；反之，匹配效果越好。

匹配长度度量函数L(i，j)即为3.1 节中计算所得。

3 基于进化计算的全局拼接

二维碎片的拼接属于非确定性多项式（Non deterministic Polynomial，NP）问题，其特点为验证一个问题的解要比生成一个问题的解快得多。对于此类问题，若使用穷举法来进行处理，算法的复杂度会成指数上升，势必大大增加算法的执行时间。

传统方法通过遍历的方式寻找局部最优解直接进行拼接，再将二者融合更新为一个整体进行下一次的寻找。一旦某一次的局部最优解寻找错误，则导致最终结果错误，需要回溯至出错位置重新向下进行，故效率较为低下。进化计算通过模拟生物进化论，以“优胜劣汰”的方式基于全局寻找适应度最高的匹配方案，进行最终拼接［6，20］。算法流程如图9 所示。

3.1 编码方式

本文采用顺序排列的二进制编码对问题的解进行表征。与一般形状为“长条形”或“正方形”的规则碎片编码方式不同，本文研究的碎纸片由于形状的不规则性以及碎裂位置的随机性，无法使用传统的编码方式。针对不规则碎纸片对象，结合两两匹配数据库，利用二值符号集合｛0，1｝表示碎片对的拼接与否，得到更加灵活的编码方式。

图9 进化计算流程图

随机生成一个个体数为M的初始化种群，基因的排列即按照碎片序号由小到大依次与后面碎片进行匹配的顺序，若碎片总数为X，则理想状态下其染色体长度为

但实际情况下，无法保证任意2 碎片间均有配对的可能，故应针对实际情况调整染色体长度。

3.2 适应度函数

适应度函数的设置决定了算法的收敛速度以及最终结果，故合适的适应度函数极其重要。考虑到相关参数对拼接优劣的影响，对于3.1 节中得到的匹配长度度量函数L(i，j)以及3.3 节中得到的匹配面积度量函数S(i，j)，通过

进行计算，得到适应度函数fitness(p) ，用来判断个体p相对于整个种群的适应度优劣。

因匹配面积与匹配长度的结果值差距较大，故通过将其统一到同一数量级，并结合二者在拼接优劣判断中所占的不同权值比重，设置比例参数λ 和μ。λ即关于匹配长度的比例参数，μ 即关于匹配面积的比例参数。

3.3 遗传算子

选择算子作为实现“优胜劣汰”思想的具体实施步骤，本文采用锦标赛选择法。即在每一次的迭代过程中，从种群中抽取一定数量的个体，选择其中适应度值最高的进入到子代种群，重复该操作直到种群规模达到原来的规模。该方法具有更强的随机性，在保证种群多样性的同时，使算法快速收敛至最优结果。

交叉算子采用一点交叉。当条件满足交叉概率时，将相邻两个染色体从中间位置进行一点交叉，提高遗传算法的搜索能力。

变异算子采用二进制变异。当条件满足变异概率时，随机选取染色体上任一基因位，对该位置的基因进行取反，保证种群的多样性。

通过选择，交叉以及变异操作，不断地使种群得到进化，最终实现收敛为对环境适应最佳的个体，该个体即所求得问题的最优解。

4 实验结果

本文使用Matlab 为平台，对两张真实的碎纸片分别进行实验。实验一针对发票碎纸数据。实验二针对照片碎纸数据。均能实现100%的复原成功率。

实验1：碎纸片的数字化图像由CCD 相机拍照所获取，如图10 所示。

图10 碎纸片数据1

对于碎纸片的数字化图像，进行基于Primal Sketch的特征提取，并通过碎片匹配算法得到两两匹配数据库，如图11 所示。

在最终拼接阶段，按照表1 对进化计算的相关参数进行设置。对于其中适应度部分的两个参数λ 和μ，通过表2 进行参数取值对比。由表中数据可得，当参数取值λ = 0.1、μ = 100 时，由于给予匹配长度过高的权值，使得适应度判断几乎没有考虑到匹配面积的影响，故最终收敛结果无法成功得到最优解。而当λ =0.01、μ = 1 000 时，可以在使用最少迭代次数的情况下找到最优解，提高运行速度，故本文选取该参数进行实验。

图11 匹配碎片数据库中部分碎片对

表1 进化计算相关参数设置

表2 适应度函数参数取值对比

对于进化计算通过“优胜劣汰”逐代演化出的全局适应度最高的拼合方案，从两两匹配数据库中选择出相应的碎片对进行最终的拼合。其迭代过程如图12 所示。碎纸拼接重构结果如图13 所示。实验证明，本文所进行的算法研究，可以将独立的发票碎纸数据还原成完整的纸张形状。

图12 进化计算迭代过程

图13 重建结果1

实验2：照片碎纸原始数据如图14 所示。最终的拼接结果如图15 所示。

图14 碎纸片数据2

图15 重建结果2

5 结 语

针对碎纸拼接目前所存在的人工拼接难的问题，本文提出了一种基于进化计算的碎纸拼接重构算法。通过基于Primal sketch 的特征提取，并结合进化计算以“优胜劣汰”的方式求取基于全局的最优拼合方案，实现较为精准的碎纸片拼接重构，大大地提高了拼接的效率。但对于待处理碎片数据出现磨损的情况，则无法实现拼接重建，在后续的工作中将结合深度学习的方法来克服该缺陷，增加算法的适用范围，实现更加精准的重构结果。