Laplacian圖像邊緣檢測(cè)器的FPGA實(shí)現(xiàn)研究

1 引言
    邊緣可定義為圖像中灰度發(fā)生急劇變化的區(qū)域邊界，它是圖像最基本的特征，是圖像分析識(shí)別前必不可少的環(huán)節(jié)，是一種重要的圖像預(yù)處理技術(shù)。邊緣檢測(cè)主要就是(圖像的)灰度變化的度量、檢測(cè)和定位，它是圖像分析和模式識(shí)別的主要特征提取手段，在計(jì)算機(jī)視覺、圖像分析等應(yīng)用中起著重要的作用，是圖像分析與處理中研究的熱點(diǎn)問題。
    數(shù)字信號(hào)和圖像處理算法的實(shí)現(xiàn)有多種途徑，傳統(tǒng)上多采用高級(jí)語言編程實(shí)現(xiàn)，便于使用的還有基于專用單片機(jī)來實(shí)現(xiàn)(一般稱為可編程DSP單片機(jī))以及在VLSI上實(shí)現(xiàn)某種算法的專用集成電路芯片(ASIC)等。近年來，隨著EDA技術(shù)的迅速發(fā)展，國(guó)內(nèi)外逐漸比較流行的是在FPGA中實(shí)現(xiàn)復(fù)雜算法的運(yùn)算處理。
    在圖形處理領(lǐng)域，圖像處理的速度一直是一個(gè)很難突破的設(shè)計(jì)瓶頸。這里通過研究圖像邊緣檢測(cè)器的FPGA實(shí)現(xiàn)，來探討提高圖像處理速度的有關(guān)途徑。

2 Laplacian邊緣檢測(cè)的數(shù)學(xué)模型
    常見的邊緣檢測(cè)算子有：Roberts，Laplacian，Kirseh，So—bel，Prewitt等。各種檢測(cè)算子各有其優(yōu)缺點(diǎn)，其中Laplacian算子是一種典型的邊緣檢測(cè)方法，它是一個(gè)3×3模板，對(duì)實(shí)現(xiàn)硬件的要求不高，用于檢測(cè)屋頂型邊緣的效果也不錯(cuò)。研究其硬件實(shí)現(xiàn)具有一定的典型性，可推廣到對(duì)其他算子的硬件實(shí)現(xiàn)。
    拉普拉斯算子是根據(jù)圖像f(x，y)在x，y方向上的二階偏導(dǎo)數(shù)定義的一種邊緣檢測(cè)算子，其定義：

   
    因?yàn)閳D像邊緣的灰度變化較大，所以圖像的一階偏導(dǎo)數(shù)在邊緣處有局部最大值或最小值，這樣二階偏導(dǎo)數(shù)在邊緣處會(huì)通過零點(diǎn)。用拉普拉斯算子檢測(cè)邊緣就是估算拉普拉斯算子的輸出，找出其零點(diǎn)位置。拉普拉斯算子定義為：

   
    如果把它用加權(quán)矩陣來表示則可表示成圖1左側(cè)所示的卷積模板。由于數(shù)字圖像中離散信號(hào)的特點(diǎn)，在連續(xù)情況下能獲得的精確零點(diǎn)這時(shí)可能無法全部檢測(cè)出來，故拉普拉斯算子輸出為零的點(diǎn)并不能表示出完整的目標(biāo)邊緣。為此，在設(shè)計(jì)中定義邊緣為滿足以下兩個(gè)條件的像素點(diǎn)的集合：①拉普拉斯算子的輸出為正；②在其8鄰點(diǎn)存在拉普拉斯算子的輸出為負(fù)的點(diǎn)。

3 圖像邊緣檢測(cè)的實(shí)現(xiàn)流程
    圖像邊緣檢測(cè)有一個(gè)共同點(diǎn)：可轉(zhuǎn)化為用一個(gè)模板(2×2．3×3，4×4，5×5等)對(duì)圖像進(jìn)行卷積。因此圖像邊緣檢測(cè)的核心就是如何處理模板的卷積運(yùn)算。Laplacian算子就是一個(gè)3×3的卷積模板。
    3x3卷積運(yùn)算閣定義如(3)式所示，其中Cm，n為被卷積后的像素值，Pm，n為圖像的實(shí)際像素值，其中Cm，n為被卷積后的像素值，Pm，n為圖像的實(shí)際像素值。由(3)式可知，完成一次3x3卷積操作需要9次乘法和8次加法操作。

   
    由圖1可知，圖像邊緣檢測(cè)的主要實(shí)現(xiàn)流程為：①模板在圖像中以光柵掃描方式移動(dòng)；②將模板系數(shù)與模板下對(duì)應(yīng)像素相乘；③將所有乘積相加；④將和(模板輸出響應(yīng))賦給圖像中對(duì)應(yīng)模板中心位置的像素完成一次卷積。不斷重復(fù)上述步驟直至整幅圖像被處理完。

4 分布式算法的運(yùn)算原理
    分布式算法早在1973年就被Croisier提出，直到FPGA出現(xiàn)，才被廣泛地應(yīng)用在FPGA中計(jì)算乘積和。除了用于卷積運(yùn)算，還用于相關(guān)DFT和RNS反演映射的運(yùn)算。介紹DA算法的運(yùn)算原理。一個(gè)線性時(shí)不變網(wǎng)絡(luò)的輸出用下式表示：

   
    假設(shè)系數(shù)c[n]是已知常數(shù)，x[n]是變量，在有符號(hào)DA系統(tǒng)中假設(shè)變量x[n]的表達(dá)式如下：

   
    式中xb[n]表示x[n]的第b位，而x[n]也就是x的第n次采樣。于是，內(nèi)積y可以表示為：

   
    重新分別求和(即分布式算法的由來)，其結(jié)果為：

   
    從(7)式發(fā)現(xiàn)，分布式算法是一種以實(shí)現(xiàn)乘加運(yùn)算為目的運(yùn)算方法。與傳統(tǒng)算法的不同在于執(zhí)行部分積運(yùn)算的先后順序不同。分布式算法在實(shí)現(xiàn)乘加功能時(shí)，是將各輸入數(shù)據(jù)的每一對(duì)應(yīng)位產(chǎn)生的部分積預(yù)先相加形成相應(yīng)的部分積．然后再對(duì)各個(gè)部分積累加形成最終結(jié)果，而傳統(tǒng)算法是等到所有乘積已經(jīng)產(chǎn)生后再相加完成乘加運(yùn)算。與傳統(tǒng)串行算法相比，分布式算法可極大地減少硬件電路的規(guī)模，提高電路的執(zhí)行速度。該算法實(shí)際上是一個(gè)“速度最優(yōu)的高階分布式算法”

5 Laplacian邊緣檢測(cè)器的FPGA設(shè)計(jì)
5．1 系統(tǒng)的總體設(shè)計(jì)
    Laplacian邊緣檢測(cè)器DETECTOR總體設(shè)計(jì)如圖2所示。系統(tǒng)工作原理為：幀存儲(chǔ)器按照一定的規(guī)則(是按行)輸出數(shù)據(jù)，經(jīng)過FIFO輸入緩沖，進(jìn)入兩個(gè)32位的移位寄存器。由SIPO(串進(jìn)并出)模塊得到所需的9個(gè)并行數(shù)據(jù)，送卷積處理器(Convolver)得到處理后的數(shù)據(jù)，最后卷積器輸出一個(gè)像素值。根據(jù)邊緣判斷規(guī)則，即可判斷出該點(diǎn)是否為邊緣點(diǎn)。

5．2 卷積運(yùn)算模塊的設(shè)計(jì)
    Laplacian模板是一個(gè)3x3階的數(shù)，每個(gè)像素值為8位，因此，它和另外的3x3模板進(jìn)行卷積，其輸出表達(dá)式為：

   

   
    對(duì)于該卷積運(yùn)算的實(shí)現(xiàn)，采用前述的“速度最優(yōu)的高階分布式算法”，其硬件實(shí)現(xiàn)的原理框圖如圖3所示。它是完全流水線式字并行結(jié)構(gòu)，能夠達(dá)到最大的運(yùn)算速度。其中的8個(gè)ROM是用于實(shí)現(xiàn)9個(gè)R圖位的數(shù)相乘，每個(gè)ROM都實(shí)現(xiàn)一個(gè)9位的查找表的功能。5．3卷積運(yùn)算數(shù)據(jù)“流水線”輸入模塊的設(shè)計(jì)圖像的像素是由CCD(或CMOS)攝像機(jī)經(jīng)A／D轉(zhuǎn)換，再經(jīng)量化而得到，并放入幀存儲(chǔ)器。在圖像中，整幅圖像像素以幀為單位進(jìn)行存儲(chǔ)。每一幀數(shù)據(jù)的存儲(chǔ)方式如圖4所示。卷積運(yùn)算掃描像素的獲取如圖5所示，該數(shù)據(jù)輸入方式，使用了兩個(gè)32位的移位寄存器存放像素值，避免了卷積運(yùn)算中對(duì)存儲(chǔ)器數(shù)據(jù)的高度重復(fù)讀取，使用9個(gè)寄存器實(shí)現(xiàn)了數(shù)據(jù)由串行到并行的轉(zhuǎn)換，實(shí)現(xiàn)了完全“流水線”的輸入方式。

5．4 系統(tǒng)的仿真結(jié)果
    根據(jù)前述的總體設(shè)計(jì)方案，使用VHDL設(shè)計(jì)進(jìn)行各個(gè)模塊和系統(tǒng)總體程序，選擇的FPGA為ALTERA／FLEX／EPF10K20TC144—3，使用的開發(fā)工具是MAX+plus II 10．0。圖6是邊緣檢測(cè)器的時(shí)序仿真圖(鐘頻率10 MHz)，由波形仿真結(jié)果分析可知，系統(tǒng)達(dá)到了設(shè)計(jì)功能要求，該系統(tǒng)經(jīng)過初始的兩行行延遲和串并轉(zhuǎn)化后(為72個(gè)時(shí)鐘周期)，以后每個(gè)時(shí)鐘周期就可“流水式”輸出一個(gè)處理結(jié)果，若系統(tǒng)時(shí)鐘周期TCLK，對(duì)于像素為N個(gè)點(diǎn)的數(shù)字圖像，系統(tǒng)的處理時(shí)間TN=70xTCLK+N×TCLK。處理一幅1 024x1 024的圖像的時(shí)間，當(dāng)系統(tǒng)時(shí)鐘為10MHz時(shí)，僅需0．1 s，而系統(tǒng)時(shí)鐘為10 MHz時(shí)，僅需0．Ol s。

6 結(jié)語
    在Laplacian圖像邊緣檢測(cè)器的設(shè)計(jì)中，采用了速度最優(yōu)的高階分布式算法(DA)完成模板的卷積運(yùn)算，使用兩個(gè)32位的移位寄存器存放像素值，避免了卷積運(yùn)算中對(duì)存儲(chǔ)器數(shù)據(jù)的高度重復(fù)讀取，使用9個(gè)寄存器實(shí)現(xiàn)數(shù)據(jù)由串行到并行的轉(zhuǎn)換，實(shí)現(xiàn)了完全“流水線”的數(shù)據(jù)輸入方式，從而在資源．速度上達(dá)到了較好的優(yōu)化，具有良好的實(shí)時(shí)處理性能。若系統(tǒng)工作時(shí)鐘為100 MHz，則處理一幅1 024x1 024的圖像的時(shí)間僅需0．01 s左右?！傲魉€”的數(shù)據(jù)輸入方式和分布式卷積運(yùn)算的設(shè)計(jì)思想，對(duì)于數(shù)字圖像和數(shù)字信號(hào)處理的FPGA硬件實(shí)現(xiàn)，具有廣泛的推廣應(yīng)用價(jià)值。