Ransac for Dummies.pdf-资料库

zhl8619-3022223-4744302543021693263.pdf-第1页.png

第1页 / 共99页

zhl8619-3022223-4744302543021693263.pdf-第2页.png

第2页 / 共99页

zhl8619-3022223-4744302543021693263.pdf-第3页.png

第3页 / 共99页

zhl8619-3022223-4744302543021693263.pdf-第4页.png

第4页 / 共99页

zhl8619-3022223-4744302543021693263.pdf-第5页.png

第5页 / 共99页

zhl8619-3022223-4744302543021693263.pdf-第6页.png

第6页 / 共99页

zhl8619-3022223-4744302543021693263.pdf-第7页.png

第7页 / 共99页

zhl8619-3022223-4744302543021693263.pdf-第8页.png

第8页 / 共99页

RANSAC for Dummies With examples using the RANSAC toolbox for Matlab™ and more. . . Not for public release Marco Zuliani marco.zuliani@gmail.com ©2008–2009 October 18, 2009 vision.ece.ucsb.edu/∼zuliani Draft

Copyright of Marco Zuliani 2008–2009 Draft Copyright © 2008 Marco Zuliani. Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation; with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. A copy of the license is included in the appendix entitled “GNU Free Documentation License”. Draft 3

1 Parameter Estimation In Presence of Outliers Contents 7 7 8 10 11 11 12 12 14 14 15 17 18 19 21 23 23 23 23 24 1.1 A Toy Example: Estimating 2D Lines . . . . . . . . . . . . . . . . . . 1.1.1 Maximum Likelihood Estimation . . . . . . . . . . . . . . . . 1.2 Outliers, Bias and Breakdown Point . . . . . . . . . . . . . . . . . . . 1.2.1 Outliers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.2 Bias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.3 Breakdown Point . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 The Breakdown Point for a 2D Line Least Squares Estimator . . . . . Draft 2 RANdom Sample And Consensus 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 RANSAC Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.1 How many iterations? . . . . . . . . . . . . . . . . . . . . . . 2.3.2 Constructing the MSSs and Calculating q . . . . . . . . . . . 2.3.3 Ranking the Consensus Set . . . . . . . . . . . . . . . . . . . 2.4 Computational Complexity . . . . . . . . . . . . . . . . . . . . . . . . 2.4.1 Hypothesize Step . . . . . . . . . . . . . . . . . . . . . . . . . 2.4.2 Test Step . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4.3 Overall Complexity . . . . . . . . . . . . . . . . . . . . . . . . 2.5 Other RANSAC Flavors . . . . . . . . . . . . . . . . . . . . . . . . . 4

Copyright of Marco Zuliani 2008–2009 Draft 3 RANSAC at Work 3.1 The RANSAC Toolbox for Matlab™ . . . . . . . . . . . . . . . . . . . RANSAC.m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Some Examples Using the RANSAC Toolbox . . . . . . . . . . . . . . 3.1.1 3.2.1 Estimating Lines . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.2 Estimating Planes . . . . . . . . . . . . . . . . . . . . . . . . 3.2.3 Estimating A Rotation Scaling and Translation . . . . . . . . 3.2.4 Estimating Homographies . . . . . . . . . . . . . . . . . . . . 3.3 Frequently Asked Questions . . . . . . . . . . . . . . . . . . . . . . . 3.3.1 What is the “right” value of σ? . . . . . . . . . . . . . . . . . 3.3.2 How do I use the toolbox for image registration purposes? . . 3.3.3 Why the behaviour of RANSAC is not repeatable? . . . . . . 3.3.4 What should I do if I ﬁnd a bug in the toolbox? . . . . . . . . 3.3.5 Are there any other RANSAC routines for Matlab? . . . . . . Draft 26 26 26 30 30 33 34 38 42 42 42 42 42 43 44 45 45 48 48 49 50 50 51 55 57 62 62 62 63 65 A Notation B Some Linear Algebra Facts B.1 The Singular Value Decomposition . . . . . . . . . . . . . . . . . . . B.2 Relation Between the SVD Decomposition and the Eigen Decomposition 46 B.3 Fast Diagonalization of Symmetric 2 × 2 Matrices . . . . . . . . . . . B.4 Least Square Problems Solved via SVD . . . . . . . . . . . . . . . . . 47 B.4.1 Solving Aθ = b . . . . . . . . . . . . . . . . . . . . . . . . . . B.4.2 Solving Aθ = 0 subject to kθk = 1 . . . . . . . . . . . . . . . C The Normalized Direct Linear Transform (nDLT) Algorithm C.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . C.2 Point Normalization . . . . . . . . . . . . . . . . . . . . . . . . . . . C.3 A Numerical Example . . . . . . . . . . . . . . . . . . . . . . . . . . C.4 Concluding Remarks About the Normalized DLT Algorithm . . . . . D Some Code from the RANSAC Toolbox D.1 Function Templates . . . . . . . . . . . . . . . . . . . . . . . . . . . . D.1.1 MSS Validation . . . . . . . . . . . . . . . . . . . . . . . . . . D.1.2 Parameter Estimation . . . . . . . . . . . . . . . . . . . . . . D.1.3 Parameter Validation . . . . . . . . . . . . . . . . . . . . . . . 5

Copyright of Marco Zuliani 2008–2009 Draft 66 68 68 71 75 79 87 88 89 90 91 93 93 94 94 95 95 95 96 D.1.4 Fitting Error . . . . . . . . . . . . . . . . . . . . . . . . . . . D.2 Source Code for the Examples . . . . . . . . . . . . . . . . . . . . . . D.2.1 Line Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . D.2.2 Plane Estimation . . . . . . . . . . . . . . . . . . . . . . . . . D.2.3 RST Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . D.2.4 Homography Estimation . . . . . . . . . . . . . . . . . . . . . E GNU Free Documentation License 1. APPLICABILITY AND DEFINITIONS . . . . . . . . . . . . . . . . . . 2. VERBATIM COPYING . . . . . . . . . . . . . . . . . . . . . . . . . . 3. COPYING IN QUANTITY . . . . . . . . . . . . . . . . . . . . . . . . . 4. MODIFICATIONS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5. COMBINING DOCUMENTS . . . . . . . . . . . . . . . . . . . . . . . 6. COLLECTIONS OF DOCUMENTS . . . . . . . . . . . . . . . . . . . . 7. AGGREGATION WITH INDEPENDENT WORKS . . . . . . . . . . . 8. TRANSLATION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9. TERMINATION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10. FUTURE REVISIONS OF THIS LICENSE . . . . . . . . . . . . . . . ADDENDUM: How to use this License for your documents . . . . . . . . . References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Draft 6

Parameter Estimation In Presence of Outliers 1 This chapter introduces the problem of parameter estimation when the measurements are contaminated by outliers. To motivate the results that will be presented in the next chapters and to understand the power of RANSAC, we will study a simple problem: ﬁtting a 2D line to a set of points on the plane. Despite its simplicity, this problem retains all the challenges that are encountered when the models used to explain the measurements are more complex. Draft pθ2 (1.1) 1.1 A Toy Example: Estimating 2D Lines Consider a set of N points D = {d1, . . . , dN} ⊂ R2 and suppose we want to estimate the best line that ﬁts such points.1 For each point we wish to minimize a monotonically increasing function of the absolute value of the signed error: eM(d; θ) = θ1x1 + θ2x2 + θ3 1 + θ2 1 The sign of the error (1.1) accounts for the fact that the point lies on the left or on the right semi- plane determined by the line. The parameter vector θ ∈ R2 describes the line according the implicit representation θ1x1 + θ2x2 + θ3 = 0 (this is the model M that we will use to Figure 1.1: Line ﬁtting example. 1Further details regarding the estimation of 2D lines can be found in Section 3.2.1. 7 !1x1"!2x2"!3=0de#d,!$d

Copyright of Marco Zuliani 2008–2009 Draft ﬁt the measurements). Note that the length of θ is immaterial. This type of ﬁtting is also known as orthogonal regression, since the distances of the sample points from the line are evaluated computing the orthogonal projection of the measurements on the line itself. Other type of regression can also be used, e.g. minimizing the distance of the projection of the measurements along the y axis (however such an approach produce an estimate of the parameters that is not invariant with respect a rotation of the coordinate system). 1.1.1 Maximum Likelihood Estimation Imagine that the ﬁtting error is modeled as a Gaussian random variable with zero mean and standard deviation ση, i.e. eM(d; θ) ∼ N (0, ση). The maximum likelihood approach aims at ﬁnding the parameter vector that maximize the likelihood of the joint error distribution deﬁned as: L(θ) def= p [eM(d1; θ), . . . , eM(dN ; θ)]. In the previous expression p indicates the joint probability distribution function (pdf) of the errors. Intuitively, we are trying to ﬁnd the parameter vector that maximizes the probability of observing the signed errors eM(di; θ). Therefore: Draft ˆθ = argmax L(θ) θ NX NX ση 8 To simplify this maximization problem, we assume that the errors are independent (an assumption that should be made with some caution, especially in real life scenar- ios. . . ) and we consider the log-likelihood L∗(θ) def= log L(θ). This trick allows us to simplify some calculations without aﬀecting the ﬁnal result, since the logarithm is a monotonically increasing function (and therefore the maximizer remains the same). Under the previous assumptions we can write: L∗(θ) def= log p[eM(di; θ)] = log p[eM(di; θ)] = i=1 i=1 log 1 ZG − 1 2 ση eM(di; θ) 2! where ZG = Therefore the maximum likelihood estimate of the parameter vector is given by: 2πση is the normalization constant for the Gaussian distribution. eM(di; θ) 2! NX 1 2 eM(di; θ) 2 ση (1.2) = argmin θ i=1 ˆθ = argmax θ i=1 log 1 ZG − 1 2 NY i=1 √ NX

资料库

Ransac for Dummies.pdf

相关推荐

开发技术

热门标签

最新资料