自適應閾值FAST特征點檢測算法的FPGA實現

程 彪，黃 魯

(中國科學技術大學 信息科學技術學院，安徽 合肥 230026)

0 引言

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

傳統的FAST特征點檢測算法都是基于通用處理器CPU實現的，通用處理器按順序串行執行指令。圖像處理算法中的所有元素均可以實行同樣操作，存在固有的并行性。FPGA硬件配置靈活，具有并行執行優勢[4]，在大數據量圖像處理領域有著天然優勢。FAST特征點檢測算法結構簡單，只涉及整數運算，非常適合用FPGA來實現。對于相同大小的圖片，FPGA實現的FAST特征點檢測算法在主頻小于ARM的情況下仍可以獲得可觀的算法運算速度提升。

1 FAST特征點檢測算法原理

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

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

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

圖1 FAST特征點Bresenham圓示意圖

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

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

(1)

圖3 FAST特征點檢測算法模塊

2 系統設計方案

2.1 系統硬件結構

系統的硬件結構框圖如圖2所示，FPGA芯片通過SCCB接口對OV5640攝像頭的寄存器進行配置，得到幀率為30 f/s、分辨率為480×272的灰度視頻圖像。DDR3存儲控制模塊通過配置FPGA內置的MCB硬核將攝像頭采集的數據緩存到DDR3芯片中。

圖2 系統框圖

將DDR3圖像存儲空間分為兩塊，當地址1開始的區域作為圖像數據寫地址的時候，地址2開始的區域就作為圖像的讀開始地址，等一幅圖像數據寫入DDR3完成后交換讀寫地址空間，這樣可以避免物體運動產生圖像拖影的現象。將讀取到的數據送入FAST特征提取算法模塊處理后再顯示，對于一幅圖像，將作為特征點的坐標的像素置為8’b0，以便在LCD顯示屏上可以直觀觀察特征點。

2.2 FAST特征點提取算法硬件實現

FAST特征點提取算法總體硬件實現由7×7窗口生成模塊、FAST主模塊、特征點判斷模塊、自適應閾值模塊、得分值計算模塊和非極大值抑制模塊構成。總體硬件實現框圖如圖3所示。

系統的主要數據流如箭頭所示，從DDR3緩存中讀出來的像素數據以串行的數據流方式傳入7×7窗口生成模塊。此后FAST主模塊在同一個時鐘沿并行地獲取中心像素值以及對應的bresenham圓上的16個像素點，FAST主模塊用中心像素值與bresenham圓上的這些像素值作差值、比較等運算，運算結果傳入得分值計算模塊和特征點判斷模塊處理，非極大值抑制模塊對處理結果進行比較運算，得到最終的特征點，自適應閾值模塊再對特征點進行計數，設計自適應閾值再傳回FAST主模塊。

2.2.17×7窗口生成模塊

7×7窗口生成模塊由6個深度為480、數據寬度為8的FIFO和49個8位寄存器構成[6]，其結構如圖4所示，FIFO的讀寫、寄存器的控制均由同一個時鐘信號控制，可以在同一個時鐘沿并行地獲取中心像素值以及對應的bresenham圓上的16個像素點數據。隨著串行數據的輸入，模塊以滑動窗口的形式(每個時鐘周期處理一個圖像窗口)完成整幅圖像的處理。

圖4 7×7窗口生成模塊

2.2.2FAST主模塊

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

圖5 FAST主模塊

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

2.2.3特征點判斷模塊

對于FAST-9算法，圓環上具有9個以上的連續亮點或暗點的center像素即為特征點。特征點判斷模塊由FAST主模塊傳入的bright[15:0]和dark[15:0]來實現判斷。bright[15:0]=16’b0000_1111_0000_1111表示圓環上的p1～p4，p9～p12為亮點，其余的為非亮點；同理dark[15:0]=16’b0000_1111_0000_1111表示圓環上的p1～p4,p9～p12為暗點，其余的為非暗點。

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

match1=b1 &b2 &…b9

match2=b2 &b3 &…b10

…

match16=b16 &b1 &...b8

(2)

圖6 亮點匹配的邏輯實現圖

圖7 match1函數FPGA硬件實現

滿足亮點匹配信號由16個match信號的或運算得出，如公式(3)所示。

is_corner_b=match1|match2...|match16

(3)

特征點判斷模塊的最終輸出信號iscorner為兩路匹配判斷電路或運算計算結果，如公式(4)所示。

is_corner=is_corner_b|is_corner_d

(4)

2.2.4得分值計算模塊

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

sum_b=o_bright_1+...+o_bright_16

sum_d=o_dark_1+...+o_dark_16

(5)

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

圖8 sun_b信號生成電路結構圖

2.2.5非極大值抑制模塊

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

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

2.2.6自適應閾值模塊

實際工程應用中，多樣化環境會使傳統的單一閾值方法失效，環境紋理豐富程度變化時，FAST算法提取角點數目波動范圍非常大，不利于后續算法處理。基于ORB-SLAM的定位算法中FAST算法提取300～500個特征點是一個比較理想的結果。

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

表1 當前幀閾值與前一幀閾值th的關系

圖9 自適應閾值為39 檢測出特征點數為490

圖10 自適應閾值為12 檢測出特征點數為331

3 實驗驗證分析

本文實現的FAST特征點檢測算法的硬件平臺為Xlinx公司Spartan6系列xc6slx45芯片，采用ISE14.7軟件和Verilog語言來編寫程序。用ISim進行功能仿真，用FPGA作板級驗證。

3.1 功能仿真

由于直接觀察波形圖結果不夠直觀，testbench中將為角點的像素坐標處像素值設為255，其余像素值保持不變，將處理好的圖片數值保存在txt文件中，再利用MATLAB將txt文件中的像素數據恢復成圖片[8]，恢復出的結果如圖11所示，由仿真圖可知，可以很好地檢測出FAST特征點。

3.2 板級驗證

FPGA硬件平臺實時檢測特征點效果如圖12所示為了直觀顯示效果，將圖12局部放大如圖13所示，黑點為實時檢測到的特征點。板級驗證結果表明FPGA實現的FAST特征點檢測精度和實時性均良好。

圖11 MATLAB還原結果

圖12 實時檢測特征點示意圖

圖13 局部放大示意圖

3.3 速度比較

對于同樣的算法，圖片都為大小480×272的灰度圖。由仿真得知，FPGA處理一幅圖片需要132 976個時鐘周期，系統時鐘為100 MHz，處理時間為1.33 ms。ARM處理器為三星S5PV210，主頻達1 GHz，其處理時間為5.01 ms(算法為OpenCV-2.4.10標準庫函數，運行時間為50次運行時間平均值)。在主頻只有ARM 1/10的情況下，FPGA達到了3.8倍的運行時間性能提升。

4 結論

本文提出了一種基于FPGA的FAST特征點檢測算法硬件實現方法。實驗結果表明，該硬件實現能根據環境紋理的豐富程度設計自適應閾值，使每幅圖片都可以檢測到300～500個特征點。該實現能夠充分發揮FPGA硬件平臺的并行執行優勢，相比通用處理器，算法的運算速度有了大幅提高。該實現對FPGA實現基于模板圖像處理算法具有通用性，對FPGA實現圖像處理算法的加速具有重要意義。