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