【正文】 角形特征點(diǎn)匹配算法。本章針對實(shí)際情況的復(fù)雜多樣性，對兩種特征點(diǎn)提取方法(Harris算法和SIFT算法)進(jìn)行分析研究。實(shí)驗(yàn)結(jié)果表明Moravec，SUSAN算法存在較多的誤檢測和漏檢測現(xiàn)象，且對旋轉(zhuǎn)前后的圖像角點(diǎn)檢測不一致，而Harris角點(diǎn)檢測法具有最好的效果。2) 對圖像進(jìn)行高斯濾波，得到新的M。從圖中可以看出，Harris算法在圖像旋轉(zhuǎn)時檢測得到角點(diǎn)的重復(fù)數(shù)很高，具有良好的抗旋轉(zhuǎn)性能。但是Harris特征點(diǎn)檢測算法也存在著一定的局限性。接著對圖像使用不同的采樣距離以形成一個金字塔圖像分層結(jié)構(gòu)，這就意味著將原來圖像放大一倍，第一次采樣的圖像作為第一組的圖像，然后以成倍的采樣距離即4個像素再分別對圖像進(jìn)行采樣從而產(chǎn)生第二、三、四組的圖像。 高斯 雙高斯差（DoG） 候選特征點(diǎn)生成圖 2) 空間極值點(diǎn)檢測為了尋找尺度空間的極值點(diǎn)，每一個采樣點(diǎn)要和它所有的相鄰點(diǎn)比較，看其是否比它的圖像域和尺度域的相鄰點(diǎn)大或者小。 () ()令，則： ()的值在兩個特征值相等的時候最小，隨著的增大而增大，因此，為了檢測主曲率是否在某域值下，只需檢測 ()在Lowe的文章[15]中，取＝10。 4. 特征點(diǎn)描述符的確定通過以上步驟得到了每個特征點(diǎn)的位置、尺度、方向,下一步將為每個特征點(diǎn)建立一個描述符，使其不隨各種變化而變化，比如光線變化、視角變化等。每創(chuàng)建一個將要使用OpenCV的VC++ Project都需要給它指定需要的lib菜單：ProjectSettings,然后將Settings for選為All Configurations，選擇右邊的link標(biāo)簽，在Object/library modules附加上： 。(a)原圖特征向量(b)尺度變化圖特征向量(c)圖像尺度變化時匹配結(jié)果 圖像尺度不變特征提取及匹配圖 3. 圖像旋轉(zhuǎn)、縮放共存條件時不變性(a)為原圖特征向量提取圖，(b)為旋轉(zhuǎn)、縮放共存時特征向量提取圖，(c)所示。比較分析Harris角點(diǎn)檢測算法和SIFT特征點(diǎn)提取算法，揚(yáng)長避短，對它們進(jìn)行有效的結(jié)合，使特征點(diǎn)的提取獲得更好的效果。 H/S算法結(jié)合方案研究首先傳統(tǒng)的Harris特征點(diǎn)提取算法是在單一尺度下進(jìn)行特征點(diǎn)的檢測，當(dāng)尺度變化時，可能檢測出新的角點(diǎn)，或者老的角點(diǎn)發(fā)生移位或消失，這樣使得有效點(diǎn)的比例將存在極大的降低，不利于后續(xù)的特征點(diǎn)匹配，所以需要在Harris算法初步得到單一尺度下特征點(diǎn)后，引入SIFT檢測特征點(diǎn)第一個步驟中的尺度空間極值檢測的思想，使傳統(tǒng)Harris特征點(diǎn)提取算法得到的抗尺度變化的有效的特征點(diǎn)數(shù)目能夠提高，再在此基礎(chǔ)上結(jié)合SIFT特征點(diǎn)描述符的方法，使結(jié)合后的提取算法更穩(wěn)定、快速、有效。Koenderink和Lindeberg(1994)[14]研究發(fā)現(xiàn)高斯函數(shù)是唯一的尺度空間內(nèi)核函數(shù)。 算法流程圖 H/S算法實(shí)現(xiàn) 多尺度特征點(diǎn)檢測為了獲取Harris算法的尺度空間表示，首先計(jì)算圖像上某點(diǎn)在和方向上的偏導(dǎo)，然后與標(biāo)準(zhǔn)偏差為(其中：為一常量，1)的高斯核的微分進(jìn)行卷積：()()其中，=為尺度參數(shù)，=為微分尺度，為高斯函數(shù)。 () ()式()、()為處梯度的模值和方向公式。最后，特征點(diǎn)描述符要作一些改動以減少光線變化時的影響。H/S特征向量的構(gòu)造過程使用了16維的梯度信息，與SIFT特征向量的128維相比，極大的提高了特征向量的構(gòu)造效率，同時由于H/S對于特征向量的構(gòu)造是在獲得抗尺度變化的特征點(diǎn)基礎(chǔ)上，因此構(gòu)造特征向量的數(shù)量也大為降低。多尺度空間下的Harris角點(diǎn)檢測方法獲取了多個尺度下的角點(diǎn)信息，減小了閾值對角點(diǎn)提取的制約，同時多尺度空間下H/S角點(diǎn)檢測實(shí)現(xiàn)了小尺度下的精確定位和大尺度下的去偽存真，算法尺度不變性得到很大改善。圖像特征點(diǎn)提取及匹配算法研究 第四章 基于H/S的特征點(diǎn)匹配方法第四章 基于H/S的特征點(diǎn)匹配方法本章在使用改進(jìn)的H/S特征點(diǎn)提取算法檢測圖像的特征點(diǎn)基礎(chǔ)上，結(jié)合特征點(diǎn)間的幾何結(jié)構(gòu)，根據(jù)三角形相似性原理提出一種改進(jìn)的相似三角形匹配方法，大大降低了傳統(tǒng)相似三角形匹配算法的時間復(fù)雜性，并提高了算法的可靠性和準(zhǔn)確性。算法過程具體描述如下：1． 三角形的建立及表示：從待匹配的兩幅圖像中提取的角點(diǎn)集和中任意三點(diǎn)，依次連接這三點(diǎn)組成的三角形就稱之為三角形。2． 三角形匹配窮舉方法就是用A組中的每一個三角形去和B組中的每一個三角形進(jìn)行比較，而每一次的比較都涉及到笛卡爾距離的計(jì)算。權(quán)值矩陣由兩組點(diǎn)對組成。這個思想在于運(yùn)用這些參數(shù)可以限制一些匹配，比如比較大的三角形僅僅和比較大的三角形匹配。再者當(dāng)模板點(diǎn)集中的一個點(diǎn)與目標(biāo)點(diǎn)集中多個點(diǎn)匹配這種情況出現(xiàn)時，特征點(diǎn)的對應(yīng)關(guān)系就找不出來了。2. 奇異三角形的去除奇異三角形是指存在夾角近似于或的三角形()。下面給出兩三角形同向的判斷條件及證明。本文將采用一種主動的相似三角形檢索方法，時間復(fù)雜度僅為。對點(diǎn)是否為特征點(diǎn)的判斷，只需在保存實(shí)物圖像特征點(diǎn)的二維布爾值數(shù)組中檢查點(diǎn)對應(yīng)的值是否為真即可，算法復(fù)雜度為。稱復(fù)數(shù)為旋轉(zhuǎn)因子，可由向量對應(yīng)的復(fù)數(shù)與向量對應(yīng)的復(fù)數(shù)相除得到。A(a)模板圖像三角形 (b)實(shí)物圖像中三角形 相似三角形本章改進(jìn)算法是在現(xiàn)有相似三角形匹配算法的基礎(chǔ)上，通過選取模板圖像中特征點(diǎn)組成基線的相應(yīng)三角形組后，對實(shí)物圖像相應(yīng)特征點(diǎn)組成的基線進(jìn)行對應(yīng)的相似三角形檢索來實(shí)現(xiàn)模板圖像的定位，從而很大程度上減少了傳統(tǒng)模板匹配方法的搜索空間，提高了搜索的效率。實(shí)驗(yàn)使用VC++，首先利用H/S特征點(diǎn)提取算法提取出圖像中特征點(diǎn)，得到待匹配的兩幅圖像對應(yīng)特征點(diǎn)集。改進(jìn)算法繼承了傳統(tǒng)相似三角形匹配算法抗旋轉(zhuǎn)和縮放的優(yōu)點(diǎn)，將傳統(tǒng)被動同向相似三角形檢索方法變?yōu)樵趶?fù)數(shù)空間下選擇基線后主動構(gòu)造相似三角形，同時在選擇基線及進(jìn)行相似三角形的判斷時利用了特征點(diǎn)的描述符信息，提高了算法效率。 實(shí)驗(yàn)結(jié)果與分析實(shí)驗(yàn)實(shí)現(xiàn)改進(jìn)的相似三角形特征點(diǎn)匹配算法，驗(yàn)證其在圖像存在旋轉(zhuǎn)、縮放、噪聲以及復(fù)雜背景下物體識別的準(zhǔn)確性及算法效率。在復(fù)數(shù)向量空間中，從特征點(diǎn)集中結(jié)合特征點(diǎn)的描述符信息，根據(jù)與模板圖像對應(yīng)特征向量的屬性相似度，從實(shí)物圖中選擇基線，以其余所有的特征點(diǎn)與構(gòu)成三角形組，具體方法以構(gòu)造為例說明如下()：由模版圖對應(yīng)的復(fù)數(shù)與對應(yīng)的復(fù)數(shù)相除得到旋轉(zhuǎn)因子，運(yùn)用旋轉(zhuǎn)因子找出點(diǎn)，使與所確定的三角形與模板為同向相似三角形。假設(shè)中向量到向量的角度為，與的比值為，可知只需中向量到向量的角度為，與的比值為，則與同向相似。這樣就得到兩個與相似的三角形，這兩個三角形反向相似，其中有且僅有一個三角形與同向相似，且對應(yīng)的交點(diǎn)即為要求的點(diǎn)，證畢。不能由旋轉(zhuǎn)得到。 相似三角形檢索方法改進(jìn)由于同向相似三角形檢索首先需要對三角形進(jìn)行相似性判斷，然后進(jìn)行同向性判斷。 匹配算法流程 三角形選取方案研究1. 改進(jìn)選取三角形思路根據(jù)傳統(tǒng)的基于相似三角形匹配方法，模板圖像中個特征點(diǎn)，任意可組成個三角形，然后逐個使用每個三角形在實(shí)物圖像中尋找相似三角形，是一種被動檢索方式，顯然這種方法基數(shù)非常大，所需要比較的三角形個數(shù)很多，時間復(fù)雜度也就相應(yīng)的增加。而且判定方法還需牽涉到較為復(fù)雜的除法和比較操作。規(guī)范化可能是一組中所有三角形關(guān)于這個屬性的平均值。每一組匹配上的三角形，對于構(gòu)成三角形的每個點(diǎn)，其在權(quán)值矩陣中的元素的權(quán)值被加1。由上面的定義可知，三角形映射到三角空間中是被限制在一個三角形區(qū)域中()，但是對于相似三角形，無論它如何平移、旋轉(zhuǎn)或縮放，它總是投影在空間的同一點(diǎn)?；诖嗽?，將相似兩三角形對應(yīng)點(diǎn)的置信度加一。本章將尺度空間理論和特征點(diǎn)描述符的思想應(yīng)用到傳統(tǒng)的Harris角點(diǎn)檢測的方法中，實(shí)現(xiàn)了具有平移、旋轉(zhuǎn)、抗尺度和抗噪聲變化的H/S特征點(diǎn)提取算法。1. 尺度不變性將H/S特征點(diǎn)提取算法與傳統(tǒng)的Harris角點(diǎn)檢測算法，分別對尺度變化前后的圖像進(jìn)行角點(diǎn)檢測。因此利用了128維的向量信息以提高其抗旋轉(zhuǎn)及抗噪聲等性能。這種鄰域方向的信息聯(lián)合的思想增強(qiáng)了算法抗噪聲的能力，同時對于含有定位誤差的特征匹配也提供了較好的容錯性。在每一個尺度水平上提取出在鄰域內(nèi)的局部極值點(diǎn)，然后選取大于給定閾值的極值點(diǎn)作為候選點(diǎn)，最后驗(yàn)證這些點(diǎn)是否在DOG算子尺度空間上獲得極值，若能獲得極值，則是特征點(diǎn)；否則舍棄。算法步驟：首先利用單尺度Harris特征點(diǎn)提取算法初步得到圖像中的粗特征點(diǎn)，以保證特征點(diǎn)提取的高效；然后結(jié)合多尺度空間理論，進(jìn)行高斯差分算子得到抗尺度變化的特征點(diǎn)，剔除初步粗特征點(diǎn)中對于尺度變化時新產(chǎn)生或者發(fā)生偏移的特征點(diǎn)；再根據(jù)描述符方法思想，利用計(jì)算起來比較簡單的信息，對剔除掉隨尺度變化的特征點(diǎn)后剩余特征點(diǎn)進(jìn)行描述，以使穩(wěn)定的特征點(diǎn)信息更準(zhǔn)確。多尺度下提取圖像的特征點(diǎn)，將尺度看作是附加在圖像空間上的一維連續(xù)變化的坐標(biāo)。根據(jù)局部不變SIFT特征點(diǎn)提取算法，利用少量的局部信息，例如特征點(diǎn)周圍的小圖像塊的統(tǒng)計(jì)信息或高斯導(dǎo)數(shù)構(gòu)成特征向量，利用SIFT方法從圖像中提取出的特征點(diǎn)可以用于一個物體或場景不同視角下的可靠匹配，提取出的特征點(diǎn)對圖像尺度和旋轉(zhuǎn)保持不變，對光線變化、噪聲、部分仿射變化都具有魯棒性，但是由于SIFT算法在進(jìn)行特征點(diǎn)的描述時，在選擇的尺度上，在每個關(guān)鍵點(diǎn)的鄰域計(jì)算局部圖像梯度的方向直方圖并且將轉(zhuǎn)換為128維的特征描述符，使算法對于特征點(diǎn)檢測的效率下降，同時由于該方法利用特征點(diǎn)構(gòu)造的128維向量進(jìn)行匹配，這樣圖像就得滿足足夠多的紋理，否則構(gòu)造出的特征向量區(qū)別性就不是太大，容易造成誤匹配，極限情況如指紋圖像的匹配，星圖識別等這類圖像特征點(diǎn)周圍根本沒有什么紋理，這時SIFT算法就完全失效了。 本章小結(jié)本章在分析特征點(diǎn)提取重要性的基礎(chǔ)上，首先對Harris角點(diǎn)提取算法進(jìn)行研究，實(shí)驗(yàn)表明該算法檢測效率高，針對圖像存在旋轉(zhuǎn)情況下有很高的點(diǎn)重復(fù)率，是一種比較有效的點(diǎn)特征提取算法，但它在尺度和噪聲發(fā)生變化情況下表現(xiàn)的魯棒性差；針對Harris 算法的不足，對局部不變特征點(diǎn)提取SIFT算法進(jìn)行研究，實(shí)驗(yàn)表明該算法提取出的特征點(diǎn)對圖像的旋轉(zhuǎn)、縮放及光照、噪聲變化時表現(xiàn)出較強(qiáng)的魯棒性，但該算法速度較慢，并且要求圖像滿足足夠多的紋理。(d)與(e)為對應(yīng)的一個特征區(qū)域的局部放大圖像，從圖中可以看出，這兩個區(qū)域內(nèi)容基本相同。實(shí)驗(yàn)實(shí)現(xiàn)SIFT及最近鄰匹配算法時，利用了開源函數(shù)庫(OpenCV)，它包含了一系列C函數(shù)和少量C++類。在梯度方向直方圖中，當(dāng)存在另一個相當(dāng)于主峰值80%能量的峰值時，則將這個方向認(rèn)為是該關(guān)鍵點(diǎn)的輔方向。主曲率通過一個22的Hessian矩陣H求出: ()導(dǎo)數(shù)由采樣點(diǎn)相鄰差估計(jì)得到。在文中取為，第二層濾波因子增加k倍，依次增加濾波因子直到最高層第五層。首先對圖像進(jìn)行預(yù)處理以消除圖像模糊，對提取穩(wěn)定的特征點(diǎn)有好處。 SIFT特征點(diǎn)提取算法原理及步驟SIFT算法是Lowe[14]利用尺度空間性質(zhì)提出的一種尺度不變關(guān)鍵點(diǎn)的檢測方法，主要利用目標(biāo)局部區(qū)域的信息來構(gòu)造特征量，它以同時在尺度域和空間域取得極值的點(diǎn)作為關(guān)鍵點(diǎn)，并以關(guān)鍵點(diǎn)作為特征區(qū)域的中心，同時關(guān)鍵點(diǎn)所在的尺度還用以確定特征區(qū)域的大小，在每個特征區(qū)域內(nèi)以梯度方向的直方圖為基礎(chǔ)得到局部不變特征向量。(a)閾值設(shè)置為5000(b)閾值設(shè)置為10000(c)閾值設(shè)為15000(d)閾值設(shè)置為20000 設(shè)置不同閾值時角點(diǎn)提取結(jié)果圖通過對Harris算法提取圖像特征點(diǎn)的原理及實(shí)驗(yàn)結(jié)果分析，可以看出Harris算法在圖像存在旋轉(zhuǎn)情況下有很高的點(diǎn)重復(fù)數(shù)，是一種比較有效的點(diǎn)特征提取算法。實(shí)驗(yàn)所提取的角點(diǎn)用十字劃線來標(biāo)識。實(shí)際運(yùn)用中用來計(jì)算角點(diǎn)的響應(yīng)函數(shù)可以寫成： ()其中，當(dāng)某個區(qū)域矩陣的主對角線之和很大時，則表明這是一條邊；當(dāng)矩陣的行列式很大時，則表明這是一條邊或一個角點(diǎn)。目前在圖像匹配中，常見的基于灰度的角點(diǎn)提取算法主要有Moravec算法，SUSAN算法和Harris算法等。圖像特征點(diǎn)提取及匹配算法研究 第二章 圖像特征點(diǎn)提取算法研究第二章 圖像特征點(diǎn)提取算法研究圖像特征點(diǎn)提取是圖像處理和計(jì)算機(jī)視覺的基本技術(shù)，它也是特征點(diǎn)匹配方法的首要步驟。基于描述符的匹配方法對有效點(diǎn)的要求低，適合圖像視角變換、輕微變形情況，但是實(shí)現(xiàn)復(fù)雜，對圖像紋理要就比較高；而基于幾何結(jié)構(gòu)的匹配方法實(shí)現(xiàn)簡單、紋理要求低，但是抗圖像形變、視角變化能力差，算法時間復(fù)雜度比較高。由于時間、視角、環(huán)境的變化、多種傳感器的使用等，使拍攝的圖像不僅受到噪聲的影響，而且存在嚴(yán)重的灰度失真和幾何畸變。2)基于特征點(diǎn)幾何結(jié)構(gòu)的匹配方法[20]。這樣使匹配算法能夠簡化為只考慮有平移、旋轉(zhuǎn)的情況下求解點(diǎn)集之間的對應(yīng)關(guān)系，但在很多實(shí)際應(yīng)用中，由于存在圖像噪聲及視場變換還有不同時間和不同傳感器獲取的圖像等因素，待匹配的兩幅圖像中不可避免出現(xiàn)虛假點(diǎn)、丟失點(diǎn)以及非剛性形變。除此之外，各種匹配方法所采用的優(yōu)化算法也不盡相同，有的使用全局優(yōu)化算法，如動態(tài)規(guī)劃法、窮舉法、凸規(guī)劃法和松弛法等；還有的使用一些非全局最優(yōu)算法，如貪婪算法，模擬退火算法和隨機(jī)搜索算法等。當(dāng)相比于SIFT，SURF的速度要更快，但是在圖像出現(xiàn)視角和光照變化上匹配的效果沒有SIFT好。下面將分析和比較不同方法如何解決這兩個問題。主要缺點(diǎn)是對邊緣提