Blame view

3rdparty/opencv-4.5.4/doc/tutorials/calib3d/usac.markdown 13.7 KB
f4334277   Hu Chunming   提交3rdparty
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
  ---
  author:
  - Maksym Ivashechkin
  bibliography: 'bibs.bib'
  csl: 'acm-sigchi-proceedings.csl'
  date: August 2020
  title: 'Google Summer of Code: Improvement of Random Sample Consensus in OpenCV'
  ...
  
  Contribution
  ============
  
  The integrated part to OpenCV `calib3d` module is RANSAC-based universal
  framework USAC (`namespace usac`) written in C++. The framework includes
  different state-of-the-arts methods for sampling, verification or local
  optimization. The main advantage of the framework is its independence to
  any estimation problem and modular structure. Therefore, new solvers or
  methods can be added/removed easily. So far it includes the following
  components:
  
  1.  Sampling method:
  
      1.  Uniform – standard RANSAC sampling proposed in \[8\] which draw
          minimal subset independently uniformly at random. *The default
          option in proposed framework*.
  
      2.  PROSAC – method \[4\] that assumes input data points sorted by
          quality so sampling can start from the most promising points.
          Correspondences for this method can be sorted e.g., by ratio of
          descriptor distances of the best to second match obtained from
          SIFT detector. *This is method is recommended to use because it
          can find good model and terminate much earlier*.
  
      3.  NAPSAC – sampling method \[10\] which takes initial point
          uniformly at random and the rest of points for minimal sample in
          the neighborhood of initial point. This is method can be
          potentially useful when models are localized. For example, for
          plane fitting. However, in practise struggles from degenerate
          issues and defining optimal neighborhood size.
  
      4.  Progressive-NAPSAC – sampler \[2\] which is similar to NAPSAC,
          although it starts from local and gradually converges to
          global sampling. This method can be quite useful if local models
          are expected but distribution of data can be arbitrary. The
          implemented version assumes data points to be sorted by quality
          as in PROSAC.
  
  2.  Score Method. USAC as well as standard RANSAC finds model which
      minimizes total loss. Loss can be represented by following
      functions:
  
      1.  RANSAC – binary 0 / 1 loss. 1 for outlier, 0 for inlier. *Good
          option if the goal is to find as many inliers as possible.*
  
      2.  MSAC – truncated squared error distance of point to model. *The
          default option in framework*. The model might not have as many
          inliers as using RANSAC score, however will be more accurate.
  
      3.  MAGSAC – threshold-free method \[3\] to compute score. Using,
          although, maximum sigma (standard deviation of noise) level to
          marginalize residual of point over sigma. Score of the point
          represents likelihood of point being inlier. *Recommended option
          when image noise is unknown since method does not require
          threshold*. However, it is still recommended to provide at least
          approximated threshold, because termination itself is based on
          number of points which error is less than threshold. By giving 0
          threshold the method will output model after maximum number of
          iterations reached.
  
      4.  LMeds – the least median of squared error distances. In the
          framework finding median is efficiently implement with $O(n)$
          complexity using quick-sort algorithm. Note, LMeds does not have
          to work properly when inlier ratio is less than 50%, in other
          cases this method is robust and does not require threshold.
  
  3.  Error metric which describes error distance of point to
      estimated model.
  
      1.  Re-projection distance – used for affine, homography and
          projection matrices. For homography also symmetric re-projection
          distance can be used.
  
      2.  Sampson distance – used for Fundamental matrix.
  
      3.  Symmetric Geometric distance – used for Essential matrix.
  
  4.  Degeneracy:
  
      1.  DEGENSAC – method \[7\] which for Fundamental matrix estimation
          efficiently verifies and recovers model which has at least 5
          points in minimal sample lying on the dominant plane.
  
      2.  Collinearity test – for affine and homography matrix estimation
          checks if no 3 points lying on the line. For homography matrix
          since points are planar is applied test which checks if points
          in minimal sample lie on the same side w.r.t. to any line
          crossing any two points in sample (does not assume reflection).
  
      3.  Oriented epipolar constraint – method \[6\] for epipolar
          geometry which verifies model (fundamental and essential matrix)
          to have points visible in the front of the camera.
  
  5.  SPRT verification – method \[9\] which verifies model by its
      evaluation on randomly shuffled points using statistical properties
      given by probability of inlier, relative time for estimation,
      average number of output models etc. Significantly speeding up
      framework, because bad model can be rejected very quickly without
      explicitly computing error for every point.
  
  6.  Local Optimization:
  
      1.  Locally Optimized RANSAC – method \[5\] that iteratively
          improves so-far-the-best model by non-minimal estimation. *The
          default option in framework. This procedure is the fastest and
          not worse than others local optimization methods.*
  
      2.  Graph-Cut RANSAC – method \[1\] that refine so-far-the-best
          model, however, it exploits spatial coherence of the
          data points. *This procedure is quite precise however
          computationally slower.*
  
      3.  Sigma Consensus – method \[3\] which improves model by applying
          non-minimal weighted estimation, where weights are computed with
          the same logic as in MAGSAC score. This method is better to use
          together with MAGSAC score.
  
  7.  Termination:
  
      1.  Standard – standard equation for independent and
          uniform sampling.
  
      2.  PROSAC – termination for PROSAC.
  
      3.  SPRT – termination for SPRT.
  
  8.  Solver. In the framework there are minimal and non-minimal solvers.
      In minimal solver standard methods for estimation is applied. In
      non-minimal solver usually the covariance matrix is built and the
      model is found as the eigen vector corresponding to the highest
      eigen value.
  
      1.  Affine2D matrix
  
      2.  Homography matrix – for minimal solver is used RHO
          (Gaussian elimination) algorithm from OpenCV.
  
      3.  Fundamental matrix – for 7-points algorithm two null vectors are
          found using Gaussian elimination (eliminating to upper
          triangular matrix and back-substitution) instead of SVD and then
          solving 3-degrees polynomial. For 8-points solver Gaussian
          elimination is used too.
  
      4.  Essential matrix – 4 null vectors are found using
          Gaussian elimination. Then the solver based on Gröbner basis
          described in \[11\] is used. Essential matrix can be computed
          only if <span style="font-variant:small-caps;">LAPACK</span> or
          <span style="font-variant:small-caps;">Eigen</span> are
          installed as it requires eigen decomposition with complex
          eigen values.
  
      5.  Perspective-n-Point – the minimal solver is classical 3 points
          with up to 4 solutions. For RANSAC the low number of sample size
          plays significant role as it requires less iterations,
          furthermore in average P3P solver has around 1.39
          estimated models. Also, in new version of `solvePnPRansac(...)`
          with `UsacParams` there is an options to pass empty intrinsic
          matrix `InputOutputArray cameraMatrix`. If matrix is empty than
          using Direct Linear Transformation algorithm (PnP with 6 points)
          framework outputs not only rotation and translation vector but
          also calibration matrix.
  
  Also, the framework can be run in parallel. The parallelization is done
  in the way that multiple RANSACs are created and they share two atomic
  variables `bool success` and `int num_hypothesis_tested` which
  determines when all RANSACs must terminate. If one of RANSAC terminated
  successfully then all other RANSAC will terminate as well. In the end
  the best model is synchronized from all threads. If PROSAC sampler is
  used then threads must share the same sampler since sampling is done
  sequentially. However, using default options of framework parallel
  RANSAC is not deterministic since it depends on how often each thread is
  running. The easiest way to make it deterministic is using PROSAC
  sampler without SPRT and Local Optimization and not for Fundamental
  matrix, because they internally use random generators.\
  \
  For NAPSAC, Progressive NAPSAC or Graph-Cut methods is required to build
  a neighborhood graph. In framework there are 3 options to do it:
  
  1.  `NEIGH_FLANN_KNN` – estimate neighborhood graph using OpenCV FLANN
      K nearest-neighbors. The default value for KNN is 7. KNN method may
      work good for sampling but not good for GC-RANSAC.
  
  2.  `NEIGH_FLANN_RADIUS` – similarly as in previous case finds neighbor
      points which distance is less than 20 pixels.
  
  3.  `NEIGH_GRID` – for finding points’ neighborhood tiles points in
      cells using hash-table. The method is described in \[2\]. Less
      accurate than `NEIGH_FLANN_RADIUS`, although significantly faster.
  
  Note, `NEIGH_FLANN_RADIUS` and `NEIGH_FLANN_RADIUS` are not able to PnP
  solver, since there are 3D object points.\
  \
  New flags:
  
  1.  `USAC_DEFAULT` – has standard LO-RANSAC.
  
  2.  `USAC_PARALLEL` – has LO-RANSAC and RANSACs run in parallel.
  
  3.  `USAC_ACCURATE` – has GC-RANSAC.
  
  4.  `USAC_FAST` – has LO-RANSAC with smaller number iterations in local
      optimization step. Uses RANSAC score to maximize number of inliers
      and terminate earlier.
  
  5.  `USAC_PROSAC` – has PROSAC sampling. Note, points must be sorted.
  
  6.  `USAC_FM_8PTS` – has LO-RANSAC. Only valid for Fundamental matrix
      with 8-points solver.
  
  7.  `USAC_MAGSAC` – has MAGSAC++.
  
  Every flag uses SPRT verification. And in the end the final
  so-far-the-best model is polished by non minimal estimation of all found
  inliers.\
  \
  A few other important parameters:
  
  1.  `randomGeneratorState` – since every USAC solver is deterministic in
      OpenCV (i.e., for the same points and parameters returns the
      same result) by providing new state it will output new model.
  
  2.  `loIterations` – number of iterations for Local Optimization method.
      *The default value is 10*. By increasing `loIterations` the output
      model could be more accurate, however, the computationial time may
      also increase.
  
  3.  `loSampleSize` – maximum sample number for Local Optimization. *The
      default value is 14*. Note, that by increasing `loSampleSize` the
      accuracy of model can increase as well as the computational time.
      However, it is recommended to keep value less than 100, because
      estimation on low number of points is faster and more robust.
  
  Samples:
  
  There are three new sample files in opencv/samples directory.
  
  1.  `epipolar_lines.cpp` – input arguments of `main` function are two
      pathes to images. Then correspondences are found using
      SIFT detector. Fundamental matrix is found using RANSAC from
      tentaive correspondences and epipolar lines are plot.
  
  2.  `essential_mat_reconstr.cpp` – input arguments are path to data file
      containing image names and single intrinsic matrix and directory
      where these images located. Correspondences are found using SIFT.
      The essential matrix is estimated using RANSAC and decomposed to
      rotation and translation. Then by building two relative poses with
      projection matrices image points are triangulated to object points.
      By running RANSAC with 3D plane fitting object points as well as
      correspondences are clustered into planes.
  
  3.  `essential_mat_reconstr.py` – the same functionality as in .cpp
      file, however instead of clustering points to plane the 3D map of
      object points is plot.
  
  References:
  
  1\. Daniel Barath and Jiří Matas. 2018. Graph-Cut RANSAC. In *Proceedings
  of the iEEE conference on computer vision and pattern recognition*,
  6733–6741.
  
  2\. Daniel Barath, Maksym Ivashechkin, and Jiri Matas. 2019. Progressive
  NAPSAC: Sampling from gradually growing neighborhoods. *arXiv preprint
  arXiv:1906.02295*.
  
  3\. Daniel Barath, Jana Noskova, Maksym Ivashechkin, and Jiri Matas.
  2020. MAGSAC++, a fast, reliable and accurate robust estimator. In
  *Proceedings of the iEEE/CVF conference on computer vision and pattern
  recognition (cVPR)*.
  
  4\. O. Chum and J. Matas. 2005. Matching with PROSAC-progressive sample
  consensus. In *Computer vision and pattern recognition*.
  
  5\. O. Chum, J. Matas, and J. Kittler. 2003. Locally optimized RANSAC. In
  *Joint pattern recognition symposium*.
  
  6\. O. Chum, T. Werner, and J. Matas. 2004. Epipolar geometry estimation
  via RANSAC benefits from the oriented epipolar constraint. In
  *International conference on pattern recognition*.
  
  7\. Ondrej Chum, Tomas Werner, and Jiri Matas. 2005. Two-view geometry
  estimation unaffected by a dominant plane. In *2005 iEEE computer
  society conference on computer vision and pattern recognition
  (cVPR’05)*, 772–779.
  
  8\. M. A. Fischler and R. C. Bolles. 1981. Random sample consensus: A
  paradigm for model fitting with applications to image analysis and
  automated cartography. *Communications of the ACM*.
  
  9\. Jiri Matas and Ondrej Chum. 2005. Randomized RANSAC with sequential
  probability ratio test. In *Tenth iEEE international conference on
  computer vision (iCCV’05) volume 1*, 1727–1732.
  
  10\. D. R. Myatt, P. H. S. Torr, S. J. Nasuto, J. M. Bishop, and R.
  Craddock. 2002. NAPSAC: High noise, high dimensional robust estimation.
  In *In bMVC02*, 458–467.
  
  11\. Henrik Stewénius, Christopher Engels, and David Nistér. 2006. Recent
  developments on direct relative orientation.