【正文】 三點(diǎn)組成的三角形就稱之為三角形。定義 ：從兩幅圖像中任意選擇兩個(gè)三角形，它們組成一個(gè)三角形對(duì)。定義 ：如果一個(gè)三角形對(duì)中的兩個(gè)三角形的三個(gè)頂點(diǎn)對(duì)應(yīng)匹配，則稱它們?yōu)橐粋€(gè)匹配三角形對(duì)。三角形具有旋轉(zhuǎn)、平移、伸縮變化不變性的特點(diǎn)，每一個(gè)三角形包含兩個(gè)獨(dú)立的不變的形狀參數(shù)，參數(shù)的表示方法有很多種，常選擇使用三角形邊的比率來表示：參數(shù)1是三角形中間長(zhǎng)度的邊與最長(zhǎng)邊的比，參數(shù)2是三角形最短邊長(zhǎng)與最長(zhǎng)邊的比，a，b與c是三角形的三條邊，且。通過定義可知,并且，同時(shí)。 三角空間的三角形特征由空間中的三個(gè)點(diǎn)構(gòu)成的三角形就可以轉(zhuǎn)換成空間中用一個(gè)點(diǎn)來表示。由上面的定義可知，三角形映射到三角空間中是被限制在一個(gè)三角形區(qū)域中()，但是對(duì)于相似三角形，無論它如何平移、旋轉(zhuǎn)或縮放，它總是投影在空間的同一點(diǎn)。兩個(gè)圖像中的三角形在三角空間中的對(duì)應(yīng)點(diǎn)之間的距離在范圍內(nèi)，就認(rèn)為它們相互匹配，即為一個(gè)三角形匹配對(duì)。2． 三角形匹配窮舉方法就是用A組中的每一個(gè)三角形去和B組中的每一個(gè)三角形進(jìn)行比較，而每一次的比較都涉及到笛卡爾距離的計(jì)算。然而對(duì)三角空間中的B組坐標(biāo)分別按照進(jìn)行排序，再使用折半查找法能夠迅速地在組B中找到開始點(diǎn)，只有那些落在范圍之內(nèi)的點(diǎn)需要進(jìn)行比較，能夠避免大量的比較。確定匹配點(diǎn)。指派兩組點(diǎn)模式之間候選點(diǎn)的匹配是基于這樣的思想：當(dāng)存在很多個(gè)點(diǎn)時(shí)，將會(huì)在包含對(duì)應(yīng)點(diǎn)的三角形之間出現(xiàn)過剩的匹配。換句話說，A組的一個(gè)點(diǎn)作為很多匹配的三角形的一部分，而這些三角形在B組有著對(duì)應(yīng)點(diǎn)。為了計(jì)算A組的點(diǎn)i和B組的點(diǎn)j具有共同的三角形的數(shù)目，定義的權(quán)值二維表，并初始化為零。每一組匹配上的三角形，對(duì)于構(gòu)成三角形的每個(gè)點(diǎn)，其在權(quán)值矩陣中的元素的權(quán)值被加1。通過加權(quán)后，權(quán)值矩陣中數(shù)值大的元素對(duì)應(yīng)著匹配點(diǎn)。權(quán)值矩陣由兩組點(diǎn)對(duì)組成。很明顯點(diǎn)對(duì)的權(quán)值越高，點(diǎn)對(duì)為真正的配對(duì)的可能性越大。一種方法是給權(quán)值應(yīng)用一個(gè)閾值，通過控制這個(gè)閾值的大小來控制隨機(jī)誤匹配點(diǎn)的數(shù)目及真正點(diǎn)匹配對(duì)的數(shù)目。估計(jì)這些數(shù)目是很難的，需要依靠許多參數(shù)來完成，比如參與匹配的點(diǎn)的個(gè)數(shù)，數(shù)組中數(shù)據(jù)排序程度等。3. 減少誤匹配點(diǎn)擴(kuò)展三角空間可以減少誤匹配?？赡艿臄U(kuò)展是包括一個(gè)與三角形尺寸有關(guān)的規(guī)范化參數(shù)，如三角形面積、周長(zhǎng)。規(guī)范化可能是一組中所有三角形關(guān)于這個(gè)屬性的平均值。規(guī)范化使得參數(shù)比例穩(wěn)定，相似三角形具有相似的參數(shù)值。這個(gè)思想在于運(yùn)用這些參數(shù)可以限制一些匹配，比如比較大的三角形僅僅和比較大的三角形匹配。這個(gè)方法很具有直覺性，是人類視覺識(shí)別相似三角形的部分技能。4. 匹配流程1) 由兩幅圖像所有特征點(diǎn)任意組合成的三角形集合，分別記為A、B；2) 構(gòu)建權(quán)值矩陣M。假設(shè)A、B分別有m和n個(gè)點(diǎn)，表示匹配相似三角形對(duì)中出現(xiàn)的次數(shù)，通過設(shè)定閾值確定三角形匹配對(duì)；3) 減少誤匹配。4) 經(jīng)過上面層層篩選，進(jìn)而得到最終的匹配點(diǎn)。 三角形相似方法局限性假設(shè)兩特征點(diǎn)集的數(shù)量都為，每個(gè)點(diǎn)集將構(gòu)成個(gè)三角形，方法需要對(duì)每對(duì)三角形進(jìn)行相似性判定，時(shí)間復(fù)雜度。而且判定方法還需牽涉到較為復(fù)雜的除法和比較操作。且未利用其他信息對(duì)一些偽匹配三角形進(jìn)行剔除，造成相似三角形對(duì)數(shù)過多，容易造成誤匹配。再者當(dāng)模板點(diǎn)集中的一個(gè)點(diǎn)與目標(biāo)點(diǎn)集中多個(gè)點(diǎn)匹配這種情況出現(xiàn)時(shí)，特征點(diǎn)的對(duì)應(yīng)關(guān)系就找不出來了。 改進(jìn)的相似三角形匹配方法實(shí)現(xiàn)根據(jù)以上對(duì)于傳統(tǒng)三角形特征點(diǎn)匹配算法的原理及局限性分析，針對(duì)傳統(tǒng)三角形匹配算法時(shí)間復(fù)雜度高，使用單模板匹配的局限性，通過引入基線及基線三角形組的概念，由復(fù)數(shù)相乘的幾何意義，將圖像特征點(diǎn)轉(zhuǎn)移到復(fù)數(shù)向量空間中求解，不僅使算法的效率得到提高，同時(shí)也增強(qiáng)了算法的可靠性。下面進(jìn)行改進(jìn)相似三角形匹配方法的具體研究與實(shí)現(xiàn)。：選取圖像點(diǎn)集中任意兩個(gè)特征點(diǎn)、則定義向量為圖像中的一條基線。：在選取圖像中的一條基線后，以與以點(diǎn)集中其余特征點(diǎn)為頂點(diǎn)組成對(duì)應(yīng)于的三角形組，則稱該三角形組為基線的三角形組。算法步驟：首先提取圖像特征點(diǎn)，在圖像中選取特征值較高且分布均勻的特征點(diǎn)構(gòu)成特征點(diǎn)集，并根據(jù)圖像特征點(diǎn)間的歐氏距離及描述符信息條件選擇滿足要求的基線，構(gòu)造基線三角形組形成相應(yīng)基線的三角形集合；然后從模版圖像的基線三角形集合中選取三角形子模版，對(duì)實(shí)物圖像中的特征點(diǎn)進(jìn)行相似三角形檢索，當(dāng)找到基線所對(duì)應(yīng)三角形的頂點(diǎn)幾何位置時(shí)，在判斷它是否為特征點(diǎn)基礎(chǔ)上，進(jìn)一步結(jié)合該特征點(diǎn)位置的描述符信息剔除偽匹配三角形，在實(shí)物圖像中準(zhǔn)確定位出模版圖像。 匹配算法流程 三角形選取方案研究1. 改進(jìn)選取三角形思路根據(jù)傳統(tǒng)的基于相似三角形匹配方法，模板圖像中個(gè)特征點(diǎn)，任意可組成個(gè)三角形，然后逐個(gè)使用每個(gè)三角形在實(shí)物圖像中尋找相似三角形，是一種被動(dòng)檢索方式，顯然這種方法基數(shù)非常大，所需要比較的三角形個(gè)數(shù)很多，時(shí)間復(fù)雜度也就相應(yīng)的增加。本章改進(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ù)雜度由降為。2. 奇異三角形的去除奇異三角形是指存在夾角近似于或的三角形()。奇異三角形，由于這些三角形面積狹小及邊和邊之間的關(guān)系不明顯而不利于模版圖像的定位，所以不被選為子模版三角形。三角空間有一個(gè)特點(diǎn)，如果兩點(diǎn)靠得很近，也就是說有兩個(gè)點(diǎn)的坐標(biāo)距離相當(dāng)小，將在三角空間的某個(gè)角出現(xiàn)大量的點(diǎn)。這些三角形很難進(jìn)行相似判定。另一方面，給定三角空間一個(gè)固定的容錯(cuò)量，那么這些靠的很近的點(diǎn)對(duì)，將大量地被篩選為相似匹配(或非相似匹配)。于是，通過限制三角形的形成來減少誤匹配的可能及處理三角形的配對(duì)。 相似三角形檢索方法改進(jìn)由于同向相似三角形檢索首先需要對(duì)三角形進(jìn)行相似性判斷，然后進(jìn)行同向性判斷。設(shè)實(shí)物圖像中提取出個(gè)特征點(diǎn)，傳統(tǒng)的同向相似三角形檢索需要對(duì)個(gè)點(diǎn)組成的個(gè)三角形進(jìn)行同向相似性判斷，三角形相似性判斷方法目前已經(jīng)相當(dāng)成熟。下面給出兩三角形同向的判斷條件及證明。：的頂點(diǎn)坐標(biāo)為，，對(duì)應(yīng)頂點(diǎn)坐標(biāo)分別為，，則與頂點(diǎn)同方向排列的充分必要條件是()證明：將點(diǎn)、和點(diǎn)、看作空間直角坐標(biāo)系下的點(diǎn)，可得，，。則點(diǎn)、與點(diǎn)、同向排列的充要條件是向量和的向量積與向量和的向量積同向。() ()其中：,分別是三個(gè)坐標(biāo)軸上的單位向量。易知同向的充要條件就是滿足式()。證畢。，不能由旋轉(zhuǎn)得到。 不同向的兩相似三角形很顯然傳統(tǒng)的同向相似三角形檢索時(shí)間復(fù)雜度為，且過程涉及到大量的除法和比較運(yùn)算。本文將采用一種主動(dòng)的相似三角形檢索方法，時(shí)間復(fù)雜度僅為。且根據(jù)復(fù)數(shù)相乘的幾何意義，將圖像特征點(diǎn)轉(zhuǎn)移到復(fù)數(shù)向量空間中求解，大大提高了算法效率。 給定邊與的邊對(duì)應(yīng)，那么將存在唯一的點(diǎn)使與同向相似。證明：假設(shè)對(duì)應(yīng)邊長(zhǎng)分別為。邊的長(zhǎng)度為，根據(jù)三角形相似原理可知：邊的長(zhǎng)度與邊的長(zhǎng)度可由下式求出：()分別以點(diǎn)、為圓心，、為半徑做圓、。由三角形三邊之間的關(guān)系及式()可得：() 由式()知兩圓必交于不同的兩點(diǎn)，且兩點(diǎn)關(guān)于邊對(duì)稱。這樣就得到兩個(gè)與相似的三角形，這兩個(gè)三角形反向相似，其中有且僅有一個(gè)三角形與同向相似，且對(duì)應(yīng)的交點(diǎn)即為要求的點(diǎn)，證畢。，同向相似三角形檢索只需對(duì)條對(duì)應(yīng)邊求出對(duì)應(yīng)點(diǎn)，然后判斷點(diǎn)是否為特征點(diǎn)即可。對(duì)點(diǎn)是否為特征點(diǎn)的判斷，只需在保存實(shí)物圖像特征點(diǎn)的二維布爾值數(shù)組中檢查點(diǎn)對(duì)應(yīng)的值是否為真即可，算法復(fù)雜度為。然而，則需要求解二元二次方程組以及進(jìn)行同向性判斷，計(jì)算過程比較復(fù)雜，下面將采用另一種方法求解點(diǎn)。在復(fù)數(shù)向量空間中，(a)，由向量與向量唯一確定。(b)，假設(shè)其與向量對(duì)應(yīng)，則算法只要找出點(diǎn)，使向量與向量所確定的與模板為同向相似三角形即可。，點(diǎn)存在且唯一。根據(jù)三角形相似判定定理：兩邊對(duì)應(yīng)成比例且夾角相等，則兩三角形相似。假設(shè)中向量到向量的角度為，與的比值為，可知只需中向量到向量的角度為，與的比值為，則與同向相似。根據(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)被確定。稱復(fù)數(shù)為旋轉(zhuǎn)因子，可由向量對(duì)應(yīng)的復(fù)數(shù)與向量對(duì)應(yīng)的復(fù)數(shù)相除得到。 同向相似三角形 多模板改進(jìn)方法分析相似三角形的特征點(diǎn)匹配方法利用了三角形的平移、旋轉(zhuǎn)、縮放不變性，傳統(tǒng)的判定方法目前已經(jīng)比較成熟，所以在對(duì)于旋轉(zhuǎn)和縮放這類圖像匹配的應(yīng)用方面，具有較為突出的優(yōu)越性。方法通過選取模板圖像中三角形子模板對(duì)實(shí)物圖像特征點(diǎn)進(jìn)行同向相似三角形檢索，來實(shí)現(xiàn)模板圖像的粗匹配，可以在很大程度上減少傳統(tǒng)圖像匹配方法的搜索空間。但當(dāng)模板三角形特征點(diǎn)中含有出格點(diǎn)時(shí)，則檢索出的匹配三角形集合中就不會(huì)含有同名匹配三角形，從而得不到準(zhǔn)確的匹配位置。所以用單個(gè)三角形模板進(jìn)行匹配是不可靠的，在本文提出的改進(jìn)方法中將考慮用多個(gè)三角形模板進(jìn)行匹配，具體是通過使用基線的三角形組形成多模板，使改進(jìn)方法可靠性得到改善，并且利用特征點(diǎn)的描述符信息，更合理的選擇基線，并可以剔除部分偽匹配三角形。在復(fù)數(shù)空間下得到對(duì)應(yīng)特征點(diǎn)組成向量的三角形組的基礎(chǔ)上，通過判斷實(shí)物圖中對(duì)應(yīng)于模版圖像中的基線的三角形組的頂點(diǎn)為特征點(diǎn)的數(shù)量是否達(dá)到一定閾值，若滿足閾值要求，則可以認(rèn)為在實(shí)物圖中找到一個(gè)模版圖像，同理遍歷模版圖像中的所有基線，進(jìn)行相似三角形檢索，找到實(shí)物圖中所有的模版圖像。在復(fù)數(shù)向量空間中，從特征點(diǎn)集中結(jié)合特征點(diǎn)的描述符信息，根據(jù)與模板圖像對(duì)應(yīng)特征向量的屬性相似度，從實(shí)物圖中選擇基線，以其余所有的特征點(diǎn)與構(gòu)成三角形組，具體方法以構(gòu)造為例說明如下()：由模版圖對(duì)應(yīng)的復(fù)數(shù)與對(duì)應(yīng)的復(fù)數(shù)相除得到旋轉(zhuǎn)因子，運(yùn)用旋轉(zhuǎn)因子找出點(diǎn)，使與所確定的三角形與模板為同向相似三角形。在得到以為基線構(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ì)性和有效性。A(a)模板圖像三角形 (b)實(shí)物圖像中三角形 相似三角形本章改進(jìn)算法是在現(xiàn)有相似三角形匹配算法的基礎(chǔ)上，通過選取模板圖像中特征點(diǎn)組成基線的相應(yīng)三角形組后，對(duì)實(shí)物圖像相應(yīng)特征點(diǎn)組成的基線進(jìn)行對(duì)應(yīng)的相似三角形檢索來實(shí)現(xiàn)模板圖像的定位，從而很大程度上減少了傳統(tǒng)模板匹配方法的搜索空間，提高了搜索的效率。并且通過構(gòu)造基線三角形組的思想，使匹配模板由單個(gè)模板變?yōu)槎鄠€(gè)模板，提高了搜索策略的可靠性。同時(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)一步提高。改進(jìn)的相似三角形匹配方法步驟如下：1) 模板圖像特征點(diǎn)構(gòu)造點(diǎn)集，以點(diǎn)集組成個(gè)不同的向量作為基線，選擇未處理的基線，將模板三角形轉(zhuǎn)到復(fù)數(shù)向量空間中，通過向量和向量，計(jì)算出旋轉(zhuǎn)因子；2) 實(shí)物圖像特征點(diǎn)構(gòu)造點(diǎn)集，以點(diǎn)集組成個(gè)不同的向量，結(jié)合H/S算法提取得到特征點(diǎn)的描述符信息，選取與模板圖像基線描述符信息相似的向量作為基線，如果個(gè)向量都處理完，則轉(zhuǎn)步驟5。否則從中選取一個(gè)未處理的向量，與模板中向量對(duì)應(yīng)，根據(jù)旋轉(zhuǎn)因子，計(jì)算出向量，確定點(diǎn)的坐標(biāo)；3) 判斷實(shí)物圖像中周邊很小的范圍內(nèi)是否有一個(gè)特征點(diǎn)。如果是，則進(jìn)一步判斷該位置特征點(diǎn)的描述符信息與模板圖中對(duì)應(yīng)相似三角形頂點(diǎn)的描述符信息相似度，若相似度滿足要求則輸出為模板的一同向相似三角形，并設(shè)置特征點(diǎn)數(shù)量記錄匹配到的同向相似三角形的數(shù)目；4) 判斷與模板圖中對(duì)應(yīng)基線的三角形組的頂點(diǎn)數(shù)量關(guān)系，若值達(dá)到一定的閾值，則輸出在模板圖像中匹配到一個(gè)模板圖像，并用矩形框?qū)⑵錁?biāo)識(shí)出；轉(zhuǎn)步驟2，繼續(xù)判斷實(shí)物圖中特征點(diǎn)集合中的其它基線；5) 算法結(jié)束。 實(shí)驗(yàn)結(jié)果與分析實(shí)驗(yàn)實(shí)現(xiàn)改進(jìn)的相似三角形特征點(diǎn)匹配算法，驗(yàn)證其在圖像存在旋轉(zhuǎn)、縮放、噪聲以及復(fù)雜背景下物體識(shí)別的準(zhǔn)確性及算法效率。實(shí)驗(yàn)中提取出角點(diǎn)用十字劃線標(biāo)識(shí)，并用矩形框標(biāo)識(shí)出實(shí)物圖像中識(shí)別出的模板圖。實(shí)驗(yàn)使用VC++，首先利用H/S特征點(diǎn)提取算法提取出圖像中特征點(diǎn)，得到待匹配的兩幅圖像對(duì)應(yīng)特征點(diǎn)集。1. 模板圖像旋轉(zhuǎn)、縮放時(shí)匹配、縮放時(shí)匹配結(jié)果，(a)為模板圖，(b)為實(shí)物圖，在(b)中存在與(a)相同、旋轉(zhuǎn)、尺度變化、旋轉(zhuǎn)縮放共存的模板圖，用矩形標(biāo)識(shí)出實(shí)物圖中存在的模板圖，實(shí)驗(yàn)結(jié)果表明該算法對(duì)于圖像存在旋轉(zhuǎn)、縮放情況下的有效性。(a)模板圖(b)實(shí)物圖 模板圖像存在旋轉(zhuǎn)、縮放時(shí)匹配結(jié)果圖2. 存在噪聲圖像匹配。(a)為在模板圖，(b)為將實(shí)物圖增加噪聲后得到的匹配結(jié)果，實(shí)驗(yàn)結(jié)果表明在實(shí)物圖受噪聲干擾情況下，該算法仍能準(zhǔn)確找到發(fā)生旋轉(zhuǎn)、縮放情況的模板圖像，同時(shí)也驗(yàn)證了改進(jìn)H/S算法提取角點(diǎn)特征點(diǎn)的有效性。(a)模板圖(b)添加噪聲圖 圖像存在噪聲時(shí)匹配結(jié)果圖3. 背景較復(fù)雜時(shí)圖像匹配使用GoogleEarth上截得的搖感圖像圖像匹配，(a)模板圖像經(jīng)過90度旋轉(zhuǎn)，并存在一定尺度放大，結(jié)果顯示該方法準(zhǔn)確的在實(shí)物圖中找到相應(yīng)模板圖像，體現(xiàn)該算法在復(fù)雜背景下識(shí)別目標(biāo)物體的實(shí)用性。(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)造方法。改進(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)的描述符信息，提高了