基于FPGA的二值圖像連通域快速標記
加入技術(shù)交流群
1．2 等價(jià)關(guān)系合并
在第一次掃描過(guò)程中，在對像素臨時(shí)標記的同時(shí)對等價(jià)表進(jìn)行合并。等價(jià)表合并按照等價(jià)表的存儲順序以較大值為索引的鏈表循環(huán)查找的方式進(jìn)行合并，合并后的等價(jià)關(guān)系存儲到新的等價(jià)表中。以圖3所示的等價(jià)表合并為例來(lái)說(shuō)明等價(jià)表合并過(guò)程。圖3中，第一行為等價(jià)關(guān)系存儲的順序；第二、三行分別為等價(jià)關(guān)系的索引值和等價(jià)值。其中，a>b>0，a>d>0，b>c>0。等表合并步驟如下：
(1)首先以a為索引在新的等價(jià)表中查找a所對應等價(jià)值，查得a沒(méi)有對應值，因此將較大值a為索引，b為等價(jià)值存入新的等價(jià)表。同理，b，c也存入了新的等價(jià)表。
(2)合并等價(jià)關(guān)系a，d時(shí)：
①若b=d，則不存入等價(jià)表，合并下一個(gè)等價(jià)關(guān)系。
②若bd，則以d為索引在當前新等價(jià)表中查找d對應等價(jià)值，查得d沒(méi)有對應關(guān)系，從而將d為索引，b為等價(jià)值存入新等價(jià)表。
③若b>d，則將d替代a的等價(jià)值b，然后以b為索引查找得到其對應值c，比較c，d大小。若cd，則以d為索引在當前新等價(jià)表中查找，查得d沒(méi)有對應關(guān)系，從而將d為索引，c為等價(jià)值存入新等價(jià)表。若c>d，則將d替代b的等價(jià)值c，然后以c為索引查找，查得c沒(méi)有對應關(guān)系，從而將c為索引，d為等價(jià)值存入新等價(jià)表。若c=d，則不存入等價(jià)表，合并下一個(gè)等價(jià)關(guān)系。
1．3 鏈表歸并
等價(jià)表合并完成后，從1到臨時(shí)標記的最大值按照從小到大的順序依次進(jìn)行歸并。以當前合并值為索引對合并后的新等價(jià)表進(jìn)行查找，如果沒(méi)有對應等價(jià)值，則將其本身作為其等價(jià)值存入新的等價(jià)鏈表；如果查得其對應等價(jià)值為M，則繼續以M為索引對當前新的等價(jià)鏈表查找，查得M對應值為P；若P為不零，則將P作為當前合并值的等價(jià)值存入新的等價(jià)鏈表；否則，就將M作為當前合并值的等價(jià)值存入新的等價(jià)鏈表。
1．4 順序合并
圖像進(jìn)行第二次掃描時(shí)，利用像素的臨時(shí)標記值為索引在等價(jià)鏈表中查找其對應值，經(jīng)過(guò)歸并后輸出以自然數順序的標記的圖像。第二次掃描過(guò)程中，如果第一個(gè)臨時(shí)標記X1對應值Q1不為零時(shí)，以1替代X1；如果第二個(gè)臨時(shí)標記X2對應值Q2不為零時(shí)，若Q2不等于Q1，則以2替代X2，否則以1替代X2。依此類(lèi)推，當第n個(gè)臨時(shí)標記Xn對應值Qn不為零時(shí)，若Qn=Qm，則以m替代Xn；若Qn≠Qm(0mn)，則以n替代Xn。
1．5 算法特點(diǎn)分析
本文算法主要是針對FPGA流水線(xiàn)和并行處理的特點(diǎn)而提出的。利用FPGA實(shí)現時(shí)的運算復雜度優(yōu)于文獻。采用FPGA實(shí)現該算法需要總時(shí)鐘周期小于2×N×M，N為圖像行數，M為列數。
算法利用FPGA的特點(diǎn)主要體現在：圖像標記過(guò)程中同時(shí)對等價(jià)關(guān)系進(jìn)行合并，在FPGA實(shí)現時(shí)圖像標記和等價(jià)關(guān)系合并可以并行執行，減少了整個(gè)過(guò)程的處理時(shí)間；臨時(shí)標記和順序合并采用了流水線(xiàn)方式進(jìn)行，減少了處理等待時(shí)間，能較快輸出圖像；鏈表歸并和順序合并單元采用高于臨時(shí)標記和等價(jià)關(guān)系合并單元時(shí)鐘頻率，既體現了并行處理特性又提高了處理速度。
2 硬件實(shí)現方案
該設計采用單片FPGA來(lái)實(shí)現上述連通域快速標記算法，標記處理單元均利用FPGA片內資源，不需要其他外部單元，縮小了硬件體積，電路結構簡(jiǎn)單，節約了硬件資源、易于實(shí)現。該算法實(shí)現過(guò)程采用VHDL編程的方式在FPGA上實(shí)現。硬件實(shí)現框圖如圖4所示。本文引用地址：http://dyxdggzs.com/article/191201.htm
標記單元采用流水線(xiàn)的方式對二值圖像逐個(gè)像素進(jìn)行標記。采用FPGA內部的FIFO存儲1行已標記像素的標記值來(lái)實(shí)現2×2的掃描窗口。標記單元結構如圖5所示。圖像經(jīng)標記單元處理后，將像素的標記值Label_value存儲到圖像存儲單元中，等價(jià)關(guān)系Eq_valuel，Eq_value2存儲到等價(jià)表中。圖像存儲、等價(jià)表合并和鏈表歸并三個(gè)處理單元都是采用對雙口RAM的讀／寫(xiě)操作來(lái)實(shí)現。處理單元流程圖如圖6所示。圖像存儲單元采用兩個(gè)雙口RAM乒乓操作來(lái)實(shí)現，分別為RAMa和RAMb，每個(gè)雙口RAM單獨存儲一幀圖像像素臨時(shí)標記。在圖像的標記過(guò)程中，像素的臨時(shí)標記值實(shí)時(shí)的存儲到RAMa或RAMb中。等價(jià)表存儲采用一個(gè)異步的雙口RAMc作為緩存，將標記輸出的等價(jià)關(guān)系Eq_valuel，Eq_value2中較大值作為高位，較小值作為低位合并后按順序存儲到RAMc中。存儲的同時(shí)，從另一個(gè)端口讀取RAMc中存儲的等價(jià)關(guān)系，進(jìn)行等價(jià)表合并。等價(jià)表合并過(guò)程中，將等價(jià)關(guān)系中較大值作為地址，較小值作為數據存儲到異步雙口RAMd中。鏈表歸并采用兩個(gè)雙口RAM進(jìn)行乒乓操作，分別為RAMe和RAMf。每個(gè)RAM存儲1幀圖像標記后的歸并鏈表值。RAMe和RAMf存儲的圖像鏈表分別與RAMa和RAMb存儲的像素標記相對應。順序合并主要采用寄存器和比較器來(lái)實(shí)現。利用寄存器存儲經(jīng)等價(jià)鏈表處理后圖像非零像素的不同的標記，然后通過(guò)比較器進(jìn)行判斷處理，最后以自然數順序的標記替代像素的標記。
評論