基于FPGA的KLT特征點多層次歸并排序

柴志雷，方萬元

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

◎圖形圖像處理◎

基于FPGA的KLT特征點多層次歸并排序

柴志雷，方萬元

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

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

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

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

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

排序算法在科學(xué)計算領(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]，分為輸入隊列、乒乓排序網(wǎng)絡(luò)和輸出檢測模塊。Martinez等[6]提出了應(yīng)用在塊排序壓縮上的網(wǎng)絡(luò)排序算法，采用了乒乓操作，實現(xiàn)數(shù)據(jù)循環(huán)處理。排序單元處理128個字符，最終的結(jié)果顯示可達到的最大時鐘頻率為50 MHz左右?；诰€性數(shù)組的排序基于可擴展的線性數(shù)組。Paraham，Kwai[8]采用比較/插入單元。每個單元包含比較器，乘法器和控制單元。可擴展線性數(shù)組包含一系列的單元。

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

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

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

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

1.1 歸并操作

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

歸并步驟：

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

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

（3）將tmp壓入C的隊尾（入隊操作）。

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

圖1 歸并操作示意圖

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

（5）將tmp壓入C的隊尾（入隊操作）。

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

1.2 基于歸并操作的排序

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

歸并排序步驟：

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

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

歸并排序的如圖2。

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

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

2 可并行歸并排序

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

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

2.1 基于寄存器的歸并操作

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

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

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

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

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

2.1.1 隊列行為

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

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

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

2.1.2 歸并輸入

（1）在T∈[1，N]時，A依次入隊，隊列標記位加1。組標記位加1。

（2）在T∈[N+1，2N]時，B依次入隊，隊列標記位加1。組標記位加1。

2.1.3 歸并輸出

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

（2）當A，B任一為空時，依次輸出另一隊列，將其標記減1，組標記位減1。OUTENABLE為0；直到A，B均為空，OUTENABLE為0。

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

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

2.2 基于FIFO的歸并操作

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

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

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

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

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

圖4 基于FIFO的歸并操作

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

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

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

2.2.1 隊列行為

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

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

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

2.2.2 歸并輸入

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

（1）A的隊頭和B的隊尾銜接；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，用組合邏輯。

時序邏輯：

當T=2N-1，同時取AB隊頭，即A_R1<=1；B_R1<=1。

組合邏輯：

當T∈[2N，4N]時，T時刻設(shè)置A，B的R2信號，T+1，A，B的隊頭更新，比較兩者大小，根據(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的隊頭。輸出其中較大者，并將其隊頭出隊，設(shè)置其R2等于1，將其標記減1。組標記位減1。OUTENABLE為1。

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

2.3 乒乓的歸并操作

如圖3，圖4中設(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ù)，最后一層無需乒乓操作，只使用一組隊列就可以輸出排序之后的數(shù)據(jù)。

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

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

3 實驗

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

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

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

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

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

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

表1 綜合歸并排序的資源報告1

表2 綜合歸并排序的資源報告2

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

4 結(jié)語

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

[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保障機制中的FPGA堆排序?qū)崿F(xiàn)[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