圖像特征匹配算法的FPGA 實(shí)現(xiàn)*

陳 超

(東南大學(xué)網(wǎng)絡(luò)與信息中心，江蘇 南京210096)

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

目前SIFT 算法大多應(yīng)用在電腦主機(jī)、DSP 等平臺(tái)上。 由于運(yùn)用SIFT 算法進(jìn)行圖像配準(zhǔn)計(jì)算較為復(fù)雜[11-13]，在上述平臺(tái)上運(yùn)行效率較差，本設(shè)計(jì)給出了基于FPGA(Field Programmable Gate Array，現(xiàn)場(chǎng)可編程門陣列)平臺(tái)實(shí)現(xiàn)SIFT 算法的運(yùn)行架構(gòu)方案。 該方案的實(shí)現(xiàn)能提高圖像數(shù)據(jù)獲取的及時(shí)性和連續(xù)性，具有一定的推廣價(jià)值。

1 SIFT 算法

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

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

圖1 高斯金字塔示意圖

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

(2)尺度空間極值檢測(cè):特征值由差異空間的局部特征值形成。 通過(guò)比較每個(gè)像素及其周圍每一個(gè)鄰域像素點(diǎn)來(lái)查找差異函數(shù)的特征值，以查看它與其參照?qǐng)D和比例域的相鄰點(diǎn)大小是否一致。 如圖2 所示:中間檢測(cè)點(diǎn)與相同比例的8 個(gè)相鄰值和上下相鄰尺度的9 個(gè)值相比，保證在尺度范圍和二維圖像范圍中都檢測(cè)到特征值。 此外，受邊緣響應(yīng)的影響，由此產(chǎn)生的離散空間的特征值不是真正的特征值，還需對(duì)標(biāo)度空間DoG 函數(shù)進(jìn)行曲線擬合，進(jìn)而提高特征值的準(zhǔn)確度和穩(wěn)定性。

圖2 極值點(diǎn)檢測(cè)示意圖

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

圖3 特征點(diǎn)梯度直方圖統(tǒng)計(jì)

(4)特征點(diǎn)方向確定及描述子生成:首先根據(jù)特征值的方向旋轉(zhuǎn)坐標(biāo)軸，保證旋轉(zhuǎn)不變性，旋轉(zhuǎn)結(jié)果如圖4 所示。

圖4 特征點(diǎn)鄰域旋轉(zhuǎn)結(jié)果

由左圖坐標(biāo)旋轉(zhuǎn)到右圖坐標(biāo)轉(zhuǎn)換公式如式(2)所示:

然后為每個(gè)特征點(diǎn)生成SIFT 描述符。 描述符使用臨界點(diǎn)標(biāo)度空間中的4×4 窗口計(jì)算的八個(gè)方向的梯度數(shù)據(jù)，由4×4×8＝128 維向量表示，如圖5 所示。

最后按特征點(diǎn)的尺度對(duì)特征描述向量進(jìn)行規(guī)范化。 如式(3)所示。

圖5 128 維SIFT 向量生成圖

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

在實(shí)際應(yīng)用中，SIFT 算法還需進(jìn)行特征點(diǎn)配準(zhǔn)。 為了減少錯(cuò)誤匹配的可能性，采用歐氏距離來(lái)作為SIFT 描述子相似度的判別依據(jù)。 式(4)給出了歐氏距離的計(jì)算公式:

2 SIFT 配準(zhǔn)硬件整體構(gòu)架

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

如圖6 所示，系統(tǒng)主要是通過(guò)FPGA 與PC 機(jī)實(shí)現(xiàn)通信。 FPGA 主要完成SIFT 關(guān)鍵值描述符的產(chǎn)生、存儲(chǔ)、位置坐標(biāo)提取、注冊(cè)及通信功能等。 PC 機(jī)上主要是實(shí)現(xiàn)圖像配準(zhǔn)結(jié)果的最終顯示。

圖6 SIFT 配準(zhǔn)硬件整體構(gòu)架圖

3 FPGA 通信模塊設(shè)計(jì)

本設(shè)計(jì)中，特征點(diǎn)描述子產(chǎn)生模塊將產(chǎn)生的特征點(diǎn)坐標(biāo)順序儲(chǔ)存在FIFO(First Input First Output)存儲(chǔ)器中，而通信模塊的主要功能是將FIFO 中的坐標(biāo)數(shù)據(jù)讀出來(lái)，并通過(guò)串口與PC 機(jī)通信，最終由Labview 界面接收和顯示。

3.1 UART 傳輸時(shí)序和發(fā)送程序

UART 是一種用于異步通信的通用串行數(shù)據(jù)總線。 在FPGA 開(kāi)發(fā)板設(shè)計(jì)中，UART 用來(lái)與PC 進(jìn)行通信，包括數(shù)據(jù)通信，命令和控制信息的傳輸?shù)?，特點(diǎn)是能進(jìn)行雙向通信，能滿足FPGA 并行設(shè)計(jì)要求。

圖7 給出了UART 傳輸時(shí)序圖。 消息幀由低起始位、數(shù)據(jù)位和高位停止位組成。 接收器在找到消息幀起始位時(shí)開(kāi)始與發(fā)送器時(shí)鐘頻率同步，表示傳輸數(shù)據(jù)的開(kāi)始。 在數(shù)據(jù)位后加上奇偶校驗(yàn)位，用于校驗(yàn)數(shù)據(jù)傳輸?shù)恼_性。

圖7 UART 傳輸時(shí)序圖

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

3.2 硬件介紹

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

圖8 USB 轉(zhuǎn)串口原理圖

3.3 頂層文件原理圖

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

圖9 頂層文件原理圖

3.4 測(cè)試結(jié)果

使用USB 電纜連接PC 和FPGA 開(kāi)發(fā)板，然后打開(kāi)串行調(diào)試助手。 在串口調(diào)試助手中，可設(shè)置波特率、校驗(yàn)位、數(shù)據(jù)位、停止位的一些信息。 另外，將端口設(shè)置為我們?cè)谠O(shè)備管理器中看到的端口號(hào)。

下載uart＿tx.sof 到FPGA 開(kāi)發(fā)板，我們可以在串口工具上看到從FPGA 開(kāi)發(fā)板不斷發(fā)給PC 的從0 到FF 的16 進(jìn)制的測(cè)試數(shù)據(jù)。

4 SIFT 配準(zhǔn)算法FPGA 實(shí)現(xiàn)與結(jié)果

4.1 Sift＿top 頂層設(shè)計(jì)

SIFT 算法整體結(jié)構(gòu)如圖10 所示，主要由高斯金字塔模塊，差分金字塔模塊，極值點(diǎn)檢測(cè)模塊等組成。 基于FPGA 開(kāi)發(fā)平臺(tái)實(shí)現(xiàn)的圖像特征匹配算法以Sift＿top 作為頂層依次調(diào)用上述模塊。 最終通過(guò)通信模塊發(fā)送特征點(diǎn)坐標(biāo)位置至串口，并導(dǎo)入MATLAB 顯示最終匹配結(jié)果。

圖10 SIFT 算法程序整體構(gòu)圖

4.2 系統(tǒng)實(shí)現(xiàn)結(jié)果分析

首先根據(jù)特征匹配需求選擇一個(gè)FPGA 型號(hào)并對(duì)整體程序進(jìn)行時(shí)序仿真。 由于SIFT 算法提高了準(zhǔn)確度和系統(tǒng)魯棒性，因此程序在時(shí)序仿真和功能仿真過(guò)程中耗時(shí)較長(zhǎng)。 從仿真結(jié)果我們可以看出硬件資源的消耗情況，從而可以判斷我們選擇的FPGA 型號(hào)是否滿足設(shè)計(jì)要求。

隨后進(jìn)行功能仿真，這個(gè)過(guò)程主要是驗(yàn)證程序時(shí)序仿真結(jié)果和算法整體架構(gòu)是否符合FPGA 實(shí)現(xiàn)的要求。

圖11 給出了最終的實(shí)現(xiàn)平臺(tái)，以FPGA 開(kāi)發(fā)板作為主控，利用通信模塊建立FPGA 開(kāi)發(fā)板與PC機(jī)之間的通信。 將存儲(chǔ)在FIFO 中的特征點(diǎn)坐標(biāo)提取出來(lái)并利用串口通信方式傳輸?shù)缴衔粰C(jī)界面上進(jìn)行顯示。

圖11 最終實(shí)現(xiàn)平臺(tái)

Labview 上位機(jī)界面采集的數(shù)據(jù)即為存儲(chǔ)在FIFO 中的特征點(diǎn)位置坐標(biāo)，如表1 所示。

表1 上位機(jī)界面接收的特征點(diǎn)位置坐標(biāo)

針對(duì)本設(shè)計(jì)利用MATLAB 平臺(tái)，讀取FPGA 運(yùn)行程序得到的匹配特征點(diǎn)的位置坐標(biāo)文件，并在原圖像上進(jìn)行顯示，如圖12 所示。 由于FPGA 資源的限制，運(yùn)行SIFT 后得到的特征點(diǎn)對(duì)數(shù)量較少，但保證了特征點(diǎn)準(zhǔn)確度，因此基本滿足特征匹配的需求。

圖12 SIFT 算法FPGA 實(shí)現(xiàn)結(jié)果展示圖

5 結(jié)束語(yǔ)

本設(shè)計(jì)在研究了基于SIFT 圖像配準(zhǔn)算法相關(guān)理論基礎(chǔ)上，對(duì)其進(jìn)行了FPGA 硬件平臺(tái)實(shí)現(xiàn)。 主要完成了SIFT 算法的FPGA 整體結(jié)構(gòu)設(shè)計(jì)以及FPGA 顯示與通信模塊設(shè)計(jì)。

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