基于改進凸包檢測算法的多幅芯片圖像校正方法

朱俊杰，巢淵，馬成霞

（江蘇理工學院機械工程學院，江蘇常州 213001）

隨著電子市場的快速發展，半導體芯片的應用越來越廣泛，需求也在不斷增加，傳統的人工抽檢方法已難以滿足表面貼裝芯片高速高精度檢測的需求[1]。機器視覺技術以其高效率、高精度、高可靠性、非接觸性和客觀性強等優點，在芯片封裝模塊檢測方面得到了廣泛研究和應用[2]。由于圖像采集系統捕獲的目標并非規則地出現，因此，在進行芯片封裝缺陷視覺檢測前，需要對芯片圖像進行旋轉校正，以提高后續檢測的正確率以及基于缺陷檢測的芯片分選效率[3]。

圖像傾斜校正算法研究的重點在于傾斜角度檢測。楊立剛等人[4]通過Hough 變換精確定位車牌位置，再利用Radon 變換獲取車牌的傾斜角度，但此方法中Hough 變換和Radon 變換計算量大，校正效率較低。汪敏倩等人[5]通過車牌圖像投影方差的規律性提取局部特征來獲得車牌水平傾斜角度或垂直錯切角度，但對于局部規律性不明顯的圖像，此方法難以獲取精準的傾斜角度。胡人偉等人[6]運用傅里葉變換將商標圖像從空域轉換到頻域，再通過Hough 變換求出頻譜圖像中的傾斜角度，以實現圖像的傾斜校正；此方法雖然只做了一次空域到頻域的變換，但耗時較長，實用性不強。鄧翔宇等人[7]通過大尺度梯度下降法實現簡譜的粗校正，再利用小尺度梯度下降法進行精細調整；但是當傾斜角度超過±8°時，該方法校正精準性下降明顯。李青等人[8]結合Canny 邊緣檢測和Hough 變換獲取交通標識牌矩形邊緣的4 個角點坐標，再應用透視變換對其進行校正；但該方法中Hough變換耗時長，且較為依賴Canny 邊緣檢測獲取的圖像邊緣，不適用于背景復雜的圖像。

傾斜角度檢測方法耗時長、難以獲取精確角度，而凸包檢測則可以通過叉乘、角度和長度等方法精準篩選凸包頂點，獲取包含位置和角度信息的特征點[9]。黃珂等人[10]通過Harris角點檢測算法獲取QR 碼圖像的角點并進行凸包檢測，以獲取QR 碼位置信息；但角點檢測過于依賴拍攝的圖像，難以獲取復雜背景圖像的有效角點，且參與凸包篩選的角點數量較多，耗時長。郭亞盛等人[11]運用Andrew 算法獲取圓柱類零件圖像輪廓凸包，再獲取凸包的最小外接矩形以實現對圓柱類零件圖像的尺寸測量；但凸包篩選邊緣點較多，計算時間較長，且存在特征點集簇擁情況。王亞杰等人[12]提取棋盤輪廓邊緣點后，運用凸包檢測算法獲取棋盤4個頂點坐標，以實現棋盤校正；但該方法需要篩選的棋盤輪廓邊緣點較多，計算時間較長。朱俊卿[13]采用基于凸包檢測的矩形頂點檢測方法定位矩形的4個頂點，采用透視變換對畸變圖像進行校正；但該方法需要進行凸包篩選的點集較多，耗時長。

針對凸包檢測耗時長、特征點多的問題，彭志光等人[14]改進凸包算法，對葉片型截面點云數據進行排序和精準分割，通過矩形區域腐蝕法確定凸包邊界區域，刪除冗余點，以減少參與排序和生成凸包的點集數量，提高構造凸包效率。張勇等人[15]根據圖像分辨率確定掃描行數，保留掃描行第一個和最后一個像素點形成點集，以提高構造凸包效率。蔡文婷等人[16]對二維條碼的邊緣點集進行預處理，濾除二維條碼內部的點集，再對剩余點集構造凸包，從而實現圖像的高效定位。

在圖像傾斜校正算法研究中，旋轉變換矩陣的選擇也是校正的關鍵。旋轉變換矩陣通常有三種：一是二維歐式變換矩陣[17]，該矩陣包括平移、旋轉和縮放三個基本變換矩陣，可用于對平面圖形進行傾斜校正；二是仿射變換矩陣[18]，該矩陣是在二維歐氏變換矩陣的基礎上增加了一個錯切變換矩陣，從而能夠更加精確地對圖像進行傾斜校正；三是透視變換矩陣[19]，該矩陣在仿射變換矩陣的基礎上增加了一個透視變換矩陣，能夠對三維場景進行投影并進行傾斜校正。相較于二維歐式變換矩陣，仿射變換矩陣可更精確地校正傾斜圖像。相較于透視變換矩陣，仿射變換可以保持直線的平行性，從而很好地保持圖像的形狀，而透視變換會改變圖像的形狀和大小，容易引起失真。

基于上述分析，本文通過標記多幅芯片圖像中每個芯片的位置，改進Andrew 算法以獲取傾斜角度和旋轉中心，運用仿射變換實現多幅芯片圖像的快速校正與提取。

1 圖像預處理

半導體芯片在封裝過程中存在尺寸公差，制造料盤承載口時會留有一定余量，導致芯片放置于承載口時存在一定程度的傾斜[20]。本文以QFN芯片引腳面圖像為研究對象，為了減少噪聲的影響，需要對圖像進行預處理，獲取芯片中心焊盤和引腳邊緣點簡化圖像信息，減少后續處理的計算量。多幅傾斜芯片圖像的預處理包括高斯濾波、灰度化和Canny邊緣檢測。如圖1所示，為預處理流程圖。

圖1 預處理流程圖

具體步驟為：

（1）采用3×3 高斯濾波器對圖像進行卷積，以平滑圖像，減少噪聲對后續邊緣檢測的影響。

（2）對圖像進行灰度化處理，以減少后續處理計算量。

（3）為減少噪聲影響，獲取芯片中心焊盤和引腳邊緣點，采用Canny 邊緣檢測算法，設定低閾值為100，高閾值為200。

2 基于改進凸包檢測算法的多幅芯片圖像校正方法

常見的凸包檢測算法有Graham 掃描法[21]、Andrew算法[22]，其中Andrew算法是對Graham掃描法的優化。Graham 掃描法中需要對兩個點算出叉乘，甚至在某些情況下還要算出兩個點的距離，復雜度較高且極角排序會造成丟點現象，而Andrew 算法直接通過對點(x,y)排序就可以實現，降低了算法復雜度且解決了丟點的問題[23]；但Andrew 算法在構造凸包時，存在特征點過多和計算時間較長等問題。因此，本文對Andrew算法進行改進。

2.1 Andrew算法

假設同一平面內3 個不重合的點A=(XA，YA)、B=(XB，XB)、C=(XC，YC)，記AB為點A指向點B的向量，AC為點A指向點C的向量。那么，向量AB=(XB-XA，YB-YA) ，向量AC=(XC-XA，YC-YA)。兩者叉積為：式中：T被稱為點C相對于點A和點B的凸度，通過判斷T的正負，可以確定這3 個點的相對位置。如圖2所示，根據A、B、C這3個不重合點的相對位置，凸度T有3種情況：

圖2 A、B、C三個不重合點相對位置情況

（1）若T(A，B，C)＜0 ，則AB順時針轉向AC，如圖2（a）所示。

（2）若T(A，B，C)=0，則A、B、C三點在同一直線上，如圖2（b）所示。

（3）若T(A，B，C)＞0 ，則AB逆時針轉向AC，如圖2（c）所示。

Andrew 算法通過對點(x,y)排序確定構造凸包的起始點和終點，點集按照點橫坐標x從小到大排序，在橫坐標x相同的情況下，再按照點縱坐標y從小到大排序。如圖3 所示，為采用Andrew 算法構造凸包的示意圖。從排序后的第一個點p1到排序后的最后一個點pn，通過判斷凸度T大小順時針構造凸包上部；再從排序后的最后一個點pn到排序后的第一個點p1，通過判斷凸度T大小順時針構造凸包下部；合并凸包上部和下部保留其中一個的起點和終點，獲得完整的凸包。

圖3 Andrew算法構造凸包示意圖

2.2 Andrew算法改進思路

由Andrew 算法構造凸包的方法可知，當芯片的傾斜方向不同時，構造凸包上下部的點集不同。為了提高凸包算法的效率，本文通過設計新的點集排序方式，使芯片中心焊盤左下角、右下角和右上角3個拐角的邊緣點在Andrew算法構造的凸包下部，以省去獲取凸包上部點集環節，從而大幅度減少凸包計算量。

針對Andrew 算法篩選出的凸包點集存在邊緣點簇擁情況，首先通過限制凸度大小減少凸包點集的數量；再設計新點集的排序方法對篩選后的凸包點集進行排序，濾除不需要的凸包點集。如圖4 所示，為改進的Andrew 算法步驟示意圖。具體步驟為：

（1）設計新的點集排序規則，以坐標系原點為旋轉中心將圖像逆時針旋轉45 ° ，然后將點從下往上排序。 經過排序之后，得到序列φnew：p1，p2，…，pn，其中 p1是中心焊盤左下角的點，pn是中心焊盤右上角的點。如圖4（a）所示，為點集排序示意圖。

（2）創建3 個拐角邊緣點點集序列ν，并在序列ν 中加入點p1。

（3）從第1 個點p1到最后1 個點pn逆時針構造凸包下部得到凸包點集。如圖4（b）所示，為構造凸包下部示意圖?？梢钥闯?，連接凸包下部需要篩選的邊緣點為L 型。序列φnew: p1，p2，…，pn中的點從p1開始逐個加入序列τ ，若序列τ 中的點多余1 個，取出序列τ 中最后2 個點，設定當前點pi和序列τ中最后2 個點的凸度T(τlast-1,τlast,pi) 大小為20。若設定凸度的值較小，篩選的凸包點集將過多，不利于后續篩選；若設定的凸度值較大，則存在篩選后的凸包點集中，不能將3 個拐角點都包含在內的情況。 經過測試，選擇凸度T(τlast-1,τlast,pi)為20，這樣，篩選的凸包點集中能夠包含3 個拐角點，且點集數量較少。判斷T(τlast-1,τlast,pi) 是否大于等于設定值，若T(τlast-1,τlast,pi)小于等于設定值，則刪除序列τ 中最后1 個點；若T(τlast-1,τlast,pi) 大于等于設定值，則將當前點pi加入序列τ 的最后。

（4）在序列ν 中加入點τlast。

（5）為了保證能精準獲取L 型邊緣點的拐角邊緣點，設計新的點集排序規則，以坐標系原點為旋轉中心將圖像順時針旋轉45°，然后將點從下往上排序。如圖4（c）所示，為序列τ 的點集排序示意圖。將序列τ 的點集進行排序，取出排序后的第1個點加入序列ν。

（6）在序列ν 中獲取芯片中心焊盤左下角、右下角和右上角3個拐角邊緣點。

由上述步驟可知，該方法不僅適用于QFN封裝芯片傾斜角度的快速獲??；而且對于和芯片中心焊盤相同類型、可通過水平或垂直輪廓線來表示傾斜角度、且存在L 型輪廓邊緣點的圖像，也可以應用該算法快速獲取傾斜角度。

2.3 多幅芯片圖像校正

本文通過改進Andrew 凸包檢測算法，快速獲取多幅芯片的傾斜角度和旋轉中心，校正多幅芯片圖像。如圖5 所示，為多幅芯片校正方法流程圖。具體步驟為：

（1）預處理。根據本文第1 節預處理方法，完成多幅芯片傾斜圖像的預處理，獲取每個芯片的邊緣點。

（2）邊緣點篩選。篩選出中心焊盤輪廓邊緣點，剔除非中心焊盤輪廓點。本文通過限制Canny邊緣檢測獲取的邊緣點個數，保留邊緣點個數小于500 或大于2 000 的輪廓，篩選出中心焊盤的輪廓邊緣點，濾除其余輪廓邊緣點。

（3）記錄芯片位置信息。為后續應用ROI 感興趣區域提取校正后的圖像，本文采用最小外接正矩形標記每個芯片位置信息。當得到目標對象輪廓后，獲取包覆此輪廓的最小正矩形，并記錄其左上角坐標和長寬。

（4）獲取傾斜角度和旋轉中心。為了獲取每個芯片的傾斜角度，本文提出改進Andrew 凸包檢測算法，篩選凸包點，獲取每個芯片中心焊盤左下角、右上角和右下角3個拐角的邊緣點。計算芯片中心焊盤左下角拐角點和右下角拐角點坐標組成的向量與坐標x軸之間的夾角，即每個芯片的傾斜角度。設兩個坐標點分別為p(x,y)、q(x,y)，則圖像傾斜角度θ計算公式為：

式中：xp和yp為點p的橫坐標和縱坐標；xq和yq為點q的橫坐標和縱坐標。為了獲取每個芯片的旋轉中心，應用改進Andrew 凸包檢測算法篩選凸包獲得中心焊盤左下角邊緣點和右上角邊緣點，兩者連線的中心點即旋轉中心。

（5）校正傾斜芯片圖像?；诟倪MAndrew 凸包檢測算法獲取多幅芯片傾斜角度，且以每個芯片形心為旋轉中心獲得仿射變換矩陣，通過仿射變換矩陣將傾斜圖像上的每個點進行旋轉校正。在二維空間內，常見的旋轉變換矩陣有兩種：一種為繞原點旋轉；另一種為繞任意點旋轉。繞原點旋轉的旋轉變換矩陣簡單直接，但圖像旋轉中心不在原點，需先將圖像移動到原點再進行旋轉，該操作將增加計算量和實現難度。相比之下，繞任意點旋轉可以直接指定旋轉中心點的坐標，方便靈活。由于通過改進Andrew 算法已經獲取了芯片的傾斜角度和旋轉中心，因此，本文將芯片圖像繞旋轉中心旋轉以實現校正。設旋轉中心為(x,y)，傾斜角度為θ弧度，繞旋轉中心逆時針旋轉θ的旋轉變換矩陣M1計算公式為：

繞旋轉中心順時針旋轉θ的旋轉變換矩陣M2計算公式為：

設傾斜圖像上的點為(x1,y1)，旋轉變換矩陣M為M1或M2，旋轉后圖像上的點(x2,y2) 計算公式為：

（6）提取校正后的芯片圖像。根據最小外接正矩形標記每個芯片位置信息，以芯片的左上角坐標和芯片的長寬設定矩形ROI 區域，進而提取校正后多幅芯片圖像的矩形ROI區域。

3 實驗結果與分析

3.1 實驗結果

本文通過改進凸包檢測算法實現多幅芯片圖像校正，解決了傳統方法在處理多幅芯片圖像時必須先進行圖像切分才能夠繼續校正的問題[20]，從而有效提高了多幅圖像的校正效率。選取10 幅不同的多幅QFN 芯片引腳面圖像為實驗對象，每幅圖像中包含9 個QFN 芯片，共90 個QFN 芯片。實驗環境為四核十二線程、CPU@2.2 GHz、內存16 G、Visual Studio 2017。如圖7（a）所示，為多幅芯片傾斜圖像。如圖7（b）至7（j）所示，為校正后的多幅芯片圖像，其分別對應多幅芯片傾斜圖像中第1 至第9 個芯片。由圖7 可見，對于一幅包含9 個不同芯片的多幅QFN 芯片引腳面圖像，本文方法能夠省去單幅芯片圖像的切分環節，直接完成每個芯片的校正與提取。

圖7 采用本文方法校正多幅芯片圖像

3.2 算法對比

3.2.1 時間對比

對于多幅芯片圖像，傳統算法需要先切分，再對切分后的單幅芯片圖像進行校正。如圖8所示，為了檢測切分多幅芯片圖像的運行時間，本文對采集到的9 幅多幅芯片傾斜圖像進行切分，每幅圖像中包含9 個芯片，使得切分后的圖像中僅包含單幅芯片。如圖8（a）所示，為多幅芯片傾斜圖像，如圖8（b）至8（j）所示，為切分后單幅芯片傾斜圖像，其分別對應多幅芯片傾斜圖像中第1 個至第9個芯片。

圖8 切分多幅芯片圖像

如表1 所示，為9 張多幅芯片傾斜圖像的切分時間。從表1 可見，平均切分時間為406.67 ms，平均每個芯片的切分時間為45.18 ms。本文采用最小外接正矩形標記芯片位置信息，應用ROI 完成校正后的芯片圖像提取，從而直接省去如表1 所示的45.18 ms 的平均單幅芯片切分時間。

表1 切分多幅芯片圖像的時間 單位：ms

為了檢測本文方法與傳統Hough 變換校正方法[24]、最小外接矩形校正方法[25]、傅里葉變換校正方法[26]的時間差異，分別對9幅不同的QFN芯片引腳面圖像進行運行時間對比。為了保證算法對比的有效性，首先，將3 種對比算法都按上述完成芯片傾斜圖像的預處理，獲取邊緣點；接著，獲取邊緣點最小外接矩形，通過限制最小外接矩形長寬，篩選出芯片中心焊盤輪廓邊緣點；最后，通過芯片中心焊盤的最小外接矩形確定旋轉中心，該旋轉中心即為最小外接矩形的中心點。

傳統Hough 變換校正方法通過Hough 變換計算芯片中心焊盤水平或垂直輪廓線的傾斜角度，再應用仿射變換校正芯片圖像。最小外接矩形校正方法通過最小外接矩形獲取芯片中心焊盤的傾斜角度，再應用仿射變換校正芯片圖像。傅里葉變換校正方法通過最小外接正矩形標記芯片中心焊盤位置信息，設定矩形ROI 區域提取芯片中心焊盤圖像；再應用傅里葉變換求出芯片中心焊盤頻域圖像，應用Hough 變換計算頻域圖像中直線的傾斜角度；最后應用仿射變換校正芯片圖像。如表2所示，為4種算法的運行時間。對9 幅芯片引腳面圖像校正的平均時間，傳統Hough 變換校正方法為153.89 ms，最小外接矩形校正方法為120.33 ms，傅里葉變換校正方法為191.89 ms，本文方法處理單幅圖像的平均用時僅為45.11 ms；與對比方法中平均用時最少的最小外接矩形校正方法120.33 ms 相比，本文方法的平均用時少于其1/2。由于采用最小外接正矩形標記芯片位置信息，應用ROI 完成校正后芯片圖像的提取，省去了單幅芯片圖像切分環節，本文方法校正包含9個芯片的多幅芯片圖像中每個芯片的平均時間為79.44 ms，與對比方法中校正單幅芯片平均用時最少的最小外接矩形校正方法120.33 ms 相比，本文方法校正多幅芯片圖像的平均用時少于其2/3。

表2 4種算法校正圖像的時間 單位：ms

3.2.2 角度偏差對比

如圖9 所示，通過人工標定5 幅傾角分別為1°、2°、3°、4°、5°，規格為34 mm×30 mm×9 mm的金屬量塊圖像，對本文方法獲取傾斜角度的準確性進行驗證。如表3所示，運用上述4種算法分別檢測5幅量塊圖像得到傾斜角度及偏差值。根據表3，本文方法獲取的5幅量塊圖像傾斜角度和人工標定角度的平均偏差為0.085°，低于其它3種對比方法，說明本文方法可以獲取相對更為準確的量塊圖像傾斜角度。

表3 4種算法獲取傾斜角度與人工標定角度的誤差對比 單位：（°）

為了驗證本文方法應用在QFN芯片引腳面圖像檢測中的準確性，如圖10所示，選取一張標準無傾斜的QFN 芯片引腳面圖像為實驗對象，將此芯片圖像每次順時針旋轉0.5°，旋轉7 次獲取傾角分別為0.5°、1.0°、1.5°、2.0°、2.5°、3.0°、3.5°的7 張標準角度傾斜芯片圖像。如表4所示，運用上述4種算法分別檢測7張標準角度傾斜芯片圖像的傾斜角度及偏差值，平均偏差分別為：本文方法0.112°、傳統Hough變換校正方法0.293°、最小外接矩形校正方法0.339°、傅里葉變換校正方法0.753°；本文方法獲取的平均偏差小于其它3種對比方法，說明其獲取傾斜角度更加準確。

表4 4種算法獲取傾斜角度與標準角度的誤差對比 單位：（°）

圖10 標準角度傾斜芯片圖像

4 結論

本文以多幅QFN 芯片圖像為實驗對象，針對芯片在封裝缺陷視覺檢測過程中存在的圖像傾斜問題，改進Andrew 凸包檢測算法，實現多幅芯片圖像校正。首先，通過限制輪廓點個數篩選出芯片中心焊盤輪廓，用最小外接正矩形標記每個芯片位置信息；然后，采用改進Andrew 算法快速獲取多幅芯片圖像中每個芯片的傾斜角度和旋轉中心；最后，應用仿射變換校正多幅芯片圖像，根據芯片位置信息應用ROI完成芯片圖像的校正與提取。實驗結果表明，與傳統的Hough 變換方法、最小外接矩形方法、傅里葉變換校正方法相比，該方法能夠更精準校正芯片圖像，且校正單幅芯片圖像的運行時間少于對比方法的1/2。

本文方法采用最小外接矩形標記芯片位置信息，應用ROI完成校正后的芯片圖像提取，省去了單幅芯片圖像切分環節，能夠進一步提高圖像校正效率。改進的Andrew算法不僅適用于QFN芯片圖像，而且同樣適用于可通過水平或垂直輪廓線來表示傾斜角度且存在L 型輪廓邊緣點的圖像。但是，該方法依賴于能夠獲取連續不間斷的L型邊緣點，若缺少L型邊緣點，則無法獲取旋轉中心；若邊緣點不連續，則會出現兩個傾斜角度和旋轉中心，影響校正精度。在后續研究中，可研究邊緣檢測算法以獲取連續邊緣，再配合本文改進的Andrew 算法，獲取存在L型邊緣點圖像的傾斜角度。