基于FPGA的二值圖像連通域快速標(biāo)記

摘要：針對連通域標(biāo)記算法運(yùn)算量大、速度慢、硬件實(shí)現(xiàn)困難的缺點(diǎn)，提出一種適于現(xiàn)場可編程邏輯門陣列(FPGA)實(shí)現(xiàn)的二值圖像連通域快速標(biāo)記的算法，并用VHDL硬件開發(fā)語言在XILINX公司的FPGA上實(shí)現(xiàn)。實(shí)驗(yàn)結(jié)果表明了該算法能對二值圖像復(fù)雜的連通關(guān)系正確標(biāo)記，易于硬件實(shí)現(xiàn)，大大節(jié)約了硬件資源，電路結(jié)構(gòu)簡單，滿足實(shí)時(shí)性要求。
關(guān)鍵詞：FPGA；二值圖像；連通域；快速標(biāo)記

連通域標(biāo)記算法是圖像處理、計(jì)算機(jī)視覺和模式識別等領(lǐng)域的基本算法，它可以對圖像中不同目標(biāo)標(biāo)上不同的標(biāo)記，進(jìn)而提取、分離目標(biāo)，確定目標(biāo)的特征和參數(shù)，從而對目標(biāo)進(jìn)行識別和跟蹤。連通域標(biāo)記算法廣泛應(yīng)用于軍事目標(biāo)跟蹤、工業(yè)產(chǎn)品監(jiān)控、交通路口監(jiān)控等場合圖像處理系統(tǒng)中。目前的連通標(biāo)記算法分為兩大類，一是基于像素的連通成分標(biāo)記，另一種就是基于行程的連通成分標(biāo)記算法?；谛谐痰倪B通域標(biāo)記算法難以采用硬件實(shí)現(xiàn)，一般都采用軟件編程的方式在PC機(jī)上實(shí)現(xiàn)，處理速度較慢，占用資源多?；谙袼氐倪B通域標(biāo)記采用軟件實(shí)現(xiàn)速度較慢，適于硬件實(shí)現(xiàn)。針對FPGA的特點(diǎn)，提出了一種適于FPGA實(shí)現(xiàn)的連通域快速標(biāo)記的方法。在33 MHz工作時(shí)鐘下，單片F(xiàn)PGA能夠完成1 000 f／s的128×128的二值圖像標(biāo)記，處理速度能夠滿足實(shí)時(shí)系統(tǒng)要求。

1 標(biāo)記算法
1．1 臨時(shí)標(biāo)記
連通域標(biāo)記對二值圖像采取從左到右，從上到下的方式進(jìn)行兩次掃描。第一次掃描過程中，對像素為一的點(diǎn)標(biāo)記一個(gè)臨時(shí)標(biāo)記，為零的點(diǎn)不標(biāo)記，標(biāo)記完后得到一個(gè)等價(jià)表，合并等價(jià)表形成一個(gè)以較大標(biāo)記值為索引的鏈表；第二次掃描時(shí)，對臨時(shí)標(biāo)記的逐個(gè)像素進(jìn)行替代，最后得到以目標(biāo)出現(xiàn)順序的自然數(shù)順順序的標(biāo)記。二值圖像整個(gè)標(biāo)記處理過程如圖1所示。

采用2×2的窗口進(jìn)行逐行掃描的方式對二值圖像的逐個(gè)像素進(jìn)行臨時(shí)標(biāo)記，掃描窗口如圖2所示。圖2中：P為當(dāng)前像素；U為當(dāng)前像素上一行像素對應(yīng)的標(biāo)記；L為其左邊像素標(biāo)記；P的臨時(shí)標(biāo)記記為PL；當(dāng)前標(biāo)記最大值記為LN。臨時(shí)標(biāo)記方法如下：
(1)如果當(dāng)前像素P不為零：如果L和U只有一個(gè)不為零，則復(fù)制此標(biāo)記給PL；如果L和U均不為零且相同則復(fù)制此標(biāo)記給PL；如果L和U均為零，則分配一個(gè)新的標(biāo)記LN+1給PL；如果L和U均不為零但不相同，則復(fù)制其中較小一個(gè)給PL，并將L和U，存入等價(jià)表中。如圖3所示。
(2)如果當(dāng)前像素P為零則PL為零。