陳慧敏 張合生 朱曉錦

(上海大學機電工程與自動化學院 上海 200444)

0 引 言

芯片表面字符是辨別封裝相同但是功能不同的芯片的唯一方式，所以在進行集成電路測試前，需要對IC芯片表面的制造商名稱、產品編號、序列號等字符進行識別[1]。能否正確識別一個字符，字符分割起著重要的作用，因為在識別前需要將字符從文字圖像中準確地分離出來[2]。但是由于工業(yè)環(huán)境復雜，所采集的圖像普遍存在亮度對比度較低、字符斷裂和噪聲干擾等問題。在對芯片圖像進行預處理時可能會造成芯片字符標識粘連。所以，在識別之前必須先對粘連字符進行分割。

針對粘連字符分割，許多學者進行研究并取得了有益的成果。Ma等[3]針對藏文歷史文獻圖像中的粘連字符，使用改進的harris角點檢測算法來提取粘連區(qū)域分割點，準確率達到95%，但并不適用于芯片圖像。Farulla等[4]提出一種新的模糊策略并結合粘連字符的三個特點，在噪聲情況下也能進行較好的分割，但在對于筆畫重疊的字符可能無法實現(xiàn)準確分割。Zaw等[5]提出了一種基于區(qū)域定位的粘連字符分割技術，使用緬甸文字的孔洞數、上下分量和左右分量等特征進行分割。姜燕[6]引入種子點概念，并用下種子點產生引力，使得水滴在合力作用下運動，但是其只能分割固定個數的字符。李興國等[7]將字符的寬度統(tǒng)計值和豎直投影直方圖中的投影極小值點相結合找到分割點，對驗證碼粘連字符分割取得了較好的效果，對芯片圖像中一些寬度差別較大的字符無法正確分割。Tang等[8]結合二叉樹和字符寬度選取分割最優(yōu)路徑，有效降低了分割位置的不確定性，但容易受到偽谷底的影響。

本文使用一種基于改進滴水算法的方法，對芯片圖像粘連字符進行分割。利用字符寬度、分割點方差和上下分割點對應關系來篩選垂直投影、上輪廓和下輪廓的局部極小值，以此提高滴水算法起始點的正確率；考慮水滴的不同位置受到種子點(即下分割點)的影響不同，因此定義不同的水滴滴落規(guī)則，得到更為精準的分割。實際測試表明，本文方法可有效解決芯片圖像的字符粘連問題，并且在分割精準度上擁有良好的表現(xiàn)。

1 滴水算法

在常見的粘連字符分割方法中，滴水算法相對較為簡單且有效，并且在分割粘連數字串上擁有較好的效果，其基本原理是模擬水滴在重力的作用下從高處向下滴落的過程來對粘連字符進行切分[9]。水滴從粘連字符串的頂端沿輪廓向下或水平滴落，當水滴落入字符輪廓的凹陷處時，水滴會融入字符筆畫中，穿透筆畫繼續(xù)向下滑落。在此過程中，水滴經過的軌跡就構成了粘連字符分割的路徑。

滴水算法主要受三個因素影響，分別是起始滴落點、水滴運動規(guī)則和運動方向。圖1(a)中n0表示為水滴當前像素點位置，其下一步的水滴位置由其左右的兩個像素點和下方的三個像素點共同決定。

圖1 滴水算法原理圖

一組滴水算法根據水滴下落方向的不同會有不同的分割路徑[10]，以其中的Top-Left方法為例，水滴的運動規(guī)則如圖1(b)所示，其中w表示白色像素，b表示黑色像素，*表示既可能是白色像素，也可能是黑色像素。以圖1(b)中的(1)為例，當前水滴位置相鄰像素都為白色時，水滴將會向下滴落。當水滴落入字符輪廓的凹陷處時，情況4和情況5循環(huán)交替出現(xiàn)，即水滴在水平左右來回移動。因此傳統(tǒng)的滴水算法起始點選取困難并且容易造成斷裂字符[11]。

文獻[12]中，對水滴算法進行了數學描述。設當前水滴坐標為(xi,yi)，水滴路徑為T，則T(xi+1,yi+1)=f(xi,yi,Wi),其中i=0,1,2,…N,(xi+1,yi+1)表示為下個水滴坐標位置，Wi是水滴在當前位置上的重力勢能的衡量。Wi的值由式(1)所決定。

(1)

式中：zj表示nj點的像素值，白色像素為1,黑色像素為0。Wj表示nj點為下一個滴落點權重大小，Wj=6-j。

2 改進的滴水算法

傳統(tǒng)的滴水算法的起點選擇是通過對字符圖像從上到下從左到右掃描每一行像素，第一個滿足(…1*0…01…)分布的白色像素點為水滴算法的起點[13]。其中，1表示白色像素點，0表示黑色像素點，*表示既可以是白色相似點也可以是黑色像素點。上述方式選擇的初始滴落點可能處于字符的凹陷處或者是字符內部，這將會造成錯誤分割。因此本文利用垂直投影和上下輪廓選出候選滴落點，再基于字符寬度、雙向路徑方差和上下點一一對應關系篩選得到初始滴落點。

對芯片粘連字符的分割，首先檢測輪廓連通域，并對其進行分析，提取得到粘連字符。然后對粘連區(qū)域進行垂直投影，得到垂直投影直方圖和上下輪廓圖，三者相互印證得到分割候選點。利用預處理時得到的字符的最小寬度Dmin和最大寬度Dmax，對候選點進行第一次篩選；對第一次篩選后的分割點進行雙向路徑求方差，并進行第二次篩選；最后根據上下分割點對應關系，補齊或篩選得到有效分割點。以有效上分割點為改進的滴水算法的初始滴落點，以有效下分割點為算法終止點。然后根據水滴位置與種子點(即下分割點)之間的距離選擇不同的滴落規(guī)則進行分割。對分割結果進行判斷，若不滿足單字符條件，則繼續(xù)進行粘連分割。算法流程如圖2所示。

圖2 粘連字符分割流程

2.1 芯片圖像預處理

分割可為兩步：圖像的預處理和字符的分割[8]，所以先對芯片圖像進行預處理。工廠采集環(huán)境復雜，多數的芯片圖像亮度和對比例都較低，因此先對圖像進行對比度和亮度處理，然后將圖片二值化；為了能夠準確地得到字符寬度，將圖片進行縮放處理；此時得到的圖片可能存在許多噪聲，噪聲往往不利于字符分割，所以對圖片進行中值濾波處理。最后，為了防止斷裂字符影響字符寬度的統(tǒng)計對圖片進行膨脹處理。芯片圖像經過預處理后如圖3所示。

圖3 芯片圖像預處理圖

2.2 粘連區(qū)域提取

2.2.1 標準字符

本文需要利用字符寬度等先驗信息對粘連字符進行分割，所以需要先統(tǒng)計標準字符的大小。隨機選取部分芯片圖像進行手工分割，排除過窄與過寬的字符后，統(tǒng)計分離出的字符寬高比，從而得到字符寬高比最小值Pmin和最大值Pmax。

對預處理后圖像中的白色像素內容進行輪廓連通域檢測，根據連通域作最小外接矩形框。對圖像中的矩形框進行篩選，來定位目標圖像中的字符部分。在所得矩形框中選擇寬高比在[Pmin,Pmax]之間的矩形框視為標準字符，并對這些矩形框的寬高比、寬度和高度分別求均值。將這些作為該芯片圖像的標準字符，參考值為：寬度Waver和高度Haver，最小字符寬度Dmin和最大字符寬度Dmax。

2.2.2 粘連區(qū)域提取

針對芯片中存在橫豎混排字符的情況，采用對膨脹后的芯片圖像進行輪廓連通域檢測并根據連通域最小外接矩形框的面積、寬度和高度等先驗條件進行行列矩形框判斷，將相鄰的行(或列)矩形框合并，最后得到行列字符。行列判斷過程如圖4(a)所示。對行字符(列字符旋轉90度)進行水平投影分割后，使用最小外接矩形框方法將圖片分割成若干區(qū)域。檢測各個矩形框寬高比和寬度等信息與標準字符的參考值進行比較，可以很容易地合并斷裂字符，并且提取出粘連字符區(qū)域。如圖4(b)所示，經以上分析方法提取的芯片字符區(qū)域中包含部分粘連字符區(qū)域。

圖4 粘連字符區(qū)域提取過程

2.3 字符分割點

2.3.1 分割候選點

文獻[14]通過對粘連字符做垂直投影，統(tǒng)計投影值的局部極小值點以此得到初始滴落點。但是對于原本就存在凹陷的英文字符，此方法難以得到較為準確的初始滴落點。本文對垂直投影圖和上下輪廓圖分別求取局部極值，并相互印證，得到字符分割候選點。

先對二值圖像進行反色處理后得到白底黑字的圖像，再進行垂直投影得到圖5(a)的垂直投影圖。

圖5 粘連字符區(qū)域垂直投影圖和輪廓圖

由字符每列的最高點組成的輪廓稱之為上輪廓[15]，其定義如式(2)所示。

PT(i)=ET(i)i=1,2,…,M

(2)

式中：M表示圖像總列數，PT(i)表示像素點坐標，ET(i)表示第i列從上到下遇到的第一個白色像素點的縱坐標值。若此列無白色像素點，則ET(i)=0。

同理，由字符每列的最低點組成的輪廓稱之為下輪廓。其定義如式(3)所示。

PB(i)=EB(i)i=1,2,…，M

(3)

式中：PB(i)表示像素點坐標；EB(i)表示第i列從下到上遇到的第一個白色像素點的縱坐標值。若此列無白色像素點，則EB(i)=0。由此得到的上下輪廓圖如圖5中(b)和(c)所示。

對垂直投影圖和上輪廓圖求局部極大值，對下輪廓圖求局部極小值。如果存在一個ε>0,使得對于任意滿足|x-x*|<ε的x都有f(x)≤f(x*)(或f(x)≥f(x*))，則稱f(x*)為局部極值。由此得到圖6中的局部極值點。

圖6 局部極值點

一般上下分割點與垂直投影極值點是對應關系，所以為了去除上下輪廓的偽投影極值點，可以通過三組局部極值點互相篩選得到上下分割候選點，即滿足式(4)。最后得到的每對上下候選點之間不超過a個像素點，且最后得到的垂直投影極值點不超過a個像素點。本文實驗中選擇a=5作為分割點之間的距離，是由于上下分割點之間距離較近，能夠排除大部分上下輪廓的偽投影極值點。

(4)

式中：m[i]表示上輪廓分割候選點的橫坐標值，n[i]表示下輪廓分割候選點的橫坐標值,v[i]表示垂直投影分割候選點的橫坐標值。

2.3.2 有效分割點

經過2.3.1節(jié)的篩選后，依舊存在部分偽分割點，所以需對分割候選點進一步篩選。本文利用字符寬度、雙向路徑方差和上下分割點對應關系提取有效分割點。

為了得到更準確的粘連字個數k，對小數點后兩位進行四舍五入操作。k的求取公式如下：

(5)

式中：round(·)為四舍五入操作，w和h分別代表粘連區(qū)域的寬度和高度，Waver和Haver分別代表標準字符的寬度和高度。

分別從左右兩端開始向另一端根據字符寬度確定有效分割點，并對最后得到的這兩組分割點進行方差計算[16]，選取方差較小的一組作為有效分割點。設分割候選點共有N個，具體步驟如下：

Step1如式(6)所示，在[xp+Dmin，xp+Dmax]內尋找上輪廓有效分割點。其中：d表示可容許范圍誤差；p=0時，xp表示粘連字符區(qū)域的左端點，p>0時，xp表示找到的前一個有效分割點。

(6)

Step2同理，從右端開始向左確定一組上輪廓有效分割點，即在[xp-Dmax，xp-Dmin]內尋找上輪廓有效分割點。此時p=0，xp表示粘連字符區(qū)域的右端點。

(7)

Step3設此時得到的有效分割點個數為S，有效分割點數組為sp。分別對上述兩組有效分割點求取方差，選取方差較小的一組為上輪廓有效分割點mp。方差公式如下：

(8)

Step4同理，對下輪廓局部極值求取有效分割點np。

由于此時得到的上輪廓和下輪廓有效分割點個數可能不相同，為后續(xù)能將下分割點設為種子點對水滴位置進行引導，所以根據上下分割點一一對應關系，進行最后一步篩選。篩選情況分為以下四種：

(1) 當mp和np中有一組個數與k-1相同，且另一組個數不為0時，則利用個數是k-1這組，以式(9)為標準篩選另外一組。例如，假設mp個數與k-1相同，np個數為n，從np中選取與每個上分割點不相差a個像素點的下分割點作為有效點。

(9)

(2) 當mp和np的個數都不與k-1相同，且兩者個數都既不為0也互不相同時，則選擇個數小的數組篩選個數大的數組，篩選標準為式(9)。

(3) 當mp和np的個數都不與k-1相同時，且兩者個數中有一組為0，若np個數為0則以mp中的數據為初始滴落點，并讓(mp[i],h)為下分割點，其中：mp[i]表示上分割點的橫坐標值，h表示粘連字符區(qū)域的高度；若mp個數為0則以(np[i],0)為初始滴落點，np中的數據為下分割點。

(4) 當mp和np的個數相同且都不為k-1時，則進行互相篩選，即滿足式(9)。

根據上述情況，對分割候選點mp和np進行篩選.若篩選后兩組個數不同，對個數小的以(mp[i],h)或(np[i],0)進行填充，最后得到上下有效分割點，如圖7所示?？梢?，分割點的選取避免了字符凹陷的部分。選取上分割點作為初始滴落點，下分割點作為種子點，使得水滴在合力作用下運動。

圖7 上下有效分割點

2.4 滴落規(guī)則

文獻[6]中，通過引入種子點概念，使得水滴在合力作用下運動，本文在此基礎上進行改進。通過縮小引力范圍來提高分割的精準度，對在重力作用下的水滴規(guī)則進行了修改，主要以向下為首個選擇方向，種子點的位置僅作為引導方向，避免水滴為了向種子點位置靠近而產生斜切路徑。在水滴未進入種子點(即下分割點)引力影響范圍內時，水滴主要受重力作用，種子點主要起著方向引導的作用；當水滴進入種子點影響范圍內時，水滴受引力和重力共同作用。設(x0,y0)為當前水滴位置，下分割點即引導點為位置為(x1,y1)。算法分為以下兩種情況：

(1) 0≤y0≤0.5y1時，水滴主要受重力作用。

當x0>x1時，以左下為引導方向，水滴的運動規(guī)則如圖8(a)所示。如果(x0,y0+1)為白色像素，水滴則直接向下滴落；如果(x0,y0+1)為黑色像素，則會依次按照左下、右下、左邊和右邊作為下一個水滴位置。

(a) 0≤y0<0.5×y1&& x0>x1

(b) 0≤y0<0.5×y1&& x0>x1

(c) 0≤y0<0.5×y1&& x0>x1圖8 受重力作用下的水滴運動圖

當x0=x1，只受重力作用。因為此時引導點和水滴點處于同一列，不受任何方向引導，水滴的運動規(guī)則如圖8(b)所示。

當x0

其中，當水滴落入字符凹陷處即局部極值時，對應的處理如下：(a)、(b)和(c)三種情況中，若情況(4)和情況(5)不斷交替出現(xiàn)時，應從a(4)轉入b(6)、b(4)轉入b(6)以及c(4)轉入b(6)。

(2) 0.5y1≤y0≤y1時，水滴受合力作用。

當x0>x1時，水滴的運動規(guī)則如圖9(a)所示，合力方向為左下；如果(x0+1,y0+1)為白色像素，水滴則直接向左下方向滴落；如果(x0+1,y0+1)為黑色像素，則會依次按照下、右下、左邊和右邊作為下一個水滴位置。

(a) 0.5×y1≤y0x1

(b) 0.5×y1≤y0x1

(c) 0.5×y1≤y0x1圖9 受合力作用下的水滴運動圖

當x0=x1時，水滴的運動規(guī)則如圖9(b)所示，合力方向向下，與只受到重力作用時保持一樣的運動規(guī)則。

當x0

其中，當水滴落入字符凹陷處即局部極值時，對應的處理如下：當水滴出現(xiàn)a(4)→b(5)→a(4)不斷交替時，應從a(4)轉入(a)6；當水滴出現(xiàn)a(4)→a(5)→a(6)或a(5)→a(4)→a(5) 不斷交替時，應從a(4)轉入(a)6；當水滴出現(xiàn)b(4)→a(5)→b(4)或b(5)→c(5)→b(5)不斷交替時，應從b(4)或b(5)轉入b(6)；當水滴出現(xiàn)c(4)→b(5)→c(4)不斷交替時，應從c(4)轉入c(6)；當水滴出現(xiàn)c(4)→c(5)→c(4)或c(5)→c(4)→c(5)不斷交替時，應從c(4) 轉入c(6)。

(3)y0=y1時，水滴平移至(x1,y1)。

在分割好的字符圖像中可能依然存在粘連，為了防止發(fā)生欠分割，對每個分割出的子圖都進行粘連區(qū)域判斷。當切分后的圖像寬高之比滿足式(10)時，認為子圖中字符依然存在粘連，則繼續(xù)根據上述方法進行粘連字符切分；若不滿足式(10)，則認為此時得到的為單幅字符圖像。

(10)

選取1.5倍的標準字符寬高比作為判斷條件是考慮到粘連區(qū)域中存在“1”或“i”等寬度過小的字符這類情況。

3 實驗結果與分析

為了驗證所提出算法的有效性，選取了在上海某芯片封裝制造企業(yè)所采集芯片的表面字符圖像進行實驗并分析結果。由于復雜的生產環(huán)境，所采集的圖像普遍存在亮度對比度低、字符斷裂和噪聲干擾等問題，因此在對芯片圖像進行預處理時會造成芯片字符粘連。隨機選取200幅芯片圖像，粘連區(qū)域共436個，其中包括雙字粘連、多字粘連和字符傾斜。

本文實驗中，誤差d=8，像素誤差a=5，對印刷字符較粗的芯片選取正常字符寬高之比為[0.4, 0.95]之間，字符較細的芯片為[0.1, 0.4]之間。首先經過本文的預處理來提取粘連字符區(qū)域，然后分別采用豎直投影分割算法、文獻[7]算法和本文算法進行字符分割。以文獻[17]中的字符分割準則為標準來統(tǒng)計正確率，即滿足式(11)則認為得到正確分割，其中A表示算法分割出的字符圖像，B表示正確字符分割圖像。

(11)

從實驗結果中可以看出，針對芯片圖像中粘連字符分割，本文的算法相比豎直投影法和傳統(tǒng)滴水算法取得更好的效果。部分芯片粘連字符分割結果如圖10和表1所示，可看出較目前已有文獻所采用的算法，本文算法準確率高，能夠對斷裂字符進行準確分割且運行時間較短。對粘連嚴重的芯片字符圖像能夠進行準確分割，起始滴落點位置的確定有所提高并且可以得到較為完整的輪廓分割路徑。對分割失敗的字符圖像進行分析，主要原因有以下兩部分：部分芯片字符大小差距過大，導致起始滴落點的位置選擇錯誤，從而導致字符過分割；在粘連情況十分嚴重的情況下，由于種子點的影響，導致切分路徑產生誤差，導致某些字符輪廓不夠完整。

圖10 本文方法與豎直分割、文獻[7]算法對比

表1 部分芯片粘連字符分割結果

4 結 語

本文提出一種改進的滴水算法對芯片圖像粘連字符進行分割。在傳統(tǒng)的滴水算法上，對起始滴落點的選取進行優(yōu)化，并改進滴落規(guī)則。通過字符寬度、方差和分割點對應關系提取有效分割點，提高了起始滴落點的準確度；根據當前水滴位置與種子點之間的距離來選擇水滴滴落方式，從而得到擁有較為完整的字符圖像。實驗結果證明了該方法的有效性和高精準度。實驗過程中也發(fā)現(xiàn)，此方法依然還存在著一些不足之處。例如，字符大小差距過大時，字符粘連位置難以確定；對于一些筆畫重疊、粘連嚴重的字符無法進行正確分割；當字符嚴重扭曲時，水滴的運動規(guī)則無法分割出完整的字符輪廓。因此，如何提高在這些情況下粘連字符的分割準確率，則是下一步要繼續(xù)深入研究的方向。