1 /*
2 * Copyright (C) 2016 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.numerical.polynomials.estimators;
17
18 import com.irurueta.numerical.LockedException;
19 import com.irurueta.numerical.NotReadyException;
20 import com.irurueta.numerical.polynomials.Polynomial;
21 import com.irurueta.numerical.robust.RANSACRobustEstimator;
22 import com.irurueta.numerical.robust.RANSACRobustEstimatorListener;
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.ArrayList;
28 import java.util.List;
29
30 /**
31 * Finds the best polynomial using RANSAC algorithm.
32 */
33 public class RANSACPolynomialRobustEstimator extends PolynomialRobustEstimator {
34
35 /**
36 * Constant defining default threshold to determine whether polynomials are
37 * inliers or not.
38 * Threshold will be used to compare either algebraic or geometric distance
39 * of estimated polynomial respect each provided evaluation.
40 */
41 public static final double DEFAULT_THRESHOLD = 1e-6;
42
43 /**
44 * Minimum value that can be set as threshold.
45 * Threshold must be strictly greater than 0.0.
46 */
47 public static final double MIN_THRESHOLD = 0.0;
48
49 /**
50 * Threshold to determine whether polynomial evaluations are inliers or not
51 * when testing possible estimation solutions
52 */
53 private double threshold;
54
55 /**
56 * Constructor.
57 */
58 public RANSACPolynomialRobustEstimator() {
59 super();
60 threshold = DEFAULT_THRESHOLD;
61 }
62
63 /**
64 * Constructor.
65 *
66 * @param degree degree of polynomial to be estimated.
67 * @throws IllegalArgumentException if provided degree is less than 1.
68 */
69 public RANSACPolynomialRobustEstimator(final int degree) {
70 super(degree);
71 threshold = DEFAULT_THRESHOLD;
72 }
73
74 /**
75 * Constructor.
76 *
77 * @param evaluations collection of polynomial evaluations.
78 * @throws IllegalArgumentException if provided number of evaluations is
79 * less than the required minimum.
80 */
81 public RANSACPolynomialRobustEstimator(final List<PolynomialEvaluation> evaluations) {
82 super(evaluations);
83 threshold = DEFAULT_THRESHOLD;
84 }
85
86 /**
87 * Constructor.
88 *
89 * @param listener listener to be notified of events such as when estimation
90 * starts, ends or its progress significantly changes.
91 */
92 public RANSACPolynomialRobustEstimator(final PolynomialRobustEstimatorListener listener) {
93 super(listener);
94 threshold = DEFAULT_THRESHOLD;
95 }
96
97 /**
98 * Constructor.
99 *
100 * @param degree degree of polynomial to be estimated.
101 * @param evaluations collection of polynomial evaluations.
102 * @throws IllegalArgumentException if provided degree is less than 1 or if
103 * provided number of evaluations is less than the required minimum for
104 * provided degree.
105 */
106 public RANSACPolynomialRobustEstimator(final int degree, final List<PolynomialEvaluation> evaluations) {
107 super(degree, evaluations);
108 threshold = DEFAULT_THRESHOLD;
109 }
110
111 /**
112 * Constructor.
113 *
114 * @param degree degree of polynomial to be estimated.
115 * @param listener listener to be notified of events such as when estimation
116 * starts, ends or its progress significantly changes.
117 * @throws IllegalArgumentException if provided degree is less than 1.
118 */
119 public RANSACPolynomialRobustEstimator(final int degree, final PolynomialRobustEstimatorListener listener) {
120 super(degree, listener);
121 threshold = DEFAULT_THRESHOLD;
122 }
123
124 /**
125 * Constructor.
126 *
127 * @param evaluations collection of polynomial evaluations.
128 * @param listener listener to be notified of events such as when estimation
129 * starts, ends or its progress significantly changes.
130 * @throws IllegalArgumentException if provided number of evaluations is
131 * less than the required minimum.
132 */
133 public RANSACPolynomialRobustEstimator(
134 final List<PolynomialEvaluation> evaluations, final PolynomialRobustEstimatorListener listener) {
135 super(evaluations, listener);
136 threshold = DEFAULT_THRESHOLD;
137 }
138
139 /**
140 * Constructor.
141 *
142 * @param degree degree of polynomial to be estimated.
143 * @param evaluations collection of polynomial evaluations.
144 * @param listener listener to be notified of events such as when estimation
145 * starts, ends or its progress significantly changes.
146 * @throws IllegalArgumentException if provided degree is less than 1 or if
147 * provided number of evaluations is less than the required minimum for
148 * provided degree.
149 */
150 public RANSACPolynomialRobustEstimator(
151 final int degree, final List<PolynomialEvaluation> evaluations,
152 final PolynomialRobustEstimatorListener listener) {
153 super(degree, evaluations, listener);
154 threshold = DEFAULT_THRESHOLD;
155 }
156
157 /**
158 * Returns threshold to determine whether polynomials are inliers or not
159 * when testing possible estimation solutions.
160 *
161 * @return threshold to determine whether polynomials are inliers or not
162 * when testing possible estimation solutions.
163 */
164 public double getThreshold() {
165 return threshold;
166 }
167
168 /**
169 * Sets threshold to determine whether polynomials are inliers or not when
170 * testing possible estimation solutions.
171 *
172 * @param threshold threshold to determine whether polynomials are inliers
173 * or not when testing possible estimation solutions.
174 * @throws IllegalArgumentException if provided value is equal or less than
175 * zero.
176 * @throws LockedException if robust estimator is locked.
177 */
178 public void setThreshold(final double threshold) throws LockedException {
179 if (isLocked()) {
180 throw new LockedException();
181 }
182 if (threshold <= MIN_THRESHOLD) {
183 throw new IllegalArgumentException();
184 }
185 this.threshold = threshold;
186 }
187
188
189 /**
190 * Estimates polynomial.
191 *
192 * @return estimated polynomial.
193 * @throws LockedException if robust estimator is locked because an
194 * estimation is already in progress.
195 * @throws NotReadyException if provided input data is not enough to start
196 * the estimation.
197 * @throws RobustEstimatorException if estimation fails for any other reason
198 * (i.e. numerical instability, no solution available, etc).
199 */
200 @Override
201 public Polynomial estimate() throws LockedException, NotReadyException, RobustEstimatorException {
202 if (isLocked()) {
203 throw new LockedException();
204 }
205 if (!isReady()) {
206 throw new NotReadyException();
207 }
208
209 final RANSACRobustEstimator<Polynomial> innerEstimator = new RANSACRobustEstimator<>(
210 new RANSACRobustEstimatorListener<>() {
211
212 // subset of evaluations picked on each iteration
213 private final List<PolynomialEvaluation> subsetEvaluations = new ArrayList<>();
214
215 @Override
216 public double getThreshold() {
217 return threshold;
218 }
219
220 @Override
221 public int getTotalSamples() {
222 return evaluations.size();
223 }
224
225 @Override
226 public int getSubsetSize() {
227 return polynomialEstimator.getMinNumberOfEvaluations();
228 }
229
230 @Override
231 public void estimatePreliminarSolutions(
232 final int[] samplesIndices, final List<Polynomial> solutions) {
233 subsetEvaluations.clear();
234 for (var samplesIndex : samplesIndices) {
235 subsetEvaluations.add(evaluations.get(samplesIndex));
236 }
237
238 try {
239 polynomialEstimator.setLMSESolutionAllowed(false);
240 polynomialEstimator.setEvaluations(subsetEvaluations);
241
242 final var polynomial = polynomialEstimator.estimate();
243 solutions.add(polynomial);
244 } catch (Exception e) {
245 // if anything fails, no solution is added
246 }
247 }
248
249 @Override
250 public double computeResidual(final Polynomial currentEstimation, final int i) {
251 final var eval = evaluations.get(i);
252 return getDistance(eval, currentEstimation);
253 }
254
255 @Override
256 public boolean isReady() {
257 return RANSACPolynomialRobustEstimator.this.isReady();
258 }
259
260 @Override
261 public void onEstimateStart(final RobustEstimator<Polynomial> estimator) {
262 if (listener != null) {
263 listener.onEstimateStart(RANSACPolynomialRobustEstimator.this);
264 }
265 }
266
267 @Override
268 public void onEstimateEnd(final RobustEstimator<Polynomial> estimator) {
269 if (listener != null) {
270 listener.onEstimateEnd(RANSACPolynomialRobustEstimator.this);
271 }
272 }
273
274 @Override
275 public void onEstimateNextIteration(
276 final RobustEstimator<Polynomial> estimator, final int iteration) {
277 if (listener != null) {
278 listener.onEstimateNextIteration(RANSACPolynomialRobustEstimator.this, iteration);
279 }
280 }
281
282 @Override
283 public void onEstimateProgressChange(
284 final RobustEstimator<Polynomial> estimator, final float progress) {
285 if (listener != null) {
286 listener.onEstimateProgressChange(RANSACPolynomialRobustEstimator.this, progress);
287 }
288 }
289 });
290
291 try {
292 locked = true;
293 innerEstimator.setConfidence(confidence);
294 innerEstimator.setMaxIterations(maxIterations);
295 innerEstimator.setProgressDelta(progressDelta);
296 return innerEstimator.estimate();
297 } finally {
298 locked = false;
299 }
300 }
301
302 /**
303 * Returns method being used for robust estimation.
304 *
305 * @return method being used for robust estimation.
306 */
307 @Override
308 public RobustEstimatorMethod getMethod() {
309 return RobustEstimatorMethod.RANSAC;
310 }
311 }