SIFT特征點(diǎn)提取

1、精選優(yōu)質(zhì)文檔-傾情為你奉上摘 要圖像匹配在遙感、醫(yī)學(xué)、計(jì)算機(jī)視覺等很多領(lǐng)域中有著廣泛的應(yīng)用，是提取和匹配圖像特征是實(shí)現(xiàn)圖像自動(dòng)配準(zhǔn)的一種重要方法。SIFT(尺度不變特性變換，Scale Invariant Feature Transform)最初是作為一種關(guān)鍵點(diǎn)的特征提取出來的，其匹配能力較強(qiáng)，可以處理兩幅圖像之間發(fā)生平移、旋轉(zhuǎn)、防輻射4等變換情況下的匹配問題，甚至在某種程度上對(duì)任意角度拍攝的圖像也具備較為穩(wěn)定的特征匹配能力。作為一種優(yōu)秀的局部特征描述子，SIFT算子被廣泛應(yīng)用于目標(biāo)識(shí)別、圖像配準(zhǔn)、室內(nèi)場(chǎng)景定位等場(chǎng)合。論文著重介紹了一種基于圖像特征值的匹配方法(SIFT算法),包括SIFT算法

2、的發(fā)展歷史，算法特點(diǎn)，主要思想和實(shí)現(xiàn)步驟，然后實(shí)現(xiàn)SIFT特征點(diǎn)提取，以尋找一種優(yōu)化算法，減少SIFT的算法復(fù)雜度。(介紹用什么實(shí)驗(yàn),得到什么結(jié)論)關(guān)鍵詞：SIFT算法，特征匹配，特征點(diǎn)提取專心-專注-專業(yè)AstractIn remote sensing image matching, medical, computer vision many adjacent domain in a wide range of applications, Extraction and matching image characteristics is to realize the automatic ima

3、ge registration is a kind of important method . SIFT was originally as a key point for feature extraction of come out, its matching with the strong ability can handle two images occur between translation, rotation and anti-radiation such transformation under the circumstance of the matching problem,

4、 even in some extent of arbitrary Angle photographs of image and also has a relatively stable feature matching ability. As a kind of excellent local characteristics description son, SIFT operators are widely used in target recognition, image registration, indoor scene positioning and so on. This pap

5、er mainly introduces a method based on image eigenvalue of matching method (SIFT algorithm). Including SIFT algorithm development history, algorithm characteristics, main ideas and implementation steps and then realized SIFT feature point extraction to find an optimization algorithm to reduce SIFT a

6、lgorithm complexity .(請(qǐng)不要直譯)Keywords：SIFT algorithm, feature matching, feature point extraction, simplified algorithm. 目 錄摘 要I第1章 緒論11.1 課題背景11.2目的意義11.3研究內(nèi)容及結(jié)構(gòu)安排2第2章 智能優(yōu)化方法32.1 基于蟻群的優(yōu)化算法32.2 基于魚群的優(yōu)化算法32.3 基于神經(jīng)網(wǎng)絡(luò)的優(yōu)化算法32.4 本章小結(jié)3第3章 SIFT基本算法43.1 構(gòu)建尺度空間53.2局部極值點(diǎn)的檢測(cè)73.3 極值點(diǎn)的方向分配73.4特征點(diǎn)描述子的生成83.5 SIFT算法的

7、擴(kuò)展93.6 本章小結(jié)10第4章 SIFT算法的改進(jìn)方案114.1 SIFT簡化算法介紹114.2 SIFT簡化算法124.3 本章小結(jié)14第5章 實(shí)驗(yàn)結(jié)果及分析155.1 簡化算法不變性測(cè)試155.2 描述子維數(shù)的選擇155.3改進(jìn)算法的時(shí)間復(fù)雜度155.4 本章小結(jié)15致 謝16參考文獻(xiàn)17附錄18第1章 緒論1.1 課題背景SIFT（Scale Invariant Feature Transform）算法由D.GLowe8于1999年提出，2004年哥倫比亞大學(xué)的David Lowe7提出了一種新的提取特征點(diǎn)的算法SIFT算法。后來，Y。ke將其描述子部分用PCA代替直方圖的方式，對(duì)SI

8、FT算法進(jìn)行改進(jìn)，目前基于改進(jìn)SIFT特征點(diǎn)的算法在圖像處理中的應(yīng)用越來越廣泛，而且近年來這方面的研究也取得了很大的成果。較好的解決了物體遮掩、旋轉(zhuǎn)縮放、視覺變換引起的圖像變形等問題。本文主要針對(duì)圖像匹配中的SIFT算法進(jìn)行研究，然后將圖片編程到OPENCV軟件中，并借助gsl來實(shí)現(xiàn)改進(jìn)的SIFT算法1的可用性。1.2目的意義 在圖像提取算法百花齊放的時(shí)候，SIFT算法作為一個(gè)嶄新特征提取的技術(shù)，具有強(qiáng)大和精確的匹配能力和廣闊的發(fā)展和應(yīng)用空間。對(duì)SIFT算法的改進(jìn)和優(yōu)化方法也有很多，如降低特征向量維數(shù)，增強(qiáng)算法的獨(dú)特性和魯棒性等。目前新型改進(jìn)算法CSIFT，將SIFT與顏色不變量相結(jié)合19。S

9、IFT算子的應(yīng)用鄰域很廣泛，目前已應(yīng)用于目標(biāo)識(shí)別、移動(dòng)物體識(shí)別和圖像配準(zhǔn)和全景拼接等鄰域，并仍有很大研究潛力；尤其在圖像檢索中的應(yīng)用研究也有很廣泛的應(yīng)用意義和價(jià)值。因此SIFT算法將在以后將被更多研究者深入的研究，并具有更實(shí)用的應(yīng)用價(jià)值。圖像配準(zhǔn)2的用處很廣泛，其技術(shù)廣泛應(yīng)用于計(jì)算機(jī)視覺3、目標(biāo)跟蹤、醫(yī)療診斷等許多方面。景象匹配技術(shù)給予圖像匹配的原理，以其定位的精確度在理論上與射程無關(guān)和自主性強(qiáng)等特點(diǎn)，成為組合導(dǎo)航中頗受重視的關(guān)鍵技術(shù)之一。在遙感領(lǐng)域，實(shí)現(xiàn)圖像融合、變化檢測(cè)、圖像校正、圖像鑲嵌等應(yīng)用中，圖像匹配都是必不可少的一個(gè)關(guān)鍵步驟。1.3研究內(nèi)容及結(jié)構(gòu)安排 第2章 智能優(yōu)化方法優(yōu)化算法簡

10、單介紹2.1 基于蟻群的優(yōu)化算法2.2 基于魚群的優(yōu)化算法 2.3 基于神經(jīng)網(wǎng)絡(luò)的優(yōu)化算法2.4 本章小結(jié)第3章 SIFT基本算法SIFT算法的發(fā)展歷程 SIFT算法由D.GLowe 1999年提出，2004年完善總結(jié)。后來Y.Ke將其描述子部分用PCA代替直方圖的方式，對(duì)其進(jìn)行改進(jìn)。SIFT算法的主要思想 SIFT算法是一種提取局部特征的算法，在尺度空間尋找極值點(diǎn)，提取位置，尺度，旋轉(zhuǎn)不變量。SIFT算法的主要特點(diǎn)：a) SIFT特征是圖像的局部特征，對(duì)其旋轉(zhuǎn)、尺度縮放、亮度變化保持不變性，對(duì)視覺變化、放射變化、噪聲也保持一定程度的穩(wěn)定性。b) 獨(dú)特性（Distinctiveness）好，信

11、息量豐富，適用于在海量特征數(shù)據(jù)中進(jìn)行快速、準(zhǔn)確的圖像匹配9。c) 多量性，即使少數(shù)的幾個(gè)物體，也可以產(chǎn)生大量的SIFT特征向量。d) 高速性，經(jīng)簡化的SIFT匹配算法可以達(dá)到實(shí)時(shí)性的要求。e) 可擴(kuò)展性，可以很方便的與其他形式的特征向量進(jìn)行聯(lián)合。SIFT（Scale Invariant Feature Transform）即尺度不變特征變換，它對(duì)于圖像的尺寸和旋轉(zhuǎn)保持不變性，以下是用來產(chǎn)生SIFT圖像特征的主要計(jì)算步驟： 1)尺度空間檢測(cè)極值點(diǎn)：計(jì)算的第一階段是搜索所有的尺度和圖像位置，使用高斯差分公式可以有效的檢測(cè)出潛在的特征點(diǎn)，這些特征點(diǎn)對(duì)于尺度縮放的旋轉(zhuǎn)變換具有不變性； 2）關(guān)鍵點(diǎn)的定位

12、：對(duì)于每個(gè)點(diǎn)，確定他們的位置和尺度； 3）確定關(guān)鍵點(diǎn)的方向：為每個(gè)關(guān)鍵點(diǎn)分配一個(gè)方向，以后所有對(duì)圖像的數(shù)據(jù)的操作都被轉(zhuǎn)換為對(duì)特征點(diǎn)方向、尺度和位置的操作，從而保證變化得不變性； 4）生成特征點(diǎn)描述子：通過對(duì)關(guān)鍵點(diǎn)當(dāng)前尺度周圍區(qū)域的梯度統(tǒng)計(jì)，生成特征點(diǎn)描述子。 下面詳細(xì)介紹SIFT算子特征提取的過程。3.1 構(gòu)建尺度空間 構(gòu)建尺度空間的目的是檢測(cè)對(duì)于圖像的尺度變化具有不變性的位置，可以使用尺度的連續(xù)函數(shù)也就是尺度空間在所有可能的尺度中尋找穩(wěn)定的特征，高斯卷積核實(shí)實(shí)現(xiàn)尺度變換的唯一線性核。因此，若I（x,y）為輸入圖像，G（x,y,）是尺度可變高斯函數(shù)，則一個(gè)圖像的尺度空間被定義為函數(shù)L（x,y,

13、），見式（2.1）。 L（x,y,）= G（x,y,）*I（x,y） （2.1） 其中，為尺度因子，越大，表示圖像的概貌特征；越小，表明圖像的細(xì)節(jié)特征，*為卷積運(yùn)算。式（2.1）中的高斯函數(shù)G（x,y,）定義為式（2.2）。G（x,y,）=1/22 e-（x2+y2）/22 （2.2）為了在尺度空間中有效的檢測(cè)穩(wěn)定關(guān)鍵點(diǎn)的位置，Lowe提出了高斯差分卷積，高斯差分函數(shù)D（x,y,）可以通過不變倍增因子K的兩個(gè)相鄰尺度圖像差計(jì)算得出，見式（2.3）。D（x,y,）=（G(x,y,k)-G(x,y,)）*I(x,y)=L(x,y,k)- L(x,y,) （2.3）選擇高斯差分函數(shù)的幾個(gè)優(yōu)點(diǎn)： 1）

14、計(jì)算效率高：由于L對(duì)于每個(gè)尺度空間都是需要計(jì)算的，而D只需在此基礎(chǔ)上做減法操作； 2）高斯差分函數(shù)DoG(differerce-of-Gaussian)是尺度歸一化算子LoG(Laplacian of Gaussian)的近似，Lindeberg證明具有因子2 的尺度歸一化算子LoG對(duì)于真正的尺度不變性是必須的。DoG于LoG關(guān)系如式（2.4）。 2G=G/GG(x,y,k)- G(x,y,)/( k-k) （2.4） 因此，G(x,y,k)- G(x,y,) （k-1）22G 式（2.5）中的（k-1）因子在所有的尺度中式一個(gè)常量，所以不會(huì)影響極值點(diǎn)的位置，當(dāng)k變?yōu)?時(shí)近似的誤差會(huì)趨近于零，

15、但是在試驗(yàn)中發(fā)現(xiàn)近似值對(duì)于極值點(diǎn)檢測(cè)方面的穩(wěn)定性沒有什么影響。 3）實(shí)驗(yàn)表明，從尺度歸一化LoG空間中提取的特征穩(wěn)定性最佳，優(yōu)于梯度、Hessian、Harris焦點(diǎn)函數(shù)6。不要直接貼圖,要自已畫D（x,y,）具體計(jì)算過程見圖2.3，初始圖像經(jīng)逐步高斯卷積運(yùn)算，得到一系列尺度空間，即高斯（Gaussian）尺度空間，也就是圖中左邊的一列，右邊一列表示由高斯制度空間經(jīng)差分運(yùn)算得到的高斯差分（DoG）尺度空間。尺度空間分為o階，每一階有s層。為了能再高斯差分（DoG）尺度空間的s層上檢測(cè)候選點(diǎn)，需要有s+2層的高斯差分尺度空間，因而對(duì)應(yīng)的高斯尺度空間需要為，則下一層尺度因子為k，故k=2I/s。在

16、產(chǎn)生了s+2個(gè)圖像后，頂層圖像有s+3層。如圖所展示的，s+3個(gè)高斯圖像產(chǎn)生s+2個(gè)高斯差分圖像，所以必須首先構(gòu)造s+3個(gè)高斯尺度圖像。這些圖像的尺度因子逐個(gè)以常數(shù)k倍遞增，即若當(dāng)前層圖像的尺度因子由原始圖像進(jìn)行了1：2的采樣計(jì)算得出。圖2.3中，左邊的o階尺度空間構(gòu)成高斯金字塔，右邊o階尺度空間構(gòu)成高斯差分金字塔。3.2局部極值點(diǎn)的檢測(cè) 為了檢測(cè)D（x,y,）的局部極大值和極小值，每個(gè)采樣點(diǎn)都要和它同尺度的8個(gè)相鄰點(diǎn)和上下相鄰尺寸對(duì)應(yīng)的92個(gè)點(diǎn)相比較。只有當(dāng)它比所有相鄰點(diǎn)都大或者都小的時(shí)候這個(gè)點(diǎn)菜被選擇。這個(gè)檢查的花費(fèi)是相當(dāng)?shù)偷?，因?yàn)榇蟛糠值牟蓸狱c(diǎn)在上一次檢查中就被淘汰了，見圖2.4所示。圖

17、要自已畫，圖標(biāo)移到圖外面來上一步被選擇的點(diǎn)稱為候選點(diǎn)，但是如果要進(jìn)行下一步確定關(guān)鍵點(diǎn)的位置、尺度、主曲率，還要剔除那些低對(duì)比（對(duì)噪聲很敏感）的點(diǎn)和處于邊緣的點(diǎn)。3.3 極值點(diǎn)的方向分配 通過為每個(gè)關(guān)鍵點(diǎn)分配一個(gè)統(tǒng)一的基于局部圖像屬性的方向，關(guān)鍵點(diǎn)描述子轉(zhuǎn)化為由它的方向來描述，從而實(shí)現(xiàn)圖像旋轉(zhuǎn)的不變性。這個(gè)方法了Schmid和Mohr（1997）的方向不變描述子5。這種方法的缺點(diǎn)是它限制了描述子的使用并拋棄了一部分圖像信息。 對(duì)于每一個(gè)采樣點(diǎn)L（x,y）,計(jì)算其梯度模值m（x,y）和方向（x,y）的公式為式（2.14）和式（2.15）。m（x,y）= 2.14（x,y）=tan-1（L(x,y,

18、+1)-L(x,y-1)）/（L(x+1,y)-L(x-1,y)） 2.15 為了進(jìn)一步精確關(guān)鍵點(diǎn)的方向，采用梯度直方圖統(tǒng)計(jì)法。以關(guān)鍵點(diǎn)為圓心，1.5為半徑的圓形區(qū)域中，統(tǒng)計(jì)關(guān)鍵點(diǎn)鄰域窗口的梯度值，并繪制梯度直方圖。其中梯度直方圖將360°分為36個(gè)單元（bin）,每10°為一個(gè)單元。每個(gè)鄰域點(diǎn)對(duì)梯度方向的貢獻(xiàn)隨鄰域點(diǎn)與關(guān)鍵點(diǎn)的距離增加而減少，具體為成高斯函數(shù)遞增。直方圖的峰值處即為關(guān)鍵點(diǎn)的主方向。 在主方向被選定之后，梯度直方圖中還可能存在一個(gè)或一個(gè)以上峰值為主峰值的80%以上，為了增強(qiáng)匹配的魯棒性，可以增強(qiáng)一些關(guān)鍵點(diǎn)，這些關(guān)鍵點(diǎn)于原關(guān)鍵點(diǎn)具有相同位置和尺度，并將符合要求

19、的峰值作為其方向，只有15%關(guān)鍵點(diǎn)才具有多個(gè)方向。3.4特征點(diǎn)描述子的生成我們已經(jīng)計(jì)算了關(guān)鍵點(diǎn)的位置、尺度和方向，下一步是要確定關(guān)鍵點(diǎn)描述子，特征點(diǎn)描述子的生成過程具體如下：鍵點(diǎn)為圓心將關(guān)鍵點(diǎn)鄰域旋轉(zhuǎn)°，其中為關(guān)鍵點(diǎn)的方向，從而保證了旋轉(zhuǎn)的不變性；在旋轉(zhuǎn)后的圖像中，以關(guān)鍵點(diǎn)的中心取1616的鄰域窗口，圖2.5中左圖即為關(guān)鍵點(diǎn)的鄰域窗口，每個(gè)小格代表關(guān)鍵點(diǎn)鄰域窗口中的一個(gè)像素，箭頭的長度為像素的模值，箭頭的方向?yàn)橄袼氐姆较?，這個(gè)方向是旋轉(zhuǎn)后的像素方向，即-；將1616的矩形窗口均勻分為16個(gè)44個(gè)子區(qū)域，如圖2.5中右圖，采用高斯模糊的方法，高斯模糊的方法有利于增加與關(guān)鍵點(diǎn)較近鄰域的權(quán)

20、值，并降低與關(guān)鍵點(diǎn)較遠(yuǎn)鄰域的權(quán)值，然后計(jì)算每個(gè)林宇中8個(gè)方向的梯度累加值： 得到特征點(diǎn)描述子的特征向量為448=128維向量。經(jīng)過以上的變換，SIFT特征向量已經(jīng)剔除了尺度變換、旋轉(zhuǎn)變換的影響。3.5 SIFT算法的擴(kuò)展 SIFT算法具有很好的魯棒性和抗干擾性，有著廣泛的應(yīng)用，但是由于SIFT算子具有很高的維數(shù)（128維），增強(qiáng)了其計(jì)算復(fù)雜性和時(shí)間復(fù)雜度，并且在大規(guī)模特征數(shù)據(jù)庫的檢索中存在存儲(chǔ)壓力。國內(nèi)外研究學(xué)者針對(duì)其高維數(shù)的缺點(diǎn)，進(jìn)行了改進(jìn)和嘗試，以求在保持SIFT算子良好特征的前提下，盡量降低其維數(shù)。在這些研究中，較為有代表性的事PCA-SIFT和GLOH，兩者都是從這個(gè)方面入手，并且都采

21、用了PCA（Principal componment analysis）技術(shù)。 PCA技術(shù)11是通過對(duì)數(shù)據(jù)降維萊實(shí)現(xiàn)簡化的目的。通過一個(gè)正交矩陣變換把原數(shù)據(jù)變換到一個(gè)新的坐標(biāo)系統(tǒng)中，從而實(shí)現(xiàn)高維數(shù)數(shù)據(jù)到低維數(shù)數(shù)據(jù)的轉(zhuǎn)換，原變量中的大部分信息可以用維數(shù)少且互不相關(guān)的新變量來表示。主成分的劃分按照信息量的數(shù)目，包含最大信息的綜合指標(biāo)作為第一主成分，其次的作為第二主成分，一般主成分的數(shù)目按需要反映全部信息量的百分比來決定。主成分分析主要是采用樣本矩陣的協(xié)方差矩陣。 PCA技術(shù)的優(yōu)點(diǎn)之一是其完全無參數(shù)限制。也就是說，PCA的計(jì)算和實(shí)現(xiàn)過程中不需要人為預(yù)先設(shè)定的參數(shù)或根據(jù)任何經(jīng)驗(yàn)?zāi)Ｐ蛯?duì)過程進(jìn)行干預(yù)，計(jì)算

22、結(jié)果只與數(shù)據(jù)本身有關(guān)。3.6 本章小結(jié)第4章 SIFT算法的改進(jìn)方案SIFT算法是一種基于局部特征描述的算法，對(duì)于每個(gè)特征點(diǎn)，根據(jù)其鄰域內(nèi)的像素決定其描述子向量，較全局特征算法在大型數(shù)據(jù)庫匹配中有了更好的應(yīng)用，但是由于SIFT算子的特征描述子為128維，在存儲(chǔ)中需要耗費(fèi)的存儲(chǔ)空間和匹配時(shí)間，GLOH算法雖然比SIFT算法由著更好的性能，但其特征向量也為128維，沒有在復(fù)雜度上進(jìn)行提高。針對(duì)于SIFT算法維數(shù)較高的缺點(diǎn)，本論文SIFT算法進(jìn)行了改進(jìn)，一下為具體的改進(jìn)算法。4.1 SIFT簡化算法介紹 SIFT算法的改進(jìn)方案是從特征點(diǎn)的描述子入手，因?yàn)樘卣鼽c(diǎn)描述子生成占去整個(gè)算法處理時(shí)間的大部分，

23、影響了算法的實(shí)時(shí)性，本論文的改進(jìn)算法也是針對(duì)于特征點(diǎn)描述子進(jìn)行改進(jìn)。 本論文的改進(jìn)算法是將原有的均勻分布的矩形區(qū)域改為以關(guān)鍵點(diǎn)為中心向外擴(kuò)散的同心圓區(qū)域，生成關(guān)鍵點(diǎn)的鄰域沒有變小。這樣改進(jìn)主要有以下一些因素：1)SIFT算法中應(yīng)用了高斯模糊的方法，也就是將圖像與高斯函數(shù)即正態(tài)函數(shù)做卷積。對(duì)于圖像來說，高斯模糊生成的曲面等高線是從關(guān)鍵點(diǎn)開始呈高斯分布的同心圓。這樣處理以后與關(guān)鍵點(diǎn)較近區(qū)域中的像素對(duì)關(guān)鍵點(diǎn)描述子的生成影響比重較大，而與關(guān)鍵點(diǎn)較遠(yuǎn)區(qū)域中的像素對(duì)關(guān)鍵點(diǎn)描述子的生成影響小。若將原區(qū)域劃分改為以關(guān)鍵點(diǎn)為中心的同心圓區(qū)域，可以省去高斯的模糊的步驟：2）SIFT算法需要計(jì)算每個(gè)關(guān)鍵點(diǎn)的方向，并

24、在描述子生成前旋轉(zhuǎn)鄰域，使關(guān)鍵點(diǎn)的方向?yàn)?°，從而保證旋轉(zhuǎn)不變性。這是因?yàn)榫匦尾⒉痪哂行D(zhuǎn)不變性，相對(duì)而言，圓形區(qū)域具有很好的旋轉(zhuǎn)不變性，可以免去鄰域角度歸零的步驟。新的描述子構(gòu)造方法如下：以關(guān)鍵點(diǎn)為中心，16為直徑的圓形窗戶區(qū)域作為鄰域，以保證生成特征點(diǎn)描述子所需要計(jì)算的鄰域范圍和原算法基本一致：將半徑為8的圓形鄰域以2為單位分為4個(gè)同心圓，圖3.1即為劃分之后的同心圓，每個(gè)格子代表一個(gè)像素值：對(duì)于4個(gè)同心圓區(qū)域，分別求出其10個(gè)方向（0°、36°、72°、108°、144°、180°、216°、252°

25、;、288°、324°）的梯度累加值。由中心向外，取第一個(gè)圓環(huán)的10維向量作為特征向量的第一至第十個(gè)元素，取第二個(gè)圓環(huán)的10維向量作為特征向量的第11至第20個(gè)個(gè)元素，以此類推。這樣，特征點(diǎn)描述子即為410=40維向量：為了保證旋轉(zhuǎn)不變性，對(duì)特征向量實(shí)施排序操作。設(shè)D使關(guān)鍵點(diǎn)的特征向量，D1、D2、D3、D4分別為從中心向外第一、第二、第三、第四個(gè)圓環(huán)的特征向量，則D=（D1,D2,D3,D4），其中Di=(Di1,Di2,Di9,Di10),i1,4。首先標(biāo)記出最內(nèi)圓最大值出現(xiàn)的位置，即 dI1,dI2,dI9,dI10中的最大值，若dI1為最大值，則不需要做任何處理，若

26、最大值不是dI1,則進(jìn)行如下操作：將D1、D2、D3、D4同時(shí)循環(huán)左移，直至D1中的最大值為特征向量D1中的第一位，設(shè)d17為向量D1中的最大值，則移動(dòng)之后四個(gè)圓環(huán)的特征向量為Di=(di7,di8,，di10,di1,di2,，di6)。如果將每一個(gè)10維向量分別取向量的最大值并執(zhí)行此步驟，則匹配的效果會(huì)大大降低。這樣操作保證了四個(gè)圓環(huán)旋轉(zhuǎn)相同的角度，等同于原算法中鄰域歸零的操作，從而保證了改進(jìn)描述子具有選擇不變性。4.2 SIFT簡化算法將編好的程序輸入到VC+運(yùn)行，具體的步驟為：第一步，動(dòng)態(tài)文件加入要運(yùn)行的DEBUG里面第二步，在options -directory里面加頭文件和lib

27、文件；在右側(cè)下拉框里面選include files,include files包含opencv安裝程序里的和gnuwin32里面的；同樣的lib文件也是同樣的方法，加到OPENCV和GUNWIN32里面。第三步，升級(jí)VC+運(yùn)稈就可以了。實(shí)驗(yàn)中分別處理了經(jīng)過旋轉(zhuǎn)的兩幅圖片，如圖（1），圖（2），經(jīng)過觀察與分析得出：兩幅圖像在經(jīng)過旋轉(zhuǎn)后，利用SIFT簡化的算法提取的特征點(diǎn)是相同的： 圖（1）（圖標(biāo)） 圖（2），圖標(biāo)4.3 本章小結(jié)第5章 實(shí)驗(yàn)結(jié)果及分析5.1 簡化算法不變性測(cè)試 為了驗(yàn)證改進(jìn)的SIFT算法的可行性和有效性，實(shí)驗(yàn)驗(yàn)證了在其旋轉(zhuǎn)、尺度、變換時(shí)的圖像匹配效果，并與原算法在匹配時(shí)間及匹配效

28、果上做對(duì)比。編程環(huán)境為OPENCV。5.2 描述子維數(shù)的選擇本論文在改進(jìn)算法中需要確定的一個(gè)重要參數(shù)是四個(gè)同心圓環(huán)窗口的向量維數(shù)，即每個(gè)同心圓環(huán)窗口所要統(tǒng)計(jì)的梯度直方圖數(shù)目。例如，若每個(gè)同心圓環(huán)選擇的向量維度為8，則生成的特征向量的維度為88=32維。向量維數(shù)不是越大越好，選擇一個(gè)合適的向量維度可以提高查全率、正確率和降低時(shí)間復(fù)雜度。 5.3改進(jìn)算法的時(shí)間復(fù)雜度 由于改進(jìn)算子簡化了特征點(diǎn)描述子，在匹配效果上有一定的降低，但是大大降低了SIFT算子的維數(shù)，時(shí)間復(fù)雜度也降低了很多。更實(shí)用于海亮的數(shù)據(jù)搜索。5.4 本章小結(jié) 本文在總結(jié)了SIFT算子的優(yōu)點(diǎn)的同時(shí)，針對(duì)其維數(shù)過高，不適用于海量數(shù)據(jù)匹配的

29、不足，提出了自己的改進(jìn)方案。本人從改進(jìn)描述子入手，因?yàn)樘卣鼽c(diǎn)描述子的生成占居了整個(gè)算法處理的大部分時(shí)間。簡化的特征點(diǎn)描述子將原算法中均勻分布的矩形區(qū)域改為關(guān)鍵點(diǎn)為中心向外擴(kuò)展的四個(gè)同心圓區(qū)域，生成關(guān)鍵點(diǎn)所需要計(jì)算的鄰域沒有變小，只是改進(jìn)了鄰域的劃分方法。改進(jìn)后的SIFT算子將特征點(diǎn)描述子的維數(shù)由128維降至40維。 致 謝 論文完成之際，首先衷心地感謝我的指導(dǎo)教師王妍瑋老師的諄諄教誨和悉心指導(dǎo)，在畢業(yè)設(shè)計(jì)的3個(gè)月時(shí)間里，王老師給了我極大的幫助。王老師知識(shí)豐富、思維敏捷，在學(xué)業(yè)上積極創(chuàng)新的開拓精神令我永生難忘。在畢業(yè)設(shè)計(jì)和畢業(yè)論文撰寫階段，王老師不僅在學(xué)習(xí)上給予我?guī)椭?，而且她的那種負(fù)責(zé)的精神和強(qiáng)

30、烈的責(zé)任感，對(duì)我今后的發(fā)展提出了指導(dǎo)性建議。王老師認(rèn)真敬業(yè)的工作態(tài)度和為人師表的作風(fēng)，體現(xiàn)了一個(gè)教育工作者的無私奉獻(xiàn)精神和科研工作者嚴(yán)謹(jǐn)?shù)闹螌W(xué)態(tài)度，這將使我在未來的工作和學(xué)習(xí)中受益終身。在此謹(jǐn)向尊敬的王老師致以我最誠摯的謝意。還要感謝華德學(xué)院電子信息工程系的所有教師，在學(xué)習(xí)和生活上你們都給予我最寶貴的意見和極大的幫助，還有我的指導(dǎo)員王明志教師，在平時(shí)的學(xué)習(xí)和生活中給予我的鼓勵(lì)和關(guān)心。 感謝我的父母，一直以來對(duì)我無私的關(guān)懷和付出，在面對(duì)各種困難時(shí)，給我支持的鼓勵(lì)！感謝所有關(guān)心我，幫助過我的朋友和同學(xué)！參考文獻(xiàn)1 王國美，陳孝威 SIFT特征匹配算法研究D.貴州大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院：2007.

31、2 何文峰，查紅彬 基于平面特征的深度圖像配準(zhǔn)D 北京大學(xué)：2006.3 馬頌德，張正友 計(jì)算機(jī)視覺計(jì)算理論與算法基礎(chǔ)M.北京：科學(xué)出版社，2003.4 于長江.高等畫法幾何學(xué)M北京：航空專業(yè)教材編審組，1983.5 Schmid C,Mohr R.Local grayvalue invariants for image retrievalJ.IEEE Transactiongs on Pattern Analysis and Machine Intelligence1997.6 K.Mikolajczyk.detection of local features invariant to af

32、fine transformationsC.Ph.D.thesis Institut National Polytechnique deGrenoble France.2002.7 David G.Lowe.Distinctive Image Features from Scale-Invariant KeypointsC.International Journal of Computer Vision,2004.8 David G.Lowe.Object recognition from Iocal scale-invariant featuresC.International Confer

33、enceon Computer Vision,CorfuGreece,1999.9 趙輝.基于特征點(diǎn)的圖像配準(zhǔn)算法研究C.山東大學(xué)碩士學(xué)位論文.2006.附錄SIFT源程序代碼#include "utils.h"#include "imgfeatures.h"#include <cxcore.h>#include <math.h>int import_oxfd_features( char*, struct feature* );int export_oxfd_features( char*, struct feature*, i

34、nt );void draw_oxfd_features( IplImage*, struct feature*, int );void draw_oxfd_feature( IplImage*, struct feature*, CvScalar );int import_lowe_features( char*, struct feature* );int export_lowe_features( char*, struct feature*, int );void draw_lowe_features( IplImage*, struct feature*, int );void dr

35、aw_lowe_feature( IplImage*, struct feature*, CvScalar );int import_features( char* filename, int type, struct feature* feat )int n;switch( type )case FEATURE_OXFD:n = import_oxfd_features( filename, feat );break;case FEATURE_LOWE:n = import_lowe_features( filename, feat );break;default:fprintf( stde

36、rr, "Warning: import_features(): unrecognized feature" "type, %s, line %dn", _FILE_, _LINE_ );return -1;if( n = -1 )fprintf( stderr, "Warning: unable to import features from %s,"" %s, line %dn", filename, _FILE_, _LINE_ );return n;int export_features( char* fi

37、lename, struct feature* feat, int n )int r, type;if( n <= 0 | ! feat )fprintf( stderr, "Warning: no features to export, %s line %dn",_FILE_, _LINE_ );return 1;type = feat0.type;switch( type )case FEATURE_OXFD:r = export_oxfd_features( filename, feat, n );break;case FEATURE_LOWE:r = expo

38、rt_lowe_features( filename, feat, n );break;default:fprintf( stderr, "Warning: export_features(): unrecognized feature" "type, %s, line %dn", _FILE_, _LINE_ );return -1;if( r )fprintf( stderr, "Warning: unable to export features to %s,"" %s, line %dn", filenam

39、e, _FILE_, _LINE_ );return r;void draw_features( IplImage* img, struct feature* feat, int n )int type;if( n <= 0 | ! feat )fprintf( stderr, "Warning: no features to draw, %s line %dn",_FILE_, _LINE_ );return;type = feat0.type;switch( type )case FEATURE_OXFD:draw_oxfd_features( img, feat

40、, n );break;case FEATURE_LOWE:draw_lowe_features( img, feat, n );break;default:fprintf( stderr, "Warning: draw_features(): unrecognized feature" " type, %s, line %dn", _FILE_, _LINE_ );break;double descr_dist_sq( struct feature* f1, struct feature* f2 )double diff, dsq = 0;double

41、* descr1, * descr2;int i, d;d = f1->d;if( f2->d != d )return DBL_MAX;descr1 = f1->descr;descr2 = f2->descr;for( i = 0; i < d; i+ )diff = descr1i - descr2i;dsq += diff*diff;return dsq;int import_oxfd_features( char* filename, struct feature* features )struct feature* f;int i, j, n, d;d

42、ouble x, y, a, b, c, dv;FILE* file;if( ! features )fatal_error( "NULL pointer error, %s, line %d", _FILE_, _LINE_ );if( ! ( file = fopen( filename, "r" ) ) )fprintf( stderr, "Warning: error opening %s, %s, line %dn",filename, _FILE_, _LINE_ );return -1;if( fscanf( file,

43、 " %d %d ", &d, &n ) != 2 )fprintf( stderr, "Warning: file read error, %s, line %dn",_FILE_, _LINE_ );return -1;if( d > FEATURE_MAX_D )fprintf( stderr, "Warning: descriptor too long, %s, line %dn",_FILE_, _LINE_ );return -1;f = calloc( n, sizeof(struct featur

44、e) );for( i = 0; i < n; i+ )if( fscanf( file, " %lf %lf %lf %lf %lf ", &x, &y, &a, &b, &c ) != 5 )fprintf( stderr, "Warning: error reading feature #%d, %s, line %dn",i+1, _FILE_, _LINE_ );free( f );return -1;fi.img_pt.x = fi.x = x;fi.img_pt.y = fi.y = y;fi.

45、a = a;fi.b = b;fi.c = c;fi.d = d;fi.type = FEATURE_OXFD;for( j = 0; j < d; j+ )if( ! fscanf( file, " %lf ", &dv ) )fprintf( stderr, "Warning: error reading feature descriptor" " #%d, %s, line %dn", i+1, _FILE_, _LINE_ );free( f );return -1;fi.descrj = dv;fi.scl =

46、 fi.ori = 0;fi.class = 0;fi.fwd_match = fi.bck_match = fi.mdl_match = NULL;fi.mdl_pt.x = fi.mdl_pt.y = -1;fi.feature_data = NULL;if( fclose(file) )fprintf( stderr, "Warning: file close error, %s, line %dn",_FILE_, _LINE_ );free( f );return -1;*features = f;return n;int export_oxfd_features

47、( char* filename, struct feature* feat, int n )FILE* file;int i, j, d;if( n <= 0 )fprintf( stderr, "Warning: feature count %d, %s, line %sn",n, _FILE_, _LINE_ );return 1;if( ! ( file = fopen( filename, "w" ) ) )fprintf( stderr, "Warning: error opening %s, %s, line %dn&quo

48、t;,filename, _FILE_, _LINE_ );return 1;d = feat0.d;fprintf( file, "%dn%dn", d, n );for( i = 0; i < n; i+ )fprintf( file, "%f %f %f %f %f", feati.x, feati.y, feati.a,feati.b, feati.c );for( j = 0; j < d; j+ )fprintf( file, " %f", feati.descrj );fprintf( file, "

49、;n" );if( fclose(file) )fprintf( stderr, "Warning: file close error, %s, line %dn",_FILE_, _LINE_ );return 1;return 0;void draw_oxfd_features( IplImage* img, struct feature* feat, int n )CvScalar color = CV_RGB( 255, 255, 255 );int i;if( img-> nChannels > 1 )color = FEATURE_OXFD

50、_COLOR;for( i = 0; i < n; i+ )draw_oxfd_feature( img, feat + i, color );void draw_oxfd_feature( IplImage* img, struct feature* feat, CvScalar color )double m4 = feat->a, feat->b, feat->b, feat->c ;double v4 = 0 ;double e2 = 0 ;CvMat M, V, E;double alpha, l1, l2;cvInitMatHeader( &M

51、, 2, 2, CV_64FC1, m, CV_AUTOSTEP );cvInitMatHeader( &V, 2, 2, CV_64FC1, v, CV_AUTOSTEP );cvInitMatHeader( &E, 2, 1, CV_64FC1, e, CV_AUTOSTEP );cvEigenVV( &M, &V, &E, DBL_EPSILON );l1 = 1 / sqrt( e1 );l2 = 1 / sqrt( e0 );alpha = -atan2( v1, v0 );alpha *= 180 / CV_PI;cvEllipse( img

52、, cvPoint( feat->x, feat->y ), cvSize( l2, l1 ), alpha,0, 360, CV_RGB(0,0,0), 3, 8, 0 );cvEllipse( img, cvPoint( feat->x, feat->y ), cvSize( l2, l1 ), alpha,0, 360, color, 1, 8, 0 );cvLine( img, cvPoint( feat->x+2, feat->y ), cvPoint( feat->x-2, feat->y ),color, 1, 8, 0 );cvLine( img, cvPoint( feat->x, feat->y+2 ), cvPoint( feat->x, feat->y-2 ),color, 1, 8, 0 );int import_lowe_features( char* filename, struct feature* features )struct feature*