《電子技術應用》
您所在的位置:首頁 > 可編程邏輯 > 設計應用 > 邊緣圖像連通區(qū)域標記的算法研究和SoPC實現(xiàn)
邊緣圖像連通區(qū)域標記的算法研究和SoPC實現(xiàn)
來源:電子技術應用2011年第3期
謝昭莉,彭 琴,白穎杰
重慶大學 自動化學院,重慶400030
摘要: 針對二值邊緣圖像目標點較少的特點,提出了基于目標像素鄰域的8方向生長區(qū)域標記算法。該算法充分利用了邊緣圖像的走向信息,提高了搜索效率,降低了堆??臻g消耗,消除了鄰域反復掃描問題。
中圖分類號: TP391.41
文獻標識碼: A
文章編號: 0258-7998(2011)03-0035-03
Algorithm research and SoPC implementation of connected component labeling of edge image
Xie Zhaoli,Peng Qin,Bai Yingjie
College of Automation, Chongqing University, Chongqing 400030,China
Abstract: For binary edge image has less target pixels, an 8-directions growth region labeling algorithm based on target pixel’s neighborhood is proposed. This algorithm makes full use of the edge image’s tendency information, improves search efficiency, reduces the consumption of stack space, and eliminates the neighborhood repeatedly scanning problem.
Key words : connected component labeling;edge image;region growth;region merge;SoPC


    連通區(qū)域標記算法用于從圖像中提取目標區(qū)域,并計算目標區(qū)域的特征參數(shù),是目標檢測和目標識別的關鍵步驟[1],其在工業(yè)檢測、光學字符識別、機器人目標跟蹤等領域有廣泛的應用。
    目前的連通區(qū)域標記算法中,基于等價標號的標記算法需要至少掃描圖像兩次,并且要處理標記沖突問題,其執(zhí)行時間過于依賴連通區(qū)域的復雜程度[2]。而基于區(qū)域生長的標記算法只需掃描圖像一次,沒有標記沖突問題,對復雜圖像適應性好,但目標點數(shù)多時搜索效率低,堆??臻g消耗大。
    本文所標記的圖像是經(jīng)過邊緣檢測得的二值邊緣圖像。相對于原始圖像(或其二值圖像),邊緣圖像保留了輪廓信息,目標點數(shù)大大減小,適合使用區(qū)域生長標記算法。但是,現(xiàn)有的區(qū)域生長標記算法一方面需要對每一個目標點進行N×N窗口搜索,搜索效率低并會出現(xiàn)同一像素重復掃描現(xiàn)象;另一方面,如果搜索窗口較?。ㄈ缱畛S玫?×3,也稱8鄰域),雖然干擾少,但是同一個連通區(qū)很容易被標記成若干個不同的連通區(qū);而如果增大搜索窗口(如7×7),雖然得到的標記圖像連通性好,但是會引入較多干擾點。
1 基于生長算法的區(qū)域標記
    像素P的上、下、左、右、左上、左下、右上、右下的像素集合為像素P的8鄰域,鄰域內(nèi)所有目標點同屬于一個連通區(qū)。通常采用8鄰域生長法則進行連通區(qū)域標記。
1.1 8鄰域區(qū)域生長算法
    設邊緣圖像的背景像素為255,目標像素為0,對其進行8鄰域區(qū)域生長標記的步驟如下:
    (1)按從上到下、從左到右的順序掃描圖像,遇到目標像素P時,標記為新的標記值L;
    (2)以P為種子點,將其8鄰域內(nèi)的目標像素標記為L;
    (3)將所有與L像素8鄰域內(nèi)相鄰的目標像素標記為L,直到該連通區(qū)域標記完畢;
    (4)繼續(xù)按順序掃描圖像,重復前三步,直到圖像中所有目標像素都標記完畢。
    每個連通區(qū)域的起始點是按順序掃描整個圖像得到的,而各個連通區(qū)域的標記過程是遞歸調(diào)用生長函數(shù)的過程。生長函數(shù)依次掃描目標點的8鄰域,若遇到新的目標點,則將當前目標點的處理過程壓棧,轉(zhuǎn)而掃描新目標點的8鄰域,如此不斷地將目標點壓棧。當某一目標點的8鄰域內(nèi)沒有新的目標點,則將其彈棧,當所有目標點都彈棧完畢,則該連通區(qū)域標記完畢。
1.2 鄰域重復掃描問題
    在圖1中,P0的8鄰域和P1、P2、P3、P4的8鄰域有4個像素的重疊,與P5、P6、P7、P8的8鄰域有2個像素的重疊。按上述的8鄰域區(qū)域生長算法,當P0與P4均為目標點時(設遞歸過程由P0 向P4傳遞),P0、P1、P8、P3、P7這5個像素點被掃描了2次;當P0與P5均為目標點時(設遞歸過程由P0 向P5傳遞),P0、P1、P2這3個像素點被掃描了2次。
1.3 8方向鄰域生長算法
    8方向鄰域生長算法的思路是:目標點A和目標點B相鄰,從A到B有8個方向,當按某個方向從A傳遞到B的8鄰域搜索時,只搜索B的8鄰域中未被A的8鄰域覆蓋的部分。例如,圖1中從P0傳遞到P4的8鄰域搜索時,只搜索P18、P04、P37;從P0傳遞到P5的8鄰域搜索時,只搜索P05、P25、P01、P15、P02。即:

    8方向鄰域生長算法由9個生長函數(shù)組成。對于連通區(qū)域的起點,必須搜索8個方向,此時調(diào)用主生長函數(shù)。在目標點傳遞的過程中,按其傳遞方向,按式(1)調(diào)用相應的生長函數(shù)搜索鄰域點。區(qū)域標記從起點調(diào)用主生長函數(shù)開始,過程是8個生長函數(shù)互相調(diào)用,最后這些函數(shù)都返回時,區(qū)域標記完畢。
    該方法充分利用了從目標點A到目標點B的方向信息,從而在搜索B的鄰域時,搜索個數(shù)降低為原來的3/8或5/8,平均效率提高了50%。
1.4 邊緣端點與區(qū)域合并
    僅用8鄰域搜索連通區(qū),往往得到的連通區(qū)域并不完整,連通性不好。圖2(a)中,右半部分是圓形左下局部放大圖。當按逆時針搜索到圖中圓圈標識的“11”時,在其8鄰域內(nèi)沒有新的目標點,因此也就和區(qū)域“15”斷開了。當搜索到某個目標點時,其8鄰域內(nèi)沒有新的目標點,則該點就是邊緣的“末端”。一個區(qū)域可能有多個末端。
    在圖2(b)中,右半部分是“米”字中心局部放大圖。圖中圓圈標識的“4”點,其8鄰域內(nèi)有新的目標點(左下點),但最近的“3”點并不在其鄰域內(nèi),因此兩個連通區(qū)斷開。對于單個像素寬的邊緣圖像,其走向基本一致;而走向改變較大的點,就是圖形的“拐點”,此時容易出現(xiàn)區(qū)域斷開的現(xiàn)象。


    圖1中,假設三個目標點的傳遞順序是P0到P5,P5再到P02,則P5就是走向拐點。
    要改善連通性,可以增大搜索范圍,如增大到7×7范圍。這樣雖然在一定程度上改善了連通性,但是會引入更多的干擾點。而本文的思路是:首先按照上述8方向鄰域生長算法搜索連通區(qū)域,同時記錄邊緣“端點”,然后通過比較各個區(qū)域的端點,將端點較近的兩個區(qū)域合并。結(jié)合前文的分析,本文認為邊緣端點包括3類:區(qū)域起點;邊緣末端;邊緣拐點。這樣得到的端點個數(shù)少,包含了絕大部分的“斷點”。通過不斷比較各個區(qū)域的端點,相近則將區(qū)域合并,最終得到合并后的標記圖像。
    該方法實質(zhì)上是在小尺度內(nèi)搜索連通區(qū),并利用得到的邊緣端點在大尺度內(nèi)進行區(qū)域合并,既不引入更多的雜點,又改善了標記圖像的連通性,并在保證區(qū)域合并正確率的同時,提高了合并效率。
2 區(qū)域標記及合并的SoPC實現(xiàn)
    本文以FPGA為核心,利用SoPC技術,實現(xiàn)了對320×240圖像的8方向生長連通區(qū)域標記。系統(tǒng)使用FPGA邏輯硬件進行邊緣檢測[3],使用NiosII軟核處理器進行連通區(qū)域標記,用Avalon總線將兩者結(jié)合起來,實現(xiàn)了硬件加速,軟硬件協(xié)同工作,既提高了實時性又保證了靈活性。
2.1 SoPC系統(tǒng)的結(jié)構設計
    系統(tǒng)結(jié)構圖如圖3所示,主要模塊的功能簡述如下:
    (1)NiosII CPU模塊。該模塊是整個系統(tǒng)運算和調(diào)度的中心,完成系統(tǒng)工作流程的控制;圖像處理中區(qū)域標記和區(qū)域合并算法的實現(xiàn);圖形用戶接口(GUI)的實現(xiàn)。
    (2)Image模塊。圖像采集部分負責按照320×240大小采集攝像頭的數(shù)據(jù),由DMA控制器通過Avalon總線將原始圖像數(shù)據(jù)存儲到DDR SDRAM中。邊緣檢測部分同步地將原始圖像數(shù)據(jù)邊緣化,生成邊緣圖像數(shù)據(jù),并通過DMA控制器和Avalon總線存儲到DDR SDRAM中。
    (3)Display模塊。負責驅(qū)動LCD液晶顯示屏顯示原始圖像、標記圖像以及處理信息。

2.2 區(qū)域標記及合并的算法實現(xiàn)
      圖像處理過程分為連通區(qū)域標記、區(qū)域合并和區(qū)域排序三步。
      (1)連通區(qū)域標記:按照改進后的8方向鄰域生長算法進行連通區(qū)域標記,為每個連通區(qū)分配一個鏈表數(shù)組元素,用鏈表記錄該連通區(qū)的目標點和端點。
      (2)區(qū)域合并:逐個比較任意兩個連通區(qū)域的端點鏈表,在大尺度范圍內(nèi)(本文采用9×9范圍),若其中有相鄰的端點,則合并這兩個連通區(qū)。
      (3)區(qū)域排序:按照目標點的個數(shù),從大到小對合并后的連通區(qū)域排序,取前N個目標點數(shù)大于X的連通區(qū)域作為后續(xù)特征提取的對象(本文N的最大取值為10,X取值20),其余的視為干擾去掉。取形狀較大的N個連通區(qū)進行下一步的特征提取,可以節(jié)省處理時間。
3 實驗結(jié)果及分析
    本文使用Altera公司的高性價比CycloneIII系列的FPGA EP3C25F324C8。SoPC系統(tǒng)共用邏輯單元8916/24624(36%),寄存器5 415個,引腳101個,片內(nèi)SRAM位數(shù)421 248/608 256(69%),內(nèi)置乘法器4個,PLL鎖相環(huán)1個。系統(tǒng)時鐘為100 MHz,NiosII軟核處理器的性能為113 DMIPS。
    實驗結(jié)果如圖4所示。圖4(a)為實驗用開發(fā)板和攝像頭,圖4(b)、(c)、(d)是不同圖像在LCD液晶屏上顯示的實驗結(jié)果。顯示分為三部分:左側(cè)上部為原始灰度圖像,大小為320×240;左側(cè)下部為標記圖像(不同區(qū)域由不同顏色顯示),大小為320×240;右側(cè)為處理信息,大小為480×480。處理信息包括:Connection Num為連通區(qū)域個數(shù);Merge Num為合并后的區(qū)域數(shù);Region Num為排序后的區(qū)域數(shù);Process Time為圖像處理時間,單位為ms。

    實驗結(jié)果表明,本文算法得出的標記圖像結(jié)果正確、邊緣清晰、去掉了雜點、提高了區(qū)域的連通性。在SoPC系統(tǒng)上實現(xiàn)時,對復雜圖像的處理速度約30幀/s,滿足了實時性要求。
    本文在SoPC系統(tǒng)中,將提出的基于目標像素鄰域的8方向生長區(qū)域標記算法和基于邊緣端點的區(qū)域合并算法成功地予以實現(xiàn)。實驗結(jié)果表明了算法的有效性和實時性?;赟oPC技術的圖像處理系統(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圖像邊緣檢測及邊緣細化的FPGA實現(xiàn)[J].電子技術應用,2010,36(6):39-42.

此內(nèi)容為AET網(wǎng)站原創(chuàng),未經(jīng)授權禁止轉(zhuǎn)載。