基于FPGA的二值圖像連通域快速標記

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

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

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

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