基于嵌入式GPU的pyramid LK光流法高速計算方法研究

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

關鍵詞：LK光流； 嵌入式GPU； CUDA； SLAM； 并行計算

中圖分類號：TP302 文獻標志碼：A

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

doi：10.19734/j.issn.1001-3695.2021.12.0675

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

作者簡介：孫瑞鑫（1997-），男，河南信陽人，碩士，主要研究方向為計算機體系結構；朱國梁（1989-），男，甘肅人，博士，主要研究方向為計算機體系結構和編譯器；謝雙鐿（1995-），男，湖南醴陵人，碩士，主要研究方向為計算機體系結構；郭雪亮（1993-），男，河北邢臺人，碩士，主要研究方向為3D視覺；柴志雷（1975-），男（通信作者），山西人，教授，博導，博士，主要研究方向為計算機體系結構（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）算法一直以來都是計算機視覺領域研究的重點，其本質是計算運動圖像的連續幀之間像素點的運動矢量，在自動駕駛、三維重建、目標檢測、場景分割等領域具有巨大應用潛力。光流算法目前主要分為以知識驅動的傳統方法和以數據驅動的深度學習方法。傳統光流算法主要是依賴視覺理論知識進行推導計算，其中較為著名的是LK光流^［1］和HS光流^［2］。數據驅動的方法主要是依托于深度學習知識設計出光流網絡，其中較為著名的FlowNet^［3］、FlowNet2.0^［4］、SpyNet^［5］等都在多組公開數據集上取得了較好的效果。然而光流訓練集的構建既耗時又昂貴，隨著使用場景的變化可能需要重新構建訓練集并訓練網絡，這使得該類方法目前還處于研究階段，很難廣泛投入應用^［6］。相較之下，傳統算法無須額外的使用代價，在實際應用中具有更強的泛用性，目前的研究表明^［7～9］在SLAM系統中應用傳統的LK光流依舊是方便且可行的。

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

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

本文的主要貢獻如下：

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

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

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

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

1.1 KLT角點檢測算法

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

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

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

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

通過式（3）求出每個像素點對應的協方差矩陣的最小特征值。

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

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

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

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

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

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

通過讓目標函數式（5）對d求導，使其值為0以求極值，并對其進行泰勒展開可得

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

其中：

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

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

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

1.2.2 光流的雙向約束

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

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

2 從算法本身優化計算性能

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

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

2.2 網格劃分的特征提取設計

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

a）將圖像劃分成若干個固定大小的網格區域。

b）對每個網格區域局部執行KLT角點檢測算法，并在每個區域內提取一個特征點。

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

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

2.3 減少冗余的特征提取

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

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

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

該設計使得在連續幀的追蹤過程中，只對失去信息的網格進行特征提取，有效減少了計算次數。

2.4 提取終止迭代設計

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

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

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

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

3.1 嵌入式GPU架構

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

3.2 光流計算的負載分析及優化

3.2.1 GPU線程負載不均衡問題分析

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

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

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

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

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

3.2.2 金字塔模型中動態窗口設計

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

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

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

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

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

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

該方法在保證金字塔結構的同時，針對GPU計算特性動態調整窗口大小，更好地發揮了硬件性能。對這兩個方案實驗結果的比較和分析，將在4.3.2節中詳細闡述。

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

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

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

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

FP32轉FP16的轉換公式如下：

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

最后在b做reduce后使用式（23）進行縮放：

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

4 實驗結果

4.1 實驗環境介紹

軟件環境：Ubuntu 16.04，CUDA 9.0，OpenCV 3.3.1，g++5.4.0。

硬件環境：Stereo zed2攝像頭，Jetson TX2開發套件。

對照組介紹：OpenCV中實現的KLT角點檢測和LK光流的GPU優化版本。后續實驗都是與OpenCV 3.3.1中的實現對比。

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

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

實際場景介紹：基于Stereo zed2攝像頭和TX2開發板在實際駕駛過程中使用SLAM系統進行測試。

4.2 角點檢測的實驗結果分析

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

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

圖8給出不同網格大小下特征提取的耗時對比。可以看出無論采用多大的網格，新的角點檢測方法都遠快于原本方法，平均提升了2倍左右的性能。其中圖8（b）表明對于連續幀光流的追蹤，由于很多的角點信息被繼承下來，所以其性能表現得更加優秀，平均提升了3.2倍的性能。

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

4.3.1 算法參數設置

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

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

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

c）迭代次數選擇默認的maxCount=30。

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

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

4.3.2 負載不均衡問題的實驗結果

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

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

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

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

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

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

4.4 真實場景實驗測試

4.4.1 單目SLAM算法模塊介紹

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

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

4.4.2 真實場景測試結果

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

5 結束語

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

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

參考文獻：

[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]吳進，李喬深，閔育，等.一種基于OpenCL的Lukas-Kanade光流并行加速算法［J］.電訊技術，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]盧勝男，李小和.結合雙向光流約束的特征點匹配車輛跟蹤方法［J］.交通運輸系統工程與信息，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.