邊緣圖像連通區域標記的算法研究和SoPC實(shí)現

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