1 /*
2 * Copyright (C) 2013 Alberto Irurueta Carro (alberto@irurueta.com)
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16 package com.irurueta.numerical.robust;
17
18 import com.irurueta.numerical.LockedException;
19 import com.irurueta.numerical.NotReadyException;
20
21 import java.util.ArrayList;
22 import java.util.BitSet;
23
24 /**
25 * This class implements RANSAC (RANdom SAmple Consensus) algorithm to robustly
26 * estimate a data model.
27 * RANSAC is based on the idea that given a proportion of outliers (that is
28 * estimated while the algorithm is run), it is needed a certain number of
29 * random sub-samples to obtain required data with a certain level of confidence.
30 * To determine whether a sample is an outlier or not, provided constant
31 * threshold is used. If a threshold cannot be determined beforehand, then it
32 * is better to use LMedS algorithm, at the expense of slightly less accurate
33 * results.
34 *
35 * @param <T> type of object to be estimated.
36 */
37 @SuppressWarnings("DuplicatedCode")
38 public class RANSACRobustEstimator<T> extends RobustEstimator<T> {
39
40 /**
41 * Constant defining default confidence of the estimated result, which is
42 * 99%. This means that with a probability of 99% estimation will be
43 * accurate because chosen sub-samples will be inliers.
44 */
45 public static final double DEFAULT_CONFIDENCE = 0.99;
46
47 /**
48 * Default maximum allowed number of iterations.
49 */
50 public static final int DEFAULT_MAX_ITERATIONS = 5000;
51
52 /**
53 * Minimum allowed confidence value.
54 */
55 public static final double MIN_CONFIDENCE = 0.0;
56
57 /**
58 * Maximum allowed confidence value.
59 */
60 public static final double MAX_CONFIDENCE = 1.0;
61
62 /**
63 * Minimum allowed number of iterations.
64 */
65 public static final int MIN_ITERATIONS = 1;
66
67 /**
68 * Minimum allowed threshold to determine inliers.
69 */
70 public static final double MIN_THRESHOLD = 0.0;
71
72 /**
73 * Indicates that by default inliers will only be computed but not kept.
74 */
75 public static final boolean DEFAULT_COMPUTE_AND_KEEP_INLIERS = false;
76
77 /**
78 * Indicates that by default residuals will only be computed but not kept.
79 */
80 public static final boolean DEFAULT_COMPUTE_AND_KEEP_RESIDUALS = false;
81
82 /**
83 * Amount of confidence expressed as a value between 0 and 1.0 (which is
84 * equivalent to 100%). The amount of confidence indicates the probability
85 * that the estimated result is correct. Usually this value will be close
86 * to 1.0, but not exactly 1.0.
87 */
88 private double confidence;
89
90 /**
91 * Maximum allowed number of iterations. When the maximum number of
92 * iterations is exceeded, result will not be available, however an
93 * approximate result will be available for retrieval.
94 */
95 private int maxIterations;
96
97 /**
98 * Instance in charge of picking random subsets of samples.
99 */
100 private SubsetSelector subsetSelector;
101
102 /**
103 * Number of iterations to be done to obtain required confidence.
104 */
105 private int nIters;
106
107 /**
108 * Best solution that has been found so far during an estimation.
109 */
110 private T bestResult;
111
112 /**
113 * Data related to inliers found for best result.
114 */
115 private RANSACInliersData bestInliersData;
116
117 /**
118 * Indicates whether inliers must be computed and kept.
119 */
120 private boolean computeAndKeepInliers;
121
122 /**
123 * Indicates whether residuals must be computed and kept.
124 */
125 private boolean computeAndKeepResiduals;
126
127 /**
128 * Constructor.
129 */
130 public RANSACRobustEstimator() {
131 super();
132 confidence = DEFAULT_CONFIDENCE;
133 maxIterations = DEFAULT_MAX_ITERATIONS;
134 nIters = maxIterations;
135 bestResult = null;
136 bestInliersData = null;
137 computeAndKeepInliers = DEFAULT_COMPUTE_AND_KEEP_INLIERS;
138 computeAndKeepResiduals = DEFAULT_COMPUTE_AND_KEEP_RESIDUALS;
139 }
140
141 /**
142 * Constructor with listener.
143 *
144 * @param listener listener to be notified of events such as when estimation
145 * starts, ends or its progress significantly changes, as well as in charge
146 * of picking samples and doing per-iteration estimations.
147 */
148 public RANSACRobustEstimator(final RANSACRobustEstimatorListener<T> listener) {
149 super(listener);
150 confidence = DEFAULT_CONFIDENCE;
151 maxIterations = DEFAULT_MAX_ITERATIONS;
152 nIters = maxIterations;
153 bestResult = null;
154 bestInliersData = null;
155 computeAndKeepInliers = DEFAULT_COMPUTE_AND_KEEP_INLIERS;
156 computeAndKeepResiduals = DEFAULT_COMPUTE_AND_KEEP_RESIDUALS;
157 }
158
159 /**
160 * Returns amount of confidence expressed as a value between 0 and 1.0
161 * (which is equivalent to 100%). The amount of confidence indicates the
162 * probability that the estimated result is correct. Usually this value will
163 * be close to 1.0, but not exactly 1.0.
164 *
165 * @return amount of confidence as a value between 0.0 and 1.0.
166 */
167 public double getConfidence() {
168 return confidence;
169 }
170
171 /**
172 * Sets amount of confidence expressed as a value between 0 and 1.0 (which
173 * is equivalent to 100%). The amount of confidence indicates the
174 * probability that the estimated result is correct. Usually this value will
175 * be close to 1.0, but not exactly 1.0.
176 *
177 * @param confidence confidence to be set as a value between 0.0 and 1.0.
178 * @throws IllegalArgumentException if provided value is not between 0.0 and
179 * 1.0.
180 * @throws LockedException if this estimator is locked because an estimation
181 * is being computed.
182 */
183 public void setConfidence(final double confidence) throws LockedException {
184 if (isLocked()) {
185 throw new LockedException();
186 }
187 if (confidence < MIN_CONFIDENCE || confidence > MAX_CONFIDENCE) {
188 throw new IllegalArgumentException();
189 }
190 this.confidence = confidence;
191 }
192
193 /**
194 * Maximum allowed number of iterations. When the maximum number of
195 * iterations is exceeded, result will not be available, however an
196 * approximate result will be available for retrieval.
197 *
198 * @return maximum allowed number of iterations.
199 */
200 public int getMaxIterations() {
201 return maxIterations;
202 }
203
204 /**
205 * Sets maximum allowed number of iterations. When the maximum number of
206 * iterations is exceeded, result will not be available, however an
207 * approximate result will be available for retrieval.
208 *
209 * @param maxIterations maximum allowed number of iterations to be set.
210 * @throws IllegalArgumentException if provided value is less than 1.
211 * @throws LockedException if this estimator is locked because an estimation
212 * is being computed.
213 */
214 public void setMaxIterations(final int maxIterations) throws LockedException {
215 if (isLocked()) {
216 throw new LockedException();
217 }
218 if (maxIterations < MIN_ITERATIONS) {
219 throw new IllegalArgumentException();
220 }
221 this.maxIterations = maxIterations;
222 }
223
224 /**
225 * Returns number of iterations to be done to obtain required confidence.
226 *
227 * @return number of iterations to be done to obtain required confidence.
228 */
229 public int getNIters() {
230 return nIters;
231 }
232
233 /**
234 * Returns best solution that has been found so far during an estimation.
235 *
236 * @return best solution that has been found so far during an estimation.
237 */
238 public T getBestResult() {
239 return bestResult;
240 }
241
242 /**
243 * Gets data related to inliers found for best result.
244 *
245 * @return data related to inliers found for best result.
246 */
247 public RANSACInliersData getBestInliersData() {
248 return bestInliersData;
249 }
250
251 /**
252 * Indicates whether inliers must be computed and kept.
253 *
254 * @return true if inliers must be computed and kept, false if inliers
255 * only need to be computed but not kept.
256 */
257 public boolean isComputeAndKeepInliersEnabled() {
258 return computeAndKeepInliers;
259 }
260
261 /**
262 * Specifies whether inliers must be computed and kept.
263 *
264 * @param computeAndKeepInliers true if inliers must be computed and kept,
265 * false if inliers only need to be computed but not kept.
266 * @throws LockedException if estimator is locked.
267 */
268 public void setComputeAndKeepInliersEnabled(final boolean computeAndKeepInliers) throws LockedException {
269 if (isLocked()) {
270 throw new LockedException();
271 }
272 this.computeAndKeepInliers = computeAndKeepInliers;
273 }
274
275 /**
276 * Indicates whether residuals must be computed and kept.
277 *
278 * @return true if residuals must be computed and kept, false if residuals
279 * only need to be computed but not kept.
280 */
281 public boolean isComputeAndKeepResidualsEnabled() {
282 return computeAndKeepResiduals;
283 }
284
285 /**
286 * Specifies whether residuals must be computed and kept.
287 *
288 * @param computeAndKeepResiduals true if residuals must be computed and
289 * kept, false if residuals only need to be computed but not kept.
290 * @throws LockedException if estimator is locked.
291 */
292 public void setComputeAndKeepResidualsEnabled(final boolean computeAndKeepResiduals) throws LockedException {
293 if (isLocked()) {
294 throw new LockedException();
295 }
296 this.computeAndKeepResiduals = computeAndKeepResiduals;
297 }
298
299 /**
300 * Indicates if estimator is ready to start the estimation process.
301 *
302 * @return true if ready, false otherwise.
303 */
304 @Override
305 public boolean isReady() {
306 if (!super.isReady()) {
307 return false;
308 }
309 return (listener instanceof RANSACRobustEstimatorListener);
310 }
311
312 /**
313 * Robustly estimates an instance of T.
314 *
315 * @return estimated object.
316 * @throws LockedException if robust estimator is locked.
317 * @throws NotReadyException if provided input data is not enough to start
318 * the estimation.
319 * @throws RobustEstimatorException if estimation fails for any reason
320 * (i.e. numerical instability, no solution available, etc).
321 */
322 @Override
323 public T estimate() throws LockedException, NotReadyException, RobustEstimatorException {
324 if (isLocked()) {
325 throw new LockedException();
326 }
327 if (!isReady()) {
328 throw new NotReadyException();
329 }
330
331 try {
332 final var listener = (RANSACRobustEstimatorListener<T>) this.listener;
333
334 locked = true;
335
336 listener.onEstimateStart(this);
337
338 final var totalSamples = listener.getTotalSamples();
339 final var subsetSize = listener.getSubsetSize();
340 final var threshold = listener.getThreshold();
341 // only positive thresholds are allowed
342 if (threshold < MIN_THRESHOLD) {
343 throw new RobustEstimatorException();
344 }
345
346 var bestNumInliers = 0;
347 nIters = Integer.MAX_VALUE;
348 int newNIters;
349 var currentIter = 0;
350 // reusable list that will contain preliminary solutions on each
351 // iteration
352 final var iterResults = new ArrayList<T>();
353 bestResult = null;
354 int currentInliers;
355 var previousProgress = 0.0f;
356 float progress;
357 final var subsetIndices = new int[subsetSize];
358
359 BitSet inliers = null;
360 double[] residuals = null;
361 if (computeAndKeepInliers || computeAndKeepResiduals) {
362 bestInliersData = new RANSACInliersData(totalSamples, computeAndKeepInliers, computeAndKeepResiduals);
363
364 if (computeAndKeepInliers) {
365 inliers = new BitSet(totalSamples);
366 }
367 if (computeAndKeepResiduals) {
368 residuals = new double[totalSamples];
369 }
370 }
371
372 if (subsetSelector == null) {
373 // create new subset selector
374 subsetSelector = SubsetSelector.create(totalSamples);
375 } else {
376 // set number of samples to current subset selector
377 subsetSelector.setNumSamples(totalSamples);
378 }
379
380 while ((nIters > currentIter) && (currentIter < maxIterations)) {
381 // generate a random subset of samples
382 subsetSelector.computeRandomSubsets(subsetSize, subsetIndices);
383
384 // clear list of preliminary solutions before calling listener
385 iterResults.clear();
386 // compute solution for current iteration
387 listener.estimatePreliminarSolutions(subsetIndices, iterResults);
388
389 for (final var iterResult : iterResults) {
390 // compute number of inliers
391 currentInliers = 0;
392 for (var i = 0; i < totalSamples; i++) {
393 final var error = listener.computeResidual(iterResult, i);
394 if (error <= threshold) {
395 currentInliers++;
396 // keep inlier data if needed
397 if (inliers != null) {
398 inliers.set(i);
399 }
400 } else {
401 // outlier
402 if (inliers != null) {
403 inliers.clear(i);
404 }
405 }
406
407 if (residuals != null) {
408 residuals[i] = error;
409 }
410 }
411
412 // save result that produces the largest number of inliers
413 // and update number of iterations
414 if (currentInliers > bestNumInliers) {
415 // update best number of inliers
416 bestNumInliers = currentInliers;
417 // keep current result
418 bestResult = iterResult;
419
420 // update best inlier data
421 if (bestInliersData != null) {
422 bestInliersData.update(inliers, residuals, bestNumInliers);
423 }
424
425 // recompute number of times the algorithm needs to be
426 // executed depending on current number of inliers to
427 // achieve with probability mConfidence that we have
428 // inliers and probability 1 - mConfidence that we have
429 // outliers
430 final var probSubsetAllInliers = Math.pow((double) bestNumInliers / (double) totalSamples,
431 subsetSize);
432
433 if (Math.abs(probSubsetAllInliers) < Double.MIN_VALUE || Double.isNaN(probSubsetAllInliers)) {
434 newNIters = Integer.MAX_VALUE;
435 } else {
436 final var logProbSomeOutliers = Math.log(1.0 - probSubsetAllInliers);
437 if (Math.abs(logProbSomeOutliers) < Double.MIN_VALUE || Double.isNaN(logProbSomeOutliers)) {
438 newNIters = Integer.MAX_VALUE;
439 } else {
440 newNIters = (int) Math.ceil(Math.abs(Math.log(1.0 - confidence) / logProbSomeOutliers));
441 }
442 }
443 if (newNIters < nIters) {
444 nIters = newNIters;
445 }
446 }
447 }
448
449 if (nIters > 0) {
450 progress = Math.min((float) currentIter / (float) nIters, 1.0f);
451 } else {
452 progress = 1.0f;
453 }
454 if (progress - previousProgress > progressDelta) {
455 previousProgress = progress;
456 listener.onEstimateProgressChange(this, progress);
457 }
458 currentIter++;
459
460 listener.onEstimateNextIteration(this, currentIter);
461 }
462
463 // no solution could be found after completing all iterations
464 if (bestResult == null) {
465 throw new RobustEstimatorException();
466 }
467
468 listener.onEstimateEnd(this);
469
470 return bestResult;
471 } catch (final SubsetSelectorException e) {
472 throw new RobustEstimatorException(e);
473 } finally {
474 locked = false;
475 }
476 }
477
478 /**
479 * Returns data about inliers once estimation has been done.
480 *
481 * @return data about inliers or null if estimation has not been done.
482 */
483 @Override
484 public InliersData getInliersData() {
485 return getBestInliersData();
486 }
487
488
489 /**
490 * Returns method being used for robust estimation.
491 *
492 * @return method being used for robust estimation.
493 */
494 @Override
495 public RobustEstimatorMethod getMethod() {
496 return RobustEstimatorMethod.RANSAC;
497 }
498
499 /**
500 * Contains data related to estimated inliers.
501 */
502 public static class RANSACInliersData extends InliersData {
503
504 /**
505 * Efficiently stores which samples are considered inliers and which
506 * ones aren't.
507 */
508 private BitSet inliers;
509
510 /**
511 * Constructor.
512 *
513 * @param totalSamples total number of samples.
514 * @param keepInliers true to keep inliers, false otherwise.
515 * @param keepResiduals true to keep residuals, false otherwise.
516 */
517 protected RANSACInliersData(final int totalSamples, final boolean keepInliers, final boolean keepResiduals) {
518 if (keepInliers) {
519 inliers = new BitSet(totalSamples);
520 }
521 if (keepResiduals) {
522 residuals = new double[totalSamples];
523 }
524 numInliers = 0;
525 }
526
527 /**
528 * Returns efficient array indicating which samples are considered
529 * inliers and which ones aren't.
530 *
531 * @return array indicating which samples are considered inliers and
532 * which ones aren't.
533 */
534 @Override
535 public BitSet getInliers() {
536 return inliers;
537 }
538
539 /**
540 * Updates data contained in this instance.
541 *
542 * @param inliers efficiently stores which samples are considered
543 * inliers and which ones aren't.
544 * @param residuals residuals obtained for each sample of data.
545 * @param numInliers number of inliers found on current iteration.
546 */
547 protected void update(final BitSet inliers, final double[] residuals, final int numInliers) {
548 var totalSamples = 0;
549 if (inliers != null) {
550 totalSamples = inliers.length();
551 }
552 if (residuals != null) {
553 totalSamples = residuals.length;
554 }
555
556 if (this.inliers != null && inliers != null && this.residuals != null && residuals != null) {
557 // update inliers and residuals
558 for (var i = 0; i < totalSamples; i++) {
559 this.inliers.set(i, inliers.get(i));
560 this.residuals[i] = residuals[i];
561 }
562 } else if (this.inliers != null && inliers != null) {
563 // update inliers but not the residuals
564 for (var i = 0; i < totalSamples; i++) {
565 this.inliers.set(i, inliers.get(i));
566 }
567 } else if (this.residuals != null && residuals != null) {
568 // update residuals but not inliers
569 System.arraycopy(residuals, 0, this.residuals, 0, totalSamples);
570 }
571 this.numInliers = numInliers;
572 }
573 }
574 }