摘 要：在嵌入式計算平臺上實現(xiàn)雙向約束LK金字塔高精度光流的實時計算，是該算法能否應(yīng)用于自動駕駛等場景的重要影響因素。為了實現(xiàn)該目的，提出了基于網(wǎng)格劃分的特征提取方法及新的雙向約束方法；然后設(shè)計了動態(tài)窗口的金字塔模型，解決了光流計算過程中的負(fù)載不均衡問題；最后通過降低計算位寬，使得整體性能獲得進(jìn)一步提升。實驗結(jié)果表明：在Jetson TX2上，針對真實場景所用的720P視頻，所提出方法的性能比OpenCV的GPU版本提升了4.1倍，達(dá)到30 fps以上；將采用該方法的SLAM系統(tǒng)成功應(yīng)用于車載場景并在真實環(huán)境中測試，使得系統(tǒng)的性能達(dá)到了28 fps。新方法有效地提升了位姿和點云的精度，較好地滿足了車載場景的實時處理需求。

關(guān)鍵詞：LK光流； 嵌入式GPU； CUDA； SLAM； 并行計算

中圖分類號：TP302 文獻(xiàn)標(biāo)志碼：A

文章編號：1001-3695（2022）07-007-1966-07

doi：10.19734/j.issn.1001-3695.2021.12.0675

基金項目：國家自然科學(xué)基金資助項目（61972180）

作者簡介：孫瑞鑫（1997-），男，河南信陽人，碩士，主要研究方向為計算機體系結(jié)構(gòu)；朱國梁（1989-），男，甘肅人，博士，主要研究方向為計算機體系結(jié)構(gòu)和編譯器；謝雙鐿（1995-），男，湖南醴陵人，碩士，主要研究方向為計算機體系結(jié)構(gòu)；郭雪亮（1993-），男，河北邢臺人，碩士，主要研究方向為3D視覺；柴志雷（1975-），男（通信作者），山西人，教授，博導(dǎo)，博士，主要研究方向為計算機體系結(jié)構(gòu)（zlchai@jiangnan.edu.cn）.

High-speed computing of pyramid LK optical flow based on embedded GPU

Sun Ruixin¹， Zhu Guoliang²， Xie Shuangyi¹， Guo Xueliang³， Chai Zhilei^1，4?

（1.School of Artificial Intelligence amp; Computer Science， Jiangnan University， Wuxi Jiangsu 214122， China; 2.Wuxi Institute of Advanced Technology， Wuxi Jiangsu 214125， China; 3.UISEE （Shanghai） Automotive Technologies Ltd. ， Shanghai 201807， China; 4.Jiangsu Provincial Engineering Laboratory of Pattern Recognition amp; Computational Intelligence， Wuxi Jiangsu 214122， China）

Abstract：Real-time calculation of high-precision forward-backward pyramid LK optical flow on embedded computing platform has become the decisive factor of whether the algorithm can be used in realistic scenarios such as autonomous driving. This paper presented a feature extraction method based on mesh division and a new forward-backward constraint method. To address the load unbalance in the optical flow calculation process， this paper proposed a dynamic window-based pyramid model. It also reduced the calculation bit width to further improve the overall performance. Using the 720P videos in realistic scenarios， this method yields significant performance gained over the GPU optimized version of OpenCV by 4.1 times on the embedded GPU platform TX2 and achieved 30 fps performance. It helped the SLAM system increase the frame rate to 28 fps in real car scene. This method improves the accuracy of the pose and point cloud in realistic scenarios， meeting the real-time application requirements of vehicle scenarios.

Key words：LK optical flow; embedded GPU; CUDA; SLAM; parallel computing

0 引言

光流（optical flow）算法一直以來都是計算機視覺領(lǐng)域研究的重點，其本質(zhì)是計算運動圖像的連續(xù)幀之間像素點的運動矢量，在自動駕駛、三維重建、目標(biāo)檢測、場景分割等領(lǐng)域具有巨大應(yīng)用潛力。光流算法目前主要分為以知識驅(qū)動的傳統(tǒng)方法和以數(shù)據(jù)驅(qū)動的深度學(xué)習(xí)方法。傳統(tǒng)光流算法主要是依賴視覺理論知識進(jìn)行推導(dǎo)計算，其中較為著名的是LK光流^［1］和HS光流^［2］。數(shù)據(jù)驅(qū)動的方法主要是依托于深度學(xué)習(xí)知識設(shè)計出光流網(wǎng)絡(luò)，其中較為著名的FlowNet^［3］、FlowNet2.0^［4］、SpyNet^［5］等都在多組公開數(shù)據(jù)集上取得了較好的效果。然而光流訓(xùn)練集的構(gòu)建既耗時又昂貴，隨著使用場景的變化可能需要重新構(gòu)建訓(xùn)練集并訓(xùn)練網(wǎng)絡(luò)，這使得該類方法目前還處于研究階段，很難廣泛投入應(yīng)用^［6］。相較之下，傳統(tǒng)算法無須額外的使用代價，在實際應(yīng)用中具有更強的泛用性，目前的研究表明^［7～9］在SLAM系統(tǒng)中應(yīng)用傳統(tǒng)的LK光流依舊是方便且可行的。

本文針對傳統(tǒng)算法中的基于雙向約束的金字塔LK（forward backward pyramid LK）光流算法進(jìn)行加速研究。該算法是在原本LK光流的基礎(chǔ)上引入金字塔模型^［10］和雙向約束^［11］而形成的光流算法，具有更好的精度和魯棒性，但計算復(fù)雜度太大，目前難以實現(xiàn)在嵌入式平臺上達(dá)到實時計算。近年來并行計算的快速發(fā)展為解決計算量大、并行度高的問題提供了良好的解決方案。通過對光流算法中需要復(fù)雜處理的模塊進(jìn)行并行加速，能夠極大地提高光流計算的實時性。文獻(xiàn)［12］給出一種金字塔LK光流的GPU實現(xiàn)方案，但其未考慮計算過程中的負(fù)載不均衡問題，沒有針對雙向約束進(jìn)行優(yōu)化。文獻(xiàn)［13］使用OpenCL對金字塔LK光流算法進(jìn)行加速，其在GTX950上計算11 920 dpi×1 080 dpi的圖像需要82.522 ms，同時也沒有考慮雙向約束的情況。文獻(xiàn)［14］提出一種新的LK光流的計算方法，并使用Titan GPU對其進(jìn)行加速，對于1 920 dpi×1 080 dpi的圖像，其計算速度可以達(dá)到14.4 ms/frame，但僅適用于特定的場景。

目前這些針對光流計算進(jìn)行加速的成果，大多數(shù)都是使用服務(wù)器設(shè)備進(jìn)行實驗，未能專門針對嵌入式平臺進(jìn)行研究設(shè)計。這使得眾多加速后的LK光流算法難以在實際應(yīng)用場景下落地使用。OpenCV庫是應(yīng)用最廣泛的計算機視覺庫，然而其針對GPU專門進(jìn)行性能優(yōu)化的庫函數(shù)在嵌入式設(shè)備上依然難以滿足實時計算的需求。同時在優(yōu)化過程中考慮雙向約束是必要的，因為SLAM系統(tǒng)很難將未篩選的光流直接應(yīng)用于后期的位姿恢復(fù)和點云重建中?？紤]到這些因素，本文在嵌入式設(shè)備Jetson TX2上對forward backward pyramid LK光流算法進(jìn)行加速設(shè)計，成功實現(xiàn)了該算法對高清圖片的實時追蹤。在車載場景下，該算法的優(yōu)化使得SLAM系統(tǒng)的幀率從9 fps提升到28 fps，有效提升了系統(tǒng)的精度，對車載場景下的實時定位和深度估計具有重大意義。

本文的主要貢獻(xiàn)如下：

a）改進(jìn)算法以優(yōu)化性能，提出并實現(xiàn)了基于網(wǎng)格劃分的KLT（Kanade-Lucas-Tomasi）角點檢測^［15］算法以及新的雙向約束方法。新的角點檢測方法不僅突破了原本算法的并行瓶頸，同時減少了連續(xù)幀光流計算過程中特征提取的頻率，有效地解決了特征點聚集的問題。新的雙向約束有效地減少了反向追蹤過程中的計算冗余。

b）針對硬件特性，本文分析并解決了GPU線程負(fù)載不均衡問題，并通過降低計算位寬進(jìn)一步提升計算性能。通過分析發(fā)現(xiàn)OpenCV采用二維線程塊的方式計算光流，該方法會導(dǎo)致GPU線程負(fù)載不均衡。針對這一問題，本文給出使用一維線程塊和構(gòu)建動態(tài)窗口這兩種解決方案，更好地發(fā)揮了嵌入式GPU的性能。

c）將優(yōu)化后的算法應(yīng)用于某自動駕駛公司真實車載場景下的SLAM系統(tǒng)，使得系統(tǒng)的精度與速度獲得有效提升，證明了其能夠解決實際車載場景下的光流計算問題。

1 基于雙向約束的金字塔LK光流算法

1.1 KLT角點檢測算法

KLT角點檢測算法是一種經(jīng)典特征提取算法。假設(shè)圖像表示為I（x，y），則每個像素點的梯度協(xié)方差矩陣為

其中：dIdx和dIdy分別表示像素點在x和y方向的梯度;p=［ux，uy］為像素點在圖像中的位置;W（p）表示以p為中心的窗口。

將式（1）化簡為式（2）：

設(shè)矩陣M的特征值分別為λ1和λ2，則

通過式（3）求出每個像素點對應(yīng)的協(xié)方差矩陣的最小特征值。

其中：I為指示函數(shù)，即括號內(nèi)兩式相等時則值為1，否則為0。對于圖像中所有的像素，在所有g(shù)（p）為1的點中選擇λmin（p）值最大的K個點作為該圖像提取的K個特征點。

設(shè)原圖像中像素點數(shù)目為n，窗口W（p）中的像素點數(shù)量為m，則KLT角點檢測算法的時間復(fù)雜度為O（nm+n log n）。該算法的計算時間主要是由前面的特征值計算和后續(xù)的排序算法決定，這兩部分的計算耗時和使用場景關(guān)系不大，僅由n和m決定，計算耗時較為穩(wěn)定。

1.2 基于金字塔的雙向約束LK光流算法

1.2.1 基于金字塔的LK光流算法

LK光流算法是對KLT角點進(jìn)行追蹤的稀疏光流算法。該算法是根據(jù)三種假設(shè)推導(dǎo)而來，其分別為：a）亮度恒定假設(shè);b）小范圍運動假設(shè);c）空間一致性假設(shè)。

在運動圖像的連續(xù)幀中，設(shè)第t時刻的圖像為I，t+1時刻的圖像為J，特征點的位移為d=［dxdy］T。根據(jù)亮度恒定假設(shè)以及空間一致性假設(shè)，可以推斷出連續(xù)兩幀之間同一個特征點的鄰域內(nèi)像素點值相等。因此可以得到以下優(yōu)化目標(biāo)：

通過讓目標(biāo)函數(shù)式（5）對d求導(dǎo)，使其值為0以求極值，并對其進(jìn)行泰勒展開可得

其中：δI=I（x，y）－J（x，y）， Ix和Iy分別為圖像I在（x，y）處的梯度。然后通過推導(dǎo)求解可得

其中：

在實際計算過程中需要不斷迭代以計算出d的值來更新p的位置，直至當(dāng)前d的模長過小或者越界。由于上述算法僅適用于小位移的情況，所以在此基礎(chǔ)之上需要引入圖片金字塔結(jié)構(gòu)來處理大位移特征點的追蹤。

對于金字塔結(jié)構(gòu)的LK光流計算方法如下：通過下采樣操作將圖像I和J進(jìn)行下采樣處理，建立對應(yīng)圖像的圖像金字塔;將特征點p自上而下進(jìn)行計算，在計算l層光流時使用l+1層光流的計算結(jié)果來初始化本層特征點的初始位置（這里設(shè)金字塔頂層的初始光流值為0）。設(shè)從頂層至l+1層的累計位移為gl，本層光流位移為dl。

通過式（10）的迭代就可以計算出連續(xù)幀的光流值，然而其是依賴于三個光流假設(shè)都成立的情況。在實際的應(yīng)用場景中，可能只有部分假設(shè)成立，而且還要考慮噪聲、遮擋等情況。因此通過以上計算方式雖然可以計算出每個特征點的光流信息，但卻無法評估每個光流計算的準(zhǔn)確性。將不準(zhǔn)確的光流應(yīng)用于后續(xù)的位姿恢復(fù)中，會導(dǎo)致位姿矩陣的計算效率低下，甚至無法計算出一個合理的位姿矩陣。為了解決這個問題，光流計算的過程中一般都會引入雙向約束。

1.2.2 光流的雙向約束

雙向約束的基本思想如圖1所示，在t時刻的圖像I中提取到特征點pcurr并通過LK光流算法估算出從I（t）到I（t+1）的光流信息，得到特征點pcurr在圖像I（t+1）中對應(yīng)的位置pnext。將圖像I（t+1）看成當(dāng)前幀，圖像I（t）看成下一幀，對圖像I（t+1）中的點pnext使用同樣的算法計算，可以得到其在圖像I（t）中對應(yīng)點pback。雙向約束認(rèn)為如果pcurr和pback的距離十分接近，那么就保留該光流，反之則刪除該光流。因此可得

其中：θ為設(shè)置的閾值;I為指示函數(shù)。如果goodFlag的值為1，就認(rèn)為這個光流是準(zhǔn)確的，反之則會剔除這個光流。設(shè)金字塔的層數(shù)為L，特征點的數(shù)量為n，W（p）窗口中像素點的數(shù)目為m，最大迭代次數(shù)為C，則LK光流算法的時間復(fù)雜度為O（nmCL）。由于在迭代過程中存在提前終止迭代的情況，所以該算法的計算耗時相對不太穩(wěn)定。對于噪聲小、像素點位移少且小的場景，該算法能夠較快的終止計算，而在噪聲大、像素點位移多且大的場景下，該算法則會更耗時。

2 從算法本身優(yōu)化計算性能

2.1 特征提取的并行度瓶頸分析

KLT角點檢測算法中式（1）～（4）的計算部分很容易進(jìn)行加速設(shè)計，因為在這部分中每個像素點的計算是完全并行的，它們之間沒有相互依賴關(guān)系。然而后續(xù)的排序篩選部分卻限制了整個算法的并行度，具體情況如圖2（a）所示。由于式（4）中g(shù)（p）值等于1的像素點數(shù)目過多，所以后續(xù)的排序篩選模塊成了整個算法并行度的瓶頸。

2.2 網(wǎng)格劃分的特征提取設(shè)計

為了解決上述問題，本文在原本算法的基礎(chǔ)之上引入網(wǎng)格劃分的思想。具體方案如下：

a）將圖像劃分成若干個固定大小的網(wǎng)格區(qū)域。

b）對每個網(wǎng)格區(qū)域局部執(zhí)行KLT角點檢測算法，并在每個區(qū)域內(nèi)提取一個特征點。

c）如果需要控制特征點的數(shù)目，可以通過式（3）所計算出的每個特征點的λmin（p）值進(jìn)行篩選。

該方法的優(yōu)勢在于能在整張圖像上均勻地提取特征，而不至于使得特征點集中于局部區(qū)域。由于步驟b）只提取單個特征點而無須復(fù)雜的排序，所以該步驟速度很快。步驟c）中需要排序點的數(shù)目在經(jīng)過步驟b）的篩選之后大幅減少，極大地提升了該步的排序效率。具體流程如圖2（b）所示，運行效果如圖7所示（圖7（a）與（b）的特征點數(shù)目完全一致）。

2.3 減少冗余的特征提取

在連續(xù)幀光流的追蹤過程中，可能需要頻繁地使用角點檢測來計算多幀圖像之間的光流。原本的算法需要對每一幀進(jìn)行一次完整的角點檢測，并沒有充分利用光流計算中繼承下來的特征點信息。而采用基于網(wǎng)格劃分的特征提取之后，通過合理的繼承方式，可以極大地減少特征提取的次數(shù)。

假設(shè)對t時刻的圖像I（t）提取得到特征點的集合為P（t），通過和t+1時刻的圖像I（t+1）計算光流得到P（t+1）。此時，如果繼續(xù)計算I（t+1）和I（t+2）的光流，那么就需要對I（t+1）進(jìn)行特征提取。當(dāng)使用基于網(wǎng)格劃分的特征提取方式后，對于圖像I（t+1）中的任意一個網(wǎng)格G（x，y），如果P（t+1）中存在一個特征點pi∈G（x，y），則無須在網(wǎng)格G（x，y）內(nèi)再提取特征點，直接使用pi即可。

如圖3所示，對圖像I（t）劃分四個網(wǎng)格提取出四個特征點，通過和t+1時刻的圖像I（t+1）計算得到兩個光流，其中圖像I（t）中的3和4號網(wǎng)格的特征追蹤失敗或者沒有通過雙向約束。那么在計算I（t+1）和I（t+2）的光流時，僅需要對I（t+1）中1和2號網(wǎng)格提取特征，對于3和4號網(wǎng)格則無須再提取特征，直接使用追蹤過來的點。

該設(shè)計使得在連續(xù)幀的追蹤過程中，只對失去信息的網(wǎng)格進(jìn)行特征提取，有效減少了計算次數(shù)。

2.4 提取終止迭代設(shè)計

雙向約束雖然可以很方便地篩選光流，但是卻使得算法的計算量翻倍。文獻(xiàn)［16］提出了一種直接推導(dǎo)的判別方式，但該方法在GPU上很難實現(xiàn)。通過分析可以發(fā)現(xiàn)，雙向約束只是為了篩選光流，并不需要準(zhǔn)確計算出pback。因此對于式（12），圖4（a）的計算方式會帶來冗余計算。為此本文提出圖4（b）這一新的約束方法，即在每次迭代計算后都去判斷當(dāng)前的pback是否到達(dá)pprev附近，一旦到達(dá)就立刻終止計算，并認(rèn)為該光流是一次準(zhǔn)確的計算。新的約束方法可以減少不必要的迭代計算，提高光流的計算效率。

在使用新的約束方法時，如果將式（12）中的θ值設(shè)置為固定值，會導(dǎo)致模長小于θ的光流直接被保留下來，對這些光流雙向約束就沒有起到作用。為了解決這一問題，本文提出新的判別方法：

其中：θ∈［0，1］。式（13）將前向光流模長的百分比作為閾值，以此判斷當(dāng)前計算出的光流是否準(zhǔn)確。這樣可解決式（12）對部分模長較小的光流沒有約束的問題。

3 充分利用GPU硬件加速計算

3.1 嵌入式GPU架構(gòu)

本文采用NVIDIA公司推出的Jetson TX2嵌入式板卡進(jìn)行加速優(yōu)化。其板載CPU端有兩個Denver核心以及四個A57核心，共計六個CPU核心。GPU端有兩個多核流處理器（streaming multiprocessor，SM），其采用Pascal架構(gòu)。后續(xù)實驗過程中主要采用CUDA編程模型來對GPU進(jìn)行調(diào)用。通過將設(shè)備端的代碼組織成kernel，由ARM端進(jìn)行kernel的調(diào)用。每個kernel包含大量的線程（thread），這些線程聚集在不同的塊（block）中，而這些塊被劃分成網(wǎng)格（grid）。被調(diào)度的線程在不同的數(shù)據(jù)上執(zhí)行相同的指令。每個塊都會被調(diào)度在一個多核流處理器上，該處理器上同時有多個塊被交替調(diào)度以隱藏延遲^{［17，18］}。嵌入式GPU架構(gòu)如圖5所示。

3.2 光流計算的負(fù)載分析及優(yōu)化

3.2.1 GPU線程負(fù)載不均衡問題分析

Pyramid LK光流算法中最復(fù)雜的計算來自于式（8）和（9）。這兩個公式對窗口內(nèi)每個像素點進(jìn)行數(shù)值計算，并把計算的結(jié)果累加起來。從算法的層面來說，越大的窗口代表越高的算法魯棒性，越小的窗口代表越高的計算準(zhǔn)確性^［10］;從性能層面來說，在串行計算模式中窗口的大小與計算量成正比，而在并行計算模式中窗口大小的選擇可能會帶來負(fù)載不均衡問題。

通過分析OpenCV的光流計算，可以發(fā)現(xiàn)其是以一個二維線程塊來處理一個窗口的計算。然而以8×8的線程塊來處理一個21×21窗口的光流計算，必然會導(dǎo)致負(fù)載不均衡的問題，具體如圖6（a）所示。該方法使得計算量最大的線程和最小的線程相差一倍多的計算量。為了解決圖6（a）所示的負(fù)載不均衡問題，本文提出兩種解決方案：

a）將線程塊內(nèi)的線程組織成一維形式。通過將線程塊組織成一維形式，可以極大地緩解不平衡性問題，如圖6（b）所示，每個圓代表一個GPU線程，圓中的數(shù)字代表該線程需要計算的像素點個數(shù)。線程之間計算量的差異最大僅為1個像素點。

b）選擇能均勻分配計算量的窗口。從圖6（a）和（b）中可以看出，無論采用哪種調(diào)度方式總會導(dǎo)致GPU線程計算負(fù)載不均衡，只是在二維的情況下問題更嚴(yán)重。為了充分發(fā)揮GPU的算力，解決不平衡問題，本文認(rèn)為應(yīng)該盡量選擇8×8、16×16、24×24、32×32等窗口進(jìn)行計算。

在上述的兩個方案中，方案a）僅僅是設(shè)計實現(xiàn)上的改變，而方案b）則會限制窗口的選擇范圍。因此為了更好地應(yīng)用方案b）以徹底解決不平衡問題，本文提出一種動態(tài)窗口的設(shè)計方法，該方法可以將原本任意的固定窗口大小轉(zhuǎn)換為更適合GPU特性的大小。

3.2.2 金字塔模型中動態(tài)窗口設(shè)計

如式（10）和（11）所示的金字塔模型中，該算法從頂層開始進(jìn)行迭代計算，最終在底層得到結(jié)果。在計算過程中，對于每一層一般采用相等大小的窗口，而本文基于GPU的架構(gòu)提出了一種新的動態(tài)窗口設(shè)計策略，具體如下：

設(shè)原本采用的窗口大小為WinOri，金字塔的層數(shù)為L。WinlNew代表第l層對應(yīng)的新的窗口大小，其中L是最頂層。則有

其中：WinLNew代表最頂層的新窗口大小。

其中：PNumlOri代表采用原本的窗口從l～L層所計算的像素點的個數(shù)。

其中：PNumlNew代表采用動態(tài)設(shè)計的窗口從l～L層所計算的像素點的個數(shù)。因此可得

采用上述方法可以推算出使用動態(tài)窗口時金字塔各層的窗口大小。新方法會使得參與計算的像素點總數(shù)在多于原本方法的基礎(chǔ)上盡可能少。這可能會使得每層的窗口大小呈現(xiàn)自頂向下變小的趨勢。例如對原本W(wǎng)inOri=21，L=3，新的窗口大小為WinNew=［24，24，24，16］。該特性從某種程度上也符合算法本身的思想，因為在頂層的時候初始點距離真值較遠(yuǎn)，所以采用較大的窗口;而計算越靠近下層，該層的初始點距離真值點越近，因此采用較小的窗口進(jìn)行計算。

該方法在保證金字塔結(jié)構(gòu)的同時，針對GPU計算特性動態(tài)調(diào)整窗口大小，更好地發(fā)揮了硬件性能。對這兩個方案實驗結(jié)果的比較和分析，將在4.3.2節(jié)中詳細(xì)闡述。

3.3 通過降低位寬提升計算性能

從Tegra X1開始，NVIDIA的GPU支持原生的半精度浮點（FP16）計算指令，通過合理地使用FP16指令進(jìn)行數(shù)據(jù)運算，理論上可以獲得兩倍于32位浮點（FP32）的性能^［19］。在LK光流算法中，大多數(shù)變量的取值范圍會隨著窗口大小的變化而波動，故無法對整個算法使用FP16進(jìn)行運算。但計算過程中的中間變量取值范圍比較穩(wěn)定，因此可以局部使用FP16替代FP32進(jìn)行計算。

LK光流在GPU上的計算主要分為四個模塊：計算式（8）中的G，計算式（9）中的b、求解式（7）以及計算過程中的reduce耗時。由于采用的是逆向LK光流法^［20］，所以對于每個光流，矩陣G僅需要計算一次，矩陣b則需要在迭代過程中反復(fù)地計算。這四個模塊的耗時占比如表1所示。

從表1可以看出，該算法的主要耗時是對矩陣b的反復(fù)計算，其占據(jù)了總時間的80%以上。因此進(jìn)一步優(yōu)化的關(guān)鍵是對這部分計算的優(yōu)化。計算矩陣b的核心是計算δIIx和δIIy，參與這兩步計算的變量的取值不會隨著外部參數(shù)的改變而變化。其中δI的取值范圍在圖像進(jìn)行全局歸一化后是［-1，1］，采用Scharr算子計算梯度后Ix和Iy的取值為［-16，16］，故δIIx和δIIy的表示為［-16，16］。從以上分析可以看出，參與δIIx和δIIy計算的變量的取值范圍較小，可以在保證精度的基礎(chǔ)上使用FP16替代FP32，更好地發(fā)揮平臺的計算性能。

FP32轉(zhuǎn)FP16的轉(zhuǎn)換公式如下：

在轉(zhuǎn)換后，對half變量調(diào)用GPU的FP16計算指令計算δIIx和δIIy，然后再使用以下公式將FP16轉(zhuǎn)換到FP32并累加到b上。

最后在b做reduce后使用式（23）進(jìn)行縮放：

為了在數(shù)據(jù)不溢出的基礎(chǔ)上盡可能的保留精度，本文令Q1=6，Q2=4。其中式（19）（20）的轉(zhuǎn)換不需要每次計算都使用，只需要全局縮放一次。局部使用FP16計算雖然會造成部分精度損失，但4.3.3節(jié)的實驗結(jié)果表明，損失的精度對整個光流的結(jié)果幾乎沒有影響，卻能有效地提升性能。

4 實驗結(jié)果

4.1 實驗環(huán)境介紹

軟件環(huán)境：Ubuntu 16.04，CUDA 9.0，OpenCV 3.3.1，g++5.4.0。

硬件環(huán)境：Stereo zed2攝像頭，Jetson TX2開發(fā)套件。

對照組介紹：OpenCV中實現(xiàn)的KLT角點檢測和LK光流的GPU優(yōu)化版本。后續(xù)實驗都是與OpenCV 3.3.1中的實現(xiàn)對比。

數(shù)據(jù)集介紹：本文采用了KITTI數(shù)據(jù)集中的光流數(shù)據(jù)集（1 242×375）以及真實場景中實地錄制的高清數(shù)據(jù)集（1 280×720）。KITTI數(shù)據(jù)集含有光流的真值信息，方便驗證結(jié)果的準(zhǔn)確性，并且數(shù)據(jù)更具說服力。真實數(shù)據(jù)集可以更好地衡量其在真實車載場景下對720P圖片的性能。

誤差衡量指標(biāo)：本文使用角度誤差（angular error，AE）和絕對誤差（end point error，EPE） ^［21］兩個經(jīng)典的評價指標(biāo)來評價光流精度。由于自行錄制的數(shù)據(jù)集中沒有光流的真值，所以只能給出性能評測結(jié)果。

實際場景介紹：基于Stereo zed2攝像頭和TX2開發(fā)板在實際駕駛過程中使用SLAM系統(tǒng)進(jìn)行測試。

4.2 角點檢測的實驗結(jié)果分析

對KITTI數(shù)據(jù)集中的一組數(shù)據(jù)分別使用OpenCV的角點檢測和基于網(wǎng)格劃分的角點檢測方法，兩者都在GPU上運行;圖7和8分別對應(yīng)光流結(jié)果對比和耗時對比，對比過程中兩種方案提取的特征點數(shù)目保持一致。

圖7（a）左圖中提取的特征點聚集到圖像上方的樹上和左右兩邊的車上，從而導(dǎo)致地面區(qū)域光流嚴(yán)重缺失。在圖7（b）中新方法使得光流在整個圖像上的分布十分均勻，很少發(fā)生大片區(qū)域的光流信息缺失現(xiàn)象。

圖8給出不同網(wǎng)格大小下特征提取的耗時對比?？梢钥闯鰺o論采用多大的網(wǎng)格，新的角點檢測方法都遠(yuǎn)快于原本方法，平均提升了2倍左右的性能。其中圖8（b）表明對于連續(xù)幀光流的追蹤，由于很多的角點信息被繼承下來，所以其性能表現(xiàn)得更加優(yōu)秀，平均提升了3.2倍的性能。

4.3 基于雙向約束的金字塔LK光流實驗結(jié)果分析

4.3.1 算法參數(shù)設(shè)置

基于金字塔的LK光流算法主要由四個參數(shù)影響計算結(jié)果，分別是：a）式（13）的θ值；b）金字塔的構(gòu)建方式以及最大層數(shù)；c）最大迭代次數(shù)；d）特征提取過程的網(wǎng)格大小。

a）θ值的大小會影響追蹤成功的光流精度和數(shù)目。θ越大則保留的數(shù)目越多，但其中包含誤差較大的光流；反之則代表保留少數(shù)更準(zhǔn)確的光流。θ的具體值可根據(jù)需求調(diào)整，本文實驗中θ=0.01。

b）采用相對效果最好的高斯金字塔^［22］。金字塔最大層數(shù)設(shè)置為maxLevel=3。

c）迭代次數(shù)選擇默認(rèn)的maxCount=30。

d）特征提取的網(wǎng)格大小和特征點的數(shù)目相關(guān)，也直接影響光流的性能，這里采用10×10的網(wǎng)格，對于1 280×720的圖像可以提取出大約8 000個特征點，其足夠用于后期的位姿恢復(fù)。

在后續(xù)的實驗中，根據(jù)對于算法的逐步改進(jìn)，本文分為三種級別的優(yōu)化來進(jìn)行實驗結(jié)果的對比。其分別是使用動態(tài)窗口（Optimization_a）、使用動態(tài)窗口以及半精度浮點（Optimi-zation_b）、在b級優(yōu)化上使用新的雙向約束（Optimization_c）。

4.3.2 負(fù)載不均衡問題的實驗結(jié)果

圖9給出了在解決負(fù)載不均衡問題時所提出的兩種方案與OpenCV的時間對比。通過圖9展示的結(jié)果看出，這兩個方案都能較好地解決負(fù)載不平衡問題。在本文的720P數(shù)據(jù)上，性能相比于OpenCV的GPU版本分別提升了2.2和2.9倍。對比這兩個方案可以發(fā)現(xiàn)，雖然動態(tài)窗口增加了計算量，但其性能卻優(yōu)于一維線程調(diào)度方法。通過表2和3的誤差統(tǒng)計可以看出，使用動態(tài)窗口（Optimization_a）并沒有使光流精度有所下降。

4.3.3 降低計算位寬和雙向約束的實驗結(jié)果

合理地應(yīng)用3.3節(jié)介紹的降低計算位寬方法以及2.4節(jié)部分的新的約束方法可以進(jìn)一步提升算法的性能，具體如圖10所示。圖中給出了僅使用動態(tài)窗口（Optimization_a）、使用動態(tài)窗口和半精度浮點（Optimization_b）、在b級基礎(chǔ)上使用新的約束（Optimization_c）的性能對比。其結(jié)果表明，降低計算位寬精度（Optimization_b）和新的約束方法（Optimization_c）都可以進(jìn)一步提升光流計算的性能，在多組數(shù)據(jù)集上都達(dá)到了30 fps以上的性能。最終在720P數(shù)據(jù)上，新的方法將原本OpenCV在GPU上需要117.7 ms的計算加速到28.3 ms，使性能提升了4.1倍。其中動態(tài)窗口和半精度浮點對于性能的提升最為顯著。

表2和3的誤差統(tǒng)計說明，使用降低計算位寬對光流的精度沒有較大影響，而新的約束方法使得光流的誤差明顯增大。通過分析可以找到統(tǒng)計誤差增大的原因并不是計算出的結(jié)果不準(zhǔn)確，而是因為使用新的方法會使雙性約束的約束性變?nèi)?，從而保留下更多的光流。如圖11所示，該光流按照原本的方法會被刪除，但是新的方法卻將其保留下來，這些保留下來的光流導(dǎo)致光流整體的誤差變大。后續(xù)4.4節(jié)的實驗表明在SLAM系統(tǒng)中，該方法雖然會保留更多低精度的光流并使得恢復(fù)位姿的計算耗時略微增加，但整個耗時在減少，從而可以提升整個系統(tǒng)的精度。

在原本的雙向約束中，θ值只與光流的數(shù)目和精度有很強的相關(guān)性，與計算耗時幾乎沒有關(guān)系。無論是想要更多精度偏低的光流，還是更少更為準(zhǔn)確的光流，其耗時基本都是穩(wěn)定不變的。而在2.4節(jié)新提出的約束中，θ值的變化不但影響光流的結(jié)果，同時會導(dǎo)致計算耗時的變化，適當(dāng)調(diào)整θ值可以更好地權(quán)衡性能與精度。如圖12所示，θ值越大，則反向光流的迭代次數(shù)越少，計算速度則會越快，反之計算速度則會越慢。這表明新的約束方案不僅有效減少了冗余的計算，而且可以針對不同的需求調(diào)整θ的值，使得其在實際應(yīng)用中更加靈活。

除上述分析外，表4給出本文和其他LK光流計算在性能上的對比總結(jié)。根據(jù)1.2節(jié)的時間復(fù)雜度分析，表4詳細(xì)地列出了這些方法和復(fù)雜度相關(guān)的各類數(shù)值的大小，表中所有方法的金字塔總層數(shù)都為4層。這些不同實現(xiàn)之間的性能差距不僅和計算平臺以及參與計算的數(shù)據(jù)量有關(guān)，而且與數(shù)據(jù)本身的性質(zhì)相關(guān)。本文的實現(xiàn)主要是針對車載場景下，圖片整體變化較為劇烈，光流步長較大的情況，在相同的配置和環(huán)境下有效地提升了整體的計算性能。

4.4 真實場景實驗測試

4.4.1 單目SLAM算法模塊介紹

本文在實際車載場景下構(gòu)建并測試一套完整的單目視覺SLAM系統(tǒng)。該系統(tǒng)主要完成傳感器信息讀取、自身軌跡恢復(fù)與稀疏點云重建，使之能夠在車載場景下完成實時定位與建圖。如圖13所示，該SLAM系統(tǒng)主要包含圖片預(yù)處理、LK光流估計、相機位姿恢復(fù)與稀疏點云重建^{［24，25］}四個模塊。在車輛行駛過程中，該系統(tǒng)實時地從攝像頭中得到當(dāng)前路況的RGB圖片，經(jīng)過整個系統(tǒng)的計算得到自身軌跡以及稀疏三維點云。

考慮到嵌入式設(shè)備的實際性能，實驗過程中在LK光流計算模塊中采用隱藏幀的機制。如圖14所示，每次對PreImage提取到的特征進(jìn)行連續(xù)k幀的光流計算，然后得到PreImage與CurrImage對應(yīng)的光流。在之后的模塊中只考慮這兩幀的信息，中間幀的信息在后續(xù)計算中被隱藏。

4.4.2 真實場景測試結(jié)果

在實驗過程中，K的值取1。各個模塊的具體耗時統(tǒng)計如表5所示，光流計算模塊速度的提升使得整個系統(tǒng)的耗時大幅減少。需要注意的是，在Optimization_c中，使用新的約束方法后，會導(dǎo)致部分不精確光流被保留下來，因此使用RANSAC算法的恢復(fù)相機位姿模塊的耗時會有所提升，但整個系統(tǒng)的耗時下降。本文在車載場景下進(jìn)行SLAM系統(tǒng)的實地測試，攝像頭輸出的圖片頻率是30 fps。由于SLAM系統(tǒng)處理頻率低于攝像頭輸出的頻率，為了保證系統(tǒng)測試的實時性，SLAM系統(tǒng)盡可能地處理最新幀的信息，對于無法及時處理的圖片選擇丟棄。具體效果如圖15所示。圖15（a）所代表的實驗中，SLAM系統(tǒng)中光流計算的頻率大約是9 fps，位姿輸出的頻率大約是4 fps；圖15（b）所代表的實驗中，光流計算頻率為28 fps左右，位姿輸出的頻率為14 fps左右。從圖15可以看出，優(yōu)化后的光流計算能達(dá)到更高的幀率，從而成功追蹤到更多光流。該實驗表明，新的方法提升了整個SLAM的性能，從而更好地獲得了行駛軌跡和稀疏點云的結(jié)果。

5 結(jié)束語

本文以Jetson TX2嵌入式開發(fā)板為基礎(chǔ)，使用CUDA編程模型，實現(xiàn)了更加高效的實時光流計算。通過對特征提取使用網(wǎng)格劃分，提升了算法并行度與性能，并解決了特征點聚集的問題。通過對OpenCV實現(xiàn)的光流算法進(jìn)行分析，解決了其負(fù)載不均衡問題，然后合理降低計算位寬和使用新的雙向約束減少冗余計算，成功提升了光流計算的效率。最后實現(xiàn)了從特征提取到forward-backward pyramid LK光流的實時計算。通過將該算法應(yīng)用于實際車載場景下的SLAM系統(tǒng)中，成功使得系統(tǒng)的性能以及精度都獲得了極大的提升。

在車載場景下，LK光流算法能夠快速地從單目相機圖片中得到幀間的2D對應(yīng)關(guān)系，并將其應(yīng)用于后續(xù)的位姿恢復(fù)和點云計算。通過對光流算法的優(yōu)化，充分利用硬件特性，可以有效提升性能并滿足精度要求，從而用于真實的車載SLAM系統(tǒng)，為車載場景的實時定位和點云構(gòu)建提供一條可行的解決方案。

參考文獻(xiàn)：

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

［2]Horn B K， Schunck B G. Determining optical flow［J］.Artificial Intelligence，1981，17（1-3）：185-203.

［3]Dosovitskiy A， Fischer P， Ilg E， et al. FlowNet： learning optical flow with convolutional networks［C］//Proc of IEEE international Conference on Computer Vision. Piscataway， NJ： IEEE Press， 2015： 2758-2766.

［4]Ilg E， Mayer N， Saikia T， et al. FlowNet 2.0： evolution of optical flow estimation with deep networks［C］//Proc of IEEE Conference on Computer Vision and Pattern Recognition. Piscataway， NJ： IEEE Press， 2017： 1647-1655.

［5]Ranjan A， Black M J. Optical flow estimation using a spatial pyramid network［C］//Proc of IEEE Conference on Computer Vision and Pattern Recognition. Piscataway， NJ： IEEE Press， 2017： 2720-2729.

［6]Zhai Mingliang， Xiang Xuezhi， Lyu Ning， et al. Optical flow and scene flow estimation： a survey［J］.Pattern Recognition，2021，114（3）： article ID 107861.

［7]Gómez-Rodríguez J ， Lamarca J， Morlana J， et al. SD-DefSLAM： semi-direct monocular SLAM for deformable and intracorporeal scenes［C］//Proc of IEEE International Conference on Robotics and Automation.Piscataway，NJ：IEEE Press，2021：5170-5177.

［8]Tang Chuanye， Zhao Xinwen， Chen Jianfeng， et al. Fast stereo visual odometry based on LK optical flow and ORB-SLAM2［J］.Multimedia Systems，2020，2020（10）：1-10.

［9]Yu Chao， Liu Zuxin， Liu Xinjun， et al. DS-SLAM： a semantic visual SLAM towards dynamic environments［C］//Proc of IEEE/RSJ International Conference on Intelligent Robots and Systems.Piscataway，NJ：IEEE Press，2018：1168-1174.

［10]Bouguet J Y. Pyramidal implementation of the affine Lucas Kanade feature tracker description of the algorithm［EB/OL］.（2000-06-02）.http：//robots.stanford.edu/cs223b04/algo_tracking.pdf.

［11]Kalal Z， Mikolajczyk K， Matas J. Forward-backward error： automatic detection of tracking failures［C］//Proc of the 20th International Conference on Pattern Recognition.Piscataway，NJ：IEEE Press，2010：2756-2759.

［12]Marzat J， Dumortier Y， Ducrot A. Real-time dense and accurate pa-rallel optical flow using CUDA［C］//Proc of International Conference in Central Europe on Computer Graphics.2009.

［13]吳進(jìn)，李喬深，閔育，等.一種基于OpenCL的Lukas-Kanade光流并行加速算法［J］.電訊技術(shù)，2018，58（8）：871-877.（Wu Jin， Li Qiaoshen， Min Yu， et al. A Lukas-Kanade optical flow parallel acceleration algorithm based on OpenCL［J］.Telecommunication Engineering，2018，58（8）：871-877.）

［14]Plyer A， Le Besnerais G， Champagnat F. Massively parallel Lucas Kanade optical flow for real-time video processing applications［J］.Journal of Real-Time Image Processing，2016，11（4）：713-730.

［15]Shi Jianbo. Good features to track［C］//Proc of IEEE Conference on Computer Vision and Pattern Recognition.Piscataway，NJ：IEEE Press，1994：593-600.

［16]盧勝男，李小和.結(jié)合雙向光流約束的特征點匹配車輛跟蹤方法［J］.交通運輸系統(tǒng)工程與信息，2017，17（4）：76-82.（Lu Shengnan， Li Xiaohe. Vehicle tracking method using feature point matching combined with bidirectional optical flow［J］.Journal of Transportation Systems Engineering and Information Technology，2017，17（4）：76-82.）

［17]Amert T， Otterness N， Yang Ming， et al. GPU scheduling on the NVIDIA TX2： hidden details revealed［C］//Proc of IEEE Real-Time Systems Symposium.Piscataway，NJ：IEEE Press，2017：104-115.

［18]Basulto-Lantsova A， Padilla-Medina J A， Perez-Pinal F J， et al. Performance comparative of OpenCV template matching method on jetson TX2 and jetson nano developer kits［C］//Proc of the 10th Annual Computing and Communication Workshop and Conference.Pisca-taway，NJ：IEEE Press，2020：0812-0816.

［19]Mellempudi N， Srinivasan S， Das D， et al. Mixed precision training with 8-bit floating point［EB/OL］.（2019-05-29）.https：//arxiv.53yu.com/pdf/1905.12334.pdf.

［20]Baker S， Matthews I. Lucas-Kanade 20 years on： a unifying framework［J］.International Journal of Computer Vision，2004，56（3）：221-255.

［21]Baker S， Scharstein D， Lewis J P， et al. A database and evaluation methodology for optical flow［J］.International Journal of Computer Vision，2011，92（1）：1-31.

［22]Sharmin N， Brad R. Optimal filter estimation for Lucas-Kanade optical flow［J］.Sensors，2012，12（9）：12694-12709.

［23]Nam T， Kim S， Jung D. Hardware implementation of KLT tracker for real-time intruder detection and tracking using on-board camera［J］.International Journal of Aeronautical and Space Sciences，2019，20（1）：300-314.

［24]Singandhupe A， La H M. A review of SLAM techniques and security in autonomous driving［C］//Proc of the 3rd IEEE International Conference on Robotic Computing.Piscataway，NJ：IEEE Press，2019：602-607.

［25]Campos C， Elvira R， Rodríguez J J G， et al. ORB-SLAM3： an accurate open-source library for visual， visual-inertial， and multimap SLAM［J］.IEEE Trans on Robotics，2021，37（6）：1874-1890.