【正文】 條以上邊界的交點(diǎn)。這類算法的基礎(chǔ)就在于先檢測出圖像的邊緣，然后再在此基礎(chǔ)之上檢測出邊緣突然變換的點(diǎn)，就作為檢測角點(diǎn)的結(jié)果。主要缺點(diǎn)是對邊緣提取算法依賴性大，如果提取的邊緣發(fā)生錯誤，或是邊緣線發(fā)生中斷(在實(shí)際中經(jīng)常會遇到這種情況)，則對角點(diǎn)的提取結(jié)果將造成較大影響。直接基于圖像灰度的角點(diǎn)檢測，依據(jù)角點(diǎn)是局部內(nèi)灰度和梯度變換劇烈的極大點(diǎn)，所以這類算法所應(yīng)用的手段主要是通過計算曲率及梯度來達(dá)到檢測角點(diǎn)的目的。由于它不需要進(jìn)行邊緣提取工作，所以在實(shí)際中得到了廣泛的應(yīng)用。目前國內(nèi)研究角點(diǎn)提取算法重點(diǎn)主要在已有算法的改進(jìn)，如楊莉等基于SUSAN算法提出的RSUSAN (Redefined SUSAN)角點(diǎn)提取算法[9]，使用了更為有效和簡便的計算USAN區(qū)域的方法，提高了計算速度；王建琦等人提出一種改進(jìn)的角點(diǎn)提取方法[10]，該方法是基于MIC算法的改進(jìn)，該算法采用了在方形窗邊界上的線性插值，在插值的基礎(chǔ)上計算出邊緣角，通過它來對角點(diǎn)候選點(diǎn)做進(jìn)一步的篩選；李華等人提出了一種新的基于形態(tài)骨架的快速拐點(diǎn)提取方法[11]，該方法基于物體條件骨架原理，采用改進(jìn)的非對稱開運(yùn)算算子，并利用內(nèi)外骨架分別實(shí)現(xiàn)對物體凸點(diǎn)和凹點(diǎn)的提取，以保證拐點(diǎn)提取的完整性；張坤華等人提出一種利用圖像灰度特征和邊界輪廓點(diǎn)特征相復(fù)合的角點(diǎn)提取方法[12]，克服了單一特征提取角點(diǎn)所帶來的弊病，提高了角點(diǎn)提取的精度。2. 局部不變特征點(diǎn)提取方法局部不變特征點(diǎn)提取方法主要利用目標(biāo)局部區(qū)域的信息來構(gòu)造特征量，由于這些一定數(shù)目的局部區(qū)域可能離散地出現(xiàn)在目標(biāo)的不同位置，當(dāng)對每個區(qū)域獨(dú)立地提取特征時，即使目標(biāo)位于復(fù)雜環(huán)境中或有部分遮擋，通過局部特征提取仍可得到目標(biāo)的部分信息，從而實(shí)現(xiàn)復(fù)雜背景中目標(biāo)的識別與確認(rèn)。由于不用對目標(biāo)進(jìn)行分割或提取輪廓等預(yù)處理，不需要得到目標(biāo)的全部信息，因此與全局的方法相比，其適用面更廣。局部不變特征提取方法的研究已成為了一個非?；钴S的研究方向[13]，出現(xiàn)了大批研究成果，其中部分成果已達(dá)到了實(shí)用階段。局部不變特征提取需要解決兩個問題：一是特征區(qū)域定位，即在哪里提取特征；二是區(qū)域內(nèi)信息描述，即用什么特征量來描述區(qū)域內(nèi)的信息。下面將分析和比較不同方法如何解決這兩個問題。Lowe利用尺度空間性質(zhì)，提出了一種尺度不變關(guān)鍵點(diǎn)(Keypoint)檢測方法[14][15]，以同時在尺度域和空間域取得極值的點(diǎn)作為關(guān)鍵點(diǎn)，并以關(guān)鍵點(diǎn)作為特征區(qū)域的中心，同時，關(guān)鍵點(diǎn)所在的尺度還用以確定特征區(qū)域的大小。這種方法較好地同時解決了特征區(qū)域定位和大小選擇的問題。在每個特征區(qū)域內(nèi)，Lowe以梯度方向的直方圖為基礎(chǔ)構(gòu)造了一種稱為SIFT（Scale Invariant Feature Transform）的局部不變特征提取性能的衡量標(biāo)準(zhǔn)。SURF是由Herbert Bay等2006年提出的另一種有效的特征提取方法[16]，與SIFT一樣不僅可以檢測出圖像的興趣點(diǎn)即特征，同時提供了一種創(chuàng)建具有不變描述器的方法。這樣描述器獨(dú)立地用于識別所找到的興趣點(diǎn)，同時能在尺度變化、旋轉(zhuǎn)、光照及視角變化及出現(xiàn)噪聲情況下進(jìn)行很好地匹配。這種不變性對于諸如需要穩(wěn)定和重復(fù)性特點(diǎn)以用來支持目標(biāo)的識別的移動機(jī)器人這樣的應(yīng)用程序是相當(dāng)重要的。通過研究SURF在處理模糊和旋轉(zhuǎn)的圖像時表現(xiàn)出很強(qiáng)的優(yōu)點(diǎn)，而在視角變化和光照變化上略差一些。當(dāng)相比于SIFT，SURF的速度要更快，但是在圖像出現(xiàn)視角和光照變化上匹配的效果沒有SIFT好。近年來還出現(xiàn)了許多局部不變特征提取方法，如基于視覺顯著性的局部不變特征提取[17]和基于微分幾何測地線概念的方法[18]，后者甚至對非仿射變換造成的幾何形變具有很好的不變性。 特征點(diǎn)匹配研究現(xiàn)狀特征點(diǎn)匹配就是將不同圖像上由同一場景點(diǎn)投影而成的特征點(diǎn)對找出來。由匹配線索不同，現(xiàn)有的匹配算法基本可以分為兩大類：1) 基于窗口的匹配(AreaBased Matching,ABM)，窗口是由待匹配點(diǎn)附近的像素灰度值組成的二維矩陣，其中最常用的是用交叉相關(guān)性來匹配，這是目前大多數(shù)匹配算法的基礎(chǔ)。Rosenholm不使用固定大小的窗口，而是用連接窗(connected window)在全局范圍內(nèi)進(jìn)行匹配)，該方法對于處理重復(fù)紋理具有較好的效果。2) 基于特征的匹配(FeatureBased Matching，F(xiàn)BM)，在匹配前先要抽取邊或區(qū)域等特征。這些特征是圖像內(nèi)容更抽象的描述，在不同的光照下具有更多的不變性。但是特征匹配往往有很高的計算代價。除此之外，各種匹配方法所采用的優(yōu)化算法也不盡相同，有的使用全局優(yōu)化算法，如動態(tài)規(guī)劃法、窮舉法、凸規(guī)劃法和松弛法等；還有的使用一些非全局最優(yōu)算法，如貪婪算法，模擬退火算法和隨機(jī)搜索算法等。以上的大多數(shù)方法都隱含地引入了一些約束，如動態(tài)規(guī)劃法就需要順序不變約束。當(dāng)這些約束不滿足時，相應(yīng)的方法就無法使用。Maciel等使用線性規(guī)劃的方法來解決匹配中產(chǎn)生的歧義問題，這種方法可以得到某種意義上的全局最優(yōu)解，并且由于線性規(guī)劃法已經(jīng)很成熟。因此可以保證算法有較高的效率，但是線性規(guī)劃法需要消耗大量的內(nèi)存并且要預(yù)先估計正確的匹配數(shù)。如何建立特征點(diǎn)之間的對應(yīng)關(guān)系是基于特征點(diǎn)匹配方法的核心研究課題，雖然特征點(diǎn)匹配技術(shù)起步較晚，但是應(yīng)用的迫切和前景的廣泛使它引起了廣大學(xué)者們的極大關(guān)注，在近十幾年里得到了長足的發(fā)展，并出現(xiàn)大量的匹配方法。不同的圖像變換模型又具有不同的匹配方法，如在一些應(yīng)用領(lǐng)域中，根據(jù)已有的先驗(yàn)知識可以直接計算出縮放比例，如在地球資源衛(wèi)星圖像的配準(zhǔn)中，可以直接利用給定圖像的比例信息，而只需要考慮在一些區(qū)域被遮擋的情況下存在的平移與旋轉(zhuǎn)。這時相當(dāng)于提供了一個不變量，即一幅圖像中任意兩個特征點(diǎn)的距離與另一幅圖像對應(yīng)的特征點(diǎn)之間的距離相等。這樣使匹配算法能夠簡化為只考慮有平移、旋轉(zhuǎn)的情況下求解點(diǎn)集之間的對應(yīng)關(guān)系，但在很多實(shí)際應(yīng)用中，由于存在圖像噪聲及視場變換還有不同時間和不同傳感器獲取的圖像等因素，待匹配的兩幅圖像中不可避免出現(xiàn)虛假點(diǎn)、丟失點(diǎn)以及非剛性形變?；谔卣鼽c(diǎn)匹配方法主要分為如下幾類：1)直接基于特征點(diǎn)屬性的匹配方法(基于描述符的匹配方法)。這類方法在提取特征點(diǎn)后，對特征點(diǎn)進(jìn)行不同的描述，用來區(qū)別其它特征點(diǎn)，然后用描述符進(jìn)行匹配。利用特征描述符進(jìn)行匹配的方法是在特征點(diǎn)提取過程中，不僅得到特征點(diǎn)的位置，同時將得到特征點(diǎn)的其他仿射變換下不變的特征點(diǎn)描述。文獻(xiàn)[19]利用顏色直方圖進(jìn)行描述，提出了一種快速的特征點(diǎn)匹配方法。SIFT描述符[15]將特征點(diǎn)周圍的窗口分割成16個的子窗口，然后統(tǒng)計每個子窗口的方向梯度直方圖。將每個子窗口的方向分成8個方向計算。一共具有個子窗口，每個窗口描述是8位的，描述8個方向的梯度的大小值，這樣形成的描述符是維，匹配時只需利用描述符進(jìn)行配對。2)基于特征點(diǎn)幾何結(jié)構(gòu)的匹配方法[20]。這類方法不直接對特征點(diǎn)逐一進(jìn)行匹配，它利用特征點(diǎn)之間相似和穩(wěn)定幾何結(jié)構(gòu)，如邊、三角形等進(jìn)行匹配。近年來還出現(xiàn)了許多特征點(diǎn)匹配方法，如D Skea提出了一個累加器算法[21]，其核心思想是平面點(diǎn)模式匹配的一個框架，該算法對噪聲和缺少點(diǎn)及偽點(diǎn)較為魯棒，但計算復(fù)雜度較大。Sanjay Ranade and AzrielRosenfeld提出松弛法進(jìn)行點(diǎn)匹配[2]，陳志剛等在其基礎(chǔ)上通過構(gòu)建三角形并利用其相似度來定義點(diǎn)特征的匹配度，提出了一種新的具有比例與旋轉(zhuǎn)不變特性的點(diǎn)特征松弛匹配算法[22]。Shihhsu Chang等人利用二維聚類進(jìn)行匹配[23]，張立華等利用不可約矩陣和相對不變量理論提出了幾種點(diǎn)模式匹配新算法[24]，它們可分別用來解決相似變換和仿射變換下具有相同點(diǎn)數(shù)的兩個點(diǎn)模式的匹配問題。Li利用了幾何不變量來進(jìn)行點(diǎn)模式匹配[25]，Spirkovska和Reid利用了高階神經(jīng)網(wǎng)絡(luò)進(jìn)行匹配[26]。基于圖像特征的匹配方法可以克服利用圖像灰度信息進(jìn)行匹配的缺點(diǎn)，由于圖像的特征點(diǎn)比圖像總的像素要少很多，這樣就大大減少了匹配過程的計算量；而且特征點(diǎn)的提取過程可以減少噪聲的影響，對灰度變化，圖像形變以及遮擋等都有較好的適應(yīng)能力。 研究內(nèi)容特征點(diǎn)提取過程中，需要構(gòu)建在多種變換下具有良好不變性的特征點(diǎn)提取算法以獲得具有精確性高，區(qū)分度強(qiáng)的不變性圖像特征，并綜合特征局部結(jié)構(gòu)信息，構(gòu)造特征描述算子。由于時間、視角、環(huán)境的變化、多種傳感器的使用等，使拍攝的圖像不僅受到噪聲的影響，而且存在嚴(yán)重的灰度失真和幾何畸變。在這種條件下，匹配算法如何達(dá)到精度高、匹配正確率高、速度快、魯棒性和抗干擾性強(qiáng)以及并行實(shí)現(xiàn)成為人們追求的目標(biāo)。本文在研究現(xiàn)有的一些特征檢測算法及匹配方法基礎(chǔ)上，以計算機(jī)視覺的不變理論為基礎(chǔ)，本文主要研究內(nèi)容如下所述。1. 圖像不變特征點(diǎn)提取算法研究圖像特征點(diǎn)提取是基于特征點(diǎn)匹配方法的首要步驟，在實(shí)際問題中，圖像可能受到噪聲、背景的干擾，也可能發(fā)生光照、尺度、旋轉(zhuǎn)、仿射等變化，如何選擇合理的圖像特征點(diǎn)，使得這些特征點(diǎn)不僅具有良好的抗噪性能，而且在上述變化下保持不變，直接決定了基于特征點(diǎn)的匹配方法效果。由于后續(xù)匹配方法需要圖像在旋轉(zhuǎn)和尺度變換下仍滿足一定比例的有效點(diǎn)，所以本文需要對旋轉(zhuǎn)和尺度不變特征點(diǎn)的提取進(jìn)行研究。2. 圖像特征點(diǎn)匹配方法研究圖像特征點(diǎn)匹配的目的是在兩幅圖像之間建立盡可能多的匹配點(diǎn)對。它是圖像分析和處理的基本問題。圖像特征點(diǎn)匹配方法目前主要分為兩種，即為基于描述符的特征點(diǎn)匹配方法和基于特征點(diǎn)幾何結(jié)構(gòu)的匹配方法?；诿枋龇钠ヅ浞椒▽τ行c(diǎn)的要求低，適合圖像視角變換、輕微變形情況，但是實(shí)現(xiàn)復(fù)雜，對圖像紋理要就比較高；而基于幾何結(jié)構(gòu)的匹配方法實(shí)現(xiàn)簡單、紋理要求低，但是抗圖像形變、視角變化能力差，算法時間復(fù)雜度比較高。所以本文需要對圖像特征點(diǎn)的匹配方法進(jìn)行研究，探求更有效、性能更好的圖像特征點(diǎn)匹配方法。 論文組織結(jié)構(gòu)本文將圖像特征點(diǎn)的提取方法以及特征點(diǎn)匹配方法作為主要研究對象，針對圖像存在旋轉(zhuǎn)和尺度變化的情況，利用改進(jìn)H/S算法提取圖像中特征點(diǎn)，并在分析比較兩種常用特征點(diǎn)匹配方法基礎(chǔ)上，提出了一種改進(jìn)的相似三角形特征點(diǎn)匹配算法。本文的篇章結(jié)構(gòu)安排如下：第一章為緒論，介紹了圖像特征點(diǎn)、圖像匹配基本概念，相關(guān)領(lǐng)域研究現(xiàn)狀，最后闡述了本文的主要研究工作和篇章結(jié)構(gòu)。 第二章主要比較目前常用的兩種特征點(diǎn)匹配方法，分別介紹Harris角點(diǎn)檢測算法和基于描述符的SIFT算法，并分析兩種方法的優(yōu)缺點(diǎn)和適用場合，第三章主要在分析特征點(diǎn)提取算法的基礎(chǔ)上，著重介紹特征點(diǎn)檢測實(shí)驗(yàn)效果好的Harris算法，針對傳統(tǒng)Harris算法存在的局限性，引入尺度空間理論和特征描述思想，提出改進(jìn)的H/S算法。第四章在前面研究的基礎(chǔ)上，提出一種改進(jìn)的相似三角形特征點(diǎn)匹配方法，改進(jìn)方法將傳統(tǒng)被動的同向相似三角形檢索方法變?yōu)樵趶?fù)數(shù)空間下選擇基線后主動構(gòu)造相似三角形，提高了算法的效率。并利用特征點(diǎn)組成基線向量后得到三角形組形成多個模板在實(shí)物圖中進(jìn)行匹配，提高了三角形匹配算法的實(shí)時性和穩(wěn)定性。最后一章對全文工作進(jìn)行總結(jié)，并提出今后研究的問題與方向。圖像特征點(diǎn)提取及匹配算法研究 第二章 圖像特征點(diǎn)提取算法研究第二章 圖像特征點(diǎn)提取算法研究圖像特征點(diǎn)提取是圖像處理和計算機(jī)視覺的基本技術(shù)，它也是特征點(diǎn)匹配方法的首要步驟。實(shí)際圖像可能受到噪聲、背景的干擾，也可能發(fā)生光照、尺度、旋轉(zhuǎn)、仿射等變化，圖像特征點(diǎn)的選擇合理和特征點(diǎn)提取質(zhì)量，直接決定了特征點(diǎn)匹配方法的效果。本章針對實(shí)際情況的復(fù)雜多樣性，對兩種特征點(diǎn)提取方法(Harris算法和SIFT算法)進(jìn)行分析研究。 Harris特征點(diǎn)提取算法角點(diǎn)作為目前圖像匹配中常用的特征點(diǎn)，它是二維圖像亮度變化劇烈或圖像邊緣曲線上曲率極大值的點(diǎn)，決定了目標(biāo)的輪廓特征，因此被廣泛應(yīng)用于攝像機(jī)標(biāo)定、虛擬場景重建、運(yùn)動估計、圖像配準(zhǔn)等計算機(jī)視覺處理任務(wù)中。角點(diǎn)檢測方法分為基于邊緣的提取方法和基于圖像灰度的提取方法。前者往往需要對圖像邊緣進(jìn)行編碼，這在很大程度上依賴于圖像的分割和邊緣提取，而這兩種操作本身就具有相當(dāng)大的難度和計算量，況且一旦待檢測目標(biāo)局部發(fā)生變化(例如被部分遮擋)，則很可能導(dǎo)致圖像分割和圖像邊緣提取操作的失敗，所以這種方法的適用范圍很??；而基于圖像灰度的方法則避開了上述這些缺陷，它考慮的是像素點(diǎn)鄰域的灰度變化，而不是整個目標(biāo)的邊緣輪廓。它通過計算曲率及梯度來達(dá)到檢測角點(diǎn)的目的。由于它不需要進(jìn)行邊緣提取工作，所以在實(shí)際中得到了廣泛的應(yīng)用。目前在圖像匹配中，常見的基于灰度的角點(diǎn)提取算法主要有Moravec算法，SUSAN算法和Harris算法等。Schmid[27]對Moravec，SUSAN和Harris等基于圖像灰度的角點(diǎn)檢測方法從重復(fù)率和角點(diǎn)周圍的局部區(qū)域所包含的信息量兩個方面進(jìn)行了對比。實(shí)驗(yàn)結(jié)果表明Moravec，SUSAN算法存在較多的誤檢測和漏檢測現(xiàn)象，且對旋轉(zhuǎn)前后的圖像角點(diǎn)檢測不一致，而Harris角點(diǎn)檢測法具有最好的效果。因此本節(jié)主要分析Harris算法。 Harris特征點(diǎn)檢測原理Harris 角點(diǎn)檢測算法是一種基于信號的點(diǎn)特征提取算子，它的思想是在圖像中設(shè)計一個局部檢測窗口，當(dāng)該窗口沿各個方向作微小移動時，考察窗口的平均能量變化，當(dāng)該能量變化值超過設(shè)定的閾值時，就將窗口的中心像素點(diǎn)提取為角點(diǎn)。Harris角點(diǎn)檢測公式為： ()其中，為窗函數(shù)，為圖像灰度的梯度值?？蔀榫匦未盎蚋咚勾?。對于每個小的位移量，檢測公式可雙線性近似表示為： ()其中 ()設(shè)，是矩陣的兩個特征值，則可表示局部自相關(guān)函數(shù)的曲率。實(shí)際運(yùn)用中用來計算角點(diǎn)的響應(yīng)函數(shù)可以寫成： ()其中，當(dāng)某個區(qū)域矩陣的主對角線之和很大時，則表明這是一條邊；當(dāng)矩陣的行列式很大時，則表明這是一條邊或一個角點(diǎn)。 Harris特征點(diǎn)檢測步驟應(yīng)用Harris方法提取圖像中角點(diǎn)的過程可以分為以下幾步：1) 計算圖像像素點(diǎn)在水平和垂直方向上的梯度，以及兩者的乘積，得到M公式()中4個元素的值, 其中，、分別表示在x ,y方向上的一階導(dǎo)數(shù)。2