圖像特征匹配算法的FPGA 實現*

陳 超

(東南大學網絡與信息中心，江蘇 南京210096)

近年來，無人機遙感技術中的圖像識別技術在航天軍事、農業監測等領域發揮了不可替代的作用，尤其是在城市規劃、環境檢測、地圖測繪、地形勘探等方面有著更為廣泛的應用[1-2]。 在惡劣工作環境下，利用無人機圖像識別系統拍攝的圖像往往存在圖像縮放旋轉[3]、輕微抖動[4]、噪聲干擾[5]、非線性畸變[6]、布局重疊[7]、圖像序列獲取不完整[8]等問題。 為了減小上述影響，SIFT 算法[9-10](Scale Invariant Feature Transform，尺度不變特征變換匹配算法)應運而生。 SIFT 算法能在保證上述大部分現象穩定運行的同時繼續提高數據獲取的精確度和系統魯棒性，極大地提高人們的工作效率。 但SIFT 算法存在閾值過多的弊端，即計算效率低，實時性不夠理想。 因此對SIFT 算法進行優化具有重要意義。

目前SIFT 算法大多應用在電腦主機、DSP 等平臺上。 由于運用SIFT 算法進行圖像配準計算較為復雜[11-13]，在上述平臺上運行效率較差，本設計給出了基于FPGA(Field Programmable Gate Array，現場可編程門陣列)平臺實現SIFT 算法的運行架構方案。 該方案的實現能提高圖像數據獲取的及時性和連續性，具有一定的推廣價值。

1 SIFT 算法

SIFT 算法是David Lowe[14]在2004 年提出的用于圖像處理領域的一種可擴展局部特征描述子。 在應對圖像平移旋轉、尺度縮放、明暗變化、仿射變換等情形時，其具有良好的不變性與抗噪能力。 SIFT 算法運算復雜，但能獲得大量的特征向量，能充分達到特征匹配的需求，經優化后甚至可以滿足系統實時性的要求。 SIFT 算法流程可簡要概述為如下四步。

(1)尺度空間的構建:在實現尺度空間時通常使用DoG(Difference of Gaussian，高斯差分函數)來表示，首先通過連續減小原始圖像(降采樣)的順序獲得從大到小不同尺寸的一系列圖像。 原始圖像用作金字塔的底層，每次降采樣獲得的新參照用作原圖像的上一層。 原始圖像的尺寸和頂部圖像的尺寸共同確定了金字塔中的層數。 隨后，為反映尺度連續性，對高斯金字塔進行高斯濾波。 如圖1 所示，高斯模糊被用于金字塔每層中具有不同參數的圖像。 金字塔每層的多張高斯模糊圖像被集體分為一組(Octave)。

圖1 高斯金字塔示意圖

最后，為得到DoG 尺度空間，利用不同尺度的高斯差分核與輸入圖像I(x，y)卷積生成高斯圖像差分，如式(1)所示。

(2)尺度空間極值檢測:特征值由差異空間的局部特征值形成。 通過比較每個像素及其周圍每一個鄰域像素點來查找差異函數的特征值，以查看它與其參照圖和比例域的相鄰點大小是否一致。 如圖2 所示:中間檢測點與相同比例的8 個相鄰值和上下相鄰尺度的9 個值相比，保證在尺度范圍和二維圖像范圍中都檢測到特征值。 此外，受邊緣響應的影響，由此產生的離散空間的特征值不是真正的特征值，還需對標度空間DoG 函數進行曲線擬合，進而提高特征值的準確度和穩定性。

圖2 極值點檢測示意圖

(3)特征點定位:要使關鍵描述符具有旋轉不變性，有必要為每個關鍵點分配參考方向。 圖像梯度用于找到鄰域中結構的穩定方向。 如果在差分金字塔中檢測到特征值，則采集并處理其所在高斯金字塔相鄰窗口中像素的方向分布特征和梯度。 之后，處理鄰域中的像素的梯度和方向以形成直方圖。 如圖3 所示，梯度直方圖分為8 列(箱)，范圍為0 到360°，每列45°。 直方圖峰值表示關鍵值處的鄰域梯度的方向，并且特征值的主方向由直方圖中的峰值方向表示。對于具有相同梯度值的多個峰的特征值，它們將處于同樣的坐標和比例。 在不同方向上創建不同特征值能夠顯著增強特征值配準的穩定性。

圖3 特征點梯度直方圖統計

(4)特征點方向確定及描述子生成:首先根據特征值的方向旋轉坐標軸，保證旋轉不變性，旋轉結果如圖4 所示。

圖4 特征點鄰域旋轉結果

由左圖坐標旋轉到右圖坐標轉換公式如式(2)所示:

然后為每個特征點生成SIFT 描述符。 描述符使用臨界點標度空間中的4×4 窗口計算的八個方向的梯度數據，由4×4×8＝128 維向量表示，如圖5 所示。

最后按特征點的尺度對特征描述向量進行規范化。 如式(3)所示。

圖5 128 維SIFT 向量生成圖

式中:Ij表示規范化后的SIFT 特征向量，wj表示未規范化的SIFT 特征向量。

在實際應用中，SIFT 算法還需進行特征點配準。 為了減少錯誤匹配的可能性，采用歐氏距離來作為SIFT 描述子相似度的判別依據。 式(4)給出了歐氏距離的計算公式:

2 SIFT 配準硬件整體構架

通過FPGA 開發平臺設計SIFT 算法整體構架，設計流程主要包括電路設計和輸入，時序仿真，電路綜合優化，以及集成功能仿真，程序板級驗證，編譯和程序調試。 工程師在分析要實現的電路功能時通常采用自頂向下的設計方法，這樣利于模塊劃分和軟件維護，提升可移植性和仿真效率。 考慮到FPGA 內部資源的特性，并行設計思想更為重要。為此，本設計采用Verilog 語言進行程序編寫。

如圖6 所示，系統主要是通過FPGA 與PC 機實現通信。 FPGA 主要完成SIFT 關鍵值描述符的產生、存儲、位置坐標提取、注冊及通信功能等。 PC 機上主要是實現圖像配準結果的最終顯示。

圖6 SIFT 配準硬件整體構架圖

3 FPGA 通信模塊設計

本設計中，特征點描述子產生模塊將產生的特征點坐標順序儲存在FIFO(First Input First Output)存儲器中，而通信模塊的主要功能是將FIFO 中的坐標數據讀出來，并通過串口與PC 機通信，最終由Labview 界面接收和顯示。

3.1 UART 傳輸時序和發送程序

UART 是一種用于異步通信的通用串行數據總線。 在FPGA 開發板設計中，UART 用來與PC 進行通信，包括數據通信，命令和控制信息的傳輸等，特點是能進行雙向通信，能滿足FPGA 并行設計要求。

圖7 給出了UART 傳輸時序圖。 消息幀由低起始位、數據位和高位停止位組成。 接收器在找到消息幀起始位時開始與發送器時鐘頻率同步，表示傳輸數據的開始。 在數據位后加上奇偶校驗位，用于校驗數據傳輸的正確性。

圖7 UART 傳輸時序圖

UART 發送程序包含3 個程序，分別是時鐘產生程序(clkdiv.v)，串口發送程序(uarttx.v)和串口發送測試程序(testuart.v)。 程序clkdiv.v 用于處理波特率為9 600 bit/s 的時鐘信號和UART 接收信號，這里產生的時鐘clkout 是波特率的16 倍，以便在UART 接收期間接收的所有數據位有16 個時鐘樣本。 若對50 MHz 的系統時鐘進行分頻，則分頻系數為50 000 000/(16×9 600)＝325.52，取整為326。 uarttx.v 程序用于發送數據，在接收到數據傳輸命令之后，線路起始位的時間T被下拉，然后數據從低位到高位順序傳輸。 在一幀數據傳輸完成之后，發送停止位并等待下一個數據傳輸指令。 testuart.v 程序用于校準UART 發送模塊的正確性，通過產生串口發送數據(0～0xFF)和發送命令信號給串口發送模塊從而請求發送。

3.2 硬件介紹

硬件設計采用Silicon Labs CP2102 GM 芯片作為USB 和UART 電平轉換的橋梁，USB 接口規格為Micro USB 接口，用戶可以用一根開發板自帶的USB 線連接到PC 上進行數據通信。 串口部分的原理圖如圖8 所示:RXD 從PC 發送給FPGA，TXD 從FPGA 發送給PC，以此實現全雙工傳輸和接收。

圖8 USB 轉串口原理圖

3.3 頂層文件原理圖

圖9 給出了頂層文件原理圖。 各個模塊間用導線連接，其中testuart 的dataout[7..0]和uarttx 的datain[7..0]之間用Diagonal Bus Tool 連接；其他的線用Diagonal Node Tool 連接。 再添加2 個輸入端口分別連接到clk50 和rst＿n，同時添加一個輸出端口連接到tx，另外把每個端口的名字改成與實際的功能一致，便于后續程序的調試與擴展。

圖9 頂層文件原理圖

3.4 測試結果

使用USB 電纜連接PC 和FPGA 開發板，然后打開串行調試助手。 在串口調試助手中，可設置波特率、校驗位、數據位、停止位的一些信息。 另外，將端口設置為我們在設備管理器中看到的端口號。

下載uart＿tx.sof 到FPGA 開發板，我們可以在串口工具上看到從FPGA 開發板不斷發給PC 的從0 到FF 的16 進制的測試數據。

4 SIFT 配準算法FPGA 實現與結果

4.1 Sift＿top 頂層設計

SIFT 算法整體結構如圖10 所示，主要由高斯金字塔模塊，差分金字塔模塊，極值點檢測模塊等組成。 基于FPGA 開發平臺實現的圖像特征匹配算法以Sift＿top 作為頂層依次調用上述模塊。 最終通過通信模塊發送特征點坐標位置至串口，并導入MATLAB 顯示最終匹配結果。

圖10 SIFT 算法程序整體構圖

4.2 系統實現結果分析

首先根據特征匹配需求選擇一個FPGA 型號并對整體程序進行時序仿真。 由于SIFT 算法提高了準確度和系統魯棒性，因此程序在時序仿真和功能仿真過程中耗時較長。 從仿真結果我們可以看出硬件資源的消耗情況，從而可以判斷我們選擇的FPGA 型號是否滿足設計要求。

隨后進行功能仿真，這個過程主要是驗證程序時序仿真結果和算法整體架構是否符合FPGA 實現的要求。

圖11 給出了最終的實現平臺，以FPGA 開發板作為主控，利用通信模塊建立FPGA 開發板與PC機之間的通信。 將存儲在FIFO 中的特征點坐標提取出來并利用串口通信方式傳輸到上位機界面上進行顯示。

圖11 最終實現平臺

Labview 上位機界面采集的數據即為存儲在FIFO 中的特征點位置坐標，如表1 所示。

表1 上位機界面接收的特征點位置坐標

針對本設計利用MATLAB 平臺，讀取FPGA 運行程序得到的匹配特征點的位置坐標文件，并在原圖像上進行顯示，如圖12 所示。 由于FPGA 資源的限制，運行SIFT 后得到的特征點對數量較少，但保證了特征點準確度，因此基本滿足特征匹配的需求。

圖12 SIFT 算法FPGA 實現結果展示圖

5 結束語

本設計在研究了基于SIFT 圖像配準算法相關理論基礎上，對其進行了FPGA 硬件平臺實現。 主要完成了SIFT 算法的FPGA 整體結構設計以及FPGA 顯示與通信模塊設計。

本設計給出了高斯濾波、尺度空間、DoG 金字塔、特征點提取等模塊的設計方法與理念。 不但要求熟練進行FPGA 時序設計，還要熟悉相關配置和通信流程，才能進行二者的順利通信。 SIFT 算法中梯度直方圖的計算采用雙口RAM 進行同時讀取，而通訊模塊設計采用串口傳輸方式，合理分配了FPGA 的內部資源，提高了系統的實時性和連續性。利用MATLAB 平臺進行數據讀取，并將最終配準結果進行顯示。 在FPGA 開發板及上位機上實現圖像實時匹配驗證，匹配結果初步滿足實用要求，具有一定的應用價值。