改進(jìn)MSAC估計(jì)F與H矩陣在匹配點(diǎn)中的提純

李 城，王仁禮，王成港，明平壽

(山東科技大學(xué)山東省基礎(chǔ)地理信息與數(shù)字化技術(shù)重點(diǎn)實(shí)驗(yàn)室，山東 青島 266590)

尋找兩幅影像相同場(chǎng)景或物體的同名點(diǎn)在攝影測(cè)量與計(jì)算機(jī)視覺領(lǐng)域有著諸多應(yīng)用，如相機(jī)標(biāo)定[1]、三維重建、影像校正[2-3]、影像拼接[4]和特征追蹤等。然而影像匹配難免會(huì)存在誤匹配，錯(cuò)誤的對(duì)應(yīng)關(guān)系會(huì)直接影響后續(xù)的工作。對(duì)多視影像來講，通常采用兩種約束：一是極線約束，即點(diǎn)與線的對(duì)應(yīng)關(guān)系；二是單應(yīng)約束，即點(diǎn)與點(diǎn)的對(duì)應(yīng)關(guān)系。因此，常常估計(jì)基本矩陣或單應(yīng)矩陣來剔除誤匹配點(diǎn)。到目前為止，基本矩陣/單應(yīng)矩陣的估計(jì)方法可分為線性估計(jì)方法、迭代估計(jì)方法和穩(wěn)健估計(jì)方法。其中線性估計(jì)方法代表有8點(diǎn)算法；迭代估計(jì)算法中最具代表性的為非線性最小二乘法；穩(wěn)健性算法是最具有抗噪性的算法，其主要分為非隨機(jī)抽樣算法如M估計(jì)算法[5]、LMedS[6]、LTS[7]和隨機(jī)抽樣算法如RANSAC[5,8]、MSAC[9]、MLESAC[9]等一系列通過修改RANSAC代價(jià)函數(shù)的衍生算法。但是非隨機(jī)抽樣算法只能容忍不超過50%的“潰點(diǎn)”[7]，限制了它們的適用性[10]。故穩(wěn)健隨機(jī)抽樣算法在目前廣泛應(yīng)用，然而又因?yàn)殡S機(jī)抽樣算法沒有考慮到抽取特征點(diǎn)的位置，這就有可能造成抽取的樣本成線性分布或彼此之間太過緊湊，從而導(dǎo)致估計(jì)的F/H矩陣準(zhǔn)確性下降，因此本文通過改進(jìn)其抽樣模式來盡可能地避免這一劣勢(shì)。同時(shí)，本文在基于改進(jìn)MSAC算法估計(jì)F/H矩陣的基礎(chǔ)上，采用不同地物類型的影像，通過大量試驗(yàn)比較了兩種提純方式的適用場(chǎng)景。

1 算法原理

1.1 基本矩陣

在計(jì)算機(jī)視覺中，立體像對(duì)的同名點(diǎn)之間必關(guān)聯(lián)一個(gè)3×3的基本矩陣；在對(duì)極幾何中，基本矩陣是同名點(diǎn)的齊次坐標(biāo)x與x′的對(duì)應(yīng)關(guān)系，F(xiàn)x描述的是另一幅影像上的同名點(diǎn)x′所在的極線[7]，這就意味著所有的同名點(diǎn)必滿足

(1)

這種約束有利于搜索和檢測(cè)錯(cuò)誤的對(duì)應(yīng)關(guān)系。換言之，基本矩陣描述的同名點(diǎn)之間的關(guān)系也可被稱為極線約束。

1.2 單應(yīng)矩陣

平面單應(yīng)性是基本矩陣的一種特殊形式，即當(dāng)所有的物點(diǎn)都位于同一平面上時(shí)，兩幅影像同名點(diǎn)之間存在一一對(duì)應(yīng)的關(guān)系，這種關(guān)系可以用單應(yīng)矩陣來描述，其實(shí)質(zhì)是一種嚴(yán)格的透視變換關(guān)系[8,11-13]。

X2=P′X=[A|a]X=AX1-avTX1=(A-avT)=HX1

(2)

圖1 平面單應(yīng)

將式(2)展開即得：

(3)

1.3 基本矩陣與單應(yīng)矩陣的聯(lián)系與區(qū)別

1.4 改進(jìn)MSAC估計(jì)F和H矩陣

MSAC算法是RANSAC的變體，通過對(duì)RANSAC代價(jià)函數(shù)的修改，克服了RANSAC對(duì)閾值敏感的缺點(diǎn)。同時(shí)，MSAC算法不僅反映了模型數(shù)據(jù)的數(shù)目，而且反映了模型數(shù)據(jù)的擬合程度，因此在整體上要優(yōu)于RANSAC算法。但是，同RANSAC算法一樣，它們均是隨機(jī)抽樣算法，每次抽取樣本的分布情況對(duì)估計(jì)的基本矩陣/單應(yīng)矩陣的性能有影響[15]。因此，本文在抽樣時(shí)，以所有匹配點(diǎn)集的質(zhì)心為基準(zhǔn)點(diǎn)建立坐標(biāo)系，使樣本點(diǎn)分布在4個(gè)象限，且樣本點(diǎn)兩兩之間的距離大于某個(gè)閾值，以便盡可能地均勻分布于整個(gè)重疊區(qū)域，避免了估計(jì)的基本矩陣/單應(yīng)矩陣是局部最優(yōu)而非整體最優(yōu)。

改進(jìn)后的MSAC算法估計(jì)F和H矩陣步驟如下：

(1) 初始化3*3的F/H為零矩陣。

(2) 設(shè)置計(jì)數(shù)器n=0和循環(huán)次數(shù)N。

(3) 設(shè)置條件當(dāng)n

a. 以像對(duì)匹配點(diǎn)集的質(zhì)心為原點(diǎn)建立坐標(biāo)系。

b. 使用隨機(jī)器產(chǎn)生8對(duì)同名點(diǎn)對(duì)或4對(duì)同名點(diǎn)對(duì)。

c. 若樣本點(diǎn)沒有分布在4個(gè)象限且兩兩之間的距離小于某個(gè)閾值，重復(fù)步驟b；反之，進(jìn)行下一步。

d. 計(jì)算基本矩陣/單應(yīng)矩陣(f/h)。

e. 計(jì)算除樣本點(diǎn)外所有剩余同名點(diǎn)的擬合程度。

f. 如果f/h的擬合優(yōu)于F/H，用f/h替換F/H，更新循環(huán)次數(shù)N。

g. 計(jì)數(shù)器累加，直至達(dá)到最后的抽樣次數(shù)N。

(4) 若提前達(dá)到符合數(shù)目的模型(如85%的內(nèi)點(diǎn))，則提前跳出循環(huán)。

(5) 記錄含有最多內(nèi)點(diǎn)的模型，該模型為最優(yōu)的F/H。

2 試驗(yàn)結(jié)果與分析

2.1 改進(jìn)MSAC算法抽樣模式的試驗(yàn)效果

本文改進(jìn)了抽樣模式，使得每次抽樣盡可能均勻分布，且避免了抽取的樣本太過聚集而導(dǎo)致估計(jì)的基本矩陣/單應(yīng)矩陣不能反映整體狀況。本文每對(duì)像對(duì)進(jìn)行6次試驗(yàn)，比較改進(jìn)前與改進(jìn)后的MSAC算法剔除誤匹配點(diǎn)后的最終匹配點(diǎn)數(shù)目，見表1。

表1 改進(jìn)前(方法1)與改進(jìn)后(方法2)的對(duì)比

由表1可以看出，當(dāng)匹配點(diǎn)數(shù)目不多時(shí)，改進(jìn)后效果不是太明顯。而當(dāng)匹配點(diǎn)數(shù)目較多時(shí)，改進(jìn)前每次提純之后的結(jié)果最大差異達(dá)到了約100個(gè)匹配點(diǎn)，但此時(shí)改進(jìn)后每次提純之后的結(jié)果最大差異不超過50個(gè)匹配點(diǎn)。因此，在不影響匹配點(diǎn)數(shù)目的情況下，改進(jìn)MSAC算法的抽樣模式使得每次提純之后的結(jié)果相對(duì)穩(wěn)定。

2.2 F和H矩陣提純效果

分別選取10對(duì)平坦地區(qū)的航片像對(duì)和具有明顯地形起伏的航片像對(duì)進(jìn)行試驗(yàn)，影像大小皆為6000×4000。圖2是平坦地區(qū)和地形起伏地區(qū)的部分航片圖，圖3是平坦地區(qū)和地形起伏地區(qū)的試驗(yàn)結(jié)果。

圖2 部分試驗(yàn)影像

圖3

因?yàn)楦倪M(jìn)后的MSAC算法依然是不確定模型，所以每一對(duì)影像的最終匹配點(diǎn)數(shù)目取100次結(jié)果的平均值。圖3(a)試驗(yàn)影像的第1對(duì)、第2對(duì)和第3對(duì)是田地、第4對(duì)、第5對(duì)和第6對(duì)是草地，剩下的是小的灌木林地，根據(jù)試驗(yàn)結(jié)果可以看出，對(duì)于影像中的場(chǎng)景是平面或者近似平面的話，經(jīng)過估計(jì)基本矩陣和單應(yīng)矩陣剔除完誤匹配后，兩者最終的匹配點(diǎn)數(shù)目相差不大。但是有一點(diǎn)值得注意，當(dāng)抽樣所選的同名點(diǎn)都滿足共面的話，所估計(jì)的基本矩陣就會(huì)退化，即所計(jì)算的基本矩陣不準(zhǔn)確，這便會(huì)導(dǎo)致在剔除誤點(diǎn)時(shí)，有些錯(cuò)誤的點(diǎn)也會(huì)被認(rèn)為滿足極限約束。如圖4所示，以平坦地區(qū)的田地為例，1—12號(hào)點(diǎn)對(duì)是正確的匹配點(diǎn)，13—18號(hào)點(diǎn)對(duì)是人為添加的錯(cuò)誤匹配點(diǎn)。經(jīng)過單應(yīng)矩陣和基本矩陣提純之后，如圖5所示，在基本矩陣提純的情況下，14、17、18號(hào)點(diǎn)仍然被認(rèn)為是內(nèi)點(diǎn)，而在單應(yīng)矩陣提純的情況下，在平面影像上，其利用匹配點(diǎn)二維約束的強(qiáng)限制條件，人工添加的誤點(diǎn)全部被剔除。

圖4 匹配點(diǎn)分布

圖5 提純結(jié)果對(duì)比

圖3(b)試驗(yàn)的前3對(duì)影像主要是以參差不齊的房屋為主，剩下的是山區(qū)影像，地形起伏很大?？梢钥闯銮?對(duì)影像中的房屋導(dǎo)致影像存在深度變化的場(chǎng)景，基于單應(yīng)矩陣剔除完誤匹配點(diǎn)后的結(jié)果開始少于基本矩陣，在隨后山區(qū)中的影像，這種視差變化更加明顯，基于單應(yīng)矩陣剔除了不少正確的點(diǎn)對(duì)，這種方法開始失效。因此當(dāng)兩幅影像的場(chǎng)景起伏非常明顯時(shí)，影像之間對(duì)應(yīng)像素之間的位置關(guān)系就不能用一個(gè)單應(yīng)矩陣H來描述，或者說此時(shí)一張影像的匹配點(diǎn)經(jīng)過單應(yīng)變換后在另一張影像上只能確定其近似(可能)位置，即可以運(yùn)用單應(yīng)矩陣預(yù)測(cè)點(diǎn)位。

3 結(jié) 語

對(duì)于誤匹配點(diǎn)的剔除，本文采用了改進(jìn)MSAC穩(wěn)健性算法估計(jì)基本矩陣和單應(yīng)矩陣進(jìn)行提純。通過大量的試驗(yàn)，驗(yàn)證了改進(jìn)MSAC算法的可行性，比較了兩種提純方式的適用場(chǎng)景，結(jié)果表明：

(1) 改進(jìn)后的MSAC算法盡可能地彌補(bǔ)了隨機(jī)抽樣的不均勻性，性能較原算法有所改善。

(2) 對(duì)于影像場(chǎng)景中幾乎沒有深度信息或變化微小的情況下，如平坦的地面或墻壁等，要利用單應(yīng)矩陣將匹配點(diǎn)一一對(duì)應(yīng)的特點(diǎn)來剔除誤匹配點(diǎn)；而當(dāng)影像場(chǎng)景中有著明顯的視差時(shí)，如地形起伏大的山區(qū)、走廊或者街道等，要估計(jì)基本矩陣來對(duì)誤匹配點(diǎn)進(jìn)行剔除。

參考文獻(xiàn)：

[1] DUAN Y N，CHEN W，WANG M Z，et al.A Relative Radiometric Correction Method for Airborne Image Using Outdoor Calibration and Image Statistics[J].IEEE Transactions on Geoscience and Remote Sensing,2014，52(8)：5164-5174.

[2] LINGER M E，GOSHTASBY A A.Aerial Image Registration for Tracking[J].IEEE Transactions on Geoscience and Remote Sensing,2015,53(4)：2137-2145.

[3] YE P，LIU F，ZHAO Z.Multiple Gaussian Mixture Models for Image Registration[J]，IEICE Transactions on Information and Systems，2014，97 (7)：1927-1929.

[4] ZARAGOZA J，CHIN T J，TRAN Q H，et al.As-projective-as-possible Image Stitching with Moving DLT[J].IEEE Conference on Computer Vision and Patlern Recognition，2013，36(7):2339-2346.

[5] TORR P H，MURRAY D W.The Development and Comparison of Robust Methods for Estimating the Fundamental Matrix[J].International Journal of Computer Vision,1997,24(3):271-300.

[6] ZHANG Z.Determining the Epipolar Geometry and Its Uncertainty：A Review[J].International Journal of Computer Vision,1996,27(2):161-195.

[7] ROUSSEEUW P J，LEROY A M.Robust Regression and Outlier Detection[J].Wiley-Interscience,2003,31(2):260-261.

[8] HARTLEY R，ZISSERMAN A.Multiple View Geometry in Computer Vision[M].[S.l.]：Cambridge University Press，2003:159-239.

[9] TORR P H S，ZISSERMAN A.MLESAC：A New Robust Estimator with Application to Estimating Image Geometry[J].Computer Vision and Image Understanding,2000，78(1)：138-156.

[10] WANG H，SUTER D.MDPE：A Very Robust Estimator for Model Fitting and Range Image Segmentation[J].International Journal of Computer Vision，2004，59(2):139-166.

[11] CHUM O，WERNER T，MATAS J.Two-View Geometry Estimation Unaffected by a Dominant Plane[J].IEEE Computer Society Conference on Computer Vision and Patlern Recognition，2005,1(1):772-779.

[12] FRAHM J M，POLLEFEYS M.RANSAC for(Quasi-)Degenerate Data (QDEGSAC)[J].IEEE Computer Society Conference on Computer Vision and Pattern Recognition，2006,1(1)：453-460.

[13] RAGURAM R，CHUM O，POLLEFEYS M，et al.USAC：A Universal Framework for Random Sample Consensus[J].IEEE Transactions on Pattern Analysis & Machine Intelligence，2013，35(8):2022-2038.

[14] LUONG Q T，F(xiàn)AUGERAS O D.The Fundamental Matrix：Theory，Algorithms，and Stability Analysis[J].International Journal of Computer Vision,1996，17(1):43-75.

[15] JO G S,LEE K S，CHANDRA D，et al.RANSAC versus CS-RANSAC[C]∥Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence.[S.l.]：AAAI,2015.