ABSTRACT

Nowadays the domestic industrial applications of wafer automatic slicing mainly adopt gray-based template matching method. However, its calculation is quite time-consuming with low slicing efficiency. This paper proposes an improved template matching algorithm based on geometric edge to achieve the goal of accelerating the traditional algorithm. It generates appropriate edge template by Canny edge detection; calculates the gradient direction of template edge curve, which is used to calculate similarity as matching information; optimizes the searching strategy by using the similarity threshold determination. Then, the rough traversal matching is implemented at the top layer of the image pyramid and the matching process continues layer by layer until the bottom. The result of experiment shows that the algorithm proposed in this paper performs high robustness, which can obtain good matching result under different conditions of objectives, including uniform or non-uniform illumination and partial occlusion. Besides, it meets the real-time requirement while the accuracy is ensured, which can be applied to practical industry of automatic wafer image slicing.

Keywords:Template Matching, Geometric Features, Similarity Measures Function, Image Pyramid Layer

基于改进模板匹配的晶圆划切算法

高晨舒，翟锐，薛健^*，吕科

中国科学院大学工程科学学院，北京

收稿日期：2017年6月15日；录用日期：2017年7月3日；发布日期：2017年7月6日

摘 要

当前国内晶圆自动划切的工业应用中，主要采用基于灰度的模板匹配方法，但其计算量大、划切效率较低。本文提出一种改进的基于几何边缘的模板匹配算法，通过Canny边缘检测生成合适的边缘模板，计算模板边缘曲线的梯度方向作为匹配信息进行相似度计算，采用相似度阈值判断优化搜索策略，然后在图像金字塔最顶层进行粗遍历匹配获得潜在匹配目标，逐层匹配直到最底层，以达到对传统的几何模版匹配算法进行加速的目的。实验表明，该方法具有较高的鲁棒性，对于目标均匀或非均匀变化的光照、部分遮挡的情况可以得到良好的匹配效果，而且算法在保证精度的同时可以满足实时性要求，适用于晶圆图像自动划切的工业应用。

关键词 :模板匹配，几何特征，相似性度量，图像金字塔

Copyright © 2017 by authors and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

1. 引言

模版匹配是晶圆自动划片图像处理系统中重要的组成部分。晶圆的加工制造是半导体制造业的一项关键工艺过程，其中，晶圆划片工艺是把一个晶圆划片成单独的芯片。划片机主要用于硅集成电路，发光二极管，铌酸锂，压电陶瓷，砷化镓，石英，玻璃，太阳能电池片等材料的划切加工 [1] 。我国从七十年代末开始研制划片机，但是由于我国落后的工业基础，目前国产划片机性能仍然落后于国外先进设备。国内现有的划片机切割软件在晶圆的划切中需要人工手动对准 [2] ，寻找切割区域使得划片机操作的复杂性高，人工成本高，自动化程度低，为了提高产能，对晶圆划片机专用图像处理软件系统的研发提出了需求 [3] 。目前，国外全自动划片机釆用了可对准显微镜进行自动图像识别，自动图像对准的CCD光学系统 [4] 。DISCO公司的双轴对装式12英寸全自动划片机，代表着划片机的最高技术水平，并逐渐进入实用化阶段。而由于商业保密性和研究针对性，国内外很少有公开发表的针对晶圆芯片划切的研究，因此，晶圆自动划切工业的应用对视觉系统的研究提出了需求。

机器视觉有利于信息集成，是实现计算机集成制造技术的基础 [5] ，划片机图像识别系统的应用，可以提高划片机的视觉识别效率和自动对准的能力，使得在改变工件角度、尺寸、明暗度等条件的情况下，仍能精确定位物体，实现自动对准划切。

模板匹配是机器视觉技术重要研究内容之一，在目标识别、工件精确定位等领域中得到广泛应用 [6] [7] [8] 。目前国外著名的商业化机器视觉软件包，如MVtec的HALCON HMatchlt、EURESYS的eVi-son asyFind、Adept的AdeptSight及DALSA的Sapera等已开发出性能良好的几何模板匹配算法，但由于商业保密的原因，其所采用的技术核心鲜有报道。已公开发表的几何特征模板匹配算法很少能达到商业化软件的性能。傅卫平等 [9] 提出一种综合应用SIFT特征、马氏距离和放射变换方法的目标匹配定位算法，该方法应用到了机器人的抓取定位中，它利用了立体匹配信息，计算效率并不高。文献 [10] 提出了一种基于Hausdorff距离的模板匹配算法。文献 [11] 提出一种基于广义霍夫变换的几何模版匹配方法，此方法适用于搜索存在缩放或者旋转的目标，但是需建立较多累加器数组，并且耗时较长。文献 [12] 是基于几何基元的匹配算法，此类算法计算复杂度较高。而在国内关于晶圆自动划切的工业应用中，主要采用基于灰度的模板匹配方法，但其稳定性不高、计算量大、划切效率较低，和国外先进的商业软件包相比仍有很大差距。

针对上述存在的问题，本文研究一种基于几何特征的模板匹配算法，对传统的基于几何特征的模版匹配算法计算复杂等缺点进行优化，期望性能可以相对现有的基于灰度的模版匹配算法有较大提升，提升现有划切图像处理系统的稳定性与划切效率，能够达到或者超过商业软件的性能，并能应用到晶圆划片图像处理系统中，实现晶圆图像的快速高效的匹配检测，为晶圆划片成功率提供有效的保障，推动我国半导体制造业的发展。

2. 模板匹配简介

模版匹配主要有基于灰度相关和基于几何特征两种匹配方法。基于灰度的模板匹配方法主要是以模版图像和目标图像之间的灰度相关系数来判断模版图像和匹配目标之间的相似性。该方法原理简单、实现较容易，但是受光照影响较大、抗干扰性不强、鲁棒性不高，在光照条件非恒定的条件下或者目标图像存在部分遮挡情况下不够稳定。而基于几何特征的模版匹配算法提取出模板的边缘、角点等信息作为特征信息，然后对这些信息进行相似度量匹配。基于几何特征的模版匹配具备对于光照信息不是很敏感、可以有效地解决遮挡问题、抗干扰性强、可以处理微小畸变等优点。由于晶圆划片机图像识别系统容易受冷却水、划屑形成的假图像的影响，要求系统具有极强的去伪存真能力，因此基于边缘几何特征的匹配算法则适用于这种情况下的需求。

根据Brown原理 [13] [14] ，图像模版匹配算法有三个要素：特征空间，相似性度量，搜索策略。假设待匹配图像大小为，模版图像大小为，则在待匹配图像中需要进行次匹配。匹配过程是通过相关函数的计算来获得目标在搜索图中的位置坐标，搜索窗口在待匹配的图像上以每次一个像素点的距离进行顺序移动，每次移动中都需要计算模版图像和搜索窗口之间的相关性，然后与给定的相关性阈值比较，若相关性大于该阈值则匹配成功，否则就继续移动窗口向后查找。

3. 优化的模板匹配方法

鉴于已有的基于几何边缘的模版匹配算法的计算量大、计算复杂、不能满足系统实时性要求等缺点，本文提出一种改进的基于几何模版匹配的晶圆图像自动切割方法，本文提出的模板匹配算法主要在如下三个方面进行了改进：1) 优化相似性度量函数计算效率；2) 设计一种新的相似性度量计算的停止标准；3) 采用图像金字塔对匹配进行加速，从而对传统的几何模版匹配算法进行加速，保证划片机图像处理软件系统能够高速实时的实现工业自动化生产的要求。

3.1. 加速的相似性度量计算方法

对于晶圆模版图像的边缘上的点，，经过Canny边缘检测之后每个点对应的梯度方向向量表示为，。待匹配图像经过Canny边缘检测之后的边缘点处对应的梯度方向向量表示为。匹配过程中变换后的模版图像与待匹配图像某一位置的子图像计算相似性度量值。模板中边缘点梯度向量经变换后为，即在目标图像某位置子图像处，相似度量函数为式(1)所示 [15] ：

(1)

式(1)计算得到模版边缘点与子图像对应边缘点的梯度向量点积平均值。当梯度方向相反时点积取得负的最大值。梯度方向正交时点积为零。一对对应边缘点梯度方向相同时，点积取得最大值。根据式(1)计算得到的相似度量值的取值范围为整个实数域，不方便判断，很难确定一个阈值来筛选所需要的结果。因此进行归一化处理，即归一化互相关算法(NCC)：

(2)

由于式(2)对方向向量进行了归一化处理，所以相似性度量对光照变化具有不变性，此外噪声导致的方向向量是随机的平均后，其结果对(2)式没有影响，因此归一化的公式，提升了抗干扰性，但缺点是计算量大，时间复杂度高。当模版平移时，待匹配图像每个被模版覆盖的边缘点都要进行一次开方运算。文献 [16] 提出了一种NCC快速模版匹配算法，先对(2)式中的分子进行差分求和以降低每个位置处相似性度量值的计算量，再提出对待匹配图像进行区域分割并设定阈值，分别对分割后的小区域进行匹配和比较，减少了需要计算的点的数目；文献 [17] 提出了通过引入全1矩阵与源图像做卷积以此来降低NCC算法的计算量，该算法虽然降低了匹配时间，但是同时也降低了匹配精度。

针对以上研究现状，本文在计算相似性度量之前，首先对模版图像和待匹配图像的梯度进行归一化处理。优化过后的相似性度量公式为如公式(3)所示。其中表示模版边缘梯度向量的单位向量，表示待匹配图像边缘梯度向量的单位向量。

(3)

由(3)式可以看出，在相似度量求和时每个特征点只需要做两次乘法和一次加法。优化前当模板平移时，每次被模板覆盖的所有边缘点都要作一次开方运算。模板图像边缘点的梯度向量单位化时可以离线处理，而目标图像边缘点向量单位化时每个点只需要进行一次开方运算。降低了NCC算法的计算次数，在保证精度的前提下有效的减少了计算时间。

3.2. 相似性度量的停止标准

搜索待匹配图像的过程中，在非可能目标位置相似度量值可以不必完全计算，即通过设定一定阈值，采用一定的终止条件，提前结束计算，从而快速地定位到真正的目标位置，加快整个算法的处理速度。

由归一化相似度量公式(2)可知，剩余n-j项的和小于，所以当部分和满足(为设定的阈值)，即可终止相似度量的计算。文献 [15] 提出了一个改进的终止条件，第1部分采用宽松的阈值判断，剩下的部分采用严格阈值判断，通过预设设定一个系数g来实现。式中，当时，所有的点都使用严格的终止条件；当时，所有的点都使用宽松的终止条件来判断。一般情况下，为了保证不产生误判，参数g通常设置为0.9。在计算相似度量值时，每求一次和都要与阈值进行一次判断，判断的过程使得处理器没有充分发挥流水线功能，降低了处理器的效率，并且当存在部分遮挡时也检测不到。

在整个匹配过程中，绝大部分位置的相似度量值没有必要完全计算，一般只有目标位置计算相似度量值才是真正有用的，为了在搜索待匹配图像时能加快计算相似度量值，尽快终止在非目标位置处相似度量的计算，本文提出了一种停止标准的策略，即选择一部分散乱的边缘点作为试探点，先判断该点是否为可能的目标位置点，再决定是否继续计算相似性度量值。

本方法的具体策略为：

1) 提取出模板图像的边缘信息后，将边缘点分为2部分。设模板边缘点数为n，n1、n2分别为两部分的边缘点个数，且n1 + n2 = n，第1部分n1个零散点作为试探点，即先选择离模板左上角距离最远的边缘点作为第1点，再在到第1点的距离最远的边缘点作为第2个点；在剩余的边缘点中，选择到前面两点距离和最大的点作为第3点，依次而得到n1个点作为第1部分的点，剩余的边缘点作为第2部分，

2) 计算第1部分n1个点的部分相似度量值，计算完后与设定的阈值判断若，则停止计算本次相似度量值，

3) 若，则在的基础上，继续计算第2部分n2个点的部分相似度量值，从而得到完整的相似度量值，停止计算本次相似度量值。

如图1所示为本文优化的停止标准算法流程图。

通过对停止标准进行优化提高了相似度量值的计算效率，降低了NCC算法的计算次数，从而减少了相似性度量的计算时间，因此提高了模版匹配的匹配效率。

3.3. 图像金字塔加速策略

仅仅通过相似性度量的停止标准来进行模版匹配的加速效果有限，想要达到晶圆自动划切的工业应用中的实时性要求，必须采用更加快速的搜索策略来提高计算效率。本文采用构建图像金字塔的方法有效的降低了算法的复杂度。

金字塔的第一层为原始的高分辨率图像，顶部为低分辨率图像。当金字塔向上层移动时，图像的尺寸和分辨率降低、像素点减少。如上图2所示，原始图像为J级，图像像素点数为，图像每向上移动一层目标图像和末班图像的像素点个数各减少到原来的1/4，大大减少了计算量，速度提高了16倍，因此提高了图像处理效率。假设金字塔共有级，且，则级金字塔中像素点总数为

(4)

图1. 停止标准优化算法流程图

由式(4)可见，越往上侧像素点越少。本文图像金字塔为4层，首先通过穷举使模板遍历一次金字塔最顶层的图像，即分辨率最低的那一层。在计算相似度量值时，使用上文提到的优化的计算方法和停止标准加快判断效率。然后，将在最顶层找到的位置映射到下一层，在该位置的一定邻域内进行更精细的匹配，直到图像金字塔的最底层，也即得到最高分辨率匹配精度。

4. 检测结果与分析

如下图3、图4、图5中(c)匹配结果所示，成功在目标图像中匹配到模版，并用绿色曲线标示出，基于几何边缘的模版匹配能够对不同类型的晶圆划切图像得到的不同模版匹配结果。可以看出本方法对不同类型的图像均得到较好的匹配结果。

而相对于传统的基于几何边缘的模版匹配算法，本文在计算效率上进行优化，大大提高了基于几何模版匹配算法的计算效率，使其能满足工业生产实时性的要求，克服了基于几何模版匹配算法耗时较大、计算复杂等问题。表1是对不同类型的待匹配图像，本文使用的匹配算法与传统的基于几何边缘的模版匹配算法和传统基于灰度模版匹配算法耗时进行的比较。从表1可以看出相对传统几何边缘模版匹配算法和传统基于灰度模版匹配算法，本文匹配时间大大降低，能够满足划片机图像处理软件系统要求的实时性、稳定性等需求。

图2. 图像金字塔

图3. 模版匹配结果1

图4. 模版匹配结果2

图5. 模版匹配结果3

表1. 本文算法和传统的基于边缘和基于灰度匹配算法耗时比较

5. 结束语

本文提出了一种优化的基于几何边缘模板匹配的晶圆划切图像检测方法，结合图像金字塔和相似度阈值计算的优化来提高匹配速度，解决了基于灰度的模版匹配和基于传统几何边缘算法计算效率低等问题。实验结果证明该方法高效快速，能适应实际工业自动化实时检测的需要。

基金项目

国家自然科学基金资助项目(U1301251, 61271435, 61671426, 61471150)，北京市自然科学基金重点项目(4141003)。

文章引用

高晨舒,翟 锐,薛 健,吕 科. 基于改进模板匹配的晶圆划切算法
Algorithm for Wafer Slicing Based on Improved Template Matching[J]. 图像与信号处理, 2017, 06(03): 139-146. http://dx.doi.org/10.12677/JISP.2017.63017

参考文献 (References)