臺灣博碩士論文加值系統

3D重建在電腦視覺的領域中一直扮演著相當重要的角色，無論電腦圖學或多媒體對於3D模型的需求也越來越多。如今熱門的電腦遊戲以及虛擬實境都是建構在複雜的真實環境當中，但想要得到越逼真的3D模型，系統所做的運算量也就越大。因此，如何能提出好的方法來降低重建的計算量以及提升其重建後的準確度是相當需要的。

在3D重建的方法之中，最普遍使用的就是利用相機擷取物體的多張影像以進行3D重建。但處理過程中必須要計算一個相當重要的矩陣，稱做fundamental matrix。這個矩陣隱藏著兩張影像相對關係的資訊，因此它可由兩張影像中的對應點所計算出來，而且其精確度將會大大的影響物體3D重建的結果。

影像組中的對應點都是利用現有的方法透過電腦來自動尋找，因此難免會比對錯誤，如果不把這些比對錯誤的對應點予以剔除，勢必會嚴重的損害到我們所欲計算fundamental matrix的準確度。雖然現今已有不少方法被提出來剔除比對錯誤的對應點，但當有大量的影像對應點來自於同一張真實平面上時，那麼這些方法很可能會失去它們的效能。然而這種情況也不難碰到。例如一個具有很多窗窗角角的建築物，其所擷取到的影像組將會包含大量的對應點來自於同一張真實平面上，那麼所計算出來的fundamental matrix很可能是錯的。這是個很實際的問題。為了克服它，在本篇論文裡將討論傳統計算fundamental matrix方法失去效能的原因，進而針對這些原因提出一個方法來解決。

在本篇論文中，我們提出一個利用影像組的共同主平面之強健Fundamental Matrix 計算法。首先，我們要先在影像組中偵測出是否有大量的對應點來自於同一張真實平面，如是，就利用這個平面以穩定性較高的計算fundamental matrix方法Single-Plane method來產生fundamental matrix 的樣本群，然後從這些樣本群之中挑選一個比較好，而不滿足這個樣本的對應點將被視為比對錯誤的對應點並予以剔除。如此一來所計算出來的fundamental matrix就會比較精準，而後所重建出來的3D 結構也會來的真實。這個方法仰賴真實平面的準確度，也就是當有更多對應點來自於同一張真實平面時，那所計算出來的平面就更準確，因此我們可以預期到，當有大量的對應點來自於同一張真實平面時，這個方法所計算出的fundamental matrix就可以有好的穩定性以及精確度。

我們用電腦合成實驗以及實際影像實驗來測試我們的系統。在合成實驗之中，當有越來越多的對應點來自於同一張真實平面，傳統方法所計算出來的 fundamental matrix 就會越來越差，然而我們的方法仍然可以維持在可接受的範圍內。而實際影像測試中我們擷取了三棟建築物的影像組來進行分析，其結果都能夠符合我們理論的預期以及合成實驗的結果，這都顯示了當影像組中含有大量的對應點，我們方法是比較適用的。

1. Introduction 1
1.1 Motivation ………………………………………………………………...... 1
1.2 Objectives ………………………………………………………………....... 2
1.3 Literature Survey ………………………………………………………….... 3
1.3.1 Methods for Estimating Fundamental Matrix ……………………… 3
1.3.1.1 Linear Methods …………………………………………... 4
1.3.1.2 Nonlinear Methods …………………………………….…. 5
1.3.1.3 Special Methods ………………………………………….. 6
1.3.2 Robust Estimations for Fundamental Matrix ………………………. 7
1.4 Thesis Organization ……………………………………………………….... 8
2. Epipolar Geometry and Fundamental Matrix 11
2.1 Camera Model ……………………………………………….……………. 11
2.2 Epipolar Geometry ………………………………………….…………….. 13
2.3 Fundamental Matrix …...………………………………………….………. 14
2.3.1 Algebraic Derivation ……………………………………………… 15
2.3.2 Geometric Derivation ……………………………………………... 16
2.3.3 Correspondence Condition ………………………………………... 18
2.3.4 Summary of the Fundamental Matrix …………………………….. 18
2.4 General Methods for Estimating Fundamental Matrix …………….……... 19
2.4.1 Linear Methods …………………………………………………… 20
2.4.1.1 Seven-Point Method …………………………………….. 20
2.4.1.2 Eight-Point Method ……………………………………... 21
2.4.1.3 Data Normalization …………………………………...… 23
2.4.1.4 Normalized Eight-Point Method ………………………... 24
2.4.2 Nonlinear Methods ………………………………………………... 24
2.4.2.1 Gold Standard Method ………………………………….. 25
2.4.2.2 Gradient-Based Technique ……………………………… 26
2.4.2.3 Minimizing the Symmetric Epipolar Distance ………….. 28
2.5 Robust Estimations for Fundamental Matrix ………….………………….. 30
2.5.1 M-Estimators ……………………………………………………… 30
2.5.2 LMedS (Least Median of Squares) ……………………………….. 32
2.5.3 RANSAC (Random Sample Consensus) …………………………. 34
3. Single-Plane Method and Homography 37
3.1 Homography …………………………………………………….………… 37
3.2 Methods for Estimating Homography …………………………….………. 38
3.2.1 Normalized Direct Linear Transformation (DLT) Method ……….. 38
3.2.2 Nonlinear Methods …………………………………………….….. 40
3.3 Robust Estimations for Homography ……………………………….…….. 42
3.4 Homography Induced by a Plane ………………………………….……… 42
3.5 Single-Plane Method ……………………………………………….……... 45
3.6 Algorithm Evaluation and Error Analysis ………………………….……... 46
3.6.1 Optimal (Maximum Likelihood) Estimation ……………………... 47
3.6.1.1 Optimal Estimation for Fundamental Matrix …………… 48
3.6.1.2 Optimal Estimation for Homography …………………... 49
3.6.2 Performance Measures ……………………………………………. 50
4. Proposed Method 52
4.1 Problem for Robust Estimations for Fundamental Matrix ……….……….. 52
4.2 Proposed Method …………………………………………………….….... 55
4.2.1 Homography Detection ………………………………………….... 55
4.2.2 Sample Generation ………………………………………………... 57
5. Experiment Results 61
5.1 Synthetic Data …………………………………………………….………. 61
5.2 Real Data ………………………………………………………….………. 67
6. Conclusions 71
Bibliography 73

[1] D. Faugeras, Three-Dimensional Computer Vision: A Geometric Viewpoint, MIT Press, 1993.
[2] H. C. Longuet-Higgins, “A computer algorithm for reconstructing a scene from two projections,” vol. 293, pp. 133-135, Nature, 1981.
[3] Q. T. Luong, Matrice Fondamentale et Autocalibrations en Vision par Ordinateur, Ph.D. thesis, Université de Paris-Sud, France, 1992.
[4] O. D. Faugeras, “Stratification of 3-D vision: projective, affine, and metric representation,” Journal of the Optical Society of America A, vol. 2, pp. 465-484, 1995.
[5] Q. T. Luong and O. D. Faugeras, “The fundamental matrix: Theory, algorithm and stability analysis,” International Journal of Computer Vision, vol. 1, no. 17, pp. 43-76, 1996.
[6] O. D. Faugeras, “What can be seen in three dimensions with an uncalibrated stereo rig?,” in Proc. European Conf. on Computer Vision, Lecture Notes in Computer Science, 588, 1992, Springer-Verlag, pp. 563-578.
[7] R. I. Hartley, R. Gupta, and T. Chang, “Stereo from uncalibrated cameras,” in Proc. IEEE Conf. Computer Vision and Pattern Recognition, 1992, pp. 761-764.
[8] O. D. Faugeras, Q. T. Luong and S. Maybank, “Camera self-calibration: theory and experiments,” in Proc. European Conf. on Computer Vision, Lecture Notes in Computer Science, 1992, vol. 588, Springer-Verlag, pp. 321-334.
[9] R. I. Hartley and R. Gupta, “Computing matched-epipolar projections,” in Proc. IEEE Conf. Computer Vision and Pattern Recognition, 1993, pp. 549-555.
[10] S. Carlsson, “Multiple image invariants using the double algebra,” in Proc. Second Europe-U.S. Workshop on Invariance, pp. 335-350, Ponta Delgaba, Azores, 1993.
[11] R. Deriche, Z. Zhang, Q. T. Luong and O. D. Faugeras, “Robust recovery of the epipolar geometry for an uncalibrated stereo rig,” in Proc. European Conf. on Computer Vision, vol. 1, Lecture Notes in Computer Science, 1994, vol. 800, Springer-Verlag, pp. 567-576.
[12] P. H. S. Torr and D. W. Murry, “Outlier detection and motion segmentation,” Sensor Fusion VI, P.S. Schenker, ed., pp. 432-443, SPIE vol. 2059, Boston, 1993.
[13] Z. Zhang, R. Deriche, O. D. Faugeras and Q. T. Luong, “A robust technique for matching two uncalibrated images though the recovery of the unknown epipolar geometry,” Artificial Intelligence Journal, vol. 78, pp. 87-119,1995.
[14] Q. T. Luong and O. D. Faugeras, “Determining the fundamental matrix with Planes: unstability and new algorithms,” in Proc. Computer Vision and Pattern Recognition, pp. 489-494, 1993.
[15] P. H. S. Torr, “The problem of degeneracy in structure and motion recovery from uncalibrated image sequences,” International Journal of Computer Vision, vol. 32, no. 1, pp. 27-44, 1999.
[16] M. Pollefeys, F. Verbiest and L. V. Gool, “Surviving dominant planes in Uncalibrated structure and motion recovery,” in Proc. European Conf. on Computer Vision, 2002, vol. 2350, Springer-Verlag.
[17] R. I. Hartley, “Estimation of relative camera positions for uncalibrated cameras,” in Proc. European Conference on Computer Vision, Lecture Notes in Computer Science, 588, 1992, Springer-Verlag, pp. 579-587.
[18] T. Huang and A. Netravali, “Motion and structure from feature correspondences: a review,” in Proc. IEEE, vol. 82, no. 2, pp. 252-268, 1994.
[19] R. I. Hartley, “Projective reconstruction and invariants from multiple images,” IEEE Transaction on Pattern Analysis and Machine Intelligent, vol. 16, pp. 1035–1041, 1994.
[20] R. I. Hartley, “In defense of the eight-point algorithm,” IEEE Transaction on Pattern Analysis and Machine Intelligent, vol. 19, no. 6, pp. 580-593, 1997.
[21] R. I. Harley, “Euclidean reconstruction from uncalibrated views,” in Proc. 2nd Europe-U.S. Workshop on Invariance, pp. 187-202, Ponta Delgada, Azores, 1993.
[22] H. P. William, P. F. Brain, A. T. Sual, and T. V. William, Numerical Recipes in C: art of Scientific Computing, Cambridge University Press, 1993.
[23] P. H. S. Torr and A. Zisserman, “Robust parameterization and computation of the trifocal tensor,” Image and Vision Computing, vol. 15, pp. 591-605, 1997.
[24] P. H. S. Torr and A. Zisserman, “Robust parameterization and computation of multiple view relations,” in Proc. International Conference on Computer Vision, Bombay, India, 1998, pp. 727-732.
[25] Z. Zhang, “Determining the epipolar geometry and its uncertainty: a review,” International Journal of Computer Vision, vol. 27, no. 2, pp. 161-195, 1998.
[26] W. Chojnacki, M. J. Brooks, D. Galwey, and A. V. D. Hengel, “A new approach to constrained parameter estimation applicable to some computer vision problems,” in Proc. European Conference on Computer Visio, Copenhagen, Denmark, 2002.
[27] Z. Zhang, “Parameter estimation techniques: a tutorial with application to conic fitting,” Image and Vision Computing, vol. 15, no. 1, pp.59-76, 1997.
[28] P. H. S. Torr and D. W. Murry, “The development and comparison of robust methods for estimating the fundamental matrix,” International Journal of Computer Vision, vol. 24, no. 3, pp.271-300, 1997.
[29] P. H. S. Torr and A. Zisserman, “MLESAC: a new robust estimator with application to estimate image geometry,” Computer Vision and Image Understanding, vol. 78, pp. 138-156, 2000.
[30] P. H. S. Torr, “Bayesian model estimation and selection for epipolar geometry and generic manifold fitting,” International Journal of Computer Vision, vol. 50, no. 1, pp. 35-61, 2002.
[31] G. Xu and Z. Zhang, Epipolar Geometry in Stereo, Motion and Object Recognition: A Unified Approach, Kluwer Academic Publishers, 1996.
[32] R. Tsai and T. Huang, “Uniqueness and estimation of three dimensional motion parameters of rigid objects with curved surface,” IEEE Transaction on Pattern Analysis and Machine Intelligence, vol. 6, no. 1, pp. 13-26, 1984.
[33] P. J. Huber, Robust Statistics, John Wiley & Sons: New York, 1981.
[34] S. Olsen, “Epipolar line estimation,” in Proc. European Conf. on Computer Vision, Santa Margherita Ligure, Italy, 1992, pp. 307-311.
[35] E. Mosteller and J. Turkey, Data and Analysis and Regression, Addison-Wesley, Reading , MA, 1977.
[36] P. Rousseeuw and A. Leroy, Robust Regression and Outlier Detection, John Wiley & Sons: New York,1987.
[37] M. A. Fishchler and R. C. Bolles, “Random sample consensus: a paradigm for model fitting with application to image analysis and automated cartography,” Communication of the ACM, vol. 24, pp. 381-395, 1981.
[38] R. I. Harley and A. Zisserman, Multiple View Geometry in Computer Vision, 2nd ed. Cambridge University Press, 2004.
[39] P. H. S. Torr and D. W. Murry, Motion segmentation and Outlier detection, Ph.D. Thesis, Department of Engineering Science, University of Oxford, 1995.
[40] P. D. Sampson, “Fitting conic sections to ‘very scattered’ data: an iterative refinement of the Bookstein algorithm,” Computer Vision, Graphics, and Image Processing, vol. 18, pp. 97-108, 1982.
[41] P. J. Rousseeuw, “Least median of squares regression,” Journal of American Statistical Association, vol. 79, pp. 871-880, 1984.
[42] I. E. Sutherland, “Sketchpad: a man-machine graphical communications system,” Technical Report 296, MIT Lincoln Laboratories, 1963.
[43] O. Chum, T. Werner, and J. Matas, “Two-view geometry estimation unaffected by a dominant plane,” in Proc. Computer Vision and Pattern Recognition, pp. 772-779, 2005.