手機站首頁散文詩歌雜文隨筆日記小小說

散文網(wǎng) » 生活 »日常 » 視覺SLAM面試題匯總（2019年秋招題庫參考）——第一部分

視覺SLAM面試題匯總（2019年秋招題庫參考）——第一部分

2020-08-29 11:51 作者:深藍學院 0人讀過 | 我要投稿

近期將有較多面試題庫進行放送，建議評論關注及時接收！

視覺SLAM總結——視覺SLAM面試題匯總

1. SIFT和SUFT的區(qū)別

2. 相似變換、仿射變換、射影變換的區(qū)別

3. Homography、Essential和Fundamental Matrix的區(qū)別

4. 視差與深度的關系

5. 描述PnP算法

6. 閉環(huán)檢測常用方法

7. 給一個二值圖，求最大連通域

8. 梯度下降法、牛頓法、高斯-牛頓法的區(qū)別

9. 推導一下卡爾曼濾波、描述下粒子濾波

10. 如何求解Ax=b的問題

11. 什么是極線約束

12. 單目視覺SLAM中尺寸漂移是怎么產(chǎn)生的

13. 解釋SLAM中的綁架問題

14. 描述特征點法和直接法的優(yōu)缺點

15. EKF和BA的區(qū)別

16. 邊緣檢測算子有哪些？

17. 簡單實現(xiàn)cv::Mat()

18. 10個相機同時看到100個路標點，問BA優(yōu)化的雅克比矩陣多少維

19. 介紹經(jīng)典的視覺SLAM框架

20. 介紹下你熟悉的非線性優(yōu)化庫

21.室內SLAM與自動駕駛SLAM有什么區(qū)別？

22. 什么是緊耦合、松耦合？優(yōu)缺點。

23. 地圖點的構建方法有哪些

24. 如果對于一個3D點，我們在連續(xù)幀之間形成了2D特征點之間的匹配，但是這個匹配中可能存在錯誤的匹配。請問你如何去構建3D點？

25. RANSAC在選擇最佳模型的時候用的判斷準則是什么?

忍住！先別看答案！

------------------------------你以為我會直接給你答案麻？嘿嘿---------------------------

=-=沒錯，請參考！

1?SIFT和SUFT的區(qū)別

構建圖像金字塔，SIFT特征利用不同尺寸的圖像與高斯差分濾波器卷積；SURF特征利用原圖片與不同尺寸的方框濾波器卷積。

特征描述子，SIFT特征有4×4×8=128維描述子，SURF特征有4×4×4=64維描述子

特征點檢測方法，SIFT特征先進行非極大抑制，再去除低對比度的點，再通過Hessian矩陣去除邊緣響應過大的點；SURF特征先利用Hessian矩陣確定候選點，然后進行非極大抑制

特征點主方向，SIFT特征在正方形區(qū)域內統(tǒng)計梯度幅值的直方圖，直方圖最大值對應主方向，可以有多個主方向；SURF特征在圓形區(qū)域內計算各個扇形范圍內x、y方向的haar小波響應，模最大的扇形方向作為主方向

2相似變換、仿射變換、射影變換的區(qū)別

等距變換：相當于是平移變換（t）和旋轉變換（R）的復合，等距變換前后長度，面積，線線之間的角度都不變。自由度為6（3+3）

相似變換：等距變換和均勻縮放（S）的一個復合，類似相似三角形，體積比不變。自由度為7（6+1）

仿射變換：一個平移變換（t）和一個非均勻變換（A）的復合，A是可逆矩陣，并不要求是正交矩陣，仿射變換的不變量是:平行線，平行線的長度的比例，面積的比例。自由度為12（9+3）

射影變換：當圖像中的點的齊次坐標的一般非奇異線性變換，射影變換就是把理想點（平行直線在無窮遠處相交）變換到圖像上，射影變換的不變量是:重合關系、長度的交比。自由度為15（16-1）

參考：多視圖幾何總結——等距變換、相似變換、仿射變換和射影變換

3?Homography、Essential和Fundamental Matrix的區(qū)別

Homography Matrix可以將一個二維射影空間的點變換該另一個二維射影空間的點，如下圖所示，在不加任何限制的情況下，僅僅考慮二維射影空間中的變換，一個單應矩陣H HH可由9個參數(shù)確定，減去scale的一個自由度，自由度為8。

?Fundamental Matrix對兩幅圖像中任何一對對應點x和x′基礎矩陣F都滿足條件：

，秩只有2，因此F的自由度為7。它自由度比本質矩陣多的原因是多了兩個內參矩陣。

Essential matrix：本質矩是歸一化圖像坐標下的基本矩陣的特殊形式，其參數(shù)由運動的位姿決定，與相機內參無關，其自由度為6，考慮scale的話自由度為5。

參考多視圖幾何總結——基礎矩陣、本質矩陣和單應矩陣的自由度分析

4?視差與深度的關系

在相機完成校正后，則有 d/b=f/z,其中d表示視差，b表示基線，f是焦距，z是深度。這個公式其實很好記，在深度和焦距確定的情況下，基線越大，視差也會越大。

?5?描述PnP算法

已知空間點世界坐標系坐標和其像素投影，公式如下

?目前一共有兩種解法，直接線性變換方法（一對點能夠構造兩個線性約束，因此12個自由度一共需要6對匹配點），另外一種就是非線性優(yōu)化的方法，假設空間坐標點準確，根據(jù)最小重投影誤差優(yōu)化相機位姿。

目前有兩個主要場景場景，其一是求解相機相對于某2維圖像/3維物體的位姿；其二就是SLAM算法中估計相機位姿時通常需要PnP給出相機初始位姿。

在場景1中，我們通常輸入的是物體在世界坐標系下的3D點以及這些3D點在圖像上投影的2D點，因此求得的是相機坐標系相對于世界坐標系(Twc)的位姿

在場景2中，通常輸入的是上一幀中的3D點（在上一幀的相機坐標系下表示的點）和這些3D點在當前幀中的投影得到的2D點，所以它求得的是當前幀相對于上一幀的位姿變換

6?閉環(huán)檢測常用方法

ORB??SLAM中采用的是詞袋模型進行閉環(huán)檢測篩選出候選幀，再通過求解Sim3判斷最合適的關鍵幀

LSD SLAM中的閉環(huán)檢測主要是根據(jù)視差、關鍵幀連接關系，找出候選幀，然后對每個候選幀和測試的關鍵幀之間進行雙向Sim3跟蹤，如果求解出的兩個李代數(shù)滿足馬氏距離在一定范圍內，則認為是閉環(huán)成功

7?給一個二值圖，求最大連通域

這個之后單獨寫一篇博客來研究這個好了，二值圖的連通域應該是用基于圖論的深度優(yōu)先或者廣度優(yōu)先的方法，后來還接觸過基于圖的分割方法，采用的是并查集的數(shù)據(jù)結構，之后再作細致對比研究。

8?梯度下降法、牛頓法、高斯-牛頓法的區(qū)別

在BA優(yōu)化、PnP、直接法里面都有接觸到非線性優(yōu)化問題，上面幾種方法都是針對對非線性優(yōu)化問題提出的方法，將非線性最優(yōu)化問題作如下展開，就可以獲得梯度下降法和牛頓法

梯度下降法是一個一階最優(yōu)化算法，通常也稱為最速下降法。要使用梯度下降法找到一個函數(shù)的局部極小值，必須向函數(shù)上當前點對應梯度（或者是近似梯度）的反方向的規(guī)定步長距離點進行迭代搜索。因此指保留一階梯度信息。缺點是過于貪心，容易走出鋸齒路線。

?牛頓法是一個二階最優(yōu)化算法，基本思想是利用迭代點處的一階導數(shù)(梯度)和二階導數(shù)(Hessen矩陣)對目標函數(shù)進行二次函數(shù)近似。因此保留二階梯度信息。缺點是需要計算H矩陣，計算量太大。? ??

?而把非線性問題，先進行一階展開，然后再作平方處理就可以得到高斯-牛頓法和列文博格方法

?高斯-牛頓法對上式展開并對Δx進行求導即可得高斯牛頓方程，其實其就是使用

對牛頓法的H矩陣進行替換，但是

有可能為奇異矩陣或變態(tài)，Δx也會造成結果不穩(wěn)定，因此穩(wěn)定性差

列文博格法就是在高斯-牛頓法的基礎上對Δx添加一個信賴區(qū)域，保證其只在展開點附近有效，即其優(yōu)化問題變?yōu)閹в胁坏仁郊s束的優(yōu)化問題，利用Lagrange乘子求解

9?推導一下卡爾曼濾波、描述下粒子濾波

用自己的描述下，僅供參考：

卡爾曼濾波：

卡爾曼濾波就是通過運動方程獲得均值和方差的預測值，然后結合觀測方程和預測的方差求得卡爾曼增益，然后在用卡爾曼增益更行均值和方差的預測值而獲得估計值。

卡爾曼濾波推導的思路是（其中一種）先假定有這么一個修正公式

?構真實值和估計值之間的協(xié)方差矩陣，然后通過對對角線元素求和獲得方差表達式，我們的修正公式是需要使得方差最小，因此把方差表達式對

求導就可以獲得卡爾曼增益的表達式，然后從先驗到預測值的方差公式可以通過求預測值和真實值的協(xié)方差矩陣獲得。

粒子濾波：

粒子濾波最常用的是SIR，其算法是用運動方程獲得粒子的狀態(tài)采樣，然后用觀測方程進行權值更新，通過新的粒子加權平均就獲得新的估計狀態(tài)，最后非常重要的一步就是重采用。

粒子濾波的推導中概念有很多，最重要的推導過程是重要性采樣過程，其思路就是我原本的采樣分布是不知道的，我如何從一個已知的分布中采樣，通過加權的方式使得從已知的分布中采樣的粒子分布和原本未知的分布中采樣的粒子分布結果一致，從而引入SIS粒子濾波，再進一步加入重采樣后就引入了SIR粒子濾波。

具體的可以參看我的另外兩個總結博客

概率機器人總結——粒子濾波先實踐再推導

概率機器人總結——(擴展)卡爾曼濾波先實踐再推導

10如何求解Ax=b的問題

參看我的另外一個總結博客多視圖幾何總結——基礎矩陣、本質矩陣和單應矩陣的求解過程

11?什么是極線約束

所謂極線約束就是說同一個點在兩幅圖像上的映射，已知左圖映射點p1，那么右圖映射點p2一定在相對于p1的極線上，這樣可以減少待匹配的點數(shù)量。如下圖：

?12單目視覺SLAM中尺寸漂移是怎么產(chǎn)生的

用單目估計出來的位移，與真實世界相差一個比例，叫做尺度。這個比例在單目初始化時通過三角化確定，但單純靠視覺無法確定這個比例到底有多大。由于SLAM過程中噪聲的影響，這個比例還不是固定不變的。修正方式是通過回環(huán)檢測計算Sim3進行修正。

13解釋SLAM中的綁架問題

綁架問題就是重定位，是指機器人在缺少之前位置信息的情況下，如何去確定當前位姿。例如當機器人被安置在一個已經(jīng)構建好地圖的環(huán)境中，但是并不知道它在地圖中的相對位置，或者在移動過程中，由于傳感器的暫時性功能故障或相機的快速移動，都導致機器人先前的位置信息的丟失，在這種情況下如何重新確定自己的位置。

初始化綁架可以闡述為一種通常狀況初始化問題，可使用蒙特卡洛估計器，即粒子濾波方法，重新分散粒子到三維位形空間里面，被里程信息和隨機擾動不斷更新，初始化粒子聚集到/收斂到可解釋觀察結果的區(qū)域。追蹤丟失狀態(tài)綁架，即在綁架發(fā)生之前，系統(tǒng)已經(jīng)保存當前狀態(tài)，則可以使用除視覺傳感器之外的其他的傳感器作為候補測量設備。

14描述特征點法和直接法的優(yōu)缺點

特征點法

優(yōu)點：1. 沒有直接法的強假設，更加精確；2. 相較與直接法，可以在更快的運動下工作，魯棒性好

缺點：1. 特征提取和特征匹配過程耗時長；2. 特征點少的場景中無法使用；3.只能構建稀疏地圖

直接法：

優(yōu)點：1.省去了特征提取和特征匹配的時間，速度較快；2. 可以用在特征缺失的場合；3. 可以構建半稠密/稠密地圖

缺點：1. 易受光照和模糊影響；2.運動必須慢；3.非凸性，易陷入局部極小解

15EKF和BA的區(qū)別

（1） EKF假設了馬爾科夫性，認為k時刻的狀態(tài)只與k-1時刻有關。BA使用所有的歷史數(shù)據(jù)，做全體的SLAM

（2） EKF做了線性化處理，在工作點處用一階泰勒展開式近似整個函數(shù)，但在工作點較遠處不一定成立。BA每迭代一次，狀態(tài)估計發(fā)生改變，我們會重新對新的估計點做泰勒展開，可以把EKF看做只有一次迭代的BA

16邊緣檢測算子有哪些？

邊緣檢測一般分為三步，分別是濾波、增強、檢測?；驹矶际怯酶咚篂V波器進行去噪，之后在用卷積內核尋找像素梯度。常用有三種算法：canny算子，sobel算子，laplacian算子

canny算子：一種完善的邊緣檢測算法，抗噪能力強，用高斯濾波平滑圖像，用一階偏導的有限差分計算梯度的幅值和方向，對梯度幅值進行非極大值抑制，采用雙閾值檢測和連接邊緣。

sobel算子：一階導數(shù)算子，引入局部平均運算，對噪聲具有平滑作用，抗噪聲能力強，計算量較大，但定位精度不高，得到的邊緣比較粗，適用于精度要求不高的場合。

laplacian算子：二階微分算子，具有旋轉不變性，容易受噪聲影響，不能檢測邊緣的方向，一般不直接用于檢測邊緣，而是判斷明暗變化。

17簡單實現(xiàn)cv::Mat()

1810個相機同時看到100個路標點，問BA優(yōu)化的雅克比矩陣多少維

因為誤差對相機姿態(tài)的偏導數(shù)的維度是2×6,對路標點的偏導數(shù)是2×3，又10個相機可以同時看到100個路標點，所以一共有10×100×2行，100×3+10×6個塊。

?19介紹經(jīng)典的視覺SLAM框架

視覺SLAM總結——ORB SLAM2中關鍵知識點總結

視覺SLAM總結——SVO中關鍵知識點總結

視覺SLAM總結——LSD SLAM中關鍵知識點總結

20介紹下你熟悉的非線性優(yōu)化庫

非線性優(yōu)化庫一般有ceres和g2o兩種，我比較熟悉的是g2o，看下g2o的結構圖

它表示了g2o中的類結構。首先根據(jù)前面的代碼經(jīng)驗可以發(fā)現(xiàn)，我們最終使用的optimizer是一個SparseOptimizer對象，因此我們要維護的就是它(對它進行各種操作)。一個SparseOptimizer是一個可優(yōu)化圖(OptimizableGraph)，也是一個超圖(HyperGraph)。而圖中有很多頂點(Vertex)和邊(Edge)。頂點繼承于BaseVertex，邊繼承于BaseUnaryEdge、BaseBinaryEdge或BaseMultiEdge。它們都是抽象的基類，實際有用的頂點和邊都是它們的派生類。我們用SparseOptimizer.addVertex和SparseOptimizer.addEdge向一個圖中添加頂點和邊，最后調用SparseOptimizer.optimize完成優(yōu)化。

在優(yōu)化之前還需要制定求解器和迭代算法。一個SparseOptimizer擁有一個OptimizationAlgorithm，它繼承自Gauss-Newton, Levernberg-Marquardt, Powell’s dogleg三者之一。同時，這個OptimizationAlgorithm擁有一個Solver，它含有兩個部分。一個是 SparseBlockMatrix，用于計算稀疏的雅可比和海塞矩陣；一個是線性方程求解器，可從PCG、CSparse、Choldmod三選一，用于求解迭代過程中最關鍵的一步：

?因此理清了g2o的結構，也就知道了其使用流程。在之前已經(jīng)說過了，這里就再重復一遍：

（1）選擇一個線性方程求解器，PCG、CSparse、Choldmod三選一，來自g2o/solvers文件夾

（2）選擇一個BlockSolver，用于求解雅克比和海塞矩陣，來自g2o/core文件夾

（3）選擇一個迭代算法，GN、LM、DogLeg三選一，來自g2o/core文件夾

參考G2O圖優(yōu)化基礎和SLAM的Bundle Adjustment(光束法平差)

這里我補充下：

注意到上面的結構圖中，節(jié)點Basevertex<D,T>，BaseBinaryEdge<D,E,VertexXi,VertexXj>和BlockSolver<>等都是模板類，我們可以根據(jù)自己的需要初始化不同類型的節(jié)點和邊以及求解器，以ORB SLAM2為例，分析下后端最典型的全局BA所用的邊、節(jié)點和求解器：

（1）邊是EdgeSE3ProjectXYZ，它其實就是繼承自BaseBinaryEdge<2, Vector2d, VertexSBAPointXYZ, VertexSE3Expmap>，其模板類型里第一個參數(shù)是觀測值維度，這里的觀測值是其實就是我們的像素誤差u,v u,vu,v，第二個參數(shù)就是我們觀測值的類型，第三個第四個就是我們邊兩頭節(jié)點的類型；

（2）相機節(jié)點VertexSE3Expmap，它其實就是繼承自BaseVertex<6, SE3Quat>，其模板類第一個參數(shù)就是其維度，SE3是六維的這沒毛病，第二個就是節(jié)點的類型，SE3Quat就是g2o自定義的SE3的類，類里面寫了各種SE3的計算法則；

（3）空間點節(jié)點VertexSBAPointXYZ，它其實就是繼承自BaseVertex<3, Vector3d>，其模板類第一個參數(shù)是說明咱空間點的維度是三維，第二個參數(shù)說明這個點的類型是Vector3d；

（4）求解器是BlockSolver_6_3，它其實就是BlockSolver< BlockSolverTraits<6, 3> >，6,3分別指代的就是邊兩邊的維度了。

我記得我剛開始學習SLAM的時候自己想辦法寫后端的時候很納悶這個圖是怎么構建起來的，在ORB或者SVO里面，所有的地圖點和關鍵幀都是以類的形式存在的，例如在ORB中是先將關鍵幀的節(jié)點添加起來，然后添加空間點，然后遍歷空間點中記錄的與哪些關鍵幀有關系，然后相應ID的關鍵幀的節(jié)點和空間點的節(jié)點連接起來，然后就把圖建立起來了，我覺得不寫類好像沒有什么其他更好的辦法了。

21室內SLAM與自動駕駛SLAM有什么區(qū)別？

這是個開放題，參考無人駕駛技術與SLAM的契合點在哪里，有什么理由能夠讓SLAM成為無人駕駛的關鍵技術？

22?什么是緊耦合、松耦合？優(yōu)缺點。

這里默認指的是VIO中的松緊耦合，這里參考深藍學院的公開課里面介紹：