新聞中心

EEPW首頁 > EDA/PCB > 設(shè)計應(yīng)用 > 基于FPGA的二值圖像連通域快速標(biāo)記

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

作者: 時間:2011-05-23 來源:網(wǎng)絡(luò) 收藏

1.2 等價關(guān)系合并
在第一次掃描過程中,在對像素臨時的同時對等價表進行合并。等價表合并按照等價表的存儲順序以較大值為索引的鏈表循環(huá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)系。
②若bd,則以d為索引在當(dāng)前新等價表中查找d對應(yīng)等價值,查得d沒有對應(yīng)關(guān)系,從而將d為索引,b為等價值存入新等價表。
③若b>d,則將d替代a的等價值b,然后以b為索引查找得到其對應(yīng)值c,比較c,d大小。若cd,則以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到臨時的最大值按照從小到大的順序依次進行歸并。以當(dāng)前合并值為索引對合并后的新等價表進行查找,如果沒有對應(yīng)等價值,則將其本身作為其等價值存入新的等價鏈表;如果查得其對應(yīng)等價值為M,則繼續(xù)以M為索引對當(dāng)前新的等價鏈表查找,查得M對應(yīng)值為P;若P為不零,則將P作為當(dāng)前合并值的等價值存入新的等價鏈表;否則,就將M作為當(dāng)前合并值的等價值存入新的等價鏈表。
1.4 順序合并
圖像進行第二次掃描時,利用像素的臨時值為索引在等價鏈表中查找其對應(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(0mn),則以n替代Xn。
1.5 算法特點分析
本文算法主要是針對流水線和并行處理的特點而提出的。利用實現(xiàn)時的運算復(fù)雜度優(yōu)于文獻。采用實現(xiàn)該算法需要總時鐘周期小于2×N×M,N為圖像行數(shù),M為列數(shù)。
算法利用FPGA的特點主要體現(xiàn)在:圖像標(biāo)記過程中同時對等價關(guān)系進行合并,在FPGA實現(xiàn)時圖像標(biāo)記和等價關(guān)系合并可以并行執(zhí)行,減少了整個過程的處理時間;臨時標(biāo)記和順序合并采用了流水線方式進行,減少了處理等待時間,能較快輸出圖像;鏈表歸并和順序合并單元采用高于臨時標(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所示。

本文引用地址:http://butianyuan.cn/article/191201.htm

e.jpg


標(biāo)記單元采用流水線的方式對逐個像素進行標(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單獨存儲一幀圖像像素臨時標(biāo)記。在圖像的標(biāo)記過程中,像素的臨時標(biāo)記值實時的存儲到RAMa或RAMb中。等價表存儲采用一個異步的雙口RAMc作為緩存,將標(biāo)記輸出的等價關(guān)系Eq_valuel,Eq_value2中較大值作為高位,較小值作為低位合并后按順序存儲到RAMc中。存儲的同時,從另一個端口讀取RAMc中存儲的等價關(guān)系,進行等價表合并。等價表合并過程中,將等價關(guān)系中較大值作為地址,較小值作為數(shù)據(jù)存儲到異步雙口RAMd中。鏈表歸并采用兩個雙口RAM進行乒乓操作,分別為RAMe和RAMf。每個RAM存儲1幀圖像標(biāo)記后的歸并鏈表值。RAMe和RAMf存儲的圖像鏈表分別與RAMa和RAMb存儲的像素標(biāo)記相對應(yīng)。順序合并主要采用寄存器和比較器來實現(xiàn)。利用寄存器存儲經(jīng)等價鏈表處理后圖像非零像素的不同的標(biāo)記,然后通過比較器進行判斷處理,最后以自然數(shù)順序的標(biāo)記替代像素的標(biāo)記。



關(guān)鍵詞: FPGA 二值圖像 標(biāo)記

評論


相關(guān)推薦

技術(shù)專區(qū)

關(guān)閉