基于FPGA的特征降維算法實現

周 曉，黃德湖，鄭曉亮

(武漢理工大學 機電工程學院，湖北 武漢 430070)

圖像特征提取是實現目標識別算法的一個重要步驟，許多優秀的目標識別算法[1-4]依靠提取有效的圖像特征獲得了極高的識別率。為了獲取出色的識別精度，所提取的特征信息必須足夠豐富，這使得算法需要消耗大量的資源進行運算。巨大的計算量在帶來優秀的性能表現的同時，也帶來了計算資源和時間效率的問題。FPGA(field programmable gatearray)因為其高并行和高吞吐率的特點，使得許多圖像處理算法以其作為實現平臺進行優化加速[5-6]。

在特征提取算法中，圖像的高維特征包含的信息并不完全是研究人員所需要的，在每維度的數據間還存在冗余特征。這些冗余信息不僅妨礙對有用的信息進行篩選，還使數據量變得十分龐大，占用了更多的存儲空間，浪費了大量的系統資源。PCA(prinicpal component analysis)技術可使高維數據變為維數較低的數據，并包含了原始數據中的大部分信息，在圖像特征提取的領域得到了廣泛應用。

LARK(local adaptive regression kernel)算子是韓國學者Hae Jong Seo提出的一種圖像特征提取方法[4]。相比許多基于直方圖統計的特征描述算子，LARK算子提取的特征信息更為豐富[7]。然而，將所有的特征信息一起用于分析，又會造成信息冗余度過高的問題。因此，在提取出原始LARK特征后，需要進行PCA降維計算，以避免后續分析的計算資源過度消耗。PCA算法中的協方差運算、特征向量分解和線性空間投影等計算需要消耗大量的運算資源，并且需要消耗大量的運算時間。筆者利用PCA算法原理，對圖像LARK特征進行降維，并提出了相應的硬件架構，極大地提高了算法的運行效率。

1 算法原理

1.1 LARK特征簡介

LARK是基于經典核回歸的一種特征描述方法,算法的核心思想是通過梯度圖像的自相似性來獲取穩定的特征[8-9]。在LARK算子的理論中，圖像是一個三維曲面，通過像素點的空間曲線距離來衡量像素的相似性。其特征提取公式為：

(1)

式中：l∈[1,2,…，P],P為選定窗口內像素的總數;Cl是基于像素梯度建立的協方差矩陣；Δxl是以x點坐標為中心的像素點坐標矩陣。x為像素點空間坐標，s為像素點的距離。在圖像的每一個像素點處，協方差矩陣Cl都是不同的。因此，LARK算子并不是單一的利用高斯回歸核進行計算，而是根據每一像素點處的梯度大小進行回歸核形狀的調整。在這樣的特性下，LARK描述的特征信息是十分豐富的。

LARK算子描述了在選定的窗口內，窗口中心像素與其他像素的相似性。因此，窗口尺寸大小對計算量的影響十分巨大。在本文的研究中，選取了尺寸為5×5的窗口，對應的原始LARK特征為25維。

1.2 PCA算法

PCA算法是一種用于降低數據集維度的統計技術。它的主要思想是，在盡可能減少信息損失的情況下，找到一種降低數據維度的方法。直觀地說，PCA技術通過查找數據中方差最大的方向，根據數據的重要性對數據進行排序。PCA的使用可以看作是一種線性變換，它為原始數據集選擇一個新的坐標系，其中數據集中方差最大的方向被選擇為第一主軸。PCA計算公式如下：

K=VΛV-1

(2)

Y=XVT

(3)

式中：K為數據X的協方差矩陣；V為正交矩陣，并且矩陣中的列向量為K的特征向量。數據在矩陣V上的投影結果為數據的主成分。新的數據集Y包含了了原始數據集X的主要信息，其信息維度由矩陣V的維度決定。

通常情況下，用特征向量對應的特征值大小代表數據在此方向上的能量，當矩陣V中的特征向量對應的能量值超過設定值時，就可將矩陣V當做數據的投影矩陣。

PCA算法的主要目的是尋找一種線性變換關系，使得原先具有p維度的數據集X，經過變換后可以表示為具有更低維度l的數據集Y。算法的整體架構如圖1所示。

圖1 算法整體架構

PCA算法的計算步驟如下：

(1)組織數據集。假設數據集是一系列向量組合x1,x2,…,xn,其中xi是一個具有p個元素的向量，可將向量組表示為一個維度為n×p的矩陣。

(3)計算數據集的去均值特征。將數據集的每一列都減去當列的平均值，將計算結果儲存在矩陣X=X-huT,其中h為n維列向量，并且每個元素值為1。

(4)計算協方差矩陣。計算數據集的均方差矩陣C=XTX,其中XT為矩陣X的轉置矩陣。

(5)計算協方差矩陣的特征值與特征向量。將矩陣C對角化：V-1CV=D,其中D為一個對角矩陣，矩陣對角線上的值為矩陣C的特征值。矩陣V由矩陣C的p個特征向量構成，特征值和特征向量一一對應。

(6)重組特征值和特征向量。將特征值降序排列，并將特征值對應的特征向量也進行相同的調整，確保特征值與特征向量的對應關系。

(7)選擇特征向量作為新的基向量。選取特征值最大的L個特征向量作為新的數據集Y的基向量，并將這些向量組成投影矩陣W。

(8)利用投影矩陣對數據進行映射。投影矩陣的每個向量為協方差矩陣的特征向量，以這些向量作為新的數據集的基向量，可以得到原始數據中具有最大代表性的數據。新的數據集Y=XWT,數據的維度為n×L。

2 算法的FPGA架構

算法的硬件整體架構如圖2所示。系統中的數據輸入預先存在DDR3芯片中，通過VDMA將數據傳送到FPGA內部進行處理。系統采用Xilinx公司ZYNQ系列的FPGA芯片作為核心處理器件，該芯片內嵌了一個雙核的ARM處理器，在整個系統中主要起到配置和調試作用。硬件邏輯處理模塊主要負責PCA算法的降維運算，并將最終結果通過數據總線與ARM端進行交互。

圖2 硬件整體架構

系統架構主要是基于ARM處理器和FPGA硬件邏輯實現的。值得注意的是，為了提高系統的運算時間效率，內嵌的ARM處理器不參與數據降維過程的運算。系統主要計算均由FPGA實現，在運算過程中使用流水線運算和并行運算等方法，極大地提高了系統的時間效率。

系統中的FPGA數據流圖如圖3所示。上位機將原始數據通過調試接口置入DDR3內存，進行定點化處理后再將數據流導入降維計算硬件模塊進行處理。最后，計算結果通過VDMA搬運到DDR內存，再由上位機讀取計算結果進行分析。整個系統中，原始數據格式為32位浮點數據，為了發揮FPGA的運算優勢，文中將數據轉換為32位定點數。

圖3 系統數據流圖

硬件處理模塊如圖4所示，主要包括定點數轉換模塊、協方差矩陣求解模塊、SVD分解模塊、RAM模塊和重映射模塊，對于定點數運算，FPGA在計算周期和運算資源的消耗上能顯現出其突出的優勢。定點數轉換模塊負責將VDMA傳輸過來的數據進行定點化處理，以節省內存資源及其后續運算資源的占用。定點數據再依次經過協方差運算、SVD分解和重映射運算得到計算結果。在協方差運算、SVD分解和重映射運算時，需要對數據進行緩存。因此用RAM資源作為共享內存，作為各個模塊的輸出緩存。

圖4 硬件處理模塊

協方差矩陣的計算過程如圖5所示。首先，輸入數據在存入RAM的同時進行累加運算，在所有數據輸入完成后，進行除法運算得到數據的平均值。接著從RAM中讀出緩存的輸入數據，計算去均值結果，并將結果存入RAM覆蓋原先的輸入數據。最后，將RAM中緩存的矩陣進行乘法計算得到協方差矩陣并將其輸出。至此，系統的RAM模塊中保留了數據的去均值特征。

圖5 協方差矩陣計算模塊

圖6展示了SVD模塊對協方差矩陣進行SVD分解的過程。在SVD模塊中，運用Jacobi算法對矩陣進行迭代運算[10]。模塊主要包括：輸入選擇器、輸入端口RAM、向量點乘模塊、CORDIC模塊、旋轉計算模塊和范數計算模塊。協方差矩陣數據通過輸入選擇器緩存到雙端口RAM中，作為迭代運算的起始數據。在數據輸入完成后，從RAM中讀取向量列進行點乘運算，再通過CORDIC模塊計算得出向量旋轉角度，根據角度進行旋轉運算。旋轉運算后，兩個向量更新為互相垂直的向量，再將其通過輸入選擇器寫入到RAM中代替原來的向量列。在進行若干輪迭代運算后，可以在模塊中的雙端口RAM中得到協方差矩陣的特征值和特征向量。

圖6 SVD模塊

在完成協方差矩陣的特征值分解后，得到了一組特征向量可以作為降維數據的向量空間。將數據的去均值特征在新的向量上進行投影運算即可得到數據的主成分。重映射的計算架構如圖7所示。重映射模塊中主要是數據的乘加法運算，因此其硬件結構主要由乘法器和加法器構成。對于輸入的兩個向量A=[a0,a1,…，an]和B=[b0,b1,…，bn]，輸入數據經過乘法器計算后得到第一層的結果為[a0×b0,a1×b1,…，an×bn]。結構的第二層由相鄰的兩個結果加法運算得到，在第三層進行第二層結果的加法運算，直到所有數據全部累加完成。為了利用FPGA的優勢，需要對這個過程進行流水線優化，在每一層的計算結果完成后用寄存器進行緩存，可以是后續的計算結果流水輸出。

圖7 重映射模塊

3 實驗結果

設計選用了Xilinx公司ZYNQ系列的FPGA芯片作為算法的實現平臺。整個算法的設計過程均由Verilog語言實現，芯片的內置ARM處理器在整個算法過程中負責調試配置等功能。算法運算過程中對FPGA的片上RAM資源有較大需求，因此設計平臺選取了Xilinx公司的TySOM-2-7Z045/7Z100開發板，利用的硬件資源主要包括XC7Z100FPGA芯片和DDR內存。

系統輸入為一個320×320分辨率圖像的25維LARK特征，如圖8所示。圖像的LARK特征雖然包含了豐富的信息，但是有些特征圖的差別很小。如果把所有的維度特征都作為圖像的特征描述，在LARK特征的后續應用中將造成信息冗余，計算量極度增大等問題。利用前述架構對其進行降維運算，可以極大地提高算法的時間效率。

圖8 輸入圖像的LARK特征

圖9為圖像特征進行降維后的數據信息保留度。在本文的設計中，降維計算后保留了前6維特征數據。進行PCA算法后，前6個維度的數據包含了原始數據90%的信息，同時減少了76%的數據量。算法開始前，需要將圖像特征預存在DDR中，通過VDMA將DDR數據搬運到FPGA硬件實現模塊處理。最后，硬件輸出結果通過VDMA搬運到DDR中，由芯片內置ARM處理器和調試接口與上位機進行交互，硬件的輸出結果如圖10所示。

圖9 維度序數與信息保留度關系

圖10 硬件輸出

表1為架構主要模塊的硬件資源利用情況。由表1可知在協方差矩陣模塊和重映射模塊中，為了提高計算的時間效率，進行了大量的并行運算和流水運算，因此消耗的硬件資源很大。其中協方差模塊中的RAM資源存儲了輸入的特征數據，被整個算法實現過程共享。

表1 硬件資源利用情況

表2為在不同平臺下算法的運行時間。測試平臺為搭載了I5-6300HQ處理器的PC，其主頻為2.2 GHz，擁有16 GB的內存。在PC上，測得算法的運行時間為108.28 ms。在同樣的輸入數據下，文中提出的硬件架構只需要8.67 ms的運行時間，相對于PC處理速度大幅提升。

表2 算法運行時間

4 結論

筆者針對圖像LARK特征存在的信息冗余特點，利用PCA算法原理，提出了基于FPGA的LARK特征降維算法實現。提出的架構主要包括：協方差矩陣計算模塊、SVD分解模塊以及重映射模塊。對圖像的LARK特征進行降維計算，提取出顯著特征。通過實驗表明，所設計的硬件架構比PC的時間效率大幅提高，可應用在實時性要求較高的場合。