❶ 全局視覺定位系統研究的意義
全局視覺定位
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
RANSAC 主要是用於處理 外點數 (outline) 比較多情況下來搜索一條直線或進行模型參數擬合。從 RANSAC 全名字面意思是隨機采樣一致性。是一種非常簡單且有效估計模型參數的方法。不僅限於直線模型的參數，在 SLAM 通過對比前後量幀圖像上特徵點間關系可以計算出攝像機的外參數，從而計算運動軌跡並生成稀疏點雲。
對於RANSAC演算法來說一個基本的假設就是數據是由 內點 和 外點 組成的。
同時 RANSAC 假設：在給定一組含有少部分 內點 的數據，存在一個程序可以估計出符合 內點 的模型。
通常會有如下幾個步驟
如圖
到此算完成一次迭代，重復上面的迭代記錄小每次迭代選擇點後繪制所得到的投票數，投票數最大所對應的直線模型就是我們要找到的直線
從上面求解過程，可以發現迭代次數 N 和內點率 t 或者理解為外點率 e 都可以這些參數確定是比較困難的，可以感覺經驗進行來設置這些參數，
通常我們還會設定一個閾值，這個閾值是關於投票數的閾值，也就是最少投票數值，計算出直線中投票數最大的直線的投票數量還需要大於這個最少投票數才可以。其實 RANSAC 輸出一個一條投票數最多且大於事先設定好閾值的直線模型參數，也可以是多條投票數大於最小投票(閾值)的多條直線。
通常我們對這些點的外點率是一無所知的，那麼在這種情況下應該如何處理呢?
首先將迭代次數 N 設置無窮大，因為現在對外點率一無所知，所以也就沒辦法設置 N。所以真實迭代次數 sample_count 通常都會比 N 小
接下來就是將 sample_count 增加 1 然後重復上面步驟，在下一次迭代中 N 就不再是無窮大而是用 N1 來 如果在下一次迭代中計算 d 內點數量要比上一次高就保留本次 d 以及計算得到 N1 而舍棄上一次的計算得到 N1 。
圖像配准就是找到一幅圖像像素到另一幅圖像像素間的空間映射關系。這些圖像可以是不同時間(多時間配准)，不同感測器在不同地方拍攝（多模式配准）。這些圖像之間的空間關系可以是剛性 (平移和旋轉)，仿射(例如剪切），單應性(或復雜的大變形模型）。
這是一個三維重建必用的演算法，如果在三維重建不用 RANSAC 就說明你做的還不算好。幫助我們排序一些噪音點還是outline 的點。我們以擬合直線為例講解 RANSAC 我們隨機地挑選兩個點作為模型，然後看有多少點 inline，我們在隨意找兩個點來作為模型，我們通過評估（投票形式）來找出最優模型，但是這本模型並不是最優模型而是我們要，隨意選擇最少 x 個樣本，x 個數取決於你要擬合模型，如果是直線就是 2 個點，平面需要3 點。然後計算有多少點和模型擬合。直到找到一個模型其中 inline 樣本點是最多的。然後在擬合一次就可以得到我們想要點。
❸ 基於特徵匹配和迭代優化的航拍圖像拼接
本文研究了無人機（UAV）遙感圖像拼接過程中重疊區域的不匹配問題。為了解決這個問題，首先通過將雙重匹配與隨機抽樣共識（RANSAC）方法相結合來過濾特徵點。其次，為了保證每幅圖像與全景照片的投影關系的一致性，我們提出了一種局部拼接的方法。為了避免隨著圖像數量的增加透視變化累積而導致圖像傾斜的錯誤，我們建立了圖像旋轉坐標系，並將圖像之間的關系限制為平移和旋轉。用坐標原點的相對位置來表示平移距離，通過迭代求解最優旋轉角度。最後，圖像的重疊部分通過線性加權融合。通過實驗結果驗證，本文提出的方法在大量圖像的情況下能夠保證更快的處理速度和更高的處理精度，從而達到理想的拼接效果。
近年來，隨著計算機視覺的不斷進步，圖像拼接技術在海洋和礦產勘探、遙感勘探、醫學成像、效果生成、虛擬現實等方面得到了廣泛的應用。許多航拍遙感圖像可以通過配備攝像頭的無人機在地面拍攝得到。通常，由於無人機飛行高度、相機焦距等因素，單幅圖像存在信息量少、全局解析度低等問題。因此，要獲得廣角高解析度的照片，就需要研究全景圖像拼接技術。Brown 在 2003 年引入了著名的 AutoSitich 演算法，很快就被用於商業產品，如 Photoshop。但是，該演算法假定圖像的重疊區域沒有深度變化。2013 年，薩拉戈薩 J 等人。將圖像拆分為密集的網格，並為每個網格使用單個更改，稱為網格變形。該方法在一定程度上解決了圖像變形、尺寸縮放、重定向等問題。
圖像拼接技術一般分為圖像幾何校正、圖像預處理、圖像對齊、圖像融合四個步驟。由於相機鏡頭的畸變，需要對無人機的圖像進行校正，使得到的圖像滿足個別地圖的投影關系。圖像預處理是幾乎所有圖像處理技術的重要組成部分，包括去噪、灰度變化等。這個過程可以降低匹配難度，提高匹配精度。然而，對於無人機遙感圖像的拼接，圖像匹配和圖像融合是成功的關鍵。
圖像匹配技術是圖像拼接的基礎。1975年米爾格拉姆提出了計算機拼接技術。於是，在重疊區域尋找最優接縫線就成為一個重要的研究方向。同年，Kuslin 提出了一種相位相關方法，通過傅里葉變化將圖像轉換到頻域，並利用功率譜計算平移。1987 年，Reddy 提出了一種擴展的相位相關方法，該方法可以計算圖像的平移和旋轉關系並解決圖像縮放問題。圖像拼接的另一個分支是基於圖像特徵。1988年Harris提出經典的Harris點檢測演算法，它使用特定的旋轉不變性哈里斯點進行特徵匹配。2004 年，Lowe 提出了一種完美的尺度不變特徵變換演算法（SIFT），對平移、旋轉、尺度縮放、不均勻光照等圖像領域應用最廣泛的技術具有良好的適應性。C Aguerrebere 根據輸入圖像的 SNR 條件給出的問題難度級別顯示不同的行為區域。Wu通過建立模型，將深度學習和進化演算法應用於遙感圖像的拼接，實現概率意義上的全局優化。
圖像融合技術是遙感圖像拼接技術中的另一項核心技術，分為像素級融合、特徵級融合、決策級融合。像素級融合仍然是現階段最常用的圖像融合方法之一。
對於無人機的遙感圖像，存在圖像數量多、光照條件多變等問題。每次拼接過程中的小錯誤都難以避免。隨著圖像數量的增加，誤差不斷累積，圖像拼接後期會出現圖像失真和重影。S Bang 創建高質量全景圖，過濾掉視頻的模糊幀，選擇關鍵幀，並校正相機鏡頭失真。Zhang 提出了基於 STIF 的 GA-SIFT 並給出了一種自適應閾值方法來解決計算量大和拼接時間長的問題。李明基於動態規劃解決無人機側視問題尋找最佳接縫線。然而，當圖像數量逐漸增加時，現有的拼接演算法存在誤差累積。
也有一些基於網格變形的圖像拼接演算法，但計算量太大。在本文中，圖像被匹配兩次以過濾特徵點以提高准確度。拼接問題對應於通過坐標系轉換的旋轉角度解，應用高斯-牛頓迭代計算最優旋轉角度。此外，我們練習局部匹配方法以減少錯誤並使用加權融合來實現過度平滑。
SIFT特徵點不僅在空間尺度和旋轉上保持不變，而且在光照和視角變化的條件下，還具有優異的抗干擾能力和良好的穩定性。為了實現空間尺度的不變性，SIFT特徵點可以根據物體遠看小而模糊，反之大而清晰的特點，建立高斯金字塔模型。差分金字塔 (DoG) 是通過計算金字塔中相鄰兩層圖像之間的差異來獲得的。使用函數擬合在 DOG 空間中測試極值。通過對確定場中基於SIFT特徵點的梯度信息進行統計，選擇加權幅度最大的梯度方向作為主梯度方向。通過將特徵點與其主梯度方向相關聯，可以解決圖像特徵點的旋轉不變性問題。最後，利用特徵點周圍像素的信息建立一個128維的向量作為特徵點的描述符。
提取特徵點後，需要對兩幅圖像的特徵點進行匹配。通過特徵點成對匹配，可以計算出兩個特徵點對應的描述符之間的歐氏距離，選擇歐氏距離最小的點作為匹配點對。為了減少不匹配的發生率， 被用作正確匹配的閾值。具有大於 的描述符歐幾里得距離的匹配點對被消除。
RANSAC 是特徵點匹配中最常用的方法之一。它首先從匹配結果中隨機選擇四對特徵點並計算單應矩陣。其次，根據上一步得到的單應矩陣，計算第一幅圖像在第二幅圖像中的重投影坐標，並計算該坐標與第二幅圖像中匹配點對坐標的距離。通過設置距離閾值記錄所有匹配點對中正確匹配特徵點對的個數。重復上面的過程，最終留下與最多點對數的正確匹配。
高斯-牛頓迭代是求解非線性最小二乘優化問題的演算法之一，可以描述為：
我們選擇一個初始值，然後不斷更新當前優化變數以減小目標函數值。高斯-牛頓迭代的主要思想是對函數 進行一階泰勒展開，計算 及其雅可比矩陣 對應的函數值。使用 和 計算 的增量，直到 足夠小。
加權平均法是圖像融合中簡單有效的方法之一。第一幅圖像和第二幅圖像重疊區域的像素值由兩幅圖像像素的加權求和得到，表示為：
其中：越接近 img1， 的值越大。 的值從1逐漸變為0，重疊區域從第一幅圖像逐漸過渡到第二幅圖像，從而實現畫面的平滑過渡。照片的加權平均融合因其直觀的簡單性和快速的運行速度而被廣泛使用和圖像拼接。
對於兩幅圖像的拼接，由於無人機的遙感相機通常安裝在一個穩定的平台上，通過選擇合適的坐標系，將圖像對齊問題轉化為單幅圖像旋轉問題，如圖1所示。
此外，大多數具有相關高光頻的常用相機通常在連續幀之間具有較大的重疊區域。因此，在圖像拼接過程中，第 幅圖像在全局位置上的投影關系，不僅受第 幅圖像的影響，還與 圖像相關。為了保證圖像變形的一致性，首先將 張圖像拼接在一起，然後將結果整合到整幅圖像中。大量的實驗測試證明，當i設置為3時效果最佳。整個過程如圖圖2。
圖像中的特徵點有很多種，本文使用最常見的SIFT特徵點。我們提取並匹配兩張輸入圖像的特徵點，結果如下所示。
特徵點的匹配精度直接影響旋轉角度的計算，因此使用前必須對特徵點對進行過濾。鑒於過濾特徵點的方法很多，本文先將左圖與右圖進行匹配，再將右圖與左圖進行匹配。兩次相同結果配對的匹配點將被保留。在此基礎上，使用RANSAC方法對結果進行優化，成功匹配了上圖中的121個特徵點。
從無人機拍攝的兩張照片之間通常存在旋轉和平移。為了獨立優化旋轉角度，我們首先建立如圖 5所示的坐標系。
以圖像匹配成功的特徵點坐標值的平均值作為該坐標的原點，坐標軸與像素坐標系的兩個坐標軸平行。根據公式（3），特徵點從圖像坐標系轉換為圖像旋轉坐標系：
其中 為濾波後的特徵對的總數， 為特徵點在原始圖像坐標系中的坐標值，並且 是新的值。
在計算圖像的旋轉角度之前，我們首先需要分析圖像的縮放比例。由飛行高度引起的尺寸變化將在軸上具有相同的縮放比例。因此，根據所有特徵點與圖像旋轉坐標系原點的歐氏距離比，可以計算出兩幅圖像之間的縮放比例，對圖像進行縮放和改變。
圖像縮放後，計算圖像旋轉的角度。高斯牛頓迭代的方式計算旋轉角度的最優解。首先設置目標函數：
通過迭代選擇最優的 使得：
使用誤差函數 的泰勒展開進行迭代。
其中
根據
我們可以發現增量值 每次迭代。最終，當我們計算出的 滿足條件時，停止迭代過程。可以使用最佳旋轉角度和旋轉中心來求解圖像的變換矩陣。
由於拍攝圖像時光線不均勻，連續兩張圖像之間可能存在一些顏色差異。此外，圖像旋轉不可避免地存在小誤差，因此我們練習線性加權融合以消除兩幅圖像之間的拼接線和色度變化。圖像的重疊是按距離加權的，這樣拼接結果自然是從img1到img2過度了。
我們利用OpenCV的功能從遙感圖像中提取SIFT特徵點並進行匹配。從Stitch拼接功能、基於透視變化的圖像拼接結果以及本文的拼接速度的對比可以看出，本文採用的方法具有一定的優越性。
從表1數據可以看出，在拼接少量圖像時，三種演算法的拼接結果相似，沒有出現明顯的拼接誤差。但是，Stitcher 演算法比其他兩種拼接方法花費的時間要多得多。
圖 11很明顯，隨著圖像數量的增加，基於透視變換的圖像拼接演算法出現了嚴重的失配。然而，本文採用的方法取得了比較滿意的結果，因為在無人機拍攝的圖像中，地面上的所有特徵都可以近似地視為在同一平面上。根據透視變換，無人機的遠近抖動會引入圖像拼接導致錯誤。圖像數量的不斷增加會導致錯誤的積累，從而導致嚴重的失配。另外，這使得程序中斷，從而無法完成所有60幅圖像的拼接。假設同一平面上圖片的仿射變化會更符合無人機遙感圖像的實際情況。最後，可以通過線性加權融合來解決誤差問題，以提高拼接效果。考慮到stitch演算法耗時過長，本文不會對兩者進行比較。
在上面的圖 12 中，使用 100 張圖像來測試本文中的方法。圖像的仿射變換是通過計算圍繞圖像特徵點中心的旋轉角度來進行的。變換後的圖像採用線性加權融合後，可以得到大量圖像數據處理後的結果。拼接自然，符合人類視覺體驗。
我們在網路上跑了一組數據，結果如下。
鑒於以上實驗結果，該方法具有一定的抗干擾能力，可以高速運行。與高度集成的Stitcher和基於透視變換的圖像拼接結果相比，我們可以發現，基於透視變化的圖像拼接結果隨著圖像數量的增加而逐漸變差。然而，盡管拼接效果很好，但 Stitcher 需要更長的處理時間。
在本文中，我們研究了無人機遙感圖像的拼接技術，主要貢獻可以總結如下：
通過實驗結果可以看出，本文提出的方法比現有方法具有更好的實時性，對於相機平面與成像平面平行的情況具有更好的拼接效果。
❹ 程序員必須掌握哪些演算法
A搜索演算法——圖形搜索演算法，從給定起點到給定終點計算出路徑。其中使用了一種啟發式的估算，為每個節點估算通過該節點的最佳路徑，並以之為各個地點排定次序。演算法以得到的次序訪問這些節點。因此，A*搜索演算法是最佳優先搜索的範例。
集束搜索（又名定向搜索，BeamSearch）——最佳優先搜索演算法的優化。使用啟發式函數評估它檢查的每個節點的能力。不過，集束搜索只能在每個深度中發現最前面的m個最符合條件的節點，m是固定數字——集束的寬度。
二分查找（BinarySearch）——在線性數組中找特定值的演算法，每個步驟去掉一半不符合要求的數據。
分支界定演算法（BranchandBound）——在多種最優化問題中尋找特定最優化解決方案的演算法，特別是針對離散、組合的最優化。
Buchberger演算法——一種數學演算法，可將其視為針對單變數最大公約數求解的歐幾里得演算法和線性系統中高斯消元法的泛化。
數據壓縮——採取特定編碼方案，使用更少的位元組數（或是其他信息承載單元）對信息編碼的過程，又叫來源編碼。
Diffie-Hellman密鑰交換演算法——一種加密協議，允許雙方在事先不了解對方的情況下，在不安全的通信信道中，共同建立共享密鑰。該密鑰以後可與一個對稱密碼一起，加密後續通訊。
Dijkstra演算法——針對沒有負值權重邊的有向圖，計算其中的單一起點最短演算法。
離散微分演算法（Discretedifferentiation）
動態規劃演算法（DynamicProgramming）——展示互相覆蓋的子問題和最優子架構演算法
歐幾里得演算法（Euclideanalgorithm）——計算兩個整數的最大公約數。最古老的演算法之一，出現在公元前300前歐幾里得的《幾何原本》。
期望-最大演算法（Expectation-maximizationalgorithm，又名EM-Training）——在統計計算中，期望-最大演算法在概率模型中尋找可能性最大的參數估算值，其中模型依賴於未發現的潛在變數。EM在兩個步驟中交替計算，第一步是計算期望，利用對隱藏變數的現有估計值，計算其最大可能估計值；第二步是最大化，最大化在第一步上求得的最大可能值來計算參數的值。
快速傅里葉變換（FastFouriertransform，FFT）——計算離散的傅里葉變換（DFT）及其反轉。該演算法應用范圍很廣，從數字信號處理到解決偏微分方程，到快速計算大整數乘積。
梯度下降（Gradientdescent）——一種數學上的最優化演算法。
哈希演算法（Hashing）
堆排序（Heaps）
Karatsuba乘法——需要完成上千位整數的乘法的系統中使用，比如計算機代數系統和大數程序庫，如果使用長乘法，速度太慢。該演算法發現於1962年。
LLL演算法（Lenstra-Lenstra-Lovaszlatticerection）——以格規約（lattice）基數為輸入，輸出短正交向量基數。LLL演算法在以下公共密鑰加密方法中有大量使用：背包加密系統（knapsack）、有特定設置的RSA加密等等。
最大流量演算法（Maximumflow）——該演算法試圖從一個流量網路中找到最大的流。它優勢被定義為找到這樣一個流的值。最大流問題可以看作更復雜的網路流問題的特定情況。最大流與網路中的界面有關，這就是最大流-最小截定理（Max-flowmin-cuttheorem）。Ford-Fulkerson能找到一個流網路中的最大流。
合並排序（MergeSort）
牛頓法（Newton'smethod）——求非線性方程（組）零點的一種重要的迭代法。
Q-learning學習演算法——這是一種通過學習動作值函數（action-valuefunction）完成的強化學習演算法，函數採取在給定狀態的給定動作，並計算出期望的效用價值，在此後遵循固定的策略。Q-leanring的優勢是，在不需要環境模型的情況下，可以對比可採納行動的期望效用。
兩次篩法（QuadraticSieve）——現代整數因子分解演算法，在實踐中，是目前已知第二快的此類演算法（僅次於數域篩法NumberFieldSieve）。對於110位以下的十位整數，它仍是最快的，而且都認為它比數域篩法更簡單。
RANSAC——是「RANdomSAmpleConsensus」的縮寫。該演算法根據一系列觀察得到的數據，數據中包含異常值，估算一個數學模型的參數值。其基本假設是：數據包含非異化值，也就是能夠通過某些模型參數解釋的值，異化值就是那些不符合模型的數據點。
RSA——公鑰加密演算法。首個適用於以簽名作為加密的演算法。RSA在電商行業中仍大規模使用，大家也相信它有足夠安全長度的公鑰。
Schönhage-Strassen演算法——在數學中，Schönhage-Strassen演算法是用來完成大整數的乘法的快速漸近演算法。其演算法復雜度為：O(Nlog(N)log(log(N)))，該演算法使用了傅里葉變換。
單純型演算法（SimplexAlgorithm）——在數學的優化理論中，單純型演算法是常用的技術，用來找到線性規劃問題的數值解。線性規劃問題包括在一組實變數上的一系列線性不等式組，以及一個等待最大化（或最小化）的固定線性函數。
奇異值分解（Singularvaluedecomposition，簡稱SVD）——在線性代數中，SVD是重要的實數或復數矩陣的分解方法，在信號處理和統計中有多種應用，比如計算矩陣的偽逆矩陣（以求解最小二乘法問題）、解決超定線性系統（overdeterminedlinearsystems）、矩陣逼近、數值天氣預報等等。
求解線性方程組（）——線性方程組是數學中最古老的問題，它們有很多應用，比如在數字信號處理、線性規劃中的估算和預測、數值分析中的非線性問題逼近等等。求解線性方程組，可以使用高斯—約當消去法（Gauss-Jordanelimination），或是柯列斯基分解（Choleskydecomposition）。
Strukturtensor演算法——應用於模式識別領域，為所有像素找出一種計算方法，看看該像素是否處於同質區域（homogenousregion），看看它是否屬於邊緣，還是是一個頂點。
合並查找演算法（Union-find）——給定一組元素，該演算法常常用來把這些元素分為多個分離的、彼此不重合的組。不相交集（disjoint-set）的數據結構可以跟蹤這樣的切分方法。合並查找演算法可以在此種數據結構上完成兩個有用的操作：
查找：判斷某特定元素屬於哪個組。
合並：聯合或合並兩個組為一個組。
維特比演算法（Viterbialgorithm）——尋找隱藏狀態最有可能序列的動態規劃演算法，這種序列被稱為維特比路徑，其結果是一系列可以觀察到的事件，特別是在隱藏的Markov模型中。
❺ 大數據最常用的演算法有哪些
奧地利符號計算研究所(Research Institute for Symbolic Computation，簡稱RISC)的Christoph Koutschan博士在自己的頁面上發布了一篇文章，提到他做了一個調查，參與者大多數是計算機科學家，他請這些科學家投票選出最重要的演算法，以下是這次調查的結果，按照英文名稱字母順序排序。
大數據等最核心的關鍵技術：32個演算法
1、A* 搜索演算法——圖形搜索演算法，從給定起點到給定終點計算出路徑。其中使用了一種啟發式的估算，為每個節點估算通過該節點的最佳路徑，並以之為各個地點排定次序。演算法以得到的次序訪問這些節點。因此，A*搜索演算法是最佳優先搜索的範例。
2、集束搜索(又名定向搜索，Beam Search)——最佳優先搜索演算法的優化。使用啟發式函數評估它檢查的每個節點的能力。不過，集束搜索只能在每個深度中發現最前面的m個最符合條件的節點，m是固定數字——集束的寬度。
3、二分查找(Binary Search)——在線性數組中找特定值的演算法，每個步驟去掉一半不符合要求的數據。
4、分支界定演算法(Branch and Bound)——在多種最優化問題中尋找特定最優化解決方案的演算法，特別是針對離散、組合的最優化。
5、Buchberger演算法——一種數學演算法，可將其視為針對單變數最大公約數求解的歐幾里得演算法和線性系統中高斯消元法的泛化。
6、數據壓縮——採取特定編碼方案，使用更少的位元組數(或是其他信息承載單元)對信息編碼的過程，又叫來源編碼。
7、Diffie-Hellman密鑰交換演算法——一種加密協議，允許雙方在事先不了解對方的情況下，在不安全的通信信道中，共同建立共享密鑰。該密鑰以後可與一個對稱密碼一起，加密後續通訊。
8、Dijkstra演算法——針對沒有負值權重邊的有向圖，計算其中的單一起點最短演算法。
9、離散微分演算法(Discrete differentiation)。
10、動態規劃演算法(Dynamic Programming)——展示互相覆蓋的子問題和最優子架構演算法
11、歐幾里得演算法(Euclidean algorithm)——計算兩個整數的最大公約數。最古老的演算法之一，出現在公元前300前歐幾里得的《幾何原本》。
12、期望-最大演算法(Expectation-maximization algorithm，又名EM-Training)——在統計計算中，期望-最大演算法在概率模型中尋找可能性最大的參數估算值，其中模型依賴於未發現的潛在變數。EM在兩個步驟中交替計算，第一步是計算期望，利用對隱藏變數的現有估計值，計算其最大可能估計值;第二步是最大化，最大化在第一步上求得的最大可能值來計算參數的值。
13、快速傅里葉變換(Fast Fourier transform，FFT)——計算離散的傅里葉變換(DFT)及其反轉。該演算法應用范圍很廣，從數字信號處理到解決偏微分方程，到快速計算大整數乘積。
14、梯度下降(Gradient descent)——一種數學上的最優化演算法。
15、哈希演算法(Hashing)。
16、堆排序(Heaps)。
17、Karatsuba乘法——需要完成上千位整數的乘法的系統中使用，比如計算機代數系統和大數程序庫，如果使用長乘法，速度太慢。該演算法發現於1962年。
18、LLL演算法(Lenstra-Lenstra-Lovasz lattice rection)——以格規約(lattice)基數為輸入，輸出短正交向量基數。LLL演算法在以下公共密鑰加密方法中有大量使用：背包加密系統(knapsack)、有特定設置的RSA加密等等。
19、最大流量演算法(Maximum flow)——該演算法試圖從一個流量網路中找到最大的流。它優勢被定義為找到這樣一個流的值。最大流問題可以看作更復雜的網路流問題的特定情況。最大流與網路中的界面有關，這就是最大流-最小截定理(Max-flow min-cut theorem)。Ford-Fulkerson 能找到一個流網路中的最大流。
20、合並排序(Merge Sort)。
21、牛頓法(Newton』s method)——求非線性方程(組)零點的一種重要的迭代法。
22、Q-learning學習演算法——這是一種通過學習動作值函數(action-value function)完成的強化學習演算法，函數採取在給定狀態的給定動作，並計算出期望的效用價值，在此後遵循固定的策略。Q-leanring的優勢是，在不需要環境模型的情況下，可以對比可採納行動的期望效用。
23、兩次篩法(Quadratic Sieve)——現代整數因子分解演算法，在實踐中，是目前已知第二快的此類演算法(僅次於數域篩法Number Field Sieve)。對於110位以下的十位整數，它仍是最快的，而且都認為它比數域篩法更簡單。
24、RANSAC——是「RANdom SAmple Consensus」的縮寫。該演算法根據一系列觀察得到的數據，數據中包含異常值，估算一個數學模型的參數值。其基本假設是：數據包含非異化值，也就是能夠通過某些模型參數解釋的值，異化值就是那些不符合模型的數據點。
25、RSA——公鑰加密演算法。首個適用於以簽名作為加密的演算法。RSA在電商行業中仍大規模使用，大家也相信它有足夠安全長度的公鑰。
26、Sch?nhage-Strassen演算法——在數學中，Sch?nhage-Strassen演算法是用來完成大整數的乘法的快速漸近演算法。其演算法復雜度為：O(N log(N) log(log(N)))，該演算法使用了傅里葉變換。
27、單純型演算法(Simplex Algorithm)——在數學的優化理論中，單純型演算法是常用的技術，用來找到線性規劃問題的數值解。線性規劃問題包括在一組實變數上的一系列線性不等式組，以及一個等待最大化(或最小化)的固定線性函數。
28、奇異值分解(Singular value decomposition，簡稱SVD)——在線性代數中，SVD是重要的實數或復數矩陣的分解方法，在信號處理和統計中有多種應用，比如計算矩陣的偽逆矩陣(以求解最小二乘法問題)、解決超定線性系統(overdetermined linear systems)、矩陣逼近、數值天氣預報等等。
29、求解線性方程組(Solving a system of linear equations)——線性方程組是數學中最古老的問題，它們有很多應用，比如在數字信號處理、線性規劃中的估算和預測、數值分析中的非線性問題逼近等等。求解線性方程組，可以使用高斯—約當消去法(Gauss-Jordan elimination)，或是柯列斯基分解( Cholesky decomposition)。
30、Strukturtensor演算法——應用於模式識別領域，為所有像素找出一種計算方法，看看該像素是否處於同質區域( homogenous region)，看看它是否屬於邊緣，還是是一個頂點。
31、合並查找演算法(Union-find)——給定一組元素，該演算法常常用來把這些元素分為多個分離的、彼此不重合的組。不相交集(disjoint-set)的數據結構可以跟蹤這樣的切分方法。合並查找演算法可以在此種數據結構上完成兩個有用的操作：
查找：判斷某特定元素屬於哪個組。
合並：聯合或合並兩個組為一個組。
32、維特比演算法(Viterbi algorithm)——尋找隱藏狀態最有可能序列的動態規劃演算法，這種序列被稱為維特比路徑，其結果是一系列可以觀察到的事件，特別是在隱藏的Markov模型中。
以上就是Christoph博士對於最重要的演算法的調查結果。你們熟悉哪些演算法?又有哪些演算法是你們經常使用的?