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.algebra.AlgebraException;
19 import com.irurueta.geometry.AffineTransformation2D;
20 import com.irurueta.geometry.CoincidentLinesException;
21 import com.irurueta.geometry.Line2D;
22 import com.irurueta.numerical.robust.LMedSRobustEstimator;
23 import com.irurueta.numerical.robust.LMedSRobustEstimatorListener;
24 import com.irurueta.numerical.robust.RobustEstimator;
25 import com.irurueta.numerical.robust.RobustEstimatorException;
26 import com.irurueta.numerical.robust.RobustEstimatorMethod;
27
28 import java.util.List;
29
30 /**
31 * Finds the best affine 2D transformation for provided collections of matched
32 * 2D lines using LMedS algorithm.
33 */
34 public class LMedSLineCorrespondenceAffineTransformation2DRobustEstimator extends
35 LineCorrespondenceAffineTransformation2DRobustEstimator {
36
37 /**
38 * Default value to be used for stop threshold. Stop threshold can be used
39 * to keep the algorithm iterating in case that best estimated threshold
40 * using median of residuals is not small enough. Once a solution is found
41 * that generates a threshold below this value, the algorithm will stop.
42 * The stop threshold can be used to prevent the LMedS algorithm iterating
43 * too many times in cases where samples have a very similar accuracy.
44 * For instance, in cases where proportion of outliers is very small (close
45 * to 0%), and samples are very accurate (i.e. 1e-6), the algorithm would
46 * iterate for a long time trying to find the best solution when indeed
47 * there is no need to do that if a reasonable threshold has already been
48 * reached.
49 * Because of this behaviour the stop threshold can be set to a value much
50 * lower than the one typically used in RANSAC, and yet the algorithm could
51 * still produce even smaller thresholds in estimated results.
52 */
53 public static final double DEFAULT_STOP_THRESHOLD = 1e-6;
54
55 /**
56 * Minimum allowed stop threshold value.
57 */
58 public static final double MIN_STOP_THRESHOLD = 0.0;
59
60 /**
61 * Threshold to be used to keep the algorithm iterating in case that best
62 * estimated threshold using median of residuals is not small enough. Once
63 * a solution is found that generates a threshold below this value, the
64 * algorithm will stop.
65 * The stop threshold can be used to prevent the LMedS algorithm iterating
66 * too many times in cases where samples have a very similar accuracy.
67 * For instance, in cases where proportion of outliers is very small (close
68 * to 0%), and samples are very accurate (i.e. 1e-6), the algorithm would
69 * iterate for a long time trying to find the best solution when indeed
70 * there is no need to do that if a reasonable threshold has already been
71 * reached.
72 * Because of this behaviour the stop threshold can be set to a value much
73 * lower than the one typically used in RANSAC, and yet the algorithm could
74 * still produce even smaller thresholds in estimated results.
75 */
76 private double stopThreshold;
77
78
79 /**
80 * Constructor.
81 */
82 public LMedSLineCorrespondenceAffineTransformation2DRobustEstimator() {
83 super();
84 stopThreshold = DEFAULT_STOP_THRESHOLD;
85 }
86
87 /**
88 * Constructor with lists of lines to be used to estimate an affine 2D
89 * transformation.
90 * Lines in the list located at the same position are considered to be
91 * matched. Hence, both lists must have the same size, and their size must
92 * be greater or equal than MINIMUM_SIZE.
93 *
94 * @param inputLines list of input lines to be used to estimate an affine
95 * 2D transformation.
96 * @param outputLines list of output lines to be used to estimate an affine
97 * 2D transformation.
98 * @throws IllegalArgumentException if provided lists of lines don't have
99 * the same size or their size is smaller than MINIMUM_SIZE.
100 */
101 public LMedSLineCorrespondenceAffineTransformation2DRobustEstimator(
102 final List<Line2D> inputLines, final List<Line2D> outputLines) {
103 super(inputLines, outputLines);
104 stopThreshold = DEFAULT_STOP_THRESHOLD;
105 }
106
107 /**
108 * Constructor.
109 *
110 * @param listener listener to be notified of events such as when estimation
111 * starts, ends or its progress significantly changes.
112 */
113 public LMedSLineCorrespondenceAffineTransformation2DRobustEstimator(
114 final AffineTransformation2DRobustEstimatorListener listener) {
115 super(listener);
116 stopThreshold = DEFAULT_STOP_THRESHOLD;
117 }
118
119 /**
120 * Constructor with listener and lists of lines to be used to estimate an
121 * affine 2D transformation.
122 * Lines in the list located at the same position are considered to be
123 * matched. Hence, both lists must have the same size, and their size must
124 * be greater or equal than MINIMUM_SIZE.
125 *
126 * @param listener listener to be notified of events such as when estimation
127 * starts, ends or its progress significantly changes.
128 * @param inputLines list of input lines to be used to estimate an affine
129 * 2D transformation.
130 * @param outputLines list of output lines to be used to estimate an affine
131 * 2D transformation.
132 * @throws IllegalArgumentException if provided lists of lines don't have
133 * the same size or their size is smaller than MINIMUM_SIZE.
134 */
135 public LMedSLineCorrespondenceAffineTransformation2DRobustEstimator(
136 final AffineTransformation2DRobustEstimatorListener listener,
137 final List<Line2D> inputLines, final List<Line2D> outputLines) {
138 super(listener, inputLines, outputLines);
139 stopThreshold = DEFAULT_STOP_THRESHOLD;
140 }
141
142 /**
143 * Returns threshold to be used to keep the algorithm iterating in case that
144 * best estimated threshold using median of residuals is not small enough.
145 * Once a solution is found that generates a threshold below this value, the
146 * algorithm will stop.
147 * The stop threshold can be used to prevent the LMedS algorithm iterating
148 * too many times in cases where samples have a very similar accuracy.
149 * For instance, in cases where proportion of outliers is very small (close
150 * to 0%), and samples are very accurate (i.e. 1e-6), the algorithm would
151 * iterate for a long time trying to find the best solution when indeed
152 * there is no need to do that if a reasonable threshold has already been
153 * reached.
154 * Because of this behaviour the stop threshold can be set to a value much
155 * lower than the one typically used in RANSAC, and yet the algorithm could
156 * still produce even smaller thresholds in estimated results.
157 *
158 * @return stop threshold to stop the algorithm prematurely when a certain
159 * accuracy has been reached.
160 */
161 public double getStopThreshold() {
162 return stopThreshold;
163 }
164
165 /**
166 * Sets threshold to be used to keep the algorithm iterating in case that
167 * best estimated threshold using median of residuals is not small enough.
168 * Once a solution is found that generates a threshold below this value, the
169 * algorithm will stop.
170 * The stop threshold can be used to prevent the LMedS algorithm iterating
171 * too many times in cases where samples have a very similar accuracy.
172 * For instance, in cases where proportion of outliers is very small (close
173 * to 0%), and samples are very accurate (i.e. 1e-6), the algorithm would
174 * iterate for a long time trying to find the best solution when indeed
175 * there is no need to do that if a reasonable threshold has already been
176 * reached.
177 * Because of this behaviour the stop threshold can be set to a value much
178 * lower than the one typically used in RANSAC, and yet the algorithm could
179 * still produce even smaller thresholds in estimated results.
180 *
181 * @param stopThreshold stop threshold to stop the algorithm prematurely
182 * when a certain accuracy has been reached.
183 * @throws IllegalArgumentException if provided value is zero or negative.
184 * @throws LockedException if robust estimator is locked because an
185 * estimation is already in progress.
186 */
187 public void setStopThreshold(final double stopThreshold) throws LockedException {
188 if (isLocked()) {
189 throw new LockedException();
190 }
191 if (stopThreshold <= MIN_STOP_THRESHOLD) {
192 throw new IllegalArgumentException();
193 }
194
195 this.stopThreshold = stopThreshold;
196 }
197
198 /**
199 * Estimates an affine 2D transformation using a robust estimator and
200 * the best set of matched 2D lines correspondences found using the robust
201 * estimator.
202 *
203 * @return an affine 2D transformation.
204 * @throws LockedException if robust estimator is locked because an
205 * estimation is already in progress.
206 * @throws NotReadyException if provided input data is not enough to start
207 * the estimation.
208 * @throws RobustEstimatorException if estimation fails for any reason
209 * (i.e. numerical instability, no solution available, etc).
210 */
211 @SuppressWarnings("DuplicatedCode")
212 @Override
213 public AffineTransformation2D estimate() throws LockedException, NotReadyException, RobustEstimatorException {
214 if (isLocked()) {
215 throw new LockedException();
216 }
217 if (!isReady()) {
218 throw new NotReadyException();
219 }
220
221 final var innerEstimator = new LMedSRobustEstimator<>(
222 new LMedSRobustEstimatorListener<AffineTransformation2D>() {
223
224 // line to be reused when computing residuals
225 private final Line2D testLine = new Line2D();
226
227 @Override
228 public int getTotalSamples() {
229 return inputLines.size();
230 }
231
232 @Override
233 public int getSubsetSize() {
234 return AffineTransformation2DRobustEstimator.MINIMUM_SIZE;
235 }
236
237 @Override
238 public void estimatePreliminarSolutions(
239 final int[] samplesIndices, final List<AffineTransformation2D> solutions) {
240 final var inputLine1 = inputLines.get(samplesIndices[0]);
241 final var inputLine2 = inputLines.get(samplesIndices[1]);
242 final var inputLine3 = inputLines.get(samplesIndices[2]);
243
244 final var outputLine1 = outputLines.get(samplesIndices[0]);
245 final var outputLine2 = outputLines.get(samplesIndices[1]);
246 final var outputLine3 = outputLines.get(samplesIndices[2]);
247
248 try {
249 final var transformation = new AffineTransformation2D(inputLine1, inputLine2, inputLine3,
250 outputLine1, outputLine2, outputLine3);
251 solutions.add(transformation);
252 } catch (final CoincidentLinesException e) {
253 // if lines are coincident, no solution is added
254 }
255 }
256
257 @Override
258 public double computeResidual(final AffineTransformation2D currentEstimation, final int i) {
259 final var inputLine = inputLines.get(i);
260 final var outputLine = outputLines.get(i);
261
262 // transform input line and store result in mTestLine
263 try {
264 currentEstimation.transform(inputLine, testLine);
265
266 return getResidual(outputLine, testLine);
267 } catch (final AlgebraException e) {
268 // this happens when internal matrix of affine transformation
269 // cannot be reverse (i.e. transformation is not well-defined,
270 // numerical instabilities, etc.)
271 return Double.MAX_VALUE;
272 }
273 }
274
275 @Override
276 public boolean isReady() {
277 return LMedSLineCorrespondenceAffineTransformation2DRobustEstimator.this.isReady();
278 }
279
280 @Override
281 public void onEstimateStart(final RobustEstimator<AffineTransformation2D> estimator) {
282 if (mListener != null) {
283 mListener.onEstimateStart(
284 LMedSLineCorrespondenceAffineTransformation2DRobustEstimator.this);
285 }
286 }
287
288 @Override
289 public void onEstimateEnd(final RobustEstimator<AffineTransformation2D> estimator) {
290 if (mListener != null) {
291 mListener.onEstimateEnd(
292 LMedSLineCorrespondenceAffineTransformation2DRobustEstimator.this);
293 }
294 }
295
296 @Override
297 public void onEstimateNextIteration(
298 final RobustEstimator<AffineTransformation2D> estimator, final int iteration) {
299 if (mListener != null) {
300 mListener.onEstimateNextIteration(
301 LMedSLineCorrespondenceAffineTransformation2DRobustEstimator.this,
302 iteration);
303 }
304 }
305
306 @Override
307 public void onEstimateProgressChange(
308 final RobustEstimator<AffineTransformation2D> estimator, final float progress) {
309 if (mListener != null) {
310 mListener.onEstimateProgressChange(
311 LMedSLineCorrespondenceAffineTransformation2DRobustEstimator.this,
312 progress);
313 }
314 }
315 });
316
317 try {
318 locked = true;
319 inliersData = null;
320 innerEstimator.setConfidence(confidence);
321 innerEstimator.setMaxIterations(maxIterations);
322 innerEstimator.setProgressDelta(progressDelta);
323 innerEstimator.setStopThreshold(stopThreshold);
324 final var transformation = innerEstimator.estimate();
325 inliersData = innerEstimator.getInliersData();
326 return attemptRefine(transformation);
327 } catch (final com.irurueta.numerical.LockedException e) {
328 throw new LockedException(e);
329 } catch (final com.irurueta.numerical.NotReadyException e) {
330 throw new NotReadyException(e);
331 } finally {
332 locked = false;
333 }
334 }
335
336 /**
337 * Returns method being used for robust estimation.
338 *
339 * @return method being used for robust estimation.
340 */
341 @Override
342 public RobustEstimatorMethod getMethod() {
343 return RobustEstimatorMethod.LMEDS;
344 }
345
346 /**
347 * Gets standard deviation used for Levenberg-Marquardt fitting during
348 * refinement.
349 * Returned value gives an indication of how much variance each residual
350 * has.
351 * Typically, this value is related to the threshold used on each robust
352 * estimation, since residuals of found inliers are within the range of
353 * such threshold.
354 *
355 * @return standard deviation used for refinement.
356 */
357 @Override
358 protected double getRefinementStandardDeviation() {
359 final var inliersData = (LMedSRobustEstimator.LMedSInliersData) getInliersData();
360
361 // avoid setting a threshold too strict
362 final var threshold = inliersData.getEstimatedThreshold();
363 return Math.max(threshold, stopThreshold);
364 }
365 }