【正文】 行匹配，這樣圖像就得滿足足夠多的紋理，否則構造出的特征向量區(qū)別性就不是太大，容易造成誤匹配，極限情況如指紋圖像的匹配，星圖識別等這類圖像特征點周圍根本沒有什么紋理，這時SIFT算法就完全失效了。1. 多尺度理論多尺度理論認為事物的存在都是以尺度范圍為前提的。多尺度下提取圖像的特征點，將尺度看作是附加在圖像空間上的一維連續(xù)變化的坐標。其中高斯核()具有平移、旋轉、尺度不變性，且被證明是實現(xiàn)尺度變換的唯一線性核[15]，利用高斯核的一階偏導數將Harris角點算法變換成尺度空間的表示。算法步驟：首先利用單尺度Harris特征點提取算法初步得到圖像中的粗特征點，以保證特征點提取的高效；然后結合多尺度空間理論，進行高斯差分算子得到抗尺度變化的特征點，剔除初步粗特征點中對于尺度變化時新產生或者發(fā)生偏移的特征點；再根據描述符方法思想，利用計算起來比較簡單的信息，對剔除掉隨尺度變化的特征點后剩余特征點進行描述，以使穩(wěn)定的特征點信息更準確。下一步將驗證在某一尺度水平上檢測出的角點是否取得極值，從而得到具有尺度不變性的特征點。在每一個尺度水平上提取出在鄰域內的局部極值點，然后選取大于給定閾值的極值點作為候選點，最后驗證這些點是否在DOG算子尺度空間上獲得極值，若能獲得極值，則是特征點；否則舍棄。在獲得特征點的以上信息后，通過選擇一個具有參數的高斯權重函數為每個樣本特征點梯度值賦一個權重，其中等于描述符窗口寬度的一半，(b)所示是SIFT生成的特征點描述符。這種鄰域方向的信息聯(lián)合的思想增強了算法抗噪聲的能力，同時對于含有定位誤差的特征匹配也提供了較好的容錯性。當圖像對比度改變時，每個像素值會被乘以一個常量，同時梯度值也被乘以相同的常量，因此對比度改變產生的影響就會通過向量的標準化而被取消掉。因此利用了128維的向量信息以提高其抗旋轉及抗噪聲等性能。H/S特征點提取算法結合了Harris算法高效檢測特征點以及SIFT算法抗尺度和抗噪聲魯棒性強的優(yōu)點，使圖像特征點的檢測更為有效、穩(wěn)定。1. 尺度不變性將H/S特征點提取算法與傳統(tǒng)的Harris角點檢測算法，分別對尺度變化前后的圖像進行角點檢測。(a)Harris原圖提取結果(b)H/S算法原圖提取結果(c) Harris噪聲圖提取結果(d)H/S算法噪聲圖提取結果 圖像噪聲變化前后角點檢測比較噪聲添加率 H/S算法與Harris算法角點檢測點重復率比較比較點重復率，改進后的H/S算法在圖像增加噪聲時提取的角點一致性效果較好。本章將尺度空間理論和特征點描述符的思想應用到傳統(tǒng)的Harris角點檢測的方法中，實現(xiàn)了具有平移、旋轉、抗尺度和抗噪聲變化的H/S特征點提取算法。 三角形匹配原理三角形相似的匹配方法[28]基本思想是：一個三角形的內角不但對于平移和旋轉具有不變性，而且對于三角形的縮放也具有不變性 ()?；诖嗽?，將相似兩三角形對應點的置信度加一。定義 ：如果一個三角形對中的兩個三角形的三個頂點對應匹配，則稱它們?yōu)橐粋€匹配三角形對。由上面的定義可知，三角形映射到三角空間中是被限制在一個三角形區(qū)域中()，但是對于相似三角形，無論它如何平移、旋轉或縮放，它總是投影在空間的同一點。確定匹配點。每一組匹配上的三角形，對于構成三角形的每個點，其在權值矩陣中的元素的權值被加1。一種方法是給權值應用一個閾值，通過控制這個閾值的大小來控制隨機誤匹配點的數目及真正點匹配對的數目。規(guī)范化可能是一組中所有三角形關于這個屬性的平均值。4. 匹配流程1) 由兩幅圖像所有特征點任意組合成的三角形集合，分別記為A、B；2) 構建權值矩陣M。而且判定方法還需牽涉到較為復雜的除法和比較操作。下面進行改進相似三角形匹配方法的具體研究與實現(xiàn)。 匹配算法流程 三角形選取方案研究1. 改進選取三角形思路根據傳統(tǒng)的基于相似三角形匹配方法，模板圖像中個特征點，任意可組成個三角形，然后逐個使用每個三角形在實物圖像中尋找相似三角形，是一種被動檢索方式，顯然這種方法基數非常大，所需要比較的三角形個數很多，時間復雜度也就相應的增加。三角空間有一個特點，如果兩點靠得很近，也就是說有兩個點的坐標距離相當小，將在三角空間的某個角出現(xiàn)大量的點。 相似三角形檢索方法改進由于同向相似三角形檢索首先需要對三角形進行相似性判斷，然后進行同向性判斷。則點、與點、同向排列的充要條件是向量和的向量積與向量和的向量積同向。不能由旋轉得到。 給定邊與的邊對應，那么將存在唯一的點使與同向相似。這樣就得到兩個與相似的三角形，這兩個三角形反向相似，其中有且僅有一個三角形與同向相似，且對應的交點即為要求的點，證畢。在復數向量空間中，(a)，由向量與向量唯一確定。假設中向量到向量的角度為，與的比值為，可知只需中向量到向量的角度為，與的比值為，則與同向相似。方法通過選取模板圖像中三角形子模板對實物圖像特征點進行同向相似三角形檢索，來實現(xiàn)模板圖像的粗匹配，可以在很大程度上減少傳統(tǒng)圖像匹配方法的搜索空間。在復數向量空間中，從特征點集中結合特征點的描述符信息，根據與模板圖像對應特征向量的屬性相似度，從實物圖中選擇基線，以其余所有的特征點與構成三角形組，具體方法以構造為例說明如下()：由模版圖對應的復數與對應的復數相除得到旋轉因子，運用旋轉因子找出點，使與所確定的三角形與模板為同向相似三角形。同時結合了H/S算法提取出圖像中的特征點具有的描述符信息，更合理的選擇實物圖中的向量作為基線，減少搜索三角形的數量，提高了算法的效率，在復數空間下得到對應基線的三角形的幾何位置時，不僅判斷該點的位置是否為特征點，并利用該特征點與對應模板圖中的相似三角形的頂點的特征向量的相似性，剔除部分偽匹配三角形，使算法的準確性得到進一步提高。 實驗結果與分析實驗實現(xiàn)改進的相似三角形特征點匹配算法，驗證其在圖像存在旋轉、縮放、噪聲以及復雜背景下物體識別的準確性及算法效率。(a)模板圖(b)實物圖 模板圖像存在旋轉、縮放時匹配結果圖2. 存在噪聲圖像匹配。改進算法繼承了傳統(tǒng)相似三角形匹配算法抗旋轉和縮放的優(yōu)點，將傳統(tǒng)被動同向相似三角形檢索方法變?yōu)樵趶蛿悼臻g下選擇基線后主動構造相似三角形，同時在選擇基線及進行相似三角形的判斷時利用了特征點的描述符信息，提高了算法效率。(a)模板圖(b)添加噪聲圖 圖像存在噪聲時匹配結果圖3. 背景較復雜時圖像匹配使用GoogleEarth上截得的搖感圖像圖像匹配，(a)模板圖像經過90度旋轉，并存在一定尺度放大，結果顯示該方法準確的在實物圖中找到相應模板圖像，體現(xiàn)該算法在復雜背景下識別目標物體的實用性。實驗使用VC++，首先利用H/S特征點提取算法提取出圖像中特征點，得到待匹配的兩幅圖像對應特征點集。否則從中選取一個未處理的向量，與模板中向量對應，根據旋轉因子，計算出向量，確定點的坐標；3) 判斷實物圖像中周邊很小的范圍內是否有一個特征點。A(a)模板圖像三角形 (b)實物圖像中三角形 相似三角形本章改進算法是在現(xiàn)有相似三角形匹配算法的基礎上，通過選取模板圖像中特征點組成基線的相應三角形組后，對實物圖像相應特征點組成的基線進行對應的相似三角形檢索來實現(xiàn)模板圖像的定位，從而很大程度上減少了傳統(tǒng)模板匹配方法的搜索空間，提高了搜索的效率。所以用單個三角形模板進行匹配是不可靠的，在本文提出的改進方法中將考慮用多個三角形模板進行匹配，具體是通過使用基線的三角形組形成多模板，使改進方法可靠性得到改善，并且利用特征點的描述符信息，更合理的選擇基線，并可以剔除部分偽匹配三角形。稱復數為旋轉因子，可由向量對應的復數與向量對應的復數相除得到。點存在且唯一。對點是否為特征點的判斷，只需在保存實物圖像特征點的二維布爾值數組中檢查點對應的值是否為真即可，算法復雜度為。邊的長度為，根據三角形相似原理可知：邊的長度與邊的長度可由下式求出：()分別以點、為圓心，、為半徑做圓、。本文將采用一種主動的相似三角形檢索方法，時間復雜度僅為。易知同向的充要條件就是滿足式()。下面給出兩三角形同向的判斷條件及證明。另一方面，給定三角空間一個固定的容錯量，那么這些靠的很近的點對，將大量地被篩選為相似匹配(或非相似匹配)。2. 奇異三角形的去除奇異三角形是指存在夾角近似于或的三角形()。：在選取圖像中的一條基線后，以與以點集中其余特征點為頂點組成對應于的三角形組，則稱該三角形組為基線的三角形組。再者當模板點集中的一個點與目標點集中多個點匹配這種情況出現(xiàn)時，特征點的對應關系就找不出來了。4) 經過上面層層篩選，進而得到最終的匹配點。這個思想在于運用這些參數可以限制一些匹配，比如比較大的三角形僅僅和比較大的三角形匹配。3. 減少誤匹配點擴展三角空間可以減少誤匹配。權值矩陣由兩組點對組成。換句話說，A組的一個點作為很多匹配的三角形的一部分，而這些三角形在B組有著對應點。2． 三角形匹配窮舉方法就是用A組中的每一個三角形去和B組中的每一個三角形進行比較，而每一次的比較都涉及到笛卡爾距離的計算。通過定義可知,并且，同時。算法過程具體描述如下：1． 三角形的建立及表示：從待匹配的兩幅圖像中提取的角點集和中任意三點，依次連接這三點組成的三角形就稱之為三角形。(a) (b) (c) 三角形的旋轉和縮放不變性假設兩點集，其中，之間的最大匹配點子集，且，點匹配的任務就是找出這些匹配點集。圖像特征點提取及匹配算法研究 第四章 基于H/S的特征點匹配方法第四章 基于H/S的特征點匹配方法本章在使用改進的H/S特征點提取算法檢測圖像的特征點基礎上，結合特征點間的幾何結構，根據三角形相似性原理提出一種改進的相似三角形匹配方法，大大降低了傳統(tǒng)相似三角形匹配算法的時間復雜性，并提高了算法的可靠性和準確性。 本章小結本章根據Harris特征點提取算法提取特征點速度快、效率高的優(yōu)點，結合局部不變特征點SIFT提取算法尺度不變性和抗噪性強的優(yōu)點，提出了一種新的H/S特征點提取算法。多尺度空間下的Harris角點檢測方法獲取了多個尺度下的角點信息，減小了閾值對角點提取的制約，同時多尺度空間下H/S角點檢測實現(xiàn)了小尺度下的精確定位和大尺度下的去偽存真，算法尺度不變性得到很大改善。 分情況特征點提取結果分析實驗實現(xiàn)H/S特征點提取算法，測試其在圖像存尺度變化、噪聲等情況下的點重復率，驗證其對于傳統(tǒng)Harris算法尺度不變性和抗噪性的改進性能。H/S特征向量的構造過程使用了16維的梯度信息，與SIFT特征向量的128維相比，極大的提高了特征向量的構造效率，同時由于H/S對于特征向量的構造是在獲得抗尺度變化的特征點基礎上，因此構造特征向量的數量也大為降低?？梢娞卣鼽c描述符不受圖像光線仿射變化的任何影響。最后，特征點描述符要作一些改動以減少光線變化時的影響。由關鍵點的鄰域梯度信息生成特征向量，以關鍵點為中心取88的窗口，(a)的中央黑點為當前關鍵點的位置，每一個小格代表關鍵點鄰域所在尺度空間的一個像素，箭頭方向代表該像素的梯度方向，箭頭長度代表梯度模值，圖中的圓環(huán)代表高斯加權的范圍(越靠近關鍵點的像素梯度方向信息貢獻越大)，然后在每44的小塊上計算8個方向的梯度方向直方圖，繪制每個梯度方向的累加值即可形成一個種子點。 () ()式()、()為處梯度的模值和方向公式。 (a) 沒有明顯的極值點 (b) 有多個極值點 (c) 只有單個極值點 尺度不變檢測函數選擇根據上述原則，選取DOG(DifferenceofGaussians)函數()，作為獲取特征尺度的函數。 算法流程圖 H/S算法實現(xiàn) 多尺度特征點檢測為了獲取Harris算法的尺度空間表示，首先計算圖像上某點在和方向上的偏導，然后與標準偏差為(其中：為一常量，1)的高斯核的微分進行卷積：()()其中，=為尺度參數，=為微分尺度，為高斯函數。特征點描述符的計算過程：首先在確定了特征點的尺度基礎上，針對圍繞著特征點的圖像梯度大小和方向采樣并將其表示出，為了達到方向的不變性，描述符的坐標和梯度方向隨著特征點方向的改變而改變；然后通過關鍵點的鄰域梯度信息生成特征向量。Koenderink和Lindeberg(1994)[14]研究發(fā)現(xiàn)高斯函數是唯一的尺度空間內核函數。多尺度理論在多個尺度上研究物體，從而獲得物體的全面可靠的信息。 H/S算法結合方案研究首先傳統(tǒng)的Harris特征點提取算法是在單一尺度下進行特征點的檢測，當尺度變化時，可能檢測出新的角點，或者老的角點發(fā)生移位或消失，這樣使得有效點的比例將存在極大的降低，不利于后續(xù)的特征點匹配，所以需要在Harris算法初步得到單一尺度下特征點后，引入SIFT檢測特征點第一個步驟中的尺度空間極值檢測的思想，使傳統(tǒng)Harris特征點提取算法得到的抗尺度變化的有效的特征點數目能夠提高，再在此基礎上結合SIFT特征點描述符的方法，使結合后的提取算法更穩(wěn)定、快速、有效。首先對于Harris角點檢測算法來說，它是基于圖像灰度的提取算法，通過計算曲率及梯度來達到檢測角點的目的，特征點的檢測效率高。比較分析Harris角點檢測算法和SIFT特征點提取算法，揚長避短，對它們進行有效的結合，使特征點的提取獲得更好的效果。(a)原圖特征向量(b)光照變化特征向量(c)圖像光照變化時匹配結果 光照變化不變特征提取及匹配圖(a)原圖特征向量(b)添加10%噪聲特征向量(c)圖像添加10%噪聲匹配圖 添加噪聲不變特征提取及匹配圖根據前文對SIFT特征點提取算法原理研究，從實驗結果可以看出該算法提取出的特征點對圖像的旋轉、縮放及光照、噪聲