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

為了充分利用面試題的學習價值砂碉，建議大家先自行解答一遍，再對照參考答案刻两！

溫馨提示：文章過長增蹭，且題庫僅放送了一部分，建議先收藏加關(guān)注再花時間自行查閱~

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

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

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

4. 視差與深度的關(guān)系

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.室內(nèi)SLAM與自動駕駛SLAM有什么區(qū)別？

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

23. 地圖點的構(gòu)建方法有哪些

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

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

忍兹碜濉！先別看答案残制！

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

=-=沒錯，請參考初茶！

1 SIFT和SUFT的區(qū)別

構(gòu)建圖像金字塔颗祝，SIFT特征利用不同尺寸的圖像與高斯差分濾波器卷積；SURF特征利用原圖片與不同尺寸的方框濾波器卷積恼布。

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

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

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

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

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

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

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

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

參考：多視圖幾何總結(jié)——等距變換疮薇、相似變換胸墙、仿射變換和射影變換

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

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

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

补履，秩只有2，因此F的自由度為7剿另。它自由度比本質(zhì)矩陣多的原因是多了兩個內(nèi)參矩陣箫锤。

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

參考多視圖幾何總結(jié)——基礎(chǔ)矩陣馏臭、本質(zhì)矩陣和單應矩陣的自由度分析

4?視差與深度的關(guān)系

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

5 描述PnP算法

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

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

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

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

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

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

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

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

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

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

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也會造成結(jié)果不穩(wěn)定饰序，因此穩(wěn)定性差

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

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

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

卡爾曼濾波：

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

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

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

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

粒子濾波：

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

粒子濾波的推導中概念有很多终抽，最重要的推導過程是重要性采樣過程，其思路就是我原本的采樣分布是不知道的桶至，我如何從一個已知的分布中采樣昼伴，通過加權(quán)的方式使得從已知的分布中采樣的粒子分布和原本未知的分布中采樣的粒子分布結(jié)果一致，從而引入SIS粒子濾波镣屹，再進一步加入重采樣后就引入了SIR粒子濾波圃郊。

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

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

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

10如何求解Ax=b的問題

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

11什么是極線約束

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

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

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

13解釋SLAM中的綁架問題

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

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

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

特征點法

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

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

直接法：

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

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

15EKF和BA的區(qū)別

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

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

16邊緣檢測算子有哪些螟碎？

邊緣檢測一般分為三步眉菱，分別是濾波、增強掉分、檢測俭缓。基本原理都是用高斯濾波器進行去噪酥郭，之后在用卷積內(nèi)核尋找像素梯度华坦。常用有三種算法：canny算子，sobel算子不从，laplacian算子

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

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

laplacian算子：二階微分算子扔役，具有旋轉(zhuǎn)不變性帆喇，容易受噪聲影響，不能檢測邊緣的方向亿胸，一般不直接用于檢測邊緣坯钦，而是判斷明暗變化预皇。

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總結(jié)——ORB SLAM2中關(guān)鍵知識點總結(jié)

視覺SLAM總結(jié)——SVO中關(guān)鍵知識點總結(jié)

視覺SLAM總結(jié)——LSD SLAM中關(guān)鍵知識點總結(jié)

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

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

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

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

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

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

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

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

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

這里我補充下：

注意到上面的結(jié)構(gòu)圖中，節(jié)點Basevertex<D,T>逸爵，BaseBinaryEdge<D,E,VertexXi,VertexXj>和BlockSolver<>等都是模板類蚣常，我們可以根據(jù)自己的需要初始化不同類型的節(jié)點和邊以及求解器，以O(shè)RB 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的時候自己想辦法寫后端的時候很納悶這個圖是怎么構(gòu)建起來的，在ORB或者SVO里面束亏，所有的地圖點和關(guān)鍵幀都是以類的形式存在的铃在，例如在ORB中是先將關(guān)鍵幀的節(jié)點添加起來，然后添加空間點枪汪，然后遍歷空間點中記錄的與哪些關(guān)鍵幀有關(guān)系涌穆，然后相應ID的關(guān)鍵幀的節(jié)點和空間點的節(jié)點連接起來怔昨，然后就把圖建立起來了，我覺得不寫類好像沒有什么其他更好的辦法了宿稀。

21室內(nèi)SLAM與自動駕駛SLAM有什么區(qū)別趁舀？

這是個開放題，參考無人駕駛技術(shù)與SLAM的契合點在哪里祝沸，有什么理由能夠讓SLAM成為無人駕駛的關(guān)鍵技術(shù)矮烹？

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

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