面向多目標(biāo)透鏡的連通域標(biāo)記檢測算法

謝智烜，姚紅兵，范 寧，陳 楓

(1.江蘇大學(xué) 機(jī)械工程學(xué)院，江蘇 鎮(zhèn)江 212000；2.河海大學(xué) 理學(xué)院，江蘇 南京 210098)

機(jī)器視覺[1-2]是一門研究如何利用計(jì)算機(jī)來模擬人類視覺功能并識別圖像中有價(jià)值信息的學(xué)科，主要由3個(gè)系統(tǒng)組成[3]：照明系統(tǒng)、圖像處理系統(tǒng)和機(jī)械控制系統(tǒng)。圖像處理系統(tǒng)是機(jī)器視覺中非常重要的一個(gè)部分，它接收來自照明系統(tǒng)的圖像，并對其分析出所需要的有價(jià)值信息，例如目標(biāo)的坐標(biāo)、種類等，并將這些信息傳輸給機(jī)械控制系統(tǒng)。

連通域標(biāo)記是圖像處理系統(tǒng)中常用的一個(gè)方法，該方法可以從圖像中提取目標(biāo)區(qū)域，并統(tǒng)計(jì)目標(biāo)區(qū)域的特征參數(shù)，如面積和外接矩形等。目前常用的連通域標(biāo)記算法主要分為兩類[4-5]：基于游程的連通域標(biāo)記算法和基于像素的連通域標(biāo)記算法。其中基于行程的連通域標(biāo)記算法[6]先對游程進(jìn)行編碼，然后判斷游程與游程之間的是否連通來標(biāo)定連通域；基于像素的連通域標(biāo)記算法[7]直接通過判斷像素與像素之間是否相連來標(biāo)定連通域。目前針對單目標(biāo)[8]、多目標(biāo)[9-10]以及動(dòng)態(tài)目標(biāo)追蹤[11-12]等方面已有較多研究：王凱[13]等人通過對圖像面積分塊來達(dá)到快速區(qū)分前后景的目的。趙曉[14]等人提出一種基于段的連通域標(biāo)記處理算法，用于檢測紙病。姑麗祖熱·吐爾遜和尤努斯·艾沙[15]等使用跑長碼的連通區(qū)域算法，通過結(jié)合重疊度計(jì)算方法完成了對維吾爾族文字的切分。

上述方法中的目標(biāo)物與目標(biāo)物大多是完全分離開的，可是在實(shí)際中則會出現(xiàn)兩個(gè)甚至多個(gè)目標(biāo)物體緊挨在一起且連通域相連的情況。如圖1所示，圖1(a)為透鏡在側(cè)面光源照射下產(chǎn)生的圖像，圖1(b)是經(jīng)過預(yù)處理后的二值圖像。由圖可知，標(biāo)號為2和3的目標(biāo)透鏡是緊挨在一起的。為了解決這一問題，本文在圖像邊框處做一個(gè)特殊的標(biāo)記值，設(shè)計(jì)了一種針對多目標(biāo)透鏡的連通域檢測算法。

1 算法原理

本算法以被白色區(qū)域包圍的黑色區(qū)域?yàn)樘崛∧繕?biāo)，將圖像的4個(gè)邊框處的臨時(shí)標(biāo)記值都置為2，將二值圖像中的原本為1的白色區(qū)域的臨時(shí)標(biāo)記置為1。原本被白色區(qū)域包圍的黑色區(qū)域的臨時(shí)標(biāo)記都將大于2，最終只輸出所有標(biāo)記值大于2的區(qū)域，從而完成目標(biāo)區(qū)域的提取。

算法首先對二值圖像進(jìn)行從上到下、從左到右的一次掃描，在掃描過程中進(jìn)行連通域的臨時(shí)標(biāo)記，并且對臨時(shí)標(biāo)記對應(yīng)的參數(shù)存儲器進(jìn)行更新。在標(biāo)記過程中發(fā)現(xiàn)兩個(gè)臨時(shí)標(biāo)記等價(jià)時(shí)，需要在等價(jià)表中生成對應(yīng)的等價(jià)關(guān)系。一次掃描結(jié)束后，對臨時(shí)標(biāo)記以及參數(shù)存儲器進(jìn)行整理，同時(shí)剔除一些面積小的虛假目標(biāo)。最后，將目標(biāo)區(qū)域?qū)?yīng)的參數(shù)寄存器內(nèi)的數(shù)據(jù)輸出。

算法主要由3個(gè)部分組成：圖像標(biāo)定與等價(jià)表生成模塊、標(biāo)記值參數(shù)寄存器更新與合并模塊，以及等價(jià)表整理模塊。

1.1 圖像標(biāo)定與等價(jià)表生成模塊

標(biāo)記模塊采用單次逐像素法對輸入的大小為M×N的二值圖像進(jìn)行標(biāo)記。標(biāo)記模塊采用4連通模式，每個(gè)點(diǎn)需要考慮該點(diǎn)的正上方點(diǎn)和左邊點(diǎn)的值(如果存在)。標(biāo)記時(shí)，需要1個(gè)初始值為3的標(biāo)記值tip，1個(gè)等價(jià)表L和兩個(gè)行存儲器，分別為行存儲器0和行存儲器1。等價(jià)表L中地址代表臨時(shí)標(biāo)記，值對應(yīng)等價(jià)關(guān)系，例如L(n1)=n2，表示臨時(shí)標(biāo)記n1和n2具有等價(jià)關(guān)系。當(dāng)標(biāo)記模塊對第0行進(jìn)行讀取時(shí)，只對行存儲器0進(jìn)行操作，在行存儲器0對應(yīng)位置寫入當(dāng)前行位置像素的標(biāo)記值；當(dāng)標(biāo)記模塊對1、3、5等等奇數(shù)行進(jìn)行讀取時(shí)，行存儲器1寫入，行存儲器0作為該行的上一行；當(dāng)標(biāo)記模塊對2、4、6等等偶數(shù)行進(jìn)行讀取時(shí)，行存儲器0寫入當(dāng)前行位置像素的標(biāo)記值，行存儲器1作為該行的上一行。

圖3中箭頭表示圖像掃描的順序，灰色部分為已經(jīng)標(biāo)記完成的像素點(diǎn)，白色部分為未標(biāo)記點(diǎn)，x表示當(dāng)前待標(biāo)記點(diǎn)的值，a、b、c、d均為臨時(shí)標(biāo)記值。在進(jìn)行全圖標(biāo)記時(shí)主要由以下幾種情況：第1行、第M行、第1列、第N列以及2～M行2～N列。其中第一行、第M行、第一列和第N列組成了一幅圖像的框架，本算法中將這兩行兩列所對應(yīng)的標(biāo)記都置為2。對第2～M行2～N列，先判斷當(dāng)前像素點(diǎn)的值為0還是1：如果是1，那么將該點(diǎn)對應(yīng)的標(biāo)記都置為1；如果為0，則需要查看該像素點(diǎn)上一行同位置行存儲器1中的值和當(dāng)前行坐標(biāo)位置行存儲器0中的值。具體可以分為以下幾種情況(假設(shè)當(dāng)前行為偶數(shù)行，即行存儲器0為當(dāng)前行，行存儲器1為上一行)：(1)左邊和上邊都是1。即左邊像素點(diǎn)值的標(biāo)記值d為1，上邊像素點(diǎn)值的標(biāo)記值b為1，當(dāng)前像素點(diǎn)與左邊和上邊的點(diǎn)都不連通，可以當(dāng)做一個(gè)新的開始節(jié)點(diǎn)，將tip的值賦給當(dāng)前像素點(diǎn)對應(yīng)的行存儲器0。同時(shí)對等價(jià)表L進(jìn)行操作，以tip為地址，寫入值為tip，最后tip加1；(2)左邊為1，上邊大于等于2。即左邊像素點(diǎn)值為1，上邊像素點(diǎn)值為0，該像素點(diǎn)的標(biāo)記值等于上邊的點(diǎn)的標(biāo)記值，將該值寫入對應(yīng)的行存儲器0。不對等價(jià)表進(jìn)行操作；(3)左邊大于等于2，上邊為1。即左邊像素點(diǎn)值為0，上邊像素點(diǎn)值為1，該像素點(diǎn)的標(biāo)記值等于左邊的點(diǎn)的標(biāo)記值，將該值寫入對應(yīng)的行存儲器0，此時(shí)不對等價(jià)表進(jìn)行操作；(4)左邊大于等于2，上邊大于等于2。此時(shí)出現(xiàn)了等價(jià)關(guān)系，需要比較上邊像素點(diǎn)的標(biāo)記值b和左邊像素點(diǎn)的標(biāo)記值d的大小關(guān)系。若b=d，不進(jìn)行等價(jià)關(guān)系的處理；若b>d，將左邊點(diǎn)標(biāo)記值賦給當(dāng)前點(diǎn)，同時(shí)將臨時(shí)標(biāo)記b和d計(jì)入等價(jià)關(guān)系；若b

1.2 標(biāo)記值參數(shù)寄存器更新和合并模塊

參數(shù)存儲器的結(jié)構(gòu)如表1所示，其中需要記錄的參數(shù)有6個(gè)：對應(yīng)的標(biāo)記值、該區(qū)域的x坐標(biāo)最大值Xmax、x坐標(biāo)最小值Xmin、y坐標(biāo)最大值Ymax、y坐標(biāo)最小值Ymin以及該區(qū)域的面積。

表1參數(shù)存儲器結(jié)構(gòu)Table 1.Memory data structure

在圖像順序標(biāo)定的同時(shí)，需要對標(biāo)記值參數(shù)存儲器進(jìn)行更新操作。當(dāng)在標(biāo)記過程中遇到一個(gè)坐標(biāo)為(x,y)像素點(diǎn)時(shí)，若該點(diǎn)不和鄰域連通，則為一個(gè)新的臨時(shí)標(biāo)記值，令該像素點(diǎn)的標(biāo)記值對應(yīng)的參數(shù)存儲器中的Xmax=Xmin=x，Ymax=Ymin=y，面積置為1。當(dāng)遇到的臨時(shí)標(biāo)記值出現(xiàn)過時(shí)，將面積加1，同時(shí)將該點(diǎn)的x、y坐標(biāo)值和參數(shù)存儲器中對應(yīng)的值比較后更新。當(dāng)出現(xiàn)兩個(gè)臨時(shí)標(biāo)記值的區(qū)域合并，且該兩個(gè)臨時(shí)標(biāo)記值都大于2時(shí)，進(jìn)行標(biāo)記參數(shù)存儲器的合并。將兩個(gè)臨時(shí)標(biāo)記值對應(yīng)參數(shù)存儲器中的面積相加，x,y最值相比較更新后都存入數(shù)值較小的臨時(shí)標(biāo)記值對應(yīng)的參數(shù)存儲器中。

1.3 等價(jià)表整理模塊

圖像標(biāo)定結(jié)束時(shí)會給出等價(jià)表整理開始信號，同時(shí)新建一個(gè)輸出表L1，此時(shí)記錄需要輸出的臨時(shí)標(biāo)記值，以及一個(gè)初始為1的最終標(biāo)記值sum。從地址0開始讀等價(jià)表L中的值，每當(dāng)?shù)刂泛妥x出的數(shù)據(jù)相等時(shí)，將該臨時(shí)標(biāo)記值寫入原先的地址中，然后處理下一個(gè)地址；如果讀出數(shù)據(jù)小于地址，那么將該數(shù)據(jù)當(dāng)做新的地址，再次讀取。重復(fù)這個(gè)操作，直到所有地址都處理完成。在這個(gè)過程中，每次出現(xiàn)地址和讀出數(shù)據(jù)相等的情況時(shí)，若滿足輸出表L1更新條件，則將該臨時(shí)標(biāo)記值寫入L1[sum]，同時(shí)最終標(biāo)記值sum加1。輸出表L1更新條件為：該臨時(shí)標(biāo)記值大于L1[sum-1]且大于2，對應(yīng)的參數(shù)存儲器中面積大于500。

2 FPGA實(shí)驗(yàn)

為了驗(yàn)證該算法的實(shí)際效果，采用Xilinx的Spartan-6系列XC6SLX45芯片，將待處理的二值圖像通過PC輸入到FPGA，經(jīng)過處理后再將結(jié)果輸出回PC端以方便顯示與分析。需要注意的是，本算法針對的目標(biāo)圖像有一定的局限性：(1)目標(biāo)透鏡需要盡可能不出現(xiàn)在第1行、第M行、第1列和第N列；(2)目標(biāo)需要在特定光照條件下生成具有環(huán)形輪廓的目標(biāo)。

選擇圖6中二值圖像(a)為待處理圖像，大小為1 280×1 024。整個(gè)過程一共形成了254個(gè)臨時(shí)標(biāo)記，經(jīng)過等價(jià)表處理和虛假目標(biāo)剔除，最終只剩下4個(gè)最終標(biāo)記進(jìn)行輸出。圖6(b)是經(jīng)過標(biāo)記后的圖像，其中白色區(qū)域是臨時(shí)標(biāo)記值大于2的像素點(diǎn)。

經(jīng)過等價(jià)表整理后，sum=4，因此輸出L1中地址1到地址4對應(yīng)臨時(shí)標(biāo)記值的參數(shù)存儲器。表2是輸出表L1記錄的數(shù)值。表3是4個(gè)對應(yīng)參數(shù)存儲器輸出的數(shù)據(jù)。

表3臨時(shí)標(biāo)記值以及對應(yīng)的參數(shù)Table 3.Temporary markup value and corresponding parameters

在初次標(biāo)記后的圖像的基礎(chǔ)上，利用統(tǒng)計(jì)出來的每個(gè)區(qū)域x和y的最值所形成的外接矩形在每個(gè)區(qū)域外都畫一個(gè)方框，結(jié)果如圖7所示?？梢钥闯鲆还部虺隽?個(gè)區(qū)域，且這4個(gè)區(qū)域分別對應(yīng)二值圖像中目標(biāo)的內(nèi)部輪廓，完成了多個(gè)目標(biāo)透鏡分離。整個(gè)電路的工作時(shí)間為1 280×1 024×2+254×2個(gè)電路時(shí)鐘周期，對比文獻(xiàn)[8,16]中的實(shí)現(xiàn)方法，對該圖像標(biāo)記的工作周期是1 280×1 024×4，本算法消耗的時(shí)間更少。

3 結(jié)束語

連通域標(biāo)記是圖像處理的重要部分，本文設(shè)計(jì)了面向環(huán)形目標(biāo)的連通域標(biāo)記算法，在單次連通域掃描的過程中，通過在圖像的4個(gè)邊框處做一個(gè)特殊的標(biāo)記值，提取出具有環(huán)形輪廓的目標(biāo)內(nèi)部輪廓所包含的區(qū)域，實(shí)現(xiàn)了將緊挨在一起的透鏡目標(biāo)分離開的目的。該算法運(yùn)算速度較快且結(jié)構(gòu)簡單，已經(jīng)被應(yīng)用在了多目標(biāo)透鏡的定位和凹凸面的識別系統(tǒng)上。