張海斌, 朱蘇磊, 徐明亮

(上海師范大學(xué) 信息與機(jī)電工程學(xué)院,上海 200234)

基于可編程邏輯陣列的索貝爾邊緣檢測(cè)算法的兩種實(shí)現(xiàn)方案

張海斌, 朱蘇磊*, 徐明亮

(上海師范大學(xué) 信息與機(jī)電工程學(xué)院,上海 200234)

基于可編程邏輯陣列(FPGA)的片上可編程及并行流水線具有處理快、實(shí)時(shí)性等優(yōu)點(diǎn),采用Quartus II自帶知識(shí)產(chǎn)權(quán)(IP)核進(jìn)行設(shè)計(jì)的方案耗資源多,處理速度慢,針對(duì)于此提出了改進(jìn)的索貝爾(Sobel)算子方案,使以上缺點(diǎn)得到改善;結(jié)合Matlab和Modelsim對(duì)這兩種方案的仿真和驗(yàn)證結(jié)果表明,改進(jìn)后的Sobel算子方案明顯優(yōu)于Quartus II自帶IP核進(jìn)行設(shè)計(jì)的方案,并且能很好地實(shí)現(xiàn)圖像邊緣檢測(cè),減少了偏差.

邊緣檢測(cè); 可編程邏輯陣列; 數(shù)字圖像處理

0 引 言

數(shù)字圖像處理就是采用計(jì)算機(jī)或嵌入式系統(tǒng)對(duì)圖像進(jìn)行深度加工,并從中獲得有用的信息.伴隨著計(jì)算機(jī)技術(shù)、集成電路技術(shù)的飛速發(fā)展,數(shù)字圖像處理技術(shù)也得到了很大的發(fā)展,并且也出現(xiàn)了許多與數(shù)字圖像處理技術(shù)相關(guān)的新理論、新技術(shù)、新設(shè)備.這些新理論、新技術(shù)在工業(yè)生產(chǎn)、科學(xué)研究、醫(yī)療衛(wèi)生等領(lǐng)域得到了廣泛應(yīng)用,對(duì)社會(huì)的發(fā)展及人類生活水平的提高做出了極大的貢獻(xiàn)[1].

邊緣是圖像的基本特征,是指圖像灰度變化率最大的位置,由圖像像素點(diǎn)數(shù)據(jù)局部的不連續(xù)而形成.邊緣的表現(xiàn)形式有圖像紋理結(jié)構(gòu)的突變及灰度級(jí)的突變,彩色變化等等,邊緣檢測(cè)利用物體與背景在某些特征上的差異而實(shí)現(xiàn).由于實(shí)時(shí)圖像邊緣檢測(cè)算法涉及到的數(shù)據(jù)量大,一般運(yùn)算器的順序執(zhí)行或者傳統(tǒng)軟件處理實(shí)時(shí)圖像很難滿足要求.而采用可編程邏輯陣列(FPGA)的流水線和并行處理技術(shù),不僅可以提高數(shù)字圖像的處理速度,也可以在一定程度上滿足實(shí)時(shí)系統(tǒng)中的應(yīng)用需求.

邊緣檢測(cè)算子可以分為一階微分算子和二階微分算子.常見(jiàn)的一階微分算子有Prewitt算子,Canny算子、Sobel算子、Roberts Cross算子,Kirsch算子,羅盤算子等等;二階微分算子包括Laplacian算子以及高斯-拉普拉斯(LOG)算子等等[2].本研究主要介紹了基于FPGA的索貝爾(Sobel)邊緣檢測(cè)算法實(shí)現(xiàn)的兩種方案,方案一完全采用Quartus II自帶的知識(shí)產(chǎn)權(quán)核(IP)核進(jìn)行實(shí)現(xiàn),實(shí)現(xiàn)簡(jiǎn)單、工程周期短,但占用邏輯資源多,設(shè)計(jì)效果不夠理想;方案二針對(duì)方案一的缺點(diǎn)進(jìn)行了改進(jìn),改善了系統(tǒng)處理速度,減少了邏輯資源的消耗,在一定程度上改善了設(shè)計(jì)效果,優(yōu)化了系統(tǒng)性能.

1 Sobel邊緣檢測(cè)算子實(shí)現(xiàn)理論及總體框架

1.1 Sobel邊緣檢測(cè)算子

索貝爾算子(Sobel operator)是數(shù)字圖像處理中的常用算子之一,在圖像邊緣檢測(cè)和噪聲濾波中都有運(yùn)用,它是離散型差分算子,用來(lái)提取圖像亮度函數(shù)的梯度近似值.在圖像的任何像素點(diǎn)上運(yùn)用這一算子,都可以產(chǎn)生對(duì)應(yīng)像素點(diǎn)的梯度矢量或是其法矢量[2].

現(xiàn)在假設(shè)圖像數(shù)據(jù)點(diǎn)上有9個(gè)像素點(diǎn):

σ=[(-1,-1),(-1,0),(-1,1),(0,-1),(0,0),(0,1),(1,-1),(1,0),(1,1)].

(1)

現(xiàn)用一個(gè)二次曲面z(x,y)來(lái)擬合這9個(gè)點(diǎn)的灰度值,即用

z(x,y)=ax2+bxy+cy2+dx+ey+g.

(2)

來(lái)近似圖像灰度函數(shù)f(x,y),并使均方誤差

(3)

將二次曲面z(x,y)對(duì)x,y求偏導(dǎo)數(shù),得到梯度的幅度值[3]:

G(i,j)=[f(i-1,j-1)+2f(i-1,j)+f(i-1,j+1)]-

[f(i+1,j-1)+2f(i+1,j)+f(i+1,j+1)]+

[f(i-1,j-1)+2f(i,j-1)+f(i+1,j-1)]-

[f(i-1,j+1)+2f(i,j+1)+f(i+1,j+1)].

(4)

它的兩個(gè)卷積模塊為:

(5)

(6)

1.2 基于FPGA的Sobel算子實(shí)現(xiàn)框圖

圖1 Sobel邊緣檢測(cè)實(shí)現(xiàn)的原理框圖

Sobel邊緣檢測(cè)算法的實(shí)現(xiàn)主要包括三個(gè)模塊,如圖1所示.

圖1中,前兩個(gè)模塊主要是實(shí)現(xiàn)圖像像素點(diǎn)的梯度值計(jì)算,圖像數(shù)據(jù)輸入通過(guò)數(shù)據(jù)緩存模塊構(gòu)成3×3矩陣像素陣列,然后再分別計(jì)算水平梯度和垂直梯度,然后把兩個(gè)方向上的梯度結(jié)合起來(lái),接著通過(guò)門限處理模塊,實(shí)現(xiàn)判別輸出.假設(shè)輸入的像素值依次為:p11、p12、p13、p21、p22、p31、p32、p33,那么在垂直方向上的梯度和在水平方向上的梯度分別為:

GH=(p13+2p23+p33)-(p11+2p21+p31),

(7)

GV=(p11+2p12+p13)-(p31+2p32+p33).

(8)

梯度結(jié)合后的梯度值G為:

(9)

通常為了提高程序的運(yùn)行速度都采用如下的公式:

(10)

門限處理模塊之后輸出數(shù)值P22,當(dāng)設(shè)定的門限值大于G時(shí),輸出為0,當(dāng)G大于設(shè)定的門限值時(shí)輸出為255.綜上分析Sobel算子在理論設(shè)計(jì)上容易實(shí)現(xiàn),并且具有濾除噪聲的作用,所以適合用在圖像噪聲較多的圖像處理中.

2 基于IP核的Sobel算子實(shí)現(xiàn)方案

2.1 圖像緩存實(shí)現(xiàn)

圖2 altshift_taps內(nèi)部數(shù)據(jù)流

由于Sobel算子理論基于3×3像素塊計(jì)算中心像素梯度,構(gòu)造3×3像素矩陣特別重要,要實(shí)現(xiàn)這個(gè)效果,必須使用一個(gè)容量足夠大的存儲(chǔ)單元來(lái)緩存串行輸入的圖像數(shù)據(jù)流,并把串行數(shù)據(jù)轉(zhuǎn)化成并行的3行像素值,這樣在3個(gè)像素時(shí)鐘后就可以得到3×3圖像像素矩陣.過(guò)去常使用先入先出(FIFO)作為圖像數(shù)據(jù)的存儲(chǔ)方式,但對(duì)FIFO的讀寫(xiě)操作較為復(fù)雜.而本設(shè)計(jì)中主要是調(diào)用了Quartus II軟件自帶的altshift_taps移位寄存器宏模塊.軟件中提供的altshift_taps宏模塊是一個(gè)可設(shè)置參數(shù)的并具有多個(gè)端口(Taps)輸出的移位寄存器,每一個(gè)抽頭在移位寄存器鏈的指定位置上輸出數(shù)據(jù).對(duì)于Matlab經(jīng)常應(yīng)用的256×256大小圖像進(jìn)行Sobel邊緣檢測(cè),altshift_taps模塊配置為8 bit輸入/8 bit輸出、3個(gè)抽頭,相鄰兩個(gè)抽頭有256個(gè)registor(寄存單元).經(jīng)過(guò)預(yù)處理的9個(gè)圖像灰度像素點(diǎn)進(jìn)入緩沖區(qū)后數(shù)據(jù)流如,圖2所示.

2.2 卷積計(jì)算和門限比較模塊

編寫(xiě)的卷積計(jì)算模塊是為了得到水平的、垂直的兩個(gè)方向上的梯度值,要達(dá)到卷積運(yùn)算的效果需要做大量的乘法、加法運(yùn)算.若是采用以往分立的D觸發(fā)器、加法器和乘法器來(lái)完成,可以實(shí)現(xiàn)預(yù)期的功能,但其結(jié)構(gòu)復(fù)雜,設(shè)計(jì)繁瑣.在本方案中先通過(guò)調(diào)用Quartus II開(kāi)發(fā)工具提供的IP核模塊中的可編程乘加法器altmult_add、可編程多路加法器parallel_add以及開(kāi)方模塊(altsqrt)來(lái)實(shí)現(xiàn).其原理如圖3所示.

圖3 卷積計(jì)算示意圖

圖3中前面的3個(gè)Line就是緩存數(shù)據(jù)模塊,而后面的實(shí)現(xiàn)水平梯度和垂直梯度的計(jì)算及開(kāi)方后的結(jié)果再與門限比較,輸出判別后的結(jié)果.

3 改進(jìn)后的Sobel算子實(shí)現(xiàn)方案

考慮到上述方案調(diào)用IP時(shí),占用FPGA邏輯資源大,在處理數(shù)據(jù)乘、開(kāi)方時(shí),占用大量CPU資源,提出了改進(jìn)設(shè)計(jì)方案.

3.1 圖像緩沖模塊設(shè)計(jì)改進(jìn)

基于圖2的圖像數(shù)據(jù)緩沖模塊的數(shù)據(jù)流結(jié)構(gòu),構(gòu)想在shift_RAM中存儲(chǔ)2行數(shù)據(jù),同時(shí)與當(dāng)前的輸入行數(shù)據(jù)組成3行的陳列,具體的實(shí)現(xiàn)步奏如下:

(1) 首先,將輸入的信號(hào)用像素使能時(shí)鐘同步一拍,以保證數(shù)據(jù)和宏模塊altshift_taps輸出的數(shù)據(jù)保持同步,主要實(shí)現(xiàn)代碼如圖4所示.

圖4 同步宏模塊altshift_taps輸出數(shù)據(jù)代碼

(2) 例化并輸入row3_data,經(jīng)過(guò)Modelsim仿真可以觀察到3行數(shù)據(jù)同時(shí)存在.

(3) row_data讀取信號(hào)的分析及生成數(shù)據(jù)在altshift-taps里存儲(chǔ)消耗一個(gè)時(shí)鐘,因此3×3陣列陣列讀取使能需要一個(gè)時(shí)鐘的偏移.

(4) 此時(shí),根據(jù)read_image_clken信號(hào)直接讀取3×3像素陣列,最后得到的matrix_p11、matrix_p12、matrix_p13、matrix_p21、matrix_p22、matrix_p23、matrix_p31、matrix_p32、matrix_p33即為得到的3×3像素陣列,主要代碼如圖5所示.

圖5 3×3像素陣列生成代碼

3.2 卷積模塊的實(shí)現(xiàn)

在1.2節(jié)中,可以利用(7),(8)式實(shí)現(xiàn)Sobel算子算像素點(diǎn)P22處的水平和垂直梯度值計(jì)算,在上面構(gòu)成的3×3陳列中可以得到圖像的每一個(gè)像素值,所以只要把(7),(8)式用Verilog語(yǔ)言實(shí)現(xiàn)就可以了,水平梯度值計(jì)算主要代碼如圖6所示.

圖6 水平梯度值計(jì)算代碼

這里只分析像素P22在水平上的梯度值,從3×3矩陣模塊中出來(lái)的像素值matrix_p11,matrix_p12,matrix_p13,matrix_p21,matrix_p22,matrix_p23,matrix_p31,matrix_p32,matrix_p33都是reg無(wú)符號(hào)數(shù)型,即分別為P1、P2、P3、…、P9,在計(jì)算機(jī)內(nèi)部數(shù)字乘以2就是bit位向左移一位,代碼中通過(guò)暫存正結(jié)果和負(fù)結(jié)果,通過(guò)比較這個(gè)數(shù)值的大小最終給出水平上的梯度值.垂直上的梯度值同理實(shí)現(xiàn).接著另一個(gè)進(jìn)程中實(shí)現(xiàn)平方加的結(jié)果,最后再把平方加的結(jié)果送入開(kāi)方模塊SQRT中,輸出對(duì)應(yīng)像素點(diǎn)的估算梯度值,得到的梯度估算值與閥門值比較得出該像素點(diǎn)是否為邊緣像素點(diǎn).

4 實(shí)驗(yàn)結(jié)果及分析

4.1 兩種方案在Quartus II下的分析對(duì)比

兩種方案都是基于altera的CycloneIVE EP4CE10F17C8為目標(biāo)芯片,在Quartus II下編譯綜合,得出兩種方案的硬件資源使用情況綜合報(bào)告及在約定輸入時(shí)鐘25 mHz時(shí)TimeQuest的時(shí)序分析報(bào)告如表1、2所示.

表1 IP核設(shè)計(jì)資源占用情況

表2 改進(jìn)后的設(shè)計(jì)資源占用情況

從表1、2可以看出方案二明顯比方案一占用資源少,首先,內(nèi)嵌乘法器只占用了9%,這樣數(shù)據(jù)處理大大減少;其次,專用邏輯寄存器和引腳也明顯減少,這樣可以在FPGA上留用更多的資源來(lái)處理其他信息;最后在25 mHz時(shí)鐘約束下,從TimeQuest的分析時(shí)鐘看,方案一最大工作效率為34.19 mHz,方案二可以達(dá)到47.78 mHz,這可以看出優(yōu)化后的方案二數(shù)據(jù)處理速度明顯提高,滿足實(shí)時(shí)性的要求.

4.2 仿真結(jié)果分析

圖7 圖像顯示處理代碼

圖8,9分別為輸入相同圖像數(shù)據(jù)時(shí)在Modelsim下兩種方案的Sobel邊緣檢測(cè)仿真結(jié)果,門限設(shè)定都為200,從圖8,9中可以看出在clk時(shí)鐘的作用下,圖像的各個(gè)像素值逐個(gè)輸進(jìn)輸入端口,可以從輸出端口(oDATA、post_img_Bits)看到只有兩種狀態(tài),若該點(diǎn)在邊緣上,則通過(guò)系統(tǒng)后該點(diǎn)值變?yōu)?xff,若不在邊緣則變?yōu)?x00.兩種方案可以實(shí)現(xiàn)對(duì)圖像的邊緣檢測(cè).

圖8 方案一仿真結(jié)果

圖9 方案二仿真結(jié)果

圖10是設(shè)定閾值為200時(shí)兩種方案對(duì)圖像邊緣提取后的結(jié)果對(duì)比,從圖10中可以看出方案二的處理效果明顯比方案一好,進(jìn)一步說(shuō)明改進(jìn)后的方案優(yōu)于采用IP核的方案;處理后的圖片邊沿明顯出現(xiàn)了誤判,這是沒(méi)有對(duì)邊沿像素點(diǎn)采取處理的結(jié)果,在實(shí)際工程中可以對(duì)圖像邊沿采取重疊復(fù)制、忽略處理等方法.

圖10 Matlab重構(gòu)處理后的結(jié)果

5 結(jié) 論

本文作者基于FPGA采用兩種設(shè)計(jì)方案對(duì)Sobel邊緣檢測(cè)進(jìn)行了實(shí)現(xiàn)并仿真分析,首先方案一中完全采用Quartus II自帶的IP核設(shè)計(jì)各個(gè)模塊,實(shí)現(xiàn)圖像各個(gè)像素值卷積實(shí)現(xiàn)圖像邊緣檢測(cè),針對(duì)方案一占用FPGA邏輯資源多,處理圖像數(shù)據(jù)慢等特點(diǎn),設(shè)計(jì)了另一種設(shè)計(jì)方案,一方面,針對(duì)數(shù)據(jù)的左移一位(乘2)的思想很好地實(shí)現(xiàn)了數(shù)據(jù)點(diǎn)的水平和垂直梯度的提取,這樣大大減少了FPGA內(nèi)嵌乘法器的使用,也減少了結(jié)果誤差的舍入;另一方面,為了構(gòu)建3×3的圖像矩陣,就需要構(gòu)建圖像數(shù)據(jù)緩沖模塊,方案一中采用的圖像數(shù)據(jù)緩沖模塊完全采用3個(gè)taps的數(shù)據(jù)緩沖模塊,每個(gè)taps的深度均為圖片行的像素點(diǎn),這樣FPGA的邏輯資源很大程度上就被浪費(fèi)了,影響FPGA的性能.為了改善這種狀況,方案二只調(diào)用了2個(gè)taps的數(shù)據(jù)緩沖模塊,并結(jié)合輸入的數(shù)據(jù)端口利用FIFO的思想構(gòu)成3×3矩陣,很好地改善了方案一中的占用邏輯資源較大的情況.綜合對(duì)比兩種方案,改善后的方案明顯比方案一效果好,消耗資源少,耗時(shí)少,并且處理效果較好,完全滿足實(shí)時(shí)圖像處理的要求.

[1] Fang H R.The application of FPGA in image edge detection [J].Information and Communication,2015(1):9-11.

[2] Yan L,Lei B,Ding W,et al.Based on local adaptive thresholds edge detection of color image color difference [J].Journal of Electronics and Information,2012,34(9):2058-2063.

[3] Liao C Z.A Sobel edge-detection algorithm based on FPGA and emulation [J].Journal of Yangtze University,2015,12 (7):37-40.

[4] Pan M,Chen Y,Li Q.Design of image sampling system based on FPGA [J].Research and Development,2012,31 (3):58-61.

[5] Ruan Q Q,Ruan Y Z.Image processing [M].Beijing:Publishing House of Electronics Industry,2014.

[6] Xia Y W.Verilog course in digital systems design [M].Beijing:Beihang University Press,2008.

[7] Zhang Z Y.The master of Matlab [M].Beijing:Beihang University Press,2011.

[8] Zhang Y J.Design and algorithm realization of FPGA-based image processing systems[D].Chongqing:Chongqing University,2006.

[9] Wu Y.Basic algorithms of digital image processing based on FPGA design and implementation [D].Harbin:Harbin Institute of Technology,2008.

(責(zé)任編輯：包震宇)

Two kinds of implementations of sobel edge detection algorithmbased on field programmable gate array

Zhang Haibin, Zhu Sulei*, Xu Mingliang

(College of Information,Mechanical and Electrical Engineering,Shanghai Normal University,Shanghai 200234,China)

In this paper,two kinds of edge detection scheme based on Field Programmable Gate Array(FPGA) are realized and analyzed by using the Sobel operator.In view of the design which utilizes the intellectual property(IP) cores embedded in the Quartus II has some disadvantages such as more resources are consumed、process is relatively slow and so on,an improved scheme which improves the first design′s shortcomings is proposed.Simulation and verification results of these two schemes which are combined with Matlab and Modelsim show that the improved Sobel operator scheme is better than the previous scheme designed by using IP cores embedded in the Quartus II,achieving a good image detection and reducing errors.

edge detection; field programmable gate array; digital image processing

2015-11-10

上海師范大學(xué)樣級(jí)科研項(xiàng)目(SK201410)

張海斌(1989-),男,碩士研究生,主要從事圖像處理及模式識(shí)別方面的研究.E-mail:838026281@qq.com

導(dǎo)師簡(jiǎn)介: 朱蘇磊(1975-),女,副教授,主要從事圖像處理及嵌入式方面的研究.E-mail:suleizhu@163.com

TN 911.73

A

1000-5137(2017)02-0247-07

*通信作者