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.RANSACRobustEstimator;
23 import com.irurueta.numerical.robust.RANSACRobustEstimatorListener;
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 RANSAC algorithm.
33 */
34 @SuppressWarnings("DuplicatedCode")
35 public class RANSACLineCorrespondenceAffineTransformation2DRobustEstimator
36 extends LineCorrespondenceAffineTransformation2DRobustEstimator {
37
38 /**
39 * Constant defining default threshold to determine whether lines are
40 * inliers or not.
41 * Residuals to determine whether lines are inliers or not are computed by
42 * comparing two lines algebraically (e.g. doing the dot product of their
43 * parameters).
44 * A residual of 0 indicates that dot product was 1 or -1 and lines were
45 * equal.
46 * A residual of 1 indicates that dot product was 0 and lines were
47 * orthogonal.
48 * If dot product between lines is -1, then although their director vectors
49 * are opposed, lines are considered equal, since sign changes are not taken
50 * into account and their residuals will be 0.
51 */
52 public static final double DEFAULT_THRESHOLD = 1e-6;
53
54 /**
55 * Minimum value that can be set as threshold.
56 * Threshold must be strictly greater than 0.0.
57 */
58 public static final double MIN_THRESHOLD = 0.0;
59
60 /**
61 * Indicates that by default inliers will only be computed but not kept.
62 */
63 public static final boolean DEFAULT_COMPUTE_AND_KEEP_INLIERS = false;
64
65 /**
66 * Indicates that by default residuals will only be computed but not kept.
67 */
68 public static final boolean DEFAULT_COMPUTE_AND_KEEP_RESIDUALS = false;
69
70 /**
71 * Threshold to determine whether lines are inliers or not when testing
72 * possible estimation solutions.
73 * The threshold refers to the amount of error a possible solution has on a
74 * matched pair of lines.
75 */
76 private double threshold;
77
78 /**
79 * Indicates whether inliers must be computed and kept.
80 */
81 private boolean computeAndKeepInliers;
82
83 /**
84 * Indicates whether residuals must be computed and kept.
85 */
86 private boolean computeAndKeepResiduals;
87
88 /**
89 * Constructor.
90 */
91 public RANSACLineCorrespondenceAffineTransformation2DRobustEstimator() {
92 super();
93 threshold = DEFAULT_THRESHOLD;
94 computeAndKeepInliers = DEFAULT_COMPUTE_AND_KEEP_INLIERS;
95 computeAndKeepResiduals = DEFAULT_COMPUTE_AND_KEEP_RESIDUALS;
96 }
97
98 /**
99 * Constructor with lists of lines to be used to estimate an affine 2D
100 * transformation.
101 * Lines in the list located at the same position are considered to be
102 * matched. Hence, both lists must have the same size, and their size must
103 * be greater or equal than MINIMUM_SIZE.
104 *
105 * @param inputLines list of input lines to be used to estimate an affine
106 * 2D transformation.
107 * @param outputLines list of output lines to be used to estimate an affine
108 * 2D transformation.
109 * @throws IllegalArgumentException if provided lists of lines don't have
110 * the same size or their size is smaller than MINIMUM_SIZE.
111 */
112 public RANSACLineCorrespondenceAffineTransformation2DRobustEstimator(
113 final List<Line2D> inputLines, final List<Line2D> outputLines) {
114 super(inputLines, outputLines);
115 threshold = DEFAULT_THRESHOLD;
116 computeAndKeepInliers = DEFAULT_COMPUTE_AND_KEEP_INLIERS;
117 computeAndKeepResiduals = DEFAULT_COMPUTE_AND_KEEP_RESIDUALS;
118 }
119
120 /**
121 * Constructor.
122 *
123 * @param listener listener to be notified of events such as when estimation
124 * starts, ends or its progress significantly changes.
125 */
126 public RANSACLineCorrespondenceAffineTransformation2DRobustEstimator(
127 final AffineTransformation2DRobustEstimatorListener listener) {
128 super(listener);
129 threshold = DEFAULT_THRESHOLD;
130 computeAndKeepInliers = DEFAULT_COMPUTE_AND_KEEP_INLIERS;
131 computeAndKeepResiduals = DEFAULT_COMPUTE_AND_KEEP_RESIDUALS;
132 }
133
134 /**
135 * Constructor with listener and lists of lines to be used to estimate an
136 * affine 2D transformation.
137 * Lines in the list located at the same position are considered to be
138 * matched. Hence, both lists must have the same size, and their size must
139 * be greater or equal than MINIMUM_SIZE.
140 *
141 * @param listener listener to be notified of events such as when estimation
142 * starts, ends or its progress significantly changes.
143 * @param inputLines list of input lines to be used to estimate an affine
144 * 2D transformation.
145 * @param outputLines list of output lines to be used to estimate an affine
146 * 2D transformation.
147 * @throws IllegalArgumentException if provided lists of lines don't have
148 * the same size or their size is smaller than MINIMUM_SIZE.
149 */
150 public RANSACLineCorrespondenceAffineTransformation2DRobustEstimator(
151 final AffineTransformation2DRobustEstimatorListener listener,
152 final List<Line2D> inputLines, final List<Line2D> outputLines) {
153 super(listener, inputLines, outputLines);
154 threshold = DEFAULT_THRESHOLD;
155 computeAndKeepInliers = DEFAULT_COMPUTE_AND_KEEP_INLIERS;
156 computeAndKeepResiduals = DEFAULT_COMPUTE_AND_KEEP_RESIDUALS;
157 }
158
159 /**
160 * Returns threshold to determine whether lines are inliers or not when
161 * testing possible estimation solutions.
162 * Residuals to determine whether lines are inliers or not are computed by
163 * comparing two lines algebraically (e.g. doing the dot product of their
164 * parameters).
165 * A residual of 0 indicates that dot product was 1 or -1 and lines were
166 * equal.
167 * A residual of 1 indicates that dot product was 0 and lines were
168 * orthogonal.
169 * If dot product between lines is -1, then although their director vectors
170 * are opposed, lines are considered equal, since sign changes are not taken
171 * into account and their residuals will be 0.
172 *
173 * @return threshold to determine whether matched lines are inliers or not.
174 */
175 public double getThreshold() {
176 return threshold;
177 }
178
179 /**
180 * Sets threshold to determine whether lines are inliers or not when
181 * testing possible estimation solutions.
182 * Residuals to determine whether lines are inliers or not are computed by
183 * comparing two lines algebraically (e.g. doing the dot product of their
184 * parameters).
185 * A residual of 0 indicates that dot product was 1 or -1 and lines were
186 * equal.
187 * A residual of 1 indicates that dot product was 0 and lines were
188 * orthogonal.
189 * If dot product between lines is -1, then although their director vectors
190 * are opposed, lines are considered equal, since sign changes are not taken
191 * into account and their residuals will be 0.
192 *
193 * @param threshold threshold to determine whether matched lines are inliers
194 * or not.
195 * @throws IllegalArgumentException if provided value is equal or less than
196 * zero.
197 * @throws LockedException if robust estimator is locked because an
198 * estimation is already in progress.
199 */
200 public void setThreshold(final double threshold) throws LockedException {
201 if (isLocked()) {
202 throw new LockedException();
203 }
204 if (threshold <= MIN_THRESHOLD) {
205 throw new IllegalArgumentException();
206 }
207 this.threshold = threshold;
208 }
209
210 /**
211 * Indicates whether inliers must be computed and kept.
212 *
213 * @return true if inliers must be computed and kept, false if inliers only
214 * need to be computed but not kept.
215 */
216 public boolean isComputeAndKeepInliersEnabled() {
217 return computeAndKeepInliers;
218 }
219
220 /**
221 * Specifies whether inliers must be computed and kept.
222 *
223 * @param computeAndKeepInliers true if inliers must be computed and kept,
224 * false if inliers only need to be computed but not kept.
225 * @throws LockedException if estimator is locked.
226 */
227 public void setComputeAndKeepInliersEnabled(final boolean computeAndKeepInliers) throws LockedException {
228 if (isLocked()) {
229 throw new LockedException();
230 }
231 this.computeAndKeepInliers = computeAndKeepInliers;
232 }
233
234 /**
235 * Indicates whether residuals must be computed and kept.
236 *
237 * @return true if residuals must be computed and kept, false if residuals
238 * only need to be computed but not kept.
239 */
240 public boolean isComputeAndKeepResidualsEnabled() {
241 return computeAndKeepResiduals;
242 }
243
244 /**
245 * Specifies whether residuals must be computed and kept.
246 *
247 * @param computeAndKeepResiduals true if residuals must be computed and
248 * kept, false if residuals only need to be computed but not kept.
249 * @throws LockedException if estimator is locked.
250 */
251 public void setComputeAndKeepResidualsEnabled(final boolean computeAndKeepResiduals) throws LockedException {
252 if (isLocked()) {
253 throw new LockedException();
254 }
255 this.computeAndKeepResiduals = computeAndKeepResiduals;
256 }
257
258 /**
259 * Estimates an affine 2D transformation using a robust estimator and
260 * the best set of matched 2D lines correspondences found using the robust
261 * estimator.
262 *
263 * @return an affine 2D transformation.
264 * @throws LockedException if robust estimator is locked because an
265 * estimation is already in progress.
266 * @throws NotReadyException if provided input data is not enough to start
267 * the estimation.
268 * @throws RobustEstimatorException if estimation fails for any reason
269 * (i.e. numerical instability, no solution available, etc).
270 */
271 @Override
272 public AffineTransformation2D estimate() throws LockedException, NotReadyException, RobustEstimatorException {
273 if (isLocked()) {
274 throw new LockedException();
275 }
276 if (!isReady()) {
277 throw new NotReadyException();
278 }
279
280 final var innerEstimator = new RANSACRobustEstimator<>(
281 new RANSACRobustEstimatorListener<AffineTransformation2D>() {
282
283 // line to be reused when computing residuals
284 private final Line2D testLine = new Line2D();
285
286 @Override
287 public double getThreshold() {
288 return threshold;
289 }
290
291 @Override
292 public int getTotalSamples() {
293 return inputLines.size();
294 }
295
296 @Override
297 public int getSubsetSize() {
298 return AffineTransformation2DRobustEstimator.MINIMUM_SIZE;
299 }
300
301 @Override
302 public void estimatePreliminarSolutions(
303 final int[] samplesIndices, final List<AffineTransformation2D> solutions) {
304 final var inputLine1 = inputLines.get(samplesIndices[0]);
305 final var inputLine2 = inputLines.get(samplesIndices[1]);
306 final var inputLine3 = inputLines.get(samplesIndices[2]);
307
308 final var outputLine1 = outputLines.get(samplesIndices[0]);
309 final var outputLine2 = outputLines.get(samplesIndices[1]);
310 final var outputLine3 = outputLines.get(samplesIndices[2]);
311
312 try {
313 final var transformation = new AffineTransformation2D(inputLine1, inputLine2, inputLine3,
314 outputLine1, outputLine2, outputLine3);
315 solutions.add(transformation);
316 } catch (final CoincidentLinesException e) {
317 // if lines are coincident, no solution is added
318 }
319 }
320
321 @Override
322 public double computeResidual(final AffineTransformation2D currentEstimation, final int i) {
323 final var inputLine = inputLines.get(i);
324 final var outputLine = outputLines.get(i);
325
326 // transform input line and store result in mTestLine
327 try {
328 currentEstimation.transform(inputLine, testLine);
329
330 return getResidual(outputLine, testLine);
331 } catch (final AlgebraException e) {
332 // this happens when internal matrix of affine transformation
333 // cannot be reverse (i.e. transformation is not well-defined,
334 // numerical instabilities, etc.)
335 return Double.MAX_VALUE;
336 }
337 }
338
339 @Override
340 public boolean isReady() {
341 return RANSACLineCorrespondenceAffineTransformation2DRobustEstimator.this.isReady();
342 }
343
344 @Override
345 public void onEstimateStart(final RobustEstimator<AffineTransformation2D> estimator) {
346 if (mListener != null) {
347 mListener.onEstimateStart(
348 RANSACLineCorrespondenceAffineTransformation2DRobustEstimator.this);
349 }
350 }
351
352 @Override
353 public void onEstimateEnd(final RobustEstimator<AffineTransformation2D> estimator) {
354 if (mListener != null) {
355 mListener.onEstimateEnd(
356 RANSACLineCorrespondenceAffineTransformation2DRobustEstimator.this);
357 }
358 }
359
360 @Override
361 public void onEstimateNextIteration(
362 final RobustEstimator<AffineTransformation2D> estimator, final int iteration) {
363 if (mListener != null) {
364 mListener.onEstimateNextIteration(
365 RANSACLineCorrespondenceAffineTransformation2DRobustEstimator.this,
366 iteration);
367 }
368 }
369
370 @Override
371 public void onEstimateProgressChange(
372 final RobustEstimator<AffineTransformation2D> estimator, final float progress) {
373 if (mListener != null) {
374 mListener.onEstimateProgressChange(
375 RANSACLineCorrespondenceAffineTransformation2DRobustEstimator.this,
376 progress);
377 }
378 }
379 });
380
381 try {
382 locked = true;
383 inliersData = null;
384 innerEstimator.setComputeAndKeepInliersEnabled(computeAndKeepInliers || refineResult);
385 innerEstimator.setComputeAndKeepResidualsEnabled(computeAndKeepResiduals || refineResult);
386 innerEstimator.setConfidence(confidence);
387 innerEstimator.setMaxIterations(maxIterations);
388 innerEstimator.setProgressDelta(progressDelta);
389 final var transformation = innerEstimator.estimate();
390 inliersData = innerEstimator.getInliersData();
391 return attemptRefine(transformation);
392 } catch (final com.irurueta.numerical.LockedException e) {
393 throw new LockedException(e);
394 } catch (final com.irurueta.numerical.NotReadyException e) {
395 throw new NotReadyException(e);
396 } finally {
397 locked = false;
398 }
399 }
400
401 /**
402 * Returns method being used for robust estimation.
403 *
404 * @return method being used for robust estimation.
405 */
406 @Override
407 public RobustEstimatorMethod getMethod() {
408 return RobustEstimatorMethod.RANSAC;
409 }
410
411 /**
412 * Gets standard deviation used for Levenberg-Marquardt fitting during
413 * refinement.
414 * Returned value gives an indication of how much variance each residual
415 * has.
416 * Typically, this value is related to the threshold used on each robust
417 * estimation, since residuals of found inliers are within the range of
418 * such threshold.
419 *
420 * @return standard deviation used for refinement.
421 */
422 @Override
423 protected double getRefinementStandardDeviation() {
424 return threshold;
425 }
426 }