圖像匹配問題的模型研究

《圖像匹配問題的模型研究》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、2013年國防科學(xué)技術(shù)大學(xué)數(shù)學(xué)建模競賽培訓(xùn)論文1A：圖像匹配問題隊(duì)員1：白謹(jǐn)寧，九院10級(jí)，9-4-3隊(duì)員2：李明洋，九院10級(jí)，9-4-3隊(duì)員3：時(shí)云龍，九院10級(jí)，9-4-32013年5月10日目錄摘要3一、問題重述與分析4二、問題假設(shè)4三、符號(hào)說明5四、模型建立與求解54.1模型的建立54.2模型的求解6五、模型的進(jìn)一步討論11六、模型優(yōu)缺點(diǎn)12七、附錄12圖像匹配問題的模型研究摘要這是一個(gè)匹配問題的建模研究。關(guān)于匹配問題，有很多經(jīng)典的算法如模板匹配法。但模板匹配法僅能處理平移的問題，這一問題中既有平移又有旋轉(zhuǎn)，因此我們考慮先找出幾個(gè)匹配的特殊點(diǎn)，以此為突

2、破口再尋找所有點(diǎn)的匹配關(guān)系。特殊點(diǎn)的尋找我們考慮了尋找全等三角形的方法。通過在兩個(gè)點(diǎn)集中尋找全等三角形，確定三角形頂點(diǎn)的對(duì)應(yīng)關(guān)系，這樣就有了三個(gè)能夠正確對(duì)應(yīng)的點(diǎn)，也就找到了突破口。對(duì)于其他所有的點(diǎn)，有兩種方法來確定對(duì)應(yīng)關(guān)系。一種是根據(jù)全等三角形坐標(biāo)的對(duì)應(yīng)關(guān)系，將點(diǎn)集一進(jìn)行坐標(biāo)變換，旋轉(zhuǎn)和平移到點(diǎn)集二，再將兩個(gè)點(diǎn)集中的點(diǎn)進(jìn)行比對(duì)。這種方法理論上沒有問題，實(shí)際操作時(shí)會(huì)產(chǎn)生有較大的誤差。于是我們引入了另一種方法，在處理其它點(diǎn)時(shí)不用坐標(biāo)旋轉(zhuǎn)和平移，而只計(jì)算距離。用任一點(diǎn)與三角形三個(gè)頂點(diǎn)的相對(duì)位置關(guān)系來確定對(duì)應(yīng)關(guān)系。這樣避免了求解過程產(chǎn)生的誤差。從計(jì)算結(jié)果來看，這一方法也

3、得到了比較好的效果。關(guān)鍵詞：匹配，全等三角形，坐標(biāo)變換，相對(duì)位置一、問題重述與分析比較不同時(shí)間采集同一景物的兩幅圖像，或者同一時(shí)間由不同傳感器采集的兩幅圖像，在眾多領(lǐng)域，如：在檢測變化方面（森林學(xué)、醫(yī)學(xué)、國防）、注冊與驗(yàn)證（衛(wèi)星圖像、地圖、指紋）以及立體成像方面都有重要應(yīng)用。其一般方法是在兩幅圖像中采用一定的方法抽取特征點(diǎn)，對(duì)特征點(diǎn)進(jìn)行匹配?，F(xiàn)設(shè)第一個(gè)點(diǎn)集有m個(gè)點(diǎn)，第二個(gè)點(diǎn)集有n個(gè)點(diǎn)，第二個(gè)點(diǎn)集是第一個(gè)點(diǎn)集經(jīng)過某個(gè)平移和旋轉(zhuǎn)得到，但由于噪聲的作用，點(diǎn)的相對(duì)位置有微小的變化，而且第一個(gè)點(diǎn)集中可能有部分點(diǎn)（稱為缺少點(diǎn)）在第二個(gè)點(diǎn)集中找不到對(duì)應(yīng)點(diǎn)，第二個(gè)點(diǎn)集中可能隨機(jī)

4、出現(xiàn)一些新的點(diǎn)（稱為偽點(diǎn)），通常m和n的大小范圍為從30到400之間。試就只有平移和既有平移又有旋轉(zhuǎn)兩種情形，設(shè)計(jì)模型與算法，解決以下三個(gè)問題：(ⅰ)找到第一個(gè)點(diǎn)集中所有的在第二個(gè)點(diǎn)集中沒有匹配的點(diǎn)；(ⅱ)找到第二個(gè)點(diǎn)集中所有的在第一個(gè)點(diǎn)集中沒有匹配的點(diǎn)；(ⅲ)對(duì)有匹配的點(diǎn)，找出正確的對(duì)應(yīng)關(guān)系。本題要求對(duì)給出的兩個(gè)點(diǎn)集進(jìn)行匹配，并找出第二個(gè)點(diǎn)集中的缺少點(diǎn)和偽點(diǎn)。在點(diǎn)集的坐標(biāo)已知的情況下，如果能首先確定兩個(gè)點(diǎn)集中幾個(gè)特殊點(diǎn)的對(duì)應(yīng)關(guān)系，那么其他的點(diǎn)就都可以根據(jù)它與這幾個(gè)特殊點(diǎn)的位置關(guān)系來找到對(duì)應(yīng)的點(diǎn)。因此，問題就可以分為兩步來解決：第一步，確定幾個(gè)特殊的點(diǎn)的對(duì)應(yīng)關(guān)系

5、；第二步，根據(jù)與這些特殊點(diǎn)的位置關(guān)系尋找其他點(diǎn)的對(duì)應(yīng)點(diǎn)。而特殊點(diǎn)的個(gè)數(shù)至少要有三個(gè)才能以此確定其它點(diǎn)的位置，因此我們考慮尋找兩個(gè)點(diǎn)集中的全等三角形，以此來確定特殊點(diǎn)。在確定其它點(diǎn)的對(duì)應(yīng)關(guān)系時(shí)，可以考慮兩種方法。一種是進(jìn)行坐標(biāo)的旋轉(zhuǎn)和平移變換，另一種是計(jì)算其它點(diǎn)與三角形的相對(duì)位置。而考慮到由于噪聲的存在，坐標(biāo)的旋轉(zhuǎn)會(huì)產(chǎn)生較大的誤差，因此用計(jì)算相對(duì)位置的方法求解對(duì)應(yīng)關(guān)系。二、問題假設(shè)假設(shè)一：兩幅圖像之間只存在平移和旋轉(zhuǎn)的變換，而不存在拉伸和壓縮變換；假設(shè)二：噪聲只對(duì)極少部分點(diǎn)產(chǎn)生較大的影響；假設(shè)三：缺少點(diǎn)和偽點(diǎn)不是普遍現(xiàn)象。三、符號(hào)說明S1：第一個(gè)點(diǎn)集；S2：第二個(gè)

6、點(diǎn)集；A、B、C：第一個(gè)點(diǎn)集中三角形的三個(gè)頂點(diǎn)；X、Y、Z：第二個(gè)點(diǎn)集中三角形的三個(gè)頂點(diǎn)；l1、l2、l3：第一個(gè)點(diǎn)集中三角形的三邊長；s1、s2、s3：第二個(gè)點(diǎn)集中三角形的三邊長；ε：誤差范圍，對(duì)應(yīng)兩條邊允許的差值百分比；λ：閾值，匹配過程中允許距離的差值；η：能正確對(duì)應(yīng)的點(diǎn)的比例的下限，低于這一比例則認(rèn)為對(duì)應(yīng)關(guān)系不正確；D1、D2、D3：點(diǎn)集S1中任一點(diǎn)與三角形ABC三個(gè)頂點(diǎn)之間的距離；d1、d2、d3：點(diǎn)集S2中任一點(diǎn)與三角形XYZ三個(gè)頂點(diǎn)之間的距離。四、模型建立與求解4.1模型的建立對(duì)應(yīng)關(guān)系的確立確立坐標(biāo)的對(duì)應(yīng)關(guān)系首先要找到兩個(gè)點(diǎn)集中相對(duì)應(yīng)的點(diǎn)構(gòu)成的全等

7、三角形。在第一個(gè)點(diǎn)集S1中任取三個(gè)點(diǎn)A(a1,a2)、B(b1,b2)、C(c1,c2)構(gòu)成三條邊互不相等的三角形（若有相等的邊則重新取點(diǎn)），三邊長分別是l1、l2、l3；在第二個(gè)點(diǎn)集S2中遍歷所有的點(diǎn)，得到三點(diǎn)X(x1,x2)、Y(y1,y2)、Z(z1,z2)構(gòu)成三角形，邊長為s1、s2、s3，將這兩個(gè)三角形進(jìn)行比較。給定一個(gè)誤差范圍百分比ε，如果對(duì)應(yīng)邊的差值都在這個(gè)范圍內(nèi)，就認(rèn)為兩個(gè)三角形全等。尋找全等三角形的C++代碼見附錄代碼一。但是考慮到噪聲的存在，按照上述方法找到的滿足要求的全等三角形有可能不是事實(shí)上的對(duì)應(yīng)的三角形。對(duì)于這一問題，我們可以先假定他們

8、就是事實(shí)上對(duì)應(yīng)的三角形，