SIFT特征點(diǎn)提取與匹配算法

1、精選優(yōu)質(zhì)文檔-傾情為你奉上精選優(yōu)質(zhì)文檔-傾情為你奉上專(zhuān)心-專(zhuān)注-專(zhuān)業(yè)專(zhuān)心-專(zhuān)注-專(zhuān)業(yè)精選優(yōu)質(zhì)文檔-傾情為你奉上專(zhuān)心-專(zhuān)注-專(zhuān)業(yè)二 特征點(diǎn)提取算法1、基于SIFT（Scale Invariant Feature Transform）方法的圖像特征匹配參看David G. Lowe 的“Distinctive Image Features from Scale-Invariant Keypoints”基于SIFT方法的圖像特征匹配可分為特征提取和特征匹配兩個(gè)部分，可細(xì)化分為五個(gè)部分：尺度空間極值檢測(cè)（Scale-space extrema detection）；精確關(guān)鍵點(diǎn)定位（Keypoint l

2、ocalization）關(guān)鍵點(diǎn)主方向分配（Orientation assignment）關(guān)鍵點(diǎn)描述子生成（Keypoint descriptor generation）比較描述子間歐氏距離進(jìn)行匹配（Comparing the Euclidean distance of the descriptors for matching）1.1 尺度空間極值檢測(cè)特征關(guān)鍵點(diǎn)的性質(zhì)之一就是對(duì)于尺度的變化保持不變性。因此我們所要尋找的特征點(diǎn)必須具備的性質(zhì)之一，就是在不同尺度下都能被檢測(cè)出來(lái)。要達(dá)到這個(gè)目的，我們可以在尺度空間內(nèi)尋找某種穩(wěn)定不變的特性。Koenderink和Lindeberg已經(jīng)證明，變換到尺度空

3、間唯一的核函數(shù)是高斯函數(shù)。因此一個(gè)圖像的尺度空間定義為：，是由可變尺度的高斯函數(shù)與輸入圖像卷積得到，即： （1.1）其中：在實(shí)際應(yīng)用中，為了能計(jì)算的相對(duì)高效，所真正使用的是差分高斯尺度空間（difference of Gaussian）。其定義如下： （1.2）如上式，D即是由兩個(gè)相鄰的尺度的差（兩個(gè)相鄰的尺度在尺度上相差一個(gè)相乘系數(shù)k）。圖 1.1圖1.1所展示的是建立DOG的一種實(shí)用的方法。初始圖像與不同值的高斯函數(shù)卷積，得到一垛模糊后的圖像，然后將這一垛模糊圖像臨近兩兩相減即得所對(duì)應(yīng)的DOG。這些模糊后的圖像以k為系數(shù)在尺度空間里被分隔開(kāi)，并且該垛內(nèi)最高的尺度應(yīng)是最低尺度的2倍。為了能開(kāi)

4、展后續(xù)工作（與尺度空間極值檢測(cè)相關(guān)，將在后續(xù)文章中作出解釋?zhuān)┎M(mǎn)足上述要求，每垛需要通過(guò)卷積得到s+3個(gè)模糊后的圖像，并且s和k需要具有關(guān)系。在一垛圖像建立完畢后，還需要降采樣得到下一垛圖像的DOG。在實(shí)際操作中首先用2倍于第一垛圖像的值建立出模糊圖像，然后再將此垛圖像降二采樣，即每2個(gè)像素抽出一個(gè)像素，就可以得到下一垛圖像的DOG。在上述工作完成后，所要完成的就是尺度空間的極值檢測(cè)。DOG上的某個(gè)像素要和本尺度的8個(gè)相鄰像素以及上下相鄰尺度各9個(gè)相鄰像素比較。這樣做的目的是為了確保圖像在尺度空間和二維圖像空間均檢測(cè)到極值點(diǎn)。如果該像素點(diǎn)在這所有參與比較的點(diǎn)中有最大值或者最小值，則認(rèn)為該像素點(diǎn)

5、是尺度空間的極值點(diǎn)之一。圖1.2表示這種極值檢測(cè)的原理。圖1.2另外需要注意的是，上述的尺度空間極值點(diǎn)檢測(cè)在每一個(gè)垛中都要進(jìn)行。最后獲得的極值點(diǎn)總和是所有垛中所檢測(cè)到的極值點(diǎn)的集合。那么如果這個(gè)極值點(diǎn)處在降采樣后的垛中，則需要在找出他后將其坐標(biāo)變換到原始大小的原圖上。容易寫(xiě)出這個(gè)變換公式為： （1.3）其中是原始大小圖像即原始圖像上的坐標(biāo)，經(jīng)采樣變換后變?yōu)?；o是處于垛的階數(shù)（即處于第幾個(gè)垛中）；=0或者-1，當(dāng)?shù)谝欢鈭D像為原圖經(jīng)過(guò)尺寸加倍后的圖像生成時(shí)值為1，不經(jīng)過(guò)加倍則為0。另外在建立尺度空間的過(guò)程中有兩個(gè)較為重要的參數(shù)要確定?？梢詫⒅枋鰹槌叨瓤臻g抽樣頻率和空間域抽樣頻率。尺度空間抽樣頻率

6、表現(xiàn)為每個(gè)DOG垛所含有的DOG數(shù)目。由于每個(gè)DOG垛中最大尺度已經(jīng)確定是最小尺度的2倍，則在這個(gè)范圍內(nèi)的DOG數(shù)目越多，抽樣頻率就越高。這個(gè)頻率影響著特征提取的效果。Lowe教授在其文章中論述了對(duì)于該參數(shù)所做的實(shí)驗(yàn)。圖 1.3實(shí)驗(yàn)表明在每個(gè)垛中有3個(gè)抽樣時(shí)特征點(diǎn)提取效果是最好的（從圖1.3左圖可以看出，無(wú)論是變化過(guò)的圖像中能取到與原圖中相同的特征點(diǎn)的比例，還是所取到的特征點(diǎn)與數(shù)據(jù)庫(kù)內(nèi)特征點(diǎn)匹配上的比例都是最高）。而之所以更高的抽樣頻率不能帶來(lái)更好的匹配效果，是因?yàn)槌闃宇l率越高，雖然提取的特征點(diǎn)越多，但這樣的特征點(diǎn)大多是不穩(wěn)定的，因此無(wú)法提高匹配的成功率，這從圖1.3右圖可以看出。另外一個(gè)參數(shù)

7、是空間域抽樣頻率。表現(xiàn)為的數(shù)值。由于圖像與高斯函數(shù)的卷積可以看作是空間濾波，則與濾波的截止頻率有很大的關(guān)系。越大，截止頻率就越小，能夠看到的抽樣值頻率也越小。圖 1.4Lowe教授在文章中也對(duì)的取值做了相關(guān)實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明當(dāng)取1.6時(shí)所得到的匹配效果最好，這從圖1.4中可以看出（同樣的，在變化過(guò)的圖像中能取到與原圖中相同的特征點(diǎn)的比例，還是所取到的特征點(diǎn)與數(shù)據(jù)庫(kù)內(nèi)特征點(diǎn)匹配上的比例都是最高）。另外他還證明，在建立尺度空間的第一垛圖像時(shí)，先將原始圖像的尺寸加倍，則可以使穩(wěn)定的特征點(diǎn)的數(shù)目達(dá)到原來(lái)的4倍。1.2精確關(guān)鍵點(diǎn)定位極值點(diǎn)確定之后，必須進(jìn)行有效的后續(xù)工作對(duì)這些點(diǎn)進(jìn)行篩選；因?yàn)榇藭r(shí)往往會(huì)有

8、可觀數(shù)量的極值點(diǎn)具有很低的對(duì)比度或者處于不理想的邊緣。我們把這些極值點(diǎn)成為備選關(guān)鍵點(diǎn)，而后續(xù)工作的目的就是去掉那些對(duì)比度低的以及處于不理想邊緣處的備選關(guān)鍵點(diǎn)（keypoint candidate），以得到最終參與匹配的特征關(guān)鍵點(diǎn)（keypoint）。1.2.1更精確的關(guān)鍵點(diǎn)位置描述早期的關(guān)鍵點(diǎn)定位方法比較粗糙。目前所采用較多的方法是由Brown教授所提出的三維二次曲線(xiàn)（3D quadratic function）展開(kāi)。該方法將DOG在所關(guān)注的像素點(diǎn)處用三維泰勒級(jí)數(shù)展開(kāi)（展開(kāi)到2次方項(xiàng)），然后再精確定位極值的位置至亞像素級(jí)。展開(kāi)式如下： （1.4）其中： ，（ k指當(dāng)前k層，k-1指k的下層，k

9、+1指上一層）可以看到，所有的偏導(dǎo)數(shù)值都由像素值的差分來(lái)近似；后面會(huì)涉及到的Hessian算子中的相關(guān)計(jì)算也是由像素值的差分來(lái)近似的。按照泰勒級(jí)數(shù)的定義，其中D和D的偏導(dǎo)數(shù)都是在展開(kāi)點(diǎn)所計(jì)算的值，而是估計(jì)點(diǎn)到展開(kāi)點(diǎn)的偏移量，即：其中被減值是估計(jì)點(diǎn)的坐標(biāo)，減數(shù)為展開(kāi)點(diǎn)的坐標(biāo)。那么要求得D的極值，則自然想到對(duì)這樣展開(kāi)后的D對(duì)求導(dǎo)，然后使導(dǎo)數(shù)為0，即求得了局部的極值。在這種理念下，則極值點(diǎn)對(duì)于展開(kāi)點(diǎn)的偏移量滿(mǎn)足： （1.5）則容易由此得到極值點(diǎn)的坐標(biāo)。容易想到，如果三維向量在任何一個(gè)維度的值大于0.5，那么這個(gè)極值點(diǎn)會(huì)更接近另外一個(gè)像素點(diǎn)，而不是本身的這個(gè)展開(kāi)點(diǎn)。那么此時(shí)就將展開(kāi)點(diǎn)換做更接近的那個(gè)點(diǎn)

10、，然后再次展開(kāi)計(jì)算偏移量。最后偏移量的值被加到展開(kāi)點(diǎn)上以得到關(guān)鍵點(diǎn)的最終位置。當(dāng)然這個(gè)最終位置的坐標(biāo)不一定是整數(shù)，所以這個(gè)關(guān)鍵點(diǎn)的位置是一種修正過(guò)的，或說(shuō)插值過(guò)（interpolated）的估計(jì)值。需要注意的是，SIFT特征匹配最終也不需要有一個(gè)整數(shù)的坐標(biāo)值。在生成了關(guān)鍵點(diǎn)描述子之后，在匹配時(shí)與具體的坐標(biāo)就不相關(guān)了。1.2.2去除對(duì)比度低的不穩(wěn)定關(guān)鍵點(diǎn)在精確定位了特征關(guān)鍵點(diǎn)之后，該特征關(guān)鍵點(diǎn)的DOG函數(shù)可以由其臨近的像素點(diǎn)的DOG展開(kāi)獲得，即式（1.1）。研究表明，特征關(guān)鍵點(diǎn)的DOG函數(shù)值可以用來(lái)去除那些因?yàn)閷?duì)比度偏低而不穩(wěn)定的關(guān)鍵點(diǎn)。其值越低，則越不穩(wěn)定越應(yīng)該忽略。在實(shí)際操作中，用來(lái)求的函數(shù)

11、并不是（1.1），而是在此基礎(chǔ)上繼續(xù)忽略2階項(xiàng)后所得： （1.6）在Lowe教授的研究中，這個(gè)閾值為0.03，亦即所有的點(diǎn)全部去除。1.2.3 去除由邊緣響應(yīng)所帶來(lái)的不穩(wěn)定關(guān)鍵點(diǎn)為了增強(qiáng)特征點(diǎn)的穩(wěn)定性，僅僅去除低對(duì)比的點(diǎn)是不夠的。DOG函數(shù)有著較強(qiáng)的邊緣響應(yīng)，如果關(guān)鍵點(diǎn)被定位在邊緣，那么這個(gè)關(guān)鍵點(diǎn)很有可能是不穩(wěn)定的，尤其容易受到噪聲的影響，即是是少量的噪聲也會(huì)影響匹配的穩(wěn)定性。一個(gè)定義不好的高斯差分算子的極值在橫跨邊緣的地方有較大的主曲率，而在垂直邊緣的方向有較小的主曲率。那么我們只需要求出關(guān)鍵點(diǎn)主曲率便可以決定是否因其處于邊緣而舍去他。主曲率可以通過(guò)22的Hessian矩陣來(lái)計(jì)算，其中：該點(diǎn)

12、的兩個(gè)主曲率是與Hessian矩陣的兩個(gè)特征值成比例的。而在實(shí)際應(yīng)用中并不用計(jì)算出H的特征值，因?yàn)槲覀兛梢灾豢紤]他們中較大的特征值比較小的特征值的比例r便可以確定該點(diǎn)是不是處于邊緣（因?yàn)樵跈M跨邊緣的地方有較大的主曲率，對(duì)應(yīng)一個(gè)大特征值；而在垂直邊緣的方向有較小的主曲率，對(duì)應(yīng)一個(gè)較小特征值，比例只要足夠大，就可以認(rèn)為該點(diǎn)滿(mǎn)足處于邊緣的性質(zhì)）。設(shè)為較大的特征值，為較小的特征值，則。由于 （1.7） （1.8）我們構(gòu)建 （1.9）則如果我們考慮時(shí)則認(rèn)為該點(diǎn)處于邊緣，那在具體判定時(shí)，我們可以不用計(jì)算出其具體特征值，而是只用等效判斷是否有即可。計(jì)算一個(gè)二階矩陣的跡以及其行列式，要比計(jì)算其特征值的代價(jià)小得

13、多，只用進(jìn)行20次不到的浮點(diǎn)操作即可。一般情況下，閾值取為10。1.3 關(guān)鍵點(diǎn)主方向分配給一個(gè)關(guān)鍵點(diǎn)分配主方向，并將主方向納入關(guān)鍵點(diǎn)的描述子特性之中，那么這個(gè)關(guān)鍵點(diǎn)就具有了旋轉(zhuǎn)不變性。描述主方向需要用到像素點(diǎn)的梯度。梯度的模和方向如下以像素差分的方法定義和計(jì)算： （1.10） （1.11）關(guān)鍵點(diǎn)的主方向是通過(guò)統(tǒng)計(jì)以關(guān)鍵點(diǎn)為中心的一個(gè)鄰域之內(nèi)所有點(diǎn)梯度方向來(lái)確定。在實(shí)際計(jì)算中，這種統(tǒng)計(jì)通過(guò)梯度方向直方圖來(lái)確定。梯度直方圖將360分為36個(gè)柱，每個(gè)柱為10。其中出現(xiàn)的梯度方向峰值就是這個(gè)關(guān)鍵點(diǎn)的主方向。在鄰域內(nèi)的點(diǎn)的方向被納入直方圖時(shí)，還要經(jīng)過(guò)一次高斯加權(quán)；這個(gè)加權(quán)的高斯函數(shù)是以關(guān)鍵點(diǎn)為中心，1.

14、5為標(biāo)準(zhǔn)差的，其中就是這個(gè)關(guān)鍵點(diǎn)所在的尺度。若當(dāng)梯度直方圖中存在的次高峰，其模值大于等于最高峰的80%，那么就將該次高峰對(duì)應(yīng)的方向定為該點(diǎn)的輔方向。如果一個(gè)特征點(diǎn)有輔方向，那么就建立另外一個(gè)新的特征點(diǎn)，這個(gè)特征點(diǎn)和原特征點(diǎn)有著同樣的坐標(biāo)，但是方向不同。也就是說(shuō)這樣會(huì)出現(xiàn)一些坐標(biāo)相同但是主方向不同的特征點(diǎn)。實(shí)驗(yàn)表明，雖然只有15%的特征點(diǎn)存在輔方向，但是給具有輔方向的關(guān)鍵點(diǎn)生成新關(guān)鍵點(diǎn)，能極大的提高匹配的穩(wěn)定性。最后，如果還想進(jìn)一步提高峰值位置的精度，可以用最接近峰值的3個(gè)直方圖值做拋物線(xiàn)擬合，將擬合出的拋物線(xiàn)最大值的位置作為精確的峰值位置，亦即精確的主方向角度。1.4 關(guān)鍵點(diǎn)描述子生成前面的工

15、作我們已經(jīng)指定了特征關(guān)鍵點(diǎn)的位置、尺度和方向，這樣特征點(diǎn)就已經(jīng)對(duì)于這些參數(shù)的變化保持了不變性。下一步就是要生成一種能描述這樣特征的描述子，并盡可能讓這種描述子對(duì)于其他一些變化也有一定的不變性，如光照和三維視角變化。在建立描述子時(shí)，要將描述子的主方向坐標(biāo)旋轉(zhuǎn)到關(guān)鍵點(diǎn)的主方向上來(lái)，這樣才能保證具有旋轉(zhuǎn)不變性。之后選擇以關(guān)鍵點(diǎn)為中心的1616區(qū)域（圖1.5），計(jì)算出其中每一點(diǎn)的梯度值；然后將這個(gè)區(qū)域所有的梯度值用一個(gè)中心在該區(qū)域中央的高斯函數(shù)加權(quán)（高斯函數(shù)的標(biāo)準(zhǔn)差為1.5倍的區(qū)域?qū)挾龋?。接下?lái)將整個(gè)區(qū)域分為16個(gè)44的小區(qū)域（圖1.5中紅色區(qū)域），在這個(gè)小區(qū)域中統(tǒng)計(jì)梯度直方圖，直方圖分為8個(gè)方向；那

16、么整個(gè)描述子所覆蓋的區(qū)域含有的信息就是168=128個(gè)，則整個(gè)描述子可以看做是一個(gè)128維的向量，即特征向量。生成描述子的過(guò)程可以由圖1.6表示。 最后將特征向量歸一化，則可以去掉光照變化產(chǎn)生的影響。如果光照變化是對(duì)比度變化，則相當(dāng)于是對(duì)每個(gè)點(diǎn)的梯度乘上了一個(gè)常數(shù)，那么標(biāo)準(zhǔn)化后這個(gè)常數(shù)就被消除了；如果光照變化是亮度的變化，那么相對(duì)于對(duì)每個(gè)點(diǎn)的像素值加上了一個(gè)常數(shù)，對(duì)梯度的變化沒(méi)有任何影響。但是由于一些非線(xiàn)性的光照變化會(huì)使某些像素的梯度模值產(chǎn)生較大變化，同時(shí)對(duì)梯度方向沒(méi)有影響，因此我們?cè)诮y(tǒng)計(jì)梯度直方圖時(shí)將所有大于某個(gè)閾值的梯度模值都置為這個(gè)閾值，就可以降低光照變化的影響。要注意的是，向量歸一化是

17、在所有模值經(jīng)過(guò)閾值的限制之后進(jìn)行的。因?yàn)檫@樣的操作相當(dāng)于降低了大模值點(diǎn)的模值在匹配中的權(quán)重。這個(gè)閾值一般選為0.2。圖 1.5圖 1.6至此SIFT特征全部集中在SIFT向量，亦即特征描述子之上。作為圖像的局部特征一種表征，他決定了基于特征的各種后續(xù)處理方法的效果。1.5 比較描述子間歐氏距離進(jìn)行匹配在描述子生成完畢之后，特征提取階段即告結(jié)束。完成圖像匹配，接下來(lái)要做的是對(duì)這些特征運(yùn)用適當(dāng)?shù)谋容^方法來(lái)找到對(duì)應(yīng)關(guān)系。由于特征點(diǎn)描述子可以看做為128維的向量，則可以通過(guò)向量的相關(guān)概念來(lái)抽象出比較描述子的方法。最直觀的便是兩個(gè)向量間的歐氏距離，我們可以容易的想出，兩個(gè)相同的向量其歐式距離為0，那么兩

18、個(gè)完全相同的特征點(diǎn)描述子，其歐氏距離也為0。不過(guò)很顯然，由于噪聲以及其他圖像變換的存在，同一個(gè)點(diǎn)對(duì)應(yīng)在不同圖像上的特征描述子不可能完全相同，那么如何確定兩個(gè)描述子匹配呢？首先應(yīng)該想到，描述子距離越近，越應(yīng)該認(rèn)為其匹配。但是為了達(dá)到穩(wěn)健的匹配，僅僅有“最近”是不夠的。因?yàn)閷?duì)于128維這樣高維的描述子，誤匹配并沒(méi)有像獨(dú)特的對(duì)應(yīng)性，因此誤匹配的描述子容易具有比較接近的距離。因此，如果兩個(gè)特征點(diǎn)A和B真正的是一個(gè)對(duì)匹配點(diǎn)，那么他們的描述子之間所對(duì)應(yīng)歐式距離首先要最?。黄浯?，這個(gè)小還要小到一定程度：需要他比描述子A到除B以外其他任何描述子的距離都顯著的小，才能體現(xiàn)正確匹配的唯一獨(dú)特性。在造作中，我們可以以最近距離與次近距離的比例來(lái)衡量這種“顯著程度”，只有當(dāng)最近距離與次近距離小于某個(gè)比例閾值時(shí)，我們才接受這一對(duì)匹配。要比較所有描述子的距離，我們可以通過(guò)遍歷搜索完成。雖然相對(duì)于模板匹配的整圖像遍歷搜索，這樣的計(jì)算量并不算太大，但也比較可觀。選擇一種合適的數(shù)據(jù)結(jié)構(gòu)存貯這些描述子，并用合適的搜索策略這個(gè)數(shù)據(jù)結(jié)構(gòu)，是重要優(yōu)化命題，但在本文中，不對(duì)這個(gè)問(wèn)題進(jìn)行具體的討論。RANSAC去誤匹配的思