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

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

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

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

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