1 /*
2 * Copyright (C) 2016 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.polynomials.estimators;
17
18 import com.irurueta.numerical.LockedException;
19 import com.irurueta.numerical.NotReadyException;
20 import com.irurueta.numerical.polynomials.Polynomial;
21 import com.irurueta.numerical.robust.LMedSRobustEstimator;
22 import com.irurueta.numerical.robust.LMedSRobustEstimatorListener;
23 import com.irurueta.numerical.robust.RobustEstimator;
24 import com.irurueta.numerical.robust.RobustEstimatorException;
25 import com.irurueta.numerical.robust.RobustEstimatorMethod;
26
27 import java.util.ArrayList;
28 import java.util.List;
29
30 /**
31 * Finds the best polynomial using LMedS algorithm.
32 */
33 public class LMedSPolynomialRobustEstimator extends PolynomialRobustEstimator {
34
35 /**
36 * Default value to be used for stop threshold. Stop threshold can be used
37 * to keep the algorithm iterating in case that best estimated threshold
38 * using median of residuals is not small enough. Once a solutions is found
39 * that generates a threshold below this value, the algorithm will stop.
40 * Threshold will be used to compare either algebraic or geometric distance
41 * of estimated polynomial respect each provided evaluation.
42 */
43 public static final double DEFAULT_STOP_THRESHOLD = 1e-6;
44
45 /**
46 * Minimum value that can be set as stop threshold.
47 * Threshold must be strictly greater than 0.0.
48 */
49 public static final double MIN_STOP_THRESHOLD = 0.0;
50
51 /**
52 * Threshold to be used to keep the algorithm iterating in case that best
53 * estimated threshold using median of residuals is not small enough. Once
54 * a solution is found that generates a threshold below this value, the
55 * algorithm will stop.
56 * The stop threshold can be used to prevent the LMedS algorithm iterating
57 * too many times in case where samples have a very similar accuracy.
58 * For instance, in cases where proportion of outliers is very small (close
59 * to 0%), and samples are very accurate (i.e. 1e-6), the algorithm would
60 * iterate for a long time trying to find the best solution when indeed
61 * there is no need to do that if a reasonable threshold has already been
62 * reached.
63 * Because of this behaviour the sopt threshold can be set to a value much
64 * lower than the one typically used in RANSAC, and yet the algorithm could
65 * still produce even smaller thresholds in estimated results.
66 */
67 private double stopThreshold;
68
69 /**
70 * Constructor.
71 */
72 public LMedSPolynomialRobustEstimator() {
73 super();
74 stopThreshold = DEFAULT_STOP_THRESHOLD;
75 }
76
77 /**
78 * Constructor.
79 *
80 * @param degree degree of polynomial to be estimated.
81 * @throws IllegalArgumentException if provided degree is less than 1.
82 */
83 public LMedSPolynomialRobustEstimator(final int degree) {
84 super(degree);
85 stopThreshold = DEFAULT_STOP_THRESHOLD;
86 }
87
88 /**
89 * Constructor.
90 *
91 * @param evaluations collections of polynomial evaluations.
92 * @throws IllegalArgumentException if provided number of evaluations is
93 * less than the required minimum.
94 */
95 public LMedSPolynomialRobustEstimator(final List<PolynomialEvaluation> evaluations) {
96 super(evaluations);
97 stopThreshold = DEFAULT_STOP_THRESHOLD;
98 }
99
100 /**
101 * Constructor.
102 *
103 * @param listener listener to be notified of events such as when estimation
104 * starts, ends or its progress significantly changes.
105 */
106 public LMedSPolynomialRobustEstimator(final PolynomialRobustEstimatorListener listener) {
107 super(listener);
108 stopThreshold = DEFAULT_STOP_THRESHOLD;
109 }
110
111 /**
112 * Constructor.
113 *
114 * @param degree degree of polynomial to be estimated.
115 * @param evaluations collection of polynomial evaluations.
116 * @throws IllegalArgumentException if provided degree is less than 1 or if
117 * provided number of evaluations is less than the required minimum for
118 * provided degree.
119 */
120 public LMedSPolynomialRobustEstimator(final int degree, final List<PolynomialEvaluation> evaluations) {
121 super(degree, evaluations);
122 stopThreshold = DEFAULT_STOP_THRESHOLD;
123 }
124
125 /**
126 * Constructor.
127 *
128 * @param degree degree of polynomial to be estimated.
129 * @param listener listener to be notified of events such as when estimation
130 * starts, ends or its progress significantly changes.
131 * @throws IllegalArgumentException if provided degree is less than 1.
132 */
133 public LMedSPolynomialRobustEstimator(final int degree, final PolynomialRobustEstimatorListener listener) {
134 super(degree, listener);
135 stopThreshold = DEFAULT_STOP_THRESHOLD;
136 }
137
138 /**
139 * Constructor.
140 *
141 * @param evaluations collection of polynomial evaluations.
142 * @param listener listener to be notified of events such as when estimation
143 * starts, ends or its progress significantly changes.
144 * @throws IllegalArgumentException if provided number of evaluations is
145 * less than the required minimum.
146 */
147 public LMedSPolynomialRobustEstimator(
148 final List<PolynomialEvaluation> evaluations, final PolynomialRobustEstimatorListener listener) {
149 super(evaluations, listener);
150 stopThreshold = DEFAULT_STOP_THRESHOLD;
151 }
152
153 /**
154 * Constructor.
155 *
156 * @param degree degree of polynomial to be estimated.
157 * @param evaluations collection of polynomial evaluations.
158 * @param listener listener to be notified of events such as when estimation
159 * starts, ends or its progress significantly changes.
160 * @throws IllegalArgumentException if provided degree is less than 1 or if
161 * provided number of evaluations is less than the required minimum for
162 * provided degree.
163 */
164 public LMedSPolynomialRobustEstimator(
165 final int degree, final List<PolynomialEvaluation> evaluations,
166 final PolynomialRobustEstimatorListener listener) {
167 super(degree, evaluations, listener);
168 stopThreshold = DEFAULT_STOP_THRESHOLD;
169 }
170
171 /**
172 * Returns threshold to be used to keep the algorithm iterating in case that
173 * best estimated threshold using median of residuals is not small enough.
174 * Once a solution is found that generates a threshold below this value, the
175 * algorithm will stop.
176 * The stop threshold can be used to prevent the LMedS algorithm iterating
177 * too many times in cases where samples have a very similar accuracy.
178 * For instance, in cases where proportion of outliers is very small (close
179 * to 0%), and samples are very accurate (i.e. 1e-6), the algorithm would
180 * iterate for a long time trying to find the best solution when indeed
181 * there is no need to do that if a reasonable threshold has already been
182 * reached.
183 * Because of this behaviour the stop threshold can be set to a value much
184 * lower than the one typically used in RANSAC, and yet the algorithm could
185 * still produce even smaller thresholds in estimated results.
186 *
187 * @return stop threshold to stop the algorithm prematurely when a certain
188 * accuracy has been reached.
189 */
190 public double getStopThreshold() {
191 return stopThreshold;
192 }
193
194 /**
195 * Sets threshold to be used to keep the algorithm iterating in case that
196 * best estimated threshold using median of residuals is not small enough.
197 * Once a solution is found that generates a threshold below this value, the
198 * algorithm will stop.
199 * The stop threshold can be used to prevent the LMedS algorithm iterating
200 * too many times in cases where samples have a very similar accuracy.
201 * For instance, in cases where proportion of outliers is very small (close
202 * to 0%), and samples are very accurate (i.e. 1e-6), the algorithm would
203 * iterate for a long time trying to find the best solution when indeed
204 * there is no need to do that if a reasonable threshold has already been
205 * reached.
206 * Because of this behaviour the stop threshold can be set to a value much
207 * lower than the one typically used in RANSAC, and yet the algorithm could
208 * still produce even smaller thresholds in estimated results
209 *
210 * @param stopThreshold stop threshold to stop the algorithm prematurely
211 * when a certain accuracy has been reached
212 * @throws IllegalArgumentException if provided value is zero or negative
213 * @throws LockedException if robust estimator is locked because an
214 * estimation is already in progress
215 */
216 public void setStopThreshold(final double stopThreshold) throws LockedException {
217 if (isLocked()) {
218 throw new LockedException();
219 }
220 if (stopThreshold <= MIN_STOP_THRESHOLD) {
221 throw new IllegalArgumentException();
222 }
223 this.stopThreshold = stopThreshold;
224 }
225
226 /**
227 * Estimates polynomial.
228 *
229 * @return estimated polynomial.
230 * @throws LockedException if robust estimator is locked because an
231 * estimation is already in progress.
232 * @throws NotReadyException if provided input data is not enough to start
233 * the estimation.
234 * @throws RobustEstimatorException if estimation fails for any other reason
235 * (i.e. numerical instability, no solution available, etc).
236 */
237 @Override
238 public Polynomial estimate() throws LockedException, NotReadyException, RobustEstimatorException {
239 if (isLocked()) {
240 throw new LockedException();
241 }
242 if (!isReady()) {
243 throw new NotReadyException();
244 }
245
246 final LMedSRobustEstimator<Polynomial> innerEstimator =
247 new LMedSRobustEstimator<>(new LMedSRobustEstimatorListener<>() {
248
249 // subset of evaluations picked on each iteration
250 private final List<PolynomialEvaluation> subsetEvaluations = new ArrayList<>();
251
252 @Override
253 public int getTotalSamples() {
254 return evaluations.size();
255 }
256
257 @Override
258 public int getSubsetSize() {
259 return polynomialEstimator.getMinNumberOfEvaluations();
260 }
261
262 @Override
263 public void estimatePreliminarSolutions(
264 final int[] samplesIndices, final List<Polynomial> solutions) {
265 subsetEvaluations.clear();
266 for (final var samplesIndex : samplesIndices) {
267 subsetEvaluations.add(evaluations.get(samplesIndex));
268 }
269
270 try {
271 polynomialEstimator.setLMSESolutionAllowed(false);
272 polynomialEstimator.setEvaluations(subsetEvaluations);
273
274 final var polynomial = polynomialEstimator.estimate();
275 solutions.add(polynomial);
276 } catch (final Exception e) {
277 // if anything fails, no solution is added
278 }
279 }
280
281 @Override
282 public double computeResidual(final Polynomial currentEstimation, final int i) {
283 final var eval = evaluations.get(i);
284 return getDistance(eval, currentEstimation);
285 }
286
287 @Override
288 public boolean isReady() {
289 return LMedSPolynomialRobustEstimator.this.isReady();
290 }
291
292 @Override
293 public void onEstimateStart(final RobustEstimator<Polynomial> estimator) {
294 if (listener != null) {
295 listener.onEstimateStart(LMedSPolynomialRobustEstimator.this);
296 }
297 }
298
299 @Override
300 public void onEstimateEnd(final RobustEstimator<Polynomial> estimator) {
301 if (listener != null) {
302 listener.onEstimateEnd(LMedSPolynomialRobustEstimator.this);
303 }
304 }
305
306 @Override
307 public void onEstimateNextIteration(
308 final RobustEstimator<Polynomial> estimator, final int iteration) {
309 if (listener != null) {
310 listener.onEstimateNextIteration(LMedSPolynomialRobustEstimator.this, iteration);
311 }
312 }
313
314 @Override
315 public void onEstimateProgressChange(
316 final RobustEstimator<Polynomial> estimator, final float progress) {
317 if (listener != null) {
318 listener.onEstimateProgressChange(LMedSPolynomialRobustEstimator.this, progress);
319 }
320 }
321 });
322
323 try {
324 locked = true;
325 innerEstimator.setConfidence(confidence);
326 innerEstimator.setMaxIterations(maxIterations);
327 innerEstimator.setProgressDelta(progressDelta);
328 innerEstimator.setStopThreshold(stopThreshold);
329 return innerEstimator.estimate();
330 } finally {
331 locked = false;
332 }
333 }
334
335 /**
336 * Returns method being used for robust estimation.
337 *
338 * @return method being used for robust estimation.
339 */
340 @Override
341 public RobustEstimatorMethod getMethod() {
342 return RobustEstimatorMethod.LMEDS;
343 }
344 }