基于FPGA的二值圖像連通域快速標(biāo)記
掃描二維碼
隨時(shí)隨地手機(jī)看文章
摘要:針對(duì)連通域標(biāo)記算法運(yùn)算量大、速度慢、硬件實(shí)現(xiàn)困難的缺點(diǎn),提出一種適于現(xiàn)場(chǎng)可編程邏輯門陣列(FPGA)實(shí)現(xiàn)的二值圖像連通域快速標(biāo)記的算法,并用VHDL硬件開發(fā)語(yǔ)言在XILINX公司的FPGA上實(shí)現(xiàn)。實(shí)驗(yàn)結(jié)果表明了該算法能對(duì)二值圖像復(fù)雜的連通關(guān)系正確標(biāo)記,易于硬件實(shí)現(xiàn),大大節(jié)約了硬件資源,電路結(jié)構(gòu)簡(jiǎn)單,滿足實(shí)時(shí)性要求。
關(guān)鍵詞:FPGA;二值圖像;連通域;快速標(biāo)記
連通域標(biāo)記算法是圖像處理、計(jì)算機(jī)視覺和模式識(shí)別等領(lǐng)域的基本算法,它可以對(duì)圖像中不同目標(biāo)標(biāo)上不同的標(biāo)記,進(jìn)而提取、分離目標(biāo),確定目標(biāo)的特征和參數(shù),從而對(duì)目標(biāo)進(jìn)行識(shí)別和跟蹤。連通域標(biāo)記算法廣泛應(yīng)用于軍事目標(biāo)跟蹤、工業(yè)產(chǎn)品監(jiān)控、交通路口監(jiān)控等場(chǎng)合圖像處理系統(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)。針對(duì)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)記對(duì)二值圖像采取從左到右,從上到下的方式進(jìn)行兩次掃描。第一次掃描過程中,對(duì)像素為一的點(diǎn)標(biāo)記一個(gè)臨時(shí)標(biāo)記,為零的點(diǎn)不標(biāo)記,標(biāo)記完后得到一個(gè)等價(jià)表,合并等價(jià)表形成一個(gè)以較大標(biāo)記值為索引的鏈表;第二次掃描時(shí),對(duì)臨時(shí)標(biāo)記的逐個(gè)像素進(jìn)行替代,最后得到以目標(biāo)出現(xiàn)順序的自然數(shù)順順序的標(biāo)記。二值圖像整個(gè)標(biāo)記處理過程如圖1所示。
采用2×2的窗口進(jìn)行逐行掃描的方式對(duì)二值圖像的逐個(gè)像素進(jìn)行臨時(shí)標(biāo)記,掃描窗口如圖2所示。圖2中:P為當(dāng)前像素;U為當(dāng)前像素上一行像素對(duì)應(yīng)的標(biāo)記;L為其左邊像素標(biāo)記;P的臨時(shí)標(biāo)記記為PL;當(dāng)前標(biāo)記最大值記為L(zhǎng)N。臨時(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為零。
1.2 等價(jià)關(guān)系合并
在第一次掃描過程中,在對(duì)像素臨時(shí)標(biāo)記的同時(shí)對(duì)等價(jià)表進(jìn)行合并。等價(jià)表合并按照等價(jià)表的存儲(chǔ)順序以較大值為索引的鏈表循環(huán)查找的方式進(jìn)行合并,合并后的等價(jià)關(guān)系存儲(chǔ)到新的等價(jià)表中。以圖3所示的等價(jià)表合并為例來說明等價(jià)表合并過程。圖3中,第一行為等價(jià)關(guān)系存儲(chǔ)的順序;第二、三行分別為等價(jià)關(guān)系的索引值和等價(jià)值。其中,a>b>0,a>d>0,b>c>0。等表合并步驟如下:
(1)首先以a為索引在新的等價(jià)表中查找a所對(duì)應(yīng)等價(jià)值,查得a沒有對(duì)應(yīng)值,因此將較大值a為索引,b為等價(jià)值存入新的等價(jià)表。同理,b,c也存入了新的等價(jià)表。
(2)合并等價(jià)關(guān)系a,d時(shí):
①若b=d,則不存入等價(jià)表,合并下一個(gè)等價(jià)關(guān)系。
②若b<d,則以d為索引在當(dāng)前新等價(jià)表中查找d對(duì)應(yīng)等價(jià)值,查得d沒有對(duì)應(yīng)關(guān)系,從而將d為索引,b為等價(jià)值存入新等價(jià)表。
③若b>d,則將d替代a的等價(jià)值b,然后以b為索引查找得到其對(duì)應(yīng)值c,比較c,d大小。若c<d,則以d為索引在當(dāng)前新等價(jià)表中查找,查得d沒有對(duì)應(yīng)關(guān)系,從而將d為索引,c為等價(jià)值存入新等價(jià)表。若c>d,則將d替代b的等價(jià)值c,然后以c為索引查找,查得c沒有對(duì)應(yīng)關(guān)系,從而將c為索引,d為等價(jià)值存入新等價(jià)表。若c=d,則不存入等價(jià)表,合并下一個(gè)等價(jià)關(guān)系。
1.3 鏈表歸并
等價(jià)表合并完成后,從1到臨時(shí)標(biāo)記的最大值按照從小到大的順序依次進(jìn)行歸并。以當(dāng)前合并值為索引對(duì)合并后的新等價(jià)表進(jìn)行查找,如果沒有對(duì)應(yīng)等價(jià)值,則將其本身作為其等價(jià)值存入新的等價(jià)鏈表;如果查得其對(duì)應(yīng)等價(jià)值為M,則繼續(xù)以M為索引對(duì)當(dāng)前新的等價(jià)鏈表查找,查得M對(duì)應(yīng)值為P;若P為不零,則將P作為當(dāng)前合并值的等價(jià)值存入新的等價(jià)鏈表;否則,就將M作為當(dāng)前合并值的等價(jià)值存入新的等價(jià)鏈表。
1.4 順序合并
圖像進(jìn)行第二次掃描時(shí),利用像素的臨時(shí)標(biāo)記值為索引在等價(jià)鏈表中查找其對(duì)應(yīng)值,經(jīng)過歸并后輸出以自然數(shù)順序的標(biāo)記的圖像。第二次掃描過程中,如果第一個(gè)臨時(shí)標(biāo)記X1對(duì)應(yīng)值Q1不為零時(shí),以1替代X1;如果第二個(gè)臨時(shí)標(biāo)記X2對(duì)應(yīng)值Q2不為零時(shí),若Q2不等于Q1,則以2替代X2,否則以1替代X2。依此類推,當(dāng)?shù)趎個(gè)臨時(shí)標(biāo)記Xn對(duì)應(yīng)值Qn不為零時(shí),若Qn=Qm,則以m替代Xn;若Qn≠Qm(0<m<n),則以n替代Xn。
1.5 算法特點(diǎn)分析
本文算法主要是針對(duì)FPGA流水線和并行處理的特點(diǎn)而提出的。利用FPGA實(shí)現(xiàn)時(shí)的運(yùn)算復(fù)雜度優(yōu)于文獻(xiàn)。采用FPGA實(shí)現(xiàn)該算法需要總時(shí)鐘周期小于2×N×M,N為圖像行數(shù),M為列數(shù)。
算法利用FPGA的特點(diǎn)主要體現(xiàn)在:圖像標(biāo)記過程中同時(shí)對(duì)等價(jià)關(guān)系進(jìn)行合并,在FPGA實(shí)現(xiàn)時(shí)圖像標(biāo)記和等價(jià)關(guān)系合并可以并行執(zhí)行,減少了整個(gè)過程的處理時(shí)間;臨時(shí)標(biāo)記和順序合并采用了流水線方式進(jìn)行,減少了處理等待時(shí)間,能較快輸出圖像;鏈表歸并和順序合并單元采用高于臨時(shí)標(biāo)記和等價(jià)關(guān)系合并單元時(shí)鐘頻率,既體現(xiàn)了并行處理特性又提高了處理速度。
2 硬件實(shí)現(xiàn)方案
該設(shè)計(jì)采用單片F(xiàn)PGA來實(shí)現(xiàn)上述連通域快速標(biāo)記算法,標(biāo)記處理單元均利用FPGA片內(nèi)資源,不需要其他外部單元,縮小了硬件體積,電路結(jié)構(gòu)簡(jiǎn)單,節(jié)約了硬件資源、易于實(shí)現(xiàn)。該算法實(shí)現(xiàn)過程采用VHDL編程的方式在FPGA上實(shí)現(xiàn)。硬件實(shí)現(xiàn)框圖如圖4所示。
標(biāo)記單元采用流水線的方式對(duì)二值圖像逐個(gè)像素進(jìn)行標(biāo)記。采用FPGA內(nèi)部的FIFO存儲(chǔ)1行已標(biāo)記像素的標(biāo)記值來實(shí)現(xiàn)2×2的掃描窗口。標(biāo)記單元結(jié)構(gòu)如圖5所示。圖像經(jīng)標(biāo)記單元處理后,將像素的標(biāo)記值Label_value存儲(chǔ)到圖像存儲(chǔ)單元中,等價(jià)關(guān)系Eq_valuel,Eq_value2存儲(chǔ)到等價(jià)表中。圖像存儲(chǔ)、等價(jià)表合并和鏈表歸并三個(gè)處理單元都是采用對(duì)雙口RAM的讀/寫操作來實(shí)現(xiàn)。處理單元流程圖如圖6所示。圖像存儲(chǔ)單元采用兩個(gè)雙口RAM乒乓操作來實(shí)現(xiàn),分別為RAMa和RAMb,每個(gè)雙口RAM單獨(dú)存儲(chǔ)一幀圖像像素臨時(shí)標(biāo)記。在圖像的標(biāo)記過程中,像素的臨時(shí)標(biāo)記值實(shí)時(shí)的存儲(chǔ)到RAMa或RAMb中。等價(jià)表存儲(chǔ)采用一個(gè)異步的雙口RAMc作為緩存,將標(biāo)記輸出的等價(jià)關(guān)系Eq_valuel,Eq_value2中較大值作為高位,較小值作為低位合并后按順序存儲(chǔ)到RAMc中。存儲(chǔ)的同時(shí),從另一個(gè)端口讀取RAMc中存儲(chǔ)的等價(jià)關(guān)系,進(jìn)行等價(jià)表合并。等價(jià)表合并過程中,將等價(jià)關(guān)系中較大值作為地址,較小值作為數(shù)據(jù)存儲(chǔ)到異步雙口RAMd中。鏈表歸并采用兩個(gè)雙口RAM進(jìn)行乒乓操作,分別為RAMe和RAMf。每個(gè)RAM存儲(chǔ)1幀圖像標(biāo)記后的歸并鏈表值。RAMe和RAMf存儲(chǔ)的圖像鏈表分別與RAMa和RAMb存儲(chǔ)的像素標(biāo)記相對(duì)應(yīng)。順序合并主要采用寄存器和比較器來實(shí)現(xiàn)。利用寄存器存儲(chǔ)經(jīng)等價(jià)鏈表處理后圖像非零像素的不同的標(biāo)記,然后通過比較器進(jìn)行判斷處理,最后以自然數(shù)順序的標(biāo)記替代像素的標(biāo)記。
3 FPGA實(shí)驗(yàn)結(jié)果
為了能夠仿真該算法的硬件可實(shí)現(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ā)板對(duì)本文的算法進(jìn)行了驗(yàn)證,在33 MHz工作時(shí)鐘下,單片F(xiàn)PGA能完成1 000 f/s的128×128的二值圖像標(biāo)記。實(shí)驗(yàn)結(jié)果表明本文提出的適于FPGA實(shí)現(xiàn)的二值圖像連通域快速標(biāo)記算法能滿足實(shí)時(shí)性要求。
4 結(jié)語(yǔ)
圖像連通域標(biāo)記是目標(biāo)跟蹤與識(shí)別圖像處理系統(tǒng)中的重要環(huán)節(jié)。由于圖像的數(shù)據(jù)運(yùn)算量大,利用軟件來實(shí)現(xiàn)難以滿足系統(tǒng)的實(shí)時(shí)性。本文介紹的適于FPGA實(shí)現(xiàn)的連通域快速標(biāo)記算法能夠?qū)Χ祱D像以自然數(shù)順序?qū)D像連通區(qū)域進(jìn)行快速標(biāo)記。軟件仿真和硬件實(shí)現(xiàn)結(jié)果表明,本文介紹的連通域快速標(biāo)記算法能夠?qū)Υ嬖趶?fù)雜連通關(guān)系的二值圖像進(jìn)行正確標(biāo)記。該設(shè)計(jì)只采用單片FPGA實(shí)現(xiàn),電路結(jié)構(gòu)簡(jiǎn)單,大大節(jié)約了硬件資源,體積小,易于實(shí)現(xiàn)。對(duì)于較大的圖像的連通域快速標(biāo)記,只需在FPGA外接存儲(chǔ)器就能夠?qū)崿F(xiàn)。