基于FPGA的KLT特征點(diǎn)多層次歸并排序

柴志雷，方萬元

江南大學(xué)物聯(lián)網(wǎng)技術(shù)應(yīng)用教育部工程研究中心，江蘇無錫 214122

◎圖形圖像處理◎

基于FPGA的KLT特征點(diǎn)多層次歸并排序

柴志雷，方萬元

江南大學(xué)物聯(lián)網(wǎng)技術(shù)應(yīng)用教育部工程研究中心，江蘇無錫 214122

KLT算法已在多個領(lǐng)域得到成功的應(yīng)用，其中特征點(diǎn)的排序是用來選擇好的特征點(diǎn)跟蹤的關(guān)鍵。針對傳統(tǒng)排序算法計(jì)算耗時、實(shí)時性差的缺點(diǎn)，提出一種可并行的多層次歸并排序算法并在FPGA中實(shí)現(xiàn)了其并行計(jì)算，同時分析了其周期精確的計(jì)算時間。結(jié)果表明該歸并排序算法可以O(shè)(N)的時間復(fù)雜度完成特征點(diǎn)的排序，能夠滿足高清分辨率的圖像/視頻數(shù)據(jù)中KLT特征點(diǎn)排序的實(shí)時性要求。

歸并排序；KLT；現(xiàn)場可編程門陣列（FPGA）排序

Kanade-Lucas-Tomasi（KLT）[1-4]算法是一種基于特征點(diǎn)的跟蹤算法。它的計(jì)算實(shí)時性和算法穩(wěn)定性使其在圖像處理的各個領(lǐng)域受到廣泛關(guān)注。KLT算法分為特征點(diǎn)提取和特征點(diǎn)跟蹤。特征點(diǎn)提取之后，選取合適的特征點(diǎn)是提高跟蹤魯棒性的關(guān)鍵。一般選取的方法利用特征點(diǎn)的特征值進(jìn)行排序，特征值較大的點(diǎn)為較好的跟蹤特征點(diǎn)。

隨著高清時代的到來，傳統(tǒng)的通用PC下的KLT算法對于高清資源，例如720P（1 280×720），1 080P（1 920× 1 080）的圖片處理無法再達(dá)到實(shí)時的要求。硬件平臺下的實(shí)時KLT算法就顯得尤為重要。FPGA提供了一個靈活的快速原型設(shè)計(jì)和并行計(jì)算的平臺。

排序算法在科學(xué)計(jì)算領(lǐng)域已經(jīng)有極其詳盡的研究，已有許多成熟的排序算法[5]。近年來，在不同的應(yīng)用下也提出了多種基于FPGA的排序方法。根據(jù)應(yīng)用的不同，基于FPGA的排序一般分為兩類：基于網(wǎng)絡(luò)的排序[6-7]和基于線性數(shù)組的排序[8]。

基于網(wǎng)絡(luò)的排序一般使用兩輸入的交換比較器來排序。Zhang Y.采用了固定大小的排序網(wǎng)絡(luò)[7]，分為輸入隊(duì)列、乒乓排序網(wǎng)絡(luò)和輸出檢測模塊。Martinez等[6]提出了應(yīng)用在塊排序壓縮上的網(wǎng)絡(luò)排序算法，采用了乒乓操作，實(shí)現(xiàn)數(shù)據(jù)循環(huán)處理。排序單元處理128個字符，最終的結(jié)果顯示可達(dá)到的最大時鐘頻率為50 MHz左右。基于線性數(shù)組的排序基于可擴(kuò)展的線性數(shù)組。Paraham，Kwai[8]采用比較/插入單元。每個單元包含比較器，乘法器和控制單元。可擴(kuò)展線性數(shù)組包含一系列的單元。

K.Ratnayake和A.Amer提出了計(jì)數(shù)排序算法[9]。不過是在BRAMS上實(shí)現(xiàn)排序算法，較為復(fù)雜。M.Edahiro[10]在EDK的開發(fā)環(huán)境下實(shí)現(xiàn)了并行的排序算法。吳彥宏的堆排序算法[11]是在SRAM上實(shí)現(xiàn)基于隊(duì)列的數(shù)據(jù)堆排序，實(shí)現(xiàn)較為復(fù)雜。

縱觀以上排序算法，有的是針對特殊應(yīng)用的排序，有的在對有限的數(shù)據(jù)排序的時候，資源利用率較高的同時，最大時鐘頻率很低。無法滿足對于高清實(shí)時圖片的特征點(diǎn)排序的要求。

本文首先分析了通用PC下的基于歸并操作的歸并排序，然后提出了一種基于FPGA的并行的多層次歸并排序結(jié)構(gòu)，并將其應(yīng)用于KLT特征點(diǎn)的排序。多層次歸并排序結(jié)構(gòu)由分為基于寄存器的歸并組件實(shí)現(xiàn)和基于FIFO的歸并組件構(gòu)成。可以根據(jù)FPGA開發(fā)板的寄存器和FIFO資源靈活配置組件。分析了多層次歸并排序結(jié)構(gòu)的時間周期。在ISIM仿真之后又在XC5VSX50T-1ff1136開發(fā)板上得以實(shí)現(xiàn)，在此基礎(chǔ)上分析了其在開發(fā)板上的資源利用率和最大時鐘周期。結(jié)果表明本文的歸并排序完全可以滿足高清圖片下KLT特征點(diǎn)的實(shí)時排序要求。

1 經(jīng)典歸并排序

1.1 歸并操作

歸并操作是將兩個（或兩個以上）有序隊(duì)列合并成一組新的有序表。若已知兩組有序隊(duì)列分別為1，3，5和2，4，6。如圖1所示為兩路歸并操作。A，B分別為已排完序的有序隊(duì)列。C為A，B的歸并結(jié)果。圖1為一次完整歸并操作的示意圖。

歸并步驟：

（1）分別取A，B的隊(duì)頭，設(shè)為a，b。比較a，b兩者的大小（比較操作）。

（2）將a，b中較大者出隊(duì)，放入緩存tmp中（出隊(duì)操作）。

（3）將tmp壓入C的隊(duì)尾（入隊(duì)操作）。

重復(fù)（1）～（3）直到A，B中一個為空。執(zhí)行（4）。

圖1 歸并操作示意圖

（4）若A/（B）為空，將B/（A）隊(duì)頭放入tmp中（出隊(duì)操作）。

（5）將tmp壓入C的隊(duì)尾（入隊(duì)操作）。

重復(fù)（5）～（6）直到A，B兩者都為空。

1.2 基于歸并操作的排序

設(shè)待排序的數(shù)列為D[n]，數(shù)列長度為N。

歸并排序步驟：

將D[n]分為N個已排完序的長度為1的隊(duì)列。兩兩之間運(yùn)行用1.1節(jié)中的歸并操作，合并成floor[n/2]個兩兩有序的隊(duì)列。

循環(huán)進(jìn)行上述步驟，兩兩之間進(jìn)行歸并操作，直到最后合并成一個N有序的隊(duì)列。

歸并排序的如圖2。

圖2 基于歸并操作的歸并排序

基于PC的歸并操作時間復(fù)雜度是O(N lg(N))。空間復(fù)雜度是O(N)。

2 可并行歸并排序

觀察經(jīng)典的PC下的歸并排序。隊(duì)列可以用寄存器或者FIFO實(shí)現(xiàn)。分別用寄存器和FIFO來實(shí)現(xiàn)歸并操作。當(dāng)待排序的隊(duì)列長度較小時使用基于寄存器的歸并。當(dāng)長度較大時使用基于FIFO的隊(duì)列。

歸并排序可以分解為若干層歸并操作，每一層的歸并操作的輸入是上一層的輸出。每層的歸并操作的差別是隊(duì)列的長度。歸并操作的硬件結(jié)構(gòu)為：（1）存儲的隊(duì)列；（2）比較器；（3）輔助的控制器。歸并操作的行為：（1）隊(duì)列的基礎(chǔ)行為（出隊(duì)，入隊(duì)，判斷空滿）；（2）歸并輸入；（3）歸并輸出。假設(shè)待排序的隊(duì)列長度為N。

2.1 基于寄存器的歸并操作

硬件結(jié)構(gòu)：

隊(duì)列：隊(duì)列長度為N：N個寄存器R1，R2，…，RN，其中R1為隊(duì)頭，RN為隊(duì)尾。

比較器：排序的數(shù)據(jù)位n位，采用n位的比較器。由上升沿觸發(fā)。

輔助控制器：每個隊(duì)列有一個標(biāo)記位FLAG，用一個標(biāo)記位FLAG來計(jì)數(shù)。初始為0，入隊(duì)時標(biāo)記加1，出隊(duì)時標(biāo)記減1。一組隊(duì)列（兩個）有一個標(biāo)記位BUFFFLAG。用來判斷組之間的輸入輸出切換，實(shí)現(xiàn)多組的乒乓操作。

行為描述（以下操作均為一個時間周期內(nèi)，由上升沿觸發(fā)）：

2.1.1 隊(duì)列行為

（1）出隊(duì)操作，OUT<=R1；R1<=R2；R2<=R3；…；R（N-1）<=RN。

（2）入隊(duì)操作，R1<=R2；R2<=R3；…；R（N-1）<= RN；RN<=IN。

（3）判斷隊(duì)列是否為空，F(xiàn)LAG為0時，隊(duì)列空；FLAG等于N，隊(duì)列滿。

2.1.2 歸并輸入

（1）在T∈[1，N]時，A依次入隊(duì)，隊(duì)列標(biāo)記位加1。組標(biāo)記位加1。

（2）在T∈[N+1，2N]時，B依次入隊(duì)，隊(duì)列標(biāo)記位加1。組標(biāo)記位加1。

2.1.3 歸并輸出

（1）在A，B非空時（即A_FLAG>0，B_FLAG>0），比較A，B的隊(duì)頭。輸出其中較大者；并將其隊(duì)頭出隊(duì)；將其隊(duì)列標(biāo)記減1。組標(biāo)記位減1。OUTENABLE為1。

（2）當(dāng)A，B任一為空時，依次輸出另一隊(duì)列，將其標(biāo)記減1，組標(biāo)記位減1。OUTENABLE為0；直到A，B均為空，OUTENABLE為0。

以上步驟可見基于寄存器的歸并操作步驟和經(jīng)典的PC操作幾乎一樣。因?yàn)樵诨诩拇嫫鲗?shí)現(xiàn)的時候，出隊(duì)，入隊(duì)，取隊(duì)頭，比較大小都可以在同一個時鐘周期內(nèi)實(shí)現(xiàn)，所以可以直接用時序邏輯實(shí)現(xiàn)。

硬件結(jié)構(gòu)圖如圖3所示。

2.2 基于FIFO的歸并操作

當(dāng)基于FIFO實(shí)現(xiàn)的時候，入隊(duì)，出隊(duì)要依靠W，R信號位來控制。當(dāng)一個上升沿后設(shè)置R=1，等一個時鐘周期才能獲得FIFO隊(duì)頭數(shù)據(jù)。若比較器用時序邏輯實(shí)現(xiàn)，則需要再等一個時鐘周期之后，才能比較兩個隊(duì)頭數(shù)據(jù)。那么數(shù)據(jù)的輸出比輸入多一倍的時鐘周期，無法組合成乒乓操作和并行的多層次結(jié)構(gòu)。所以將FIFO的控制用時序邏輯實(shí)現(xiàn)，而將比較器用組合邏輯實(shí)現(xiàn)。從而實(shí)現(xiàn)輸入，輸出的時鐘周期數(shù)相等。

硬件結(jié)構(gòu)：

隊(duì)列：FIFO隊(duì)列。FIFO長度為2M（大于等于N）。

FIFO的硬件結(jié)構(gòu)見圖4。有數(shù)據(jù)輸入輸出端口，和讀信號W，寫信號R，以及空滿信號。

圖3 乒乓操作的寄存器歸并操作

圖4 基于FIFO的歸并操作

比較器：排序的數(shù)據(jù)位n位，采用n位的比較器。采用組合邏輯實(shí)現(xiàn)。

時序邏輯輔助控制器：每個隊(duì)列有一個讀信號：W，寫信號R1，有一個標(biāo)記位FLAG，用一個標(biāo)記位FLAG來計(jì)數(shù)。初始為0，入隊(duì)時標(biāo)記加1，出隊(duì)時標(biāo)記減1。一組隊(duì)列（兩個）有一個標(biāo)記位BUFFFLAG。用來判斷組件的輸入輸出切換，實(shí)現(xiàn)多組的乒乓操作。

組合邏輯輔助控制器：每個隊(duì)列有一個額外的讀信號R1，由比較器的比較結(jié)果控制R2。

2.2.1 隊(duì)列行為

（1）出隊(duì)操作，F(xiàn)IFOIN<=IN；R<=1。

（2）入隊(duì)操作，OUT<=FIFOOUT；W<=1。

（3）判斷隊(duì)列是否為空，F(xiàn)IFO自己空滿信號。不過一般FIFO的長度和有序隊(duì)列的長度不等，所以還是用FLGA來判斷。FLAG為0時，隊(duì)列空；FLAG等于N，隊(duì)列滿。

2.2.2 歸并輸入

將A的隊(duì)頭和B的隊(duì)尾銜接。數(shù)據(jù)始終由A的隊(duì)尾插入，再由A的隊(duì)頭插入B的隊(duì)尾。AB由A_FIFOOUT和B_FIFOIN銜接。等價(jià)模型就是AB中間加了2個寄存器；具體見圖4。

（1）A的隊(duì)頭和B的隊(duì)尾銜接；B_FIFIIN<=A_ FIFOOUT。

（2）數(shù)據(jù)輸入A，T∈[1，2N]時，A_W<=1。

（3）數(shù)據(jù)輸入B，T∈[N+1，2N]時B_W<=1。

（4）AB中有2個寄存器，所以A的R信號要比B的W信號提取2個周期，即T∈[N-1，2N-2]時A_R1<=1。

2.2.3 歸并輸出

輸出的控制分為時序邏輯和組合邏輯，F(xiàn)IFO的控制用時序邏輯，由上升沿觸發(fā)。比較器及依據(jù)判斷結(jié)果設(shè)置R2，用組合邏輯。

時序邏輯：

當(dāng)T=2N-1，同時取AB隊(duì)頭，即A_R1<=1；B_R1<=1。

組合邏輯：

當(dāng)T∈[2N，4N]時，T時刻設(shè)置A，B的R2信號，T+1，A，B的隊(duì)頭更新，比較兩者大小，根據(jù)比較結(jié)果設(shè)置AB的R2信號。

（1）A_R<=A_R1|A_R2;B_R<=B_R1|B_R2。

（2）在A，B非空時（即A_FLAG>0，B_FLAG>0），比較A，B的隊(duì)頭。輸出其中較大者，并將其隊(duì)頭出隊(duì)，設(shè)置其R2等于1，將其標(biāo)記減1。組標(biāo)記位減1。OUTENABLE為1。

（3）當(dāng)A，B任一為空時，依次輸出另一隊(duì)列，將另一隊(duì)列標(biāo)記減1，組標(biāo)記位減1，設(shè)置另一隊(duì)列R2等于1，OUTENABLE為0。直到A，B均為空，OUTENABLE為0。

2.3 乒乓的歸并操作

如圖3，圖4中設(shè)置兩隊(duì)列，實(shí)現(xiàn)乒乓操作。用BUFFFLAG切換每一組的輸入輸出。

（1）T∈[1，2N]時，組AB輸入；OUTENABLE<=0。

（2）T∈[2N+1，4N]時，組AB輸出，組CD輸入；OUTENABLE<=1。

（3）T∈[4N+1，6N]時，組CD輸出，組AB輸入；OUTENABLE<=1。

循環(huán)執(zhí)行（2），（3）直到所有的數(shù)據(jù)都變成2N有序的輸出。

2.4 基于歸并操作的排序

不論是基于寄存器的歸并操作，還是基于FIFO的歸并操作，都可以看成一個歸并組件，作為歸并排序的一層。它們擁有統(tǒng)一的接口。

歸并組件接口：

輸入：

INDATA：待排序數(shù)輸入端口

INENABLE：輸入使能信號。INENABLE為1時INDATA有效

輸出：

OUTDATA：待排序數(shù)輸出端口

OUTENABLE：輸出使能信號。OUTENABLE為1時OUTDATA輸出有效

如同1.2節(jié)所述，將歸并排序分多層，首先是長度為1，最后一層是長度為N/2。上一層的輸出和下一層的輸入銜接，并通過上一層的OUTENBALE信號，控制下一層的歸并的開始。第一層輸入原始的待排序數(shù)據(jù)，最后一層無需乒乓操作，只使用一組隊(duì)列就可以輸出排序之后的數(shù)據(jù)。

可以靈活地選用基于寄存器的組件和選用基于FIFO的組件搭配，實(shí)現(xiàn)小規(guī)模數(shù)據(jù)和大規(guī)模數(shù)據(jù)下不同的配置。

在KLT跟蹤算法里實(shí)際使用的是圖片特征點(diǎn)的坐標(biāo)位置，所以在排序的存儲隊(duì)列中，將一個點(diǎn)的特征值和坐標(biāo)位置同時存儲。歸并排序時的比較器只使用特征值比較，排序之后，輸出特征點(diǎn)的坐標(biāo)位置和特征值。

3 實(shí)驗(yàn)

多層次歸并排序，一層的輸出作為下一層的輸入。通過乒乓操作形成流水操作。每一層的輸出周期即為下一層的輸入時間周期。所以總的時間周期分為兩部分：每一層的輸入時間周期和最后一層的輸出時間周期。設(shè)總時間周期為T，第i層的輸入時間為Ti，最后一層的輸出周期數(shù)為T′。待排序隊(duì)列長度為N，排序?qū)訑?shù)為M。

即并行歸并排序時間復(fù)雜度為O(N)。優(yōu)于傳統(tǒng)的O(N lg(N))的歸并排序。

系統(tǒng)首先使用ISIM仿真，驗(yàn)證結(jié)構(gòu)正確性。然后在Xilinx Virtex5 SXT FPGA（XC5VSX50T-1ff1136）開發(fā)板上實(shí)現(xiàn)。KLT特征提取算法提取出4 096個特征點(diǎn)，設(shè)為1～4 096。要求從大到小排序。待排序的數(shù)據(jù)使用32位的整數(shù)，點(diǎn)的位置坐標(biāo)X，Y使用10位。所以寄存器，或者FIFO內(nèi)存儲52位數(shù)據(jù)。FIFO的實(shí)現(xiàn)采用Xilinx提供的IP Core。

4 096個數(shù)據(jù)采用11層的結(jié)構(gòu)，1到4層為基于寄存器的實(shí)現(xiàn)，5～11層為基于FIFO的實(shí)現(xiàn)。第11層不使用乒乓操作直接輸出最終結(jié)果。排序部分結(jié)果如圖5所示。

圖5 仿真部分結(jié)果

表1和表2總結(jié)了本文的歸并排序結(jié)構(gòu)在Virtex5 SX50T開發(fā)板上的資源利用率。

表1 綜合歸并排序的資源報(bào)告1

表2 綜合歸并排序的資源報(bào)告2

在對1 024×1 024的高清圖片的特征點(diǎn)進(jìn)行排序時，最高時鐘頻率可以達(dá)到159.795 MHz。即每秒可以處理100張以上分辨率為1 024×1 024的圖片特征點(diǎn)排序。完全可以達(dá)到高清圖片的實(shí)時處理要求。

4 結(jié)語

首先分析了經(jīng)典的歸并排序算法然后將其歸并操作的結(jié)果和行為拓展到FPGA結(jié)構(gòu)和硬件行為。提出了兩種基于FPGA的歸并操作，分別是基于寄存器的歸并操作和基于FIFO的歸并操作。兩種操作都可以采用乒乓操作實(shí)現(xiàn)排序的完全流水。其中基于寄存器的結(jié)構(gòu)采用時序邏輯。基于FIFO的結(jié)構(gòu)采用時序邏輯和組合邏輯。最后在FPGA的歸并操作基礎(chǔ)之上，采用多層次構(gòu)架，可以靈活地選用不同的歸并組件，實(shí)現(xiàn)資源和效率的最大化。實(shí)驗(yàn)結(jié)果證明本文的歸并排序完全可以滿足高清圖片KLT跟蹤算法的實(shí)時排序。

[1]Lucas B D，Kanade T.An iterative image registration technique with an application to stereo vision[C]//International Joint Conference on Artificial Intelligence，1981：674-679.

[2]Tomasi C，Kanade T.Detection and tracking of point features，CMU-CS-91-132[R].Pittsburgh，PA：Carnegie Mellon University，1991.

[3]Shi Jianbo，Tomasi C.Good features to track[C]//IEEE Conference on Computer Vision and Pattern Recognition，1994：593-600.

[4]Birchfield S.Derivation of Kanade-Lucas-Tomasi tracking equation[Z].1997.

[5]Knuth D E.The art of computer programming，Vol.3-sorting and searching[M].[S.l.]：Addison Wesley，1973.

[6]Mart J，Cumplido R R，F(xiàn)eregrino C.An FPGA-based parallel sorting architecture for the Burrows Wheeler transform[C]//Proceedings International Conference on Reconfigurable Computing and FPGAs，Puebla City，Mexico，2005：28-30.

[7]Zhang Y，Zheng S Q.An efficient parallel VLSI sorting architecture[J].VLSI Design，2000，11：137-147.

[8]Parhami B，Kwai D M.Data-driven control scheme for linear arrays：application to a stable insertion sorter[J]. IEEE Trans on Parallel and Distributed Systems，1999，10（1）：23-28.

[9]Ratnayake K，Amer A.An FPGA architecture of stablesorting on a large data volume：application to video signals[C]//41st Annual Conf on Information Sciences and Systems（CISS’07），2007.

[10]Edahiro M.Parallelizing fundamental algorithms such as sorting on multi-core processors for EDA acceleration[C]// Asia and South Pacific Design Automation Conference（ASP-DAC’2009），2009.

[11]吳彥宏，陳相寧.QoS保障機(jī)制中的FPGA堆排序?qū)崿F(xiàn)[J].計(jì)算機(jī)工程，2009，35（12）：223-225.

CHAI Zhilei,FANG Wanyuan

Development Center of Internet of Things Engineering,MoE,Jiangnan University,Wuxi,Jiangsu 214122,China

The Kanade-Lucas-Tomasi feature tracker（KLT）has

special attention due to its effectiveness on image track.The sort of feature point is the key point of joining the feature detection and feature track.This paper presents a novel FPGA-based parallel merge sort architecture for the KLT feature points,then analyzes its time period.The time complexity of the parallel merge sort architecture isO(N).The result shows that the FPGA-based merge sort can solve the real-time KLT feature points sort problem for HD image/video resolution.

parallel merge sort;Kanade-Lucas-Tomasi（KLT）;Field Programmable Gate Array（FPGA）sort

A

TP391

10.3778/j.issn.1002-8331.1211-0179

CHAI Zhilei,FANG Wanyuan.FPGA-based multi-level parallel merge sorting architecture for KLT feature points. Computer Engineering and Applications,2014,50（21）：157-161.

國家自然科學(xué)基金（No.60703106，No.61170121，No.61202312）。

柴志雷（1975—），男，副教授，研究生導(dǎo)師，主要研究方向：嵌入式系統(tǒng)；方萬元（1988—），男，碩士研究生，主要研究方向：視頻壓縮、圖像處理。E-mail：zlchai@jiangnan.edu.cn

2012-11-15

2013-03-11

1002-8331（2014）21-0157-05

CNKI出版日期：2013-09-05,http://www.cnki.net/kcms/detail/11.2127.TP.20130905.1048.006.html