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

高建利，侯為萍，劉玉倩

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

晶粒掃描技術是電子工藝專用設備的常用功能，主要應用于LED 晶粒、半導體晶粒分揀、封裝和檢測設備中。晶粒以行列方式粘結在晶片環(huán)的藍膜上，設備按一定的順序對晶粒進行圖像識別和拾取，這個順序就是晶粒掃描的方法。合理的晶粒掃描方法可以提高設備的效率。

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

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

（2）不管是否有晶粒，對每個晶粒位置都要走到并進行晶粒識別；

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

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

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

由于逐行掃描存在以上缺點，因此改進晶粒掃描方法是提升設備性能的有效方式。將晶粒看作廣度優(yōu)先搜索中的節(jié)點，根據廣度優(yōu)先搜索算法進行晶粒掃描，可以提升設備性能。

1 硬件環(huán)境

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

圖1 晶片臺機構

藍膜固定在晶片環(huán)上，晶粒在藍膜上的分布如圖2 所示。晶粒是刻有電路圖形的半導體顆粒，在藍膜上按行列排列，可能會出現晶粒空缺和晶粒缺陷的情況。晶粒的X 向間距和Y 向間距都在小范圍內波動，因此設備需要通過圖像識別的方法準確定位晶粒位置以供取片使用。

2 逐行掃描方法

圖2 晶粒分布示意圖

圖3 晶粒逐行掃描示意圖

晶粒逐行掃描方法如圖3 所示，晶片臺X 向向右（或向左，Y 向為向上或向下）運動到下一個晶粒位置處，發(fā)送圖像識別命令，根據識別結果把晶粒對準到圖像中心，等待拾片機構拾取晶粒，拾取完畢后，晶片臺繼續(xù)運動到下一個晶粒位置處。當本行達到連續(xù)無晶粒數后，晶片臺跳轉到第一次沒有晶粒位置的正下方(或正上方)晶粒處，并保持原來的運動方向繼續(xù)掃描，直到再次達到連續(xù)無晶粒數后，晶片臺運動到上次晶粒跳轉時晶粒的左側(右側)晶粒處，并改變掃描方向為向左(或向右)，繼續(xù)識別對準晶粒的過程。直到達到連續(xù)幾個晶粒行數后，晶粒掃描結束。

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

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

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

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

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

1) 從圖中的某一節(jié)點V1開始，先訪問V1；

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

3) 依次訪問與V2，V3，V4相鄰的所有未曾訪問過的節(jié)點；

4) 循此以往，直至所有的頂點都被訪問過為止。

5) 這種搜索的次序體現沿層次向橫向擴長的趨勢，所以稱之為廣度優(yōu)先搜索。

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

4.1 條件

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

4.2 實現過程

圖5 晶粒識別示意圖

實際掃描過程從使用者指定的掃描起始點開始掃描晶粒，通過圖像識別將與起始位置鄰接的晶粒得到第二層晶粒位置，記入隊列，再依次運動到第二層晶粒經圖像識別得到第三層晶粒并記入隊列……，如此依次擴展，掃描下去，直到拾取完所有連通區(qū)域的晶粒為止。如圖6 所示，即：

1)運動到晶粒1 進行晶粒的圖像識別，將識別到的晶粒位置像素值轉換為電機脈沖數，然后對晶粒位置進行編號，中心位置晶粒編號為1，左上角為編號2，以此類推，如圖6 所示，編到9為止；

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

2) 將編號的晶粒位置依次與隊列中的晶粒位置進行對比，晶粒位置相差過小的認為是重合晶粒，已經進入隊列，晶粒位置沒有重合的記入隊尾；

3)隊列頭出列，晶片臺運動到對列頭位置識別并拾取晶粒；

4)重復步驟2、3，進行圖像識別將鄰接的晶粒記入隊尾；

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

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

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

4.3 限制

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

5 結束語

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

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

[2] 殷人昆.數據結構：用面向對象方法與C++描述[M].北京：清華大學出版社，2002.

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

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

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