sift和meanshift原理和算法

1、SIFT算法由D.G.Lowe1999年提出，2004年完善總結(jié)，論文發(fā)表在2004年的IJCV上：DavidG.Lowe,Distinctiveimagefeaturesfromscale-invariantkeypoints,InternationalJournalofComputerVision,60,2(2004),pp.91-110后來Y.Ke將其描述子部分用PCA代替直方圖的方式，對(duì)其進(jìn)行改進(jìn)。SIFT方法一經(jīng)推出就在圖像處理界引起巨大反響，其方法效果良好、實(shí)現(xiàn)便捷,很快風(fēng)靡世界。很多圖像檢測(cè)、識(shí)別的應(yīng)用里都能找到sift方法的身影SIFT算法是一種提取局部特征的算法，在尺度空間尋

2、找極值點(diǎn)，提取位置，尺度，旋轉(zhuǎn)不變量。算法的主要特點(diǎn)為：SIFT特征是圖像的局部特征，其對(duì)旋轉(zhuǎn)、尺度縮放、亮度變化保持不變性，對(duì)視角變化、仿射變換、噪聲也保持一定程度的穩(wěn)定性。獨(dú)特性(Distinctiveness)好，信息量豐富，適用于在海量特征數(shù)據(jù)庫(kù)中進(jìn)行快速、準(zhǔn)確的匹配23。多量性，即使少數(shù)的幾個(gè)物體也可以產(chǎn)生大量SIFT特征向量。高速性，經(jīng)優(yōu)化的SIFT匹配算法甚至可以達(dá)到實(shí)時(shí)的要求?？蓴U(kuò)展性，可以很方便的與其他形式的特征向量進(jìn)行聯(lián)合。SIFT算法主要步驟：檢測(cè)尺度空間極值點(diǎn)精確定位極值點(diǎn)為每個(gè)關(guān)鍵點(diǎn)指定方向參數(shù)關(guān)鍵點(diǎn)描述子的生成SIFT算法詳細(xì)尺度空間理論目的是模擬圖像數(shù)據(jù)的多尺度特

3、征。高斯卷積核是實(shí)現(xiàn)尺度變換的唯一線性核，于是一副二維圖像的尺度空間定義為：L(x,y,e)=G(x,y,e)*I(x,y)其中G(x,y,e)是尺度可變高斯函數(shù)，G(x,y,e)=1/2*pi*e2*exp-(X2+y2)/2e2(x，y)是空間坐標(biāo)，e是尺度坐標(biāo)。為了有效的在尺度空間檢測(cè)到穩(wěn)定的關(guān)鍵點(diǎn)，提出了高斯差分尺度空間(DOGscale-space)。利用不同尺度的高斯差分核與圖像卷積生成。D(x,y,e)=(G(x,y,ke)-G(x,y,e)*I(x,y)=L(x,y,ke)-L(x,y,e)DOG算子計(jì)算簡(jiǎn)單，是尺度歸一化的LoG算子的近似。Gaussian卷積是有尺寸大小的，

4、使用同一尺寸的濾波器對(duì)兩幅包含有不同尺寸的同一物體的圖像求局部最值將有可能出現(xiàn)一方求得最值而另一方卻沒有的情況，但是容易知道假如物體的尺寸都一致的話它們的局部最值將會(huì)相同。SIFT的精妙之處在于采用圖像金字塔的方法解決這一問題，我們可以把兩幅圖像想象成是連續(xù)的，分別以它們作為底面作四棱錐，就像金字塔，那么每一個(gè)截面與原圖像相似，那么兩個(gè)金字塔中必然會(huì)有包含大小一致的物體的無(wú)窮個(gè)截面，但應(yīng)用只能是離散的，所以我們只能構(gòu)造有限層，層數(shù)越多當(dāng)然越好，但處理時(shí)間會(huì)相應(yīng)增加，層數(shù)太少不行，因?yàn)橄蛳虏蓸拥慕孛嬷锌赡苷也坏匠叽绱笮∫恢碌膬蓚€(gè)物體的圖像。有了圖像金字塔就可以對(duì)每一層求出局部最值，但是這樣的穩(wěn)定

5、點(diǎn)數(shù)目將會(huì)十分可觀，所以需要使用某種方法抑制去除一部分點(diǎn)，但又使得同一尺度下的穩(wěn)定點(diǎn)得以保存圖像金字塔的構(gòu)建：圖像金字塔共O組，每組有S層，下一組的圖像由上一組圖像降采樣得到。OctaveQOctave12圖1TwooctavesofaGaussianscale-spaceimagepyramidwiths=2intervals.ThefirstimageinthesecondoctaveiscreatedbydownsamplingthesecondtolastimageinthepreviousOctave1圖2Thedifferenceoftwoadjacentintervalsinth

6、eGaussianscale-spacepyramidcreateanintervalinthedifference-of-Gaussianpyramid（showningreen）.空間極值點(diǎn)檢測(cè)為了尋找尺度空間的極值點(diǎn)，每一個(gè)采樣點(diǎn)要和它所有的相鄰點(diǎn)比較，看其是否比它的圖像域和尺度域的相鄰點(diǎn)大或者小。如圖3所示，中間的檢測(cè)點(diǎn)和它同尺度的8個(gè)相鄰點(diǎn)和上下相鄰尺度對(duì)應(yīng)的9X2個(gè)點(diǎn)共26個(gè)點(diǎn)比較，以確保在尺度空間和二維圖像空間都檢測(cè)到極值點(diǎn)。構(gòu)建尺度空間需確定的參數(shù)e尺度空間坐標(biāo)Ooctave坐標(biāo)Ssub-level坐標(biāo)注：octaves的索引可能是負(fù)的。第一組索引常常設(shè)為0或者-1，當(dāng)設(shè)為-1

7、的時(shí)候，圖像在計(jì)算高斯尺度空間前先擴(kuò)大一倍。空間坐標(biāo)x是組octave的函數(shù)，設(shè)是0組的空間坐標(biāo)，注：在Lowe的文章中，Lowe使用了如下的參數(shù)：在組o=-1，圖像用雙線性插值擴(kuò)大一倍（對(duì)于擴(kuò)大的圖像）。精確確定極值點(diǎn)位置通過擬和三維二次函數(shù)以精確確定關(guān)鍵點(diǎn)的位置和尺度（達(dá)到亞像素精度），同時(shí)去除低對(duì)比度的關(guān)鍵點(diǎn)和不穩(wěn)定的邊緣響應(yīng)點(diǎn)（因?yàn)镈oG算子會(huì)產(chǎn)生較強(qiáng)的邊緣響應(yīng)），以增強(qiáng)匹配穩(wěn)定性、提高抗噪聲能力。邊緣響應(yīng)的去除一個(gè)定義不好的高斯差分算子的極值在橫跨邊緣的地方有較大的主曲率，而在垂直邊緣的方向有較小的主曲率。主曲率通過一個(gè)2x2的Hessian矩陣H求出：導(dǎo)數(shù)由采樣點(diǎn)相鄰差估計(jì)得到。D

8、的主曲率和H的特征值成正比，令為最大特征值關(guān)鍵點(diǎn)方向分配利用關(guān)鍵點(diǎn)鄰域像素的梯度方向分布特性為每個(gè)關(guān)鍵點(diǎn)指定方向參數(shù)，使算子具備旋轉(zhuǎn)不變性。在實(shí)際計(jì)算時(shí)，我們?cè)谝躁P(guān)鍵點(diǎn)為中心的鄰域窗口內(nèi)采樣，并用直方圖統(tǒng)計(jì)鄰域像素的梯度方向。梯度直方圖的范圍是0360度，其中每10度一個(gè)柱，總共36個(gè)柱。直方圖的峰值則代表了該關(guān)鍵點(diǎn)處鄰域梯度的主方向，即作為該關(guān)鍵點(diǎn)的方向。圖4是采用7個(gè)柱時(shí)使用梯度直方圖為關(guān)鍵點(diǎn)確定主方向的示例。圖4由梯度方向直方圖確定主梯度方向在梯度方向直方圖中，當(dāng)存在另一個(gè)相當(dāng)于主峰值80%能量的峰值時(shí)，則將這個(gè)方向認(rèn)為是該關(guān)鍵點(diǎn)的輔方向。一個(gè)關(guān)鍵點(diǎn)可能會(huì)被指定具有多個(gè)方向（一個(gè)主方向，

9、一個(gè)以上輔方向），這可以增強(qiáng)匹配的魯棒性53。至此，圖像的關(guān)鍵點(diǎn)已檢測(cè)完畢，每個(gè)關(guān)鍵點(diǎn)有三個(gè)信息：位置、所處尺度、方向。由此可以確定一個(gè)SIFT特征區(qū)域（在實(shí)驗(yàn)章節(jié)用橢圓或箭頭表示）。陳運(yùn)文特征點(diǎn)描述子生成關(guān)鍵點(diǎn)垮匪向量由關(guān)鍵點(diǎn)鄰域梯度信息生成特征向量接下來以關(guān)鍵點(diǎn)為中心取8X8的窗口。圖5-4左部分的中央黑點(diǎn)為當(dāng)前關(guān)鍵點(diǎn)的位置，每個(gè)小格代表關(guān)鍵點(diǎn)鄰域所在尺度空間的一個(gè)像素，箭頭方向代表該像素的梯度方向，箭頭長(zhǎng)度代表梯度模值，圖中藍(lán)色的圈代表高斯加權(quán)的范圍（越靠近關(guān)鍵點(diǎn)的像素梯度方向信息貢獻(xiàn)越大）。然后在每4X4的小塊上計(jì)算8個(gè)方向的梯度方向直方圖，繪制每個(gè)梯度方向的累加值，即可形成一個(gè)種子點(diǎn)

10、，如圖5右部分所示。此圖中一個(gè)關(guān)鍵點(diǎn)由2X2共4個(gè)種子點(diǎn)組成，每個(gè)種子點(diǎn)有8個(gè)方向向量信息。這種鄰域方向性信息聯(lián)合的思想增強(qiáng)了算法抗噪聲的能力，同時(shí)對(duì)于含有定位誤差的特征匹配也提供了較好的容錯(cuò)性。實(shí)際計(jì)算過程中，為了增強(qiáng)匹配的穩(wěn)健性，Lowe建議對(duì)每個(gè)關(guān)鍵點(diǎn)使用4X4共16個(gè)種子點(diǎn)來描述，這樣對(duì)于一個(gè)關(guān)鍵點(diǎn)就可以產(chǎn)生128個(gè)數(shù)據(jù)，即最終形成128維的SIFT特征向量。此時(shí)SIFT特征向量已經(jīng)去除了尺度變化、旋轉(zhuǎn)等幾何變形因素的影響，再繼續(xù)將特征向量的長(zhǎng)度歸一化，則可以進(jìn)一步去除光照變化的影響。當(dāng)兩幅圖像的SIFT特征向量生成后，下一步我們采用關(guān)鍵點(diǎn)特征向量的歐式距離來作為兩幅圖像中關(guān)鍵點(diǎn)的相似

11、性判定度量。取圖像1中的某個(gè)關(guān)鍵點(diǎn)，并找出其與圖像2中歐式距離最近的前兩個(gè)關(guān)鍵點(diǎn)，在這兩個(gè)關(guān)鍵點(diǎn)中，如果最近的距離除以次近的距離少于某個(gè)比例閾值，則接受這一對(duì)匹配點(diǎn)。降低這個(gè)比例閾值，SIFT匹配點(diǎn)數(shù)目會(huì)減少，但更加穩(wěn)定。SIFT算法的實(shí)際匹配效果如下：記得剛讀研究生的時(shí)候，學(xué)習(xí)的第一個(gè)算法就是meanshift算法，所以一直記憶猶新，今天和大家分享一下Meanshift算法,如有錯(cuò)誤，請(qǐng)?jiān)诰€交流。MeanShift算法，一般是指一個(gè)迭代的步驟，即先算出當(dāng)前點(diǎn)的偏移均值,移動(dòng)該點(diǎn)到其偏移均值，然后以此為新的起始點(diǎn)，繼續(xù)移動(dòng),直到滿足一定的條件結(jié)束.Meanshift推導(dǎo)給定d維空間Rd的n個(gè)樣

12、本點(diǎn)，i=l,n,在空間中任選一點(diǎn)x,那么MeanShift向量的基本形式定義為：S是一個(gè)半徑為h的高維球區(qū)域，滿足以下關(guān)系的y點(diǎn)的集合,k$何=y:(y-珀丁心-如撐k表示在這n個(gè)樣本點(diǎn)x中，有k個(gè)點(diǎn)落入S區(qū)域中.ik以上是官方的說法，即書上的定義，我的理解就是，在d維空間中，任選一個(gè)點(diǎn),然后以這個(gè)點(diǎn)為圓心，h為半徑做一個(gè)高維球，因?yàn)橛衐維，d可能大于2,所以是高維球。落在這個(gè)球內(nèi)的所有點(diǎn)和圓心都會(huì)產(chǎn)生一個(gè)向量，向量是以圓心為起點(diǎn)落在球內(nèi)的點(diǎn)位終點(diǎn)。然后把這些向量都相加。相加的結(jié)果就是Meanshift向量。如圖所以。其中黃色箭頭就是M（meanshift向量）hCenterCfmassMe

13、anuftvectorRe|roriofinterest再以meanshift向量的終點(diǎn)為圓心，再做一個(gè)高維的球。如下圖所以，重復(fù)以上步驟，就可得到一個(gè)meanshift向量。如此重復(fù)下去，meanshift算法可以收斂到概率密度最大得地方。也就是最稠密的地方。RegiOh：interest最終的結(jié)果如下:RerestMeanshift推導(dǎo):把基本的meanshift向量加入核函數(shù).那么，meanshift算法變形為n解釋一下K()核函數(shù)，h為半徑，C/nhd為單位密度，要使得上式f得到最大,kd最容易想到的就是對(duì)上式進(jìn)行求導(dǎo)，的確meanshift就是對(duì)上式進(jìn)行求導(dǎo).令

14、:K(x)叫做g(x)的影子核，名字聽上去聽深?yuàn)W的，也就是求導(dǎo)的負(fù)方向，那么上式可以表示VA,k(x.)二X對(duì)于上式，如果才用高斯核，那么，第一項(xiàng)就等于/Xx(fh,k第二項(xiàng)就相當(dāng)于一個(gè)meanshift向量的式子:那么(2)就可以表示為下圖分析的構(gòu)成，如圖所以，可以很清晰的表達(dá)其構(gòu)成。MeanShift要使得v/;-:7,當(dāng)且僅當(dāng)山川*=o,可以得出新的圓心坐標(biāo):_IX嚴(yán)曲寧件ELlV（H2）(3)上面介紹了meanshift的流程，但是比較散，下面具體給出它的算法流程。選擇空間中x為圓心，以h為半徑為半徑，做一個(gè)高維球，落在所有球內(nèi)的所有點(diǎn)x.i計(jì)算H1xl，如果111*,則利用（3）計(jì)算

15、X，返回1.meanshift在圖像上的聚類:真正大牛的人就能創(chuàng)造算法，例如像meanshift,em這個(gè)樣的算法，這樣的創(chuàng)新才能推動(dòng)整個(gè)學(xué)科的發(fā)展。還有的人就是把算法運(yùn)用的實(shí)際的運(yùn)用中，推動(dòng)整個(gè)工業(yè)進(jìn)步，也就是技術(shù)的進(jìn)步。下面介紹meashift算法怎樣運(yùn)用到圖像上的聚類核跟蹤。一般一個(gè)圖像就是個(gè)矩陣，像素點(diǎn)均勻的分布在圖像上，就沒有點(diǎn)的稠密性。所以怎樣來定義點(diǎn)的概率密度，這才是最關(guān)鍵的。如果我們就算點(diǎn)x的概率密度，采用的方法如下：以x為圓心，以h為半徑。落在球內(nèi)的點(diǎn)位x定義二個(gè)模式規(guī)則。i（1）X像素點(diǎn)的顏色與x像素點(diǎn)顏色越相近，我們定義概率密度越高。i（2）離x的位置越近的像素點(diǎn)x，定義

16、概率密度越高。i所以定義總的概率密度，是二個(gè)規(guī)則概率密度乘積的結(jié)果，可以（4）表示（4）其中：代表空間位置的信息，離遠(yuǎn)點(diǎn)越近，其值就越大，表示顏色信息，顏色越相似，其值越大。如圖左上角圖片，按照（4）計(jì)算的概率密度如圖右上。利用meanshift對(duì)其聚類，可得到左下角的圖。本文翻譯自維基百科，英文原文地址是：/wiki/ransac，如果您英語(yǔ)不錯(cuò)，建議您直接查看原文。RANSAC是“RANdomSAmpleConsensus（隨機(jī)抽樣一致）的縮寫。它可以從一組包含“局外點(diǎn)”的觀測(cè)數(shù)據(jù)集中，通過迭代方式估計(jì)數(shù)學(xué)模型的參數(shù)。它是一種不確定的算法它有一定的概率得出一個(gè)合理的結(jié)果；為了提高概率必須提

17、高迭代次數(shù)。該算法最早由Fischler和Bolles于1981年提出。RANSAC的基本假設(shè)是：（1）數(shù)據(jù)由“局內(nèi)點(diǎn)”組成，例如：數(shù)據(jù)的分布可以用一些模型參數(shù)來解釋；（2）“局外點(diǎn)”是不能適應(yīng)該模型的數(shù)據(jù)；（3）除此之外的數(shù)據(jù)屬于噪聲。局外點(diǎn)產(chǎn)生的原因有：噪聲的極值；錯(cuò)誤的測(cè)量方法；對(duì)數(shù)據(jù)的錯(cuò)誤假設(shè)。RANSAC也做了以下假設(shè)：給定一組（通常很小的）局內(nèi)點(diǎn)，存在一個(gè)可以估計(jì)模型參數(shù)的過程；而該模型能夠解釋或者適用于局內(nèi)點(diǎn)。本文內(nèi)容1示例2概述3算法4參數(shù)5優(yōu)點(diǎn)與缺點(diǎn)6應(yīng)用7參考文獻(xiàn)8外部鏈接一、示例一個(gè)簡(jiǎn)單的例子是從一組觀測(cè)數(shù)據(jù)中找出合適的2維直線。假設(shè)觀測(cè)數(shù)據(jù)中包含局內(nèi)點(diǎn)和局外點(diǎn)，其中局內(nèi)

18、點(diǎn)近似的被直線所通過，而局外點(diǎn)遠(yuǎn)離于直線。簡(jiǎn)單的最小二乘法不能找到適應(yīng)于局內(nèi)點(diǎn)的直線，原因是最小二乘法盡量去適應(yīng)包括局外點(diǎn)在內(nèi)的所有點(diǎn)。相反，RANSAC能得出一個(gè)僅僅用局內(nèi)點(diǎn)計(jì)算出模型，并且概率還足夠高。但是，RANSAC并不能保證結(jié)果一定正確，為了保證算法有足夠高的合理概率，我們必須小心的選擇算法的參數(shù)。左圖：包含很多局外點(diǎn)的數(shù)據(jù)集右圖：RANSAC找到的直線（局外點(diǎn)并不影響結(jié)果）二、概述RANSAC算法的輸入是一組觀測(cè)數(shù)據(jù)，一個(gè)可以解釋或者適應(yīng)于觀測(cè)數(shù)據(jù)的參數(shù)化模型，一些可信的參數(shù)。RANSAC通過反復(fù)選擇數(shù)據(jù)中的一組隨機(jī)子集來達(dá)成目標(biāo)。被選取的子集被假設(shè)為局內(nèi)點(diǎn)，并用下述方法進(jìn)行驗(yàn)證：

19、1.有一個(gè)模型適應(yīng)于假設(shè)的局內(nèi)點(diǎn)，即所有的未知參數(shù)都能從假設(shè)的局內(nèi)點(diǎn)計(jì)算得出。2用1中得到的模型去測(cè)試所有的其它數(shù)據(jù)，如果某個(gè)點(diǎn)適用于估計(jì)的模型，認(rèn)為它也是局內(nèi)點(diǎn)。如果有足夠多的點(diǎn)被歸類為假設(shè)的局內(nèi)點(diǎn)，那么估計(jì)的模型就足夠合理。4然后，用所有假設(shè)的局內(nèi)點(diǎn)去重新估計(jì)模型，因?yàn)樗鼉H僅被初始的假設(shè)局內(nèi)點(diǎn)估計(jì)過。5最后，通過估計(jì)局內(nèi)點(diǎn)與模型的錯(cuò)誤率來評(píng)估模型。這個(gè)過程被重復(fù)執(zhí)行固定的次數(shù)，每次產(chǎn)生的模型要么因?yàn)榫謨?nèi)點(diǎn)太少而被舍棄，要么因?yàn)楸痊F(xiàn)有的模型更好而被選用。三、算法偽碼形式的算法如下所示:輸入：data組觀測(cè)數(shù)據(jù)model適應(yīng)于數(shù)據(jù)的模型n適用于模型的最少數(shù)據(jù)個(gè)數(shù)k算法的迭代次數(shù)t用于決定數(shù)據(jù)是

20、否適應(yīng)于模型的閥值d判定模型是否適用于數(shù)據(jù)集的數(shù)據(jù)數(shù)目輸出：best_model跟數(shù)據(jù)最匹配的模型參數(shù)（如果沒有找到好的模型，返回null）best_consensus_set估計(jì)出模型的數(shù)據(jù)點(diǎn)best_error跟數(shù)據(jù)相關(guān)的估計(jì)出的模型錯(cuò)誤iterations=0best_model=nullbest_consensus_set二nullbest_error=無(wú)窮大while（iterationsk）maybe_inliers=從數(shù)據(jù)集中隨機(jī)選擇n個(gè)點(diǎn)maybe_model=適合于maybe_inliers的模型參數(shù)consensus_set二maybe_inliersfor（每個(gè)數(shù)據(jù)集中不

21、屬于maybe_inliers的點(diǎn)）if（如果點(diǎn)適合于maybe_model，且錯(cuò)誤小于t）將點(diǎn)添加到consensus_setif（consensus_set中的元素?cái)?shù)目大于d）已經(jīng)找到了好的模型，現(xiàn)在測(cè)試該模型到底有多好better_model=適合于consensus_set中所有點(diǎn)的模型參數(shù)this_error=better_model究竟如何適合這些點(diǎn)的度量if（this_errorbest_error）我們發(fā)現(xiàn)了比以前好的模型，保存該模型直到更好的模型出現(xiàn)best_model=better_modelbest_consensus_set二consensus_setbest_error=this_error增加迭代次數(shù)-返回best_model,best_consensus_set,best_errorRANSAC算法的可能變化包括以下幾種：（1）如果發(fā)現(xiàn)了一種足夠好的模型（該模型有足夠小的錯(cuò)誤率），則跳出主循環(huán)。這樣可能會(huì)節(jié)約計(jì)算額外參數(shù)的時(shí)間。（2）直接從maybe_model計(jì)算this_error，而不從consensus_set重新估計(jì)模型。這樣可能會(huì)節(jié)約比較兩種模型錯(cuò)誤的時(shí)間，但可能會(huì)對(duì)噪聲更敏感。四、參數(shù)我們不得不根據(jù)特定的問題和數(shù)據(jù)集通過實(shí)驗(yàn)來確定參數(shù)t和d。然而參數(shù)k（迭代次數(shù)）可以從理論結(jié)果推斷。當(dāng)我們從估計(jì)模型參數(shù)