【正文】 (a)為在模板圖，(b)為將實(shí)物圖增加噪聲后得到的匹配結(jié)果，實(shí)驗(yàn)結(jié)果表明在實(shí)物圖受噪聲干擾情況下，該算法仍能準(zhǔn)確找到發(fā)生旋轉(zhuǎn)、縮放情況的模板圖像，同時也驗(yàn)證了改進(jìn)H/S算法提取角點(diǎn)特征點(diǎn)的有效性。改進(jìn)的相似三角形匹配方法步驟如下：1) 模板圖像特征點(diǎn)構(gòu)造點(diǎn)集，以點(diǎn)集組成個不同的向量作為基線，選擇未處理的基線，將模板三角形轉(zhuǎn)到復(fù)數(shù)向量空間中，通過向量和向量，計算出旋轉(zhuǎn)因子；2) 實(shí)物圖像特征點(diǎn)構(gòu)造點(diǎn)集，以點(diǎn)集組成個不同的向量，結(jié)合H/S算法提取得到特征點(diǎn)的描述符信息，選取與模板圖像基線描述符信息相似的向量作為基線，如果個向量都處理完，則轉(zhuǎn)步驟5。但當(dāng)模板三角形特征點(diǎn)中含有出格點(diǎn)時，則檢索出的匹配三角形集合中就不會含有同名匹配三角形，從而得不到準(zhǔn)確的匹配位置。(b)，假設(shè)其與向量對應(yīng)，則算法只要找出點(diǎn)，使向量與向量所確定的與模板為同向相似三角形即可。證明：假設(shè)對應(yīng)邊長分別為。() ()其中：,分別是三個坐標(biāo)軸上的單位向量。這些三角形很難進(jìn)行相似判定。：選取圖像點(diǎn)集中任意兩個特征點(diǎn)、則定義向量為圖像中的一條基線。假設(shè)A、B分別有m和n個點(diǎn)，表示匹配相似三角形對中出現(xiàn)的次數(shù)，通過設(shè)定閾值確定三角形匹配對；3) 減少誤匹配。估計這些數(shù)目是很難的，需要依靠許多參數(shù)來完成，比如參與匹配的點(diǎn)的個數(shù)，數(shù)組中數(shù)據(jù)排序程度等。指派兩組點(diǎn)模式之間候選點(diǎn)的匹配是基于這樣的思想：當(dāng)存在很多個點(diǎn)時，將會在包含對應(yīng)點(diǎn)的三角形之間出現(xiàn)過剩的匹配。三角形具有旋轉(zhuǎn)、平移、伸縮變化不變性的特點(diǎn)，每一個三角形包含兩個獨(dú)立的不變的形狀參數(shù)，參數(shù)的表示方法有很多種，常選擇使用三角形邊的比率來表示：參數(shù)1是三角形中間長度的邊與最長邊的比，參數(shù)2是三角形最短邊長與最長邊的比，a，b與c是三角形的三條邊，且。三角形(a)旋轉(zhuǎn)得出(b)，但是內(nèi)角并沒有發(fā)生改變，而縮放(a)變成(c)，和的大小依舊沒有發(fā)生變化。特征點(diǎn)描述符下的H/S角點(diǎn)檢測方法獲取了角點(diǎn)的多維度信息，算法抗噪聲性能得到很大改善。 實(shí)驗(yàn)分析 算法評價標(biāo)準(zhǔn)一種評價角點(diǎn)提取效果好壞因子的點(diǎn)重復(fù)率定義如下： ()其中表示特征點(diǎn)集合，表示集合中元素的數(shù)目，表示取兩個數(shù)中較小者，分子表示兩幅圖像中相同角點(diǎn)的數(shù)量。當(dāng)亮度改變時，每個像素都會被加上一個常量但不會影響梯度值，因?yàn)樘荻仁峭ㄟ^像素值的差計算得到。首先將坐標(biāo)軸旋轉(zhuǎn)為關(guān)鍵點(diǎn)的方向，以確保旋轉(zhuǎn)不變性。作為尺度不變檢測函數(shù)需要有一個明顯的單一極值點(diǎn)。2. 描述符思想根據(jù)特征點(diǎn)的尺度、方向、位置等信息，為每個特征點(diǎn)建立一個描述符，一個常用的方法是在合適尺度對圍繞特征點(diǎn)的局部區(qū)域進(jìn)行灰度采樣。單一尺度只對應(yīng)事物的單一存在方式，用單一尺度觀察物體，只能獲得物體片面的信息。 H/S算法分析 H/S算法提出的可行性分析上一章詳細(xì)介紹了Harris角點(diǎn)檢測算法和SIFT特征點(diǎn)提取算法，兩種方法都有自己的優(yōu)缺點(diǎn)，這給兩種方法的結(jié)合形成新的特征點(diǎn)提取方法提供了條件。(a)中提取出532個特征點(diǎn)，(b)圖提取出428個特征點(diǎn)，(c)中85個特征點(diǎn)匹配到。1. 旋轉(zhuǎn)不變性(a)為原圖像特征向量提取圖，(b)為經(jīng)過逆時針旋轉(zhuǎn)40度圖像特征向量提取圖，(c)所示。為了增強(qiáng)匹配的穩(wěn)健性，Lowe建議對每個關(guān)鍵點(diǎn)使用44共16個種子點(diǎn)來描述，這樣對于一個關(guān)鍵點(diǎn)就可以產(chǎn)生128個數(shù)據(jù)，即最終形成128維的SIFT特征向量。 在實(shí)際計算時，在以關(guān)鍵點(diǎn)為中心的鄰域窗口內(nèi)采樣，并用直方圖統(tǒng)計鄰域像素的梯度方向。通過下面操作可以將侯選特征點(diǎn)中低對比度(對噪聲敏感)或位于邊緣的侯選特征點(diǎn)過濾掉。原始圖像通過高斯函數(shù)進(jìn)行卷積生成一組圖像，這些圖像在尺度空間中借助常量k被分離。為了有效的在尺度空間檢測到穩(wěn)定的關(guān)鍵點(diǎn)，提出了高斯差分尺度空間(DOG scalespace)。這樣特征點(diǎn)的重復(fù)數(shù)下降，不利于后續(xù)特征點(diǎn)匹配。圖(a)為原圖像，(b)為增加高斯噪聲后圖像，從結(jié)果圖中可以明顯看出，增加高斯噪聲后運(yùn)用Harris算法提取出的角點(diǎn)準(zhǔn)確性下降。Harris方法認(rèn)為，特征點(diǎn)是局部范圍內(nèi)的極大興趣值對應(yīng)的像素點(diǎn)。Harris角點(diǎn)檢測公式為： ()其中，為窗函數(shù)，為圖像灰度的梯度值。前者往往需要對圖像邊緣進(jìn)行編碼，這在很大程度上依賴于圖像的分割和邊緣提取，而這兩種操作本身就具有相當(dāng)大的難度和計算量，況且一旦待檢測目標(biāo)局部發(fā)生變化(例如被部分遮擋)，則很可能導(dǎo)致圖像分割和圖像邊緣提取操作的失敗，所以這種方法的適用范圍很??；而基于圖像灰度的方法則避開了上述這些缺陷，它考慮的是像素點(diǎn)鄰域的灰度變化，而不是整個目標(biāo)的邊緣輪廓。第四章在前面研究的基礎(chǔ)上，提出一種改進(jìn)的相似三角形特征點(diǎn)匹配方法，改進(jìn)方法將傳統(tǒng)被動的同向相似三角形檢索方法變?yōu)樵趶?fù)數(shù)空間下選擇基線后主動構(gòu)造相似三角形，提高了算法的效率。2. 圖像特征點(diǎn)匹配方法研究圖像特征點(diǎn)匹配的目的是在兩幅圖像之間建立盡可能多的匹配點(diǎn)對。Li利用了幾何不變量來進(jìn)行點(diǎn)模式匹配[25]，Spirkovska和Reid利用了高階神經(jīng)網(wǎng)絡(luò)進(jìn)行匹配[26]。SIFT描述符[15]將特征點(diǎn)周圍的窗口分割成16個的子窗口，然后統(tǒng)計每個子窗口的方向梯度直方圖。如何建立特征點(diǎn)之間的對應(yīng)關(guān)系是基于特征點(diǎn)匹配方法的核心研究課題，雖然特征點(diǎn)匹配技術(shù)起步較晚，但是應(yīng)用的迫切和前景的廣泛使它引起了廣大學(xué)者們的極大關(guān)注，在近十幾年里得到了長足的發(fā)展，并出現(xiàn)大量的匹配方法。2) 基于特征的匹配(FeatureBased Matching，F(xiàn)BM)，在匹配前先要抽取邊或區(qū)域等特征。這樣描述器獨(dú)立地用于識別所找到的興趣點(diǎn)，同時能在尺度變化、旋轉(zhuǎn)、光照及視角變化及出現(xiàn)噪聲情況下進(jìn)行很好地匹配。由于不用對目標(biāo)進(jìn)行分割或提取輪廓等預(yù)處理，不需要得到目標(biāo)的全部信息，因此與全局的方法相比，其適用面更廣。目前角點(diǎn)的檢測主要分為兩大類：基于圖像邊緣的角點(diǎn)提取算法和直接基于圖像灰度的角點(diǎn)檢測。在相關(guān)領(lǐng)域中，具有代表性的研究機(jī)構(gòu)是加拿大British Columbia大學(xué)智能計算實(shí)驗(yàn)室，該實(shí)驗(yàn)室開展了局部仿射不變特征提取方面的工作，其研究成果已應(yīng)用于目標(biāo)識別[4]、全景圖拼接[5]、虛擬現(xiàn)實(shí)[6]、機(jī)器人自主導(dǎo)航[7]等領(lǐng)域。本文基于以上熱點(diǎn)問題展開研究，首先對兩種特征點(diǎn)提取算法(Harris算法和SIFT算法)進(jìn)行原理分析及實(shí)驗(yàn)比較，得出Harris角點(diǎn)檢測算法效率高，但對尺度變化和噪聲干擾魯棒性差，以及SIFT算法對尺度變化及抗噪性魯棒性好，但算法時間復(fù)雜度高，且對圖像紋理要求高等結(jié)論，提出一種在多尺度下提取圖像穩(wěn)定特征點(diǎn)的H/S(Harris/SIFT)算法，并在此基礎(chǔ)上采用復(fù)數(shù)空間中相似三角形多模版匹配算法進(jìn)行特征點(diǎn)間匹配，通過理論分析及實(shí)驗(yàn)證明該方法在時間復(fù)雜度方面的改進(jìn)和在圖像存在旋轉(zhuǎn)、縮放情況時匹配的準(zhǔn)確性和有效性。如何建立圖像興趣點(diǎn)之間的對應(yīng)關(guān)系一直是這類方法的研究熱點(diǎn)。它通過建立兩幅圖像之間的對應(yīng)關(guān)系，確定相應(yīng)的幾何變換參數(shù)，對兩幅圖像中的同一目標(biāo)進(jìn)行匹配。圖像匹配分為基于灰度的方法和基于特征的方法，前者簡單易行，但算法時間復(fù)雜度高，難以處理圖像存在旋轉(zhuǎn)和尺度變化等情況，后者在適應(yīng)性和速度方面有很大優(yōu)勢，但圖像特征的提取以及如何建立特征之間的對應(yīng)關(guān)系一直是這類方法的研究難題。關(guān)鍵詞 特征點(diǎn)，H/S算法，機(jī)器視覺，相似三角形檢索ABSTRACTImage matching is a basic problem in the field of image processing, it has wide applications in puter vision, such as image stitching, panoramic view, object recognition and so on. It includes graybased method and featurebased method. The former method is simple, but the time plexity of this algorithm is high, especially it’s difficult to deal with the situations of image rotation and scaling. The latter method is much more easily overing the difficulties which encountered by the former method, but how to create the corresponding relationships between the images’ features is always a difficult problem. A new feature point extracting method is proposed in this thesis, and a new matching method which is based on similar triangles is proposed.The thesis firstly analyses and pares two kinds of extracting feature points algorithms( Harris algorithm and SIFT algorithm ), Harris algorithm has high efficiency and poor antiscaling and antinoise performance, SIFT algorithm has good robustness about antiscaling and antinoise, but the time plexity of this algorithm is high, and it has a great demand on image texture. The thesis bines the advantages of these two algorithms, a new H/S algorithm which is used to extract feature points is proposed, this algorithm has well efficiency, meanwhile, the antiscaling and antinoise performance is greatly improved. While the feature points of images are obtained by using the new H/S algorithm, the matching methods are studied. Traditional similar triangles matching method is simple and has good robustness, but the time plexity of this algorithm is high, because of this limitations, the thesis proposes a improved matching method which is based on similar triangles, making the traditional passively searching similar triangles to select the baseline to actively construct similar triangles. The algorithm uses multitemplates to match in the image, the real time ability and stability of the algorithm is improved.KEY WORDS feature points, H/S algorithm, puter vision, similar triangles retrieval圖像特征點(diǎn)提取及匹配算法研究 第一章 緒論第一章 緒論 研究背景圖像特征點(diǎn)提取和匹配是圖像處理研究領(lǐng)域中的基礎(chǔ)課題，也是機(jī)器視覺的關(guān)鍵技術(shù)之一，廣泛應(yīng)用于虛擬現(xiàn)實(shí)、視頻壓縮、圖像復(fù)原、圖像數(shù)據(jù)庫檢索等技術(shù)中，具有廣泛的應(yīng)用前景及社會經(jīng)濟(jì)價值。為了克服基于灰度匹配方法缺點(diǎn)，提出了基于特征的匹配方法。二是找出或構(gòu)造目標(biāo)作某種運(yùn)動或無論目標(biāo)作何種運(yùn)動都不變化的目標(biāo)圖像特性的特征不變量。2) 不變性獲取的途徑，如通過特征變換、小波理論、神經(jīng)網(wǎng)絡(luò)、編碼技術(shù)、特征描述子的構(gòu)造等。1. 角點(diǎn)檢測方法一直以來角點(diǎn)沒有明確的數(shù)學(xué)定義，人們普遍認(rèn)為角點(diǎn)是二維圖像亮度變化劇烈的點(diǎn)或圖像邊緣曲線上曲率極大值的點(diǎn)。由于它不需要進(jìn)行邊緣提取工作，所以在實(shí)際中得到了廣泛的應(yīng)用。這種方法較好地同時解決了特征區(qū)域定位和大小選擇的問題。 特征點(diǎn)匹配研究現(xiàn)狀特征點(diǎn)匹配就是將不同圖像上由同一場景點(diǎn)投影而成的特征點(diǎn)對找出來。當(dāng)這些約束不滿足時，相應(yīng)的方法就無法使用。這類方法在提取特征點(diǎn)后，對特征點(diǎn)進(jìn)行不同的描述，用來區(qū)別其它特征點(diǎn)，然后用描述符進(jìn)行匹配。近年來還出現(xiàn)了許多特征點(diǎn)匹配方法，如D Skea提出了一個累加器算法[21]，其核心思想是平面點(diǎn)模式匹配的一個框架，該算法對噪聲和缺少點(diǎn)及偽點(diǎn)較為魯棒，但計算復(fù)雜度較大。本文在研究現(xiàn)有的一些特征檢測算法及匹配方法基礎(chǔ)上，以計算機(jī)視覺的不變理論為基礎(chǔ)，本文主要研究內(nèi)容如下所述。 論文組織結(jié)構(gòu)本文將圖像特征點(diǎn)的提取方法以及特征點(diǎn)匹配方法作為主要研究對象，針對圖像存在旋轉(zhuǎn)和尺度變化的情況，利用改進(jìn)H/S算法提取圖像中特征點(diǎn)，并在分析比較兩種常用特征點(diǎn)匹配方法基礎(chǔ)上，提出了一種改進(jìn)的相似三