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

    連通域標(biāo)記算法是圖像處理、計算機(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)記算法難以采用硬件實現(xiàn)，一般都采用軟件編程的方式在PC機(jī)上實現(xiàn)，處理速度較慢，占用資源多?；谙袼氐倪B通域標(biāo)記采用軟件實現(xiàn)速度較慢，適于硬件實現(xiàn)。針對FPGA的特點(diǎn)，提出了一種適于FPGA實現(xiàn)的連通域快速標(biāo)記的方法。在33 MHz工作時鐘下，單片F(xiàn)PGA能夠完成1 000 f／s的128×128的二值圖像標(biāo)記，處理速度能夠滿足實時系統(tǒng)要求。

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

    采用2×2的窗口進(jìn)行逐行掃描的方式對二值圖像的逐個像素進(jìn)行臨時標(biāo)記，掃描窗口如圖2所示。圖2中：P為當(dāng)前像素；U為當(dāng)前像素上一行像素對應(yīng)的標(biāo)記；L為其左邊像素標(biāo)記；P的臨時標(biāo)記記為PL；當(dāng)前標(biāo)記最大值記為LN。臨時標(biāo)記方法如下：
    (1)如果當(dāng)前像素P不為零：如果L和U只有一個不為零，則復(fù)制此標(biāo)記給PL；如果L和U均不為零且相同則復(fù)制此標(biāo)記給PL；如果L和U均為零，則分配一個新的標(biāo)記LN+1給PL；如果L和U均不為零但不相同，則復(fù)制其中較小一個給PL，并將L和U，存入等價表中。如圖3所示。
    (2)如果當(dāng)前像素P為零則PL為零。
1．2 等價關(guān)系合并
    在第一次掃描過程中，在對像素臨時標(biāo)記的同時對等價表進(jìn)行合并。等價表合并按照等價表的存儲順序以較大值為索引的鏈表循環(huán)查找的方式進(jìn)行合并，合并后的等價關(guān)系存儲到新的等價表中。以圖3所示的等價表合并為例來說明等價表合并過程。圖3中，第一行為等價關(guān)系存儲的順序；第二、三行分別為等價關(guān)系的索引值和等價值。其中，a>b>0，a>d>0，b>c>0。等表合并步驟如下：
    (1)首先以a為索引在新的等價表中查找a所對應(yīng)等價值，查得a沒有對應(yīng)值，因此將較大值a為索引，b為等價值存入新的等價表。同理，b，c也存入了新的等價表。
    (2)合并等價關(guān)系a，d時：
    ①若b=d，則不存入等價表，合并下一個等價關(guān)系。
    ②若b<d，則以d為索引在當(dāng)前新等價表中查找d對應(yīng)等價值，查得d沒有對應(yīng)關(guān)系，從而將d為索引，b為等價值存入新等價表。
    ③若b>d，則將d替代a的等價值b，然后以b為索引查找得到其對應(yīng)值c，比較c，d大小。若c<d，則以d為索引在當(dāng)前新等價表中查找，查得d沒有對應(yīng)關(guān)系，從而將d為索引，c為等價值存入新等價表。若c>d，則將d替代b的等價值c，然后以c為索引查找，查得c沒有對應(yīng)關(guān)系，從而將c為索引，d為等價值存入新等價表。若c=d，則不存入等價表，合并下一個等價關(guān)系。
1．3 鏈表歸并
    等價表合并完成后，從1到臨時標(biāo)記的最大值按照從小到大的順序依次進(jìn)行歸并。以當(dāng)前合并值為索引對合并后的新等價表進(jìn)行查找，如果沒有對應(yīng)等價值，則將其本身作為其等價值存入新的等價鏈表；如果查得其對應(yīng)等價值為M，則繼續(xù)以M為索引對當(dāng)前新的等價鏈表查找，查得M對應(yīng)值為P；若P為不零，則將P作為當(dāng)前合并值的等價值存入新的等價鏈表；否則，就將M作為當(dāng)前合并值的等價值存入新的等價鏈表。
1．4 順序合并
    圖像進(jìn)行第二次掃描時，利用像素的臨時標(biāo)記值為索引在等價鏈表中查找其對應(yīng)值，經(jīng)過歸并后輸出以自然數(shù)順序的標(biāo)記的圖像。第二次掃描過程中，如果第一個臨時標(biāo)記X1對應(yīng)值Q1不為零時，以1替代X1；如果第二個臨時標(biāo)記X2對應(yīng)值Q2不為零時，若Q2不等于Q1，則以2替代X2，否則以1替代X2。依此類推，當(dāng)?shù)趎個臨時標(biāo)記Xn對應(yīng)值Qn不為零時，若Qn=Qm，則以m替代Xn；若Qn≠Qm(0<m<n)，則以n替代Xn。
1．5 算法特點(diǎn)分析
    本文算法主要是針對FPGA流水線和并行處理的特點(diǎn)而提出的。利用FPGA實現(xiàn)時的運(yùn)算復(fù)雜度優(yōu)于文獻(xiàn)。采用FPGA實現(xiàn)該算法需要總時鐘周期小于2×N×M，N為圖像行數(shù)，M為列數(shù)。
    算法利用FPGA的特點(diǎn)主要體現(xiàn)在：圖像標(biāo)記過程中同時對等價關(guān)系進(jìn)行合并，在FPGA實現(xiàn)時圖像標(biāo)記和等價關(guān)系合并可以并行執(zhí)行，減少了整個過程的處理時間；臨時標(biāo)記和順序合并采用了流水線方式進(jìn)行，減少了處理等待時間，能較快輸出圖像；鏈表歸并和順序合并單元采用高于臨時標(biāo)記和等價關(guān)系合并單元時鐘頻率，既體現(xiàn)了并行處理特性又提高了處理速度。

2 硬件實現(xiàn)方案
    該設(shè)計采用單片F(xiàn)PGA來實現(xiàn)上述連通域快速標(biāo)記算法，標(biāo)記處理單元均利用FPGA片內(nèi)資源，不需要其他外部單元，縮小了硬件體積，電路結(jié)構(gòu)簡單，節(jié)約了硬件資源、易于實現(xiàn)。該算法實現(xiàn)過程采用VHDL編程的方式在FPGA上實現(xiàn)。硬件實現(xiàn)框圖如圖4所示。

    標(biāo)記單元采用流水線的方式對二值圖像逐個像素進(jìn)行標(biāo)記。采用FPGA內(nèi)部的FIFO存儲1行已標(biāo)記像素的標(biāo)記值來實現(xiàn)2×2的掃描窗口。標(biāo)記單元結(jié)構(gòu)如圖5所示。圖像經(jīng)標(biāo)記單元處理后，將像素的標(biāo)記值Label_value存儲到圖像存儲單元中，等價關(guān)系Eq_valuel，Eq_value2存儲到等價表中。圖像存儲、等價表合并和鏈表歸并三個處理單元都是采用對雙口RAM的讀／寫操作來實現(xiàn)。處理單元流程圖如圖6所示。圖像存儲單元采用兩個雙口RAM乒乓操作來實現(xiàn)，分別為RAMa和RAMb，每個雙口RAM單獨(dú)存儲一幀圖像像素臨時標(biāo)記。在圖像的標(biāo)記過程中，像素的臨時標(biāo)記值實時的存儲到RAMa或RAMb中。等價表存儲采用一個異步的雙口RAMc作為緩存，將標(biāo)記輸出的等價關(guān)系Eq_valuel，Eq_value2中較大值作為高位，較小值作為低位合并后按順序存儲到RAMc中。存儲的同時，從另一個端口讀取RAMc中存儲的等價關(guān)系，進(jìn)行等價表合并。等價表合并過程中，將等價關(guān)系中較大值作為地址，較小值作為數(shù)據(jù)存儲到異步雙口RAMd中。鏈表歸并采用兩個雙口RAM進(jìn)行乒乓操作，分別為RAMe和RAMf。每個RAM存儲1幀圖像標(biāo)記后的歸并鏈表值。RAMe和RAMf存儲的圖像鏈表分別與RAMa和RAMb存儲的像素標(biāo)記相對應(yīng)。順序合并主要采用寄存器和比較器來實現(xiàn)。利用寄存器存儲經(jīng)等價鏈表處理后圖像非零像素的不同的標(biāo)記，然后通過比較器進(jìn)行判斷處理，最后以自然數(shù)順序的標(biāo)記替代像素的標(biāo)記。

3 FPGA實驗結(jié)果
    為了能夠仿真該算法的硬件可實現(xiàn)性和正確性，利用Matlab 7．1和ModelSim 6．5a進(jìn)行混合仿真。通過利用Simulink中Link for ModelSim模塊建立Matlab和ModelSim混合仿真的VHDL協(xié)同仿真模型，如圖7所示。

    通過Matlab讀入1幅128×128的二值圖像，經(jīng)VHDL Cosimulation處理后，存到Matlab的工作窗口。然后，通過Matlab把圖像數(shù)據(jù)還原成圖像矩陣顯示出來，仿真結(jié)果如圖8所示。采用XIUNX的ML506開發(fā)板對本文的算法進(jìn)行了驗證，在33 MHz工作時鐘下，單片F(xiàn)PGA能完成1 000 f／s的128×128的二值圖像標(biāo)記。實驗結(jié)果表明本文提出的適于FPGA實現(xiàn)的二值圖像連通域快速標(biāo)記算法能滿足實時性要求。

4 結(jié)語
    圖像連通域標(biāo)記是目標(biāo)跟蹤與識別圖像處理系統(tǒng)中的重要環(huán)節(jié)。由于圖像的數(shù)據(jù)運(yùn)算量大，利用軟件來實現(xiàn)難以滿足系統(tǒng)的實時性。本文介紹的適于FPGA實現(xiàn)的連通域快速標(biāo)記算法能夠?qū)Χ祱D像以自然數(shù)順序?qū)D像連通區(qū)域進(jìn)行快速標(biāo)記。軟件仿真和硬件實現(xiàn)結(jié)果表明，本文介紹的連通域快速標(biāo)記算法能夠?qū)Υ嬖趶?fù)雜連通關(guān)系的二值圖像進(jìn)行正確標(biāo)記。該設(shè)計只采用單片FPGA實現(xiàn)，電路結(jié)構(gòu)簡單，大大節(jié)約了硬件資源，體積小，易于實現(xiàn)。對于較大的圖像的連通域快速標(biāo)記，只需在FPGA外接存儲器就能夠?qū)崿F(xiàn)。