基于廣度優先搜索的晶粒掃描方法

高建利，侯為萍，劉玉倩

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

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

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

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

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

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

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

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

由于逐行掃描存在以上缺點，因此改進晶粒掃描方法是提升設備性能的有效方式。將晶?？醋鲝V度優先搜索中的節點，根據廣度優先搜索算法進行晶粒掃描，可以提升設備性能。

1 硬件環境

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

圖1 晶片臺機構

藍膜固定在晶片環上，晶粒在藍膜上的分布如圖2 所示。晶粒是刻有電路圖形的半導體顆粒，在藍膜上按行列排列，可能會出現晶?？杖焙途ЯＨ毕莸那闆r。晶粒的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 條件

將晶?？醋鰣D中的節點，完成廣度優先搜索，需要找到每個晶粒的相鄰晶粒，視場內只有一顆晶粒時不能找到相鄰晶粒，因此需要調節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.