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