基于广度优先搜索的晶粒扫描方法

高建利，侯为萍，刘玉倩

(中国电子科技集团公司第四十五研究所，北京100176)

晶粒扫描技术是电子工艺专用设备的常用功能，主要应用于LED 晶粒、半导体晶粒分拣、封装和检测设备中。晶粒以行列方式粘结在晶片环的蓝膜上，设备按一定的顺序对晶粒进行图像识别和拾取，这个顺序就是晶粒扫描的方法。合理的晶粒扫描方法可以提高设备的效率。

晶片环上的晶粒按行列排列，因此逐行扫描是最常用的晶粒扫描方法，但是逐行扫描也有一定缺陷：

（1）换行时需要空走几个晶粒位置才能判定一行到头走下一行；

（2）不管是否有晶粒，对每个晶粒位置都要走到并进行晶粒识别；

（3）扫描结束时需要连续几行没有晶粒才能判定扫描结束；

（4）除了扫描起始位置之外，还需要设置晶粒间距、扫描方向、连续无晶粒数、连续无晶粒行数等扫描参数；

（5）需要从一行中拾取晶粒，不能最大限度保证质量相似的晶粒一起拾取。

由于逐行扫描存在以上缺点，因此改进晶粒扫描方法是提升设备性能的有效方式。将晶粒看作广度优先搜索中的节点，根据广度优先搜索算法进行晶粒扫描，可以提升设备性能。

1 硬件环境

晶片台是晶粒的承载机构，主要由图像识别、运动控制、晶片台执行等组成，如图1 所示。图像识别部分包括CCD 相机、图像采集卡、镜头、光源等部件，它利用机器视觉技术，对晶粒图像进行采集和分析识别，完成晶粒的定位和缺陷检测等功能。运动控制部分包括运动控制卡、X向电机、Y 向电机与相应的电机驱动器，通过工控机发出的数字脉冲信号控制电机的运动。晶片台执行部分是电机通过滚珠丝杠或其它方式带动X-Y 平台，包括X、Y 两个轴，在平面内做运动，形成平面坐标系，这样每颗晶粒就有一个X、Y 坐标位置。

图1 晶片台机构

蓝膜固定在晶片环上，晶粒在蓝膜上的分布如图2 所示。晶粒是刻有电路图形的半导体颗粒，在蓝膜上按行列排列，可能会出现晶粒空缺和晶粒缺陷的情况。晶粒的X 向间距和Y 向间距都在小范围内波动，因此设备需要通过图像识别的方法准确定位晶粒位置以供取片使用。

2 逐行扫描方法

图2 晶粒分布示意图

图3 晶粒逐行扫描示意图

晶粒逐行扫描方法如图3 所示，晶片台X 向向右（或向左，Y 向为向上或向下）运动到下一个晶粒位置处，发送图像识别命令，根据识别结果把晶粒对准到图像中心，等待拾片机构拾取晶粒，拾取完毕后，晶片台继续运动到下一个晶粒位置处。当本行达到连续无晶粒数后，晶片台跳转到第一次没有晶粒位置的正下方(或正上方)晶粒处，并保持原来的运动方向继续扫描，直到再次达到连续无晶粒数后，晶片台运动到上次晶粒跳转时晶粒的左侧(右侧)晶粒处，并改变扫描方向为向左(或向右)，继续识别对准晶粒的过程。直到达到连续几个晶粒行数后，晶粒扫描结束。

从扫描的过程可以看出，逐行扫描需要晶粒间距、扫描方向、连续无晶粒数、连续无晶粒行数等扫描参数，在每行的两端需要空走几个晶粒位置以判断该行扫描完成，扫描结束时需要空走几行以判断扫描结束。

3 广度优先搜索算法

图4 是一个用线或边连接在一起的节点的集合，从一个给定的节点开始，访问能够到达的所有节点就是图的搜索，广度优先搜索就是一种常用的图搜索方法。如图4 表示了广度优先搜索方法。

广度优先算法的核心思想是：从初始节点开始，生成第一层节点，检查目标节点是否在这些后继节点中，若没有，再用产生式规则将所有第一层的节点逐一扩展，得到第二层节点，并逐一检查第二层节点中是否包含目标节点。若没有，再用算符逐一扩展第二层的所有节点……，如此依次扩展，检查下去，直到发现目标节点为止，即：

图4 广度优先搜索示意图

1) 从图中的某一节点V1开始，先访问V1；

2) 访问所有与V1相邻的节点V2，V3，V4；

3) 依次访问与V2，V3，V4相邻的所有未曾访问过的节点；

4) 循此以往，直至所有的顶点都被访问过为止。

5) 这种搜索的次序体现沿层次向横向扩长的趋势，所以称之为广度优先搜索。

4 广度优先搜索在晶粒扫描中的应用

4.1 条件

将晶粒看做图中的节点，完成广度优先搜索，需要找到每个晶粒的相邻晶粒，视场内只有一颗晶粒时不能找到相邻晶粒，因此需要调节CCD 的识别范围内有9 颗晶粒，这样中心的晶粒与周围8 颗晶粒相邻，可以进行广度优先搜索，如图5 所示，视场内有9 颗晶粒，因此在扫描条件中只需要指定扫描起始点和图像模板，不需要设置晶粒间距、扫描方向、连续无晶粒数、连续无晶粒行数等扫描参数，设置扫描参数简单，有利于设备操作。

4.2 实现过程

图5 晶粒识别示意图

实际扫描过程从使用者指定的扫描起始点开始扫描晶粒，通过图像识别将与起始位置邻接的晶粒得到第二层晶粒位置，记入队列，再依次运动到第二层晶粒经图像识别得到第三层晶粒并记入队列……，如此依次扩展，扫描下去，直到拾取完所有连通区域的晶粒为止。如图6 所示，即：

1)运动到晶粒1 进行晶粒的图像识别，将识别到的晶粒位置像素值转换为电机脉冲数，然后对晶粒位置进行编号，中心位置晶粒编号为1，左上角为编号2，以此类推，如图6 所示，编到9为止；

图6 晶粒广度优先搜索示意图

2) 将编号的晶粒位置依次与队列中的晶粒位置进行对比，晶粒位置相差过小的认为是重合晶粒，已经进入队列，晶粒位置没有重合的记入队尾；

3)队列头出列，晶片台运动到对列头位置识别并拾取晶粒；

4)重复步骤2、3，进行图像识别将邻接的晶粒记入队尾；

5)循此以往，直至队列为空，连通区域的所有晶粒被拾取为止。

这样晶粒扫描的次序体现沿层次向圆周扩展的趋势，即将广度优先搜索算法应用到了晶粒扫描过程中。根据以上扫描方法设计的软件流程如图7 所示，晶片台运动到扫描起始点，识别晶粒，根据晶粒的识别情况对识别到的晶粒进行编号，然后将晶粒位置与队列中保存的晶粒位置进行比较，没有重合的晶粒位置加入队尾，如果队列为空则扫描结束，否则队列头的晶粒位置出队列，晶片台运动到出列的晶粒位置，由拾片机构取走晶粒，然后继续识别晶粒。如此循环往复直到队列为空时扫描完成。这种晶粒扫描方法避免了空走晶粒位置，对提高设备的效率有重要意义。

图7 晶粒广度优先搜索流程图

4.3 限制

使用广度优先搜索扫描晶粒呈现了从扫描起始点沿层次向圆周扩展的扫描趋势，只要是邻接的晶粒就能进行扫描。对于不与扫描晶粒块邻接的非连通晶粒块，需要重新设置扫描起始点进行扫描。由于是沿层次扫描晶粒，因此这种方法也不能保证质量相似的晶粒一起拾取。需要CCD 相机的视场内有9 颗晶粒并且同时识别，也是这种扫描方法的一个限制。

5 结束语

使用广度优先搜索方法扫描晶粒需要设置的扫描参数简单，操作简便。由于每次移动到晶粒位置前都已经识别完成，广度优先搜索的方法能够保证每次移动都能到达晶粒位置，不会出现走空晶粒位置的情况，因此广度优先搜索方法能够提高设备效率。但是这种方法也存在一些缺点，比如只能扫描连通的晶粒，不能保证质量相似的晶粒一起拾取等，在设备中可以根据情况选择合适的晶粒扫描方式。

[1] 王天曦，王豫明.贴片工艺与设备[M].北京：电子工艺出版社，2008.

[2] 殷人昆.数据结构：用面向对象方法与C++描述[M].北京：清华大学出版社，2002.

[3] 徐品烈，任绍彬，郝靖. 装片机晶片台运动控制系统的分析[J]. 电子工业专用设备，2010，39(5)：12-16.

[4] 钟江生，李秦川，夏毓鹏，等. 贴片机视觉系统构成原理及其定位[J]. 电子工业专用设备，2005，34(12)：26-29.

[5] 欧阳圣. 几种经典搜索算法研究与应用[J]. 计算机系统应用，2011(5)：243-247.