基于NCC的PCB图像配准算法研究

舒 军， 李 灵， 邓明舟

(1 湖北工业大学电气与电子工程学院， 湖北 武汉 430068；2 湖北工业大学太阳能高效利用及储能运行控制湖北省重点实验室，湖北 武汉 430068)

PCB数码喷印技术作为一种高效、高精度的新型PCB字符喷绘解决方案，在缩短生产周期、提高产品质量、降低生产成本和减少环境污染等方面有显著优势，该技术正在逐步取代传统PCB制造工艺。在PCB数码喷印中，配准算法的目的是寻找基板图像中的Mark点位置，而Mark点的多样性以及与焊盘、导线等非目标因子的相似性是PCB图像配准主要技术难点。

2012年，郭峰林等学者[1]采用特征线匹配的方法，并提取边缘信息作为特征对Mark点配准,该方法对边缘信息的完备性依赖较高。2013年，管士勇等学者[2]采用特征点匹配的方法，提取图像中低维描述符KPB-SIFT[3]作为特征进行匹配，在仿射变换、遮挡、视角变化等复杂环境下具有一定稳定性，但KPB-SIFT提取算法计算量大、效率较低。2015年，岑誉等[4]采用模板匹配的方法，利用权重式椭圆拟合对PCB图像中Mark点配准，类似的还有熊光洁[5]基于Hough变换的Mark点快速定位方法、Liu[6]基于随机圆( randomized circle detection, RCD) 检测的定位方法，上述方法对圆形Mark点配准精度较高，但对多类型的Mark点识别存在局限性。2019年，刘俊锋[7]设计了一种基于多相机的大尺寸PCB定位系统，采用改进的归一化互相关性配准方法(normalized cross correlation, NCC)Mark点实时查找，该方法实时性高，但系统由多处理器分布式计算，要求较高的硬件成本。同年，Wei等学者[8]基于深度神经网络实现PCB精确配准和定位，结合支持向量回归(SVR)的简单多层感知器(MLP)、卷积神经网络模型对PCB图像进行配准，精度明显高于传统算法，但时间效率较低，且缺少足够样本训练，深度学习的方法在本文应用存在较大局限性。

模板匹配采用单一或低维度特征比对，在效率上高于其他算法，但全局遍历图像需要占用大量的内存资源，对高分辨率PCB图像配准效率受限，无法满足实时性。进一步分析特征点匹配和模板匹配的特点，发现特征点匹配在特征点的描述、查找、多维度特征比对上，花费大量时间，导致时间复杂度较高；而模板匹配则是采用单一或低维度特征进行图像全局比对，精度较差。本文在特征点匹配和模板匹配的基础上对PCB图像配准技术进一步研究。

1 NCC匹配基本原理

(1)

归一化相关性模板匹配的核心思路是归一化待匹配目标之间的相关程度。假设参考图像T的宽高为w×h，待匹配图像G的宽高为W×H，则模板图像T与待匹配图像G在位置(x,y)处的相关系数ρ定义为：

(2)

(3)

2 基于NCC的改进

通过公式(3)可知，基于归一化互相关性的图像配准总算法时间复杂度为O(n×m×h0×h1)，即需要遍历CS与CR中所有点的组合，对于PCB图像配准，存在大量关键点，即n和m较大，是算法效率的主要约束。另外，由公式(2)可知，关键点的特征块gj大小h1直接影响相关系数，在配准精度和效率方面均有影响。若特征块选取过大，对于相关系数相差过多的候选点会产生大量的冗余计算，算法效率较低。若特征块选取过小，关键点周围的灰度信息无法表达完备，配准误差增加。

分别针对以上两个问题，进行如下优化。候选点集的优化，分析PCB图像中关键点，发现正确配准点的空间距离偏移量变化较低。针对这一特性，本文通过计算关键点间的欧氏距离关系建立配准点的空间特征向量，并基于统计滤波器(statistical outlier removal，SOR)的方法将相关性较低的配准点剔除，以此得到关键点集CS中每个点的候选点集；特征块的优化，则通过分析特征块大小对相关系数的影响，提出一种自适应的特征块选取算法。基于动态规划(dynamic programming，DP)的思想，将特征块边长h1的设定问题转化为多阶段决策问题，利用广度优先搜索方法(breadth-first search，BFS)动态扩大特征块边界，通过“剪枝”的方法截止搜索，提高特征块质量，减少配准误差并提高效率。

2.1 候选点集优化

统计滤波器[9]是利用图像的局部统计特征剔除离群点，其中离群点是指特征值与统计特征值偏差较大的点。该方法的思想是对每一个点的邻域做统计分析，计算该点到所有临近点的平均距离作为局部特征值，将特征值在统计特征范围之外的点定义为离群点，其中统计特征范围由所有特征值计算均值和标准差决定。

在图像配准前需分别提取参考图像和浮动图像的关键点集CS和CR，分析Mark点图像的特点可以看出，关键点信息多集中于角点上，采用SUSAN角点检测[10]的方法得到关键点集，该方法通过邻域像素值比较来确定角点。考虑两幅图像的关键点提取算法相互独立，在程序中采用多线程处理。

1)建立领域，计算各阶矩，公式如下：

3)确定统计范围，分别通过下式计算局部特征值集合的均值μ和标准差σ。

2.2 优化特征块

图 1 图像块对相关系数的影响实验图

分析图1d，发现正确候选点的相关系数ρ随着特征块h1的增加而单调递增，但错误候选点当h1=20时出现明显的特征错误(图1f)，使得ρ在[20,30]区间单调下降。

图 2 动态规划流程图

在设计动态规划时，边界条件选择和状态转移方程的设计如下：

1)边界条件选择

2)状态转移方程

通过动态规划思想，将主要问题转化为每一阶段的小问题，即h1的增加对ρ的影响，因此需将式(2)转化为迭代式。为便于分析，对原公式归纳整理如下：

其中：

通过整理易知，Stg(t,g)为参考特征块t对浮动特征块g在尺度h1下的卷积运算，Stt(t)和St(t)分别为参考特征块t在尺度h0下的像素灰度平方和以及灰度和，Sgg(g)和Sg(g)分别为浮动特征块g在尺度h1下的像素灰度平方和以及灰度和。

上述公式均有累加性质，将ρ(t,g)中累加顺序改为将候选点作为起始点的广度优先搜索，如图3a所示，对于h1=n+1阶段的相关系数ρ(tn+1,gn+1)可以由h1=n时的Stg、Sgg、Sg并加入边界区域，即图3(b)中gn+1∩gn区域，求得。

图 3 广度优先搜索示意图

则Stg(tn+1,gn+1)和Sgg(gn+1)可写成迭代式，如下式所示，Sg同理，得到对于相关系数ρ的状态转移方程ρ(tn+1,gn+1)。

3)决策设置

通过分析图1可知，随着h1的增加，当相关系数ρ下降时，可直接设定该点为错误候选点。因此，当ρ(tn+1,gn+1)<ρ(tn,gn)时，决策当前点为错误候选点，结束迭代；否则继续迭代，即增加h1，进入下一阶段，直到达成边界条件。

3 改进的NCC算法实现

将PCB图像(图4b)与Gerber图像(如图4b)中对应目标区域的关键点进行匹配，筛选出配准点集。其中PCB图像分割采用了马尔科夫随机场模型(markov random field， MRF)[12]的图像分割算法。拟定目标区域有两种，第一种对于PCB上Mark点区域，第二种是铜层区域。PCB配准算法由三个步骤组成(图5)，分别为关键点提取和本文改进的候选点优化、特征块优化。

图 4 PCB图像分割样本局部示意图

图 5 改进的NCC图像配准流程图

算法1 候选点优化算法

输入：关键点集CS，关键点集CR

输出：候选点集C*

步骤1：分别遍历CS和CR，计算各阶矩。得到PCB图像和Gerber图像的质心坐标；

步骤2：分别遍历CS和CR，计算各点的方向特性。得到方向特性集合θS和θR；

步骤7：跳转到步骤6，直到遍历CS和遍历CR结束。得到关键点集CS对应的候选点集C*。

算法2 基于特征点优化的配准算法

输入：关键点集CS，候选点集C*

输出：配准点对集合CSR

步骤4：比较当前h1=n阶段与上一阶段(h1=n-1)的相关系数ρ。若递减则结束搜索；反之，进入下一阶段，即h1=n+1；

步骤6：跳转到步骤1，直到遍历CS结束。得到最终的配准点对集合CSR。

综上所述，候选点优化算法的时间复杂度为O(n×m)，基于特征点优化的配准算法的时间复杂度为

4 实验

实验样本按工艺的不同分为三类，分别为硬质 PCB图像、柔性 PCB图像、 PCB铜层图像，每类样本包含50张图像，样本局部如图6所示。采用基于马尔科夫随机场模型(MRF)[12]的图像分割算法对各类原始PCB图像分割，分割效果如图7所示。图像配准是PCB数码喷印系统中机器视觉算法的一个中间环节，输入为分割后的PCB图像，输出为配准点集。从候选点集和特征块两个方面进行优化。首先确定配准算法的实验设置和评价指标；再分别对提出的候选点集和特征块优化算法有效性实验，分别在精度、效率和鲁棒性三个方面，验证优化配准算法的有效性和优势。

图 6 样本局部示意图

图 7 MRF算法分割效果图

4.1 实验设置和评价指标

样本根据PCB板面宽度不同分为5 cm、10 cm、20 cm、50 cm四组样本，每组样本分别为呈现不同程度的刚性变换的10幅图像。在提出的候选点和特征块优化算法上分别进行实验，随机取一组样本的局部区域对候选点优化过程可视化展现，并分析优化前后的精度率和效率的变化。此外，对于工业现场中出现的配准目标刚性变换条件下，进行鲁棒性测试。最后，通过与文献[3]、[8]、[7]方法实验对比，验证本文算法的可靠性。

在评价指标方面，图像配准精度由匹配率和正确率构成。匹配率等于匹配数除以关键点数，主要度量候选点集的质量，匹配数不变的情况下，候选点集越少配准率越高，说明候选点集的质量越好，反之则质量越差；正确率等于正确配准数除以匹配数，主要度量配准效果，若配准点集中人工标定的正确配准点越多则正确率越高，说明配准方法的有效性。

4.2 候选点集优化实验

采用统计滤波的方法对候选点中的离群点剔除。为证明该方法剔除离群点的有效性与配准算法的匹配率和效率优势，本节实验将首先通过部分样本的候选点集优化前后进行可视化比对，再统计配准算法的匹配率和效率，分析优化前后对配准算法的影响。图8将PCB图像关键点对应的Gerber图像关键点集的优化效果可视化。

图 8 候选点集优化效果图

将图8b与图8c中灰色点数量对比可以看出，优化后的候选点集数量明显减少。该实验表明，通过统计滤波可以有效保留正确配准点，且有效滤除错误点。

进一步地，将Gerber图像做旋转等处理，测试该方法在刚体变换下的鲁棒性(图9)。从图9中可以看出，在刚体变换下，该方法依然可以较好地滤除错误点，保留正确配准点。

图 9 刚体变换下优化效果图

表1展示了候选点优化前后对样本的配准精度和效率比对实验，此实验未加入特征块优化，选用h1=60的特征块大小。

表1 优化前后匹配率

由表1知，对候选点优化后，可大幅度减少候选点数量，提高配准率，并缩短算法的时间复杂度。综上所述，提出的基于统计滤波优化候选点可有效滤除错误候选点，提高配准精度和效率。

4.3 特征块优化实验

候选点优化的基础上，本章提出动态规划思想确定特征块长度，达到特征块优化的目的。为证明该方法的有效性，本节实验将在前一节实验的基础上，对特征块优化前后的正确率和效率进行实验。表2展示了图8样本的特征块优化前后匹配率、正确率和配准时间的变化，其中特征块优化前实验为上节候选点优化的结果。

表2 优化前后匹配率

由表2知， 精度上， 优化后匹配率有一定程度的下降， 而正确率大幅度提升， 原因是特征块大小若设置为固定阈值， 可能存在较多错误点， 从而匹配率较高， 但正确率较低； 效率上， 优化后的配准时间大幅度减小， 提取部分关键点的特征块h的取值可以发现原因， 如图10展示了选取部分改进后的迭代截止点时的特征块大小， 图中灰色圆圈标注的点为正确配准点， 其他点为错误候选点。 当出现错误配准点时， 动态规划可以提前跳出迭代， 减少冗余计算， 因此降低了原配准时间复杂度O(n×m×h0×h1)中的h1， 大大减少配准时间。

图10 动态规划特征块h取值

4.4 综合实验

在分割后的基板图像提取连通域并遍历，将连通区域的局部图像作为参考图像。再遍历初始化中的Mark点索引，将每个Mark点的Gerber图像作为浮动图像。程序主线程对参考图像基于SUSAN算法提取关键点CS，并分配子线程对浮动图像提取关键点CR。配准算法采用改进的NCC算法步骤进行，先对候选点优化，输入关键点集CS和CR，输出候选点集C*，然后基于特征点优化的配准算法，最后输出配准点对集合CSR。表3展示算法改进前后对于各PCB实验样本的平均正确率和配准时间。

表3 优化前后匹配率

由表3知，优化后的配准正确率在小面幅(宽度10 cm内)样本上可在98%左右，在大面幅50 cm样本可控制在96%以上，有效提升配准精度；配准效率方面，优化后的配准时间有大幅度提升，小面幅样本配准时间在0.5 s以内，大面幅样本配准时间在7 s左右。结合硬件环境分析，配准算法采用的是并发计算，每个线程占用的内存资源峰值是配准效率的主要约束条件，通过候选点集优化减少关键点匹配计算次数，使得并发率提高，因此配准效率具有较大提高。改进的NCC配准效果见图11，其中灰色连线将配准点的坐标位置可视化。

图11 配准效果图

为验证算法的可靠性，将样本组改为100 mm、300 mm、600 mm，通过与文献[3]、[8]、[7]方法作实验对比，配准算法的效率对比图

图12 不同配准算法的效率对比图

通过图12可以发现，文献[3]采用的KPB-SIFT依赖多维度特征，配准效率远低于文献[7]和本文算法，而该现象在基于深度神经网络的文献[8]方法中更为明显；文献[7]改进传统NCC算法，适应分布式计算，但时间复杂度依然略高于本文算法。提出的Fast-NCC配准算法可有效提高配准正确率和效率，本节实验证明了该优化方法的有效性。

5 结论

针对PCB数码印刷系统中NCC图像配准效率低的问题，从候选点集和特征块两个角度进行优化。实验表明，该方法对于宽度在10 cm以内的PCB配准正确率在98%左右，配准效率在0.5 s以内；对于宽度在20 cm以上的PCB配准正确率在97%左右，配准效率在1～7s。提出的改进方案可有效提高配准精度和效率。