1 /*
2 * Copyright (C) 2017 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.*;
19 import com.irurueta.algebra.Utils;
20 import com.irurueta.geometry.*;
21
22 import java.util.ArrayList;
23 import java.util.List;
24
25 /**
26 * EPnP (Efficient Perspective-n-Point) implementation to estimate pinhole
27 * cameras from 2D/3D point correspondences.
28 * This class is an implementation following the one proposed by Vincent Lepetit
29 * on "EPnP: An Accurate O(n) Solution to the PnP Problem" with some minor
30 * changes and improvements.
31 * Paper and source code can be found at:
32 * <a href="http://cvlabwww.epfl.ch/~lepetit/papers/lepetit_ijcv08.pdf">
33 * http://cvlabwww.epfl.ch/~lepetit/papers/lepetit_ijcv08.pdf
34 * </a>
35 * <a href="http://cvlab.epfl.ch/EPnP/index.php">http://cvlab.epfl.ch/EPnP/index.php</a>
36 */
37 @SuppressWarnings("DuplicatedCode")
38 public class EPnPPointCorrespondencePinholeCameraEstimator extends PointCorrespondencePinholeCameraEstimator {
39
40 /**
41 * Indicates that by default planar configuration is checked to determine
42 * whether point correspondences are in such configuration and find a
43 * specific solution for such case.
44 */
45 public static final boolean DEFAULT_PLANAR_CONFIGURATION_ALLOWED = true;
46
47 /**
48 * Indicates that by default a dimension 2 null-space is allowed.
49 */
50 public static final boolean DEFAULT_NULLSPACE_DIMENSION2_ALLOWED = true;
51
52 /**
53 * Indicates that by default a dimension 3 null-space is allowed.
54 */
55 public static final boolean DEFAULT_NULLSPACE_DIMENSION3_ALLOWED = true;
56
57 /**
58 * Default threshold to determine whether 3D matched points are in a
59 * planar configuration.
60 * Points are considered to be laying in a plane when the smallest singular
61 * value of their covariance matrix has a value much smaller than the
62 * second smallest as many times as this value.
63 */
64 public static final double DEFAULT_PLANAR_THRESHOLD = 1e13;
65
66 /**
67 * Number of control points used in a general configuration.
68 */
69 private static final int GENERAL_NUM_CONTROL_POINTS = 4;
70
71 /**
72 * Number of control points used in a planar configuration.
73 */
74 private static final int PLANAR_NUM_CONTROL_POINTS = 3;
75
76 /**
77 * Indicates whether planar configuration is checked to determine whether
78 * point correspondences are in such configuration and find a specific
79 * solution for such case.
80 */
81 private boolean planarConfigurationAllowed = DEFAULT_PLANAR_CONFIGURATION_ALLOWED;
82
83 /**
84 * Indicates whether the case where a dimension 2 null-space is allowed.
85 * When allowed, additional constraints are taken into account to ensure
86 * equality of scales so that less point correspondences are required.
87 * Enabling this parameter is usually ok.
88 */
89 private boolean nullspaceDimension2Allowed = DEFAULT_NULLSPACE_DIMENSION2_ALLOWED;
90
91 /**
92 * Indicates whether the case where a dimension 3 null-space is allowed.
93 * When allowed, additional constraints are taken into account to ensure
94 * equality of scales so that less point correspondences are required.
95 * Enabling this parameter is usually ok although less precise than
96 * when a null-space of dimension 2 is used.
97 */
98 private boolean nullspaceDimension3Allowed = DEFAULT_NULLSPACE_DIMENSION3_ALLOWED;
99
100 /**
101 * Threshold to determine whether 3D matched points are in a planar
102 * configuration.
103 * Points are considered to be laying in a plane when the smallest singular
104 * value of their covariance matrix has a value much smaller than the
105 * largest one as many times as this value.
106 */
107 private double planarThreshold = DEFAULT_PLANAR_THRESHOLD;
108
109 /**
110 * Intrinsic parameters of camera to be estimated.
111 */
112 private PinholeCameraIntrinsicParameters intrinsic;
113
114 /**
115 * Indicates whether provided correspondences were found to be laying in a
116 * planar configuration during the estimation.
117 */
118 private boolean isPlanar;
119
120 /**
121 * Computed control points in world coordinates.
122 */
123 private List<Point3D> controlWorldPoints;
124
125 /**
126 * Contains barycentric coordinates to express 3D world point in terms of
127 * control points.
128 * For general configuration, each row contains 4 coordinates and alphas
129 * has size nx4, where n is the number of provided 3D world points.
130 * For planar configuration, each row contains 3 coordinates and alphas
131 * has size nx3, where n is the number of provided 3D world points.
132 * both reference frames are centered in the centroid, alphas can be used
133 * in both world and camera coordinates.
134 */
135 private Matrix alphas;
136
137 /**
138 * M matrix to find control points in camera coordinates.
139 * M has size 2*n x 12 (general configuration) or 2*n x 9
140 * (planar configuration), where n is the number of provided 2D observed
141 * points.
142 */
143 private Matrix m;
144
145 /**
146 * List containing columns of null-space of M. Linear combinations of these
147 * columns contain possible solutions for control points coordinates in
148 * camera reference (up to scale).
149 * First item of the list contains last column of v, which corresponds to
150 * the smallest singular value.
151 * Last item of the list contains (column - number of control points) column
152 * of v.
153 */
154 private List<double[]> nullspace;
155
156 /**
157 * Possible solutions for the estimation.
158 */
159 private List<Solution> solutions;
160
161 /**
162 * Constructor.
163 */
164 public EPnPPointCorrespondencePinholeCameraEstimator() {
165 super();
166 }
167
168 /**
169 * Constructor with listener.
170 *
171 * @param listener listener to be notified of events such as when estimation
172 * starts, ends or estimation progress changes.
173 */
174 public EPnPPointCorrespondencePinholeCameraEstimator(final PinholeCameraEstimatorListener listener) {
175 super(listener);
176 }
177
178 /**
179 * Constructor.
180 *
181 * @param points3D list of corresponding 3D points.
182 * @param points2D list of corresponding 2D points.
183 * @throws IllegalArgumentException if any of the lists are null.
184 * @throws WrongListSizesException if provided lists of points don't have
185 * the same size and enough points.
186 */
187 public EPnPPointCorrespondencePinholeCameraEstimator(
188 final List<Point3D> points3D, final List<Point2D> points2D) throws WrongListSizesException {
189 super();
190 internalSetListsEpnP(points3D, points2D);
191 }
192
193 /**
194 * Constructor.
195 *
196 * @param points3D list of corresponding 3D points.
197 * @param points2D list of corresponding 2D points.
198 * @param listener listener to be notified of events such as when estimation
199 * starts, ends or estimation progress changes.
200 * @throws IllegalArgumentException if any of the lists are null.
201 * @throws WrongListSizesException if provided lists of points don't have
202 * the same size and enough points.
203 */
204 public EPnPPointCorrespondencePinholeCameraEstimator(
205 final List<Point3D> points3D, final List<Point2D> points2D, final PinholeCameraEstimatorListener listener)
206 throws WrongListSizesException {
207 super(listener);
208 internalSetListsEpnP(points3D, points2D);
209 }
210
211 /**
212 * Constructor.
213 *
214 * @param intrinsic intrinsic parameters of camera to be estimated.
215 */
216 public EPnPPointCorrespondencePinholeCameraEstimator(final PinholeCameraIntrinsicParameters intrinsic) {
217 this();
218 this.intrinsic = intrinsic;
219 }
220
221 /**
222 * Constructor with listener.
223 *
224 * @param intrinsic intrinsic parameters of camera to be estimated.
225 * @param listener listener to be notified of events such as when estimation
226 * starts, ends or estimation progress changes.
227 * @throws IllegalArgumentException if absolute values of focal lengths are
228 * too small.
229 */
230 public EPnPPointCorrespondencePinholeCameraEstimator(
231 final PinholeCameraIntrinsicParameters intrinsic, final PinholeCameraEstimatorListener listener) {
232 this(listener);
233 this.intrinsic = intrinsic;
234 }
235
236 /**
237 * Constructor.
238 *
239 * @param intrinsic intrinsic parameters of camera to be estimated.
240 * @param points3D list of corresponding 3D points.
241 * @param points2D list of corresponding 2D points.
242 * @throws IllegalArgumentException if any of the lists are null or if
243 * absolute values of focal lengths are too small.
244 * @throws WrongListSizesException if provided lists of points don't have
245 * the same size and enough points.
246 */
247 public EPnPPointCorrespondencePinholeCameraEstimator(
248 final PinholeCameraIntrinsicParameters intrinsic, final List<Point3D> points3D,
249 final List<Point2D> points2D) throws WrongListSizesException {
250 this(points3D, points2D);
251 this.intrinsic = intrinsic;
252 }
253
254 /**
255 * Constructor.
256 *
257 * @param intrinsic intrinsic parameters of camera to be estimated.
258 * @param points3D list of corresponding 3D points.
259 * @param points2D list of corresponding 2D points.
260 * @param listener listener to be notified of events such as when estimation
261 * starts, ends or estimation progress changes.
262 * @throws IllegalArgumentException if any of the lists are null or if
263 * absolute values of focal lengths are too small.
264 * @throws WrongListSizesException if provided lists of points don't have
265 * the same size and enough points.
266 */
267 public EPnPPointCorrespondencePinholeCameraEstimator(
268 final PinholeCameraIntrinsicParameters intrinsic, final List<Point3D> points3D,
269 final List<Point2D> points2D, final PinholeCameraEstimatorListener listener)
270 throws WrongListSizesException {
271 this(points3D, points2D, listener);
272 this.intrinsic = intrinsic;
273 }
274
275 /**
276 * Sets list of corresponding points.
277 *
278 * @param points3D list of corresponding 3D points.
279 * @param points2D list of corresponding 2D points.
280 * @throws LockedException if estimator is locked.
281 * @throws IllegalArgumentException if any of the lists are null.
282 * @throws WrongListSizesException if provided lists of points don't have
283 * the same size and enough points.
284 */
285 @Override
286 public void setLists(final List<Point3D> points3D, final List<Point2D> points2D) throws LockedException,
287 WrongListSizesException {
288 if (isLocked()) {
289 throw new LockedException();
290 }
291
292 internalSetListsEpnP(points3D, points2D);
293 }
294
295 /**
296 * Indicates whether planar configuration is checked to determine whether
297 * point correspondences are in such configuration and find a specific
298 * solution for such case.
299 *
300 * @return true to allow specific solutions for planar configurations,
301 * false to always find a solution assuming the general case.
302 */
303 public boolean isPlanarConfigurationAllowed() {
304 return planarConfigurationAllowed;
305 }
306
307 /**
308 * Specifies whether planar configuration is checked to determine whether
309 * point correspondences are in such configuration and find a specific
310 * solution for such case.
311 *
312 * @param planarConfigurationAllowed true to allow specific solutions for
313 * planar configurations, false to always find a solution assuming the
314 * general case.
315 * @throws LockedException if estimator is locked.
316 */
317 public void setPlanarConfigurationAllowed(final boolean planarConfigurationAllowed) throws LockedException {
318 if (isLocked()) {
319 throw new LockedException();
320 }
321 this.planarConfigurationAllowed = planarConfigurationAllowed;
322 }
323
324 /**
325 * Indicates whether the case where a dimension 2 null-space is allowed.
326 * When allowed, additional constraints are taken into account to ensure
327 * equality of scales so that less point correspondences are required.
328 * Enabling this parameter is usually ok.
329 *
330 * @return true to allow 2-dimensional null-space, false otherwise.
331 */
332 public boolean isNullspaceDimension2Allowed() {
333 return nullspaceDimension2Allowed;
334 }
335
336 /**
337 * Specifies whether the case where a dimension 2 null-space is allowed.
338 * When allowed, additional constraints are taken into account to ensure
339 * equality of scales so that less point correspondences are required.
340 * Enabling this parameter is usually ok.
341 *
342 * @param nullspaceDimension2Allowed true to allow 2-dimensional null-space,
343 * false otherwise.
344 * @throws LockedException if estimator is locked.
345 */
346 public void setNullspaceDimension2Allowed(final boolean nullspaceDimension2Allowed) throws LockedException {
347 if (isLocked()) {
348 throw new LockedException();
349 }
350 this.nullspaceDimension2Allowed = nullspaceDimension2Allowed;
351 }
352
353 /**
354 * Indicates whether the case where a dimension 3 null-space is allowed.
355 * When allowed, additional constraints are taken into account to ensure
356 * equality of scales so that less point correspondences are required.
357 * Enabling this parameter is usually ok although less precise than
358 * when a null-space of dimension 2 is used.
359 *
360 * @return true to allow 3-dimensional null-space, false otherwise.
361 */
362 public boolean isNullspaceDimension3Allowed() {
363 return nullspaceDimension3Allowed;
364 }
365
366 /**
367 * Specifies whether the case where a dimension 3 null-space is allowed.
368 * When allowed, additional constraints are taken into account to ensure
369 * equality of scales so that less point correspondences are required.
370 * Enabling this parameter is usually ok although less precise than
371 * when a null-space of dimension 2 is used.
372 *
373 * @param nullspaceDimension3Allowed true to allow 3-dimensional null-space,
374 * false otherwise.
375 * @throws LockedException if estimator is locked.
376 */
377 public void setNullspaceDimension3Allowed(final boolean nullspaceDimension3Allowed) throws LockedException {
378 if (isLocked()) {
379 throw new LockedException();
380 }
381 this.nullspaceDimension3Allowed = nullspaceDimension3Allowed;
382 }
383
384 /**
385 * Gets threshold to determine whether 3D matched points are in a planar
386 * configuration.
387 * Points are considered to be laying in a plane when the smallest singular
388 * value of their covariance matrix has a value much smaller than the
389 * largest one as many times as this value.
390 *
391 * @return threshold to determine whether 3D matched points are in a planar
392 * configuration.
393 */
394 public double getPlanarThreshold() {
395 return planarThreshold;
396 }
397
398 /**
399 * Sets threshold to determine whether 3D matched points are in a planar
400 * configuration.
401 * Points are considered to be laying in a plane when the smallest singular
402 * value of their covariance matrix has a value much smaller than the
403 * largest one as many times as this value.
404 *
405 * @param planarThreshold threshold to determine whether 3D matched points
406 * are in a planar configuration.
407 * @throws IllegalArgumentException if provided threshold is negative.
408 * @throws LockedException if estimator is locked.
409 */
410 public void setPlanarThreshold(final double planarThreshold) throws LockedException {
411 if (isLocked()) {
412 throw new LockedException();
413 }
414 if (planarThreshold < 0.0) {
415 throw new IllegalArgumentException();
416 }
417 this.planarThreshold = planarThreshold;
418 }
419
420 /**
421 * Gets intrinsic parameters of camera to be estimated.
422 *
423 * @return intrinsic parameters of camera to be estimated.
424 */
425 public PinholeCameraIntrinsicParameters getIntrinsic() {
426 return intrinsic;
427 }
428
429 /**
430 * Sets intrinsic parameters of camera to be estimated.
431 *
432 * @param intrinsic intrinsic parameters of camera to be estimated.
433 * @throws LockedException if estimator is locked.
434 */
435 public void setIntrinsic(final PinholeCameraIntrinsicParameters intrinsic) throws LockedException {
436 if (isLocked()) {
437 throw new LockedException();
438 }
439 this.intrinsic = intrinsic;
440 }
441
442 /**
443 * Indicates if this estimator is ready to start the estimation.
444 *
445 * @return true if estimator is ready, false otherwise.
446 */
447 @Override
448 public boolean isReady() {
449 return areListsAvailable() && areValidLists(points3D, points2D) && intrinsic != null;
450 }
451
452 /**
453 * Returns type of pinhole camera estimator.
454 *
455 * @return type of pinhole camera estimator.
456 */
457 @Override
458 public PinholeCameraEstimatorType getType() {
459 return PinholeCameraEstimatorType.EPNP_PINHOLE_CAMERA_ESTIMATOR;
460 }
461
462 /**
463 * Indicates if provided point correspondences are normalized to increase
464 * the accuracy of the estimation.
465 *
466 * @return true if input point correspondences will be normalized, false
467 * otherwise.
468 */
469 @Override
470 public boolean arePointCorrespondencesNormalized() {
471 return false;
472 }
473
474 /**
475 * Specifies whether provided point correspondences are normalized to
476 * increase the accuracy of the estimation.
477 *
478 * @param normalize true if input point correspondences will be normalized,
479 * false otherwise.
480 * @throws LockedException if estimator is locked.
481 */
482 @Override
483 public void setPointCorrespondencesNormalized(final boolean normalize) throws LockedException {
484 if (isLocked()) {
485 throw new LockedException();
486 }
487 }
488
489 /**
490 * Estimates a pinhole camera.
491 *
492 * @return estimated pinhole camera.
493 * @throws LockedException if estimator is locked.
494 * @throws NotReadyException if input has not yet been provided.
495 * @throws PinholeCameraEstimatorException if an error occurs during
496 * estimation, usually because input data is not valid.
497 */
498 @Override
499 public PinholeCamera estimate() throws LockedException, NotReadyException, PinholeCameraEstimatorException {
500 if (isLocked()) {
501 throw new LockedException();
502 }
503 if (!isReady()) {
504 throw new NotReadyException();
505 }
506
507 try {
508 locked = true;
509 if (listener != null) {
510 listener.onEstimateStart(this);
511 }
512
513 computeWorldControlPointsAndPointConfiguration();
514 computeBarycentricCoordinates();
515 buildM();
516 solveNullspace();
517 } catch (final AlgebraException e) {
518 locked = false;
519 throw new PinholeCameraEstimatorException(e);
520 }
521
522
523 solutions = new ArrayList<>();
524
525 // general case
526 try {
527 generalSolution1();
528 } catch (final GeometryException ignore) {
529 // continue attempting 2nd solution if 1st one fails
530 }
531 if (nullspaceDimension2Allowed) {
532 try {
533 generalSolution2();
534 } catch (final GeometryException | AlgebraException ignore) {
535 // continue attempting 3rd solution if 2nd one fails
536 }
537 }
538 if (nullspaceDimension3Allowed && !isPlanar) {
539 try {
540 generalSolution3();
541 } catch (final GeometryException | AlgebraException ignore) {
542 // 3rd solution could not be found
543 }
544 }
545
546 // pick best solution
547 final var bestSolution = pickBestSolution();
548
549 if (listener != null) {
550 listener.onEstimateEnd(this);
551 }
552
553 if (bestSolution == null) {
554 throw new PinholeCameraEstimatorException();
555 }
556 locked = false;
557 return attemptRefine(bestSolution.camera);
558 }
559
560
561 /**
562 * Indicates whether provided correspondences were found to be laying in a
563 * planar configuration during the estimation.
564 *
565 * @return true if point correspondences are in a planar configuration,
566 * false otherwise.
567 */
568 public boolean isPlanar() {
569 return isPlanar;
570 }
571
572 /**
573 * Internal method that actually computes the normalized pinhole camera
574 * internal matrix.
575 * This implementation makes no action.
576 *
577 * @param points3D list of 3D points. Points might or might not be
578 * normalized.
579 * @param points2D list of 2D points. Points might or might not be
580 * normalized.
581 * @return matrix of estimated pinhole camera.
582 */
583 @Override
584 protected Matrix internalEstimate(final List<Point3D> points3D, final List<Point2D> points2D) {
585 return null;
586 }
587
588 /**
589 * Internal method to set list of corresponding points (it does not check
590 * if estimator is locked).
591 *
592 * @param points3D list of corresponding 3D points.
593 * @param points2D list of corresponding 2D points.
594 * @throws IllegalArgumentException if any of the lists are null
595 * @throws WrongListSizesException if provided lists of points don't have
596 * the same size and enough points.
597 */
598 private void internalSetListsEpnP(final List<Point3D> points3D, final List<Point2D> points2D)
599 throws WrongListSizesException {
600
601 if (points3D == null || points2D == null) {
602 throw new IllegalArgumentException();
603 }
604
605 if (!areValidLists(points3D, points2D)) {
606 throw new WrongListSizesException();
607 }
608
609 this.points3D = points3D;
610 this.points2D = points2D;
611 }
612
613 /**
614 * Picks best solution (the one having the smallest re-projection error).
615 *
616 * @return best solution.
617 */
618 private Solution pickBestSolution() {
619 Solution bestSolution = null;
620 var bestError = Double.MAX_VALUE;
621 for (final var s : solutions) {
622 if (s.reprojectionError < bestError) {
623 bestError = s.reprojectionError;
624 bestSolution = s;
625 }
626 }
627
628 return bestSolution;
629 }
630
631 /**
632 * Tests solution 3 for general point configuration.
633 * Because solution is up to scale, 8 different solutions for different
634 * beta1, beta2 and beta3 signs are tried.
635 *
636 * @throws AlgebraException if a numerical degeneracy occurs.
637 * @throws LockedException never happens.
638 * @throws NotReadyException never happens.
639 * @throws CoincidentPointsException if a point degeneracy has occurred.
640 */
641 private void generalSolution3() throws AlgebraException, LockedException, NotReadyException,
642 CoincidentPointsException {
643 if (isPlanar) {
644 return;
645 }
646
647 // we have the distance constraints between control world points (c) and
648 // control camera points (v):
649 // ||(beta1*vai + beta2*vbi + beta3*vci) - (beta1*vaj + beta2*vbj + beta3*vcj)||^2 = ||ci - cj||^2, i,j 1...4
650
651 // ((beta1*vaix + beta2*vbix + beta3*vcix) - (beta1*vajx + beta2*vbjx + beta3*vcjx))^2 +
652 // ((beta1*vaiy + beta2*vbiy + beta3*vciy) - (beta1*vajy + beta2*vbjy + beta3*vcjy))^2 +
653 // ((beta1*vaiz + beta2*vbiz + beta3*vciz) - (beta1*vajz + beta2*vbjz + beta3*vcjz))^2 =
654 // (cix - cjx)^2 + (ciy - cjy)^2 + (ciz - cjz)^2, i,j 1...4
655
656 // (beta1*(vaix - vajx) + beta2*(vbix - vbjx) + beta3*(vcix - vcjx))^2 +
657 // (beta1*(vaiy - vajy) + beta2*(vbiy - vbjy) + beta3*(vciy - vcjy))^2 +
658 // (beta1*(vaiz - vajz) + beta2*(vbiz - vbjz) + beta3*(vciz - vcjz))^2 =
659 // (cix - cjx)^2 + (ciy - cjy)^2 + (ciz - cjz)^2, i,j 1...4
660
661 // beta1^2*(vaix - vajx)^2 + 2*beta1*(vaix - vajx)*(beta2*(vbix - vbjx) + beta3*(vcix - vcjx)) + (beta2*(vbix - vbjx) + beta3*(vcix - vcjx))^2 +
662 // beta1^2*(vaiy - vajy)^2 + 2*beta1*(vaiy - vajy)*(beta2*(vbiy - vbjy) + beta3*(vciy - vcjy)) + (beta2*(vbiy - vbjy) + beta3*(vciy - vcjy))^2 +
663 // beta1^2*(vaiz - vajz)^2 + 2*beta1*(vaiz - vajz)*(beta2*(vbiz - vbjz) + beta3*(vciz - vcjz)) + (beta2*(vbiz - vbjz) + beta3*(vciz - vcjz))^2 =
664 // (cix - cjx)^2 + (ciy - cjy)^2 + (ciz - cjz)^2, i,j 1...4
665
666 // beta1^2*(vaix - vajx)^2 + beta1*beta2*2*(vaix - vajx)*(vbix - vbjx) + beta1*beta3*2*(vaix - vajx)*(vcix - vcjx) + beta2^2*(vbix - vbjx)^2 + beta2*beta3*2*(vbix - vbjx)*(vcix - vcjx) + beta3^2*(vcix - vcjx)^2 +
667 // beta1^2*(vaiy - vajy)^2 + beta1*beta2*2*(vaiy - vajy)*(vbiy - vbjy) + beta1*beta3*2*(vaiy - vajy)*(vciy - vcjy) + beta2^2*(vbiy - vbjy)^2 + beta2*beta3*2*(vbiy - vbjy)*(vciy - vcjy) + beta3^2*(vciy - vcjy)^2 +
668 // beta1^2*(vaiz - vajz)^2 + beta1*beta2*2*(vaiz - vajz)*(vbiz - vbjz) + beta1*beta3*2*(vaiz - vajz)*(vciz - vcjz) + beta2^2*(vbiz - vbjz)^2 + beta2*beta3*2*(vbiz - vbjz)*(vciz - vcjz) + beta3^2*(vciz - vcjz)^2 =
669 // (cix - cjx)^2 + (ciy - cjy)^2 + (ciz - cjz)^2, i,j 1...4
670
671 // We linearize the equation assuming:
672 // alpha1 = beta1^2
673 // alpha2 = beta1*beta2
674 // alpha3 = beta1*beta3
675 // alpha4 = beta2^2
676 // alpha5 = beta2*beta3
677 // alpha6 = beta3^2
678
679 // alpha1*(vaix - vajx)^2 + alpha2*2*(vaix - vajx)*(vbix - vbjx) + alpha3*2*(vaix - vajx)*(vcix - vcjx) + alpha4*(vbix - vbjx)^2 + alpha5*2*(vbix - vbjx)*(vcix - vcjx) + alpha6*(vcix - vcjx)^2 +
680 // alpha1*(vaiy - vajy)^2 + alpha2*2*(vaiy - vajy)*(vbiy - vbjy) + alpha3*2*(vaiy - vajy)*(vciy - vcjy) + alpha4*(vbiy - vbjy)^2 + alpha5*2*(vbiy - vbjy)*(vciy - vcjy) + alpha6*(vciy - vcjy)^2 +
681 // alpha1*(vaiz - vajz)^2 + alpha2*2*(vaiz - vajz)*(vbiz - vbjz) + alpha3*2*(vaiz - vajz)*(vciz - vcjz) + alpha4*(vbiz - vbjz)^2 + alpha5*2*(vbiz - vbjz)*(vciz - vcjz) + alpha6*(vciz - vcjz)^2 =
682 // (cix - cjx)^2 + (ciy - cjy)^2 + (ciz - cjz)^2, i,j 1...4
683
684 // Reorder
685 // alpha1*((vaix - vajx)^2 + (vaiy - vajy)^2 + (vaiz - vajz)^2) +
686 // alpha2*2*((vaix - vajx)*(vbix - vbjx) + (vaiy - vajy)*(vbiy - vbjy) + (vaiz - vajz)*(vbiz - vbjz)) +
687 // alpha3*2*((vaix - vajx)*(vcix - vcjx) + (vaiy - vajy)*(vciy - vcjy) + (vaiz - vajz)*(vciz - vcjz)) +
688 // alpha4*((vbix - vbjx)^2 + (vbiy - vbjy)^2 + (vbiz - vbjz)^2) +
689 // alpha5*2*((vbix - vbjx)*(vcix - vcjx) + (vbiy - vbjy)*(vciy - vcjy) + (vbiz - vbjz)*(vciz - vcjz)) +
690 // alpha6*((vcix - vcjx)^2 + (vciy - vcjy)^2 + (vciz - vcjz)^2) =
691 // (cix - cjx)^2 + (ciy - cjy)^2 + (ciz - cjz)^2, i,j 1...4
692
693 // this also produces 6 equations as in case 2.
694
695 final var va = nullspace.get(0);
696 final var vb = nullspace.get(1);
697 final var vc = nullspace.get(2);
698
699 final var controlCameraPointsA = controlPointsFromV(va);
700 final var controlCameraPointsB = controlPointsFromV(vb);
701 final var controlCameraPointsC = controlPointsFromV(vc);
702
703 final var c = constraintMatrixSolution3(controlCameraPointsA, controlCameraPointsB, controlCameraPointsC);
704 final var rhos = rhos(controlWorldPoints);
705
706 final var a = Utils.solve(c, rhos);
707
708 double beta1;
709 double beta2;
710 double beta3;
711 if (a[0] < 0.0) {
712 beta1 = Math.sqrt(-a[0]);
713 beta2 = a[3] < 0.0 ? Math.sqrt(-a[3]) : 0.0;
714 } else {
715 beta1 = Math.sqrt(a[0]);
716 beta2 = a[3] > 0.0 ? Math.sqrt(a[3]) : 0.0;
717 }
718
719 // fix sign of betas
720 if (a[1] < 0.0) {
721 beta1 = -beta1;
722 }
723
724 beta3 = a[2] / beta1;
725
726 // We linearize the equation assuming:
727 // alpha1 = beta1^2
728 // alpha2 = beta1*beta2
729 // alpha3 = beta1*beta3
730 // alpha4 = beta2^2
731 // alpha5 = beta*beta3
732 // alpha6 = beta3^2
733
734 final var initialBeta1 = beta1;
735 final var initialBeta2 = beta2;
736 final var initialBeta3 = beta3;
737
738 // compute linear combination of va and vb as
739 // v = beta1*va + beta2*vb + beta3*vc
740 final var tmp1 = ArrayUtils.multiplyByScalarAndReturnNew(va, beta1);
741 final var tmp2 = ArrayUtils.multiplyByScalarAndReturnNew(vb, beta2);
742 final var tmp3 = ArrayUtils.multiplyByScalarAndReturnNew(vc, beta3);
743 ArrayUtils.sum(tmp1, tmp2, tmp1);
744 ArrayUtils.sum(tmp1, tmp3, tmp1);
745 var controlCameraPoints = controlPointsFromV(tmp1);
746
747 var solution = computePossibleSolutionWithPoseAndReprojectionError(controlCameraPoints);
748 solutions.add(solution);
749
750 // because solutions are square roots, beta1, beta2 and beta3 can have
751 // different signs, so we add solutions for each combination so that the
752 // one with the smallest re-projection error will be picked
753 beta1 = -initialBeta1;
754 // no need to set: beta2 = initialBeta2 and beta3 = initialBeta3 because they already have
755 // those values
756
757 ArrayUtils.multiplyByScalar(va, beta1, tmp1);
758 ArrayUtils.multiplyByScalar(vb, beta2, tmp2);
759 ArrayUtils.multiplyByScalar(vc, beta3, tmp3);
760 ArrayUtils.sum(tmp1, tmp2, tmp1);
761 ArrayUtils.sum(tmp1, tmp3, tmp1);
762 // no need to set v = tmp1, because it already has this value
763 controlCameraPoints = controlPointsFromV(tmp1);
764
765 solution = computePossibleSolutionWithPoseAndReprojectionError(controlCameraPoints);
766 solutions.add(solution);
767
768
769 beta1 = initialBeta1;
770 beta2 = -initialBeta2;
771 // no need to set: beta3 = initialBeta3 as it already has that value
772
773 ArrayUtils.multiplyByScalar(va, beta1, tmp1);
774 ArrayUtils.multiplyByScalar(vb, beta2, tmp2);
775 ArrayUtils.multiplyByScalar(vc, beta3, tmp3);
776 ArrayUtils.sum(tmp1, tmp2, tmp1);
777 ArrayUtils.sum(tmp1, tmp3, tmp1);
778 // no need to set v = tmp1, because it already has this value
779 controlCameraPoints = controlPointsFromV(tmp1);
780
781 solution = computePossibleSolutionWithPoseAndReprojectionError(controlCameraPoints);
782 solutions.add(solution);
783
784 beta1 = -initialBeta1;
785 beta2 = -initialBeta2;
786 // no need to set beta3 = initialBeta3, as it already has that value
787
788 ArrayUtils.multiplyByScalar(va, beta1, tmp1);
789 ArrayUtils.multiplyByScalar(vb, beta2, tmp2);
790 ArrayUtils.multiplyByScalar(vc, beta3, tmp3);
791 ArrayUtils.sum(tmp1, tmp2, tmp1);
792 ArrayUtils.sum(tmp1, tmp3, tmp1);
793 // no need to set v = tmp1, because it already has this value
794 controlCameraPoints = controlPointsFromV(tmp1);
795
796 solution = computePossibleSolutionWithPoseAndReprojectionError(controlCameraPoints);
797 solutions.add(solution);
798
799 beta1 = initialBeta1;
800 beta2 = initialBeta2;
801 beta3 = -initialBeta3;
802
803 ArrayUtils.multiplyByScalar(va, beta1, tmp1);
804 ArrayUtils.multiplyByScalar(vb, beta2, tmp2);
805 ArrayUtils.multiplyByScalar(vc, beta3, tmp3);
806 ArrayUtils.sum(tmp1, tmp2, tmp1);
807 ArrayUtils.sum(tmp1, tmp3, tmp1);
808 // no need to set v = tmp1, because it already has this value
809 controlCameraPoints = controlPointsFromV(tmp1);
810
811 solution = computePossibleSolutionWithPoseAndReprojectionError(controlCameraPoints);
812 solutions.add(solution);
813
814 beta1 = -initialBeta1;
815 // no need to set beta2 = initialBeta2, because it already has this value
816 beta3 = -initialBeta3;
817
818 ArrayUtils.multiplyByScalar(va, beta1, tmp1);
819 ArrayUtils.multiplyByScalar(vb, beta2, tmp2);
820 ArrayUtils.multiplyByScalar(vc, beta3, tmp3);
821 ArrayUtils.sum(tmp1, tmp2, tmp1);
822 ArrayUtils.sum(tmp1, tmp3, tmp1);
823 // no need to set v = tmp1, because it already has this value
824 controlCameraPoints = controlPointsFromV(tmp1);
825
826 solution = computePossibleSolutionWithPoseAndReprojectionError(controlCameraPoints);
827 solutions.add(solution);
828
829 beta1 = initialBeta1;
830 beta2 = -initialBeta2;
831 beta3 = -initialBeta3;
832
833 ArrayUtils.multiplyByScalar(va, beta1, tmp1);
834 ArrayUtils.multiplyByScalar(vb, beta2, tmp2);
835 ArrayUtils.multiplyByScalar(vc, beta3, tmp3);
836 ArrayUtils.sum(tmp1, tmp2, tmp1);
837 ArrayUtils.sum(tmp1, tmp3, tmp1);
838 // no need to set v = tmp1, because it already has this value
839 controlCameraPoints = controlPointsFromV(tmp1);
840
841 solution = computePossibleSolutionWithPoseAndReprojectionError(controlCameraPoints);
842 solutions.add(solution);
843
844 beta1 = -initialBeta1;
845 beta2 = -initialBeta2;
846 beta3 = -initialBeta3;
847
848 ArrayUtils.multiplyByScalar(va, beta1, tmp1);
849 ArrayUtils.multiplyByScalar(vb, beta2, tmp2);
850 ArrayUtils.multiplyByScalar(vc, beta3, tmp3);
851 ArrayUtils.sum(tmp1, tmp2, tmp1);
852 ArrayUtils.sum(tmp1, tmp3, tmp1);
853 // no need to set v = tmp1, because it already has this value
854 controlCameraPoints = controlPointsFromV(tmp1);
855
856 solution = computePossibleSolutionWithPoseAndReprojectionError(controlCameraPoints);
857 solutions.add(solution);
858 }
859
860 /**
861 * Tests solution 2 for general point configuration.
862 * Because solution is up to scale, 4 different solutions for different
863 * beta1 and beta2 signs are tried.
864 *
865 * @throws AlgebraException if a numerical degeneracy occurs.
866 * @throws LockedException never happens.
867 * @throws NotReadyException never happens.
868 * @throws CoincidentPointsException if a point degeneracy has occurred.
869 */
870 private void generalSolution2() throws AlgebraException, LockedException, NotReadyException,
871 CoincidentPointsException {
872 // we have the distance constraints between control world points (c) and
873 // control camera points (v):
874 // ||beta*vi - beta*vj||^2 = ||ci - cj||^2, i,j 1...4
875 // we need to find beta to scale control camera points
876 // in the case we pick 2 columns of the null-space v, then v is a linear
877 // combination v = beta1*vA + beta2*vB and previous equation becomes
878 // ||(beta1*vAi + beta2*vBi) - (beta1*vAj + beta2*vBj)||^2 = ||ci - cj||^2, i,j 1...4
879 // This equation can be expanded in x,y,z coordinates as follows:
880 // ((beta1*vAix + beta2*vBix) - (beta1*vAjx + beta2*vBjx))^2 + ((beta1*vAiy + beta2*vBiy) - (beta1*vAjy + beta2*vBjy))^2 + ((beta1*vAiz + beta2*vBiz) - (beta1*vAjz + beta2*vBjz))^2 = ((cix - cjx)^2 + (ciy - cjy)^2 + (ciz - cjz)^2), i,j 1...4
881 // (beta1*(vAix - vAjx) + beta2*(vBix - vBjx))^2 + (beta1*(vAiy - vAjy) + beta2*(vBiy - vBjy))^2 + (beta1*(vAiz - vAjz) + beta2*(vBiz - vBjz))^2 = ((cix - cjx)^2 + (ciy - cjy)^2 + (ciz - cjz)^2), i,j 1...4
882 // beta1^2*(vAix - vAjx)^2 + beta1*beta2*2*(vAix - vAjx)*(vBix - vBjx) + beta2^2*(vBix - vBjx)^2 + beta1^2*(vAiy - vAjy)^2 + beta1*beta2*2*(vAiy - vAjy)*(vBiy - vBjy) + beta2^2*(vBiy - vBjy)^2 + beta1^2*(vAiz - vAjz)^2 + beta1*beta2*2*(vAiz - vAjz)*(vBiz - vBjz) + beta2^2*(vBiz - vBjz)^2 = ((cix - cjx)^2 + (ciy - cjy)^2 + (ciz - cjz)^2), i,j 1...4
883
884 // Since beta1 and beta2 are the unknowns, we can reorganize equation as:
885 // beta1^2*((vAix - vAjx)^2 + (vAiy - vAjy)^2 + (vAiz - vAjz)^2) +
886 // beta1*beta2*2*((vAix - vAjx)*(vBix - vBjx) + (vAiy - vAjy)*(vBiy - vBjy) + (vAiz - vAjz)*(vBiz - vBjz)) +
887 // beta2^2*((vBix - vBjx)^2 + (vBiy - vBjy)^2 + (vBiz - vBjz)^2) =
888 // ((cix - cjx)^2 + (ciy - cjy)^2 + (ciz - cjz)^2), i,j 1...4
889
890 // We linearize the equation assuming:
891 // alpha1 = beta1^2
892 // alpha2 = beta1*beta2
893 // alpha3 = beta2^2
894
895 // alpha1*((vAix - vAjx)^2 + (vAiy - vAjy)^2 + (vAiz - vAjz)^2) + alpha2*2*((vAix - vAjx)*(vBix - vBjx) + (vAiy - vAjy)*(vBiy - vBjy) + (vAiz - vAjz)*(vBiz - vBjz)) + alpha3*((vBix - vBjx)^2 + (vBiy - vBjy)^2 + (vBiz - vBjz)^2) = ((cix - cjx)^2 + (ciy - cjy)^2 + (ciz - cjz)^2), i,j 1...4
896
897 // finally we evaluate the equation for all 6 possible combinations of
898 // i,j 1...4 when we have 4 control points
899 // Obtaining the following equations:
900 // alpha1*((vA1x - vA2x)^2 + (vA1y - vA2y)^2 + (vA1z - vA2z)^2) + alpha2*2*((vA1x - vA2x)*(vB1x - vB2x) + (vA1y - vA2y)*(vB1y - vB2y) + (vA1z - vA2z)*(vB1z - vB2z)) + alpha3*((vB1x - vB2x)^2 + (vB1y - vB2y)^2 + (vB1z - vB2z)^2) = ((cix - cjx)^2 + (ciy - cjy)^2 + (ciz - cjz)^2)
901 // alpha1*((vA1x - vA3x)^2 + (vA1y - vA3y)^2 + (vA1z - vA3z)^2) + alpha2*2*((vA1x - vA3x)*(vB1x - vB3x) + (vA1y - vA3y)*(vB1y - vB3y) + (vA1z - vA3z)*(vB1z - vB3z)) + alpha3*((vB1x - vB3x)^2 + (vB1y - vB3y)^2 + (vB1z - vB3z)^2) = ((cix - cjx)^2 + (ciy - cjy)^2 + (ciz - cjz)^2)
902 // alpha1*((vA1x - vA4x)^2 + (vA1y - vA4y)^2 + (vA1z - vA4z)^2) + alpha2*2*((vA1x - vA4x)*(vB1x - vB4x) + (vA1y - vA4y)*(vB1y - vB4y) + (vA1z - vA4z)*(vB1z - vB4z)) + alpha3*((vB1x - vB4x)^2 + (vB1y - vB4y)^2 + (vB1z - vB4z)^2) = ((cix - cjx)^2 + (ciy - cjy)^2 + (ciz - cjz)^2)
903 // alpha1*((vA2x - vA3x)^2 + (vA2y - vA3y)^2 + (vA2z - vA3z)^2) + alpha2*2*((vA2x - vA3x)*(vB2x - vB3x) + (vA2y - vA3y)*(vB2y - vB3y) + (vA2z - vA3z)*(vB2z - vB3z)) + alpha3*((vB2x - vB3x)^2 + (vB2y - vB3y)^2 + (vB2z - vB3z)^2) = ((cix - cjx)^2 + (ciy - cjy)^2 + (ciz - cjz)^2)
904 // alpha1*((vA2x - vA4x)^2 + (vA2y - vA4y)^2 + (vA2z - vA4z)^2) + alpha2*2*((vA2x - vA4x)*(vB2x - vB4x) + (vA2y - vA4y)*(vB2y - vB4y) + (vA2z - vA4z)*(vB2z - vB4z)) + alpha3*((vB2x - vB4x)^2 + (vB2y - vB4y)^2 + (vB2z - vB4z)^2) = ((cix - cjx)^2 + (ciy - cjy)^2 + (ciz - cjz)^2)
905 // alpha1*((vA3x - vA4x)^2 + (vA3y - vA4y)^2 + (vA3z - vA4z)^2) + alpha2*2*((vA3x - vA4x)*(vB3x - vB4x) + (vA3y - vA4y)*(vB3y - vB4y) + (vA3z - vA4z)*(vB3z - vB4z)) + alpha3*((vB3x - vB4x)^2 + (vB3y - vB4y)^2 + (vB3z - vB4z)^2) = ((cix - cjx)^2 + (ciy - cjy)^2 + (ciz - cjz)^2)
906
907 // where alpha1, alpha2 and alpha3 are the unknowns of linear system of
908 // equations whose matrix C has size 6,3 (as seen below), and the right
909 // terms of the equation can be built by calling method
910 // #rhos(List<Point3D>) in this class
911
912 final var va = nullspace.get(0);
913 final var vb = nullspace.get(1);
914
915 final var controlCameraPointsA = controlPointsFromV(va);
916 final var controlCameraPointsB = controlPointsFromV(vb);
917
918 final var c = constraintMatrixSolution2(controlCameraPointsA, controlCameraPointsB);
919 final var rhos = rhos(controlWorldPoints);
920
921 final var a = Utils.solve(c, rhos);
922
923 // obtained a values are related to betas with the following expressions
924 // due to linearization:
925 // alpha1 = beta1^2
926 // alpha2 = beta1*beta2
927 // alpha3 = beta2^2
928
929 double beta1;
930 double beta2;
931 if (a[0] < 0.0) {
932 beta1 = Math.sqrt(-a[0]);
933 beta2 = a[2] < 0.0 ? Math.sqrt(-a[2]) : 0.0;
934 } else {
935 beta1 = Math.sqrt(a[0]);
936 beta2 = a[2] > 0.0 ? Math.sqrt(a[2]) : 0.0;
937 }
938
939 // fix sign of betas
940 if (a[1] < 0.0) {
941 beta1 = -beta1;
942 }
943
944 final var initialBeta1 = beta1;
945 final var initialBeta2 = beta2;
946
947 // compute linear combination of va and vb as v = beta1*va + beta2*vb
948 final var tmp1 = ArrayUtils.multiplyByScalarAndReturnNew(va, beta1);
949 final var tmp2 = ArrayUtils.multiplyByScalarAndReturnNew(vb, beta2);
950 ArrayUtils.sum(tmp1, tmp2, tmp1);
951 var controlCameraPoints = controlPointsFromV(tmp1);
952
953 var solution = computePossibleSolutionWithPoseAndReprojectionError(controlCameraPoints);
954 solutions.add(solution);
955
956 // because solutions are square roots, beta1 and beta2 can have different
957 // signs, so we add solutions for each combination so that the one with
958 // the smallest re-projection error will be picked
959 beta1 = -initialBeta1;
960 beta2 = -initialBeta2;
961
962 ArrayUtils.multiplyByScalar(va, beta1, tmp1);
963 ArrayUtils.multiplyByScalar(vb, beta2, tmp2);
964 ArrayUtils.sum(tmp1, tmp2, tmp1);
965 // no need to set v = tmp1, as it already has this value
966 controlCameraPoints = controlPointsFromV(tmp1);
967
968 solution = computePossibleSolutionWithPoseAndReprojectionError(controlCameraPoints);
969 solutions.add(solution);
970
971 beta1 = initialBeta1;
972 beta2 = -initialBeta2;
973
974 ArrayUtils.multiplyByScalar(va, beta1, tmp1);
975 ArrayUtils.multiplyByScalar(vb, beta2, tmp2);
976 ArrayUtils.sum(tmp1, tmp2, tmp1);
977 // no need to set v = tmp1, as it already has this value
978 controlCameraPoints = controlPointsFromV(tmp1);
979
980 solution = computePossibleSolutionWithPoseAndReprojectionError(controlCameraPoints);
981 solutions.add(solution);
982
983 beta1 = -initialBeta1;
984 beta2 = initialBeta2;
985
986 ArrayUtils.multiplyByScalar(va, beta1, tmp1);
987 ArrayUtils.multiplyByScalar(vb, beta2, tmp2);
988 ArrayUtils.sum(tmp1, tmp2, tmp1);
989 // no need to set v = tmp1, as it already has this value
990 controlCameraPoints = controlPointsFromV(tmp1);
991
992 solution = computePossibleSolutionWithPoseAndReprojectionError(controlCameraPoints);
993 solutions.add(solution);
994 }
995
996 /**
997 * Fills constraint matrix to solve betas when using control points from the
998 * last 3 columns of v (the null-space).
999 * The solution will be the linear combination of control points from the
1000 * last 3 columns using estimated betas. This solution will be control
1001 * points in camera coordinates.
1002 *
1003 * @param controlCameraPointsA control points of last column of v.
1004 * @param controlCameraPointsB control points of second last column of v.
1005 * @param controlCameraPointsC control points of third last column of v.
1006 * @return constraint matrix to solve a linear system of equations.
1007 * @throws AlgebraException never happens.
1008 */
1009 private static Matrix constraintMatrixSolution3(
1010 final List<Point3D> controlCameraPointsA, final List<Point3D> controlCameraPointsB,
1011 final List<Point3D> controlCameraPointsC) throws AlgebraException {
1012
1013 final var numControl = controlCameraPointsA.size();
1014 final var numEquations = numEquations(numControl);
1015
1016 final var c = new Matrix(numEquations, 6);
1017 int row = 0;
1018 for (var i = 0; i < numControl; i++) {
1019 final var vai = controlCameraPointsA.get(i);
1020 final var vbi = controlCameraPointsB.get(i);
1021 final var vci = controlCameraPointsC.get(i);
1022
1023 for (var j = i + 1; j < numControl; j++) {
1024 final var vaj = controlCameraPointsA.get(j);
1025 final var vbj = controlCameraPointsB.get(j);
1026 final var vcj = controlCameraPointsC.get(j);
1027
1028 fillRowConstraintMatrixSolution3(row, c, vai, vaj, vbi, vbj, vci, vcj);
1029 row++;
1030 }
1031 }
1032
1033 return c;
1034 }
1035
1036 /**
1037 * Fills constraint matrix to solve betas when using control points from the
1038 * last 2 columns of v (the null-space).
1039 * The solution will be the linear combination of control points from the
1040 * last 2 columns using estimated betas. This solution will be control
1041 * points in camera coordinates.
1042 *
1043 * @param controlCameraPointsA control points of last column of v.
1044 * @param controlCameraPointsB control points of second last column of v.
1045 * @return constraint matrix to solve a linear system of equations.
1046 * @throws AlgebraException never happens.
1047 */
1048 private static Matrix constraintMatrixSolution2(
1049 final List<Point3D> controlCameraPointsA, final List<Point3D> controlCameraPointsB)
1050 throws AlgebraException {
1051
1052 final var numControl = controlCameraPointsA.size();
1053 final var numEquations = numEquations(numControl);
1054
1055 final var c = new Matrix(numEquations, 3);
1056 var row = 0;
1057 for (var i = 0; i < numControl; i++) {
1058 final var vai = controlCameraPointsA.get(i);
1059 final var vbi = controlCameraPointsB.get(i);
1060
1061 for (var j = i + 1; j < numControl; j++) {
1062 final var vaj = controlCameraPointsA.get(j);
1063 final var vbj = controlCameraPointsB.get(j);
1064
1065 fillRowConstraintMatrixSolution2(row, c, vai, vaj, vbi, vbj);
1066 row++;
1067 }
1068 }
1069
1070 return c;
1071 }
1072
1073 /**
1074 * Fills a row of constraint matrix for solution 3.
1075 *
1076 * @param row row to be filled.
1077 * @param c matrix to be filled.
1078 * @param vai i-th control point in camera coordinates of last column of v
1079 * (i.e. the null-space).
1080 * @param vaj j-th control point in camera coordinates of last column of v
1081 * (i.e. the null-space).
1082 * @param vbi i-th control point in camera coordinates of second last column
1083 * of v (i.e. the null-space).
1084 * @param vbj j-th control point in camera coordinates of second last column
1085 * of v (i.e. the null-space).
1086 * @param vci i-th control point in camera coordinates of third last column
1087 * of v (i.e. the null-space).
1088 * @param vcj j-th control point in camera coordinates of third last column
1089 * of v (i.e. the null-space).
1090 */
1091 private static void fillRowConstraintMatrixSolution3(
1092 final int row, final Matrix c, final Point3D vai, final Point3D vaj, final Point3D vbi, final Point3D vbj,
1093 final Point3D vci, final Point3D vcj) {
1094
1095 final var vaix = vai.getInhomX();
1096 final var vaiy = vai.getInhomY();
1097 final var vaiz = vai.getInhomZ();
1098
1099 final var vajx = vaj.getInhomX();
1100 final var vajy = vaj.getInhomY();
1101 final var vajz = vaj.getInhomZ();
1102
1103 final var vbix = vbi.getInhomX();
1104 final var vbiy = vbi.getInhomY();
1105 final var vbiz = vbi.getInhomZ();
1106
1107 final var vbjx = vbj.getInhomX();
1108 final var vbjy = vbj.getInhomY();
1109 final var vbjz = vbj.getInhomZ();
1110
1111 final var vcix = vci.getInhomX();
1112 final var vciy = vci.getInhomY();
1113 final var vciz = vci.getInhomZ();
1114
1115 final var vcjx = vcj.getInhomX();
1116 final var vcjy = vcj.getInhomY();
1117 final var vcjz = vcj.getInhomZ();
1118
1119 // 1st column
1120 c.setElementAt(row, 0, Math.pow(vaix - vajx, 2.0) + Math.pow(vaiy - vajy, 2.0)
1121 + Math.pow(vaiz - vajz, 2.0));
1122
1123 // 2nd column
1124 c.setElementAt(row, 1, 2.0 * ((vaix - vajx) * (vbix - vbjx) + (vaiy - vajy) * (vbiy - vbjy)
1125 + (vaiz - vajz) * (vbiz - vbjz)));
1126
1127 // 3rd column
1128 c.setElementAt(row, 2, 2.0 * ((vaix - vajx) * (vcix - vcjx) + (vaiy - vajy) * (vciy - vcjy)
1129 + (vaiz - vajz) * (vciz - vcjz)));
1130
1131 // 4th column
1132 c.setElementAt(row, 3, Math.pow(vbix - vbjx, 2.0) + Math.pow(vbiy - vbjy, 2.0)
1133 + Math.pow(vbiz - vbjz, 2.0));
1134
1135 // 5th column
1136 c.setElementAt(row, 4, 2.0 * ((vbix - vbjx) * (vcix - vcjx) + (vbiy - vbjy) * (vciy - vcjy)
1137 + (vbiz - vbjz) * (vciz - vcjz)));
1138
1139 // 6th column
1140 c.setElementAt(row, 5, Math.pow(vcix - vcjx, 2.0) + Math.pow(vciy - vcjy, 2.0)
1141 + Math.pow(vciz - vcjz, 2.0));
1142 }
1143
1144 /**
1145 * Fills a row of constraint matrix for solution 2.
1146 *
1147 * @param row row to be filled.
1148 * @param c matrix to be filled.
1149 * @param vai i-th control point in camera coordinates of last column of v
1150 * (i.e. the null-space).
1151 * @param vaj j-th control point in camera coordinates of last column of v
1152 * (i.e. the null-space).
1153 * @param vbi i-th control point in camera coordinates of second last column
1154 * of v (i.e. the null-space).
1155 * @param vbj j-th control point in camera coordinates of second last column
1156 * of v (i.e. the null-space).
1157 */
1158 private static void fillRowConstraintMatrixSolution2(
1159 final int row, final Matrix c, final Point3D vai, final Point3D vaj, final Point3D vbi, final Point3D vbj) {
1160
1161 final var vaix = vai.getInhomX();
1162 final var vaiy = vai.getInhomY();
1163 final var vaiz = vai.getInhomZ();
1164
1165 final var vajx = vaj.getInhomX();
1166 final var vajy = vaj.getInhomY();
1167 final var vajz = vaj.getInhomZ();
1168
1169 final var vbix = vbi.getInhomX();
1170 final var vbiy = vbi.getInhomY();
1171 final var vbiz = vbi.getInhomZ();
1172
1173 final var vbjx = vbj.getInhomX();
1174 final var vbjy = vbj.getInhomY();
1175 final var vbjz = vbj.getInhomZ();
1176
1177 // 1st column
1178 c.setElementAt(row, 0, Math.pow(vaix - vajx, 2.0) + Math.pow(vaiy - vajy, 2.0)
1179 + Math.pow(vaiz - vajz, 2.0));
1180
1181 // 2nd column
1182 c.setElementAt(row, 1, 2.0 * ((vaix - vajx) * (vbix - vbjx) + (vaiy - vajy) * (vbiy - vbjy)
1183 + (vaiz - vajz) * (vbiz - vbjz)));
1184
1185 // 3rd column
1186 c.setElementAt(row, 2, Math.pow(vbix - vbjx, 2.0) + Math.pow(vbiy - vbjy, 2.0)
1187 + Math.pow(vbiz - vbjz, 2.0));
1188 }
1189
1190 /**
1191 * Tests solution 1 for general point configuration.
1192 * Because solution is up to scale. Two possible solutions must be evaluated
1193 * (positive or negative scale). The one with the smallest re-projection
1194 * error will be picked.
1195 *
1196 * @throws LockedException never happens.
1197 * @throws NotReadyException never happens.
1198 * @throws CoincidentPointsException if a point degeneracy has occurred.
1199 */
1200 private void generalSolution1() throws LockedException, NotReadyException, CoincidentPointsException {
1201 // pick last column of null-space, contains control points in camera
1202 // coordinates up to scale (including sign change)
1203 var v = nullspace.get(0);
1204 var controlCameraPoints = controlPointsFromV(v);
1205
1206 // similarly to solution2 and solution3, we could find the scale by
1207 // imposing the restriction: ||beta*vi - beta*vj||^2 = ||ci - cj||^2, i,j 1...4
1208 // This results in a linear system of 6 equations (when we have 4 control
1209 // points)
1210 // The previous constraint can be expanded as follows:
1211 // (beta*vi - beta*vj)^2 = (ci - cj)^2
1212 // (beta*vix - beta*vjx)^2 + (beta*viy - beta*vjy)^2 + (beta*viz - beta*vjz)^2 = (cix - cjx)^2 + (ciy - cjy)^2 + (ciz - cjz)^2, i,j 1...4
1213 // beta^2*(vix - vjx)^2 + beta^2*(viy - vjy)^2 + beta^2*(viz - vjz)^2 = (cix - cjx)^2 + (ciy - cjy)^2 + (ciz - cjz)^2, i,j 1...4
1214 // beta^2*((vix - vjx)^2 + (viy - vjy)^2 + (viz - vjz)^2) = (cix - cjx)^2 + (ciy - cjy)^2 + (ciz - cjz)^2, i,j 1...4
1215 //
1216 // And the system is linearized by assuming
1217 // alpha = beta^2
1218 //
1219 // alpha * ((vix - vjx)^2 + (viy - vjy)^2 + (viz - vjz)^2) = (cix - cjx)^2 + (ciy - cjy)^2 + (ciz - cjz)^2, i,j 1...4
1220
1221 // However, in order to find a solution a MetricTransformation3D estimator
1222 // is used, which is capable to determine the scale relating input and
1223 // output points, and thus, solving the linear system of equations is not
1224 // required in this case.
1225 var solution = computePossibleSolutionWithPoseAndReprojectionError(controlCameraPoints);
1226 solutions.add(solution);
1227
1228 // because v is a solution up to scale, we provide a solution with
1229 // opposite sign
1230 v = ArrayUtils.multiplyByScalarAndReturnNew(v, -1.0);
1231 controlCameraPoints = controlPointsFromV(v);
1232
1233 solution = computePossibleSolutionWithPoseAndReprojectionError(controlCameraPoints);
1234 solutions.add(solution);
1235 }
1236
1237 /**
1238 * Computes a possible solution with camera, transformation, re-projection
1239 * error and control points in camera coordinates.
1240 *
1241 * @param controlCameraPoints control points in camera coordinates.
1242 * @return a possible solution.
1243 * @throws LockedException never happens.
1244 * @throws NotReadyException never happens.
1245 * @throws CoincidentPointsException if a point degeneracy has occurred.
1246 */
1247 private Solution computePossibleSolutionWithPoseAndReprojectionError(
1248 final List<Point3D> controlCameraPoints) throws LockedException, NotReadyException,
1249 CoincidentPointsException {
1250
1251 final var worldToCameraTransformation = worldToCameraTransformationMetric(controlCameraPoints);
1252
1253 final var rotation = worldToCameraTransformation.getRotation();
1254 final var t = worldToCameraTransformation.getTranslation();
1255 final var scale = worldToCameraTransformation.getScale();
1256
1257 // Camera center is C = -1/s*R'*t
1258 final var center = new InhomogeneousPoint3D(-t[0] / scale, -t[1] / scale, -t[2] / scale);
1259 final var invRotation = rotation.inverseRotationAndReturnNew();
1260 invRotation.rotate(center, center);
1261
1262 final var camera = new PinholeCamera(intrinsic, rotation, center);
1263
1264 final var solution = new Solution();
1265 solution.controlCameraPoints = controlCameraPoints;
1266 solution.worldToCameraTransformation = worldToCameraTransformation;
1267 solution.camera = camera;
1268
1269 // compute projection error
1270 solution.reprojectionError = reprojectionError(camera);
1271
1272 return solution;
1273 }
1274
1275 /**
1276 * Estimates world to camera transformation using estimated control points
1277 * in world and camera coordinates as a metric transformation.
1278 *
1279 * @param controlCameraPoints control points in camera coordinates.
1280 * @return metric transformation relating control points from world to
1281 * camera coordinates.
1282 * @throws LockedException never happens.
1283 * @throws NotReadyException never happens.
1284 * @throws CoincidentPointsException if a point degeneracy has occurred.
1285 */
1286 private MetricTransformation3D worldToCameraTransformationMetric(final List<Point3D> controlCameraPoints)
1287 throws LockedException, NotReadyException, CoincidentPointsException {
1288 final var estimator = new MetricTransformation3DEstimator(controlWorldPoints, controlCameraPoints, isPlanar);
1289 return estimator.estimate();
1290 }
1291
1292 /**
1293 * Number of equations required to solve constraints for case 1 to 4.
1294 *
1295 * @param numControl number of control points.
1296 * @return number of constraint equations.
1297 */
1298 private static int numEquations(final int numControl) {
1299 var numEquations = 0;
1300 for (var i = 1; i < numControl; i++) {
1301 numEquations += i;
1302 }
1303 return numEquations;
1304 }
1305
1306 /**
1307 * Right term of linearized system of equations to solve betas.
1308 *
1309 * @param controlWorldPoints control points in world coordinates.
1310 * @return right term.
1311 */
1312 private static double[] rhos(final List<Point3D> controlWorldPoints) {
1313 final var numControl = controlWorldPoints.size();
1314 final var numEquations = numEquations(numControl);
1315 final var rhos = new double[numEquations];
1316
1317 // squared distance from control world i to control world j
1318 double dcijSqr;
1319 var pos = 0;
1320 for (var i = 0; i < numControl; i++) {
1321 final var ci = controlWorldPoints.get(i);
1322
1323 for (var j = i + 1; j < numControl; j++) {
1324 final var cj = controlWorldPoints.get(j);
1325
1326 dcijSqr = Math.pow(ci.distanceTo(cj), 2.0);
1327 rhos[pos] = dcijSqr;
1328 pos++;
1329 }
1330 }
1331
1332 return rhos;
1333 }
1334
1335 /**
1336 * Total re-projection error for provided camera.
1337 *
1338 * @param camera camera to estimate re-projection error.
1339 * @return reprojection error.
1340 */
1341 private double reprojectionError(final PinholeCamera camera) {
1342 final var n = points2D.size();
1343
1344 Point3D point3D;
1345 final var projected = Point2D.create();
1346 Point2D point2D;
1347 var error = 0.0;
1348 for (var i = 0; i < n; i++) {
1349 point3D = points3D.get(i);
1350 point2D = points2D.get(i);
1351 camera.project(point3D, projected);
1352 error += projected.distanceTo(point2D);
1353 }
1354 return error;
1355 }
1356
1357 /**
1358 * Computes list of control points from provided array containing one column
1359 * of the null-space of M or a linear combination of columns of the
1360 * null-space.
1361 *
1362 * @param v one column of the null-space of M or a linear combination of
1363 * columns of the null-space.
1364 * @return control points.
1365 */
1366 private List<Point3D> controlPointsFromV(final double[] v) {
1367 final var numControl = controlWorldPoints.size();
1368 final var points = new ArrayList<Point3D>();
1369
1370 for (var j = 0; j < numControl; j++) {
1371 final var k = j * 3;
1372 final var p = new InhomogeneousPoint3D(v[k], v[k + 1], v[k + 2]);
1373 points.add(p);
1374 }
1375
1376 return points;
1377 }
1378
1379 /**
1380 * Solves null-space of matrix M containing possible solutions of camera
1381 * coordinates of control points.
1382 *
1383 * @throws AlgebraException if something fails due to numerical
1384 * instabilities.
1385 */
1386 private void solveNullspace() throws AlgebraException {
1387 final var rows = m.getRows();
1388 final var cols = m.getColumns();
1389 final var numControl = cols / Point3D.POINT3D_INHOMOGENEOUS_COORDINATES_LENGTH;
1390
1391 // normalize rows of m to increase numerical accuracy
1392 for (var i = 0; i < rows; i++) {
1393 normalizeRow(m, i);
1394 }
1395
1396 final var decomposer = new SingularValueDecomposer(m);
1397 decomposer.decompose();
1398
1399 // Singular values are always in descending order, hence null space is in
1400 // the last columns of v.
1401 // V is 12x12 (general configuration) or 9x9 (planar configuration).
1402 // Each column of v contains coordinates of control points in camera
1403 // coordinates.
1404 // A solution for the linear system M*x = 0 is obtained as a linear
1405 // combination of the columns of v forming the null-space.
1406 final var v = decomposer.getV();
1407
1408 // although nullity of M could be determined after SVD, it is assumed
1409 // instead that null-space could be located in any of the latter columns
1410 // of v up to the number of control points.
1411 // Hence, for general configuration we pick the last 4 columns of v and
1412 // for planar configuration we pick the last 3.
1413
1414 // extract null points from the null space
1415 nullspace = new ArrayList<>();
1416 final var colsMinusOne = cols - 1;
1417 for (var i = 0; i < numControl; i++) {
1418 final var column = colsMinusOne - i;
1419
1420 // each picked column of v contains a possible solution
1421 final var vCol = v.getSubmatrixAsArray(0, column, colsMinusOne, column);
1422 nullspace.add(vCol);
1423 }
1424 }
1425
1426 /**
1427 * Normalizes provided row of m.
1428 *
1429 * @param m matrix to be normalized.
1430 * @param row row to be normalized.
1431 */
1432 private static void normalizeRow(final Matrix m, final int row) {
1433 final var cols = m.getColumns();
1434
1435 var norm = 0.0;
1436 for (int i = 0; i < cols; i++) {
1437 norm += Math.pow(m.getElementAt(row, i), 2.0);
1438 }
1439 norm = Math.sqrt(norm);
1440
1441 for (var i = 0; i < cols; i++) {
1442 m.setElementAt(row, i, m.getElementAt(row, i) / norm);
1443 }
1444 }
1445
1446 /**
1447 * In order to find control points in camera coordinates, an homogeneous
1448 * linear system of equations must be solved having the form M*x = 0, where
1449 * x contains the coordinates of all control points in the form [x1, y1, z1,
1450 * x2, y2, z2, ... ].
1451 * For general configuration there are 4 control points, hence x has length
1452 * 12 (3 coordinates * 4 control points).
1453 * For a planar configuration there are 3 control points, hence x has length
1454 * 9 (3 coordinates * 3 control points).
1455 * This method builds M matrix required to solve such linear system of
1456 * equations, where M has size 2*n x 12 (general configuration) or 2*n x 9
1457 * (planar configuration), where n is the number of provided 2D observed
1458 * points.
1459 *
1460 * @throws AlgebraException if numerical instabilities occur.
1461 */
1462 private void buildM() throws AlgebraException {
1463 final var n = points2D.size();
1464 final var numControlPoints = alphas.getColumns();
1465
1466 m = new Matrix(2 * n, 3 * numControlPoints);
1467
1468 int row;
1469 int col;
1470 double alpha;
1471
1472 final var horizontalFocalLength = intrinsic.getHorizontalFocalLength();
1473 final var verticalFocalLength = intrinsic.getVerticalFocalLength();
1474 final var skewness = intrinsic.getSkewness();
1475 final var horizontalPrincipalPoint = intrinsic.getHorizontalPrincipalPoint();
1476 final var verticalPrincipalPoint = intrinsic.getVerticalPrincipalPoint();
1477
1478 Point2D p;
1479 double pX;
1480 double pY;
1481 for (var i = 0; i < n; i++) {
1482 p = points2D.get(i);
1483 pX = p.getInhomX();
1484 pY = p.getInhomY();
1485
1486 row = i * 2;
1487
1488 for (var j = 0; j < numControlPoints; j++) {
1489 col = j * 3;
1490
1491 alpha = alphas.getElementAt(i, j);
1492
1493 m.setElementAt(row, col, alpha * horizontalFocalLength);
1494 m.setElementAt(row, col + 1, alpha * skewness);
1495 m.setElementAt(row, col + 2, alpha * (horizontalPrincipalPoint - pX));
1496
1497 m.setElementAt(row + 1, col, 0.0);
1498 m.setElementAt(row + 1, col + 1, alpha * verticalFocalLength);
1499 m.setElementAt(row + 1, col + 2, alpha * (verticalPrincipalPoint - pY));
1500 }
1501 }
1502 }
1503
1504 /**
1505 * Computes the coordinates of each provided world point in terms of
1506 * estimated control points in world coordinates.
1507 * Such coordinates (i.e. barycentric coordinates) are stored in alphas
1508 * matrix, where each row contains the coordinates of each world point in
1509 * terms of control points.
1510 * For general configuration, each row contains 4 coordinates and alphas
1511 * has size nx4, where n is the number of provided 3D world points.
1512 * For planar configuration, each row contains 3 coordinates and alphas
1513 * has size nx3, where n is the number of provided 3D world points.
1514 * Because world and camera coordinates are related by a rotation (since
1515 * both reference frames are centered in the centroid), alphas can be used
1516 * in both world and camera coordinates.
1517 *
1518 * @throws AlgebraException if there are numerical instabilities.
1519 */
1520 private void computeBarycentricCoordinates() throws AlgebraException {
1521 // we need to express world points in terms of control points in world
1522 // coordinates
1523
1524 // In the general configuration case:
1525 // For a point p1 in world inhomogeneous coordinates
1526 // p1 = alpha1 + c1 + alpha2 * c2 + alpha3 * c3 + alpha4 * c4
1527 // where alpha1, alpha2, alpha3, alpha4 are scalars and
1528 // c1, c2, c3 are the control points in the principal axes and
1529 // centroid is the last control point c4, all 4 expressed in world
1530 // inhomogeneous coordinates as 3-column vectors.
1531
1532 // Assuming a matrix form:
1533 // [p1] = [c1 c2 c3 c4]*[alpha1]
1534 // [alpha2]
1535 // [alpha3]
1536 // [alpha4]
1537
1538 // or in simpler for p = C * alpha, where p is a 3-column vector, C is a
1539 // 3x4 matrix and alpha is a 4-1 vector.
1540 // This can be repeated for each i-th point so that:
1541 // pi = C * alphai --> alphai = inv(C)*pi
1542 // However, in this form C is not invertible because it is rank deficient
1543 // To avoid this deficiency we add the constraint that the sum of alphas
1544 // for a point must be 1, so we can use the reduced form:
1545 // [p1 - c4] = [(c1 - c4) (c2 - c4) (c3 - c4)]*[alpha1]
1546 // [alpha2]
1547 // [alpha3]
1548 // and set alpha4 = 1 - alpha1 - alpha2 - alpha3
1549
1550 // This way the equation still holds:
1551 // p1 - c4 = (c1 - c4) * alpha1 + (c2 - c4) * alpha2 + (c3 - c4) * alpha3 =
1552 // = c1 * alpha1 + c2 * alpha2 + c3 * alpha3 - c4 * (alpha1 + alpha2 + alpha3)
1553 // p1 = c1 * alpha1 + c2 * alpha2 * c3 * alpha3 + c4 * (1 - alpha1 - alpha2 - alpha3)
1554
1555 // This way, we create reduced matrix C as having 3 rows (one for each
1556 // inhomogeneous coordinate) and 3 columns in the general case.
1557
1558 // In the planar case we have only 3 control points, and the last one
1559 // (c3) is the centroid.
1560
1561 final var numControl = controlWorldPoints.size();
1562 final var numDimensions = numControl - 1;
1563 final var numControlMinusTwo = numControl - 2;
1564 final var c = new Matrix(Point3D.POINT3D_INHOMOGENEOUS_COORDINATES_LENGTH, numDimensions);
1565
1566 // the last control point is the centroid (or mean point)
1567 final var mean = controlWorldPoints.get(numDimensions);
1568 final var meanX = mean.getInhomX();
1569 final var meanY = mean.getInhomY();
1570 final var meanZ = mean.getInhomZ();
1571
1572 for (var i = 0; i < numDimensions; i++) {
1573 final var controlPoint = controlWorldPoints.get(i);
1574 c.setElementAt(0, i, controlPoint.getInhomX() - meanX);
1575 c.setElementAt(1, i, controlPoint.getInhomY() - meanY);
1576 c.setElementAt(2, i, controlPoint.getInhomZ() - meanZ);
1577 }
1578
1579 // to find reduced alphas, we need to inverse the reduced C matrix and
1580 // multiply it by [p - centroid], where centroid can be c4 or c3 in
1581 // planar case.
1582
1583 final var invC = Utils.inverse(c);
1584
1585 // x is p - centroid, where p is each 3D world point
1586 final var n = points3D.size();
1587 final var reducedPoint = new Matrix(Point3D.POINT3D_INHOMOGENEOUS_COORDINATES_LENGTH, 1);
1588 final var reducedAlpha = new Matrix(numDimensions, 1);
1589 double[] buffer;
1590 Point3D worldPoint;
1591 alphas = new Matrix(n, numControl);
1592 for (var i = 0; i < n; i++) {
1593 worldPoint = points3D.get(i);
1594 reducedPoint.setElementAtIndex(0, worldPoint.getInhomX() - meanX);
1595 reducedPoint.setElementAtIndex(1, worldPoint.getInhomY() - meanY);
1596 reducedPoint.setElementAtIndex(2, worldPoint.getInhomZ() - meanZ);
1597
1598 invC.multiply(reducedPoint, reducedAlpha);
1599 buffer = reducedAlpha.getBuffer();
1600
1601 // copy reducedAlpha into the former components of i-th row of alphas
1602 alphas.setSubmatrix(i, 0, i, numControlMinusTwo, buffer);
1603
1604 // The last component of each alpha for each point is computed so
1605 // that their sum is equal to one
1606 if (numControl == GENERAL_NUM_CONTROL_POINTS) {
1607 // general configuration
1608 alphas.setElementAt(i, numDimensions, 1.0 - buffer[0] - buffer[1] - buffer[2]);
1609 } else {
1610 // planar configuration
1611 alphas.setElementAt(i, numDimensions, 1.0 - buffer[0] - buffer[1]);
1612 }
1613 }
1614 }
1615
1616
1617 /**
1618 * Computes control points in world coordinates and determines whether
1619 * they are located in a planar configuration or not.
1620 * This method computes the centroid of provided 3D points and their
1621 * covariance.
1622 * Uses PCA by means of SVD decomposition of their covariance matrix in
1623 * order to find the principal directions of the cloud formed by the
1624 * collection of points and sets control points as the computed centroid
1625 * and points along the principal axes so that they form a basis that
1626 * can be used to express any 3D points into.
1627 * If the smallest singular value is close to zero in comparison to the
1628 * largest one, then it is assumed that 3D points are in a planar
1629 * configuration.
1630 * If a planar configuration is allowed, then only 3 control points are
1631 * computed along the plane using the centroid and two points on the
1632 * principal directions of such plane.
1633 * Otherwise, in general configuration, 4 control points are computed as
1634 * the centroid and 3 points along the principal axes of the cloud of 3D
1635 * points.
1636 *
1637 * @throws AlgebraException if something fails because of numerical
1638 * instabilities.
1639 */
1640 private void computeWorldControlPointsAndPointConfiguration() throws AlgebraException {
1641 final var centroid = Point3D.centroid(points3D);
1642
1643 // covariance matrix elements, summed up here for speed
1644 var c11 = 0.0;
1645 var c12 = 0.0;
1646 var c13 = 0.0;
1647 var c22 = 0.0;
1648 var c23 = 0.0;
1649 var c33 = 0.0;
1650 double dx;
1651 double dy;
1652 double dz;
1653 final var n = points3D.size();
1654 for (final var point : points3D) {
1655 dx = point.getInhomX() - centroid.getInhomX();
1656 dy = point.getInhomY() - centroid.getInhomY();
1657 dz = point.getInhomZ() - centroid.getInhomZ();
1658
1659 c11 += dx * dx;
1660 c12 += dx * dy;
1661 c13 += dx * dz;
1662
1663 c22 += dy * dy;
1664 c23 += dy * dz;
1665
1666 c33 += dz * dz;
1667 }
1668 c11 /= n;
1669 c12 /= n;
1670 c13 /= n;
1671 c22 /= n;
1672 c23 /= n;
1673 c33 /= n;
1674
1675 final var covar = new Matrix(3, 3);
1676 covar.setElementAt(0, 0, c11);
1677 covar.setElementAt(1, 0, c12);
1678 covar.setElementAt(2, 0, c13);
1679
1680 covar.setElementAt(0, 1, c12);
1681 covar.setElementAt(1, 1, c22);
1682 covar.setElementAt(2, 1, c23);
1683
1684 covar.setElementAt(0, 2, c13);
1685 covar.setElementAt(1, 2, c23);
1686 covar.setElementAt(2, 2, c33);
1687
1688 final var decomposer = new SingularValueDecomposer(covar);
1689 decomposer.decompose();
1690
1691 final var singularValues = decomposer.getSingularValues();
1692 final var v = decomposer.getV();
1693
1694 // planar check
1695 int numControl;
1696 if (!planarConfigurationAllowed
1697 || Math.abs(singularValues[0]) < Math.abs(singularValues[2]) * planarThreshold) {
1698 // general configuration
1699 numControl = GENERAL_NUM_CONTROL_POINTS;
1700 isPlanar = false;
1701 } else {
1702 // planar configuration (only if allowed)
1703 numControl = PLANAR_NUM_CONTROL_POINTS;
1704 isPlanar = true;
1705 }
1706
1707 controlWorldPoints = new ArrayList<>();
1708
1709 final var centroidX = centroid.getInhomX();
1710 final var centroidY = centroid.getInhomY();
1711 final var centroidZ = centroid.getInhomZ();
1712
1713 final var numDimensions = numControl - 1;
1714 final var k = Math.sqrt(singularValues[0] / n);
1715 double vx;
1716 double vy;
1717 double vz;
1718 for (var i = 0; i < numDimensions; i++) {
1719 vx = v.getElementAt(0, i) * k;
1720 vy = v.getElementAt(1, i) * k;
1721 vz = v.getElementAt(2, i) * k;
1722
1723 controlWorldPoints.add(new InhomogeneousPoint3D(centroidX + vx, centroidY + vy, centroidZ + vz));
1724 }
1725
1726 // add centroid (it will be used for the metric transformation
1727 // estimation)
1728 controlWorldPoints.add(centroid);
1729 }
1730
1731 /**
1732 * A possible solution.
1733 */
1734 private static class Solution {
1735 /**
1736 * Control points in camera coordinates.
1737 */
1738 List<Point3D> controlCameraPoints;
1739
1740 /**
1741 * Transformation from world to camera coordinates.
1742 * Point projection is expressed by x = P * Xw, where P is a pinhole
1743 * camera and Xw is a point in world coordinates.
1744 * Points in camera coordinates are expressed as:
1745 * Xc = Tw-<c * Xw, where Tw-<c is the transformation from world to
1746 * camera.
1747 * The Euclidean transformation Tw-<c is expressed as:
1748 * Tw-<c = [R t]
1749 * [0' 1]
1750 * Projection of a point in camera coordinates can also be expressed
1751 * as x = Pc * Xc = K * [I 0] * Xc
1752 * where Pc is a camera and has the form Pc = K *[I 0], so that
1753 * x = Pc * Xc = K * [I 0] * Xc = K * [I 0] * Tw-<c * Xw
1754 * x = K * [I 0] * [R t] * Xw = K * [I*R + 0, I*t + 0] * Xw =
1755 * [0' 1]
1756 * x = K * [R t] * Xw = K * [R - R*C] * Xw = x = P * Xw,
1757 * where R is a rotation and C is the camera center in world
1758 * coordinates.
1759 * Assuming that control points are obtained up to scale, then instead
1760 * of an Euclidean transformation we will assume that Tw-<c is a metric
1761 * transformation, hence:
1762 * Tw-<c = [s*R t2]
1763 * [0' 1 ]
1764 * To obtain the previous equation, then point in camera coordinates
1765 * must be 1/s*Xc so that:
1766 * x = Pc * 1/s * Xc = K * [I 0] * 1/s * Xc
1767 * x = K * [I 0] * 1/s * Tw-<c * Xw
1768 * x = K * [I 0] * 1/s *[s*R t2] * Xw = K * 1/s * [I*s*R + 0, I*t2 + 0]
1769 * [0' 1 ]
1770 * x = K * 1 / s * [s*R t2] * Xw = K * [R 1/s*t2] * Xw
1771 * where t = 1/s*t2 = -R*C and so again
1772 * x = K * [R t] * Xw
1773 * and camera center is C = -1/s*R'*t2
1774 */
1775 MetricTransformation3D worldToCameraTransformation;
1776
1777 /**
1778 * Pinhole camera using provided intrinsic parameters and estimated
1779 * transformation for this solution.
1780 */
1781 PinholeCamera camera;
1782
1783 /**
1784 * Re-projection error.
1785 */
1786 double reprojectionError;
1787 }
1788 }