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

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