基于SoPC的邊緣圖像連通區(qū)域標(biāo)記的算法

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

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

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

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

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

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

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

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

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

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

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

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

　　1.3 8方向鄰域生長(zhǎng)算法

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

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