基于廣度優(yōu)先搜索的晶粒掃描方法

高建利，侯為萍，劉玉倩

(中國(guó)電子科技集團(tuán)公司第四十五研究所，北京100176)

晶粒掃描技術(shù)是電子工藝專(zhuān)用設(shè)備的常用功能，主要應(yīng)用于LED 晶粒、半導(dǎo)體晶粒分揀、封裝和檢測(cè)設(shè)備中。晶粒以行列方式粘結(jié)在晶片環(huán)的藍(lán)膜上，設(shè)備按一定的順序?qū)Я＿M(jìn)行圖像識(shí)別和拾取，這個(gè)順序就是晶粒掃描的方法。合理的晶粒掃描方法可以提高設(shè)備的效率。

晶片環(huán)上的晶粒按行列排列，因此逐行掃描是最常用的晶粒掃描方法，但是逐行掃描也有一定缺陷：

（1）換行時(shí)需要空走幾個(gè)晶粒位置才能判定一行到頭走下一行；

（2）不管是否有晶粒，對(duì)每個(gè)晶粒位置都要走到并進(jìn)行晶粒識(shí)別；

（3）掃描結(jié)束時(shí)需要連續(xù)幾行沒(méi)有晶粒才能判定掃描結(jié)束；

（4）除了掃描起始位置之外，還需要設(shè)置晶粒間距、掃描方向、連續(xù)無(wú)晶粒數(shù)、連續(xù)無(wú)晶粒行數(shù)等掃描參數(shù)；

（5）需要從一行中拾取晶粒，不能最大限度保證質(zhì)量相似的晶粒一起拾取。

由于逐行掃描存在以上缺點(diǎn)，因此改進(jìn)晶粒掃描方法是提升設(shè)備性能的有效方式。將晶?？醋鲝V度優(yōu)先搜索中的節(jié)點(diǎn)，根據(jù)廣度優(yōu)先搜索算法進(jìn)行晶粒掃描，可以提升設(shè)備性能。

1 硬件環(huán)境

晶片臺(tái)是晶粒的承載機(jī)構(gòu)，主要由圖像識(shí)別、運(yùn)動(dòng)控制、晶片臺(tái)執(zhí)行等組成，如圖1 所示。圖像識(shí)別部分包括CCD 相機(jī)、圖像采集卡、鏡頭、光源等部件，它利用機(jī)器視覺(jué)技術(shù)，對(duì)晶粒圖像進(jìn)行采集和分析識(shí)別，完成晶粒的定位和缺陷檢測(cè)等功能。運(yùn)動(dòng)控制部分包括運(yùn)動(dòng)控制卡、X向電機(jī)、Y 向電機(jī)與相應(yīng)的電機(jī)驅(qū)動(dòng)器，通過(guò)工控機(jī)發(fā)出的數(shù)字脈沖信號(hào)控制電機(jī)的運(yùn)動(dòng)。晶片臺(tái)執(zhí)行部分是電機(jī)通過(guò)滾珠絲杠或其它方式帶動(dòng)X-Y 平臺(tái)，包括X、Y 兩個(gè)軸，在平面內(nèi)做運(yùn)動(dòng)，形成平面坐標(biāo)系，這樣每顆晶粒就有一個(gè)X、Y 坐標(biāo)位置。

圖1 晶片臺(tái)機(jī)構(gòu)

藍(lán)膜固定在晶片環(huán)上，晶粒在藍(lán)膜上的分布如圖2 所示。晶粒是刻有電路圖形的半導(dǎo)體顆粒，在藍(lán)膜上按行列排列，可能會(huì)出現(xiàn)晶?？杖焙途ЯＨ毕莸那闆r。晶粒的X 向間距和Y 向間距都在小范圍內(nèi)波動(dòng)，因此設(shè)備需要通過(guò)圖像識(shí)別的方法準(zhǔn)確定位晶粒位置以供取片使用。

2 逐行掃描方法

圖2 晶粒分布示意圖

圖3 晶粒逐行掃描示意圖

晶粒逐行掃描方法如圖3 所示，晶片臺(tái)X 向向右（或向左，Y 向?yàn)橄蛏匣蛳蛳拢┻\(yùn)動(dòng)到下一個(gè)晶粒位置處，發(fā)送圖像識(shí)別命令，根據(jù)識(shí)別結(jié)果把晶粒對(duì)準(zhǔn)到圖像中心，等待拾片機(jī)構(gòu)拾取晶粒，拾取完畢后，晶片臺(tái)繼續(xù)運(yùn)動(dòng)到下一個(gè)晶粒位置處。當(dāng)本行達(dá)到連續(xù)無(wú)晶粒數(shù)后，晶片臺(tái)跳轉(zhuǎn)到第一次沒(méi)有晶粒位置的正下方(或正上方)晶粒處，并保持原來(lái)的運(yùn)動(dòng)方向繼續(xù)掃描，直到再次達(dá)到連續(xù)無(wú)晶粒數(shù)后，晶片臺(tái)運(yùn)動(dòng)到上次晶粒跳轉(zhuǎn)時(shí)晶粒的左側(cè)(右側(cè))晶粒處，并改變掃描方向?yàn)橄蜃?或向右)，繼續(xù)識(shí)別對(duì)準(zhǔn)晶粒的過(guò)程。直到達(dá)到連續(xù)幾個(gè)晶粒行數(shù)后，晶粒掃描結(jié)束。

從掃描的過(guò)程可以看出，逐行掃描需要晶粒間距、掃描方向、連續(xù)無(wú)晶粒數(shù)、連續(xù)無(wú)晶粒行數(shù)等掃描參數(shù)，在每行的兩端需要空走幾個(gè)晶粒位置以判斷該行掃描完成，掃描結(jié)束時(shí)需要空走幾行以判斷掃描結(jié)束。

3 廣度優(yōu)先搜索算法

圖4 是一個(gè)用線或邊連接在一起的節(jié)點(diǎn)的集合，從一個(gè)給定的節(jié)點(diǎn)開(kāi)始，訪問(wèn)能夠到達(dá)的所有節(jié)點(diǎn)就是圖的搜索，廣度優(yōu)先搜索就是一種常用的圖搜索方法。如圖4 表示了廣度優(yōu)先搜索方法。

廣度優(yōu)先算法的核心思想是：從初始節(jié)點(diǎn)開(kāi)始，生成第一層節(jié)點(diǎn)，檢查目標(biāo)節(jié)點(diǎn)是否在這些后繼節(jié)點(diǎn)中，若沒(méi)有，再用產(chǎn)生式規(guī)則將所有第一層的節(jié)點(diǎn)逐一擴(kuò)展，得到第二層節(jié)點(diǎn)，并逐一檢查第二層節(jié)點(diǎn)中是否包含目標(biāo)節(jié)點(diǎn)。若沒(méi)有，再用算符逐一擴(kuò)展第二層的所有節(jié)點(diǎn)……，如此依次擴(kuò)展，檢查下去，直到發(fā)現(xiàn)目標(biāo)節(jié)點(diǎn)為止，即：

圖4 廣度優(yōu)先搜索示意圖

1) 從圖中的某一節(jié)點(diǎn)V1開(kāi)始，先訪問(wèn)V1；

2) 訪問(wèn)所有與V1相鄰的節(jié)點(diǎn)V2，V3，V4；

3) 依次訪問(wèn)與V2，V3，V4相鄰的所有未曾訪問(wèn)過(guò)的節(jié)點(diǎn)；

4) 循此以往，直至所有的頂點(diǎn)都被訪問(wèn)過(guò)為止。

5) 這種搜索的次序體現(xiàn)沿層次向橫向擴(kuò)長(zhǎng)的趨勢(shì)，所以稱(chēng)之為廣度優(yōu)先搜索。

4 廣度優(yōu)先搜索在晶粒掃描中的應(yīng)用

4.1 條件

將晶粒看做圖中的節(jié)點(diǎn)，完成廣度優(yōu)先搜索，需要找到每個(gè)晶粒的相鄰晶粒，視場(chǎng)內(nèi)只有一顆晶粒時(shí)不能找到相鄰晶粒，因此需要調(diào)節(jié)CCD 的識(shí)別范圍內(nèi)有9 顆晶粒，這樣中心的晶粒與周?chē)? 顆晶粒相鄰，可以進(jìn)行廣度優(yōu)先搜索，如圖5 所示，視場(chǎng)內(nèi)有9 顆晶粒，因此在掃描條件中只需要指定掃描起始點(diǎn)和圖像模板，不需要設(shè)置晶粒間距、掃描方向、連續(xù)無(wú)晶粒數(shù)、連續(xù)無(wú)晶粒行數(shù)等掃描參數(shù)，設(shè)置掃描參數(shù)簡(jiǎn)單，有利于設(shè)備操作。

4.2 實(shí)現(xiàn)過(guò)程

圖5 晶粒識(shí)別示意圖

實(shí)際掃描過(guò)程從使用者指定的掃描起始點(diǎn)開(kāi)始掃描晶粒，通過(guò)圖像識(shí)別將與起始位置鄰接的晶粒得到第二層晶粒位置，記入隊(duì)列，再依次運(yùn)動(dòng)到第二層晶粒經(jīng)圖像識(shí)別得到第三層晶粒并記入隊(duì)列……，如此依次擴(kuò)展，掃描下去，直到拾取完所有連通區(qū)域的晶粒為止。如圖6 所示，即：

1)運(yùn)動(dòng)到晶粒1 進(jìn)行晶粒的圖像識(shí)別，將識(shí)別到的晶粒位置像素值轉(zhuǎn)換為電機(jī)脈沖數(shù)，然后對(duì)晶粒位置進(jìn)行編號(hào)，中心位置晶粒編號(hào)為1，左上角為編號(hào)2，以此類(lèi)推，如圖6 所示，編到9為止；

圖6 晶粒廣度優(yōu)先搜索示意圖

2) 將編號(hào)的晶粒位置依次與隊(duì)列中的晶粒位置進(jìn)行對(duì)比，晶粒位置相差過(guò)小的認(rèn)為是重合晶粒，已經(jīng)進(jìn)入隊(duì)列，晶粒位置沒(méi)有重合的記入隊(duì)尾；

3)隊(duì)列頭出列，晶片臺(tái)運(yùn)動(dòng)到對(duì)列頭位置識(shí)別并拾取晶粒；

4)重復(fù)步驟2、3，進(jìn)行圖像識(shí)別將鄰接的晶粒記入隊(duì)尾；

5)循此以往，直至隊(duì)列為空，連通區(qū)域的所有晶粒被拾取為止。

這樣晶粒掃描的次序體現(xiàn)沿層次向圓周擴(kuò)展的趨勢(shì)，即將廣度優(yōu)先搜索算法應(yīng)用到了晶粒掃描過(guò)程中。根據(jù)以上掃描方法設(shè)計(jì)的軟件流程如圖7 所示，晶片臺(tái)運(yùn)動(dòng)到掃描起始點(diǎn)，識(shí)別晶粒，根據(jù)晶粒的識(shí)別情況對(duì)識(shí)別到的晶粒進(jìn)行編號(hào)，然后將晶粒位置與隊(duì)列中保存的晶粒位置進(jìn)行比較，沒(méi)有重合的晶粒位置加入隊(duì)尾，如果隊(duì)列為空則掃描結(jié)束，否則隊(duì)列頭的晶粒位置出隊(duì)列，晶片臺(tái)運(yùn)動(dòng)到出列的晶粒位置，由拾片機(jī)構(gòu)取走晶粒，然后繼續(xù)識(shí)別晶粒。如此循環(huán)往復(fù)直到隊(duì)列為空時(shí)掃描完成。這種晶粒掃描方法避免了空走晶粒位置，對(duì)提高設(shè)備的效率有重要意義。

圖7 晶粒廣度優(yōu)先搜索流程圖

4.3 限制

使用廣度優(yōu)先搜索掃描晶粒呈現(xiàn)了從掃描起始點(diǎn)沿層次向圓周擴(kuò)展的掃描趨勢(shì)，只要是鄰接的晶粒就能進(jìn)行掃描。對(duì)于不與掃描晶粒塊鄰接的非連通晶粒塊，需要重新設(shè)置掃描起始點(diǎn)進(jìn)行掃描。由于是沿層次掃描晶粒，因此這種方法也不能保證質(zhì)量相似的晶粒一起拾取。需要CCD 相機(jī)的視場(chǎng)內(nèi)有9 顆晶粒并且同時(shí)識(shí)別，也是這種掃描方法的一個(gè)限制。

5 結(jié)束語(yǔ)

使用廣度優(yōu)先搜索方法掃描晶粒需要設(shè)置的掃描參數(shù)簡(jiǎn)單，操作簡(jiǎn)便。由于每次移動(dòng)到晶粒位置前都已經(jīng)識(shí)別完成，廣度優(yōu)先搜索的方法能夠保證每次移動(dòng)都能到達(dá)晶粒位置，不會(huì)出現(xiàn)走空晶粒位置的情況，因此廣度優(yōu)先搜索方法能夠提高設(shè)備效率。但是這種方法也存在一些缺點(diǎn)，比如只能掃描連通的晶粒，不能保證質(zhì)量相似的晶粒一起拾取等，在設(shè)備中可以根據(jù)情況選擇合適的晶粒掃描方式。

[1] 王天曦，王豫明.貼片工藝與設(shè)備[M].北京：電子工藝出版社，2008.

[2] 殷人昆.數(shù)據(jù)結(jié)構(gòu)：用面向?qū)ο蠓椒ㄅcC++描述[M].北京：清華大學(xué)出版社，2002.

[3] 徐品烈，任紹彬，郝靖. 裝片機(jī)晶片臺(tái)運(yùn)動(dòng)控制系統(tǒng)的分析[J]. 電子工業(yè)專(zhuān)用設(shè)備，2010，39(5)：12-16.

[4] 鐘江生，李秦川，夏毓鵬，等. 貼片機(jī)視覺(jué)系統(tǒng)構(gòu)成原理及其定位[J]. 電子工業(yè)專(zhuān)用設(shè)備，2005，34(12)：26-29.

[5] 歐陽(yáng)圣. 幾種經(jīng)典搜索算法研究與應(yīng)用[J]. 計(jì)算機(jī)系統(tǒng)應(yīng)用，2011(5)：243-247.