1 /*
2 * Copyright (C) 2015 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.geometry.estimators;
17
18 import com.irurueta.geometry.CoincidentLinesException;
19 import com.irurueta.geometry.DualConic;
20 import com.irurueta.geometry.Line2D;
21 import com.irurueta.numerical.robust.PROMedSRobustEstimator;
22 import com.irurueta.numerical.robust.PROMedSRobustEstimatorListener;
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.List;
28
29 /**
30 * Finds the best conic for provided collection of 2D lines using PROMedS
31 * algorithm.
32 */
33 @SuppressWarnings("DuplicatedCode")
34 public class PROMedSDualConicRobustEstimator extends DualConicRobustEstimator {
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 solution is found
39 * that generates a threshold below this value, the algorithm will stop.
40 * The stop threshold can be used to prevent the LMedS algorithm iterating
41 * too many times in cases where samples have a very similar accuracy.
42 * For instance, in cases where proportion of outliers is very small (close
43 * to 0%), and samples are very accurate (i.e. 1e-6), the algorithm would
44 * iterate for a long time trying to find the best solution when indeed
45 * there is no need to do that if a reasonable threshold has already been
46 * reached.
47 * Because of this behaviour the stop threshold can be set to a value much
48 * lower than the one typically used in RANSAC, and yet the algorithm could
49 * still produce even smaller thresholds in estimated results.
50 */
51 public static final double DEFAULT_STOP_THRESHOLD = 1e-9;
52
53 /**
54 * Minimum allowed stop threshold value.
55 */
56 public static final double MIN_STOP_THRESHOLD = 0.0;
57
58 /**
59 * Threshold to be used to keep the algorithm iterating in case that best
60 * estimated threshold using median of residuals is not small enough. Once
61 * a solution is found that generates a threshold below this value, the
62 * algorithm will stop.
63 * The stop threshold can be used to prevent the LMedS algorithm iterating
64 * too many times in cases where samples have a very similar accuracy.
65 * For instance, in cases where proportion of outliers is very small (close
66 * to 0%), and samples are very accurate (i.e. 1e-6), the algorithm would
67 * iterate for a long time trying to find the best solution when indeed
68 * there is no need to do that if a reasonable threshold has already been
69 * reached.
70 * Because of this behaviour the stop threshold can be set to a value much
71 * lower than the one typically used in RANSAC, and yet the algorithm could
72 * still produce even smaller thresholds in estimated results.
73 */
74 private double stopThreshold;
75
76 /**
77 * Quality scores corresponding to each 2D line.
78 * The larger the score value the better the quality of the sample.
79 */
80 private double[] qualityScores;
81
82 /**
83 * Constructor.
84 */
85 public PROMedSDualConicRobustEstimator() {
86 super();
87 stopThreshold = DEFAULT_STOP_THRESHOLD;
88 }
89
90 /**
91 * Constructor with points.
92 *
93 * @param lines 2D lines to estimate a dual conic.
94 * @throws IllegalArgumentException if provided list of lines don't have
95 * a size greater or equal than MINIMUM_SIZE.
96 */
97 public PROMedSDualConicRobustEstimator(final List<Line2D> lines) {
98 super(lines);
99 stopThreshold = DEFAULT_STOP_THRESHOLD;
100 }
101
102 /**
103 * Constructor.
104 *
105 * @param listener listener to be notified of events such as when estimation
106 * starts, ends or its progress significantly changes.
107 */
108 public PROMedSDualConicRobustEstimator(final DualConicRobustEstimatorListener listener) {
109 super(listener);
110 stopThreshold = DEFAULT_STOP_THRESHOLD;
111 }
112
113
114 /**
115 * Constructor.
116 *
117 * @param listener listener to be notified of events such as when estimation
118 * starts, ends or its progress significantly changes.
119 * @param lines 2D lines to estimate a dual conic.
120 * @throws IllegalArgumentException if provided list of lines don't have
121 * a size greater or equal than MINIMUM_SIZE.
122 */
123 public PROMedSDualConicRobustEstimator(final DualConicRobustEstimatorListener listener, final List<Line2D> lines) {
124 super(listener, lines);
125 stopThreshold = DEFAULT_STOP_THRESHOLD;
126 }
127
128 /**
129 * Constructor.
130 *
131 * @param qualityScores quality scores corresponding to each provided line.
132 * @throws IllegalArgumentException if provided quality scores length is
133 * smaller than MINIMUM_SIZE (i.e. 5 lines).
134 */
135 public PROMedSDualConicRobustEstimator(final double[] qualityScores) {
136 super();
137 stopThreshold = DEFAULT_STOP_THRESHOLD;
138 internalSetQualityScores(qualityScores);
139 }
140
141 /**
142 * Constructor with points.
143 *
144 * @param lines 2D lines to estimate a dual conic.
145 * @param qualityScores quality scores corresponding to each provided line.
146 * @throws IllegalArgumentException if provided list of lines don't have
147 * the same size as the list of provided quality scores, or it their size
148 * is not greater or equal than MINIMUM_SIZE.
149 */
150 public PROMedSDualConicRobustEstimator(final List<Line2D> lines, final double[] qualityScores) {
151 super(lines);
152
153 if (qualityScores.length != lines.size()) {
154 throw new IllegalArgumentException();
155 }
156
157 stopThreshold = DEFAULT_STOP_THRESHOLD;
158 internalSetQualityScores(qualityScores);
159 }
160
161 /**
162 * Constructor.
163 *
164 * @param listener listener to be notified of events such as when estimation
165 * starts, ends or its progress significantly changes.
166 * @param qualityScores quality scores corresponding to each provided line.
167 * @throws IllegalArgumentException if provided quality scores length is
168 * smaller than MINIMUM_SIZE (i.e. 5 lines).
169 */
170 public PROMedSDualConicRobustEstimator(
171 final DualConicRobustEstimatorListener listener, final double[] qualityScores) {
172 super(listener);
173 stopThreshold = DEFAULT_STOP_THRESHOLD;
174 internalSetQualityScores(qualityScores);
175 }
176
177
178 /**
179 * Constructor.
180 *
181 * @param listener listener to be notified of events such as when estimation
182 * starts, ends or its progress significantly changes.
183 * @param lines 2D lines to estimate a dual conic.
184 * @param qualityScores quality scores corresponding to each provided line.
185 * @throws IllegalArgumentException if provided list of points don't have
186 * the same size as the list of provided quality scores, or it their size
187 * is not greater or equal than MINIMUM_SIZE.
188 */
189 public PROMedSDualConicRobustEstimator(
190 final DualConicRobustEstimatorListener listener, final List<Line2D> lines, final double[] qualityScores) {
191 super(listener, lines);
192
193 if (qualityScores.length != lines.size()) {
194 throw new IllegalArgumentException();
195 }
196
197 stopThreshold = DEFAULT_STOP_THRESHOLD;
198 internalSetQualityScores(qualityScores);
199 }
200
201 /**
202 * Returns threshold to be used to keep the algorithm iterating in case that
203 * best estimated threshold using median of residuals is not small enough.
204 * Once a solution is found that generates a threshold below this value, the
205 * algorithm will stop.
206 * As in LMedS, the stop threshold can be used to prevent the PROMedS
207 * algorithm iterating too many times in cases where samples have a very
208 * similar accuracy.
209 * For instance, in cases where proportion of outliers is very small (close
210 * to 0%), and samples are very accurate (i.e. 1e-6), the algorithm would
211 * iterate for a long time trying to find the best solution when indeed
212 * there is no need to do that if a reasonable threshold has already been
213 * reached.
214 * Because of this behaviour the stop threshold can be set to a value much
215 * lower than the one typically used in RANSAC, and yet the algorithm could
216 * still produce even smaller thresholds in estimated results.
217 *
218 * @return stop threshold to stop the algorithm prematurely when a certain
219 * accuracy has been reached.
220 */
221 public double getStopThreshold() {
222 return stopThreshold;
223 }
224
225 /**
226 * Sets threshold to be used to keep the algorithm iterating in case that
227 * best estimated threshold using median of residuals is not small enough.
228 * Once a solution is found that generates a threshold below this value, the
229 * algorithm will stop.
230 * As in LMedS, the stop threshold can be used to prevent the PROMedS
231 * algorithm iterating too many times in cases where samples have a very
232 * similar accuracy.
233 * For instance, in cases where proportion of outliers is very small (close
234 * to 0%), and samples are very accurate (i.e. 1e-6), the algorithm would
235 * iterate for a long time trying to find the best solution when indeed
236 * there is no need to do that if a reasonable threshold has already been
237 * reached.
238 * Because of this behaviour the stop threshold can be set to a value much
239 * lower than the one typically used in RANSAC, and yet the algorithm could
240 * still produce even smaller thresholds in estimated results.
241 *
242 * @param stopThreshold stop threshold to stop the algorithm prematurely
243 * when a certain accuracy has been reached.
244 * @throws IllegalArgumentException if provided value is zero or negative.
245 * @throws LockedException if robust estimator is locked because an
246 * estimation is already in progress.
247 */
248 public void setStopThreshold(final double stopThreshold) throws LockedException {
249 if (isLocked()) {
250 throw new LockedException();
251 }
252 if (stopThreshold <= MIN_STOP_THRESHOLD) {
253 throw new IllegalArgumentException();
254 }
255
256 this.stopThreshold = stopThreshold;
257 }
258
259 /**
260 * Returns quality scores corresponding to each provided line.
261 * The larger the score value the better the quality of the sampled line.
262 *
263 * @return quality scores corresponding to each point.
264 */
265 @Override
266 public double[] getQualityScores() {
267 return qualityScores;
268 }
269
270 /**
271 * Sets quality scores corresponding to each provided line.
272 * The larger the score value the better the quality of the sampled line.
273 *
274 * @param qualityScores quality scores corresponding to each line.
275 * @throws LockedException if robust estimator is locked because an
276 * estimation is already in progress.
277 * @throws IllegalArgumentException if provided quality scores length is
278 * smaller than MINIMUM_SIZE (i.e. 5 samples).
279 */
280 @Override
281 public void setQualityScores(final double[] qualityScores) throws LockedException {
282 if (isLocked()) {
283 throw new LockedException();
284 }
285 internalSetQualityScores(qualityScores);
286 }
287
288 /**
289 * Indicates if estimator is ready to start the conic estimation.
290 * This is true when input data (i.e. 2D points and quality scores) are
291 * provided and a minimum of MINIMUM_SIZE lines are available
292 *
293 * @return true if estimator is ready, false otherwise.
294 */
295 @Override
296 public boolean isReady() {
297 return super.isReady() && qualityScores != null && qualityScores.length == lines.size();
298 }
299
300 /**
301 * Estimates a dual conic using a robust estimator and the best set of 2D
302 * lines that fit into the locus of the estimated dual conic found using the
303 * robust estimator.
304 *
305 * @return a dual conic.
306 * @throws LockedException if robust estimator is locked because an
307 * estimation is already in progress.
308 * @throws NotReadyException if provided input data is not enough to start
309 * the estimation.
310 * @throws RobustEstimatorException if estimation fails for any reason
311 * (i.e. numerical instability, no solution available, etc).
312 */
313 @Override
314 public DualConic estimate() throws LockedException, NotReadyException, RobustEstimatorException {
315 if (isLocked()) {
316 throw new LockedException();
317 }
318 if (!isReady()) {
319 throw new NotReadyException();
320 }
321
322 final var innerEstimator = new PROMedSRobustEstimator<>(new PROMedSRobustEstimatorListener<DualConic>() {
323
324 @Override
325 public double getThreshold() {
326 return stopThreshold;
327 }
328
329 @Override
330 public int getTotalSamples() {
331 return lines.size();
332 }
333
334 @Override
335 public int getSubsetSize() {
336 return DualConicRobustEstimator.MINIMUM_SIZE;
337 }
338
339 @Override
340 public void estimatePreliminarSolutions(final int[] samplesIndices, final List<DualConic> solutions) {
341 final var line1 = lines.get(samplesIndices[0]);
342 final var line2 = lines.get(samplesIndices[1]);
343 final var line3 = lines.get(samplesIndices[2]);
344 final var line4 = lines.get(samplesIndices[3]);
345 final var line5 = lines.get(samplesIndices[4]);
346
347 try {
348 final var dualConic = new DualConic(line1, line2, line3, line4, line5);
349 solutions.add(dualConic);
350 } catch (final CoincidentLinesException e) {
351 // if points are coincident, no solution is added
352 }
353 }
354
355 @Override
356 public double computeResidual(final DualConic currentEstimation, final int i) {
357 return residual(currentEstimation, lines.get(i));
358 }
359
360 @Override
361 public boolean isReady() {
362 return PROMedSDualConicRobustEstimator.this.isReady();
363 }
364
365 @Override
366 public void onEstimateStart(final RobustEstimator<DualConic> estimator) {
367 if (listener != null) {
368 listener.onEstimateStart(PROMedSDualConicRobustEstimator.this);
369 }
370 }
371
372 @Override
373 public void onEstimateEnd(final RobustEstimator<DualConic> estimator) {
374 if (listener != null) {
375 listener.onEstimateEnd(PROMedSDualConicRobustEstimator.this);
376 }
377 }
378
379 @Override
380 public void onEstimateNextIteration(final RobustEstimator<DualConic> estimator, final int iteration) {
381 if (listener != null) {
382 listener.onEstimateNextIteration(PROMedSDualConicRobustEstimator.this, iteration);
383 }
384 }
385
386 @Override
387 public void onEstimateProgressChange(final RobustEstimator<DualConic> estimator, final float progress) {
388 if (listener != null) {
389 listener.onEstimateProgressChange(PROMedSDualConicRobustEstimator.this, progress);
390 }
391 }
392
393 @Override
394 public double[] getQualityScores() {
395 return qualityScores;
396 }
397 });
398
399 try {
400 locked = true;
401 innerEstimator.setConfidence(confidence);
402 innerEstimator.setMaxIterations(maxIterations);
403 innerEstimator.setProgressDelta(progressDelta);
404 return innerEstimator.estimate();
405 } catch (final com.irurueta.numerical.LockedException e) {
406 throw new LockedException(e);
407 } catch (final com.irurueta.numerical.NotReadyException e) {
408 throw new NotReadyException(e);
409 } finally {
410 locked = false;
411 }
412 }
413
414 /**
415 * Returns method being used for robust estimation.
416 *
417 * @return method being used for robust estimation.
418 */
419 @Override
420 public RobustEstimatorMethod getMethod() {
421 return RobustEstimatorMethod.PROMEDS;
422 }
423
424 /**
425 * Sets quality scores corresponding to each provided line.
426 * This method is used internally and does not check whether instance is
427 * locked or not.
428 *
429 * @param qualityScores quality scores to be set.
430 * @throws IllegalArgumentException if provided quality scores length is
431 * smaller than MINIMUM_SIZE.
432 */
433 private void internalSetQualityScores(final double[] qualityScores) {
434 if (qualityScores.length < MINIMUM_SIZE) {
435 throw new IllegalArgumentException();
436 }
437
438 this.qualityScores = qualityScores;
439 }
440 }