基于FPGA的特征降維算法實(shí)現(xiàn)

周 曉，黃德湖，鄭曉亮

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

圖像特征提取是實(shí)現(xiàn)目標(biāo)識(shí)別算法的一個(gè)重要步驟，許多優(yōu)秀的目標(biāo)識(shí)別算法[1-4]依靠提取有效的圖像特征獲得了極高的識(shí)別率。為了獲取出色的識(shí)別精度，所提取的特征信息必須足夠豐富，這使得算法需要消耗大量的資源進(jìn)行運(yùn)算。巨大的計(jì)算量在帶來(lái)優(yōu)秀的性能表現(xiàn)的同時(shí)，也帶來(lái)了計(jì)算資源和時(shí)間效率的問(wèn)題。FPGA(field programmable gatearray)因?yàn)槠涓卟⑿泻透咄掏侣实奶攸c(diǎn)，使得許多圖像處理算法以其作為實(shí)現(xiàn)平臺(tái)進(jìn)行優(yōu)化加速[5-6]。

在特征提取算法中，圖像的高維特征包含的信息并不完全是研究人員所需要的，在每維度的數(shù)據(jù)間還存在冗余特征。這些冗余信息不僅妨礙對(duì)有用的信息進(jìn)行篩選，還使數(shù)據(jù)量變得十分龐大，占用了更多的存儲(chǔ)空間，浪費(fèi)了大量的系統(tǒng)資源。PCA(prinicpal component analysis)技術(shù)可使高維數(shù)據(jù)變?yōu)榫S數(shù)較低的數(shù)據(jù)，并包含了原始數(shù)據(jù)中的大部分信息，在圖像特征提取的領(lǐng)域得到了廣泛應(yīng)用。

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

1 算法原理

1.1 LARK特征簡(jiǎn)介

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

(1)

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

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

1.2 PCA算法

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

K=VΛV-1

(2)

Y=XVT

(3)

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

通常情況下，用特征向量對(duì)應(yīng)的特征值大小代表數(shù)據(jù)在此方向上的能量，當(dāng)矩陣V中的特征向量對(duì)應(yīng)的能量值超過(guò)設(shè)定值時(shí)，就可將矩陣V當(dāng)做數(shù)據(jù)的投影矩陣。

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

圖1 算法整體架構(gòu)

PCA算法的計(jì)算步驟如下：

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

(3)計(jì)算數(shù)據(jù)集的去均值特征。將數(shù)據(jù)集的每一列都減去當(dāng)列的平均值，將計(jì)算結(jié)果儲(chǔ)存在矩陣X=X-huT,其中h為n維列向量，并且每個(gè)元素值為1。

(4)計(jì)算協(xié)方差矩陣。計(jì)算數(shù)據(jù)集的均方差矩陣C=XTX,其中XT為矩陣X的轉(zhuǎn)置矩陣。

(5)計(jì)算協(xié)方差矩陣的特征值與特征向量。將矩陣C對(duì)角化：V-1CV=D,其中D為一個(gè)對(duì)角矩陣，矩陣對(duì)角線上的值為矩陣C的特征值。矩陣V由矩陣C的p個(gè)特征向量構(gòu)成，特征值和特征向量一一對(duì)應(yīng)。

(6)重組特征值和特征向量。將特征值降序排列，并將特征值對(duì)應(yīng)的特征向量也進(jìn)行相同的調(diào)整，確保特征值與特征向量的對(duì)應(yīng)關(guān)系。

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

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

2 算法的FPGA架構(gòu)

算法的硬件整體架構(gòu)如圖2所示。系統(tǒng)中的數(shù)據(jù)輸入預(yù)先存在DDR3芯片中，通過(guò)VDMA將數(shù)據(jù)傳送到FPGA內(nèi)部進(jìn)行處理。系統(tǒng)采用Xilinx公司ZYNQ系列的FPGA芯片作為核心處理器件，該芯片內(nèi)嵌了一個(gè)雙核的ARM處理器，在整個(gè)系統(tǒng)中主要起到配置和調(diào)試作用。硬件邏輯處理模塊主要負(fù)責(zé)PCA算法的降維運(yùn)算，并將最終結(jié)果通過(guò)數(shù)據(jù)總線與ARM端進(jìn)行交互。

圖2 硬件整體架構(gòu)

系統(tǒng)架構(gòu)主要是基于ARM處理器和FPGA硬件邏輯實(shí)現(xiàn)的。值得注意的是，為了提高系統(tǒng)的運(yùn)算時(shí)間效率，內(nèi)嵌的ARM處理器不參與數(shù)據(jù)降維過(guò)程的運(yùn)算。系統(tǒng)主要計(jì)算均由FPGA實(shí)現(xiàn)，在運(yùn)算過(guò)程中使用流水線運(yùn)算和并行運(yùn)算等方法，極大地提高了系統(tǒng)的時(shí)間效率。

系統(tǒng)中的FPGA數(shù)據(jù)流圖如圖3所示。上位機(jī)將原始數(shù)據(jù)通過(guò)調(diào)試接口置入DDR3內(nèi)存，進(jìn)行定點(diǎn)化處理后再將數(shù)據(jù)流導(dǎo)入降維計(jì)算硬件模塊進(jìn)行處理。最后，計(jì)算結(jié)果通過(guò)VDMA搬運(yùn)到DDR內(nèi)存，再由上位機(jī)讀取計(jì)算結(jié)果進(jìn)行分析。整個(gè)系統(tǒng)中，原始數(shù)據(jù)格式為32位浮點(diǎn)數(shù)據(jù)，為了發(fā)揮FPGA的運(yùn)算優(yōu)勢(shì)，文中將數(shù)據(jù)轉(zhuǎn)換為32位定點(diǎn)數(shù)。

圖3 系統(tǒng)數(shù)據(jù)流圖

硬件處理模塊如圖4所示，主要包括定點(diǎn)數(shù)轉(zhuǎn)換模塊、協(xié)方差矩陣求解模塊、SVD分解模塊、RAM模塊和重映射模塊，對(duì)于定點(diǎn)數(shù)運(yùn)算，F(xiàn)PGA在計(jì)算周期和運(yùn)算資源的消耗上能顯現(xiàn)出其突出的優(yōu)勢(shì)。定點(diǎn)數(shù)轉(zhuǎn)換模塊負(fù)責(zé)將VDMA傳輸過(guò)來(lái)的數(shù)據(jù)進(jìn)行定點(diǎn)化處理，以節(jié)省內(nèi)存資源及其后續(xù)運(yùn)算資源的占用。定點(diǎn)數(shù)據(jù)再依次經(jīng)過(guò)協(xié)方差運(yùn)算、SVD分解和重映射運(yùn)算得到計(jì)算結(jié)果。在協(xié)方差運(yùn)算、SVD分解和重映射運(yùn)算時(shí)，需要對(duì)數(shù)據(jù)進(jìn)行緩存。因此用RAM資源作為共享內(nèi)存，作為各個(gè)模塊的輸出緩存。

圖4 硬件處理模塊

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

圖5 協(xié)方差矩陣計(jì)算模塊

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

圖6 SVD模塊

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

圖7 重映射模塊

3 實(shí)驗(yàn)結(jié)果

設(shè)計(jì)選用了Xilinx公司ZYNQ系列的FPGA芯片作為算法的實(shí)現(xiàn)平臺(tái)。整個(gè)算法的設(shè)計(jì)過(guò)程均由Verilog語(yǔ)言實(shí)現(xiàn)，芯片的內(nèi)置ARM處理器在整個(gè)算法過(guò)程中負(fù)責(zé)調(diào)試配置等功能。算法運(yùn)算過(guò)程中對(duì)FPGA的片上RAM資源有較大需求，因此設(shè)計(jì)平臺(tái)選取了Xilinx公司的TySOM-2-7Z045/7Z100開(kāi)發(fā)板，利用的硬件資源主要包括XC7Z100FPGA芯片和DDR內(nèi)存。

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

圖8 輸入圖像的LARK特征

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

圖9 維度序數(shù)與信息保留度關(guān)系

圖10 硬件輸出

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

表1 硬件資源利用情況

表2為在不同平臺(tái)下算法的運(yùn)行時(shí)間。測(cè)試平臺(tái)為搭載了I5-6300HQ處理器的PC，其主頻為2.2 GHz，擁有16 GB的內(nèi)存。在PC上，測(cè)得算法的運(yùn)行時(shí)間為108.28 ms。在同樣的輸入數(shù)據(jù)下，文中提出的硬件架構(gòu)只需要8.67 ms的運(yùn)行時(shí)間，相對(duì)于PC處理速度大幅提升。

表2 算法運(yùn)行時(shí)間

4 結(jié)論

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