程 彪，黃 魯

(中國(guó)科學(xué)技術(shù)大學(xué) 信息科學(xué)技術(shù)學(xué)院，安徽 合肥 230026)

0 引言

特征點(diǎn)檢測(cè)是計(jì)算機(jī)視覺中非常重要的技術(shù)之一，在物體檢測(cè)、視覺跟蹤、三維重建等領(lǐng)域都有很廣泛的應(yīng)用[1]。目前最常用的特征點(diǎn)檢測(cè)算法有FAST、Harris、Shi-Tomasi和SUSAN等。FAST特征點(diǎn)檢測(cè)算法由于結(jié)構(gòu)簡(jiǎn)單[2]，在同步定位與地圖構(gòu)建技術(shù)(Simultaneous Localization And Mapping，SLAM)[3]中得到了較廣泛應(yīng)用。

傳統(tǒng)的FAST特征點(diǎn)檢測(cè)算法都是基于通用處理器CPU實(shí)現(xiàn)的，通用處理器按順序串行執(zhí)行指令。圖像處理算法中的所有元素均可以實(shí)行同樣操作，存在固有的并行性。FPGA硬件配置靈活，具有并行執(zhí)行優(yōu)勢(shì)[4]，在大數(shù)據(jù)量圖像處理領(lǐng)域有著天然優(yōu)勢(shì)。FAST特征點(diǎn)檢測(cè)算法結(jié)構(gòu)簡(jiǎn)單，只涉及整數(shù)運(yùn)算，非常適合用FPGA來實(shí)現(xiàn)。對(duì)于相同大小的圖片，F(xiàn)PGA實(shí)現(xiàn)的FAST特征點(diǎn)檢測(cè)算法在主頻小于ARM的情況下仍可以獲得可觀的算法運(yùn)算速度提升。

1 FAST特征點(diǎn)檢測(cè)算法原理

FAST特征提取的主要原理為比較候選像素與其周圍一圈像素的灰度值，若灰度值相差較大的像素能組成連續(xù)且弧長(zhǎng)大于圓周長(zhǎng)3/4的圓弧，則是FAST角點(diǎn)[5]。FAST-9主要步驟為：

(1)如圖1所示，在一個(gè)以像素p為中心、半徑為3的Bresenham圓上，有16個(gè)像素點(diǎn)(p1，p2，…，p16)，定義一個(gè)閾值t。

(2)計(jì)算p與p1、p9、p5、p13的像素差，若它們的絕對(duì)值至少有3個(gè)大于閾值，則當(dāng)做候選點(diǎn)，進(jìn)行第3步；否則，直接排除。

圖1 FAST特征點(diǎn)Bresenham圓示意圖

(3)計(jì)算p與p1到p16這16個(gè)點(diǎn)的像素差，若它們的絕對(duì)值至少有連續(xù)9個(gè)大于閾值，則是特征點(diǎn)；否則，直接排除掉。

(4)進(jìn)行非極大值抑制，計(jì)算特征點(diǎn)的FAST得分函數(shù)值V(如公式(1)所示)，若以特征點(diǎn)p為中心的一個(gè)鄰域(如7×7)內(nèi)有多個(gè)特征點(diǎn)，而且p點(diǎn)得分值為鄰域所有特征點(diǎn)中響應(yīng)值最大的，則保留；否則，抑制。若鄰域內(nèi)只有一個(gè)特征點(diǎn)，則保留。

(1)

圖3 FAST特征點(diǎn)檢測(cè)算法模塊

2 系統(tǒng)設(shè)計(jì)方案

2.1 系統(tǒng)硬件結(jié)構(gòu)

系統(tǒng)的硬件結(jié)構(gòu)框圖如圖2所示，F(xiàn)PGA芯片通過SCCB接口對(duì)OV5640攝像頭的寄存器進(jìn)行配置，得到幀率為30 f/s、分辨率為480×272的灰度視頻圖像。DDR3存儲(chǔ)控制模塊通過配置FPGA內(nèi)置的MCB硬核將攝像頭采集的數(shù)據(jù)緩存到DDR3芯片中。

圖2 系統(tǒng)框圖

將DDR3圖像存儲(chǔ)空間分為兩塊，當(dāng)?shù)刂?開始的區(qū)域作為圖像數(shù)據(jù)寫地址的時(shí)候，地址2開始的區(qū)域就作為圖像的讀開始地址，等一幅圖像數(shù)據(jù)寫入DDR3完成后交換讀寫地址空間，這樣可以避免物體運(yùn)動(dòng)產(chǎn)生圖像拖影的現(xiàn)象。將讀取到的數(shù)據(jù)送入FAST特征提取算法模塊處理后再顯示，對(duì)于一幅圖像，將作為特征點(diǎn)的坐標(biāo)的像素置為8’b0，以便在LCD顯示屏上可以直觀觀察特征點(diǎn)。

2.2 FAST特征點(diǎn)提取算法硬件實(shí)現(xiàn)

FAST特征點(diǎn)提取算法總體硬件實(shí)現(xiàn)由7×7窗口生成模塊、FAST主模塊、特征點(diǎn)判斷模塊、自適應(yīng)閾值模塊、得分值計(jì)算模塊和非極大值抑制模塊構(gòu)成?？傮w硬件實(shí)現(xiàn)框圖如圖3所示。

系統(tǒng)的主要數(shù)據(jù)流如箭頭所示，從DDR3緩存中讀出來的像素?cái)?shù)據(jù)以串行的數(shù)據(jù)流方式傳入7×7窗口生成模塊。此后FAST主模塊在同一個(gè)時(shí)鐘沿并行地獲取中心像素值以及對(duì)應(yīng)的bresenham圓上的16個(gè)像素點(diǎn)，F(xiàn)AST主模塊用中心像素值與bresenham圓上的這些像素值作差值、比較等運(yùn)算，運(yùn)算結(jié)果傳入得分值計(jì)算模塊和特征點(diǎn)判斷模塊處理，非極大值抑制模塊對(duì)處理結(jié)果進(jìn)行比較運(yùn)算，得到最終的特征點(diǎn)，自適應(yīng)閾值模塊再對(duì)特征點(diǎn)進(jìn)行計(jì)數(shù)，設(shè)計(jì)自適應(yīng)閾值再傳回FAST主模塊。

2.2.17×7窗口生成模塊

7×7窗口生成模塊由6個(gè)深度為480、數(shù)據(jù)寬度為8的FIFO和49個(gè)8位寄存器構(gòu)成[6]，其結(jié)構(gòu)如圖4所示，F(xiàn)IFO的讀寫、寄存器的控制均由同一個(gè)時(shí)鐘信號(hào)控制，可以在同一個(gè)時(shí)鐘沿并行地獲取中心像素值以及對(duì)應(yīng)的bresenham圓上的16個(gè)像素點(diǎn)數(shù)據(jù)。隨著串行數(shù)據(jù)的輸入，模塊以滑動(dòng)窗口的形式(每個(gè)時(shí)鐘周期處理一個(gè)圖像窗口)完成整幅圖像的處理。

圖4 7×7窗口生成模塊

2.2.2FAST主模塊

7×7窗口生成模塊在同一個(gè)時(shí)鐘沿將中心元素center和圓周像素p_n(n=1,2，…，16)傳入FAST主模塊，實(shí)現(xiàn)圓周像素是否為亮、暗點(diǎn)的判斷。以亮點(diǎn)判斷為例，主模塊將p_n減center得到值S1_B，將S1_B減閾值得到值S2_B。如果S2_B大于0，則表示該點(diǎn)為亮點(diǎn)，將S2_B賦值給bright_n；否則，將bright_n賦0值。通過16組并行的硬件實(shí)現(xiàn)16個(gè)圓周像素的亮點(diǎn)判斷運(yùn)算。同理，暗點(diǎn)的判斷與亮點(diǎn)硬件結(jié)構(gòu)一致，只有暗點(diǎn)的S1_B值為center減p_n得到這一點(diǎn)不同?？傮w的硬件結(jié)構(gòu)如圖5所示。

圖5 FAST主模塊

串行處理器實(shí)現(xiàn)以上步驟至少需要2×16×3個(gè)指令周期，而FPGA硬件實(shí)現(xiàn)只要3個(gè)時(shí)鐘周期，利用面積換速度的方法實(shí)現(xiàn)了硬件加速[7]。

2.2.3特征點(diǎn)判斷模塊

對(duì)于FAST-9算法，圓環(huán)上具有9個(gè)以上的連續(xù)亮點(diǎn)或暗點(diǎn)的center像素即為特征點(diǎn)。特征點(diǎn)判斷模塊由FAST主模塊傳入的bright[15:0]和dark[15:0]來實(shí)現(xiàn)判斷。bright[15:0]=16’b0000_1111_0000_1111表示圓環(huán)上的p1～p4，p9～p12為亮點(diǎn)，其余的為非亮點(diǎn)；同理dark[15:0]=16’b0000_1111_0000_1111表示圓環(huán)上的p1～p4,p9～p12為暗點(diǎn)，其余的為非暗點(diǎn)。

硬件實(shí)現(xiàn)上，分為并行的兩路實(shí)現(xiàn)，一路實(shí)現(xiàn)亮點(diǎn)匹配，另一路實(shí)現(xiàn)暗點(diǎn)匹配。以亮點(diǎn)bright[15:0]為例，b1，b2，…，b16為其16個(gè)bit位元素。match信號(hào)的生成邏輯如公式(2)所示，match1為1時(shí)，表示p1～p9滿足亮點(diǎn)匹配。同理可以得到match2,match3,…,match16。亮點(diǎn)匹配的邏輯實(shí)現(xiàn)如圖6所示，由16路4級(jí)并行邏輯實(shí)現(xiàn)。FPGA硬件是通過兩級(jí)6輸入查找表實(shí)現(xiàn)9輸入match1函數(shù)，如圖7所示，時(shí)延僅為兩級(jí)查找表表延時(shí)，顯著加快了運(yùn)算速度。

match1=b1 &b2 &…b9

match2=b2 &b3 &…b10

…

match16=b16 &b1 &...b8

(2)

圖6 亮點(diǎn)匹配的邏輯實(shí)現(xiàn)圖

圖7 match1函數(shù)FPGA硬件實(shí)現(xiàn)

滿足亮點(diǎn)匹配信號(hào)由16個(gè)match信號(hào)的或運(yùn)算得出，如公式(3)所示。

is_corner_b=match1|match2...|match16

(3)

特征點(diǎn)判斷模塊的最終輸出信號(hào)iscorner為兩路匹配判斷電路或運(yùn)算計(jì)算結(jié)果，如公式(4)所示。

is_corner=is_corner_b|is_corner_d

(4)

2.2.4得分值計(jì)算模塊

得分值計(jì)算模塊對(duì)FAST主模塊的輸出o_bright_n[9:0]、o_dark_n[9:0](n=1,2，…，16)進(jìn)行操作。硬件實(shí)現(xiàn)上也分為兩路，一路實(shí)現(xiàn)o_bright_n的16個(gè)元素相加，另一路實(shí)現(xiàn)o_dark_n的16個(gè)元素相加，如公式(5)所示。

sum_b=o_bright_1+...+o_bright_16

sum_d=o_dark_1+...+o_dark_16

(5)

sum_b的硬件實(shí)現(xiàn)結(jié)構(gòu)如圖8所示，sum_d的硬件結(jié)構(gòu)與其一致。采用了4級(jí)流水線實(shí)現(xiàn)了16個(gè)數(shù)的加法操作[8]，相比于串行處理器(需要16次取數(shù)據(jù)指令，15次加法指令)加快了計(jì)算sum_b的運(yùn)算速度。最后的得分值輸出結(jié)果為sum_b和sum_d之間的較大值，在硬件上用一個(gè)比較器實(shí)現(xiàn)。

圖8 sun_b信號(hào)生成電路結(jié)構(gòu)圖

2.2.5非極大值抑制模塊

非極大值抑制模塊將得分值計(jì)算模塊的輸出數(shù)據(jù)corner_score[12:0]輸入到7×7窗口生成模塊。7×7窗口生成模塊由6個(gè)深度為480、數(shù)據(jù)寬度為16的FIFO和49個(gè)13位寄存器構(gòu)成。從上級(jí)模塊輸入的is_corner為候選特征點(diǎn)指示信號(hào),高電平有效。

對(duì)于窗口中的49個(gè)數(shù)據(jù)，如果窗口中心元素大于其他所有48個(gè)元素，則保留中心元素為特征點(diǎn)，置corner_right為1，否則則抑制，置corner_right為0。完成這些操作需要48次比較運(yùn)算和47次與運(yùn)算。

2.2.6自適應(yīng)閾值模塊

實(shí)際工程應(yīng)用中，多樣化環(huán)境會(huì)使傳統(tǒng)的單一閾值方法失效，環(huán)境紋理豐富程度變化時(shí)，F(xiàn)AST算法提取角點(diǎn)數(shù)目波動(dòng)范圍非常大，不利于后續(xù)算法處理?；贠RB-SLAM的定位算法中FAST算法提取300～500個(gè)特征點(diǎn)是一個(gè)比較理想的結(jié)果。

本文采用了自適應(yīng)閾值的方法來解決該問題。只需人為設(shè)定初始閾值，后續(xù)一幀圖像的閾值由前一幀的閾值和前一幀圖像檢測(cè)到的特征點(diǎn)數(shù)目來得到[9](如表1所示)。如果檢測(cè)的特征點(diǎn)數(shù)目偏少，程序會(huì)根據(jù)檢測(cè)到的特征點(diǎn)數(shù)目區(qū)間將自適應(yīng)閾值減去相應(yīng)值，反之增加相應(yīng)的值。當(dāng)前后幀圖像差異較大時(shí)，得到最終的自適應(yīng)閾值過程的迭代次數(shù)會(huì)增加。將兩幅紋理不同的圖片開始閾值都設(shè)為25，經(jīng)程序運(yùn)行后得到的結(jié)果如圖9(紋理豐富)、圖10(紋理稀少)所示，這表明了該方法可以很好地得到滿足條件的自適應(yīng)閾值。硬件實(shí)現(xiàn)上使用計(jì)數(shù)器對(duì)corner_right計(jì)數(shù)來得到特征點(diǎn)數(shù)目，自適應(yīng)閾值使用5路數(shù)字比較器比較后對(duì)前一幀閾值作相應(yīng)增減得到。

表1 當(dāng)前幀閾值與前一幀閾值th的關(guān)系

圖9 自適應(yīng)閾值為39 檢測(cè)出特征點(diǎn)數(shù)為490

圖10 自適應(yīng)閾值為12 檢測(cè)出特征點(diǎn)數(shù)為331

3 實(shí)驗(yàn)驗(yàn)證分析

本文實(shí)現(xiàn)的FAST特征點(diǎn)檢測(cè)算法的硬件平臺(tái)為Xlinx公司Spartan6系列xc6slx45芯片，采用ISE14.7軟件和Verilog語(yǔ)言來編寫程序。用ISim進(jìn)行功能仿真，用FPGA作板級(jí)驗(yàn)證。

3.1 功能仿真

由于直接觀察波形圖結(jié)果不夠直觀，testbench中將為角點(diǎn)的像素坐標(biāo)處像素值設(shè)為255，其余像素值保持不變，將處理好的圖片數(shù)值保存在txt文件中，再利用MATLAB將txt文件中的像素?cái)?shù)據(jù)恢復(fù)成圖片[8]，恢復(fù)出的結(jié)果如圖11所示，由仿真圖可知，可以很好地檢測(cè)出FAST特征點(diǎn)。

3.2 板級(jí)驗(yàn)證

FPGA硬件平臺(tái)實(shí)時(shí)檢測(cè)特征點(diǎn)效果如圖12所示為了直觀顯示效果，將圖12局部放大如圖13所示，黑點(diǎn)為實(shí)時(shí)檢測(cè)到的特征點(diǎn)。板級(jí)驗(yàn)證結(jié)果表明FPGA實(shí)現(xiàn)的FAST特征點(diǎn)檢測(cè)精度和實(shí)時(shí)性均良好。

圖11 MATLAB還原結(jié)果

圖12 實(shí)時(shí)檢測(cè)特征點(diǎn)示意圖

圖13 局部放大示意圖

3.3 速度比較

對(duì)于同樣的算法，圖片都為大小480×272的灰度圖。由仿真得知，F(xiàn)PGA處理一幅圖片需要132 976個(gè)時(shí)鐘周期，系統(tǒng)時(shí)鐘為100 MHz，處理時(shí)間為1.33 ms。ARM處理器為三星S5PV210，主頻達(dá)1 GHz，其處理時(shí)間為5.01 ms(算法為OpenCV-2.4.10標(biāo)準(zhǔn)庫(kù)函數(shù)，運(yùn)行時(shí)間為50次運(yùn)行時(shí)間平均值)。在主頻只有ARM 1/10的情況下，F(xiàn)PGA達(dá)到了3.8倍的運(yùn)行時(shí)間性能提升。

4 結(jié)論

本文提出了一種基于FPGA的FAST特征點(diǎn)檢測(cè)算法硬件實(shí)現(xiàn)方法。實(shí)驗(yàn)結(jié)果表明，該硬件實(shí)現(xiàn)能根據(jù)環(huán)境紋理的豐富程度設(shè)計(jì)自適應(yīng)閾值，使每幅圖片都可以檢測(cè)到300～500個(gè)特征點(diǎn)。該實(shí)現(xiàn)能夠充分發(fā)揮FPGA硬件平臺(tái)的并行執(zhí)行優(yōu)勢(shì)，相比通用處理器，算法的運(yùn)算速度有了大幅提高。該實(shí)現(xiàn)對(duì)FPGA實(shí)現(xiàn)基于模板圖像處理算法具有通用性，對(duì)FPGA實(shí)現(xiàn)圖像處理算法的加速具有重要意義。