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