連通區域標記算法用于從圖像中提取目標區域，并計算目標區域的特征參數，是目標檢測和目標識別的關鍵步驟[1]，其在工業檢測、光學字符識別、機器人目標跟蹤等領域有廣泛的應用。
    目前的連通區域標記算法中，基于等價標號的標記算法需要至少掃描圖像兩次，并且要處理標記沖突問題，其執行時間過于依賴連通區域的復雜程度[2]。而基于區域生長的標記算法只需掃描圖像一次，沒有標記沖突問題，對復雜圖像適應性好，但目標點數多時搜索效率低，堆棧空間消耗大。
    本文所標記的圖像是經過邊緣檢測得的二值邊緣圖像。相對于原始圖像（或其二值圖像），邊緣圖像保留了輪廓信息，目標點數大大減小，適合使用區域生長標記算法。但是，現有的區域生長標記算法一方面需要對每一個目標點進行N×N窗口搜索，搜索效率低并會出現同一像素重復掃描現象；另一方面，如果搜索窗口較小（如最常用的3×3，也稱8鄰域），雖然干擾少，但是同一個連通區很容易被標記成若干個不同的連通區；而如果增大搜索窗口（如7×7），雖然得到的標記圖像連通性好，但是會引入較多干擾點。
1 基于生長算法的區域標記
    像素P的上、下、左、右、左上、左下、右上、右下的像素集合為像素P的8鄰域，鄰域內所有目標點同屬于一個連通區。通常采用8鄰域生長法則進行連通區域標記。
1.1 8鄰域區域生長算法
    設邊緣圖像的背景像素為255，目標像素為0，對其進行8鄰域區域生長標記的步驟如下：
    (1)按從上到下、從左到右的順序掃描圖像，遇到目標像素P時，標記為新的標記值L；
    (2)以P為種子點，將其8鄰域內的目標像素標記為L；
    (3)將所有與L像素8鄰域內相鄰的目標像素標記為L，直到該連通區域標記完畢；
    (4)繼續按順序掃描圖像，重復前三步，直到圖像中所有目標像素都標記完畢。
    每個連通區域的起始點是按順序掃描整個圖像得到的，而各個連通區域的標記過程是遞歸調用生長函數的過程。生長函數依次掃描目標點的8鄰域，若遇到新的目標點，則將當前目標點的處理過程壓棧，轉而掃描新目標點的8鄰域，如此不斷地將目標點壓棧。當某一目標點的8鄰域內沒有新的目標點，則將其彈棧，當所有目標點都彈棧完畢，則該連通區域標記完畢。
1.2 鄰域重復掃描問題
    在圖1中，P0的8鄰域和P1、P2、P3、P4的8鄰域有4個像素的重疊，與P5、P6、P7、P8的8鄰域有2個像素的重疊。按上述的8鄰域區域生長算法，當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個生長函數組成。對于連通區域的起點，必須搜索8個方向，此時調用主生長函數。在目標點傳遞的過程中，按其傳遞方向，按式(1)調用相應的生長函數搜索鄰域點。區域標記從起點調用主生長函數開始，過程是8個生長函數互相調用，最后這些函數都返回時，區域標記完畢。
    該方法充分利用了從目標點A到目標點B的方向信息，從而在搜索B的鄰域時，搜索個數降低為原來的3/8或5/8，平均效率提高了50%。
1.4 邊緣端點與區域合并
    僅用8鄰域搜索連通區，往往得到的連通區域并不完整，連通性不好。圖2(a)中，右半部分是圓形左下局部放大圖。當按逆時針搜索到圖中圓圈標識的“11”時，在其8鄰域內沒有新的目標點，因此也就和區域“15”斷開了。當搜索到某個目標點時，其8鄰域內沒有新的目標點，則該點就是邊緣的“末端”。一個區域可能有多個末端。
    在圖2(b)中，右半部分是“米”字中心局部放大圖。圖中圓圈標識的“4”點，其8鄰域內有新的目標點（左下點），但最近的“3”點并不在其鄰域內，因此兩個連通區斷開。對于單個像素寬的邊緣圖像，其走向基本一致；而走向改變較大的點，就是圖形的“拐點”，此時容易出現區域斷開的現象。

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

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

    實驗結果表明，本文算法得出的標記圖像結果正確、邊緣清晰、去掉了雜點、提高了區域的連通性。在SoPC系統上實現時，對復雜圖像的處理速度約30幀/s，滿足了實時性要求。
    本文在SoPC系統中，將提出的基于目標像素鄰域的8方向生長區域標記算法和基于邊緣端點的區域合并算法成功地予以實現。實驗結果表明了算法的有效性和實時性。基于SoPC技術的圖像處理系統，軟硬件協同工作，提高了系統的并行性和靈活性，便攜性好，成本低。
參考文獻
[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實現[J].電子技術應用，2010，36(6)：39-42.