APP
角點匹配的通用流程：提取檢測子，篩選后生成描述子，特征點匹配，去除匹配錯誤點
Sift角點提取：
1、高斯模糊
高斯模糊（圖像和高斯核卷積得到的結果），對圖像進行一定的平滑處理。其中sigma表示的是尺度空間，它表示的是圖像模糊的程度，值越大圖像越模糊，越小越接近原圖。
2、構建高斯金字塔
(1)?先將原圖像擴大一倍之后作為高斯金字塔的第1組第1層，將第1組第1層圖像經(jīng)高斯卷積（其實就是高斯平滑或稱高斯濾波）之后作為第1組金字塔的第2層，然后將sigma乘以一個比例系數(shù)k,等到 一個新的平滑系數(shù)，用它來平滑第1組第2層圖像，結果圖像作為第3層。重復操作，最后得到L層圖像，在同一組中，每一層圖像的尺寸都是一樣的，只是平滑系數(shù)不一樣，由于高斯系數(shù)不同，導致尺度空間(看一張圖像的縱深，離得近看得清楚，離得遠看的模糊)也不同，sift要找的就是在不同尺度空間都存在的極值點。
(2)?用第1組倒數(shù)第三層圖像做一倍降采樣，得到的圖像作為第2組的第1層，然后對第2組的第1層圖像做平滑因子為sigma的高斯平滑，依次類推得到第2組
(3)?以此類推得到N組不同的高斯差分圖，他們的區(qū)別是每組之間大小差一倍。然后對同一組的圖進行差分，得到高斯差分圖，因此得到N組尺寸不同的差分圖用于后續(xù)提取特征
3、選取特征點
有了高斯差分后的圖像后就是要尋找極值點了。極值點的檢測只在同一組中從第二層開始至倒數(shù)第二層為止的相鄰層進行Dog(difference of gauss)的極值搜索。用當前獲取到候選的極值點與八鄰域，以及上一個和下一個高斯尺度進行比較，如果該點是極值則保留。
?
4、篩選特征點
1、首先上一步選取的極值點本身是離散的，因此需要做子像元插值，也叫亞像素插值(利用離散的點插值到連續(xù)空間的點)。
?
2、在某個尺度下的極值點空間位置為(x,y,σ), 連續(xù)情況下，極值點可能落在了(x,y,σ)的附近，設其偏離了(x,y,σ)的坐標為(Δx,Δy,Δσ)，因此用D(x)表示在(x,y,σ)點展開
? 
令泰勒展開式倒數(shù)為0，求得對應的Δx,Δy,Δσ，經(jīng)過多次迭代最終得到連續(xù)空間極值點對應的值，這里應該是sift的精髓，利用尺度空間的工具，構造了一個利用有限的離散數(shù)據(jù)來逼近連續(xù)的數(shù)據(jù)
中的極值的方法
?
3、細化候選極值點：去除較小的極值點；去掉邊緣極值點
(1)?插值后的連續(xù)空間的點對應的極值，根據(jù)一個閾值進行判斷是否保 留
(2)?特征點落在邊緣比較麻煩，因為有定位歧義，另外容易受到噪聲干 擾，邊緣在水平方向的梯度比較大，豎直方向梯度比較小，這里通過黑 塞矩陣表示x和y方向的二階導，求解黑塞矩陣兩個
方向梯度值的比值， 如果兩個特征值差別越小，越有可能是角點，差別大則可能是邊緣，因 此設置一個閾值10作為比值的閾值
?
5、生成梯度方向與特征描述
(1) 梯度方向
以當前特征點所在區(qū)域，R為半徑 這里r = 3 * 1.5 * sigma(高斯尺度)，計算該區(qū)域所有像素的幅度和幅角
? 
以10度為步長構建360度的直方圖，并將該區(qū)域幅度統(tǒng)計進去，求出幅度最大的幅角作為主方向，為了得到更精確的角度，通過選取離主峰最近的3個峰做拋物線插值，找到精確的角度。另外，
如果次高幅度達到主幅度的80%，則保留為次方向。到這里每個特征點都包含了(x,y,σ,θ)，有次方向的復制為兩個特征點
(2) 特征描述
主要步驟為矯正主方向，生成描述子，歸一化
首先以特征點為中心，旋轉后將特征點主方向與坐標軸對其，選取以特征點為中心的8x8鄰域像素，計算幅度和幅角 ，每個4x4小塊兒分別計算其8個方向單位的梯度直方圖，作為每個小塊兒的
獨立特征。在實際實現(xiàn)過程中，sift計算了16x16鄰域像素，也就是生成了16個小塊，共128維特征。
?
Surf vs sift:
看過一篇論文對sift和surf的比較，sift對尺度和旋轉要優(yōu)于surf，surf在亮度變化下效果最好，并且速度是sift的3倍
?
Surf更快：
1、尺度空間構建避開使用高斯核，而是使用不同大小的方框濾波，這樣速度更快
（1）方框濾波：利用積分圖原理對filter內(nèi)元素求和
（2）積分圖
? 
點(x,y)的積分值可以使用點(x-1,y)與點(x,y-1)的積分值之和，然后減去 重疊區(qū)域，也就是減去點(x-1,y-1)的積分值，最后再加上點(x,y)的像素 值得到點(x,y)的積分值。
2、統(tǒng)計該區(qū)域的harr哈爾小波響應得出主方向
3、以特征點為中心選取一個區(qū)域，將其劃分為16個正方形，每個正方形內(nèi)為5x5大小，計算每個正方形針對harr小波響應的 dx, dy, dx絕對值，dy絕對值
?
角點匹配：FLANN快速最近鄰匹配庫
先構建KD樹對數(shù)據(jù)進行索引劃分，減少暴力窮舉法的計算量。然后通過KNN計算該點與模板特征點中的哪個點的距離最近，找到N組匹配對后，用RANSAC進行錯誤點剔除。
（1）KD樹：
減少搜索時間的數(shù)據(jù)結構，根據(jù)超平面進行分割下圖所示，是k=2時的一顆kd樹。需要提醒的是進行劃分(split)的維度的順序可以是任意的，不一定按照x,y,z,x,y,z…的順序進行。每一個節(jié)點都會
記錄劃分的維度。FLANN中有劃分維度選擇的算法。
KD樹的構建：
KD樹是一個二叉樹，對數(shù)據(jù)空間空間進行劃分，每一個結點對應一個空間范圍。如上圖所示，三維空間的劃分方式。首先確定在數(shù)據(jù)集上對應方差最大的維度ki，并找到在ki維度上的數(shù)據(jù)集的中值kv（并作為根節(jié)點）,即第一步把空間劃分成兩部分，在第ki維上小于kv的為一部分稱為左子節(jié)點，大于kv的為另外一部分對應右子節(jié)點，，然后再利用同樣的方法，對左子結點和右子節(jié)點繼續(xù)構建二叉樹，直所剩數(shù)據(jù)集為空。
例子：有5個數(shù)據(jù)，每個數(shù)據(jù)都是5維，建立KD樹。A<7,5,7,3,8>;B<3,4,1,2,7>;C<5,2,6,6,9>;D<9,3,2,4,1>,E<2,1,5,1,4>，首先在計算在5個維度上的方差為6.56；2；5.36；2.96；8.56；可見在第5維度上方差最大，繼續(xù)在第5個維度上找到中值為7，即B點，在第5維度上值小于7的作為左子樹數(shù)據(jù)(A,C)，大于7的作為右子樹(D,E)，然后繼續(xù)在A,C,兩點上計算方差最大的維度，繼續(xù)劃分。D,E也是如此。
?
KD樹的查詢：
從根節(jié)點開始沿二叉樹搜索，直到葉子結點為止，此時該葉節(jié)點并不一定是最近的點，但是一定是葉子結點附近的點。所以一定要有回溯的過程，回溯到根節(jié)點為止。也就是所有途徑的點中并未被選中的點也會參與計算。
例如：查詢與M<5，4，1，3，6>點的最近鄰點，查詢路徑為B，A，C，計算完MC的距離后，逆序向上，查詢A及A的右子樹，再次回溯B及B左子樹，最后得到最近的距離,MB點最近。
?
Sift改進KD樹:
一般來說用標準的KD樹時數(shù)據(jù)集的維數(shù)不超過20，但是像SIFT特征描述子128為，SURF描述子為64維，所以要對現(xiàn)有的KD樹進行改進。正?；厮莸倪^程，完全是按照查詢時路徑?jīng)Q定的，沒有考慮查詢路徑上的數(shù)據(jù)性質。
BBF(Best-Bin-First)查詢機制能確保優(yōu)先包含最近鄰點的空間，即BBF維護了一個優(yōu)先隊列，每一次查詢到左子樹或右子樹的過程中，同時計算查詢點在該維度的中值的距離差保存在優(yōu)先隊列里，同時另一個孩子節(jié)點地址也存入隊列里，回溯的過程即從優(yōu)先隊列按（差值）從小到大的順序依次回溯。BBF設置了超時機制，為了在高維數(shù)據(jù)上，滿足檢索速度的需要以精度換取時間，獲得快速查詢。這樣可知，BBF機制找到的最近鄰是近似的，并非是最近的，只能說是離最近點比較近而已。
?
KNN最近鄰算法：
首先求測試數(shù)據(jù)與訓練數(shù)據(jù)的歐式距離，然后根據(jù)距離進行升序排序，接下來取前K個數(shù)據(jù)進行加權平均，根據(jù)單個數(shù)據(jù)占前k個數(shù)據(jù)距離的比值來綜合計算前k個數(shù)據(jù)的類別，從而判斷測試數(shù)據(jù)的類別。在sift里，每個特征點有128維的特征，根據(jù)對模板128維特征的距離進行計算，這里K取1，則距離最小的點則可能是對應的匹配點
?
RANSAC隨機抽樣一致：
尋找一個最佳單應性矩陣H，矩陣大小為3×3。RANSAC目的是找到最優(yōu)的參數(shù)矩陣使得滿足該矩陣的數(shù)據(jù)點個數(shù)最多。由于單應性矩陣有8個未知參數(shù)，至少需要8個線性方程求解，對應到點位置信息上，一組點對可以列出兩個方程，則至少包含4組匹配點對。
1、隨機從數(shù)據(jù)集中隨機抽出4個樣本數(shù)據(jù) (此4個樣本之間不能共線)，計算出變換矩陣H，記為模型M
2、計算數(shù)據(jù)集中所有數(shù)據(jù)與模型M的投影誤差，若誤差小于閾值，加入內(nèi)點集
3、如果當前內(nèi)點集 I 元素個數(shù)大于最優(yōu)內(nèi)點集 I_best , 則更新 I_best = I，同時更新迭代次數(shù)k
4、如果迭代次數(shù)大于k,則退出 ; 否則迭代次數(shù)加1，并重復上述步驟
5、最終只保留內(nèi)點集中的匹配點對
到這里，整個sift角點提取，匹配，去重的整個流程就結束了，經(jīng)典永流傳
?
本文摘自 ：https://www.cnblogs.com/
