【正文】 (a) (b) (c) 三角形的旋轉(zhuǎn)和縮放不變性假設(shè)兩點(diǎn)集，其中，之間的最大匹配點(diǎn)子集，且，點(diǎn)匹配的任務(wù)就是找出這些匹配點(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)提取算法。 分情況特征點(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)性能。可見特征點(diǎn)描述符不受圖像光線仿射變化的任何影響。由關(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)。 (a) 沒有明顯的極值點(diǎn) (b) 有多個(gè)極值點(diǎn) (c) 只有單個(gè)極值點(diǎn) 尺度不變檢測(cè)函數(shù)選擇根據(jù)上述原則，選取DOG(DifferenceofGaussians)函數(shù)()，作為獲取特征尺度的函數(shù)。特征點(diǎn)描述符的計(jì)算過程：首先在確定了特征點(diǎn)的尺度基礎(chǔ)上，針對(duì)圍繞著特征點(diǎn)的圖像梯度大小和方向采樣并將其表示出，為了達(dá)到方向的不變性，描述符的坐標(biāo)和梯度方向隨著特征點(diǎn)方向的改變而改變；然后通過關(guān)鍵點(diǎn)的鄰域梯度信息生成特征向量。多尺度理論在多個(gè)尺度上研究物體，從而獲得物體的全面可靠的信息。首先對(duì)于Harris角點(diǎn)檢測(cè)算法來說，它是基于圖像灰度的提取算法，通過計(jì)算曲率及梯度來達(dá)到檢測(cè)角點(diǎn)的目的，特征點(diǎn)的檢測(cè)效率高。(a)原圖特征向量(b)光照變化特征向量(c)圖像光照變化時(shí)匹配結(jié)果 光照變化不變特征提取及匹配圖(a)原圖特征向量(b)添加10%噪聲特征向量(c)圖像添加10%噪聲匹配圖 添加噪聲不變特征提取及匹配圖根據(jù)前文對(duì)SIFT特征點(diǎn)提取算法原理研究，從實(shí)驗(yàn)結(jié)果可以看出該算法提取出的特征點(diǎn)對(duì)圖像的旋轉(zhuǎn)、縮放及光照、噪聲變化時(shí)表現(xiàn)出較強(qiáng)的魯棒性。(a)中提取出149個(gè)特征點(diǎn)，(b)中提取出129個(gè)特征點(diǎn)，(c)中有70個(gè)特征點(diǎn)匹配到。此時(shí)SIFT特征向量已經(jīng)去除了尺度變化、旋轉(zhuǎn)等幾何變形因素的影響，再繼續(xù)將特征向量的長(zhǎng)度歸一化，則可以進(jìn)一步去除光照變化的影響。梯度直方圖的范圍是0～360度，其中每10度一個(gè)柱，總共36個(gè)柱。1) 精確確定極值點(diǎn)位置通過擬和三維二次函數(shù)以精確確定關(guān)鍵點(diǎn)的位置和尺度(達(dá)到亞像素精度)，同時(shí)去除低對(duì)比度的關(guān)鍵點(diǎn)和不穩(wěn)定的邊緣響應(yīng)點(diǎn)(因?yàn)镈oG算子會(huì)產(chǎn)生較強(qiáng)的邊緣響應(yīng))，以增強(qiáng)匹配穩(wěn)定性、提高抗噪聲能力。再將尺度空間中的每組分隔成一整數(shù)的間隔，令k =，所以，每組中的圖像數(shù)必須為s+3個(gè)，極值檢測(cè)才能覆蓋一組中所有圖像，論文中s為2。利用不同尺度的高斯差分核與圖像卷積生成。同時(shí)由于Harris算法采用了偏導(dǎo)來計(jì)算角點(diǎn)函數(shù)，雖然經(jīng)過高斯濾波，但對(duì)噪聲仍比較敏感。(a) 原圖像(b) 添加10%高斯噪聲圖像 圖像添加噪聲時(shí)角點(diǎn)提取結(jié)果圖4. 設(shè)置不同閾值時(shí)角點(diǎn)不變性由前文針對(duì)Harris算法提取角點(diǎn)步驟可知，設(shè)置閾值大小不同時(shí)得到的角點(diǎn)數(shù)目也隨之改變。5) 設(shè)定閾值，選取一定量的角點(diǎn)。可為矩形窗或高斯窗。它通過計(jì)算曲率及梯度來達(dá)到檢測(cè)角點(diǎn)的目的。并利用特征點(diǎn)組成基線向量后得到三角形組形成多個(gè)模板在實(shí)物圖中進(jìn)行匹配，提高了三角形匹配算法的實(shí)時(shí)性和穩(wěn)定性。它是圖像分析和處理的基本問題。基于圖像特征的匹配方法可以克服利用圖像灰度信息進(jìn)行匹配的缺點(diǎn)，由于圖像的特征點(diǎn)比圖像總的像素要少很多，這樣就大大減少了匹配過程的計(jì)算量；而且特征點(diǎn)的提取過程可以減少噪聲的影響，對(duì)灰度變化，圖像形變以及遮擋等都有較好的適應(yīng)能力。將每個(gè)子窗口的方向分成8個(gè)方向計(jì)算。不同的圖像變換模型又具有不同的匹配方法，如在一些應(yīng)用領(lǐng)域中，根據(jù)已有的先驗(yàn)知識(shí)可以直接計(jì)算出縮放比例，如在地球資源衛(wèi)星圖像的配準(zhǔn)中，可以直接利用給定圖像的比例信息，而只需要考慮在一些區(qū)域被遮擋的情況下存在的平移與旋轉(zhuǎn)。這些特征是圖像內(nèi)容更抽象的描述，在不同的光照下具有更多的不變性。這種不變性對(duì)于諸如需要穩(wěn)定和重復(fù)性特點(diǎn)以用來支持目標(biāo)的識(shí)別的移動(dòng)機(jī)器人這樣的應(yīng)用程序是相當(dāng)重要的。局部不變特征提取方法的研究已成為了一個(gè)非?；钴S的研究方向[13]，出現(xiàn)了大批研究成果，其中部分成果已達(dá)到了實(shí)用階段?；谶吘壧崛〉慕屈c(diǎn)檢測(cè)算法的基本思想是：角點(diǎn)是一種邊緣上的點(diǎn)，它是一種特殊的邊界點(diǎn)，即兩條以上邊界的交點(diǎn)。芬蘭的Oulu大學(xué)機(jī)器視覺小組于2004年開始進(jìn)行幾何不變性方面的研究，提出了一種具有完全仿射不變性的特征提取方法，并用于目標(biāo)識(shí)別與配準(zhǔn)。 研究現(xiàn)狀綜述 特征點(diǎn)提取研究現(xiàn)狀在實(shí)際問題中圖像可能受到噪聲、背景的干擾，也可能發(fā)生平移、尺度、視角、光照等變化，如何選擇合理的特征和描述算子，使得這些特征不僅具有良好的表征性能，而且在上述因素變化下保持相對(duì)不變(即不變性)，直接決定了基于特征點(diǎn)的圖像匹配效果。目前已有許多有關(guān)此類問題的如Sanjay Ranade等提出的松弛算法[2]、Zsolt Mikl243。近幾年在許多領(lǐng)域中，都對(duì)圖像配準(zhǔn)進(jìn)行了大量的研究，比較有代表的有：模式識(shí)別、自動(dòng)導(dǎo)航、遙感領(lǐng)域、醫(yī)學(xué)診斷、計(jì)算機(jī)視覺等。本文提出了一種新的特征點(diǎn)檢測(cè)算法，并根據(jù)三角形相似原理，提出一種改進(jìn)特征點(diǎn)匹配方法。傳統(tǒng)的三角形相似匹配方法雖然實(shí)現(xiàn)簡(jiǎn)單，魯棒性好，但時(shí)間復(fù)雜度高，針對(duì)此局限性，本文提出了一種改進(jìn)三角形匹配方法，將傳統(tǒng)方法被動(dòng)搜索相似三角形變?yōu)樵趶?fù)數(shù)空間下選擇基線后主動(dòng)構(gòu)造相似三角形，并利用特征點(diǎn)組成基線向量對(duì)應(yīng)三角形組得到多個(gè)模板在實(shí)物圖中匹配，提高了改進(jìn)算法的實(shí)時(shí)性和穩(wěn)定性?；诨叶鹊钠ヅ渚褪侵鹣袼氐匕岩粋€(gè)以一定大小的實(shí)時(shí)圖像窗口的灰度矩陣與實(shí)際圖像的所有可能的窗口灰度矩陣按某種相似性度量方法進(jìn)行搜索比較的匹配方法。特征提取方法一般包含兩個(gè)階段：一是對(duì)圖像進(jìn)行分割，提取目標(biāo)區(qū)域或其邊界，抽取目標(biāo)的基本特征，如灰度、紋理、形狀描述。這些研究主要集中于以下幾方面：1) 不變特征的選取，如圖像的點(diǎn)、線、輪廓，像素點(diǎn)的強(qiáng)度、曲率、矩、特征向量等。目前在特征點(diǎn)提取方面，基于角點(diǎn)、局部不變特征點(diǎn)提取研究得到廣泛關(guān)注。直接基于圖像灰度的角點(diǎn)檢測(cè)，依據(jù)角點(diǎn)是局部?jī)?nèi)灰度和梯度變換劇烈的極大點(diǎn)，所以這類算法所應(yīng)用的手段主要是通過計(jì)算曲率及梯度來達(dá)到檢測(cè)角點(diǎn)的目的。Lowe利用尺度空間性質(zhì)，提出了一種尺度不變關(guān)鍵點(diǎn)(Keypoint)檢測(cè)方法[14][15]，以同時(shí)在尺度域和空間域取得極值的點(diǎn)作為關(guān)鍵點(diǎn)，并以關(guān)鍵點(diǎn)作為特征區(qū)域的中心，同時(shí)，關(guān)鍵點(diǎn)所在的尺度還用以確定特征區(qū)域的大小。近年來還出現(xiàn)了許多局部不變特征提取方法，如基于視覺顯著性的局部不變特征提取[17]和基于微分幾何測(cè)地線概念的方法[18]，后者甚至對(duì)非仿射變換造成的幾何形變具有很好的不變性。以上的大多數(shù)方法都隱含地引入了一些約束，如動(dòng)態(tài)規(guī)劃法就需要順序不變約束。基于特征點(diǎn)匹配方法主要分為如下幾類：1)直接基于特征點(diǎn)屬性的匹配方法(基于描述符的匹配方法)。這類方法不直接對(duì)特征點(diǎn)逐一進(jìn)行匹配，它利用特征點(diǎn)之間相似和穩(wěn)定幾何結(jié)構(gòu)，如邊、三角形等進(jìn)行匹配。在這種條件下，匹配算法如何達(dá)到精度高、匹配正確率高、速度快、魯棒性和抗干擾性強(qiáng)以及并行實(shí)現(xiàn)成為人們追求的目標(biāo)。所以本文需要對(duì)圖像特征點(diǎn)的匹配方法進(jìn)行研究，探求更有效、性能更好的圖像特征點(diǎn)匹配方法。實(shí)際圖像可能受到噪聲、背景的干擾，也可能發(fā)生光照、尺度、旋轉(zhuǎn)、仿射等變化，圖像特征點(diǎn)的選擇合理和特征點(diǎn)提取質(zhì)量，直接決定了特征點(diǎn)匹配方法的效果。Schmid[27]對(duì)Moravec，SUSAN和Harris等基于圖像灰度的角點(diǎn)檢測(cè)方法從重復(fù)率和角點(diǎn)周圍的局部區(qū)域所包含的信息量?jī)蓚€(gè)方面進(jìn)行了對(duì)比。 Harris特征點(diǎn)檢測(cè)步驟應(yīng)用Harris方法提取圖像中角點(diǎn)的過程可以分為以下幾步：1) 計(jì)算圖像像素點(diǎn)在水平和垂直方向上的梯度，以及兩者的乘積，得到M公式()中4個(gè)元素的值, 其中，、分別表示在x ,y方向上的一階導(dǎo)數(shù)。1. 旋轉(zhuǎn)不變性(a)為原圖角點(diǎn)提取結(jié)果，(b)為經(jīng)過逆時(shí)針旋轉(zhuǎn)30度后的圖像角點(diǎn)提取結(jié)果。因此在圖像配準(zhǔn)中通常采用這種算法來提取特征點(diǎn)。SIFT特征點(diǎn)提取方法首先對(duì)圖像進(jìn)行預(yù)處理，通過采用高斯差分金字塔分層結(jié)構(gòu)提取出圖像中的極值點(diǎn)作為侯選，并對(duì)這些侯選特征點(diǎn)進(jìn)一步篩選掉其中低對(duì)比度和處于邊緣的點(diǎn)，最終提取出穩(wěn)定的特征點(diǎn)。采用高斯函數(shù)先對(duì)圖像進(jìn)行卷積運(yùn)算，以達(dá)到預(yù)處理的目的。第三組和第四組中圖像層的濾波因子也和上面的方法相同，依次增加濾波因子。D的主曲率和H的特征值成正比，令為最大特征值，為最小的特征。一個(gè)關(guān)鍵點(diǎn)可能會(huì)被指定具有多個(gè)方向(一個(gè)主方向，一個(gè)以上輔方向)，這可以增強(qiáng)匹配的魯棒性。在安裝好Visual C++的Windows操作系統(tǒng)下運(yùn)行安裝文件完成安裝過程。(a)原圖特征向量(d)原圖局部(b)旋轉(zhuǎn)40度特征向量(c)圖像旋轉(zhuǎn)時(shí)匹配結(jié)果(e)旋轉(zhuǎn)圖局部 局部旋轉(zhuǎn)不變特征提取及匹配圖2. 一定范圍內(nèi)的尺度不變性(a)、(b)為原圖及尺度變化時(shí)特征向量提取圖，(c)，(a)中提取出129個(gè)特征點(diǎn)，(b)提取出99個(gè)特征點(diǎn)，(c)中有29個(gè)特征點(diǎn)匹配到，由匹配結(jié)果可以看出，在圖像尺度發(fā)生變化時(shí)，兩幅圖像提取得到得不變特征點(diǎn)數(shù)量較少，表明其在尺度變化時(shí)僅能在較小范圍內(nèi)得到不變特征點(diǎn)。圖像特征點(diǎn)提取及匹配算法研究 第三章 H/S特征點(diǎn)提取算法改進(jìn)第三章 改進(jìn)的H/S特征點(diǎn)提取算法經(jīng)過前面章節(jié)的分析，不同的特征點(diǎn)提取算法具有各自的優(yōu)缺點(diǎn)，單一的方法在具體的應(yīng)用中，具有一定的局限性。所以為圖像中提取穩(wěn)定特征點(diǎn)，首先利用Harris特征點(diǎn)提取算法初步從圖像中提取粗特征點(diǎn)，然后通過多尺度高斯差分剔除部分抗尺度性較差的特征點(diǎn)，在此基礎(chǔ)上結(jié)合描述符信息得到穩(wěn)定特征點(diǎn)。首先構(gòu)建圖像的尺度空間函數(shù)。算法流程圖如下。 DOG函數(shù)圖像 尺度空間下的Harris角點(diǎn)檢測(cè)示意圖 特征點(diǎn)描述在根據(jù)傳統(tǒng)Harris算法初步獲得圖像中特征點(diǎn)的基本信息的基礎(chǔ)上，結(jié)合多尺度空間極值求解理論剔除部分偽特征點(diǎn)，并獲得圖像特征點(diǎn)的尺度信息，在此基礎(chǔ)上，根據(jù)特征點(diǎn)的尺度、方向、位置等信息，為每個(gè)特征點(diǎn)建立一個(gè)描述符，特征點(diǎn)在提取時(shí)需要給特征點(diǎn)分配一個(gè)主方向，主要目的是通過主方向旋轉(zhuǎn)特征點(diǎn)局部區(qū)域 ,確保特征描述符的旋轉(zhuǎn)不變性。每個(gè)區(qū)域中有8個(gè)方向箭頭，箭頭的長(zhǎng)度與梯度值大小相對(duì)應(yīng)，實(shí)驗(yàn)證明最好的描述符應(yīng)為44的柱狀矩陣，矩陣中每個(gè)元素占用8個(gè)方向位，那么每個(gè)特征點(diǎn)的描述符就是一個(gè)448=128維向量。但是在本章所提出的H/S算法中，首先已經(jīng)通過Harris特征點(diǎn)提取算法獲得了圖像中的粗特征點(diǎn)，并且在多尺度理論的應(yīng)用下得到了抗尺度變化的特征點(diǎn)，此時(shí)特征點(diǎn)的信息量差異已經(jīng)比較大，因此在H/S特征點(diǎn)提取算法中，通過在關(guān)鍵點(diǎn)周圍建立44的窗口，然后在每個(gè)窗口中確定一個(gè)種子點(diǎn)，計(jì)算該種子點(diǎn)分別在，和共4個(gè)方向的梯度方向直方圖，繪制每個(gè)梯度方向的累加值，這樣對(duì)于一個(gè)關(guān)鍵點(diǎn)產(chǎn)生16個(gè)數(shù)據(jù)，即最終形成16維的H/S特征向量，此時(shí)獲得的H/S特征向量不僅提供了特征點(diǎn)的抗旋轉(zhuǎn)、抗噪聲性能，進(jìn)一步將特征向量歸一化可以獲得對(duì)光照變化的有效性。(a)Harris算法提取結(jié)果(b)H/S算法提取結(jié)果(c)Harris算法提取結(jié)果(d)H/S算法提取結(jié)果 圖像尺度變化前后角點(diǎn)檢測(cè)比較(原圖像大小的2倍) H/S算法與Harris算法角點(diǎn)檢測(cè)點(diǎn)重復(fù)率比較比較尺度點(diǎn)重復(fù)率，改進(jìn)后的H/S算法提取的角點(diǎn)一致性效果較好。同時(shí)采用H/S特征點(diǎn)提取算法將為本文后續(xù)提出改進(jìn)的特征點(diǎn)匹配算法的實(shí)現(xiàn)提供穩(wěn)定的不變特征點(diǎn)。這樣，在嚴(yán)格的情況下，真實(shí)匹配的點(diǎn)對(duì)之間的置信度會(huì)大于或等于，但由于出格點(diǎn)的存在，進(jìn)行同向相似三角形檢實(shí)際算法過程中將置信度大于某一閾值的兩點(diǎn)作為最終匹配點(diǎn)。兩個(gè)圖像中的三角形在三角空間中的對(duì)應(yīng)點(diǎn)之間的距離在范圍內(nèi)，就認(rèn)為它們相互匹配，即為一個(gè)三角形匹配對(duì)。通過加權(quán)后，權(quán)值矩陣中數(shù)值大的元素對(duì)應(yīng)著匹配點(diǎn)。規(guī)范化使得參數(shù)比例穩(wěn)定，相似三角形具有相似的參數(shù)值。且未利用其他信息對(duì)一些偽匹配三角形進(jìn)行剔除，造成相似三角形對(duì)數(shù)過多，容易造成誤匹配。本章改進(jìn)傳統(tǒng)三角形的的被動(dòng)搜索為主動(dòng)搜索，即在實(shí)物圖中找到對(duì)應(yīng)于模板圖像中的基線后運(yùn)用復(fù)數(shù)空間理論，構(gòu)造條基線，在實(shí)物圖中主動(dòng)找到以該基線為準(zhǔn)的三角形組，然后判斷該三角形組與模板圖像的三角形組是否相似，從而很大程度上減少了檢索三角形的數(shù)量，使算法時(shí)間復(fù)雜度由降為。設(shè)實(shí)物圖像中提取出個(gè)特征點(diǎn)，傳統(tǒng)的同向相似三角形檢索需要對(duì)個(gè)點(diǎn)組成的個(gè)三角形進(jìn)行同向相似性判斷，三角形相似性判斷方法目前已經(jīng)相當(dāng)成熟。 不同向的兩相似三角形很顯然傳統(tǒng)的同向相似三角形檢索時(shí)間復(fù)雜度為，且過程涉及到大量的除法和比較運(yùn)算。，同向相似三角形檢索只需對(duì)條對(duì)應(yīng)邊求出對(duì)應(yīng)點(diǎn)，然后判斷點(diǎn)是否為特征點(diǎn)即可。根據(jù)復(fù)數(shù)與向量一一對(duì)應(yīng)關(guān)系及復(fù)數(shù)相乘的幾何意義，向量對(duì)應(yīng)的復(fù)數(shù)可由向量對(duì)應(yīng)的復(fù)數(shù)乘以復(fù)數(shù)計(jì)算出來，由此點(diǎn)坐標(biāo)被確定。在得到以為基線構(gòu)造的頂點(diǎn)的幾何坐標(biāo)位置后，判斷點(diǎn)是否為實(shí)物圖像中特征點(diǎn)，若為特征點(diǎn)，進(jìn)一步結(jié)合點(diǎn)特征向量信息，判斷該特征點(diǎn)與模板圖像中對(duì)應(yīng)位置點(diǎn)的描述符信息是否相似，若這兩點(diǎn)特征向量相似度高，則認(rèn)為找到一個(gè)匹配三角形，同理構(gòu)造以為基線組成的所有三角形，若三角形組頂點(diǎn)滿足要求的點(diǎn)達(dá)到一定閾值，則認(rèn)為在實(shí)物圖像的該位置找到模板圖像，提高了檢索方法針對(duì)性和有效性。實(shí)驗(yàn)中提取出角點(diǎn)用十字劃線標(biāo)識(shí)，并用矩形框標(biāo)識(shí)出實(shí)物圖像中識(shí)別出的