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