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.CoincidentLinesException;
20 import com.irurueta.geometry.Line2D;
21 import com.irurueta.geometry.ProjectiveTransformation2D;
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 projective transformation for provided collections of matched
32 * 2D lines using RANSAC algorithm.
33 */
34 @SuppressWarnings("DuplicatedCode")
35 public class RANSACLineCorrespondenceProjectiveTransformation2DRobustEstimator
36 extends LineCorrespondenceProjectiveTransformation2DRobustEstimator {
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 RANSACLineCorrespondenceProjectiveTransformation2DRobustEstimator() {
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 a projective 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 a projective
106 * 2D transformation
107 * @param outputLines list of output lines to be used to estimate a
108 * projective 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 RANSACLineCorrespondenceProjectiveTransformation2DRobustEstimator(
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 RANSACLineCorrespondenceProjectiveTransformation2DRobustEstimator(
127 final ProjectiveTransformation2DRobustEstimatorListener 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 a
136 * projective 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 a projective
144 * 2D transformation.
145 * @param outputLines list of output lines to be used to estimate a
146 * projective 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 RANSACLineCorrespondenceProjectiveTransformation2DRobustEstimator(
151 final ProjectiveTransformation2DRobustEstimatorListener 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 a projective 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 a projective 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 ProjectiveTransformation2D 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<ProjectiveTransformation2D>() {
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 ProjectiveTransformation2DRobustEstimator.MINIMUM_SIZE;
299 }
300
301 @Override
302 public void estimatePreliminarSolutions(
303 final int[] samplesIndices, final List<ProjectiveTransformation2D> 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 final var inputLine4 = inputLines.get(samplesIndices[3]);
308
309 final var outputLine1 = outputLines.get(samplesIndices[0]);
310 final var outputLine2 = outputLines.get(samplesIndices[1]);
311 final var outputLine3 = outputLines.get(samplesIndices[2]);
312 final var outputLine4 = outputLines.get(samplesIndices[3]);
313
314 try {
315 final var transformation = new ProjectiveTransformation2D(inputLine1, inputLine2,
316 inputLine3, inputLine4, outputLine1, outputLine2, outputLine3, outputLine4);
317 solutions.add(transformation);
318 } catch (final CoincidentLinesException e) {
319 // if lines are coincident, no solution is added
320 }
321 }
322
323 @Override
324 public double computeResidual(final ProjectiveTransformation2D currentEstimation, final int i) {
325 final var inputLine = inputLines.get(i);
326 final var outputLine = outputLines.get(i);
327
328 // transform input line and store result in mTestLine
329 try {
330 currentEstimation.transform(inputLine, testLine);
331
332 return getResidual(outputLine, testLine);
333 } catch (final AlgebraException e) {
334 // this happens when internal matrix of affine transformation
335 // cannot be reverse (i.e. transformation is not well-defined,
336 // numerical instabilities, etc.)
337 return Double.MAX_VALUE;
338 }
339 }
340
341 @Override
342 public boolean isReady() {
343 return RANSACLineCorrespondenceProjectiveTransformation2DRobustEstimator.this.isReady();
344 }
345
346 @Override
347 public void onEstimateStart(final RobustEstimator<ProjectiveTransformation2D> estimator) {
348 if (listener != null) {
349 listener.onEstimateStart(
350 RANSACLineCorrespondenceProjectiveTransformation2DRobustEstimator.this);
351 }
352 }
353
354 @Override
355 public void onEstimateEnd(final RobustEstimator<ProjectiveTransformation2D> estimator) {
356 if (listener != null) {
357 listener.onEstimateEnd(
358 RANSACLineCorrespondenceProjectiveTransformation2DRobustEstimator.this);
359 }
360 }
361
362 @Override
363 public void onEstimateNextIteration(
364 final RobustEstimator<ProjectiveTransformation2D> estimator, final int iteration) {
365 if (listener != null) {
366 listener.onEstimateNextIteration(
367 RANSACLineCorrespondenceProjectiveTransformation2DRobustEstimator.this,
368 iteration);
369 }
370 }
371
372 @Override
373 public void onEstimateProgressChange(
374 final RobustEstimator<ProjectiveTransformation2D> estimator, final float progress) {
375 if (listener != null) {
376 listener.onEstimateProgressChange(
377 RANSACLineCorrespondenceProjectiveTransformation2DRobustEstimator.this,
378 progress);
379 }
380 }
381 });
382
383 try {
384 locked = true;
385 inliersData = null;
386 innerEstimator.setComputeAndKeepInliersEnabled(computeAndKeepInliers || refineResult);
387 innerEstimator.setComputeAndKeepResidualsEnabled(computeAndKeepResiduals || refineResult);
388 innerEstimator.setConfidence(confidence);
389 innerEstimator.setMaxIterations(maxIterations);
390 innerEstimator.setProgressDelta(progressDelta);
391 final var transformation = innerEstimator.estimate();
392 inliersData = innerEstimator.getInliersData();
393 return attemptRefine(transformation);
394 } catch (final com.irurueta.numerical.LockedException e) {
395 throw new LockedException(e);
396 } catch (final com.irurueta.numerical.NotReadyException e) {
397 throw new NotReadyException(e);
398 } finally {
399 locked = false;
400 }
401 }
402
403 /**
404 * Returns method being used for robust estimation.
405 *
406 * @return method being used for robust estimation.
407 */
408 @Override
409 public RobustEstimatorMethod getMethod() {
410 return RobustEstimatorMethod.RANSAC;
411 }
412
413 /**
414 * Gets standard deviation used for Levenberg-Marquardt fitting during
415 * refinement.
416 * Returned value gives an indication of how much variance each residual
417 * has.
418 * Typically, this value is related to the threshold used on each robust
419 * estimation, since residuals of found inliers are within the range of
420 * such threshold.
421 *
422 * @return standard deviation used for refinement.
423 */
424 @Override
425 protected double getRefinementStandardDeviation() {
426 return threshold;
427 }
428 }