『壹』 全局視覺定位系統研究的意義
全局視覺定位
1. 引言
自主機器人是機器人研究的重點方向，定位和導航是自主機器人研究的核心問題。機器人在執行任務過程中需要確定自身當前位置，根據目標位置和當前位置之間的關系計算如何到達目的地完成任務，其中前者要解決的是自定位問題，後者是導航問題，本文主要研究前者。基於視覺的定位技術還能幫助盲人、視弱以至普通人確定自身位置。 環境模型是定位的基礎。基於模型的定位方法包括基於環境三維模型和基於拓撲地圖的定位方法。環境三維模型的建模過程非常復雜，特別是在室外的場景中建模可能遇到極大的困難。拓撲定位用圖的形式來表示環境模型，其中圖中的節點表示環境中的地點，連接節點的邊表示地點之間的聯系，拓撲定位目的是確定機器人當前的位置與地圖中的哪個節點最近，也就是機器人處於哪個地點。
在無人駕駛中，感知、定位、規劃決策、控制是四個基本的系統模塊。由於當前演算法還無法實現絕對的智能，因此依然需要大量的先驗知識來提高模塊性能、魯棒性，以實現安全的自動駕駛。其中，高精地圖是對道路及周邊環境先驗知識的集成。而建立在地圖之上的准確定位，是判斷行車狀況的重要依據，為後續的感知、規劃決策提供有力支撐。
用於定位的主要數據源目前主要有 GPS、激光雷達、視覺、毫米波雷達。對於視覺而言，雖然目前還沒有一套產業內公認的足夠可靠的定位方案，但是在這方面探索從未停止過，主要原因如下:
安全性是無人駕駛系統最重要的指標，因此大部分功能的實現，都是多源數據、不同演算法結果的耦合。沒有哪種感測器方案是完美的，比如 GPS RTK 作為廣泛使用的方案，容易受衛星狀況、天氣狀況、 數據鏈傳輸狀況影響，在隧道內、室內和高樓密集區無法使用。再者，激光雷達雖然具有運算量小，提供深度信息，不受光照影響等優點，但信息稀疏，造價目前還十分昂貴，還不具備大批量車輛裝配能力。相比較而言，攝像頭提供的視覺信息，雖然會受到光照、天氣影響，但是成本低，內容豐富，是目前輔助駕駛方案主要數據源，在地圖定位方面也具有很大潛力。
由於主流基於視覺定位演算法的核心思想一脈相承，所以本文僅從一系列重要演算法框架組件角度，介紹了目前實踐中最常用的、基於特徵點的全局定位演算法，即在地圖坐標系下進行定位。本文省略了其中涉及到的優化、幾何約束公式推導，旨在給同學們一個定位演算法的宏觀介紹，具體細節可以參考相關文獻和書籍。
2. 基於特徵點的全局定位演算法視覺全局定位，指的是根據當前圖像，求出相機在地圖坐標系中的 6 個自由度 (Degree of freedom, DoF) 位姿 (Pose) , 即 (x, y, z) 坐標，以及環繞三個坐標軸的角度偏轉 (yaw, pitch, roll) 。目前主要可以分類為基於 3D 結構的方法、基於 2D 圖像的方法、基於序列圖像的方法、基於深度學習的方法。其中，基於深度學習的方法屬於端到端 (End-to-end) 的方法，而其它多階段 (Multi-stage) 非端到端方法雖然流程有所差別，但演算法思路大都如 Fig. 1 所示:
Figure 1: 根據查詢圖像，計算 2D-3D 轉換矩陣，求解相機位姿
基於已建的地圖，匹配歷史中最相似的地圖子集（圖像/點雲/特徵點），根據匹配到的地圖子集所提供的歷史位姿真值、特徵點坐標真值，計算點對間的變換矩陣，求解當前相機位姿。
所以，其核心包含圖像描述、建圖查詢、特徵匹配，位姿計算四個方面。這里僅僅是技術層面的宏觀分類，實際演算法框架不一定按照此順序執行，而學者在研究中主要針對這些技術進行改進。整體而言，基於特徵點的圖像描述基本成熟，發展較少。而位姿計算由於是基於幾何約束的優化問題，所以方法也較為固定。相對地，建圖查詢和特徵匹配中改進技術較多。根據數據源不同，建圖查詢、匹配可以是2D-2D，2D-3D，3D-3D。2D 圖像由相機得到，3D 點雲可以由提供深度的雙目相機、RGB-D 相機產生。
2.1 特徵點提取
2D 圖像本身是一個由亮度、色彩組成的矩陣，對視角、光照、色調變化等很敏感，直接使用十分困難。所以，一般會使用具有代表性的點進行相關計算。人們希望這樣的點具有旋轉、平移、尺度、光照不變性等優點。這些點稱為圖像的特徵 (Feature) 點，包含關鍵點(Key-points) 和描述子 (Descriptor) 兩部分。關鍵點表達了特徵點的位置，而描述子則是對於特徵點視覺特性的描述，大多為向量形式。一般而言，描述子主要是以某種模式，統計關鍵點周圍的灰度/色彩梯度變化。一種魯棒的描述子，在不同圖像 的不同情況下，同一特徵點的描述子的距離 (Distance) 應當較小。
描述子一般是人為手工設計的 (Hand-crafted features) 。經典的描述如 HOG(Histogram of oriented gradients)[1]，SIFT(Scale-invariant feature transform)[2]，SURF(Speeded up robust features)[3]，AKAZE(Accelerated KAZE)[4] 等。
為了實時性的要求，一些計算速度更快的二值模式描述子被設計出來，如 LBP(Local binary patterns)[5]，BRIEF(Binary robust independent elementary features)，ORB(Oriented FAST and rotated BRIEF)[6]，BRISK(Binary robust invariant scalable key-point)[7]，FREAK(Fast retina key-point)[8] 等。
在深度學習流行之前，這些手工特徵一直引領著整個計算視覺產業，直到今天，這些特徵在那些缺少標注數據、約束較多的場景下，依然被廣泛應用。下面簡單介紹兩類常用的描述子。
2.1.1 SIFTSIFT 描述子可以算是 CV 界最具影響力的技術之一。從關鍵點檢測層面，主要使用高斯差分 (Difference of Gaussian, DoG) 方法檢測多尺度空間上的極值點，作為關鍵點。而 Babaud 等人 [9] 證明了高斯平滑是唯一的能用多尺度空間平滑濾波核，為相關方法提供了充足的理論支持。
那麼為什麼這樣的方法可以找到特徵關鍵點呢?
由於高斯核可以通過模糊的方式把圖像縮放到不同尺度空間，而梯度變化較小的平滑區域在不同尺度空間的值差距較小。相反，邊緣、點、角、紋理等區域則差距較大。這樣通過對相鄰尺度的圖像做差分，最終可以算得多尺度空間的極值點。但是，不同的圖像細節本身就處於不同的尺度中。比如一副人物畫像中，人臉可能經過較小的模糊就會被平滑為一片，而畫框的角則可能需要更大尺度的平滑才會體現出局部「極值」。
因此，如 Fig. 2 所示，首先利用圖像金字塔將圖像先分組 (Octave) ，每組中再使用不同尺度的高斯核，形成一系列的層。這種方式比單純地使用更多尺度的高斯核效果更好，可以檢測到更多的特徵點。需要注意的是，雖然 SIFT 使用了 DoG 進行關鍵點檢測，但是其它檢測方法也是可行的，並不影響 SIFT 描述子的建立。
Figure 2: 高斯差分方法
SIFT 特徵點的描述子，可以理解為一種簡單統計版的 HOG。如 Fig. 3所示，以檢測到的關鍵點為中心，選取周圍 16 × 16 的區域，將區域再組織為 4 個 4 × 4 的塊(Patch)。對每一個塊，使用 8-bins 的直方圖對梯度進行統計，梯度方向決定落入哪個 bin，而梯度的模決定值的大小。為了保證尺度一致性，梯度大小需要進行歸一化。為了保證旋轉不變性，會根據 16 × 16 的區域內的所有梯度計算出一個主方向， 所有梯度按照主方向進行旋轉。最終形成 4 × 4 × 8 的 128 維向量。
Figure 3: 基於梯度分塊統計的 SIFT 描述子
2.1.2 二值描述子雖然在 SIFT 提出後，又產生了一些改進演算法如 SURF、AKAZE 等，但是即使放在 2019 年的今天， 依然難以保證一些場景對演算法實時性的要求。例如，手持設備一般算力有限。而無人駕駛中，CPU、GPU資源需要被多個計算密集型模塊同時調度。因此，效率是考察演算法實用性的重要指標。
為了提高效率，一些二值描述子被學者們提出。一般地，這些方法都是在特徵關鍵點周圍進行點采 樣。然後比較一對點的灰度大小，結果以 0/1 表示，形成 N 維的二進制描述向量，構成特徵點的二值模式。而不同二值描述子最大的差別，主要在於特徵采樣模式不同、點對選取方法不同。
Figure 4: LBP 描述子采樣模式
如 Fig. 4所示，LBP 描述子採用對關鍵點周圍，進行環形采樣，並與中心關鍵點的灰度進行比較的方案。圓環上展示了灰度比較結果，黑色的點是 0，白色的點是 1。LBP 是二值描述子最簡單的形式，而 ORB 改進了 BRIEF 特徵，是目前比較常用的二值描述子。如 Fig. 5所示，在點對選取上，與單純使用中心點不同，ORB 採用了隨機的方式，更全面地描述局部細節。但點對的相關性會比較大，從而降低描述子的判別性(Discriminative)。ORB 直接採用了貪婪法、窮舉法解決這一問題，尋找相關性低的隨機點對。
Figure 5: ORB 描述子點對選取模式
以上二值描述子的采樣方式和點對選取方式符合人們一般直覺，而 BRISK、FREAK 等描述子則提供了更加規則化、自帶尺度信息的二值模式構建方法。例如，FREAK 描述子模仿了人眼的視覺采樣模式。如 Fig. 6所示，每個采樣點的值是紅色圓圈范圍內的灰度均值，藍線則表示點對選取方案。
Figure 6: FREAK 描述子采樣、點對選取摸式
二值描述子的高效率，主要體現在三個方面。
(1)二值描述子使用二進制向量作為特徵描述，只需要 比較點對大小而不需要計算具體梯度。(2)兩個描述子之間比較可以使用計算更快，更容易優化的漢明距離 (Hamming distance)。(3)由於每個二進制向量都對應一個十進制數，所以其本身也代了表一種模 式，而不需要像 SIFT 一樣使用直方圖進行表示。
二值描述子一般判別性不如 SIFT 家族描述子，但在特定場景下，配合並行化編程，可以在保證相似判別能力的同時，效率高出幾十甚至百倍。
2.2 資料庫建立與查詢資料庫可以理解為於地圖 + 索引的集成。地圖可以是由單純的 2D 圖像組成，也可以是由 3D 點雲地圖組成，也可以是 2D 圖像和 3D 點雲的結合。3D 點雲地圖生成主要使用三維重建的方法 SfM(Structure from motion)，從時間序列的 2D 圖像中推算 3D 信息。如果有雙目、RGB-D 相機提供深度，可以獲得 更准確的 3D 點信息。其中也包含了一些諸如關鍵幀(Key-frame)的選取策略，具體方法超出了本文的討論范圍，有興趣的同學可以自行查閱相關資料。資料庫的作用在於:
對於一張輸入的觀測圖像，通過資料庫，查詢建圖歷史（圖像/點雲/特徵點），得到當前圖像最可能觀測到的地圖子集（圖像/點雲/特徵點），將地圖與觀測信息進行匹配，計算變換矩陣，得到觀測相機的位姿。
索引則是加速這一過程的關鍵。資料庫本身往往是巨大的。以美團的小袋機器人在北京朝陽大悅城二層試運營為例，安裝有 3 個深度相機，即使經過篩選，也使用了將近 8 萬張 900 × 600 的圖片。考慮到定位所需要的實時性，查詢時不可能每次都和 8 萬張圖片一一對比，所以要使用索引技術加速整個演算法。這方面技術與 SLAM 中的回環測試，視覺中的圖像檢索、位置識別等高度重合，以下僅介紹一般方法。
一張圖像內有若干特徵點，需要先對特徵點進行編碼，如 VLAD(Vector of locally aggregated descriptors) 編碼，用局部描述子形成圖像的全局描述。再使用索引，如 kd-tree，進行圖像級查詢。當然，編碼和索引也可以同時進行，如層次化詞袋模型(Bag-of-words，BoW)+ 正向索引 + 逆向索引的方法。
2.2.1 VLAD 編碼VLAD(Vector of locally aggregated descriptors)[10]，如 Fig. 7所示，是一種通過聚合局部描述子形成碼本 (Codebook) ，通過累加計算描述子與碼詞 (Word) 的距離，進行全局編碼的簡單方法。一個 d 維描述子 x 通過 k 個碼詞的碼本進行編碼，可以形成一個 d*k 維的描述向量，向量中的值是描述子與第
k個碼詞在第 d 維的差。之後進行 L2 歸一化，形成最後的 VLAD 向量。
Figure 7: VLAD 通過描述子與碼詞的距離進行編碼
這里要特別提介紹一下 DenseVLAD[11] 和 NetVLAD[12] 。Torii 等人證明，DenseSIFT 在查詢、匹配上都優於標准 SIFT。DenseVLAD 在四個尺度，以 2 個像素間隔的網格狀采樣模式，提取 SIFT 點。在全局隨機采樣 25M 個描述子，用 k-means 演算法生成 128 個碼詞的碼本。VLAD 向量在歸一化後使用 PCA(Principal component analysis) 降維，形成最後 4096 維的 DenseVLAD 向量。如 Fig. 8所示，使用DenseSIFT 匹配後的內點（綠）數量更多。
Figure 8: DenseSIFT 和標准 SIFT 特徵點，匹配後內點(綠)對比
而 NetVLAD，將 VLAD 中加入了監督信息，加強 VLAD 編碼的判別性。如 Fig. 9所示，假設紅、綠兩個描述子來源於不應匹配到一起的兩張圖片。由於它們都離 VLAD 中心(×)半徑較大且距離相似，經過 L2 歸一化，它們編碼後值也會很相似。而加入了紅、綠描述子所對應圖片不匹配的監督信息後，NetVLAD 生成的中心點(★)則可以更好地區分兩個描述子，增加他們編碼後的距離（半徑）差。
Figure 9: NetVLAD 聚類中心(×)與 VLAD 聚類中心(★)對比。
2.2.2 BoW 編碼 + 索引基於詞袋模型 BoW[13, 14] 的特徵編碼及其設計思想在計算機視覺發展中具有舉足輕重的地位，這里不再展開介紹。本文以 2D 查詢圖像匹配 2D 圖像資料庫為例，介紹一種常見的 BoW 編碼、索引一體化的模型。如 Fig. 10所示，詞典 (Vocabulary) 生成採用層次化方法，對於數據集中的所有描述子，按樹狀結構進行空間劃分，每一層都是由 k-means 聚類計算。最終葉子節點就相當於碼詞(Fig. 10中有 9個碼詞)。
Figure 10: 帶正向索引、逆向索引的層次化 BoW 模型
樹的構造過程，實際上就是將原始圖像編碼的過程。但是編碼本身並不能加快搜索過程，與 VLAD 相似，還是需要與資料庫中的圖像逐一比較。因此，這里設計了一種逆向索引(Inverse index) ，不需要比較編碼後的向量。其原理如 Fig. 11所示，對於一張查詢圖像 (Query image) ，將提取的描述子輸入到 BoW 中，最終會落入碼詞葉子結點 (Visual word) k 中。而每個碼詞對應一個索引，記錄碼詞 k
對於資料庫中第 i
張圖的權重
(Fig.10)。這里權重使用 TF-IDF(Term frequency–inverse document frequency) 計算。即如果一個詞 k
在某個圖像 i
中出現頻率高，在其它圖像出現頻率低，則這個詞對於圖像判別性較好，權重值
較高。最終通過投票 (Voting) 機制，選出匹配圖像。同樣需要注意的是，逆向索引不一定建立在樹形結構的 BoW 上，它僅僅是提供一種快速查詢的方法。
Figure 11: 通過逆向索引 + 投票機制，直接查詢圖像
而正向索引 (Direct Index) 的作用主要是記錄構造 BoW 時，資料庫圖片的特徵點都落入了哪些結點中，這樣當查詢到圖像後，不需要計算特徵點，可以直接通過索引提取特徵點。
2.2.3 3D 點雲查詢2D 圖像查詢中，是先從語意層面查詢圖像，因此可以通過圖像對特徵點的空間范圍進行約束。3D 點雲查詢沒有這樣的約束，所以具諸多難點。如需要考慮空間連續性，查詢到的點是否都在可觀測范圍內等。這里僅介紹 Sattler 在 TPAMI 2016 上發表的方法 [15]，經過多年的打磨，這套方法框架相對簡潔、完善。由於其中的詞典編碼搜索步驟與上節內容有所重疊，這里僅介紹 Active Search 和 Visbility Filtering 兩種機制。
Active Search 主要是為了使得匹配到的 3D 點盡可能空間中臨近、有幾何意義。如 Fig. 12所示，紅 色的點通過一系列編碼、精化過程(紅線)，匹配到了點雲中一個點。根據所提出優先排序(Prioritization) 框架，從點雲中找到一個概率最大的 3D 點，並反向(藍線)匹配查詢圖像中的一個對應的 2D 點。
Figure 12: Active Search
Figure 13: Visbility Filtering
Visbility Filtering 主要是為了讓匹配到的點盡可能可以被相機觀測到（定位是無監督的，並不能知道所匹配到的點是否正確）。這里採用的方法是在使用 SfM 建立 3D 點雲地圖時，同時建立一個雙向可見圖 (Bipartite visibility graph) 。如 Fig. 13（左）所示，當一個點可以同時被兩個相機觀測時，則建立拓撲關系。Fig. 13（中）里，藍色的點為匹配到的點，它們從觀測視角上存在沖突。通過在已有拓撲上進 行圖聚類，將相機兩兩分組，如 Fig. 13（右）。這樣就可以生成新的圖拓撲關系。之後通過判斷每個子圖(Sub-graph)間的重合情況，過濾掉那些那大概率不可見的點。
需要說明的是，雖然雙目相機和 RGB-D 相機可以獲取深度，查詢 2D 圖像也可以獲得限定范圍內的 3D 特徵點坐標，但是由於目前技術限制，在室內材質復雜，室外大尺度場景下，深度並不可靠。所以 2D圖像點和 3D 點雲地圖的匹配依然是一種重要的方法。
2.3 特徵點匹配特徵點匹配過程可以是在資料庫查詢中自適應完成的，這多見於基於 3D 結構的查詢。匹配也可以是在查詢後單獨進行，多見於基於 2D 圖像查詢。特徵匹配的目的是，為後續的變換矩陣計算提供匹配的點對集，實現位姿的解算。
2.3.1 經典 RANSAC隨機抽樣一致演算法 (Random sample consensus，RANSAC)[16] 是一種經典的數據過濾、參數擬合演算法。它假設數據（內點，Inliers）分布符合一定的數學模型，通過迭代計算，去除外點 (Outliers) 、雜訊點， 同時獲取概率上最佳的模型參數。在全局定位中，內點指正確的匹配，外點指錯誤的匹配，參數模型指匹配點對的空間變換矩陣。如 Fig. 14所示，經過 RANSAC 演算法優化後，匹配更加合理。RANSAC 所期望找到的匹配子集需要滿足兩個指標：內點重投影誤差盡可能小；內點數量盡可能多。所以基本流程如下：
· ①采樣初始子集。
· ②計算變換矩陣。
· ③ 根據變換矩陣計算匹配點的重投影誤差。
· ④ 去除誤差較大的點
· ⑤ 循環①-④，保留最滿足指標的匹配方案。
Figure 14: （上）原始特徵匹配；（下）經過 RANSAC 演算法優化後的匹配
其中，初始候選匹配是根據描述子之間的距離產生的，但重投影誤差則只和關鍵點的空間位置有關， 與描述子本身無關。具體投影矩陣方法請參考「2.4 位姿計算」。需要指出的是，RANSAC 演算法受到原始匹 配誤差和參數選擇的影響，只能保證演算法有足夠高的概率合理，不一定得到最優的結果。演算法參數主要包括閾值和迭代次數。RANSAC 得到可信模型的概率與迭代次數成正比，所得到的匹配數量和閾值成反比。因此實際使用時，可能需要反復嘗試不同的參數設置才能得到較優的結果。
學者們對經典 RANSAC 演算法進行了很多改進，如 Fig. 15所示，提出了全局 RANSAC(Universal- RANSAC)[17] 的結構圖，形成了具有普適性的 RANSAC 架構，涵蓋了幾乎所有的 RANSAC 的改進方 面，如預濾波、最小子集采樣、由最小子集生成可靠模型、參數校驗、模型精化。
Figure 15: Universal-RANSAC 通用演算法框架
2.3.3 可微分 RANSAC由於手工描述子在定位領域依然表現出較高的性能，所以一些學者開始探索使用深度學習代替演算法框架中的某些部分，而不是直接使用端到端的位姿估計模型完全代替傳統方法。可微分 RANSAC(Differentiable RANSAC，DSAC)[18] 旨在用概率假說選擇代替確定性假說選擇，使得 RANSAC 過程可以被求導，流程如 Fig. 16所示，其中「Scoring」步驟依然採用重投影誤差作為指標，所不同的是，誤差是基於整張圖像而不是特徵點，而原先篩選特徵點匹配的過程被換為了直接以概率篩選相機位姿假設 h 的過程。雖然目 前方法局限性比較大，但 DSAC 為如何在當前無監督為主的定位演算法框架中加入先驗知識，提供了一種可行的思路。
Figure 16: 差分 RANSAC 演算法框架
P3P 法可以看作是 PnP 法的特殊解法，如 Fig. 17所示，利用三角形相似性質增加更多約束，只需要 3 對點就可以求解。其它解法還有直接線性變換法 (Direct linear transformation，DLT)，EPnP(Efficient PnP) 法，和 UPnP(Uncalibrated PnP)等。相對於以上線性優化方法，非線性優化方法如Bundle Adjustment(BA) 也有著廣泛的應用。BA 方法在視覺 SLAM 中是一種「萬金油」的存在，可以同時優化多個變數，這樣可以一定程度緩解局部誤差帶來的系統不魯棒，感興趣的同學可以翻閱相關資料更深入地進行了解。
Figure 17: 2D-3D 變換矩陣計算中的 P3P 方法
3. 總結與展望
本文從圖像描述、建圖查詢、特徵匹配，位姿計算四個方面介紹了基於特徵點的位姿估計演算法。雖然傳統視覺全局定位方法目前依然是實際應用中的首選，但是，傳統方法是建立在特徵點被正確定義、正確提取、正確匹配、正確觀測的前提下進行的，這一前提對於視覺本身而言就是巨大的挑戰。其次，由於傳統方法是 multi-stage 框架，而非 end-to-end，所以中間每個環節，環節之間的交互，都需要眾多參數調整，每個環節的技術都可以作為一個單獨的研究方向。實際應用時，也需要加入對應具體場景的大量tricks，工程上比較復雜。
而人們對 end-to-end 方法的期望催生出了如 PoseNet，VLocNet，HourglassNet 等網路，在 benchmark上取得了不錯的成績。筆者認為目前 end-to-end 的方法還存在很多問題，主要有 loss function 缺少幾何 約束，建圖時位姿的 6 自由度空間並不連續，與輸入空間難以形成良好映射，而且缺少相應的位姿回歸、 精化機制等。不能否認，作為非線性空間最有力的建模工具，深度學習在未來會更多地出現在定位領域中。
回歸到視覺定位本身，由於視覺最重要的優勢就是成本低、語意豐富、使用場景限制少。因此，以視覺為主，其它低成本感測器為輔的定位融合方案在未來也將會是一個重要的課題。
參考資料
[1] Dalal, N., and B. Triggs. 」Histograms of oriented gradients for human detection.」 CVPR, 2005.
[2] Lowe, David G. 」Distinctive Image Features from Scale-Invariant Keypoints.」 IJCV, 2004.
[3] Bay, Herbert, T. Tuytelaars, and L. V. Gool. 」SURF: Speeded Up Robust Features.」 ECCV, 2006.[4] P.F.Alcantarilla,J.Nuevo,andA.Bartoli.Fast explicit diffusion for accelerated features in nonlinear scale spaces. BMVC, 2013.
[5] Ojala, Timo. 」Gray Scale and Rotation Invariant Texture Classification with Local Binary Patterns.」 ECCV, 2000.
[6] Rublee, Ethan , et al. 」ORB: An efficient alternative to SIFT or SURF.」 ICCV, 2011.
[7] Leutenegger, Stefan , M. Chli , and R. Y. Siegwart . 」BRISK: Binary Robust invariant scalable keypoints.」 ICCV, 2011
[8] Alahi, Alexandre , R. Ortiz , and P. Vandergheynst . 」FREAK: Fast retina keypoint.」 CVPR, 2012.
[9] Witkin, A P, M. Baudin, and R. O. Duda. 」Uniqueness of the Gaussian Kernel for Scale-Space Filtering.」 TPAMI, 1986.
[10] Jegou, Herve , et al. 」Aggregating local descriptors into a compact image representation.」 CVPR, 2010.
[11] Torii, Akihiko , et al. 」24/7 place recognition by view synthesis.」 CVPR, 2015.
[12] Arandjelovic, Relja, et al. 」NetVLAD: CNN architecture for weakly supervised place recognition.」 TPAMI, 2017.
[13] Li, Fei Fei . 」A Bayesian Hierarchical Model for Learning Natural Scene Categories. CVPR, 2005.
[14] Galvez-Lopez, D. , and J. D. Tardos . 」Bags of Binary Words for Fast Place Recognition in Image Sequences.」 TRO, 2012.
[15] Sattler, Torsten , B. Leibe , and L. Kobbelt . 」Efficient & Effective Prioritized Matching for Large- Scale Image-Based Localization.」 TPAMI, 2016.
[16] Fischler, Martin A., and R. C. Bolles. 」Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography.」 Communications of the ACM, 1981.
[17] Raguram, Rahul , et al. 」USAC: A Universal Framework for Random Sample Consensus.」 TPAMI, 2013.
[18] Brachmann, Eric, et al. 」DSAC —Differentiable RANSAC for Camera Localization.」 CVPR, 2017.
『貳』 求助，RANSAC圖像匹配去除誤點代碼報錯問題
基本矩陣F對所有對應點x，x'都滿足x『(T)Fx=0 對應點可以先根據sift等運算元檢測出興趣點，根據其灰度鄰域的相似假設對應，再用RANSAC方法進行魯棒估計，再進行非線性估計，最後引導匹配，進一步確定興趣點的對應。不可能一下准確的找出來的。即使最後也不是完全准確的。
『叄』 計算機專業學演算法的都學些什麼演算法，有什麼書可以看的學的話需要些什麼基礎的
計算機演算法非常多的
A*搜尋演算法
俗稱A星演算法。這是一種在圖形平面上，有多個節點的路徑，求出最低通過成本的演算法。常用於游戲中的NPC的移動計算，或線上游戲的BOT的移動計算上。該演算法像Dijkstra演算法一樣，可以找到一條最短路徑；也像BFS一樣，進行啟發式的搜索。
Beam Search
束搜索(beam search)方法是解決優化問題的一種啟發式方法，它是在分枝定界方法基礎上發展起來的，它使用啟發式方法估計k個最好的路徑，僅從這k個路徑出發向下搜索，即每一層只有滿意的結點會被保留，其它的結點則被永久拋棄，從而比分枝定界法能大大節省運行時間。束搜索於20 世紀70年代中期首先被應用於人工智慧領域,1976 年Lowerre在其稱為HARPY的語音識別系統中第一次使用了束搜索方法。他的目標是並行地搜索幾個潛在的最優決策路徑以減少回溯，並快速地獲得一個解。
二分取中查找演算法
一種在有序數組中查找某一特定元素的搜索演算法。搜索過程從數組的中間元素開始，如果中間元素正好是要查找的元素，則搜索過程結束；如果某一特定元素大於或者小於中間元素，則在數組大於或小於中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較。這種搜索演算法每一次比較都使搜索范圍縮小一半。
Branch and bound
分支定界(branch and bound)演算法是一種在問題的解空間樹上搜索問題的解的方法。但與回溯演算法不同，分支定界演算法採用廣度優先或最小耗費優先的方法搜索解空間樹，並且，在分支定界演算法中，每一個活結點只有一次機會成為擴展結點。
數據壓縮
數據壓縮是通過減少計算機中所存儲數據或者通信傳播中數據的冗餘度，達到增大數據密度，最終使數據的存儲空間減少的技術。數據壓縮在文件存儲和分布式系統領域有著十分廣泛的應用。數據壓縮也代表著尺寸媒介容量的增大和網路帶寬的擴展。
Diffie–Hellman密鑰協商
Diffie–Hellman key exchange，簡稱「D–H」，是一種安全協議。它可以讓雙方在完全沒有對方任何預先信息的條件下通過不安全信道建立起一個密鑰。這個密鑰可以在後續的通訊中作為對稱密鑰來加密通訊內容。
Dijkstra』s 演算法
迪科斯徹演算法（Dijkstra）是由荷蘭計算機科學家艾茲格·迪科斯徹（Edsger Wybe Dijkstra）發明的。演算法解決的是有向圖中單個源點到其他頂點的最短路徑問題。舉例來說，如果圖中的頂點表示城市，而邊上的權重表示著城市間開車行經的距離，迪科斯徹演算法可以用來找到兩個城市之間的最短路徑。
動態規劃
動態規劃是一種在數學和計算機科學中使用的，用於求解包含重疊子問題的最優化問題的方法。其基本思想是，將原問題分解為相似的子問題，在求解的過程中通過子問題的解求出原問題的解。動態規劃的思想是多種演算法的基礎，被廣泛應用於計算機科學和工程領域。比較著名的應用實例有：求解最短路徑問題，背包問題，項目管理，網路流優化等。這里也有一篇文章說得比較詳細。
歐幾里得演算法
在數學中，輾轉相除法，又稱歐幾里得演算法，是求最大公約數的演算法。輾轉相除法首次出現於歐幾里得的《幾何原本》（第VII卷，命題i和ii）中，而在中國則可以追溯至東漢出現的《九章算術》。
最大期望（EM）演算法
在統計計算中，最大期望（EM）演算法是在概率（probabilistic）模型中尋找參數最大似然估計的演算法，其中概率模型依賴於無法觀測的隱藏變數（Latent Variable）。最大期望經常用在機器學習和計算機視覺的數據聚類（Data Clustering）領域。最大期望演算法經過兩個步驟交替進行計算，第一步是計算期望（E），利用對隱藏變數的現有估計值，計算其最大似然估計值；第二步是最大化（M），最大化在 E 步上求得的最大似然值來計算參數的值。M 步上找到的參數估計值被用於下一個 E 步計算中，這個過程不斷交替進行。
快速傅里葉變換(FFT)
快速傅里葉變換（Fast Fourier Transform，FFT），是離散傅里葉變換的快速演算法，也可用於計算離散傅里葉變換的逆變換。快速傅里葉變換有廣泛的應用，如數字信號處理、計算大整數乘法、求解偏微分方程等等。
哈希函數
HashFunction是一種從任何一種數據中創建小的數字「指紋」的方法。該函數將數據打亂混合，重新創建一個叫做散列值的指紋。散列值通常用來代表一個短的隨機字母和數字組成的字元串。好的散列函數在輸入域中很少出現散列沖突。在散列表和數據處理中，不抑制沖突來區別數據，會使得資料庫記錄更難找到。
堆排序
Heapsort是指利用堆積樹（堆）這種數據結構所設計的一種排序演算法。堆積樹是一個近似完全二叉樹的結構，並同時滿足堆積屬性：即子結點的鍵值或索引總是小於（或者大於）它的父結點。
歸並排序
Merge sort是建立在歸並操作上的一種有效的排序演算法。該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用。
RANSAC 演算法
RANSAC 是」RANdom SAmpleConsensus」的縮寫。該演算法是用於從一組觀測數據中估計數學模型參數的迭代方法，由Fischler and Bolles在1981提出，它是一種非確定性演算法，因為它只能以一定的概率得到合理的結果，隨著迭代次數的增加，這種概率是增加的。該演算法的基本假設是觀測數據集中存在」inliers」（那些對模型參數估計起到支持作用的點）和」outliers」（不符合模型的點），並且這組觀測數據受到雜訊影響。RANSAC 假設給定一組」inliers」數據就能夠得到最優的符合這組點的模型。
RSA加密演演算法
這是一個公鑰加密演算法，也是世界上第一個適合用來做簽名的演算法。今天的RSA已經專利失效，其被廣泛地用於電子商務加密，大家都相信，只要密鑰足夠長，這個演算法就會是安全的。
並查集Union-find
並查集是一種樹型的數據結構，用於處理一些不相交集合（Disjoint Sets）的合並及查詢問題。常常在使用中以森林來表示。
Viterbi algorithm
尋找最可能的隱藏狀態序列(Finding most probable sequence of hidden states)。
『肆』 是的 計算機演算法
計算機演算法是以一步接一步的方式來詳細描述計算機如何將輸入轉化為所要求的輸出的過程，或者說，演算法是對計算機上執行的計算過程的具體描述。
編輯本段演算法性質一個演算法必須具備以下性質： （1）演算法首先必須是正確的，即對於任意的一組輸入，包括合理的輸入與不合理的輸入，總能得到預期的輸出。如果一個演算法只是對合理的輸入才能得到預期的輸出，而在異常情況下卻無法預料輸出的結果，那麼它就不是正確的。 （2）演算法必須是由一系列具體步驟組成的，並且每一步都能夠被計算機所理解和執行，而不是抽象和模糊的概念。 （3）每個步驟都有確定的執行順序，即上一步在哪裡，下一步是什麼，都必須明確，無二義性。 （4）無論演算法有多麼復雜，都必須在有限步之後結束並終止運行，即演算法的步驟必須是有限的。在任何情況下，演算法都不能陷入無限循環中。 一個問題的解決方案可以有多種表達方式，但只有滿足以上4個條件的解才能稱之為演算法。編輯本段重要演算法A*搜尋演算法
俗稱A星演算法。這是一種在圖形平面上，有多個節點的路徑，求出最低通過成本的演算法。常用於游戲中的NPC的移動計算，或線上游戲的BOT的移動計算上。該演算法像Dijkstra演算法一樣，可以找到一條最短路徑；也像BFS一樣，進行啟發式的搜索。
Beam Search
束搜索(beam search)方法是解決優化問題的一種啟發式方法，它是在分枝定界方法基礎上發展起來的，它使用啟發式方法估計k個最好的路徑，僅從這k個路徑出發向下搜索，即每一層只有滿意的結點會被保留，其它的結點則被永久拋棄，從而比分枝定界法能大大節省運行時間。束搜索於20 世紀70年代中期首先被應用於人工智慧領域,1976 年Lowerre在其稱為HARPY的語音識別系統中第一次使用了束搜索方法，他的目標是並行地搜索幾個潛在的最優決策路徑以減少回溯，並快速地獲得一個解。
二分取中查找演算法
一種在有序數組中查找某一特定元素的搜索演算法。搜素過程從數組的中間元素開始，如果中間元素正好是要查找的元素，則搜素過程結束；如果某一特定元素大於或者小於中間元素，則在數組大於或小於中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較。這種搜索演算法每一次比較都使搜索范圍縮小一半。
Branch and bound
分支定界(branch and bound)演算法是一種在問題的解空間樹上搜索問題的解的方法。但與回溯演算法不同，分支定界演算法採用廣度優先或最小耗費優先的方法搜索解空間樹，並且，在分支定界演算法中，每一個活結點只有一次機會成為擴展結點。
數據壓縮
數據壓縮是通過減少計算機中所存儲數據或者通信傳播中數據的冗餘度，達到增大數據密度，最終使數據的存儲空間減少的技術。數據壓縮在文件存儲和分布式系統領域有著十分廣泛的應用。數據壓縮也代表著尺寸媒介容量的增大和網路帶寬的擴展。
Diffie–Hellman密鑰協商
Diffie–Hellman key exchange，簡稱「D–H」，是一種安全協議。它可以讓雙方在完全沒有對方任何預先信息的條件下通過不安全信道建立起一個密鑰。這個密鑰可以在後續的通訊中作為對稱密鑰來加密通訊內容。
Dijkstra』s 演算法
迪科斯徹演算法（Dijkstra）是由荷蘭計算機科學家艾茲格·迪科斯徹（Edsger Wybe Dijkstra）發明的。演算法解決的是有向圖中單個源點到其他頂點的最短路徑問題。舉例來說，如果圖中的頂點表示城市，而邊上的權重表示著城市間開車行經的距離，迪科斯徹演算法可以用來找到兩個城市之間的最短路徑。
動態規劃
動態規劃是一種在數學和計算機科學中使用的，用於求解包含重疊子問題的最優化問題的方法。其基本思想是，將原問題分解為相似的子問題，在求解的過程中通過子問題的解求出原問題的解。動態規劃的思想是多種演算法的基礎，被廣泛應用於計算機科學和工程領域。比較著名的應用實例有：求解最短路徑問題，背包問題，項目管理，網路流優化等。這里也有一篇文章說得比較詳細。
歐幾里得演算法
在數學中，輾轉相除法，又稱歐幾里得演算法，是求最大公約數的演算法。輾轉相除法首次出現於歐幾里得的《幾何原本》（第VII卷，命題i和ii）中，而在中國則可以追溯至東漢出現的《九章算術》。
最大期望（EM）演算法
在統計計算中，最大期望（EM）演算法是在概率（probabilistic）模型中尋找參數最大似然估計的演算法，其中概率模型依賴於無法觀測的隱藏變數（Latent Variable）。最大期望經常用在機器學習和計算機視覺的數據聚類（Data Clustering）領域。最大期望演算法經過兩個步驟交替進行計算，第一步是計算期望（E），利用對隱藏變數的現有估計值，計算其最大似然估計值；第二步是最大化（M），最大化在 E 步上求得的最大似然值來計算參數的值。M 步上找到的參數估計值被用於下一個 E 步計算中，這個過程不斷交替進行。
快速傅里葉變換(FFT)
快速傅里葉變換（Fast Fourier Transform，FFT），是離散傅里葉變換的快速演算法，也可用於計算離散傅里葉變換的逆變換。快速傅里葉變換有廣泛的應用，如數字信號處理、計算大整數乘法、求解偏微分方程等等。
哈希函數
HashFunction是一種從任何一種數據中創建小的數字「指紋」的方法。該函數將數據打亂混合，重新創建一個叫做散列值的指紋。散列值通常用來代表一個短的隨機字母和數字組成的字元串。好的散列函數在輸入域中很少出現散列沖突。在散列表和數據處理中，不抑制沖突來區別數據，會使得資料庫記錄更難找到。
堆排序
Heapsort是指利用堆積樹（堆）這種數據結構所設計的一種排序演算法。堆積樹是一個近似完全二叉樹的結構，並同時滿足堆積屬性：即子結點的鍵值或索引總是小於（或者大於）它的父結點。
歸並排序
Merge sort是建立在歸並操作上的一種有效的排序演算法。該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用。
RANSAC 演算法
RANSAC 是」RANdom SAmpleConsensus」的縮寫。該演算法是用於從一組觀測數據中估計數學模型參數的迭代方法，由Fischler and Bolles在1981提出，它是一種非確定性演算法，因為它只能以一定的概率得到合理的結果，隨著迭代次數的增加，這種概率是增加的。該演算法的基本假設是觀測數據集中存在」inliers」（那些對模型參數估計起到支持作用的點）和」outliers」（不符合模型的點），並且這組觀測數據受到雜訊影響。RANSAC 假設給定一組」inliers」數據就能夠得到最優的符合這組點的模型。
RSA加密演演算法
這是一個公鑰加密演算法，也是世界上第一個適合用來做簽名的演算法。今天的RSA已經專利失效，其被廣泛地用於電子商務加密，大家都相信，只要密鑰足夠長，這個演算法就會是安全的。
並查集Union-find
並查集是一種樹型的數據結構，用於處理一些不相交集合（Disjoint Sets）的合並及查詢問題。常常在使用中以森林來表示。
Viterbi algorithm
尋找最可能的隱藏狀態序列(Finding most probable sequence of hidden states)。編輯本段演算法特點1.有窮性。一個演算法應包含有限的操作步驟，而不能是無限的。事實上「有窮性」往往指「在合理的范圍之內」。如果讓計算機執行一個歷時1000年才結束的演算法，這雖然是有窮的，但超過了合理的限度，人們不把他是為有效演算法。 2. 確定性。演算法中的每一個步驟都應當是確定的，而不應當是含糊的、模稜兩可的。演算法中的每一個步驟應當不致被解釋成不同的含義，而應是十分明確的。也就是說，演算法的含義應當是唯一的，而不應當產生「歧義性」。 3. 有零個或多個輸入、所謂輸入是指在執行演算法是需要從外界取得必要的信息。 4. 有一個或多個輸出。演算法的目的是為了求解，沒有輸出的演算法是沒有意義的。 5.有效性。 演算法中的每一個 步驟都應當能有效的執行。並得到確定的結果。編輯本段演算法與程序雖然演算法與計算機程序密切相關，但二者也存在區別：計算機程序是演算法的一個實例，是將演算法通過某種計算機語言表達出來的具體形式；同一個演算法可以用任何一種計算機語言來表達。 演算法列表 圖論 路徑問題 0/1邊權最短路徑 BFS 非負邊權最短路徑（Dijkstra） 可以用Dijkstra解決問題的特徵 負邊權最短路徑 Bellman-Ford Bellman-Ford的Yen-氏優化 差分約束系統 Floyd 廣義路徑問題 傳遞閉包 極小極大距離 / 極大極小距離 Euler Path / Tour 圈套圈演算法 混合圖的 Euler Path / Tour Hamilton Path / Tour 特殊圖的Hamilton Path / Tour 構造 生成樹問題 最小生成樹 第k小生成樹 最優比率生成樹 0/1分數規劃 度限制生成樹 連通性問題 強大的DFS演算法 無向圖連通性 割點 割邊 二連通分支 有向圖連通性 強連通分支 2-SAT 最小點基 有向無環圖 拓撲排序 有向無環圖與動態規劃的關系 二分圖匹配問題 一般圖問題與二分圖問題的轉換思路 最大匹配 有向圖的最小路徑覆蓋 0 / 1矩陣的最小覆蓋 完備匹配 最優匹配 穩定婚姻 網路流問題 網路流模型的簡單特徵和與線性規劃的關系 最大流最小割定理 最大流問題 有上下界的最大流問題 循環流 最小費用最大流 / 最大費用最大流 弦圖的性質和判定 組合數學 解決組合數學問題時常用的思想 逼近 遞推 / 動態規劃 概率問題 Polya定理 計算幾何 / 解析幾何 計算幾何的核心：叉積 / 面積 解析幾何的主力：復數 基本形 點 直線，線段 多邊形 凸多邊形 / 凸包 凸包演算法的引進，卷包裹法 Graham掃描法 水平序的引進，共線凸包的補丁 完美凸包演算法 相關判定 兩直線相交 兩線段相交 點在任意多邊形內的判定 點在凸多邊形內的判定 經典問題 最小外接圓 近似O(n)的最小外接圓演算法 點集直徑 旋轉卡殼，對踵點 多邊形的三角剖分 數學 / 數論 最大公約數 Euclid演算法 擴展的Euclid演算法 同餘方程 / 二元一次不定方程 同餘方程組 線性方程組 高斯消元法 解mod 2域上的線性方程組 整系數方程組的精確解法 矩陣 行列式的計算 利用矩陣乘法快速計算遞推關系 分數 分數樹 連分數逼近 數論計算 求N的約數個數 求phi(N) 求約數和 快速數論變換 …… 素數問題 概率判素演算法 概率因子分解 數據結構 組織結構 二叉堆 左偏樹 二項樹 勝者樹 跳躍表 樣式圖標 斜堆 reap 統計結構 樹狀數組 虛二叉樹 線段樹 矩形面積並 圓形面積並 關系結構 Hash表 並查集 路徑壓縮思想的應用 STL中的數據結構 vector deque set / map 動態規劃 / 記憶化搜索 動態規劃和記憶化搜索在思考方式上的區別 最長子序列系列問題 最長不下降子序列 最長公共子序列 一類NP問題的動態規劃解法 樹型動態規劃 背包問題 動態規劃的優化 四邊形不等式 函數的凸凹性 狀態設計 規劃方向 線性規劃 常用思想 二分 最小表示法 串 KMP Trie結構 後綴樹/後綴數組 LCA/RMQ 有限狀態自動機理論 排序 選擇/冒泡 快速排序 堆排序 歸並排序 基數排序 拓撲排序 排序網路
擴展閱讀：
1
《計算機演算法設計與分析導論》朱清新等編著人民郵電出版社
開放分類：
計算機，演算法