邊緣圖像連通區(qū)域標(biāo)記的算法研究和SoPC實(shí)現(xiàn)

謝昭莉，彭琴，白穎杰

(重慶大學(xué)自動(dòng)化學(xué)院，重慶400030)

連通區(qū)域標(biāo)記算法用于從圖像中提取目標(biāo)區(qū)域，并計(jì)算目標(biāo)區(qū)域的特征參數(shù)，是目標(biāo)檢測(cè)和目標(biāo)識(shí)別的關(guān)鍵步驟[1]，其在工業(yè)檢測(cè)、光學(xué)字符識(shí)別、機(jī)器人目標(biāo)跟蹤等領(lǐng)域有廣泛的應(yīng)用。

目前的連通區(qū)域標(biāo)記算法中，基于等價(jià)標(biāo)號(hào)的標(biāo)記算法需要至少掃描圖像兩次，并且要處理標(biāo)記沖突問題，其執(zhí)行時(shí)間過于依賴連通區(qū)域的復(fù)雜程度[2]。而基于區(qū)域生長的標(biāo)記算法只需掃描圖像一次，沒有標(biāo)記沖突問題，對(duì)復(fù)雜圖像適應(yīng)性好，但目標(biāo)點(diǎn)數(shù)多時(shí)搜索效率低，堆?？臻g消耗大。

本文所標(biāo)記的圖像是經(jīng)過邊緣檢測(cè)得的二值邊緣圖像。相對(duì)于原始圖像(或其二值圖像)，邊緣圖像保留了輪廓信息，目標(biāo)點(diǎn)數(shù)大大減小，適合使用區(qū)域生長標(biāo)記算法。但是，現(xiàn)有的區(qū)域生長標(biāo)記算法一方面需要對(duì)每一個(gè)目標(biāo)點(diǎn)進(jìn)行N×N窗口搜索，搜索效率低并會(huì)出現(xiàn)同一像素重復(fù)掃描現(xiàn)象；另一方面，如果搜索窗口較小(如最常用的3×3，也稱8鄰域)，雖然干擾少，但是同一個(gè)連通區(qū)很容易被標(biāo)記成若干個(gè)不同的連通區(qū)；而如果增大搜索窗口(如7×7)，雖然得到的標(biāo)記圖像連通性好，但是會(huì)引入較多干擾點(diǎn)。

1 基于生長算法的區(qū)域標(biāo)記

像素P的上、下、左、右、左上、左下、右上、右下的像素集合為像素P的8鄰域，鄰域內(nèi)所有目標(biāo)點(diǎn)同屬于一個(gè)連通區(qū)。通常采用8鄰域生長法則進(jìn)行連通區(qū)域標(biāo)記。

1.1 8鄰域區(qū)域生長算法

設(shè)邊緣圖像的背景像素為255，目標(biāo)像素為0，對(duì)其進(jìn)行8鄰域區(qū)域生長標(biāo)記的步驟如下:

(1)按從上到下、從左到右的順序掃描圖像，遇到目標(biāo)像素P時(shí)，標(biāo)記為新的標(biāo)記值L；

(2)以P為種子點(diǎn)，將其8鄰域內(nèi)的目標(biāo)像素標(biāo)記為L；

(3)將所有與L像素8鄰域內(nèi)相鄰的目標(biāo)像素標(biāo)記為L，直到該連通區(qū)域標(biāo)記完畢；

(4)繼續(xù)按順序掃描圖像，重復(fù)前三步，直到圖像中所有目標(biāo)像素都標(biāo)記完畢。

每個(gè)連通區(qū)域的起始點(diǎn)是按順序掃描整個(gè)圖像得到的，而各個(gè)連通區(qū)域的標(biāo)記過程是遞歸調(diào)用生長函數(shù)的過程。生長函數(shù)依次掃描目標(biāo)點(diǎn)的8鄰域，若遇到新的目標(biāo)點(diǎn)，則將當(dāng)前目標(biāo)點(diǎn)的處理過程壓棧，轉(zhuǎn)而掃描新目標(biāo)點(diǎn)的8鄰域，如此不斷地將目標(biāo)點(diǎn)壓棧。當(dāng)某一目標(biāo)點(diǎn)的8鄰域內(nèi)沒有新的目標(biāo)點(diǎn)，則將其彈棧，當(dāng)所有目標(biāo)點(diǎn)都彈棧完畢，則該連通區(qū)域標(biāo)記完畢。

1.2 鄰域重復(fù)掃描問題

在圖1中，P0的8鄰域和P1、P2、P3、P4的8鄰域有4個(gè)像素的重疊，與P5、P6、P7、P8的8鄰域有2個(gè)像素的重疊。按上述的8鄰域區(qū)域生長算法，當(dāng)P0與P4均為目標(biāo)點(diǎn)時(shí)(設(shè)遞歸過程由P0向P4傳遞)，P0、P1、P8、P3、P7這5個(gè)像素點(diǎn)被掃描了2次；當(dāng)P0與P5均為目標(biāo)點(diǎn)時(shí)(設(shè)遞歸過程由P0向P5傳遞)，P0、P1、P2這3個(gè)像素點(diǎn)被掃描了2次。

1.3 8方向鄰域生長算法

8方向鄰域生長算法的思路是:目標(biāo)點(diǎn)A和目標(biāo)點(diǎn)B相鄰，從A到B有8個(gè)方向，當(dāng)按某個(gè)方向從A傳遞到B的8鄰域搜索時(shí)，只搜索B的8鄰域中未被A的8鄰域覆蓋的部分。例如，圖1中從P0傳遞到P4的8鄰域搜索時(shí)，只搜索P18、P04、P37；從P0傳遞到P5的8鄰域搜索時(shí)，只搜索P05、P25、P01、P15、P02。即:

8方向鄰域生長算法由9個(gè)生長函數(shù)組成。對(duì)于連通區(qū)域的起點(diǎn)，必須搜索8個(gè)方向，此時(shí)調(diào)用主生長函數(shù)。在目標(biāo)點(diǎn)傳遞的過程中，按其傳遞方向，按式(1)調(diào)用相應(yīng)的生長函數(shù)搜索鄰域點(diǎn)。區(qū)域標(biāo)記從起點(diǎn)調(diào)用主生長函數(shù)開始，過程是8個(gè)生長函數(shù)互相調(diào)用，最后這些函數(shù)都返回時(shí)，區(qū)域標(biāo)記完畢。

該方法充分利用了從目標(biāo)點(diǎn)A到目標(biāo)點(diǎn)B的方向信息，從而在搜索B的鄰域時(shí)，搜索個(gè)數(shù)降低為原來的3/8或5/8，平均效率提高了50%。

1.4 邊緣端點(diǎn)與區(qū)域合并

僅用8鄰域搜索連通區(qū)，往往得到的連通區(qū)域并不完整，連通性不好。圖2(a)中，右半部分是圓形左下局部放大圖。當(dāng)按逆時(shí)針?biāo)阉鞯綀D中圓圈標(biāo)識(shí)的“11”時(shí)，在其8鄰域內(nèi)沒有新的目標(biāo)點(diǎn)，因此也就和區(qū)域“15”斷開了。當(dāng)搜索到某個(gè)目標(biāo)點(diǎn)時(shí)，其8鄰域內(nèi)沒有新的目標(biāo)點(diǎn)，則該點(diǎn)就是邊緣的“末端”。一個(gè)區(qū)域可能有多個(gè)末端。

在圖2(b)中，右半部分是“米”字中心局部放大圖。圖中圓圈標(biāo)識(shí)的“4”點(diǎn)，其8鄰域內(nèi)有新的目標(biāo)點(diǎn)(左下點(diǎn))，但最近的“3”點(diǎn)并不在其鄰域內(nèi)，因此兩個(gè)連通區(qū)斷開。對(duì)于單個(gè)像素寬的邊緣圖像，其走向基本一致；而走向改變較大的點(diǎn)，就是圖形的“拐點(diǎn)”，此時(shí)容易出現(xiàn)區(qū)域斷開的現(xiàn)象。

由于8個(gè)方向鄰域生長函數(shù)本身就帶有方向信息，因而可以方便地定義邊緣圖像的走向“拐點(diǎn)”。設(shè)標(biāo)記過程中，由目標(biāo)點(diǎn)Pi傳遞到Pi+1的方向是PiP→i+1，由Pi+1傳遞到Pi+2的方向是Pi+1P→i+2，如果這兩個(gè)方向的夾角為90°，則稱Pi+1為邊緣走向的拐點(diǎn)，即:

圖1中，假設(shè)三個(gè)目標(biāo)點(diǎn)的傳遞順序是P0到P5，P5再到P02，則P5就是走向拐點(diǎn)。

要改善連通性，可以增大搜索范圍，如增大到7×7范圍。這樣雖然在一定程度上改善了連通性，但是會(huì)引入更多的干擾點(diǎn)。而本文的思路是:首先按照上述8方向鄰域生長算法搜索連通區(qū)域，同時(shí)記錄邊緣“端點(diǎn)”，然后通過比較各個(gè)區(qū)域的端點(diǎn)，將端點(diǎn)較近的兩個(gè)區(qū)域合并。結(jié)合前文的分析，本文認(rèn)為邊緣端點(diǎn)包括3類:區(qū)域起點(diǎn)；邊緣末端；邊緣拐點(diǎn)。這樣得到的端點(diǎn)個(gè)數(shù)少，包含了絕大部分的“斷點(diǎn)”。通過不斷比較各個(gè)區(qū)域的端點(diǎn)，相近則將區(qū)域合并，最終得到合并后的標(biāo)記圖像。

該方法實(shí)質(zhì)上是在小尺度內(nèi)搜索連通區(qū)，并利用得到的邊緣端點(diǎn)在大尺度內(nèi)進(jìn)行區(qū)域合并，既不引入更多的雜點(diǎn)，又改善了標(biāo)記圖像的連通性，并在保證區(qū)域合并正確率的同時(shí)，提高了合并效率。

2 區(qū)域標(biāo)記及合并的SoPC實(shí)現(xiàn)

本文以FPGA為核心，利用SoPC技術(shù)，實(shí)現(xiàn)了對(duì)320×240圖像的8方向生長連通區(qū)域標(biāo)記。系統(tǒng)使用FPGA邏輯硬件進(jìn)行邊緣檢測(cè)[3]，使用NiosII軟核處理器進(jìn)行連通區(qū)域標(biāo)記，用Avalon總線將兩者結(jié)合起來，實(shí)現(xiàn)了硬件加速，軟硬件協(xié)同工作，既提高了實(shí)時(shí)性又保證了靈活性。

2.1 SoPC系統(tǒng)的結(jié)構(gòu)設(shè)計(jì)

系統(tǒng)結(jié)構(gòu)圖如圖3所示，主要模塊的功能簡(jiǎn)述如下:

(1)NiosII CPU模塊。該模塊是整個(gè)系統(tǒng)運(yùn)算和調(diào)度的中心，完成系統(tǒng)工作流程的控制；圖像處理中區(qū)域標(biāo)記和區(qū)域合并算法的實(shí)現(xiàn)；圖形用戶接口(GUI)的實(shí)現(xiàn)。

(2)Image模塊。圖像采集部分負(fù)責(zé)按照320×240大小采集攝像頭的數(shù)據(jù)，由DMA控制器通過Avalon總線將原始圖像數(shù)據(jù)存儲(chǔ)到DDR SDRAM中。邊緣檢測(cè)部分同步地將原始圖像數(shù)據(jù)邊緣化，生成邊緣圖像數(shù)據(jù)，并通過DMA控制器和Avalon總線存儲(chǔ)到DDR SDRAM中。

(3)Display模塊。負(fù)責(zé)驅(qū)動(dòng)LCD液晶顯示屏顯示原始圖像、標(biāo)記圖像以及處理信息。

2.2 區(qū)域標(biāo)記及合并的算法實(shí)現(xiàn)

圖像處理過程分為連通區(qū)域標(biāo)記、區(qū)域合并和區(qū)域排序三步。

(1)連通區(qū)域標(biāo)記:按照改進(jìn)后的8方向鄰域生長算法進(jìn)行連通區(qū)域標(biāo)記，為每個(gè)連通區(qū)分配一個(gè)鏈表數(shù)組元素，用鏈表記錄該連通區(qū)的目標(biāo)點(diǎn)和端點(diǎn)。

(2)區(qū)域合并:逐個(gè)比較任意兩個(gè)連通區(qū)域的端點(diǎn)鏈表，在大尺度范圍內(nèi)(本文采用9×9范圍)，若其中有相鄰的端點(diǎn)，則合并這兩個(gè)連通區(qū)。

(3)區(qū)域排序:按照目標(biāo)點(diǎn)的個(gè)數(shù)，從大到小對(duì)合并后的連通區(qū)域排序，取前N個(gè)目標(biāo)點(diǎn)數(shù)大于X的連通區(qū)域作為后續(xù)特征提取的對(duì)象(本文N的最大取值為10，X取值20)，其余的視為干擾去掉。取形狀較大的N個(gè)連通區(qū)進(jìn)行下一步的特征提取，可以節(jié)省處理時(shí)間。

3 實(shí)驗(yàn)結(jié)果及分析

本文使用Altera公司的高性價(jià)比CycloneIII系列的FPGA EP3C25F324C8。SoPC系統(tǒng)共用邏輯單元8916/24624(36%)，寄存器5 415個(gè)，引腳101個(gè)，片內(nèi)SRAM位數(shù)421 248/608 256(69%)，內(nèi)置乘法器4個(gè)，PLL鎖相環(huán)1個(gè)。系統(tǒng)時(shí)鐘為100 MHz，NiosII軟核處理器的性能為113 DMIPS。

實(shí)驗(yàn)結(jié)果如圖4所示。圖4(a)為實(shí)驗(yàn)用開發(fā)板和攝像頭，圖4(b)、(c)、(d)是不同圖像在LCD液晶屏上顯示的實(shí)驗(yàn)結(jié)果。顯示分為三部分:左側(cè)上部為原始灰度圖像，大小為320×240；左側(cè)下部為標(biāo)記圖像(不同區(qū)域由不同顏色顯示)，大小為320×240；右側(cè)為處理信息，大小為480×480。處理信息包括:Connection Num為連通區(qū)域個(gè)數(shù)；Merge Num為合并后的區(qū)域數(shù)；Region Num為排序后的區(qū)域數(shù)；Process Time為圖像處理時(shí)間，單位為ms。

實(shí)驗(yàn)結(jié)果表明，本文算法得出的標(biāo)記圖像結(jié)果正確、邊緣清晰、去掉了雜點(diǎn)、提高了區(qū)域的連通性。在SoPC系統(tǒng)上實(shí)現(xiàn)時(shí)，對(duì)復(fù)雜圖像的處理速度約30幀/s，滿足了實(shí)時(shí)性要求。

本文在SoPC系統(tǒng)中，將提出的基于目標(biāo)像素鄰域的8方向生長區(qū)域標(biāo)記算法和基于邊緣端點(diǎn)的區(qū)域合并算法成功地予以實(shí)現(xiàn)。實(shí)驗(yàn)結(jié)果表明了算法的有效性和實(shí)時(shí)性?；赟oPC技術(shù)的圖像處理系統(tǒng)，軟硬件協(xié)同工作，提高了系統(tǒng)的并行性和靈活性，便攜性好，成本低。

[1]HE Lifeng，CHAO Yuyan，SUZUKI K.Fast connected-component labeling[J].Pattern Recognition，2009，42(9):1977-1987.

[2]HU Qingmao，QIAN Guoyu.Fast connected-component labelling in three-dimensional binary images based on iterative recursion[J].Computer Vision and Image Understanding，2005，99(3):414-434.

[3]謝昭莉，白穎杰.Prewitt圖像邊緣檢測(cè)及邊緣細(xì)化的FPGA實(shí)現(xiàn)[J].電子技術(shù)應(yīng)用，2010，36(6):39-42.