View Javadoc
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-&lt;c * Xw, where Tw-&lt;c is the transformation from world to
1746          * camera.
1747          * The Euclidean transformation Tw-&lt;c is expressed as:
1748          * Tw-&lt;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-&lt;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-&lt;c is a metric
1761          * transformation, hence:
1762          * Tw-&lt;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-&lt;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 }