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代替直方圖的方式，對其進(jìn)行改進(jìn)。SIFT方法一經(jīng)推出就在圖像處理界引起巨大反響，其方法效果良好、實現(xiàn)便捷,很快風(fēng)靡世界。很多圖像檢測、識別的應(yīng)用里都能找到sift方法的身影SIFT算法是一種提取局部特征的算法，在尺度空間尋

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

3、征。高斯卷積核是實現(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)。為了有效的在尺度空間檢測到穩(wěn)定的關(guā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算子計算簡單，是尺度歸一化的LoG算子的近似。Gaussian卷積是有尺寸大小的，

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

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

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

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

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

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

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

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

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

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

14、:K(x)叫做g(x)的影子核，名字聽上去聽深奧的，也就是求導(dǎo)的負(fù)方向，那么上式可以表示VA,k(x.)二X對于上式，如果才用高斯核，那么，第一項就等于/Xx(fh,k第二項就相當(dāng)于一個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為半徑為半徑，做一個高維球，落在所有球內(nèi)的所有點x.i計算H1xl，如果111*,則利用（3）計算

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

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

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

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

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

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

21、屬于maybe_inliers的點）if（如果點適合于maybe_model，且錯誤小于t）將點添加到consensus_setif（consensus_set中的元素數(shù)目大于d）已經(jīng)找到了好的模型，現(xiàn)在測試該模型到底有多好better_model=適合于consensus_set中所有點的模型參數(shù)this_error=better_model究竟如何適合這些點的度量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)了一種足夠好的模型（該模型有足夠小的錯誤率），則跳出主循環(huán)。這樣可能會節(jié)約計算額外參數(shù)的時間。（2）直接從maybe_model計算this_error，而不從consensus_set重新估計模型。這樣可能會節(jié)約比較兩種模型錯誤的時間，但可能會對噪聲更敏感。四、參數(shù)我們不得不根據(jù)特定的問題和數(shù)據(jù)集通過實驗來確定參數(shù)t和d。然而參數(shù)k（迭代次數(shù)）可以從理論結(jié)果推斷。當(dāng)我們從估計模型參數(shù)