快速合意制取樣法應用於三維電腦視覺

Efficient Consensus Sampling for Robust Model Fitting with Application to 3D Vision Problems

鄭嘉民(Chia-Ming Cheng)

指導教授 ： 賴尚宏

國立清華大學/電機資訊學院/資訊工程學系/博士(2009年)

摘要

在此論文中，我們針對穩固的資料模型比對 (robust model fitting) 問題，提出了一個新的演算法來提升傳統 RANSAC 的效能和穩定性。為了讓這個演算法具備更廣泛的實用性，我們根據以下原則來設計我們的方法：完全由資料來決定參數 (fully data driven)、容許大部分資料為錯誤的資料、追求很快速的回應。為了達到這個目的，我們提出三個主要的方法在我們的演算法中：第一，我們提出一個被稱為 consensus sampling 的技術，其主要的概念是由測試的過程中所得到資訊來改進往後取樣的策略；第二，我們發展出一個稱為 PMKA 新技巧，以用來快速地測試所取樣的模型參數中，有哪一些是更大可能性是正確的取樣，而哪一些則可以儘早被淘汰以省下測試的時間；最後，我們提出一個 coarse-to-fine 的策略，在有錯誤資料的情況下，估算出正確資料的誤差範圍 (error scale)。
我們將所發展的演算法，套用於電腦立體視覺的問題上。第一個應用是描述兩張影像幾何關係 (two-view geometry) 的模型，透過 fundamental matrix 來建立兩張影像中對應點的關係；另外，我們也將此演算法應用於由多張影像重建三維結構和相機關係 (structure from motion) 的問題。透過許多在模擬資料和實際影像上的實驗結果，我們驗證了我們的演算法比過去的方法，不論在精確度和效率上，都有更好的表現。

關鍵字

三維電腦視覺

並列摘要

In this thesis, we propose a new algorithm that improves the efficiency and robustness of random sampling consensus (RANSAC) for robust model fitting problems. To be more general and practical, this algorithm is designed to be fully data-driven, robust to highly contaminated data, and efficient enough to pursue real-time response for practical applications. To achieve this objective, three techniques are developed in an iterative consensus framework. Firstly, we propose a consensus sampling technique to increase the probability of sampling inliers by exploiting the feedback information obtained from the evaluation procedure. Secondly, the preemptive multiple K-th order approximation (PMKA) is developed for efficient model evaluation with unknown error scale. Lastly, we propose a coarse-to-fine strategy for the robust standard deviation estimation to determine the unknown error scale. We apply the algorithm to several 3D vision problems, including fundamental matrix computation and multi-view metric structure from motion. Experimental results on both simulated and real data are shown to demonstrate the superiority of the proposed algorithm over the previous methods.

並列關鍵字

robust model fitting ； 3D computer vision ； fundamental matrix ； structure from motion

參考文獻

Torre, F.D. and Black, M.J. 2003. A Framework for Robust Subspace Learning. Inter. Jour. of Computer Vision, 54: 117-142.

Bab-Hadiashar, A. and Suter, D. 1999. Robust segmentation of visual data using ranked unbiased scale estimate. Inte. Jour. of Information, Education and Research in Robotics and Artificial Intelligence, 17: 649-660.

Beck, J.V. and Arnold, K.J. 1977. Parameter estimation in engineering and science. Wiley series in probability and mathematical statistics. J. Wiley, New York.

Besl, P.J. and McKay, N.D. 1992. A method for registration of 3-d shapes. IEEE Trans. Pat. Anal. and Mach. Intel., 14(2): 239-256.

Chen, P. and Suter, D. 2004. Recovering the Missing Components in a Large Noisy Low-Rank Matrix: Application to SFM. IEEE Trans. Pat. Anal. and Mach. Intel., 26(8): 1051-1063.