【正文】 (a)模板圖(b)實(shí)物圖 復(fù)雜背景下圖像匹配(a)模板圖(b)實(shí)物圖 模板圖像旋轉(zhuǎn)、縮放圖像匹配 本章小結(jié)本章在H/S算法提取圖像中穩(wěn)定特征點(diǎn)的基礎(chǔ)上，分析傳統(tǒng)相似三角形匹配算法局限性，引入基線理論并結(jié)合特征點(diǎn)描述符信息，改進(jìn)了三角形的構(gòu)造方法。1. 模板圖像旋轉(zhuǎn)、縮放時匹配、縮放時匹配結(jié)果，(a)為模板圖，(b)為實(shí)物圖，在(b)中存在與(a)相同、旋轉(zhuǎn)、尺度變化、旋轉(zhuǎn)縮放共存的模板圖，用矩形標(biāo)識出實(shí)物圖中存在的模板圖，實(shí)驗(yàn)結(jié)果表明該算法對于圖像存在旋轉(zhuǎn)、縮放情況下的有效性。如果是，則進(jìn)一步判斷該位置特征點(diǎn)的描述符信息與模板圖中對應(yīng)相似三角形頂點(diǎn)的描述符信息相似度，若相似度滿足要求則輸出為模板的一同向相似三角形，并設(shè)置特征點(diǎn)數(shù)量記錄匹配到的同向相似三角形的數(shù)目；4) 判斷與模板圖中對應(yīng)基線的三角形組的頂點(diǎn)數(shù)量關(guān)系，若值達(dá)到一定的閾值，則輸出在模板圖像中匹配到一個模板圖像，并用矩形框?qū)⑵錁?biāo)識出；轉(zhuǎn)步驟2，繼續(xù)判斷實(shí)物圖中特征點(diǎn)集合中的其它基線；5) 算法結(jié)束。并且通過構(gòu)造基線三角形組的思想，使匹配模板由單個模板變?yōu)槎鄠€模板，提高了搜索策略的可靠性。在復(fù)數(shù)空間下得到對應(yīng)特征點(diǎn)組成向量的三角形組的基礎(chǔ)上，通過判斷實(shí)物圖中對應(yīng)于模版圖像中的基線的三角形組的頂點(diǎn)為特征點(diǎn)的數(shù)量是否達(dá)到一定閾值，若滿足閾值要求，則可以認(rèn)為在實(shí)物圖中找到一個模版圖像，同理遍歷模版圖像中的所有基線，進(jìn)行相似三角形檢索，找到實(shí)物圖中所有的模版圖像。 同向相似三角形 多模板改進(jìn)方法分析相似三角形的特征點(diǎn)匹配方法利用了三角形的平移、旋轉(zhuǎn)、縮放不變性，傳統(tǒng)的判定方法目前已經(jīng)比較成熟，所以在對于旋轉(zhuǎn)和縮放這類圖像匹配的應(yīng)用方面，具有較為突出的優(yōu)越性。根據(jù)三角形相似判定定理：兩邊對應(yīng)成比例且夾角相等，則兩三角形相似。然而，則需要求解二元二次方程組以及進(jìn)行同向性判斷，計(jì)算過程比較復(fù)雜，下面將采用另一種方法求解點(diǎn)。由三角形三邊之間的關(guān)系及式()可得：() 由式()知兩圓必交于不同的兩點(diǎn)，且兩點(diǎn)關(guān)于邊對稱。且根據(jù)復(fù)數(shù)相乘的幾何意義，將圖像特征點(diǎn)轉(zhuǎn)移到復(fù)數(shù)向量空間中求解，大大提高了算法效率。證畢。：的頂點(diǎn)坐標(biāo)為，對應(yīng)頂點(diǎn)坐標(biāo)分別為，則與頂點(diǎn)同方向排列的充分必要條件是()證明：將點(diǎn)、和點(diǎn)、看作空間直角坐標(biāo)系下的點(diǎn)，可得。于是，通過限制三角形的形成來減少誤匹配的可能及處理三角形的配對。奇異三角形，由于這些三角形面積狹小及邊和邊之間的關(guān)系不明顯而不利于模版圖像的定位，所以不被選為子模版三角形。算法步驟：首先提取圖像特征點(diǎn)，在圖像中選取特征值較高且分布均勻的特征點(diǎn)構(gòu)成特征點(diǎn)集，并根據(jù)圖像特征點(diǎn)間的歐氏距離及描述符信息條件選擇滿足要求的基線，構(gòu)造基線三角形組形成相應(yīng)基線的三角形集合；然后從模版圖像的基線三角形集合中選取三角形子模版，對實(shí)物圖像中的特征點(diǎn)進(jìn)行相似三角形檢索，當(dāng)找到基線所對應(yīng)三角形的頂點(diǎn)幾何位置時，在判斷它是否為特征點(diǎn)基礎(chǔ)上，進(jìn)一步結(jié)合該特征點(diǎn)位置的描述符信息剔除偽匹配三角形，在實(shí)物圖像中準(zhǔn)確定位出模版圖像。 改進(jìn)的相似三角形匹配方法實(shí)現(xiàn)根據(jù)以上對于傳統(tǒng)三角形特征點(diǎn)匹配算法的原理及局限性分析，針對傳統(tǒng)三角形匹配算法時間復(fù)雜度高，使用單模板匹配的局限性，通過引入基線及基線三角形組的概念，由復(fù)數(shù)相乘的幾何意義，將圖像特征點(diǎn)轉(zhuǎn)移到復(fù)數(shù)向量空間中求解，不僅使算法的效率得到提高，同時也增強(qiáng)了算法的可靠性。 三角形相似方法局限性假設(shè)兩特征點(diǎn)集的數(shù)量都為，每個點(diǎn)集將構(gòu)成個三角形，方法需要對每對三角形進(jìn)行相似性判定，時間復(fù)雜度。這個方法很具有直覺性，是人類視覺識別相似三角形的部分技能。可能的擴(kuò)展是包括一個與三角形尺寸有關(guān)的規(guī)范化參數(shù)，如三角形面積、周長。很明顯點(diǎn)對的權(quán)值越高，點(diǎn)對為真正的配對的可能性越大。為了計(jì)算A組的點(diǎn)i和B組的點(diǎn)j具有共同的三角形的數(shù)目，定義的權(quán)值二維表，并初始化為零。然而對三角空間中的B組坐標(biāo)分別按照進(jìn)行排序，再使用折半查找法能夠迅速地在組B中找到開始點(diǎn)，只有那些落在范圍之內(nèi)的點(diǎn)需要進(jìn)行比較，能夠避免大量的比較。 三角空間的三角形特征由空間中的三個點(diǎn)構(gòu)成的三角形就可以轉(zhuǎn)換成空間中用一個點(diǎn)來表示。定義 ：從兩幅圖像中任意選擇兩個三角形，它們組成一個三角形對。對點(diǎn)則可組成對相似的三角形，且以某個點(diǎn)為頂點(diǎn)的三角形有個。 相似三角形方法局限性分析由于三角形具有天然的抗平移、旋轉(zhuǎn)和縮放特性，對于處理圖像間存在平移、旋轉(zhuǎn)、縮放等情況，具有很好的優(yōu)越性，目前基于三角形幾何結(jié)構(gòu)的匹配方法研究廣泛，因此本節(jié)選擇了能夠較好體現(xiàn)基于幾何結(jié)構(gòu)匹配思想的相似三角形匹配方法進(jìn)行研究。H/S算法的實(shí)現(xiàn)主要是通過將局部不變特征SIFT特征點(diǎn)提取算法中的多尺度和特征點(diǎn)描述符的理論基礎(chǔ)，將傳統(tǒng)Harris特征點(diǎn)提取算法在單一尺度下檢測角點(diǎn)變?yōu)槎喑叨忍崛。箼z測出的特征點(diǎn)具有尺度不變性，并且利用經(jīng)多尺度過濾后的特征點(diǎn)的信息量差異較大的特點(diǎn)，構(gòu)造16維的特征向量極大的提高了特征向量的構(gòu)造速度。2. 抗噪聲分別用H/S算法和傳統(tǒng)的Harris算法對添加噪聲后的圖像進(jìn)行檢測。圖像中提取出的特征點(diǎn)用十字劃線標(biāo)識。 (a)圖像梯度 (b)關(guān)鍵點(diǎn)描述 特征點(diǎn)描述符根據(jù)以上對于H/S特征點(diǎn)提取算法中多尺度空間理論和特征點(diǎn)描述符理論的實(shí)現(xiàn)思想，H/S算法首先利用傳統(tǒng)的Harris特征點(diǎn)提取算法初步得到圖像中的特征點(diǎn)，然后通過多尺度檢測剔除部分抗尺度變化性能弱的特征點(diǎn)，在此基礎(chǔ)上為每個關(guān)鍵點(diǎn)的鄰域計(jì)算局部圖像梯度的方向直方圖，最后轉(zhuǎn)換為16維的特征描述符，使H/S特征點(diǎn)描述符具有抗噪聲性能。由于傳統(tǒng)的SIFT特征點(diǎn)描述符在構(gòu)造時，特征點(diǎn)之間的梯度方向及模值差異較小，如果特征向量描述符的維度偏低時則使構(gòu)造特征向量的特征點(diǎn)之間的區(qū)分度過小，則無法體現(xiàn)出描述符的優(yōu)越性，不利于后續(xù)圖像特征點(diǎn)的匹配。首先特征點(diǎn)描述符向量要被標(biāo)準(zhǔn)化為單位長度。(b)中每一個關(guān)鍵點(diǎn)由22共4個種子點(diǎn)組成，每個種子點(diǎn)有8個方向向量信息。其中L所用的尺度為每個關(guān)鍵點(diǎn)各自所在的尺度。DOG函數(shù)計(jì)算較簡單，是歸一化LOG算子的近似，定義如下： ()算法首先利用Harris算子在尺度上建立個尺度空間的描述，其中表示第尺度，；表示尺度因子自適應(yīng)調(diào)整尺度間的跨度。然后通過判斷()即可檢測出尺度為的特征點(diǎn)。在關(guān)鍵點(diǎn)的鄰域梯度信息計(jì)算時，以關(guān)鍵點(diǎn)為中心建立窗口，通過繪制窗口像素點(diǎn)的梯度方向和梯度模值的累加值，在生成種子點(diǎn)的基礎(chǔ)上得到每個種子點(diǎn)的方向向量信息，這種鄰域方向信息的聯(lián)合增強(qiáng)了特征點(diǎn)的抗噪聲能力。作為尺度空間理論中的一個重要概念，尺度空間核被定義為：()對于所有的信號，若它與變換核卷積后得到的信號中的極值(一階微分過零點(diǎn))不超過原圖像的極值，則稱為尺度空間核，所進(jìn)行的卷積變換稱為尺度變換。尺度空間理論正是從多尺度理論發(fā)展而來的，它從人類視覺系統(tǒng)得到啟發(fā)，從多尺度的角度來分析圖像。下面進(jìn)行提取算法結(jié)合方案的具體研究與分析。特征點(diǎn)定位較準(zhǔn)確，對局部噪聲不敏感，且計(jì)算速度快，但是它是在單一尺度下檢測角點(diǎn)，若選用較小窗口高斯卷積后提取角點(diǎn)時則會因?yàn)樵肼暤纫蛩貙?dǎo)致出現(xiàn)眾多角點(diǎn)位置；若選用較大窗口高斯卷積則會因?yàn)榫矸e的圓角效應(yīng)使角點(diǎn)的位置產(chǎn)生較大的偏移。本章在改進(jìn)Harris算法關(guān)鍵步驟的基礎(chǔ)上，結(jié)合SIFT算法中所使用的多尺度理論和特征點(diǎn)描述思想進(jìn)行結(jié)合的方案進(jìn)行研究。但該算法在對提取出的特征點(diǎn)進(jìn)行描述時，采用128維的高維度向量，算法速度較慢；其次該算法基于局部區(qū)域描述，這就要求圖像滿足足夠多的紋理，否則構(gòu)造出的向量區(qū)別性就不是很大，容易造成誤匹配。(a)中提取出846個特征點(diǎn)，(b)中提取出426個特征點(diǎn)，(c)中有163個特征點(diǎn)匹配到。在圖像存在旋轉(zhuǎn)情況下，兩幅圖像提取得到較多不變特征點(diǎn)，驗(yàn)證該算法在尺度變化時的不變性。實(shí)驗(yàn)結(jié)果圖中提取出的特征向量用箭頭表示，箭頭起點(diǎn)表示特征點(diǎn)在圖像中的二維坐標(biāo)位置，箭頭長度代表了關(guān)鍵點(diǎn)所處的尺度，箭頭方向代表了該尺度下關(guān)鍵點(diǎn)所處鄰域的主梯度方向。 實(shí)驗(yàn)分析實(shí)驗(yàn)測試SIFT不變特征提取算法及采用特征點(diǎn)歐氏距離法最近鄰(NN)匹配方法的效果與性能，通過其在旋轉(zhuǎn)、尺度變化、噪聲干擾、照度變化等情況下的匹配實(shí)驗(yàn)的結(jié)果分析，驗(yàn)證該算法在圖像匹配時的有效性及適用性。并且特征點(diǎn)描述符要盡量與眾不同，以便于特征點(diǎn)間的匹配。直方圖的峰值則代表了該關(guān)鍵點(diǎn)處鄰域梯度的主方向，即作為該關(guān)鍵點(diǎn)的方向。3. 特征點(diǎn)方向確定基于圖像屬性為每個特征點(diǎn)賦一個方向，在后面特征點(diǎn)描述符中將會用到特征點(diǎn)的方向并對特征點(diǎn)的特性進(jìn)行描述。2) 邊緣響應(yīng)的去除一個定義不好的高斯差分算子的極值在橫跨邊緣的地方有較大的主曲率，而在垂直邊緣的方向有較小的主曲率。中間的檢測點(diǎn)和它同尺度的8個相鄰點(diǎn)和上下相鄰尺度對應(yīng)的92個點(diǎn)共26個點(diǎn)比較，以確保在尺度空間和二維圖像空間都檢測到極值點(diǎn)。利用高斯差分金字塔分層結(jié)構(gòu)提取出圖像中的極值點(diǎn)作為候選特征點(diǎn)，并對這些候選特征點(diǎn)進(jìn)一步篩選掉其中低對比度和處于邊緣的特征點(diǎn)，最終提取出穩(wěn)定的特征點(diǎn)。這樣就形成一個金字塔形狀的圖像分層結(jié)構(gòu)。 ()。 SIFT算法流程1. 尺度空間極值求取SIFT方法第一步就是找出尺度空間的極值，首先構(gòu)建圖像的尺度空間函數(shù)。 SIFT特征點(diǎn)提取算法由上節(jié)對Harris特征點(diǎn)提取算法局限性的分析，本節(jié)對目前國內(nèi)外研究廣泛的局部不變特征點(diǎn)提取算法SIFT進(jìn)行研究，該算法提取出的特征點(diǎn)對圖像尺度和旋轉(zhuǎn)不變性效果好，對光線變化和噪聲變化也具有較好魯棒性。當(dāng)圖像間發(fā)生尺度變換時，Harris角點(diǎn)就可能檢測出不一致的角點(diǎn)。從圖中可以看出，將閾值設(shè)定較高時，檢測得到的角點(diǎn)數(shù)量明顯下降。(a)原圖像(b)逆時針旋轉(zhuǎn)30度圖像 圖像旋轉(zhuǎn)角點(diǎn)提取結(jié)果圖 2. 尺度變化不變性(a)為原圖像，(b)為尺度變化后圖像角點(diǎn)檢測結(jié)果，由結(jié)果圖可以看出Harris算法在尺度發(fā)生變化時圖像中檢測得到的特征點(diǎn)與原圖有較大差別。實(shí)驗(yàn)實(shí)現(xiàn)Harris角點(diǎn)檢測算法，測試其在圖像存在旋轉(zhuǎn)、尺度變化、噪聲等情況下的檢測效果，并分析Harris算法在設(shè)置不同閾值情況下提取角點(diǎn)。離散二維零均值高斯函數(shù) ()3) 計(jì)算原圖像上對應(yīng)的每個像素點(diǎn)的興趣值，即R值(角點(diǎn)量cim)。對于每個小的位移量，檢測公式可雙線性近似表示為： ()其中 ()設(shè)，是矩陣的兩個特征值，則可表示局部自相關(guān)函數(shù)的曲率。因此本節(jié)主要分析Harris算法。由于它不需要進(jìn)行邊緣提取工作，所以在實(shí)際中得到了廣泛的應(yīng)用。 Harris特征點(diǎn)提取算法角點(diǎn)作為目前圖像匹配中常用的特征點(diǎn)，它是二維圖像亮度變化劇烈或圖像邊緣曲線上曲率極大值的點(diǎn)，決定了目標(biāo)的輪廓特征，因此被廣泛應(yīng)用于攝像機(jī)標(biāo)定、虛擬場景重建、運(yùn)動估計(jì)、圖像配準(zhǔn)等計(jì)算機(jī)視覺處理任務(wù)中。最后一章對全文工作進(jìn)行總結(jié)，并提出今后研究的問題與方向。本文的篇章結(jié)構(gòu)安排如下：第一章為緒論，介紹了圖像特征點(diǎn)、圖像匹配基本概念，相關(guān)領(lǐng)域研究現(xiàn)狀，最后闡述了本文的主要研究工作和篇章結(jié)構(gòu)。圖像特征點(diǎn)匹配方法目前主要分為兩種，即為基于描述符的特征點(diǎn)匹配方法和基于特征點(diǎn)幾何結(jié)構(gòu)的匹配方法。1. 圖像不變特征點(diǎn)提取算法研究圖像特征點(diǎn)提取是基于特征點(diǎn)匹配方法的首要步驟，在實(shí)際問題中，圖像可能受到噪聲、背景的干擾，也可能發(fā)生光照、尺度、旋轉(zhuǎn)、仿射等變化，如何選擇合理的圖像特征點(diǎn)，使得這些特征點(diǎn)不僅具有良好的抗噪性能，而且在上述變化下保持不變，直接決定了基于特征點(diǎn)的匹配方法效果。 研究內(nèi)容特征點(diǎn)提取過程中，需要構(gòu)建在多種變換下具有良好不變性的特征點(diǎn)提取算法以獲得具有精確性高，區(qū)分度強(qiáng)的不變性圖像特征，并綜合特征局部結(jié)構(gòu)信息，構(gòu)造特征描述算子。Sanjay Ranade and AzrielRosenfeld提出松弛法進(jìn)行點(diǎn)匹配[2]，陳志剛等在其基礎(chǔ)上通過構(gòu)建三角形并利用其相似度來定義點(diǎn)特征的匹配度，提出了一種新的具有比例與旋轉(zhuǎn)不變特性的點(diǎn)特征松弛匹配算法[22]。一共具有個子窗口，每個窗口描述是8位的，描述8個方向的梯度的大小值，這樣形成的描述符是維，匹配時只需利用描述符進(jìn)行配對。利用特征描述符進(jìn)行匹配的方法是在特征點(diǎn)提取過程中，不僅得到特征點(diǎn)的位置，同時將得到特征點(diǎn)的其他仿射變換下不變的特征點(diǎn)描述。這時相當(dāng)于提供了一個不變量，即一幅圖像中任意兩個特征點(diǎn)的距離與另一幅圖像對應(yīng)的特征點(diǎn)之間的距離相等。Maciel等使用線性規(guī)劃的方法來解決匹配中產(chǎn)生的歧義問題，這種方法可以得到某種意義上的全局最優(yōu)解，并且由于線性規(guī)劃法已經(jīng)很成熟。但是特征匹配往往有很高的計(jì)算代價。由匹配線索不同，現(xiàn)有的匹配算法基本可以分為兩大類：1) 基于窗口的匹配(AreaBased Matching,ABM)，窗口是由待匹配點(diǎn)附近的像素灰度值組成的二維矩陣，其中最常用的是用交叉相關(guān)性來匹配，這是目前大多數(shù)匹配算法的基礎(chǔ)。通過研究SURF在處理模糊和旋轉(zhuǎn)的圖像時表現(xiàn)出很強(qiáng)的優(yōu)點(diǎn)，而在視角變化和光照變化上略差一些。在每個特征區(qū)域內(nèi)，Lowe以梯度方向的直方圖為基礎(chǔ)構(gòu)造了一種稱為SIFT（Scale Invariant Feature Transform）的局部不變特征提取性能的衡量標(biāo)準(zhǔn)。局部不變特征提取需要解決兩個問題：一是特征區(qū)域定位，即在哪里提取特征；二是區(qū)域內(nèi)信息描述，即用什么特征量來描述區(qū)域內(nèi)的信息。目前國內(nèi)研究角點(diǎn)提取算法重點(diǎn)主要在已有算法的改進(jìn)，如楊莉等基于SUSAN算法提出的RSUSAN (Redefined SUSAN)角點(diǎn)提取算法[9]，使用了更為有效和簡便的計(jì)算USAN區(qū)域的方法，提高了計(jì)算速度；王建琦等人提出一種改進(jìn)的角點(diǎn)提取方法[10]，該方法是基于MIC算法的改進(jìn)，該算法采用了在方形窗邊界上的線性插值，在插值的基礎(chǔ)上計(jì)算出邊緣角，通過它來對角點(diǎn)候選點(diǎn)做進(jìn)一步的篩選；李華等人提出了一種新的基于形態(tài)骨架的快速拐點(diǎn)提取方法[11]，該方法基于物體條件骨架原理，