ORB-SLAM 系統(tǒng)特征分析研究①

薛 瑞 李 易 李文明 安述倩 葉笑春 唐志敏

(?處理器芯片全國重點實驗室(中國科學院計算技術(shù)研究所) 北京 100190)

(??中國科學院大學計算機科學與技術(shù)學院 北京 100049)

0 引言

同步定位和建圖(simultaneous localization and mapping,SLAM)作為自動駕駛汽車、機器人、無人機、虛擬現(xiàn)實和增強現(xiàn)實等自主系統(tǒng)的關(guān)鍵技術(shù)[1-3],能很好地應用在包括路徑規(guī)劃、導航、避障和3D 重建等高級任務中。在過去的幾十年,無論在學術(shù)界還是工業(yè)界,SLAM 一直是研究的熱點[4-7],其主要工作是設(shè)計自動導航系統(tǒng)、建立和更新周圍3D 環(huán)境同時估計自身傳感器的當前位置。

近年來,基于特征點法的SLAM 系統(tǒng)與其他基于直接法的SLAM 系統(tǒng)相比,對運動較快的場景具有更好的魯棒性,且系統(tǒng)處理較為穩(wěn)定,因此受到了特別的關(guān)注[8]。在基于特征點法的SLAM 系統(tǒng)中,ORB[9](oriented FAST and rotated BRIEF)特征計算方法相比于尺度不變特征變換(scale-invariant feature transform,SIFT)或加速魯棒特征(speeded up robust features,SURF)算法具有良好的旋轉(zhuǎn)和縮放不變性,計算效率和魯棒性更高,因此被廣泛采用。

由于ORB-SLAM 系統(tǒng)應用于現(xiàn)實世界的真實場景中,主要輸入數(shù)據(jù)為大量的連續(xù)圖像幀,因此針對海量的圖像幀數(shù)據(jù)快速處理的需求,提高ORBSLAM 系統(tǒng)的處理性能成為當前亟待解決的問題,因此對ORB-SLAM 系統(tǒng)進行特征分析研究以指導面向ORB-SLAM 系統(tǒng)的底層硬件架構(gòu)的設(shè)計具有重要的意義。目前已有的底層硬件架構(gòu)設(shè)計有eSLAM[8]、HcveAcc[10]和PISCES[11]等。然而這些加速結(jié)構(gòu)沒有對算法進行深入的分析,缺乏為后續(xù)底層硬件架構(gòu)設(shè)計提供有效的指導。針對上述問題,本文對ORB-SLAM 系統(tǒng)進行了較為全面的應用特征分析,以指導面向ORB-SLAM 系統(tǒng)的底層硬件架構(gòu)的設(shè)計。

本文首先從對ORB-SLAM 系統(tǒng)介紹出發(fā),分別詳細闡述ORB-SLAM 系統(tǒng)[12]3 個線程的工作原理及其2個優(yōu)化版本ORB-SLAM2[13]和ORB-SLAM3[14],并選取ORB-SLAM2 作為本文實驗的目標系統(tǒng)。然后通過實驗ORB-SLAM2 系統(tǒng),得到并分析系統(tǒng)的熱點函數(shù)特征。最后根據(jù)對熱點函數(shù)特征的分析結(jié)果,提出設(shè)計面向ORB-SLAM 系統(tǒng)的底層硬件架構(gòu)的需求。

本文的主要貢獻包括:(1)完整地介紹了ORBSLAM 系統(tǒng)跟蹤、地圖構(gòu)建和回環(huán)檢測3 個線程的工作原理;(2)實驗分析并重點闡述了ORB-SLAM2系統(tǒng)中的熱點函數(shù)及執(zhí)行特征;(3)通過對熱點函數(shù)進行詳細的特征分析實驗,得到了面向ORBSLAM 系統(tǒng)對底層硬件架構(gòu)的需求。

1 相關(guān)工作

當前主流的SLAM 系統(tǒng)由4 個階段組成,分別為前端視覺里程計(visual odometry,VO)、后端優(yōu)化(optimization)、回環(huán)檢測(loop closing)和三維地圖建立(mapping)[12-17]。前端視覺里程計階段用來求解傳感器在各個時刻的位置信息;后端優(yōu)化階段用來全局優(yōu)化前端視覺里程計長時間的累計誤差;回環(huán)檢測階段用來檢測傳感器是否到達之前到過的位置;三維地圖建立階段用來構(gòu)建傳感器在移動過程中周圍的3D 點云地圖。

前端視覺里程計有特征點法和直接法2 種求解方法,現(xiàn)有的基于特征點法的SLAM 系統(tǒng)有Mono-SLAM[18]、PTAM[15]、ORB-SLAM[12]及其優(yōu)化系統(tǒng)ORB-SLAM2[13]和ORB-SLAM3[14]等,基于直接法的有DTAM[19]和LSD-SLAM[17]等;只關(guān)注于前端視覺里程計部分的VIO 設(shè)計方案有基于半直接法的SVO[16]、基于特征點法的OKVIS[20]和基于直接法的DSO[21]等;只關(guān)注于3D 重建部分的系統(tǒng)有Kinect-Fusion[22]、InfiniTAM[23]、ElasticFusion[24]等。表1 總結(jié)了最具有代表性的各個SLAM 系統(tǒng)。其中Mono-SLAM 系統(tǒng)是第一個實時的單目視覺SLAM 系統(tǒng)[18],擴展卡爾曼濾波(extended Kalman filter,EKF)作為后端優(yōu)化的方法,追蹤前端稀疏的特征點,以傳感器當前狀態(tài)和所有路標點為狀態(tài)量,更新特征點的均值和協(xié)方差。該方法的缺點是場景窄、路標數(shù)有限、稀疏特征點易丟失。PTAM 系統(tǒng)[15]提出并實現(xiàn)了跟蹤和建圖的并行化,首次區(qū)分出前后端概念,即把跟蹤需要實時響應的圖像數(shù)據(jù)部分作為前端,地圖優(yōu)化放在后端進行。PTAM 系統(tǒng)是第一個使用非線性優(yōu)化作為后端的方案,并提出了關(guān)鍵幀機制,該方法的缺點是場景小、跟蹤容易丟失。ORBSLAM 系統(tǒng)[12]圍繞ORB 特征計算,計算效率比SIFT 和SURF 算法高,且具有良好的旋轉(zhuǎn)和縮放不變性,并創(chuàng)新地使用了3 個線程來完成SLAM 系統(tǒng),分別為實時跟蹤特征點線程、地圖構(gòu)建線程和回環(huán)檢測線程,該方法的缺點是每幅圖像都需要計算ORB 特征,三線程結(jié)構(gòu)給CPU 帶來了較重負擔。ORB-SLAM2 系統(tǒng)[13]在單目ORB-SLAM 系統(tǒng)基礎(chǔ)上增加了雙目和RGB-D 傳感器的輸入,并通過使用光束平差法(bundle adjustment,BA),獲得了比基于迭代最近點或者光度和深度誤差最小化的方法更高的精度;ORB-SLAM2 系統(tǒng)使用近距離和遠距離的特征方法,雙目效果比直接法更精確且定位時可以重用地圖,是一種輕量級的方法,在CPU 上可以實現(xiàn)實時性;ORB-SLAM2 系統(tǒng)增加的雙目和RGB-D 方法可以解決原來ORB-SLAM 系統(tǒng)在單目回環(huán)檢測時嚴重的漂移問題。ORB-SLAM3 系統(tǒng)[14]是一種緊密集成的視覺慣性SLAM 系統(tǒng)。對比于ORB-SLAM系統(tǒng)和ORB-SLAM2 系統(tǒng),ORB-SLAM3 系統(tǒng)在慣性測量單元初始化階段引入最大后驗概率估計思想,同時采用了多子地圖系統(tǒng)。

表1 代表性的各個SLAM 系統(tǒng)的總結(jié)

隨著SLAM 系統(tǒng)需要的處理性能不斷提高,近幾年學術(shù)界和工業(yè)界涌現(xiàn)出一些面向SLAM 系統(tǒng)的加速結(jié)構(gòu)設(shè)計。對于使用廣泛且本文重點關(guān)注的基于ORB-SLAM 系統(tǒng)的加速結(jié)構(gòu)設(shè)計如針對ORBSLAM 系統(tǒng)中耗時最高的前端視覺里程計的特征提取部分進行基于FPGA 硬件結(jié)構(gòu)設(shè)計[25]。文獻[26]提出了一種基于CGRA結(jié)構(gòu)的加速器設(shè)計,從輸入圖像幀數(shù)據(jù)以及跟蹤任務和列文伯格-馬夸爾特算法(Levenberg-Marquardt,LM)的計算特點進行粗粒度可重構(gòu)的硬件邏輯設(shè)計。文獻[8]提出了eSLAM,在FPGA 平臺上設(shè)計了基于ORB 的特征提取和特征匹配2 部分的高能效加速器。在eSLAM 基礎(chǔ)上,文獻[10]提出了HcveAcc,針對ORB-SLAM系統(tǒng)的跟蹤任務中的高密集度的特征提取和高精度的描述子生成部分設(shè)計了基于ASIC 的加速器結(jié)構(gòu),實現(xiàn)ORB-SLAM 系統(tǒng)運行的高性能和高精度。文獻[11]設(shè)計了一個基于特征點法SLAM 系統(tǒng)的前端視覺里程計任務的EKF 和ORB 部分以及后端優(yōu)化任務的BA 部分的流水線結(jié)構(gòu)PISCES,利用其計算稀疏性降低訪存功耗和計算延時,提高處理性能。表2 總結(jié)了近幾年最具代表性的ORB-SLAM系統(tǒng)加速器,并分析各加速器存在的問題。針對表2中存在的問題,本文進行了面向ORB-SLAM 系統(tǒng)的應用特征分析研究,為面向ORB-SLAM 系統(tǒng)的底層硬件架構(gòu)設(shè)計提供了指導性建議。

表2 近幾年最具有代表性的ORB-SLAM 系統(tǒng)加速器

2 ORB-SLAM 系統(tǒng)介紹

ORB-SLAM 系統(tǒng)[12]是一種基于單目的、圍繞ORB 特征計算的SLAM 系統(tǒng),使用跟蹤、地圖構(gòu)建和回環(huán)檢測3 個線程進行同步定位和建圖工作。ORB-SLAM 系統(tǒng)流程圖如圖1 所示。

圖1 ORB-SLAM 系統(tǒng)流程圖

2.1 跟蹤線程

跟蹤線程主要負責定位傳感器并確定何時插入新的關(guān)鍵幀,主要由ORB 特征提取、初始位姿估計、局部地圖跟蹤和關(guān)鍵幀選取4 部分組成。

ORB 特征提取[9]部分是由FAST(features from accelerated segment test)算法[27]改進得到。ORB 利用FAST 算法對插入的新圖像幀進行FAST 角點搜索,即搜索整個圖像幀中所有與其周圍鄰域內(nèi)足夠多的像素點的灰度值相差較大的像素點。圖2 所示為圖像幀中某一個角點和周圍鄰域內(nèi)的像素點,給定比較的閾值以及圓圈大小(本文以圓圈大小16為例)。首先比較像素點1 和9,如果其和中心像素的灰度值差的絕對值均小于閾值,則該點不是角點,否則將它作為候選角點;再比較像素點1、5、9 和13與中心像素點灰度值差的絕對值,如果其中有3個絕對值大于閾值,則該點繼續(xù)作為候選點,否則舍棄;最后比較像素點1～16 與中心像素的灰度值差,如果連續(xù)大于或小于閾值的像素點超過8 個,則該點為特征點,否則舍棄。由于此時搜索出的角點過多,因此本文對檢測出來的角點群利用非極大值抑制方法進行FAST 角點的篩選,并在保留的FAST 角點上計算方向,以此來實現(xiàn)特征點的旋轉(zhuǎn)不變性,最后計算當前圖像幀中角點的BRIEF(binary robust independent elementary features)描述子[28]用于與上一幀中的角點的BRIEF 描述子進行特征匹配。

圖2 圖像幀中某一角點與其鄰域點

初始位姿估計部分首先判斷當前幀與上一幀的特征匹配是否成功,若成功則假設(shè)傳感器為恒速運動模型來預測傳感器當前位姿,并搜索與上一幀觀察到的地圖點進行對應,最后與對應的地圖點進行位姿優(yōu)化。若沒有足夠的位姿與地圖點的匹配對,則使用上一幀中更廣泛的位姿附近的地圖點的搜索范圍。若當前幀與上一幀的特征匹配失敗,則需要全局重定位,首先將當前幀轉(zhuǎn)化為詞袋向量[29],利用ORB 特征詞典與所有關(guān)鍵幀進行匹配,然后對每個關(guān)鍵幀進行隨機抽樣一致性(random sample consensus,RANSAC)迭代,并使用PnP 算法[30]進行傳感器位姿求解。若傳感器位姿有足夠多可被使用的正確數(shù)據(jù),則搜索與所有關(guān)鍵幀觀察到的地圖點進行對應,通過匹配對進行位姿優(yōu)化。初始位姿估計部分的流程圖如圖3 所示。

圖3 初始位姿估計部分流程圖

局部地圖跟蹤部分首先更新局部關(guān)鍵幀和局部地圖點,將局部地圖點與當前幀進行匹配,最后使用最小化重投影誤差方法實現(xiàn)對傳感器位姿的進一步優(yōu)化。

關(guān)鍵幀選取部分通過舍棄不滿足條件的關(guān)鍵幀,保留滿足以下條件的關(guān)鍵幀,保證系統(tǒng)具有魯棒性。

(1)自上次全局重定位后,必須已經(jīng)過大于20幀;

(2)地圖構(gòu)建部分處于空閑狀態(tài),或自上次插入關(guān)鍵幀后已經(jīng)過大于20 幀;

(3)當前幀至少跟蹤到50 個點;

(4)當前幀比與當前幀共享最多地圖點的幀跟蹤到少于90%的點。

2.2 地圖構(gòu)建

地圖構(gòu)建線程負責處理新的關(guān)鍵幀并執(zhí)行BA,以實現(xiàn)傳感器周圍地圖的最佳重建。此部分主要由關(guān)鍵幀插入、地圖點驗證、新地圖點生成、本地BA和本地關(guān)鍵幀選取5 部分組成。

關(guān)鍵幀插入部分首先更新共視圖,然后更新與跟關(guān)鍵幀中有大多數(shù)共同的點相連接在一起的生成樹,最后計算關(guān)鍵幀的詞袋向量。

地圖點驗證部分主要工作是需要地圖點必須在創(chuàng)建后的前3 個關(guān)鍵幀期間通過限制性測試,以確保它們是可進行特征匹配的并且不會錯誤地進行三角化計算。

新地圖點生成部分負責從共視圖中已連接的關(guān)鍵幀進行三角化計算ORB 特征點來創(chuàng)建新地圖點。對于關(guān)鍵幀中每個未匹配的ORB 特征點,在另一個關(guān)鍵幀中搜索與其他不匹配點進行匹配,丟棄不滿足對極約束的匹配。最后對ORB 特征點匹配對進行三角化計算生成新地圖點。

本地BA 部分主要優(yōu)化當前關(guān)鍵幀、在共視圖中所有連接到當前關(guān)鍵幀的關(guān)鍵幀以及被關(guān)鍵幀觀測到的所有地圖點。所有其他觀測到地圖點但未連接到當前關(guān)鍵幀的關(guān)鍵幀均包含在優(yōu)化中,同時保持固定不變。在優(yōu)化中間和結(jié)束時,將標記為異常值的觀測值丟棄。

本地關(guān)鍵幀選取部分主要檢測和刪除冗余的關(guān)鍵幀以維持重構(gòu)過程的緊湊。

2.3 回環(huán)檢測

回環(huán)檢測線程主要由候選幀選取、相似度計算、回環(huán)融合和全局優(yōu)化4 部分組成。此線程采用了詞袋模型來檢測回環(huán),若檢測到回環(huán),則進行相似度轉(zhuǎn)換的計算,以告知回路中累積的漂移。然后通過建立當前幀和回環(huán)幀之間的匹配關(guān)系,融合重復的點,最后對相似性約束進行位姿圖優(yōu)化[31],來修正視覺里程計的局部誤差,以實現(xiàn)全局一致性。

2.4 ORB-SLAM2 系統(tǒng)

ORB-SLAM2 系統(tǒng)[13]是在ORB-SLAM 系統(tǒng)基礎(chǔ)上提出來的一個支持單目、雙目和RGB-D 的完整SLAM 系統(tǒng)方案。它能夠?qū)崿F(xiàn)地圖重用、回環(huán)檢測和重定位功能。同時ORB-SLAM2 系統(tǒng)在后端優(yōu)化采用了基于單目和雙目的BA 方法,此方法允許米制比例尺的軌跡精確度評估。此外,ORB-SLAM2 系統(tǒng)包含一個輕量級的定位模式,該模式能夠在允許零點漂移的條件下,利用前端視覺里程計來追蹤未建圖的區(qū)域并匹配特征點。ORB-SLAM2 系統(tǒng)流程圖如圖4 所示,其中線框部分,即跟蹤線程的預處理輸入部分和全局BA 部分為ORB-SLAM2 系統(tǒng)在ORB-SLAM 系統(tǒng)的基礎(chǔ)上的改進。

圖4 ORB-SLAM2 系統(tǒng)流程圖

本文采用ORB-SLAM2 系統(tǒng)進行系統(tǒng)特征分析研究的原因如下。

(1)從第3 節(jié)可以看出,ORB-SLAM 系統(tǒng)時間占比最大部分為跟蹤線程,而ORB-SLAM3 系統(tǒng)相比于ORB-SLAM2 系統(tǒng)的主要優(yōu)化在于增加了慣性測量單元集成、初始化和縮放修正部分以及地圖合并部分,未涉及跟蹤線程部分的計算,對系統(tǒng)特征分析影響較小。因此ORB-SLAM3 系統(tǒng)的改進部分并不是本文的研究目標。

(2)相比于ORB-SLAM 系統(tǒng)和ORB-SLAM3 系統(tǒng),ORB-SLAM2 系統(tǒng)在SLAM 系統(tǒng)優(yōu)化及底層硬件架構(gòu)設(shè)計等方面均具有更廣泛的應用[8,10-11,25-26]。

因此本文實驗部分將采用ORB-SLAM2 系統(tǒng)進行系統(tǒng)熱點函數(shù)及系統(tǒng)特征分析。

3 ORB-SLAM2 系統(tǒng)熱點函數(shù)分析實驗

本節(jié)將對ORB-SLAM2 系統(tǒng)進行整體性能分析,并選取其中的熱點函數(shù)。

實驗平臺:本文采用基于Skylake 架構(gòu)的64 位Intel i5-6500 桌面電腦處理器和基于ARM v8 架構(gòu)的ARM Neoverse-N1 處理器作為實驗平臺進行對比實驗。

數(shù)據(jù)集:本文選取3 個典型開源數(shù)據(jù)集KITTI[32]、EuRoC[33]和TUM RGB-D[34]作為實驗數(shù)據(jù)集。

KITTI 數(shù)據(jù)集由德國卡爾斯魯厄理工學院和豐田美國技術(shù)研究院聯(lián)合創(chuàng)辦,是目前國際上最大的自動駕駛場景下的計算機視覺算法評測數(shù)據(jù)集[32],該數(shù)據(jù)集包含城鎮(zhèn)、鄉(xiāng)村等自動駕駛可覆蓋到的道路及道路周邊信息的圖像幀序列。EuRoC 數(shù)據(jù)集是室內(nèi)微型飛行器和慣性測量單元收集視覺慣性數(shù)據(jù)[33],包含蘇黎世聯(lián)邦理工學院的machine hall 和一個普通房間vicon room 的室內(nèi)場景的圖像幀序列。TUM RGB-D 數(shù)據(jù)集是由慕尼黑工業(yè)大學計算機視覺實驗室公布的[34],該數(shù)據(jù)集均從實際環(huán)境中采集,包含針對紋理豐富的辦公室場景以及不同幀數(shù)大小、不同運動速度、不同結(jié)構(gòu)紋理等場景的圖像幀序列。

處理器各詳細參數(shù)及數(shù)據(jù)集分別如表3 和表4所示。

表3 處理器各詳細參數(shù)

表4 數(shù)據(jù)集

本文使用Linux 的性能評估軟件Perf 進行實驗測試,針對ORB-SLAM2 的單目、雙目和RGB-D 3 種傳感器輸入,分別在KITTI、EuRoC 和TUM 數(shù)據(jù)集上進行了單目實驗,KITTI 和EuRoC 數(shù)據(jù)集上進行了雙目實驗以及將TUM 作為RGB-D 輸入數(shù)據(jù)集進行ORB-SLAM2 系統(tǒng)實驗,得到160 個在表3 所示的Intel 和ARM 處理器下測試ORB-SLAM2 系統(tǒng)中各函數(shù)的時間占比。并對這160 個時間占比結(jié)果中排名前5 的函數(shù)進行了統(tǒng)計得到如圖5 所示的熱點函數(shù)分析結(jié)果。

由圖5 所示的分析結(jié)果可以看出,由于Perf 評估軟件統(tǒng)計函數(shù)執(zhí)行時間是統(tǒng)計函數(shù)中沒有調(diào)用其他函數(shù)部分的執(zhí)行時間,因此包含F(xiàn)AST 角點提取函數(shù)FAST_t 和角點分數(shù)計算以用來進行非極大值抑制篩選角點的函數(shù)CornerScore 的ORB 特征提取函數(shù)ExtractorORB 執(zhí)行時間占比最高為67%。由于ExtractorORB 函數(shù)為前端視覺里程計部分的熱點函數(shù),對于后端非線性優(yōu)化部分,由圖5 可以看出,優(yōu)化求解器函數(shù)Solver 執(zhí)行時間占比最高為17%,且由于ORB 特征提取函數(shù)ExtractorORB 和優(yōu)化求解器函數(shù)Solver 為學術(shù)界和工業(yè)界熱門的研究部分[8,10-11,25-26],因此本節(jié)將重點介紹和分析ORB特征提取函數(shù)ExtractorORB 和優(yōu)化求解器函數(shù)Solver。

圖5 熱點函數(shù)分析

作為前端視覺里程計階段的熱點函數(shù)ExtractorORB,主要由跟蹤線程調(diào)用,在ORB-SLAM2 系統(tǒng)中,跟蹤線程作為主線程首先調(diào)用熱點函數(shù)ExtractorORB 中operator 函數(shù)進行ORB 特征點的提取。其中包含ComputePyramid 函數(shù)用來計算圖像金字塔;ComputeKeyPointsOctTree 函數(shù)對圖像金字塔進行角點檢測,提取圖像金字塔中各層圖像的關(guān)鍵點;以及ComputeDescriptors 函數(shù)對圖像金字塔的每層計算BRIEF 描述子。在ComputeKeyPointsOctTree函數(shù)中調(diào)用了時間占比最高的FAST_t 函數(shù)來進行FAST 角點的提取。熱點函數(shù)ExtractorORB 的函數(shù)調(diào)用關(guān)系如圖6 所示。

圖6 熱點函數(shù)ExtractorORB 的函數(shù)調(diào)用關(guān)系

作為后端優(yōu)化階段的熱點函數(shù)優(yōu)化求解器函數(shù)Solver 分別由跟蹤線程的GlobalBundleAdjustement、BundleAdjustment 和PoseOptimization 函數(shù)、地圖構(gòu)建線程中的LocalBundleAdjustment 函數(shù)以及回環(huán)檢測線程中的OptimizeEssentialGraph 和OptimizeSim3函數(shù)調(diào)用。這6 個函數(shù)均通過調(diào)用設(shè)置線性求解器LinearSolver 為Dense、PCG、Cholmod 之一的方法;設(shè)置塊求解器BlockSolver 為是否可變尺寸的方式;設(shè)置求解器求解算法SetAlgorithm 為高斯牛頓(Gauss Newton,GN)、列文伯格-馬夸爾特算法(LM)和信賴域(Dogleg)之一;初始化稀疏優(yōu)化器SparseOptimizer,并設(shè)置局部關(guān)鍵幀頂點以及地圖點頂點和優(yōu)化對應的邊,加入優(yōu)化器中;最后調(diào)用優(yōu)化器的optimize 函數(shù)中的熱點函數(shù)Solver 進行迭代優(yōu)化求出傳感器位置的最優(yōu)解。Solver 函數(shù)的函數(shù)調(diào)用關(guān)系如圖7 所示。

圖7 熱點函數(shù)Solver 的函數(shù)調(diào)用關(guān)系

4 ORB-SLAM2 系統(tǒng)特征分析實驗

通過對ORB-SLAM2 系統(tǒng)進行整體性能分析,本節(jié)將針對系統(tǒng)中時間占比較高的ORB 特征提取函數(shù)ExtractorORB 和優(yōu)化求解器函數(shù)Solver 進行進一步函數(shù)特征分析。本文主要從IPC(instruction per clock)、分支預測失效率、一級數(shù)據(jù)緩存讀失效率、最后一級緩存失效率和最后一級緩存MPKI 等指標進行函數(shù)特征分析。

4.1 IPC

圖8 和圖9 為2 個熱點函數(shù)ExtractorORB 和Solver 分別在Intel 和ARM 處理器對160 個數(shù)據(jù)集進行實驗得到的IPC 值對比圖。圖10 所示為在圖8和圖9 基礎(chǔ)上計算得到的2 個熱點函數(shù)在所有數(shù)據(jù)集計算得到的IPC 平均值對比圖。

圖8 兩個熱點函數(shù)在Intel 處理器運行所有數(shù)據(jù)集的IPC 值對比圖

圖9 兩個熱點函數(shù)在ARM 處理器運行所有數(shù)據(jù)集的IPC 值對比圖

圖10 熱點函數(shù)的IPC 平均值對比圖

由圖8、圖9 和圖10 可以看出,在Intel 處理器中ExtractorORB函數(shù)的IPC明顯高于Solver函數(shù),是Solver 函數(shù)的2 倍多。由于ExtractorORB 函數(shù)主要功能是進行ORB 特征提取,在提取FAST 角點和計算BRIEF 描述子時主要指令為簡單的位運算和比較指令,而Solver 函數(shù)主要功能是進行位姿增量和地標增量的計算,主要指令為矩陣向量的加減乘除運算,相比于ExtractorORB 函數(shù),指令復雜度較高。且由后文4.3 節(jié)可知,Solver 函數(shù)的一級讀緩存失效率明顯高于ExtractorORB 函數(shù),則每個cycle 訪存命中率低,每個cycle 執(zhí)行的指令要低于ExtractorORB 函數(shù)。而在ARM 處理器中,ExtractorORB 函數(shù)的IPC 要低于Solver 函數(shù),主要由于ARM 處理器使用的是精簡指令集(reduced instruction set computer,RISC)系統(tǒng),與Intel 使用的復雜指令集(complex instruction set computer,CISC)系統(tǒng)相比每條指令較為簡單。針對Solver 函數(shù)中的矩陣向量操作,如乘加操作,ARM 處理器每個cycle 需要執(zhí)行乘法和加法2 條指令,而Intel 處理器只需要執(zhí)行1 條乘加指令,因此在ARM 處理中,簡單位運算操作較多的ExtractorORB 函數(shù)的IPC 要低于復雜的矩陣向量操作的Solver 函數(shù)。

4.2 分支預測失效率

圖11 和圖12 為2 個熱點函數(shù)ExtractorORB 和Solver 分別在Intel 和ARM 處理器對160 個數(shù)據(jù)集實驗得到的分支預測失效率對比圖。圖13和圖14所示為在圖11 和圖12 基礎(chǔ)上計算得到的2 個熱點函數(shù)分別在Intel 和ARM 2 臺處理器執(zhí)行所有數(shù)據(jù)集計算得到的分支預測失效率平均值對比圖以及在EuRoC、KITTI 和TUM 3 個數(shù)據(jù)集的分支預測失效率平均值對比圖。

圖11 兩個熱點函數(shù)在Intel 處理器運行所有數(shù)據(jù)集的分支預測失效率對比圖

圖12 兩個熱點函數(shù)在ARM 處理器運行所有數(shù)據(jù)集的分支預測失效率對比圖

圖13 熱點函數(shù)的分支預測失效率平均值對比圖

圖14 熱點函數(shù)在3 個數(shù)據(jù)集的分支預測失效率平均值對比圖

由圖11、圖12 和圖13、圖14 實驗結(jié)果可以看出2 個熱點函數(shù)失效率相似,由于ExtractorORB函數(shù)的分支預測指令主要是在對每幀數(shù)據(jù)進行FAST角點提取時進行的對幀中每一個像素點進行的for循環(huán)遍歷操作,Solver 函數(shù)的分支預測指令主要是對多組傳感器位姿和路標點數(shù)據(jù)組成得到的雅克比矩陣進行的for 循環(huán)遍歷得到傳感器位姿和路標點的增量值。因此2 個函數(shù)的分支預測失效均是由for 循環(huán)產(chǎn)生,因此失效率相似,且在Intel 和ARM 2臺處理器中執(zhí)行表現(xiàn)出來的趨勢相似。

4.3 一級數(shù)據(jù)讀緩存讀失效率

如圖15 所示為熱點函數(shù)ExtractorORB 和Solver分別在Intel 和ARM 處理器對160 個數(shù)據(jù)集實驗得到的一級數(shù)據(jù)緩存讀失效率平均值對比圖。

圖15 熱點函數(shù)的一級數(shù)據(jù)緩存讀失效率平均值對比圖

由圖15 實驗結(jié)果可以看出,ExtractorORB 和Solver 函數(shù)的一級緩存數(shù)據(jù)命中率較高,但相比于ExtractorORB 函數(shù),Solver 函數(shù)命中率較低。主要由于ORB-SLAM2 系統(tǒng)中的ORB 特征提取函數(shù)和優(yōu)化求解器函數(shù)整體均具有較好的數(shù)據(jù)規(guī)則訪問特征,但由于ExtractorORB 函數(shù)對于數(shù)據(jù)的訪問局部性更好,且數(shù)據(jù)具有很好的流式讀特征;而Solver 函數(shù)的輸入數(shù)據(jù)主要為矩陣、向量,在進行矩陣乘加等操作時,由于輸入數(shù)據(jù)為行存儲,但讀取數(shù)據(jù)進行計算的方式有列讀取,數(shù)據(jù)訪問局部性相比ExtractorORB 函數(shù)較差,因此ExtractorORB 函數(shù)的一級數(shù)據(jù)緩存讀訪問失效率比Solver 函數(shù)較高。相比于Intel 處理器,2 個熱點函數(shù)在ARM 處理器上的一級數(shù)據(jù)緩存讀失效率更低,主要由于ARM 處理器具有更大的一級數(shù)據(jù)緩存。

4.4 最后一級緩存失效率

如圖16 所示為2 個熱點函數(shù)ExtractorORB 和Solver 分別在Intel 和ARM 處理器對160 個數(shù)據(jù)集實驗得到的最后一級緩存失效率平均值對比結(jié)果圖。

圖16 熱點函數(shù)的最后一級緩存失效率平均值對比圖

由圖16 實驗結(jié)果可以看出,在Intel 處理器中ExtractorORB 函數(shù)的最后一級緩存失效率是Solver函數(shù)的2 倍。由于ExtractorORB 函數(shù)的數(shù)據(jù)局部性好,且一級緩存命中率高,因此最后一級緩存命中率低于Solver 函數(shù)。而ARM 處理器中2 個函數(shù)的最后一級緩存失效率明顯低于Intel 處理器執(zhí)行結(jié)果,主要由于ARM 處理器的三級緩存大于Intel 處理器的三級緩存。

4.5 最后一級緩存MPKI

圖17 和圖18 所示為2 個熱點函數(shù)ExtractorORB和Solver 分別在Intel 和ARM 處理器對160 個數(shù)據(jù)集實驗得到的最后一級緩存MPKI 失效率對比圖。

由圖17 和圖18 實驗結(jié)果可以看出,無論在Intel 處理器還是ARM 處理器執(zhí)行,Solver 函數(shù)的最后一級緩存MPKI 值遠大于ExtractorORB 函數(shù)。ExtractorORB 函數(shù)指令簡單,且數(shù)據(jù)訪問規(guī)則、局部性好。由圖19 所示的2 個熱點函數(shù)執(zhí)行所有數(shù)據(jù)集的訪存指令占比的平均值可以看出,Solver 函數(shù)的訪存指令占比較高,由于Solver 函數(shù)中有大量的矩陣向量計算,因此需要對矩陣向量進行多次訪存操作;而ExtractorORB 函數(shù)主要訪存和計算為位運算,因此訪存指令占比較高,對于每千條指令的最后一級緩存的失效率相比于Solver 函數(shù)較低。Solver 函數(shù)相比于ExtractorORB 函數(shù)在進行底層硬件架構(gòu)設(shè)計時需要針對Solver 函數(shù)的矩陣向量數(shù)據(jù)設(shè)計更規(guī)則的數(shù)據(jù)處理結(jié)構(gòu),以及在對Solver 函數(shù)數(shù)據(jù)進行運算時設(shè)計更有效的向量運算部件以提高Solver函數(shù)的運算速度,進而提高ORB-SLAM 系統(tǒng)的性能。

圖17 熱點函數(shù)在Intel 處理器執(zhí)行所有數(shù)據(jù)集的最后一級緩存MPKI 值對比圖

圖18 熱點函數(shù)在ARM 處理器執(zhí)行所有數(shù)據(jù)集的最后一級緩存MPKI 值對比圖

圖19 熱點函數(shù)執(zhí)行所有數(shù)據(jù)集的訪存指令占比平均值

4.6 運算類型特征

通過算法分析可以得出ORB-SLAM2 系統(tǒng)中的2 個熱點函數(shù)具有以下運算特點。

(1)對于前端視覺里程計部分中的ExtractorORB 熱點函數(shù),其主要為單比特計算,在進行底層硬件架構(gòu)設(shè)計時可通過增加單比特計算邏輯來提高其處理速度。

(2)對于后端非線性優(yōu)化部分中的Solver 熱點函數(shù),其主要為浮點計算,在進行底層硬件架構(gòu)設(shè)計時可通過增加浮點乘加部件來提高其處理性能。其計算模式更適用于Vector 或SIMD 模式。

5 結(jié)論

隨著同步定位和建圖技術(shù)的廣泛應用,基于特征點法的同步定位和建圖系統(tǒng)ORB-SLAM 系統(tǒng)成為熱門的研究方向。目前缺乏面向基于ORB-SLAM系統(tǒng)底層硬件架構(gòu)設(shè)計指導的系統(tǒng)特征分析的研究。因此本文首先針對ORB-SLAM 系統(tǒng)進行了詳細的介紹;然后對ORB-SLAM2 系統(tǒng)進行了熱點函數(shù)實驗分析,得到了ExtractorORB 和Solver 2 個熱點函數(shù);最后對2 個熱點函數(shù)進行了IPC、分支預測失效率、一級數(shù)據(jù)緩存讀失效率、最后一級緩存失效率和最后一級緩存MPKI 等特征的評估,為面向ORB-SLAM 系統(tǒng)的底層硬件架構(gòu)設(shè)計提供了指導性建議。