高效Prewitt邊緣檢測算法的NEON實(shí)現(xiàn)

王 譽(yù) 博

(浙江大學(xué) 超大規(guī)模集成電路設(shè)計(jì)研究所,杭州 310027)

1 引 言

邊緣檢測能夠在保留圖像重要結(jié)構(gòu)的基礎(chǔ)上極大地減少圖像的數(shù)據(jù)量[1],被廣泛使用于輪廓檢測,模式識(shí)別[2],區(qū)域分割[3],圖像增強(qiáng)[3]等應(yīng)用場景中.由于邊緣檢測的運(yùn)算數(shù)據(jù)量極大,必須采取相應(yīng)的方案進(jìn)行改進(jìn)與加速.近些年來,相關(guān)領(lǐng)域的專家學(xué)者都圍繞加快邊緣檢測開展了大量的工作.在有一個(gè)CPU(Intel Core2 CPU 6600 @ 2.40 GHz,2 GB RAM)和GPU(NVIDIA GeForce 8800 GTX,768 MB global memory(not overclocked))的平臺(tái)上,Luo等人用利用Opencv對(duì)分辨率為512x512的圖像進(jìn)行邊緣檢測處理,花費(fèi)的時(shí)間達(dá)8.28ms[4].Ogawa等人搭建了一個(gè)擁有CPU(Intel Xeon E5540,頻率2.0GHz,內(nèi)存6GB)和GPU(Tesla C1060,240個(gè)核心,頻率1.3GHz)的平臺(tái),利用該平臺(tái)對(duì)一張分辨率為10240x10240的圖片進(jìn)行邊緣檢測處理需要444.29ms[5].通過利用CPU+GPU的平臺(tái)可以有效對(duì)圖像進(jìn)行實(shí)時(shí)邊緣處理.而隨著嵌入式系統(tǒng)的高速發(fā)展,在邊緣檢測方面,如何使嵌入式系統(tǒng)擁有與CPU+GPU平臺(tái)相當(dāng)?shù)倪\(yùn)算能力成為了極大的挑戰(zhàn).基于此,本文在利用Prewitt算子來實(shí)現(xiàn)邊緣檢測的基礎(chǔ)上,提出了一種基于NEON協(xié)處理器的邊緣檢測算法.通過實(shí)驗(yàn)證明,在Xilinx的Zedboard平臺(tái)上,本算法在僅利用ARM CortexTM-A9中的一個(gè)核心(頻率666MHz)的情況下就取得了和CPU+GPU平臺(tái)相當(dāng)?shù)倪\(yùn)算速度.

2 系統(tǒng)結(jié)構(gòu)

本系統(tǒng)是基于Xilinx公司的Zedboard開發(fā)板完成.Zedboard上集成了一顆雙核心的ARM CortexTM-A9處理器(包含NEON協(xié)處理器),512MB的DDR3和可編程門陣列等.

系統(tǒng)的整體結(jié)構(gòu)如圖1所示,主要包括:IMX219攝像頭模塊、MIPI信號(hào)處理模塊、ARM A9軟件處理模塊、HDMI發(fā)射器以及DELL顯示器.A9處理器通過I2C協(xié)議配置IMX219攝像頭模塊,使之輸出圖像數(shù)據(jù).MIPI信號(hào)處理模塊獲取IMX219輸出的MIPI信號(hào),并將獲取到的RAW8格式的圖像數(shù)據(jù)轉(zhuǎn)換成RGB格式的數(shù)據(jù)并通過AXI協(xié)議將圖像信息存入到DDR3中.A9處理器從DDR3中獲取圖像信息并執(zhí)行Prewitt運(yùn)算,在完成運(yùn)算之后將數(shù)據(jù)回寫至DDR3中.A9是一顆雙核心的CPU,本文僅使用了其中的一個(gè)核心.

圖1 系統(tǒng)框圖

HDMI發(fā)射器通過AXI協(xié)議獲取DDR3中經(jīng)過A9處理后的圖像信息,并將之轉(zhuǎn)換成TMDS信號(hào)發(fā)送給DELL顯示器.最后能夠在DELL顯示器上看到相應(yīng)的圖像.

3 NEON協(xié)處理器簡介

NEON技術(shù)是ARM Cortex-A系列處理器的128位SIMD(Single Instruction Multiple Data,單指令多數(shù)據(jù))架構(gòu)擴(kuò)展,相比于SISD(Single Instruction Single Data,單指令單數(shù)據(jù))架構(gòu),SIMD的一條指令就可以同時(shí)完成多個(gè)相同的運(yùn)算,從而極大地提高運(yùn)算效率.

NEON協(xié)處理器支持的數(shù)據(jù)類型包括32-bit單精度浮點(diǎn)數(shù),8、16、32和64-bit無符號(hào)/有符號(hào)整形.NEON協(xié)處理器擁有的寄存器有三類:32個(gè)單字寄存器(s0-s31)、32個(gè)雙字寄存器(d0-d31)和16個(gè)四字寄存器(q0-q15),這些寄存器并不是完全獨(dú)立的,具體的映射關(guān)系如圖2所示.以q0為例,q0可以拆分成d0和d1,d0則可以拆分成s0和s1.

圖2 NEON寄存器組*http://infocenter.arm.com/help/topic/com.arm.doc.dht0002a/DHT0002A_introducing_neon.pdf

3 Prewitt算法

3.1 Prewitt算法原理

圖像中物體邊界處的灰度變化往往十分劇烈,邊緣檢測的任務(wù)就是找到圖像上灰度變化劇烈的點(diǎn).經(jīng)典的邊緣檢測算法有很多,如:Reberts算子,Prewitt算子,Sobel算子,Laplacian算子,Canny算子等.本文采用Prewitt算法來完成邊緣檢測的工作.

Prewitt算法借助式(1)X方向的Prewitt算子和式(2)Y方向的Prewitt算子來完成計(jì)算.對(duì)于單個(gè)像素點(diǎn)而言,在計(jì)算時(shí)需要獲取該像素點(diǎn)周圍八個(gè)點(diǎn)的灰度值,再結(jié)合式(1)和式(2)即可算出X方向和Y方向的梯度值,式(3)和式(4)即為計(jì)算公式.最后用式(5)即可以計(jì)算出該像素點(diǎn)的最終梯度值.

(1)

(2)

Dx(i,j)= (G(i-1,j+1)+G(i,j+1)+G(i+1,j+1))-

(G(i-1,j-1)+G(i,j-1)+G(i+1,j-1))

(3)

Dy(i,j)= (G(i-1,j-1)+G(i-1,j)+G(i-1,j+1))-

(G(i+1,j-1)+G(i+,j)+G(i+1,j+1))

(4)

(5)

通過分析常規(guī)Prewitt算法的計(jì)算過程,制約Prewitt算法運(yùn)算速度的主要瓶頸有以下兩點(diǎn):

1)為了計(jì)算一個(gè)點(diǎn)X方向與Y方向的梯度值,需要額外讀取該像素點(diǎn)周圍八個(gè)點(diǎn)的像素值,并且需要計(jì)算這八個(gè)點(diǎn)的灰度值.在這一過程中存在數(shù)據(jù)的重復(fù)讀取和冗余計(jì)算.

以圖3為例,在計(jì)算點(diǎn)(2,2)和點(diǎn)(2,3)的Prewitt算子結(jié)果時(shí)都需要讀取點(diǎn)(1,2)、(1,3)、(3,2)、(3,3)的像素值并且計(jì)算這些點(diǎn)的灰度值.

圖3 部分圖像數(shù)據(jù)

2)Prewitt算子的計(jì)算過程中也存在一定程度的冗余計(jì)算.以圖3為例,當(dāng)計(jì)算點(diǎn)(2,2)的梯度值時(shí),需要計(jì)算點(diǎn)(3,2)與點(diǎn)(3,3)的灰度和,而在計(jì)算點(diǎn)(2,3)的梯度值時(shí)同樣需要計(jì)算點(diǎn)(3,2)與點(diǎn)(3,3)的灰度和.同樣的道理,在計(jì)算點(diǎn)(2,2)和點(diǎn)(3,2)的梯度值時(shí),都需要計(jì)算一次點(diǎn)(2,1)和點(diǎn)(3,1)的灰度和.

3.2 改進(jìn)的Prewitt算法

為解決上一小節(jié)中提出的兩點(diǎn)缺陷,本文提出一種高效的Prewitt邊緣檢測算法.傳統(tǒng)的Prewitt算法以像素點(diǎn)為計(jì)算單位,本文算法以像素塊為單位進(jìn)行Prewitt計(jì)算.這樣可以大幅度減少冗余的計(jì)算和冗余的數(shù)據(jù)讀取.考慮到CPU和NEON協(xié)處理器的資源數(shù)量,本文以4x6個(gè)像素點(diǎn)作為一個(gè)像素塊進(jìn)行Prewitt算子計(jì)算,以下為本文算法的計(jì)算流程:

1)灰度計(jì)算.首先從內(nèi)存中獲取6x8個(gè)像素點(diǎn)的RGB數(shù)據(jù),并用式(6)完成灰度值的計(jì)算,并將結(jié)果存放在NEON寄存器q7到q12中.圖4中(1,1)等點(diǎn)即代表一個(gè)像素點(diǎn)的灰度值.

G=(R×38+G×75+B×15)/128

(6)

2)X方向一階梯度計(jì)算.圖4給出了計(jì)算X方向梯度的計(jì)算流程,總共分為三個(gè)步驟：

①加法計(jì)算.計(jì)算q7+q8+q9,并將結(jié)果存放在q3中,同理可得q4、q5和q6.以圖4中一個(gè)值[3,1]為例,其值為步驟1中(2,1),(3,1),(4,1)的和.

②轉(zhuǎn)置操作.改變q3到q6這四個(gè)寄存器中值所處的位置,為之后的減法運(yùn)算提供支持.此步驟不改變寄存器中值的大小,只改變這些值存儲(chǔ)的位置.

③減法運(yùn)算.計(jì)算減法過程,并將運(yùn)算結(jié)果存儲(chǔ)在寄存器d0到d5中.以圖4中一個(gè)值{2,2}為例,其值是[2,3]與[2,1]的差.其余點(diǎn)的計(jì)算方式也是如此.

圖4 X方向梯度計(jì)算流程

3)Y方向的一階梯度計(jì)算.Y方向一階梯度計(jì)算過程和X方向的計(jì)算過程大體一致,先是做減法運(yùn)算,然后做轉(zhuǎn)置操作,最后做加法運(yùn)算.

4)開方運(yùn)算.首先用式(7)計(jì)算出X方向梯度與Y方向梯度的平方和,然后用式(8)來完成開方這一過程,從而最終獲得Prewitt運(yùn)算結(jié)果.

(7)

(8)

表1給出了本文算法和原始算法之間運(yùn)算量的對(duì)比.根據(jù)表1計(jì)算可得,原始算法每次只能計(jì)算1個(gè)像素點(diǎn)的Prewitt值,完成該過程需要讀取8個(gè)像素點(diǎn)的數(shù)據(jù),同時(shí)需要執(zhí)行27次加減法,26次乘法,1次開方運(yùn)算.采用本文算法則可以一次性計(jì)算出24個(gè)像素點(diǎn)的Prewitt值,完成該過程需要讀取48個(gè)像素點(diǎn)的數(shù)據(jù),執(zhí)行38次加減法,30次乘法,6次開方運(yùn)算.因此對(duì)于平均每個(gè)像素點(diǎn)而言,采用本文算法后數(shù)據(jù)讀取量為原始算法的25%,加減法數(shù)為原始算法的5.9%,乘法數(shù)量為原始算法的4.8%,開方數(shù)量為原始算法的25%.以上數(shù)據(jù)表明采用本文算法之后能夠大幅度減少運(yùn)算量以及數(shù)據(jù)讀取量.

表1 運(yùn)算量對(duì)比

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

本文以Xilinx公司生產(chǎn)的Zedboard開發(fā)板為設(shè)計(jì)平臺(tái),采用Vivado設(shè)計(jì)套件(版本2016.2)完成相關(guān)IP的設(shè)計(jì)和軟件代碼的編寫,最終完成了平臺(tái)的設(shè)計(jì)與搭建.在完成綜合之后,從表2中可以看到各個(gè)資源的使用情況,其中LUT(Look-Up-Table,顯示查找表)占用了3.59%,LUTRAM(由LUT構(gòu)建的分布式RAM)占用0.97%,FF(Flip Flop,觸發(fā)器)占用了2.02%,BRAM(塊RAM,容量比LUTRAM大)占用了1.43%,IO(輸入輸出,用于與外部外設(shè)通信)占用了16%,BUFG(用于管理時(shí)鐘,確保時(shí)鐘到達(dá)各個(gè)單元的延遲和抖動(dòng)最小)占用了3.13%.

表2 片上資源占用情況

搭建完整個(gè)系統(tǒng)并且運(yùn)行相應(yīng)代碼之后,在顯示器上即可顯示經(jīng)過邊緣檢測之后的圖像.圖5(a)為攝像頭獲取的原始圖像,圖5(b)為原始Prewitt算法計(jì)算后得到的圖像,圖5(c)為經(jīng)過本文邊緣檢測算法計(jì)算后得到的圖像.可以表明利用本文算法獲取的邊緣檢測結(jié)果和用原始算法計(jì)算得到的結(jié)果完全一致.此外,為了驗(yàn)證本文邊緣檢測的質(zhì)量,本文將數(shù)據(jù)源從攝像頭換為普通的圖像(圖5(d)所示),從而得到通過本文邊緣檢測算法計(jì)算后的圖像(圖5(f)所示).同時(shí)利用MATLAB對(duì)圖5(d)進(jìn)行邊緣檢測,得到圖5(e).通過對(duì)比圖5(e)和圖5(f)的細(xì)節(jié)部分,可以表明利用本文算法計(jì)算得到的邊緣檢測結(jié)果的質(zhì)量和MATLAB計(jì)算得到的結(jié)果一致.

圖5 實(shí)驗(yàn)結(jié)果

為驗(yàn)證本文提出的算法的計(jì)算效率,本文對(duì)不同分辨率的視頻進(jìn)行實(shí)時(shí)邊緣檢測.表3表明,采用NEON協(xié)處理器后可以有效提高運(yùn)算速度,而采用本文算法之后可以進(jìn)一步提高運(yùn)算速度.

表3 運(yùn)行時(shí)間比較(ms)

為進(jìn)一步驗(yàn)證本文提出的算法與CPU+GPU運(yùn)行平臺(tái)之間的差距,本文在表4中列出了一些CPU+GPU平臺(tái)進(jìn)行邊緣檢測的時(shí)間.通過對(duì)比表3和表4的數(shù)據(jù)可以表明,通過本文算法可以使得嵌入式平臺(tái)取得和CPU+GPU平臺(tái)相當(dāng)?shù)倪\(yùn)算速度.

表4 CPU+GPU平臺(tái)下的運(yùn)行時(shí)間(ms)

5 結(jié) 論

本文提出了一種基于NEON協(xié)處理器的高效Prewitt邊緣檢測算法.在經(jīng)過合理的算法設(shè)計(jì)和優(yōu)化之后,本文大幅度提高了嵌入式系統(tǒng)計(jì)算Prewitt的計(jì)算效率,使得嵌入式平臺(tái)也能夠?qū)崟r(shí)進(jìn)行圖像的邊緣檢測.在與其他主頻更高、功耗更高的CPU+GPU平臺(tái)比較之后可以表明,通過本文算法可以使得嵌入式平臺(tái)取得和CPU+GPU平臺(tái)相當(dāng)?shù)倪\(yùn)算速度.