Tensor-Based Synchronization and the Low-Rankness of the Block Trifocal Tensor
Authors: Daniel Miao
Gilad Lerman
Joe Kileel
Venue: NeurIPS 2024 poster (2024)
Keywords: synchronization
tensor decomposition
structure from motion
multilinear rank
multiview geometry
trifocal tensor
higher-order scene information
Primary area: machine_vision
TL;DR: This paper introduces the block trifocal tensor, established a low multilinear rank, and introduces a global synchronization framework for trifocal tensors.

Abstract: The block tensor of trifocal tensors provides crucial geometric information on the three-view geometry of a scene. The underlying synchronization problem seeks to recover camera poses (locations and orientations up to a global transformation) from the block trifocal tensor.  We establish an explicit Tucker factorization of this tensor, revealing a low multilinear rank of $(6,4,4)$ independent of the number of cameras under appropriate scaling conditions. We prove that this rank constraint provides sufficient information for camera recovery in the noiseless case. The constraint motivates a synchronization algorithm based on the higher-order singular value decomposition of the block trifocal tensor. Experimental comparisons with state-of-the-art global synchronization methods on real datasets demonstrate the potential of this algorithm for significantly improving location estimation accuracy. Overall this work suggests that higher-order interactions in synchronization problems can be exploited to improve performance, beyond the usual pairwise-based approaches.

Tensor-Based Synchronization and the Low-Rankness of the Block Trifocal Tensor
Daniel Miao
Gilad Lerman"
Joe Kileel
Abstract
The block tensor of trifocal tensors provides crucial geometric information the three-view geometry of a scene. The underlying synchronization problem seeks to recover camera poses (locations and orientations up to global transformation) from the block trifocal tensor. We establish an explicit Tucker factorization of this tensor, revealing low multilinear rank of (6,4,4) independent of the number of cameras under appropriate scaling conditions. We prove that this rank constraint provides sufficient information for camera recovery in the noiseless case. The constraint motivates synchronization algorithm based on the higher-order singular value decomposition of the block trifocal tensor. Experimental comparisons with state- of of-the-art global synchronization methods on real datasets demonstrate the potential this algorithm for significantly improving location estimation accuracy, Overall this work suggests that higher-order interactions in synchronization problems can exploited improve performance, beyond the usual pairwise-based approaches.
1 Introduction
Synchronization is crucial for the success of many data-intensive applications, including structure from motion, simultaneous localization and mapping (SLAM), and community detection. This problem involves estimating global states from relative measurements between states. While many studies have explored synchronization different contexts using pairwise measurements, few have considered measurements between three or more states. In real-world scenarios, relying solely on pairwise mea- surements often fails to capture the full complexity the system. For instance, in networked systems, interactions frequently occur among groups of nodes, necessitating approaches that can handle higher- order relationships. Extending synchronization to consider measurements between three or more states, however, increases computational complexity and requires sophisticated mathematical models. Ad- dressing these challenges is vital for advancing various technological fields. For example, higher-order synchronization can improve the accuracy of 3D reconstructions in structure from motion by leveraging more complex geometric relationships. In SLAM, it enhances mapping and localization precision in dy- namic environments by considering multi-robot interactions. Similarly, in social networks, it could lead to more accurate identification tightly-knn knit groups Developing efficient algorithms to handle higher- order measurements will open new research avenues and make systems more resilient and accurate.
In this work, we focus on a specific instance of the synchronization problem within the context of structure from motion in 3D computer vision, where each state represents the orientation and location of camera. Traditional approaches rely on relative measurements encoded by fundamental matrices, which describe the relative projective geometry between pairs of images. Instead, consider higher-order relative measurements encoded in trifocal tensors, which capture the projective information between triplets of images. Trifocal tensors uniquely determine the geometry of three views, even in the collinear case [ making them more favorable than triplets of fundamental matrices
"Shool Mathematies, University Minnesota (miao0022 @ wem.emm.iil edu lerman @ deeummeeei Department of Mathematics and Oden Institute for Computational Engineering and Sciences, University of Texas at Austin (jkileel @ math.utexas.eduu
38th Conference on Neural Information Processing Systems (NeurIPS 2024).

---

for synchronization. To understand the structure and properties of trifocal tensors in multi-viww geometry, we carefully study the mathematical properties of the block tensor of trifocal tensors. We then use these theoretical insights to develop effective synchronization algorithms.
Directly relevant previous works. In the structure from motion problem, synchronization has traditionally been done using incremental methods, such as Bundler [2] and COLMAP [3]. These methods process images sequentially, gradually recovering camera poses. However, the order of image processing can impact reconstruction quality, as error may significantly accumulate. Bundle adjustment H which jointly optimizes camera parameters and 3D points, has been used to limit drifting but is computationally expensive.
Alteratively, global synchronization methods have been proposed. These methods process multiple images simultaneouslyy avoiding iterative procedures and offering more rigorous and robust solutions. Global methods generally optimize noisy and corrupted measurements by exploiting the structure of relative measurements and imposing constraints. Many global methods solve for orientation and location separately, using structures on (3(3) and the set of locations. Solutions for retrieving camera poses from pairwise measurements have been developed for camera orientations [5] 6 7 g | [0).
camera locations 1|| [2 13,, and both simultaneously [4] 15
Some methods explore the
structure on fundamental or essential matrices 18 19 20
Several attempts extract information from trifocal tensors include works by: Leonardos et al. [2]] which parameterizes calibrated trifocal tensors with non-collinear pinhole cameras as a quotient Riemannian manifold and uses the manifold structure estimate individual trifocal tensors robustly; Larsson et al. [22], which proposes minimal solvers to determine calibrated radial trifocal tensors for use in incremental pipeline, handling distorted images with constraints invariant radial displacement; and Moulon et al. [23], which introduces a structure from motion pipeline, retrieving global rotations via cleaning the estimation graph and solving a least squares problem, and solving for translations by estimating trifocal tensors individually by linear programs. To our knowledge, no prior works develop global pipeline where the synchronization operates directly on trifocal tensors.
Contribution this work. The main contributions of this work are as follows:
We establish an explicit Tucker factorization of the block trifocal tensor when its blocks are suitably scaled, demonstrating a low multilinear rank of (6,4,4). Moreover, we prove that this rank constraint is sufficient to determine the scales and fully characterizes camera poses in the noiseless case.
We develop method for synchronizing trifocal tensors by enforeing this low rank constraint on the block tensor. We validate the effectiveness of our method through tests on several real datasets structure from motion.
2 Low-rankness of the block trifocal tensor
We first briefly review relevant background material in Section 2.1 Then we present the main new construction and theoretical results in Section 2.2
2.1
Background
2.1.1
Cameras and 3D geometry
Given collection of images In,...,/n, of a scene, let ER3 and R SO denote the location and orientation of the camera associated with the image T; in the global coordinate system. Moreover, each camera associated with calibration matrix K; that encodes the intrinsic parameters of camera, including the focal length, the principal points, and the skew parameter. Then, the 3 x camera matrix has the following form, P,= = K2 R, [3xx3 -t,] and defined up to nonzero scale. Three-dimensional world points X are represented as 4 vectors in homogeneous coordinates, and the projection of X into the image corresponding to is x P PX. 3D world lines can be represented via Plücker coordinates R vector. Then the projection of L onto the image corresponding P lisl=7 PL, where P is the 3 x line projection matrix. It can be written as P= [ xPl AP] where P is the i-th row of the camera matrix P and wedge denotes exterior product. Explicitly the (i.j) element of the line projection matrix can be calculated the determinant of the submatrix, where the i-th row

---

is omitted and the column are selected as j-th pair from (122),(333)31,,,),2))3..)) elements on the second row are multiplied by -1
The
To retrieve global poses, relative measurement of pairs or triplets of images is needed. Let and æy be any pair of corresponding keypoints in images 7; and I respectively, meaning that they images of common world point. The fundamental matrix Fiz is 3 matrix such that 22 F1y2 =0. It known that Fsy encodes the relative orientation R.j R, and translation t.j (t, ty) through Faj K;-
[t,y]x K The essential matrix corresponds to the calibrated case, where K; = I3x3 for all i.
2.1.2 Trifocal tensors
Analogous to the fundamental matrix, the trifocal tensor Tisk is a 3 x 3 x tensor that relates the features across images and characterizes the relative pose between a triplet of cameras P The trifocal tensor Tiyk corresponding cameras j.PPjPs can be calculated by
P Pd
(Tisk)wor = (-1) det
where P.V. is the w-th row of P., and P. is the 2 x 4 submatrix of P. omitting the w-th row. The trifocal tensor determines the geometry of three cameras up to global projective ambiguity, or up to scaled rigid transformation in the calibrated case. In addition to point correspondences. trifocal tensors satisfy constraints for corresponding lines, and mixtures thereof. For example, let 4,44 d be corresponding image lines in the views of cameras P. Pk respectively, then the lines are related through the trifocal tensor Ti by (1T ((TTak)) I:: (Tizk) (Tij)e (x::1%)) [ = =0", where [1] denotes the x3 seemmyymetrric matrix corresponding to cross product by I. We refer [ for more details of the properties of trifocal tensor. We include the standard derivation of the trifocal tensor in Appendix A
Since corresponding lines put constraints on the trifocal tensor, one advantage of incorporating trifocal tensors into structure from motion pipelines is that trifocal tensors can be estimated purely from line cor- respondences a mixture of points and lines. Fundamental matrices can not be estimated directly from line correspondences, so the effectiveness of pairwise methods for datasets where feature points are scarce is limited. Furthermore, trifocal tensors have the potential to improve location estimation. From pairwise measurements, one can only get the relative direction but not the scale and the location estima- tion in the pairwise setting is "notoriously difficult problem" (quoting from pages 316-317 of (24). However, trifocal tensors encode the relative scales of the direction and can greatly simplify the location estimation procedure. We refer to several works on characterizing the complexity of minimal problems for individual trifocal tensors 25 26 and on developing methods for solving certain minimal problems 32
33 We also refer to (4] for survey paper on structure from motion, which discusses minimal problem solvers from the perspective of computational algebraic geometry.
27 (28 [29], 3D
2.1.3 Tucker decomposition and the multilinear rank of tensors
We review basic material on the Tucker decomposition and the multilinear rank of tensor. We refer to (35) for more details while adopting its notation. T R x x12x be an order N tensor. The mode-i flattening (or matricization) T(e E 1
the rearrangement of T into matrix by taking mode-i fibers to be columns of the flattened matrix. By convention, the ordering of the columns in the flattening follows lexicographic order of the modes excluding i. Symbols & and @ denote the Kronecker product and the Hadamard product respectively. The norm tensors defined as ||||| = [T())ll The i-rank of T is the column rank of T(g) and is denoted as rank; (T). Let R;=rank; (T). Then the multilinear rank of T is defined as mlrank(T) = Ro..... Rx). The i-mode product of T with matrix U mR is tensor in R xI-x x 1 xIn such that
(T (Tx;U) jnUU 18i11"NN Ti Ukj.
Then, the Tucker decomposition of TEERR x is decomposition of the following form:
T=gx; X X A Axll
3

---

where G ERRQ xx is the core tensor, and A,, RR',.Qxx are the factor matrices. Without loss of generality, the factor matrices can be assumed have orthonormal columns. Given the multilinear rank of the core tensor (R....,,xy) Ry), the Tucker decomposition approximation problem can be written as
argmin
A2.
GER X XRN X.ER
A standard way of solving 2 is the higher-order singular value decomposition (HOSVD). The HOSVD is computed with the following steps. First, for each i calculate the factor matrix A, as the X2.. X n Aly- Though the solution from HOSVD will not be the optimal solution (2), it satisfies quasi-optimality property: if is the optimal solution, and T' the solution from HOS VD, then
R2 leading left singular vectors of Tie)- Second, set the core tensor G as 9 7x Af
(3)
2.2 Low Tucker rank of the block trifocal tensor and one shot camera retrieval
Suppose we are given a set of camera matrices [P:) with n 2 3 and scales fixed on each camera matrix. Define the block trifocal tensor T be the 3n 3n x 3n tensor, where the x x sized ijk block is the trifocal tensor corresponding to the triplet of cameras P.P.. We assume for all blocks that have overlapping indices, the corresponding 3 1x3xx x3 tensor is also calculated using the formula (.) We summarize key properties of T in Proposition and Theorem | is by direct computation and can be found in Appendix
The proof of Proposition
Proposition We have the following observations for the block trifocal tensor T", For all distinct
i.j [n]. we have the following properties:
(i) Th -3x333
(ii The The blocks are rearrangements of elements in the fundamental matrix Fig up to signs.
(ii)) The Thje and andT., blocks encode the epipoles.
(iv) The horizontal slices T (i;i)) T are skew symmetric.
(v) When all cameras are calibrated, three singular values Tf are equal.
Theorem 1 (Tucker factorization and low multilinear rank of block trifocal tensor). The block trifocal tensor T admits a Tucker factorization, T -G Xx2Cxx x3C, where G R2x44x4 p E & 33x6 and C E R3nx4, If the n cameras that produce T" are not all collinear. then mirank(T")) = (6.4.4). If the n cameras that produce T are collinear, then mirank(T")) (6,4,44)
Proof. We can explicitly calculate that T = G Gxi PxpC X3C. The details of the calculation are in Appendix[A.2 The specific forms for G,C.P are the following. The horizontal slices of the core are
0000
C000
Loce
0ase
Co
The factor matrices are C= PP..P Px) 5 and P- -S the camera matrices and St are the corresponding line projection matrices.
S.)"
3n36
where P. are
Now, we suppose that the cameras not collinear. We first show that C' and P both have full rank. From [] the null space of a camera matrix P. is generated by the camera center. For the sake of contradiction, suppose that rank(C) < 4. Then there exists R4 such that x: * and Cr 0. This means that = for all i= 1...,,, Then, r is the camera centre for all cameras, which means that the cameras centered one point and are collinear. Similarly, every vector in the null space of the line projection matrix S, is a line that passes through the camera centre I For the sake of contradiction, suppose that rank(P) 6. Then there exists E R such that x / and Pa O. This implies that S 0 for all i = ,,,, which means that x is a line that passes through all of the camera centers. Again the cameras trifocal tensor as T(i = ( Then 3 has rank 6, and (C (C&C)T= IR 16x9n has rank 16. Given the specific form of G. where G()) 1 is easy to check ran)(G(1)) = 6. Thus,
collinear, which is contradiction. Next we write the flattening of the block

---

rank 6. Similarly, we can show that rank(TT))) = 4, and (3)) )= = 4. This implies that the multilinear rank of the block trifocal tensor is (6,4,4) when the cameras not collinear.
When the n cameras are collinear, the individual factors in each flattening may be rank deficient, so that rank(T())) S 6,, rank(T S 4, and rank(T S 4. This implies mirank(?"") << (6,4,4).
The theorem inspires a straightforward way of retrieving global poses from the block trifocal tensor, which we summarize in the following claim.
Proposition 2 (One shot camera pose retrieval). Given the block trifocal tensor T produced by cameras P1, Pa.,...... Pa. the cameras can be retrieved from T up to a global projective ambiguity using the higher-order SVD. The cameras will be the leading singular vectors of (2) (())-
Using the higher-order SVD on T", we can get a Tucker decomposition of the block trifocal tensor T" 9 x1 P X2 C X3 C" Though the Tucker factorization is not unique [35], as we can apply an invertible linear transformation to one of the factor matrices and apply the inverse onto the core tensor, this invertible linear transformation can be interpreted as the global projective ambiguity for projective 3D reconstruction algorithms. Thus, the cameras can be retrieved by taking the leading four singular vectors of the mode-2 and mode-3 flattenings of the block tensor.
Very importantly however, in practice each trifocal tensor block in 7 can be estimated from image data only up to an unknown multiplicative scale D. The following theorem establishes the fact that the multi- linear rank constraints provide sufficient information for determining the correct scales. In the statement Oo denotes blockwise scalar multiplication, thus the (i.j.k) )-jj.k)-boock block of AO,T" is Assa E 3x3x33
Theorem 2. Let T E I2 x333x33 be a block trifocal tensor corresponding to n 2 4 calibrated or uncalibrated cameras in generic position. Let À E Ruxaxu be a block scaling with Xigk nonzero iff i.j.k are not all equal. Assume that X O, T E R x33x333 has multilinear rank (6,4,4) where Os denotes blockwise scalar multiplication. Then there exist a,B.y E R such that Xagk a,,3y% whenever i.j.k: ka are not all the same.
Sketch. The idea is to identify certain submatrices in the flattenings of X Ob 7 which must have determinant 0, and use these solve for A. A proof is in Appendix |A.4, We remark that the proof technique extends that of [36, Theorem 5.1], which showed a similar result for a matrix problem. n
Theorem is the basic guarantee for our algorithm development below. We stress that the ambiguities brought by a,B,,y y are not problematic for purposes of recovering the camera matrices by Proposition 2 Indeed, (a X 8 (8)) y) @s T G x1 (DaP) P) X2 (D&C)= X3 (D,C) where D. R is the diagonal matrix with each entry of a triplicated, etc. Hence the camera matrices can still be recovered up to individual scales (as expected) and global projective transformation, from the higher-order SVD.
Synchronization of the block trifocal tensor
In this section, we develop a heuristic method for synchronizing the block trifocal tensor 7 by exploiting the multilinear rank of T from Theorem | Let 7'm denote the estimated block trifocal tensor, and 7 the ground truth. Assume that there are n images and a set of trifocal tensor estimates Pisk where ki.j,k) E l2 and Ω is the set of indices whose corresponding trifocal tensor is estimated. Note that each estimated trifocal tensor F.ye will have unknown scale Xijz E RR associated with it. We always assume that we observe the iú blocks, as they will be O. We formulate the block trifocal tensor 7 by plugging in the estimates Tiyk and setting the unobserved positions ((1.j.k) & Q)) to 3 x 3 x 3 tensors of all zeros. Let Wa E [0,1)33 3 denote the block tensor where the (i.j.k) blocks are ones for (i.j.)) E Ω and zeros otherwise. Let Wne denote the opposite. In our experiments, we observe that the HOSVD is quite robust against noise for retrieving camera poses, which arises e.g., from numerical sensitivities when first estimating relative poses [3]. Therefore we develop an algorithm that projects Im onto the set of tensors that have multilinear rank of (6,4,4) while completing the tensor and retrieving an appropriate set of scales. Specifically, we can write our problem as
min fM -AAAA_"("AA'" \1
5

---

where A E R3 x3n each 3 x 3 x block is uniform, Aijk blocks are zero for (i.j.k) & Ω and A satisfies a normalization condition like || | = 1 to avoid its vanishing. However, we drop this normal- ization constant in our implementation as we never observe A vanishing practice. (For convenience, we formulate this section with the notation of A E 125xx3nxx x3n and Hadamard multiplication, rather than À _"x*x" and blockwise scalar multiplication from Theorem 2 Furthermore in problem (4) P- denotes the exact projection onto the set T {T E R x 3n 33n mirank (T) = (6,4,4)) Note that though HOSVD provides an efficient way to project onto r, it is quasi-optima and not the exact projection. The exact projection is much harder to calculate, and in general NP-hard. The algorithm below adopts an alternating projection strategy to estimate the best set of scales.
3.1 Higher-order SVD with hard threshold (HOSVD-HT)
The key idea for our algorithm is to use the relative scales on the rank truncated tensor as a heuristic to retrieve scales for the estimated block tensor. There are two main challenges for calculating the rank truncated tensor. First, the exact projection Pr onto is expensive and difficult to calculate. Second, many blocks in the block tensor will be unknown if the corresponding images of the block lacks corresponding point and directly projecting the uncompleted tensor will be inaccurate. We apply an HOSVD framework with imputations to tackle the challenges. Regarding the first challenge, HOSVD is a simple, efficient, and quasi-optimal (3 projection onto I'. Though inexact, it a reliable approx- imation. For the second challenge, the tensor 1 must be completed. We adopt the matrix completion 38 where the matrix is filled-in iteratively with the rank truncated matrix
idea of obtained using the thee-thresholded SVD. In other words, we complete the missing blocks with the corresponding blocks the rank truncated tensor. We define three hyperparameters l .12.13 that corre- spond to the thresholding parameters of the hard-thresholded SVD on modes 1,2,3 of the block tensor respectively. Specifically, for each mode-i flattening (i)- we calculate the full SVD Tū; = USVT. Since our tensor will scale cubically with the number of cameras, we suggest using a randomized SVD. We refer to (39] for different randomized strategies. Assume the singular values o; on the diagonal of S are sorted descending order, as usual. We return the factor matrix A; as the top a left singular vectors S >
in U, where = max i
4.. Our adapted truncation method is summarized by Algorithm |
Algorithm 1 HOSVD-HT
Input: 7 3R3x33nx3n the estimated block tensor; 1,,2,13 E R: the thresholds for modes 1,2,3
respectively
Output: 7. 3 the rank truncated tensor.
fo
Perform the randomized SVD on the mode-i flattening such that d77, + UUSV
0, ma: 4}
A first a; columns o
end for
g = 7M x1 Af X2 A A3
From now on, we refer to hard-thresholdes HOSVD HOSVD-HT and denote the operation as Pri-
3.2 Scale recovery
HOSVD-HT provides an efficient way for projecting Í onto the set of tensors with with truncated rank. To recover scales, we use the rank truncated tensor's relative scale as a heuristic to adjust the scale on our estimated block trifocal tensor (n)), For each step, we solve
A (++1) argmin| Λof" (A (1) ofr>i s.t. Aigh = 03xaxa for (i.j.)) 2
(5)
where we drop the normalization condition on A because in practice it is not needed. We solve (5) for each observed block separately. Denoting Pie (A(1) oTm) as (1,))() we have
(race((Tr)) 15k 1 ((T)) (a)))))))))
A (t-1)
= argmin (a
T (I,m ) 1==
(6)
ijk
[K 1ikk JayB
(t) (
"

---

Recall that our strategy for completing the tensor is to impute the tensor with the entries from the rank truncated tensor using HOSVD-HT. Specificallly, given the current imputed tensor (Tm)(0) we calculate Phe ((T()))))) and the new scales 11+1), Then update with
((m)(t+))_ = (A(+))
(7)
3.3
Synchronization algorithm
Now summarize synchronization framework in Algorithm
We have observed that the
Algorithm 2 Synchroonzztiion of the block trifocal tensor
Input: 1 Ignnx3nx33 Wge E {0,1) s 12, E
Output: CE CERsmx4; camera matrices up to a 4 x projective ambiguity and camera-wise scales Initialize 1 by imputing unobserved blocks randomly to get (Tm)(0) while not converged do
Calculate Par ((7m))n (0) using HOSVD-HT
Calculate (1+11 (5) using i (6)
(Tm)(t+1)+ + (A (++1) C Pit 1+1+1 end while
((SV
C First 4 columns Ag
algorithm can overfit, as the recovered scales will experience sudden and huge leaps. Our stopping criteria for the algorithm when we observe sudden jumps the variance of the new scales or when we exceed maximum number of iterations. Another challenge in structure from motion datasets that estimations may highly corrupted. The HOSVD framework mainly consists of retrieving dominant subspace from each flattening. Thus, it is natural to replace the SVD on each flattening
with more robust subspace recovery method, such as the Tyler's M estimator (TME) (40) or a recent extension TME that incorporates the information of the dimension of the subspace in the algorithm We refer to Appendix A.5.2 for more details and provide an implementation there.
41.
Numerical experiments
We conduct experiments of Algorithm@ two benchmark real datasets, the EPFL datasets 42 and the Photo Tourism datasets [П] We observe that the algorithm performs better in the calibrated setting, and since the calibration matrix is usually known in practice, we restrict our scope of experiments to calibrated trifocal tensors. We compare against three state-of-the-arr synchronization based on two view measurements, NRFM [18] and LUD [2]. NRFM relies nonconvex optimization and requires a good initialization. We test NREM with an initialization obtained from LUD and with a random initialization. We also test BATA 43 initialized with MPLS (9] We refer to A. the appendix for a comprehensive summary of numerical results including rotation and translation estimation errors. We include code in the following github repository: TrifocalSync
4.1 EPFI dataset
For EPFL. we follow the experimental setup and adopt code from (44 and test an entire structure from motion pipeline. We first describe the structure from motion pipeline for EPFL experiements.
Step (feature detection and feature matching). We obtain matched features across pairs of images using a modern deep learning based feature detection and matching algorithm, GlueStick (45. Though do not implement this in experiments, there have been methods developed further screen corrupted keypoint matches or obtain matches robustly, such as [46] 47 48). Key points across triplet of cameras is matched from pairs and is included only if appears all the pair combinations of the three images.
Step (estimation and refinement of trifocal tensors). With the triplet matches, we calculate the trifocal tensors with more than 11 correspondences. To have an even sparser graph, one can skip the
7

---

estimation of trifocal tensors and rely the imputation for images that have less than number bigger than 11 point correspondences. This can further speed up the trifocal tensor estimation process. We apply STE from [4] to find 40% of the correspondences as inliers, then use at most 30 inlier point correspondences linearly estimate the trifocal tensor. To refine the estimates, we apply bundle adjustment on the inliers and delete triplets with reprojection error larger than 1 pixel.
Step 3 (synchronization) We synchronize the estimated block trifocal tensor with robust variant of SVD using the framework described Algorithm 2 The robustness comes from replacing SVD with robust subspace recovery method [4] More details can be found in Appendix A.5.2 Recall that the cameras we retrieve are up to a global projective ambiguity. When comparing with ground truth poses, first align our estimated cameras with the ground truth cameras by finding 4 x projective transformation. Then we round the cameras to calibrated cameras and compare.
We full pipeline two EPFL datasets personal machine with GHz Intel Core i5 with 4 cores and 16GB of memory. To test NRFM [88 LUD 12 and BATA 4 initialized with MPLS We did not include blocks corresponding to two views in our trifocal tensor pipeline. The mean and median translation errors are summarized in Figure There and more comprehensive results can be found in Table and Table in the appendix.
[9]. we estimate the corresponding essential matrices using the GC-ransac 449
20
20
Our
NRFM (LUD)
NRFM (LUD)
LUD
LUD
Mean Transiation Error
15
NRFM
Medien Translation Error
NRFM
(MPLS)
BATA (MPLS)
10
FP11 HZP8 HZ25 EN10 CS19 CS30
FP11 HZP8 HZ25 EN10 CS19 CS30
Figure 1: EPFL translation error comparison between our method, NRFM initialized by LUD, LUD, and NRFM initialized randomly. BATA(MPLS) stands for BATA initialized by MPLS. HZ8 stands for HerzP8, FP11 for FountainP11, HZ25 for Herz P25, EN10 for EntryP1O, CS19 for CastleP19, CS30 for CastleP3O.
The EPFL datasets generally have plethora of point correspondences, that the trifocal tensors are estimated accurately. When the dataset focuses on a single scene, our algorithm retrieves locations competitively. Our algorithm achieves the best location estimation for out of 6 datasets. The translation error bars are not visible for FP11, HZP8, EN10 due to the accuracy that we achieve. However, our pipeline is incapable of accurately processing CastleP19 and CastleP30. The main reason that our algorithm relies on having a very dense observation graph to ensure high completion rate. CastleP19 and CastleP30 so that not many triplets have overlapping features. Our method is not suitable for this type of dataset. However, it is possible to apply our algorithm in parallel on groups of neighboring frames, so that the completion rate is high in each group. Then the results can be merged to obtain larger reconstruction. Rotations for the two view methods are estimated via rejecting outliers from iteratively applying (10). We also compare against (43) for location estimation, where we initialize with state-of- of-the-art global rotation estimation method [9] Our algorithm achieves superior rotation estimation for only out of the 6 datasets. See Table I and in the appendix for comprchensive errors.
datasets where the camera scans portions of the general
sequentially,
4.2 Photo Tourism
We conduct experiments on the Photo Tourism datasets. The Photo Tourism datasets consist of internet images of real world scenes. Each scene has hundreds to thousands of images. The datasets

---

[1 provide essential matrix estimates, and we estimate the trifocal tensors from the given essential matrices. To limit the computational cost for tensors, we downsample the datasets by choosing cameras with observations more than a certain percentage in the corresponding block frontal slice while maintaining decent number of cameras. Note that this may not be the optimal way of extracting a dense subset in general. The maximum number of cameras we select for each dataset is 225 cameras. The largest dataset Piccadilly has 2031 cameras initially. We randomly sample 1000 cameras and then run our procedure. For Roman Forum and Piccadilly, the two view methods further deleted cameras from the robust rotation estimation process or parallel rigidity test. We rerun and report the trifocal tensor synchronization algorithm with the further downsampled data. We initialize the hard thresholding parameters for HOSVD HT by first imputing the trifocal tensor with small random entries and then calculating the singular values for each of the flattenings. We take L to be the tertile singular value for each mode-i flattening. We then keep this parameter fixed for the synchronization process. Recall that the júi blocks in the block trifocal tensor correspond to elements in the essential matrix Eij. We also include these essential matrix estimations in the block trifocal tensor. The Photo Tourism experiments were run on HPC center with 32 cores, but the only procedure that can benefit from parallel computing in single experiment is the scale retrieval. Mean and median translation errors are summarized in Figure 2 Fully comprehensive results can be found in Tables 3 Band in Appendix A.6
Our NPFE (LUD in
Our YARM LUD Int)
(Pand int I0A NM
YARM Fand 5AtAgerLS
007
20-
Pauna du Pepplo
dio Madiet Merrosi
Tower of London
Vier Cotherne
Romin firmm
Mostral U.D.
Lnton Scuore
Paese MH
Mechar Vorambuoee
080 Iolend
Tower Londbn
Viema Dalhetta
Nomon Hole Monmer D.
Usbon Siuaro
Gevtbmuttnon Pecieliyy
(a) Photo Tourism mean translation errors
(b) Photo Tourism median translation errors
Figure 2: Photo Tourism translation error comparison between our method, NRFM initialized by LUD, LUD. NRFM initialized randomly, and BATA initialized with MPLS. Note that we have not been able to acquire results for Piccadilly for BATA MPLS.
Our method is able to achieve competitive translation errors on 8 of the 14 datasets tested. Similar to the observation in the EPFL experiments, our algorithm performs well when the viewing graph is dense, or in other words, when the estimation percentage is high. We achieve better locations in 6 out 8 datasets where the estimation percentage exceeds 60%, and better locations in only out of datasets where the estimation percentage falls below 60%. We achieve reasonable rotation estimations for 10 out of 14 datasets, but not as good as LUD. See Table 4or a comprehensive result. Since the block trifocal tensor scales cubically with respect to the number of cameras, our algorithm runtime longer than most two view global methods. This could be alleviated by synchronizing dense subsets in parallel and merging the results to construct larger reconstruction.
Trifocal tensors can be estimated from line correspondences mix of point and line correspondences, while fundamental matrices are estimated from only point correspondences. There are many situations where accurate point correspondences are in short supply but there is plethora of clear and distinct lines. For example, see datasets in a recent SIM method using lines [50] We demonstrate the potential of our method to be adapted to process datasets with only lines or very few points. Due to the limited availability of well annotated line datasets, we provide a small synthetic experiment that simulates case where only lines correspondences are present. We first generate 20 random camera matrices, then we generate 25 lines that are projected on and shared across all images. We add about 0.02 percent of noise in terms of the relative frobenius norms between the line equation parameters and the noise. We estimate the trifocal tensor of three different views from line correspondences linearly. One remark is that our synchronization method works well only when the signs of the initial unknown scales mostly uniform. We manually use ground truth trifocal tensors
Additional remark:
9

---

to correct the sign of the scale. This has not been an issue in the previous experiments due to bundle adjustment for EPFL and the overall good estimations in Photo Tourism. In practice, the sign of the scale on a trifocal tensor can be corrected via triangulation of points or reconstruction of lines, and correcting the sign using the depths of the reconstructed points or intersecting line segments. We synchronize the trifocal tensors with Algorithmaaan were able to achieve mean rotation error of 0.61 degrees, median rotation error 0.49 degrees, mean location error of 0.76, and median location error 0. 0.74.
5 Conclusion
In this work, we introduced the block tensor of trifocal tensors characterizing the three-view geometry of scene. We established an explicit Tucker factorization of the block trifocal tensor and proved it has low multilinear rank of (6,4,4) under appropriate scaling. We developed a synchronization algorithm based on tensor decomposition that retrieves an appropriate set of scales, and synchronizes rotations and translations simultaneously. On several real data benchmarks we demonstrated tate-of-theear performance in terms of camera location estimation, and saw particular advantages on smaller and denser sets of images. Overall, this work suggests that higher-order interactions synchronization problems have the potential to improve performance over pairwise- pairwise-based methods.
There several limitations to our tensor-based synchronization method. First, our rotation estimations are not as strong as our location estimations. Second, our algorithm performance is affected by the estimation percentage of trifocal tensors within the block trifocal tensor. One could incorporate more robust completion methods and explore new approaches for processing sparse triplet graphs. Further, our block trifocal tensor scales cubically terms of the number of cameras and becomes computationally expensive for large datasets. We can develop methods for extracting dense subgraphs, synchronizing in parallel, then merging results obtain larger reconstruction, similarly to the distributed algorithms of [51] and [52). Moreover, our synchronization method's 's success depends on accurate trifocal tensor estimations, and it motivates further work on robust estimation of multi -vew tensors. Algorithm 2 could also be made more robust by adding outlier rejection techniques. Finally we plan extend our theory by proving convergence of our algorithm and exploring structures for even higher-order tensors, such as quadrifocal tensors.
Acknowledgement
D.M. and G.L. were supported in part by NSF award DMS 2152766. J.K. was supported in part by NSF awards DMS 2309782 and CISE-IIS IIS 2312746. the DOE award SC0025312, and start-up grants from the College of Natural Science and Oden Institute at the University of Texas at Austin.
We thank Shaohan Li and Feng Yu for helpful discussions on processing EPFL and Photo Tourism. We also thank Hongyi Fan for helpful advice and references on estimating trifocal tensors.
References
[1] Richard Hartley and Andrew Zisserman. Cambridge University Press, 2003.
Multiple
View Geometry in Computer Vision.
[2] Noah Snavely, Steven Seitz, and Richard Szeliski. Photo Tourism: Exploring photo collections in 3D. In Proceedings of the ACM Special Interest Group on Computer Graphics and Interactive Techniques Conference, SIGGRAPH 2006, pages 835-846, 2006.
[3] Johannes Schonberger and Jan-Michael Frahm. Structure-free motion revisited. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2016, pages 4104 1113,0016.
[4] Bill Triggs, Philip McLauchlan, Richard Hartley, and Andrew Fitzgibbon. Bundle adjustment A modern synthesis. In Bill Triggs, Andrew Zisserman, and Richard Szeliski, editors, Vision Algorithms: Theory and Practice, pages 298-372, Berlin, Heidelberg, 2000. Springer Berlin Heidelberg.
10

---

[5] Venu Madhav Govindu. Lie-algebraic averaging for globally consistent motion estimation. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2004, volume 1, pages 1-8, 2004.
[6] Richard Hartley, Jochen Trumpf, Yuchao Dai, and Hongdong Li. Rotation averaging. International Journal of Computer Vision, 103:267-305, 2013.
[7] Avishek Chatterjee and Venu Madhav Govindu. Robust relative rotation averaging. IEEE Trunsuctions on Puttern Analysis and Machine Intelligence, 40(4):958 2018.
[8] Avishek Chatterjee and Venu Madhav Govindu. Efficient and robust large-scale rotation averaging. In Proceedings of the IEEE International Conference on Computer Vision, ICCV 2013, pages 521-528 2013.
[9] Yunpeng Shi and Gilad Lerman. Message passing least squares framework and its application to rotation synchronization. In Proceedings of the International Conference on Machine Learning, ICML 2020, pages 8796-88066 8806, 2020.
[10] Mica Arih-Nachimson, Shahar Kovalsky, Ira Kemelmacher- Shaahhhee--Slliizaann Amit Singer, and Ronen Basri. Global motion estimation from point matches. In Proceedings of the International Conference on 3D Imaging, Modeling, Processing, Visualization Transmission, 3DIMPVT 2012, pages 81 88, 2012.
[11] Kyle Wilson and Noah Snavely. Robust global translations with IDSIM. In Proceedings of the European Conference Computer Vision, EECV 2014, pages 61-75, 2014. 2014..
[12] Onur Ozyesil and Amit Singer. Robust camera location estimation by convex programming. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2015, pages 2674 2683, 2015.
[13] Thomas Goldstein, Paul Hand, Choongbum Lee, Vladislav Voroninski, and Stefano Soatto. ShapeFit and ShapeKick for robust, scalable structure from motion. In Proceedings of the European Conference on Computer Vision, EECV2016, pages 289-304, 2016
[14] David Rosen, Luca Carlone, Afonso Bandeira, and John Leonard. SE-Sync: A certifiably correct algorithm for synchronization over the special Euclidean group. International Journal of Robotics Research, 38(2-3):95-125,, 2019.
[15] Federica Arrigoni, Beatrice Rossi, and Andrea Fusiello. Spectral synchronization of multiple views SE(3). SIAM Journal on Imaging Sciences, 144):19331190 2016.
[16] Mihai Cucuringu, Yaron Lipman, and Amit Singer. Sensor network localization by eigenvector synchronization over the Euclidean group. ACM Transactions on Sensor Networks, 8(3), 2012.
[17] Jesus Briales and lavier Gonnalez--lmmenez. Cartan-Sync: Fast and global SHldD--yychromizzttin.. IEEE Robotics and Automation Letters, 2(4):2127-2134 2017.
[18) Soumyadip Sengupta, Tal Amir, Meirav Galun, Tom Goldstein, David Jacobs, Amit Singer, and Ronen Basri. A new rank constraint on multi-view fundamental matrices, and its application to camera location recovery. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2017, pages 4798-4806. 2017.
[19] Yoni Kasten, Amnon Geifman, Meirav Galun, and Ronen Basri. Algebraic characterization of essential matrices and their averaging in multiview settings. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2019, pages 5895-5903, 2019.
[20] Yoni Kasten, Amnon Geifman, Meirav Galun, and Ronen Basri. GPSfM: Global projective SFM using algebraic constraints multi-view fundamental matrices. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2019, pages 3264-3273 2019.
[21] Spyridon Leonardos, Roberto Tron, and Kostas Daniilidis. A metric parametrization for trifocal tensors with non-colinear pinholes. In Proceedings of the IEFE Conference on Computer Vision and Pattern Recognition, CVPR 2015, pages 259-267, 2015.

---

[22] Viktor Larsson, Nicolas Zobernig, Kasim Taskin, and Mare Pollefeys. Calibration-fre free prnncture-frommmne motion with calibrated radial trifocal tensors. In Proceedings of the European Conference on Computer Vision, EECV 2020, pages 382-399, 2020.
[23] Pierre Moulon, Pascal Monasse, and Renaud Marlet. Global fusion of relative motions for robust, accurate and scalable structure- frooree-froo--oo motion. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2013, pages 3248-3255, 2013.
[24] Onur Ozyesil, Vladislav Voroninski, Ronen Basri, and Amit Singer. A survey of structure from motion. Acta Numerica, 26:305-364, 2017.
[25] Joe Kileel. Minimal problems for the calibrated trifocal variety, SIAM Journal on Applied Algebra and Geometry, 111):575-598, 2017.
[26] Timothy Duff, Kathlen Kohn, Anton Leykin, and Tomas Pajdla. PLMP-point-line minimal problems in complete multi-view visibility. In Proceedings the IEEE Conference Computer Vision and Pattern Recognition, CVPR 2019, pages 1675-1684, 2019.
[27] Ricardo Fabbri, Timothy Duff, Hongyi Fan, Margaret Regan, David da Costa de Pinho, Elias Tsigaridas, Charles Wampler, Jonathan Hauenstein, Peter Giblin, Benjamin Kimia, Anton Leykin, and Tomas Pajdla. Trifocal relative pose from lines at points. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(6):7870-7884, 2023.
[28] David Nister and Henrik Stewenius. minimal solution to the generalised 3-point pose problem. Journal of Mathematical Imaging and Vision, (7))))7-79,
[29] Ali Elqursh and Ahmed Elgammal. Line-based relative pose estimation. In Proceedings of the IEEE Conference on Computer Vision and Puttern Recognition, CVPR 2011, pages 3049-3056, 2011.
[30] Yubin Kuang and Kalle Astrom. Pose estimation with unknown focal length using points, directions and lines. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2013, pages 529-536, 2013.
[31] Zuzana Kukelova, Joe Kileel, Bernd Sturmfels, and Tomas Pajdla. A clever elimination strategy for efficient minimal solvers. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2017, pages 49211 2017.
[32] Pedro Miraldo, Tiago Dias, and Srikumar Ramalingam. A minimal closed-form solution for multi-perspective pose estimation using points and lines. In Proceedings of the European Conference on Computer Vision, ECCV 20CV, pages 474-490, 2018.
[33] Joe Kileel, Zuzana Kukelova, Tomas Pajdla, and Bernd Sturmfels. Foundations of Computational Mathematics, 18:1043-1071, 2018.
Distortion varieties.
[34] Joe Kileel and Kathlén Kohn. Snapshot of algebraic vision. arXiv preprint 2rXiv:2210.11443, 2022.
[35] Tamara Kolda and Brett Bader. Tensor decompositions and applications. SIAM Review, 51(3):455-55) 500, 2009.
[36] Tommi Muller, Adriana Duncan, Eric Verbeke, and Joe Kileel. Algebraic constraints and algorithms for common lines in cryo-EM. Biological Imaging, pages 1-30, Published online 2024.
[37] Hongyi Fan, Joe Kileel, and Benjamin Kimia. On the instability of relative pose estimation and RANSAC's role. In Proceedings of the IEEE Conference on Computer Vision and Pattern 2022.
Recognition 2022, pages
[38] Rahul Mazumder, Trevor Hastie, and Robert Tibshirani. Spectral regularization algorithms for learning large incomplete matrices. Journal of Machine Learning Research, 11:2287-2322, 2010.
[39] Nathan Halko, Per-Gunnar Martinsson, and Joel Tropp. Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions. SIAM Review 53(2):217-288, 2011.
12

---

[40] David Tyler. A distribution-free M-estimator of multivariate scatter. Annals of Statistics, pages 234-24 254-251,,4 1987.
[41] Feng Yu, Teng Zhang, and Gilad Lerman. subspace-consstrainee Tyler's estimator and its applications to structure from motion. arXiv preprini arXiv:2404.1159% 2024.
[42] Christoph Strecha, Wolfgang Von Hansen, Lue Van Gool, Pascal Fua, and Ulrich Thoennessen. On benchmarking camera calibration and multi-view stereo for high resolution imagery. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2008,
pages 1-8, 2008.
[43] Bingbing Zhuang, Loong-Fun Faa Cheong, and Gim Hee Lec. Baseline desensitizing in translation averaging. In Proceedings the IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2018), June 2018.
[44] Laura Julia and Pascal Monasse. A critical review of the trifocal tensor estimation. In Proceedings of the Pucific Rim Symposium on Image and Video Technology, PSIVT 2017, Revised Selected Papers& 8, pages 337-349. Springer, 2018.
[45] Rémi Pautrat, Iago Suárez, Yifan Yu, Mare Pollefeys, and Viktor Larsson. Gluestick: Robust image matching by sticking points and lines together. In Proceedings of the IEEE/CVF International Conference on Computer Vision, CVPR 2023, pages 9706 9706-9716, 2023.
[46] Yunpeng Shi, Shaohan Li, Tyler Maunu, and Gilad Lerman. Scalable cluster-consisteng: statistics for robust multi-object matching. In Proceedings of the International Conference on 3D Vision, 3DV 2021, pages 352-360, 2021.
[47] Yunpeng Shi, Shaohan Li, and Gilad Lerman. Robust multi-object matching via iterative reweighting of the graph connection laplacian. Advances in Neural Information Processing Systems, 33:15243-15253 2020.
[48] Shaohan Li, Yunpeng Shi, and Gilad Lerman. Fast, accurate and memory-efficient partial permutation synchronization. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2022, pages 15735- 15743, 2022.
[49] Daniel Barath and Jifí Matas. Graph-cut ransac. In Proceedings of the IEEE conference on computer vision and pattern recognition, CVPR 2018, pages 6733-6741, 2018.
[50] Shaohui Liu, Yifan Yu, Rémi Pautrat, Marc Pollefeys, and Viktor Larsson. 3d line mapping revisited. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, CVPR 2023, pages 21445 2,4,,,2225.
[51] Shaohan Li, Yunpeng Shi, and Gilad Lerman. Efficient detection of long consistent cycles and its application to distributed synchronization. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, CVPR 2024, pages 5260-5269, 2024.
[52] Andrea Porfiri Dal Cin, Luca Magri, Federica Arrigoni, Andrea Fusiello, and Giacomo Boracchi. Synchronization of group-labelled multi-graphs In 2021 JEEE/CVF International Conference IEEE, 2021.
on Computer Vision, ICCV 2021, pages
[53] Joe Harris. Algebraic Geometry: A First Course, volume 133. Springer Science & Business Media, 1992.
[54] Ying Sun, Prabhu Babu, and Daniel Palomar. Regularized Tyler's s scatter estimator: Existence, uniqueness, and algorithms. IEEE Transactions on Signal Processing, 62(19):5143-5155 2014.
13

---

A Appendix /suplemmnnal material
A.1 Derivation of the trifocal tensor
To provide better intuition for the trifocal tensor, we briefly summarize the derivation of the trifocal tensor from [ and [2] under the general setup of uncalibrated cameras.
Let P;= K; P.= R4 t.] be the form of the camera matrix for Ps Let L be a line in the 3D world scene, and 12,1z the corresponding projections in the images I 12.TI,I Is respectively. Each I back projects to a plane nं = P. I, in R2, and since I correspond to the same L in the 3D world scene, [TT must be rank deficient and its kernel will generically be spanned by L. Then,
K
R4
0
4
Rr2Rkk l2 (41-12) Ry K2
KJ
KrTRiaK' (4-44)) R2 K3 13
0
will also be wank-deficient implying that the columns of are linearly dependent. This means that there exist a such that γ = auT222 + f83z. We can choose a (11 - 133) R K3 13, 3= (t1 - 122) R K3 12, so that
1 (2 K2 Riak'l (/2 122 K2 [2 Ki (4+ 11)² R2g K3
Then, the canonical trifocal tensor centered at camera is defined
T; T
K R1gK3 - K2 -
K3
(8)
where e, E R is the i-th standard basis vector. The trifocal tensor will be the tensor {Ti ,T,,To.. 2 }. where
the T.'s are stacked along the first mode. The line incidence relation is then (4)) - 12 Til.. Other
combinations of point and line incidence relations are also encoded by the trifocal tensor; details. The construction for calibrated cameras is the same, just with P; in calibrated form.
[ for
A.2 Proof details for Theorem
We include detailed calculation for the Tucker factorization of the block trifocal tensor. Recall that each individual trifocal tensor corresponding to the cameras a,b can be calculated as
~a
- det
= =(-1) det
a
c²
c²
=(-1) +1 (det
0m3
ama1]
(b - -b +det
am2
am44
(-b bp3
an3
an4
an2
an4
del
am1
amd
am2
Am3
-
an1
ax1
an2
an3
+et
am1
4m3
aml
Qm2
(bp3Cr1 - by)
an1
an3
On1
an2
Co + -o bq1C3))
P(a)ak
bmw Σ Crngkwu-
The last equality can be easily checked since G is sparse. For example, when & 1, P(a)a is the determinant of the submatrix dropping the i-th row and keeping columns 1 and 2, which is det(a,, (m (.2)]. The only nonzero elements in the first horizontal slice are (1,,4,3) -1 and ((1, 3, 4) = 1. Then, the nonzero elements in the sum when k = 1 will be exactly P(a)a -- bqw Dn E, (b
Then, since P will be the stackings of P(P:), C is the stacking of camera matrices in Theorem each kjk block in 7 will be calculated by exactly the corresponding i, j. & blocks in P. C,C.C respectively using the calculations above.
14

---

A.3
Proof details for Proposition 1
frooffor (i). We have
P pd
ià Jugr (-1)uttdet
0,
Pr
since P: is a x matrix and the submatrix above will always have two identical rows.
frroffor (ii): Consider the wgr element of the jii block trifocal tensor, 77. It can be written
p pd
(T = (-1) det
PT
Thus, when 9= =, clearly ( 0 as we will have identical rows again. When @ + r, we first observe that (Tji))up (T julurg since we just swap two rows. Second,
p
(T uid = 1et
pd
(-1))n+ det
p pm
Pr
where m E (1,2,3) \ fg.r). This is exactly the bilinear relationship in 1 defining the fundamental matrix (F)))m element up possible negative sign.
Proof for (iii): We can only show this for Thi blocks from symmetry. The elements in Th blocks can be calculated as
P
(T Tiggerr = (-1) det
p
Elements are nonzero only when w = q, and they correspond determinants of matrices with three rows from one P: and one row from Pj- By [.. these are exactly the elements of the epipoles. When w=1, the order of the rows the determinant corresponding to camera (2,3,1), 1), when w= 2, the order is (1,3,2) and there is negative sign in front of the determinant, and when = 3, the order is (1,2,3). Since the first and last case are even permutations of the rows of P., and the second case is corrected by negative sign, (w7)) is exactly the epipole.
for (iv): On a horizontal slice, the camera along the 1st mode is fixed, and blocks symmetric across the diagonal is calculated by cameras, which the 2nd and 3rd mode cameras are swapped. Then, we will simply be swapping rows in (I). which means that we will simply be changing signs for elements symmetric across the diagonal, implying skew symmetry.
Proof for (v): Now assume that we have block trifocal tensor whose corresponding cameras are all calibrated. Let P be the line projection matrix, C = [P1, ... Pa is the stacked camera matrix, and is the core tensor. The flattening in the 1st mode can be written as (ii (C where Thi is a 3n x 9n² matrix. For the proof, we calculate the eigenvalue of of (P9 (C&0)))
To (T)(T))) T (aonCC))((ccccc) p" =P9ay(C* (cT)(c))))))) pr C CIgT,
The second and third line uses two Kronecker product properties: (A & B)T (A& AC'o BD as long as AC and BD are defined.
AT & BT and
We first calculate (C' C))
We assume that the cameras are centered at the origin, i.e. Em Then we have
nl3x3
nlax3
03x1
C² -
(9)
01x3
Σ ||
15

---

so that
nl3x3
Oaxi 02x1
(c' C
(10)
01xa80
Σ i= 111111111 1
We have explicit form for 9())=
0
0
0
0
0
0
0
-1
0
0
0
0
0
0
0
0
0
0
-1
0
0
0
0
0
0
-1
0
0
0
0
0
0
0
(())
(11)
0
0
0
-1
0
0
0
0
0
0
1
0
0
11
0
0
-1
0
0
1
0
Let X =CCCCam let i; denote the ij entry in CT C. Let Σ
1|
We first show that (1)) (C" (aCt is diagonal by direct computation:
Gay(C CCCCC&CCCCC C)g())
nxx4 +aX3
0.222
-2
aX
n.X11
-2X23
nX44 taX22
n.
aX21
nX41
nX24
NX3
n.X33 - n2X22 0
0
- N2X21
-nXs1
aX13
aXaa+aXı n.Xau
N2
n244
n nX14
-1112
n. +
-n1332
X13
n.244
N23
Yra + am
0
0
0
0
0
0
n
+-
0
0
0
na+an
0
+n2
O
0
n +n?
2nma
2ma
0
0
2n
2
0
0
0
2na
0
0
2n
2
0
0
0
2T²
We then calculate the spectral decomposition Ti) With a slight abuse of notation, let p denote the k-th column of P.. The 3n x rank-6 stacked line projection matrix would have columns ordered according to
Aez
el Aea
e2
e2 Aes ezAea),
and since the second row in P for each camera is Pd AP holds
P= P!xP? x
P!XP!
P2XP2 P2XP
P
Or equivalently, the stacked wedge products between columns. Let P UUST be the thin singular value decomposition P. so that a 3n x6 orthonormal matrix, S is a 6 x diagonal matrix where all diagonal entries are nonzero, and V is 6 6 orthonormal matrix.
Then,
Th - "
16

---

Since V is orthonormal, SV (t) @ () VS is still diagonal matrix. We just need to establish the fact that three of the diagonal entries are the same. For one camera, pd P equals
0 1 Pt P (P. (Pp
P.-Pt P.
0
PP 0
- -PP. P.
- (P) P (PP-P)))
(P) POOP PD)
P
(P) p3) - (P (PP
(P. . P.
(P' PP)- PPP-P)
1
0 1
P2
-P..P.
P.
0
-PP-PP))
|| -
1!1
(P,) PPPpPP pf)
-PP PPPPP ((PPPPP)) P())
pf pd
-P3.P PPP
where the matrix is symmetric and we reduce redundancy by omitting the entries below the diagonal. For cameras,
0
P.P.P
0
-EPP-Pp
n2
Ps
0 0
PP.P P PP' P.)) -E -E,(P- -P
pd p=
P.
P
0
(P!. P..
P.P.P
-1
P!1
where P..PP means the dot product between the ath and bth column
The SVD of of is pTp=
where H is 6 x orthonormal matrix. D is 6 x 6 diagonal matrix. However, since we have an nTax3 submatrix in PT'P, we deduce that n appears as an eigenvalue 3 times for pf'p, where can use the determinant identity for block matrices. We check that this indeed holds by a computer calculation, generating random instances of Py's and calculating the eigenvalues for p''p.
As result, in the thin SVD P, we have PUUSV where S=VD.V=Ht in in
Th (i))T))) =Pg pT (U(SV"Ga))CC Cac "
Coc"
we see that SV ( T V is a diagonal matrix where three of the entries are the same. By the uniqueness of the eigenvalues, we see that we have a spectral decomposition of Th (77)) Tr so that three of the singular values of Ti) are equal.
A.4 Proof details for Theorem 2
Note blockwise multiplication by rank-1 1 tensor with nonzero entries preserves multilinear rank, since it is a Tucker product by invertible diagonal matrices. Therefore, without loss of generality may assume Ar1 λ1,1 \1ι = 1 for all i.j.k E f2. Below we will prove it follows Aisk = c if exactly one of i.j, A equals 1, and Ayk = c² if none of i.j, equal 1 and the indices are not all the same, for some constant ce R*. This will immediately imply the theorem, because taking 8 (1cc...c) and 7 ( (1.....) achieves Aua a,,8y7 whenever i.j k are not all the same.
Proof.
We consider the matrix flattenings Th and (AO, T") (2) in x3 of the block trifocal tensor and its scaled counterpart, with rows corresponding to the second mode of the tensors. By Theorem I and assumptions, the flattenings have matrix rank 4, thus all of their 5 x 5 minors vanish. The argument consists of considering several carefully chosen 5 x 5 submatrices of (A Os T )()))) to prove the existence of constant e as above. Index the rows and columns of the flattenings by (j.r) and kig
respectively, for i.j.k E [n] and g,r,3 e [3), so that c.g., (2)) Aigh (Tm ggre
17

---

Step 1: The first submatrix of (A@&T") (2) we consider has column labels (i1,11), (11,21), (i1,31),
(i1,12), (12,11) and row labels (1,1), (L3)),))))) where i m2. Explicitly, is
(Tai)
(T (2m1)2
(Ti1)
(Tidm
(1
(111))21
(11))
1221)
(TT1)121
(311)a1
(11))231
(111)33
(111)
Aa1 (T 111
A61 (TT 2211
A81 (Th) )a11
A61 (a
Aia A
Amn (Th) 121
A61 (T )2)
Aan (TT) )221
Aea (T1)
(1a(Tig)12
which abbreviate
*
*
*
(12)
A
Ass1*
Ass
Aus *
A1G
As1*
Ass1*
As11
Aa1*
A1a
with asterisk denoting the corresponding entry in (2)- As a function of A4i the determinant of (12) is degree v polynomial, which must be divisible by λşıı and A - Ausa (because if AR = then clearly the bottom two rows of (T2) are linearly independent, and if λςa A1Si we have submatrix of Tf with the bottom two rows scaled uniformly). So the determinant of 12 is scalar multiple of
As1 (Aa1 - >1t). Note that the multiple is polynomial function of the cameras P1 and P.. We claim that generically the multiple is nonzero; and see this, it suffices to exhibit a ssngle instance of (cali- brated) cameras where the determinant of [22 does not vanish identically for all Aan Aisi due to the poly- nomiality (e.g.. see (53) check that this indeed holds by a computer calculation, generating numeri- cal instances of Pi and P. randomly. Thus the vanishing of the minor in (12) implies Asa (Aa -A1a) 0, whence A;a = Aia since Asa # An analogous calculation with (Aos T (n)) )(3) gives \ = Ann-
Step 2: Next consider the submatrix of (A@, (2)))) with column labels (j1,11), (1,21), (1,31), (j1,12), (1j.11) and row labels (1,1), (1,2), (1,3), (1,1), (i.2), where i.j E (2..... are distinct. looks like
(13)
Aja1*
A5a1*
Aya
Aja1*
X1s5*
Ajr
Ajar*
A1sy*1
with asterisks denoting entries of T7
(2)
Similarly to the previous case, the determinant of 13 must
be a scalar multiple of Ajaı (Aja1 A1sj) where the scale depends polynomially on P..P..P. By computer computation, we find that the scale is nonzero for random instances of cameras (alternatively, note the polynomial system in step 1 is special case of the present one). It the scale is generically nonzero, hence Aya = -A1y-- An analogous calculation with (YO, (()) gives Aay =
Step 3: Consider the submatrix of (AOs TT (2) with column labels (j1,11), (f1,31), (j1,12), (1k,11) and row labels (1,1), (1,2), (1.3). (i,1), (i.2), for i.j.k E (2.....m) distinct. It looks like
(14)
Aja Ajn
Aysi* Aja
Ajni
Aja*
A1a
Ajii*
Ajui*
A1a*
The determinant of (14 is scalar multiple of as before, is nonzero multiple generically (alternatively. note the polynomial system in step is special of the present one). We deduce A A1ik- An analogous calculation with (AO&T") )a)) gives Ası Aιaj-
A1aa). By direct computer computation
In particular, combining with step it follows X1a== = Aıji. because Ano = A = >ukj Aua -
Ayrı = Aijs- From this, step 1 and step 2, we have that the X-scale does not depend on the ordering its indices, provided there is among the indices.
18

---

Step 4: Consider the submatrix of (AQa (2) with column labels (j1,11), (51,21), (,1,1),, (i1,12), (1i,11) and row labels (1,1), (1,2), (1,3), (i,1), (i,2), for i.j (2...... distinct. It looks like
(15)
Ays1*
Ass1*
Aza*
A511*
A1a=
Ass1*
Ays1*
Ajs1*
Ajii*
A18
The determinant of (15) is scalar multiple of Ayu (A - Aist). By a direct computer computation,
it is nonzero multiple generically (alternatively, note the polynomial system in step is special case of the present one). We deduce λ1a = A18.
Putting together what we know so far, all A-scales with single 1-index agree. Indeed, this follows from Ara A,11 As51 Xış; so all A-scales with a single 1-index and two repeated indices agree, combined with Ajı = A1a and the last sentence of step 3. Cet R denote this common scale.
Step 5: Consider the submatrix of (AOa (")T")pp (2) with column labels (1i,11), (1i,21), (11,31), (1i,12), (1j,11) and row labels (1,1), (1,2), (1,3), (i,1), (i,2), for i,j E m2 distinct. It looks like
*
C*
*
*
C*
(16)
C*
C*
C#
C%
Xig+
As function of e and Auj the determinant of (16) is a scalar multiple of - (the second factor is present because corresponds to scaling the bottom two rows and rightmost column of 5 x 5 submatrix of ((2) each by c, which preserves rank deficiency). By direct computer computation, we find that the scale nonzero for random instance of P1. P..... therefore it nonzero generically. It follows e² Xas- An analogous calculation with "",,") (O,T")(3 gives c² -Ajji-
Step Consider the submatrix of AO,T")p) with column labels (1i,11), (11,21), (11,31), (1i,12), (ji,11) and row labels (1,1), (1.2), (1.3), (i,1), (i,2), for i,j (n)....m distinct. It looks like
*
*
C*
*
*
C*
(17)
jic*
C*
C*
C*
C*
Aja+t
Similarly the previous step, the determinant of (17) must be scalar multiple of c(c² Aza). By direct computer computation, it is nonzero multiple generically. We deduce e== =Aja.
Step 7: Consider the submatrix of (AO, T (2) columm labels (11,11), (11,21), (11,31), (11,12), (ik: 11) and row labels (1,1), (1,2), (1,3), (j,1), (j,2), for i.j. (2.....m) distinct. It looks like
#
*
C*
(18)
C*
C*
C*
C*
Xijk*
C*
C#
C#
C*
Dijk*
The determinant of (18) is scalar multiple of c(c² - Aes)). By a direct computer computation, it is a nonzero multiple generically (alternatively, note the polynomial system step 5 is special case of the present case). We deduce c² =Xisk.
At this point, by steps 5,6.7 we have that all X-scales with no 1-indices and not all indices the same must equal c². Combined with the second paragraph of step 4, this shows satisfies the property announced the start of the proof. Therefore the proof is complete.
A.5
Implementation details
A.5.1
Estimating trifocal tensors from three fundamental matrices
Given three cameras Pt. P2, Pa and the corresponding fundamental matrices F21, F32, we can calculate the trifocal tensor Tife using the following procedure detailed in [[] Specifically, from
19

---

F21 calculate an initial estimate of the cameras P. Then, P3 and P Fs should be skew-symmetric matrices. This gives 20 linear equations in terms of the entries Ps, which can be used to solve for the trifocal tensor. Note that there are no geometrical constraints when calculating P3, and there will be no guarantee the quality of the estimation.
A.5.2 Higher-order regularized subspace-constraing Tyler's estimator (HOrSTE) for EPFL
We describe the robust variant of SVD that used for the EPFL experiments in Section Numerically, it performs more stably and accurately than HOSVD-HT, yet it is an iterative procedure and each iteration requires SVD of the 3n 9n² flattening. This becomes computationally expensive when n becomes large and the number of iterations are also large. However, since the number of cameras for the EPFL dataset are below 20 cameras, the computational overhead is not too great.
In HOSVD, a low dimensional subspace is estimated using the singular value decomposition and taking the R,, leading left singular vectors for each mode-n flattening. The Tyler's M Estimator (TME) [0] is robust covariance estimator objective function
dimensional dataset {xr N.N C IRP. It minimizes the
N Eiog(e log(2 -- 2 +ogdet(EE)
D
min DEROED
(19)
such that Σ is positive definite and has trace 1. The TME estimator can be applied to robustly find an R. dimensional subspace by taking the Rn leading eigenvectors of the covariance matrix of TME. To compute the TME, [40] proposes an iterative algorithm, where
(20)
Ja
(E (
TME doesn't 't exist when D N. but regularized TME has been proposed by become
154 The iterations
1 D 1+a N (E(
I
&
(21)
1+a
where is regularization parameter, and I is the D x D identity matrix. TME does not assume the dimension of the subspace is predetermined. In the case when d is prespecified, [41] improves the TME estimator by incorporating the information into the algorithm and develops the subspace-constrained Tyler's Estimator (STE). For each iteration, STE equalizes the trailing D -d cigenvalues of the estimated covariance matrix and uses a parameter <<y< 1 shrink the eigenvalues. The iterative procedure for STE is summarized into 3 steps:
1. Calculate the unnormalized TME, Z z(²) -M (E(0))))(()
2. Perform the eigendecompossiiinn of ( = UK) (()) and set the trailing D eigenvalues as >> 1
3. Calculate ((k g(t) (L= (L)()))) which is the normalized covariance matrix. Repeat steps until convergence.
Similar to the regularized TME. STE can also be regularized to succeed in situations where there fewer inliers, and can improve the robustness of the algorithm. The regularized STE differs from STE in only the first step, which is replaced by
1 Calculate the unnormalized regularized TME, 2 1 D D Ita 2i=1
22
1ta
We apply the regularized STE to the HOSVD framework, and call the resulting projection the higher-order regularized STE (HOrSTE). It performed via the following steps:
1. For each n, calculate the factor matrices A, as the R,, leading left singular vectors from regularized STE applied to T.))-
2. Set the core tensor G as = A X2
x, AN.
20

---

A.6 Additional numerical results
In this section, we include comprehensive results for the rotation and translation errors for the EPFL and Photo Tourism experiments. [ contaiin all results for EPFL datasets. Table containss the location estimation errors for Photo Tourism. containsn the rotation estimation errors for Photo Tourism. In Table 4 we only report the rotation errors for LUD for all the methods that we compared against, as they are mostly the same since they used the same rotation averaging method.
Table I: EPFL synchronization errors. e,- is the mean rotation error in degrees, ey. is the median rotation emror in degrees. 6, is the mean location error, ég is the median location error. NREM(LUD) is NREM initialized with LUD and NRFM is randomly initialized. BATA(MLPS) is BATA initialized with MPLS.
Our
LUD
NRFM(LUD)
NRFM
BATA(MPLSS)
Dataset
62
é,
6,
E1
6,
6t
ét
FountainP
0.008
0.007
0.91 0.75
0,46
3.37
3.03
1.12
1.01
HerzP8
0.02
0.02
5.06 4.37
3.42
4.24
3.14
5.04
5.03
HerzP25
4.70
4.68 7.75 8.00
6.20
5.82
8.85
8.38
7.77
8.41
EntryP10
0.05
0.02 3.08
3.02
1.34
1.11
7.63
7.43
2.90
2.58
CastleP19
9.64 5.80 4.58
3.37
3.02
15.81
5.77
5.62
CastleP30
11.00 11.33 3.72
2.75
16.54
17.04
3.26
Table 2: EPFL synchronization errors. é, is the mean rotation error in degrees, é,. is the median rotation error in degrees. BATA(MLPS) is BATA initialized with MPLS.
Our
LUD BATA(MPLS)
Dataset
Cr
6r
6,
6r
er
Gr
FountainP1
0.09
0.08
0.05
0.05 0.06
0.05
HerzP8
0.12
0.12
0.34
0.44
0.39
HerzP25
2.01
1.11
0.18
0.26
0.23
EntryPI0
0.15
0.11
0.25
0.27
0.25
CastleP19
56.24
11.71
0.22
0.27
0.25
CastleP30
38.84
4.58
0.13
0.13 0.19
0.15
Table 3: Translation errors for Photo Tourism. n is the size after downsampling. Est. % is the ratio of observed blocks over total number of blocks. e, is the mean location error, é, is the median location error. NRFM(L) is NRFM initialized with LUD and NRFM(R) randomly initialized. The notation PR means that the dataset was further downsampled to match the two view methods. BATA is BATA initialized
with MPLS. We were not able to get results for our subsampled dataset for Piccadilly with MPLS.
Dataset
Our Approach
NRFM(L.)
LUD
NRFM(R)
BATA
dataset
Est. %
è,
è,
è,
è.
é
Piazza del Popolo
185
72.3
0.78
0.45
1.63
0.85
1.66
0.86
13.45 12.06
1.63
1.10
NYC Library
127
64.7
1.01
0.53
1,39
0.48
1.49
0.57
13.06 14.03
1.59
0.68
Ellis Island
194
70.3
9.56
7.73
19.31
16.97
20.71
17.96
26.08
26.38
23.63
22.50
Tower of London
130
34.1
4.15
2.66
3.26
2.49
3.54
2.51
49.99
47.33
2.70
2.26
Madrid Metropolis
190
35.9
18.93
15.53
1.91
1.19
1.94
1.20
31.48
24.02
3.33
1.72
Yorkminster
196
37.2
1.46
1.14
2.31
1.39
2.35
1.45
16.67
14.46
1.37
1.15
Alamo
224 94.3
0.62
0.28
0.53
0.31
0.53
0.31
7.68 10.04
0.55
0.33
Vienna Cathedral
197
97.8
0.73
0.33
2.96
1.64
3.15
1.79
16.08
14.76
6.16
2.18
Roman Forum(PR)
111 51.1
10.71
6.75
1.59
0.89
1.63
0.93
23.23
11.20
1.85
1.04
Notre Dame
214 96.6
0.57
0.34
0.38
0.21
0.38
0.21
6.87
4.75
1.02
0.26
Montreal N.D.
162 97.0
0.38
0.24
0.56
0.37
0.57
0.38
10.33
11.15
0.58
0.41
Union Square
144 28.6
5.64
3.99
4.31
3.76
4.85
4.38
9.59
6.69
5.77
4.83
Gendarmenmarkt
112
89.7
45.34
23.63
37.93
17.35
37.92
17.41
62.69
26.42
54.38
15.91
Piccadilly(PR)
169
55.4
0.73
0.39
3.68
1.90
3.71
1.93
13.55
13.34
21

---

Table 4: Rotation errors for Photo Tourism. N the total number of cameras. the size after down sampling. Est. % is the ratio of observed blocks over total number of blocks. é, is the mean rotation error; &, is the median rotation error. The notation PR means that the dataset was further down sampled to match the two view methods. We were not able to get results for our subsampled dataset for Piccadilly with MPL.S.
Our Approach
LUD
MPLS
dataset
N
n
Est. %
Er
9,
6,
é,
Er
Our Runtime (s)
Piazza del Popolo
307
185
72.3
1.26
0.61
0.72
0.43
0.69
0.41
13531
LiCrar
306
127
64.7
2.80
1.58
1,16
0.61
1.19
0.57
4465
Ellis Island
223
194
70.3
4.61
1.11
1.16
0.50
0.99
0.49
13816
Tower of London
440
130
34.1
2.28
1.31
1.63
1.28
1.66
1.37
4242
Madrid Metropolis
315
190
35.9
28.85
4.60
1.27
0.61
1.54
1.15
11764
Yorkminster
410
196
37.2
2.33
1.97
1.34
1.09
1.89
1.04
13115
Alamo
564 224
94.3
1.10
0.76
1.07
0.68
1.09
0.68
17513
Vienna Cathedral
770
197
97.8
0.74
0.46
0.40
0.28
0.39
0.28
12499
Roman Forum(PR)
989 111
51.1
11.86
3.39
0.40
0.28
1.07
0.65
2162
Notre Dame
547
214
96.6
0.78
0.50
0.67
0.43
0.68
0.43
17430
Montreal N.D.
442 162
97.0
0,50
0.35
0.49
0.32
0.49
0.31
7241
Union Square
680 144
28.6
20.70
5.29
1.82
1.34
2.00
1.56
4355
Gendarmenmarkt
655
112
89.7
22.95
15.24
18.42
10.25
17.42
8.41
2432
Piccadilly(PR)
1000
169
55.4
2.01
0.96
6.12
2.95
11230
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Please check Section 3 and 4 for the main claims of paper and the experimental results. An accurate summary of the contributions is found at the end of the introduction section, and also conveyed in the abstract.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long it clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Please check our conclusion in Section 5 The last paragraph describes the limitations of the work.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings,
22

---

model well-specification. asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to- to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicablle the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: Please see the proof' in Appendix A.3 A.2 A.4 and statements in Section 2
The statements are precise, and accompanied by complete proofs.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross-referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proof' can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Yes, mention the numerical details and processing of our algorithm in section Section[4[for each experiment. We also include code in the supplementary material with instructions on how to run them. Our code depends on other publicly available code. Instructions can be found in supplementary material.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible important, regardless of whether the code and data are provided or not.
23

---

If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (c.g., in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (c.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-souree models, it may be that access to the model is limited in some way (e-g., to registered users), but it should possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: Please feel free check our code in the supplementary material and the README.MD file for instructions. A public version will be available in the future.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https
/nipss.ccppubic//gg
for more details.
While we encourage the release of code and data, we understand that this might not be pos- sible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines Sttpaiideee/ooSuumiiiisseeeeeeee
for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyperpa- rameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
24

---

Answer: [Yes]
Justification: Please see our experiment details in Section In particular, we included the way we chose hyperparameter and specific numbers when applicable.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Though we didn't set a random seed for some experiments, there were insignificant differences between different runs of the method.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [Yes]
Justification: Please see our experiment details in Section
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary failed experiments that didn't make it into the paper).
25

---

9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics htttpp////aarrrpp...c///l///eaee
Answer: [Yes]
Justification: We only used open source code and have complied to the code of ethics. Please check code in supplementary material.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consideration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts the work performed?
Answer: [Yes]
Justification: Our method is focused general framework for tensor based structure from motion and we run experiments on open source datasets. No negative social impacts are related to work. Having tensor based synchronization method opens up research directions and could help apply structure from motion to develop applications where point correspondences are scarce.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our paper doesn't pose such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
26

---

Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging. and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e-g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We cited the authors whose code in our code, and respected all relevant licenses. We include links code in our submitted code well. Please refer the code and the experiment details.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of the package should be provided. For popular datasets, jpaperswi paperswithcode thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information not available online, the authors are encouraged to reach out to the asset's i creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We provide code for our methods and instructions for running the methods in the supplementary material.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsoureing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: We do not involve crowdsourcing research with human subjects.
27

---

Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in collectin, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects. and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our paper doesn't involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
28


Reviews:
[{"review_id": "bPrwvZPBEj", "reviewer": "Reviewer_8uUu", "summary": "The paper presents a novel method for camera synchronization using a tensor-based approach, specifically focusing on the block trifocal tensor. The authors discovered that the block tensor of trifocal tensors has a (6, 4, 4) core tensor in the Tucker factorization (HOSVD), independent of the number of cameras under mild constraints. The authors propose a Higher-Order Singular Value Decomposition (HOSVD) framework with imputation techniques to handle missing data and achieve robust camera synchronization. The methodology is tested on various datasets, demonstrating competitive performance in terms of translation and rotation errors compared to existing methods.", "questions": "Notation Clarification: Can the authors provide a more detailed and consistent explanation of the tensor notations used, particularly for the trifocal and quadrifocal tensors?\nAlternative Imputation Techniques: Have the authors considered other imputation methods for handling missing data? How do these compare in terms of robustness and accuracy?\nAlternative Rotation Parameterization Techniques: Have the authors considered alternatives for the rotation parametrization? How do these compare in terms of reconstruction accuracy of the camera rotations?\nMissing Visualization of Results: Have the authors considered more visualizations that illustrate the results of the camera synchronization and the accuracy of the imputed data. Examples include visual comparisons of camera poses against ground truth and multi-view reconstruction results from the estimated camera poses?\nOutlier Handling: What specific steps are taken to identify and mitigate the impact of outliers in the data? How much do outlilers influence the result anyway when using HOSVD?", "limitations": "The authors have acknowledged some limitations, such as the scalability of the block trifocal tensor with the number of cameras. Additional limitations that should be addressed include:\n\n    Robustness to Noise: The method's sensitivity to noise and outliers should be discussed in more detail, along with potential mitigation strategies.\n    Experimental Scope: The experiments are limited to specific datasets. Broader testing on more diverse datasets would strengthen the claims.\n    Computational Efficiency: The computational demands of the proposed method should be analyzed in more detail, especially for large-scale applications.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The paper contributes significantly to the field of multi-view geometry and camera synchronization through the introduction of a tensor-based approach using the block trifocal tensor and HOSVD. The originality of applying a (6, 4, 4) core tensor in the Tucker factorization and the robustness provided by the STE are noteworthy. \n\nThe technical claims are generally sound, supported by experimental evidence and detailed derivations.\n\nThe theoretical parts of the paper are well-presented, providing clear and detailed explanations of the methodology and derivations.", "weaknesses": "The novelty could be further strengthened by exploring and comparing additional tensor decomposition methods and imputation techniques. Addressing scalability concerns and providing a more detailed comparison with existing methods would also enhance the contribution.\n\nThe robustness of the imputation method for missing data, which involves using small random entries, needs further validation. This approach might introduce biases, and its impact on the final results should be carefully evaluated. Additionally, while the use of Subspace-constrained Tyler’s Estimator (STE) is innovative, its integration and performance, especially in handling outliers and noise, require more comprehensive analysis and justification.\n\nCertain sections are dense and could benefit from additional clarity, particularly the tensor notations and some derivation steps. The paper would also be significantly improved by including more visualizations to illustrate the results of camera synchronization, such as comparisons of estimated camera poses against ground truth and multi-view reconstruction results. The lack of these visual aids makes it challenging to fully grasp the practical impact of the proposed method.\n\nHandling of Rotations: The discrepancy in performance between the translational and rotational parts of the camera poses might be related to the rotation parameterization used. The paper employs robust rotation averaging and estimation methods but does not specify the parameterization of rotations. Considering parameterizations such as quaternions, Lie algebra representations with the exponential map, or the Cayley transform could improve the accuracy of the rotational estimates and enhance the overall synchronization performance.\n\nImputation Method: The imputation of missing data with small random entries might introduce biases. Alternative imputation techniques, such as Higher-Order Alternating Least Squares (HOALS), Tensor Nuclear Norm Minimization (TNNM), or Expectation-Maximization (EM) for tensors, should be considered for potentially more robust and accurate results.\n\nHandling of Outliers: The method's robustness to outliers could be further enhanced by integrating advanced outlier detection techniques such as Robust Principal Component Analysis (RPCA), RANSAC, the Huber loss function, or autoencoder-based approaches. These techniques could provide more robust results by effectively separating or mitigating the influence of outliers on the tensor decomposition process.\n\nSensitivity Analysis: The paper does not provide a sensitivity analysis to show how the method performs under different conditions, such as varying levels of noise, different amounts of missing data, or different types of outliers. This analysis would demonstrate the robustness of the method under various real-world conditions.\n\nVisualization of Results: The paper could benefit from more visualizations that illustrate the results of the camera synchronization and the accuracy of the imputed data. This would help in understanding the practical impact of the proposed method. Examples would be camera poses compared to GT, multiview reconstructions results from the estimated camera poses.\n\nThe paper is technically solid and presents a valuable contribution to the field. However, addressing the identified weaknesses and providing additional validation for the imputation method and scaling factor calculation would significantly strengthen the work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank you for your generally positive feedback, and the suggestions for further research.\n\nQ1: Notation Clarification\n\nResponse: We will better clarify the notation in the published version. We intentionally didn't distinguish between contravariant and covariant components to avoid cluttered notation. For a block trifocal tensor $T^n$, we label the i,j,k block as $T^n_{ijk}$, where i,j,k correspond to blocks in the first, second, and then third mode. When we refer to a general trifocal tensor T, we also label it with subscripts to denote the elements of T.  The context should be clear throughout the paper such that this doesn’t cause confusion. $T_{abc}$ denotes the a,b,c element in a single tensor T. Thus, $T_{abc}$ would represent the trifocal tensor defined as $[T_{1bc}, T_{2bc}, T_{3bc}]$ following the conventions in the canonical notation in Hartley and Zisserman’s book. When we are denoting the a,b,c element of the i,j,k block, we denote it as $(T^n_{ijk})\\_{abc}$. For a quadrifocal tensor, we denote the a,b,c,d element as $T_{abcd}$, where a,b,c,d denote the indices in the first, second, third, and fourth modes respectively, corresponding to the first, second, third, and fourth cameras. \n\nQ2: Alternative Imputation Techniques:\n\nResponse: We adopt the strategy of imputing with the rank truncated tensor because it is the cheapest and easiest imputation strategy, since we are already computing the HOSVD in the synchronization algorithm. We think ALS would represent a polishing of HOSVD, in part because it’s often initialized with HOSVD which already achieves sqrt(3) quasi-optimality for Tucker approximations, see [33]. It remains to be seen whether the extra computation each iteration would improve the final accuracy. Also, tensor nuclear norm minimization may introduce a potentially expensive computation overhead. \nRegarding the initial imputation using small random entries, we have seen very small differences with and without this initial imputation. In a small portion of the synthetic experiments, we have seen a small advantage of imputing with small random entries instead of leaving them as zeros. But in most of the real datasets, we see little to on effect of this initial imputation.\nAs mentioned in the common response above, the overall emphasis of this paper is to show that the proposed theoretical ideas can work in practice with a simple implementation. It would be up to future work to investigate the effect of refined imputation techniques and initialization techniques in our synchronization framework, especially in scenarios with very low completion rate, and to what extent refined techniques are computationally feasible.  We thank the reviewer for giving us a list of algorithm variations that could be explored in future work.\n\nQ3: Alternative Robust Rotation Parametrization:\n\nResponse: We directly work with rotations as 3x3 special orthogonal matrices, and do not require any parameterization of them.  The factorization involves a factor matrix of calibrated cameras, so that the left three columns of the factor matrix is a block of rotations. In the actual synchronization step, the Tucker factorization only determines this factor matrix up to a 4x4 global transformation, so that we may no longer have exact rotations in the factor matrices. It is thus not clear how alternative robust rotation parameterizations would be applicable in our work. \n\nQ4: Missing Visualizations of Results: \n\nResponse: For an example of the visualization of camera poses for Fountain P11 of the EPFL dataset, see Figure 1 in the global rebuttal PDF with figures and tables.  We plan on adding point clouds and camera pose comparisons in the supplementary material given the acceptance of the paper. \n\nQ5: Outlier Handling:\n\nResponse: In our experiments, we have noticed that outliers do have an influence on the synchronization. In the supplementary material, we have included a robust version of Higher Order SVD, called the Higher Order Regularized STE. Essentially, we replace the normal SVD operation in HOSVD with a robust subspace recovery operation using regularized STE and call it HO-rSTE. In our EPFL experiments, we run HO-rSTE and have achieved higher accuracy than the normal HOSVD in most cases. To see a small sensitivity analysis, please refer to Table 3 in the PDF of figures and tables, where the noise levels, completion rate, and synchronization result is displayed.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "OtD3krUgqk", "reviewer": "Reviewer_dwhb", "summary": "This paper proposes a method to recover rotation and translation from the trifocal tensor, which encodes the three-view geometric parameters. The basic idea is based on Tucker factorization of the trifocal tensor, revealing a low multilinear rank of (6, 4, 4), independent of the number of cameras. A synchronization algorithm based on higher-order SVD is then introduced. The proposed method has been compared with existing methods and demonstrated certain benefits.", "questions": "The balance between rotation and translation recovery suggests that the proposed method is better for translation recovery, while existing methods excel in rotation recovery. Are there any explanations for this? Additionally, if we apply optimization using points, what are the final results?\n\nIn general, errors originate from point correspondences. The paper presents statistics using SIFT features, but do these statistics hold if we use modern learning-based features?\n\nLastly, do we achieve better results than with two-view geometry?", "limitations": "The paper provides a discussion of its limitations in the conclusion section, addressing most of the concerns. However, the paper is somewhat difficult to read and follow.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "When we have point correspondences in three views and estimate the trifocal tensor based on three-view geometry, the motion parameters are generally more accurate than those obtained from two-view geometry. Motivated by this, the trifocal tensor serves as an important alternative to two-view geometry. The derivation is based on a noise-free case, and the paper demonstrates that the rank constraint provides sufficient information for camera motion recovery.\n\nThe proposed method was tested on two datasets, EPFL and Phototourism, and was shown to outperform some existing methods on certain sequences. The main advantage lies in the accuracy of translation estimation.", "weaknesses": "The paper claims, 'We observe that the algorithm performs better in the calibrated setting, and since the calibration matrix is usually known in practice, we restrict our scope of experiments to calibrated trifocal tensors.' When focusing on the calibrated trifocal tensor, there are some algorithms that can directly obtain the rotation and translation from four points in three views, e.g., 'Nister et al. Four points in two or three calibrated views: Theory and practice. IJCV 2006.' Using such algorithms, we do not need to decompose the trifocal tensor for the calibrated case, making decomposition more relevant for the uncalibrated case.\n\nIn the main paper, only comparisons for the translation errors are presented, with rotation errors shown in the supplemental material. Based on the supplemental results, it appears that the proposed method does not perform well for rotation estimation. The derivation and rank constraint are based on the noise-free case. Conducting synthetic evaluations with noisy data could help readers understand the recovered rotation and translation accuracy in the presence of increasing image noise.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank you for your time in reviewing our manuscript, and hope that you will consider our rebuttal to your concerns.\n\nClarification for the reviewer\n\nWe want to stress that our paper is about synchronizing (or denoising) a set of multiple noisy trifocal tensors coming from n views, and subsequently recovering accurate estimates of the n camera matrices. It is not about the estimation of the individual trifocal tensors. For this reason, we work with the block trifocal tensor which is a 3n x 3n x 3n tensor. Our contribution is suggesting an alternative to methods like incremental SfM and bundle adjustment over n views.\n\nDisagreement with claims made by the reviewer\n\nIt is mentioned that “... trifocal tensor … motion parameters are generally more accurate than those obtained from two-view geometry”. In our experience, this is not true. We noticed that trifocal tensors estimated using the motion parameters obtained from two-view geometry are more accurate than trifocal tensors estimated directly from point/line correspondences prior to local bundle adjustment. This is well-known to practitioners in the area and is recorded in reference [40] of our work. The motivation of our work is not because trifocal tensors are easier to estimate, but that in theory they hold more information than fundamental matrices, especially with respect to the relative translation sizes [1]. However to access this information, we need a synchronization method with strong denoising properties, since the individual estimated trifocal tensors tend to be noisy. Our main contribution is the theoretical development of new low-rank constraints that enable such a synchronization framework for trifocal tensors. \n\nSecondly, a paper is cited and it is stated that we can get rotation and translations from three calibrated views, therefore there isn’t a need to work with tensors. Though we agree that the referenced algorithm in NS06 (Nistér and Schaffalitzky, IJCV, 2006) is theoretically attractive, it is solving a hard and possibly unstable algebraic problem, and is not practical. For example, the errors reported in Fig. 26 in NS06 suggest that the translation vector discrepancy can go up to 40 degrees. Likely, this would make NS06 not directly usable. Also, we couldn’t find a publicly available implementation of NS06, nor of similar papers on calibrated three-view geometry. Another point we wish to stress is that if we were to work directly with rotations and translations from three-view geometry, we would face a non-standard synchronization problem where relative measurements occur across triangular edges. One could run rotation and translation averaging on the simple averages, yet it wouldn’t fully use the information. On the other hand, with our new low-rank constraint and decomposition of the block tensor, we have shown that we can use the three-view information effectively via trifocal tensors. Overall we believe this gives compelling reasons to use the decomposition of the block trifocal tensor.\n\nThirdly, the review claims that our work is more relevant to the uncalibrated cases, rather than the calibrated case on which our experiments focus.  It is relevant to both cases.  We are not aware of any successful SfM pipeline that fully incorporates three-view geometry in either the calibrated or uncalibrated case.  Our experiments focused on the calibrated case to give a more straightforward demonstration of the theoretical framework.  Another reason is that our work parallels the CVPR 2017 spotlight paper [18]. The rank constraints developed in that paper are applicable to both calibrated and uncalibrated settings, yet they focus solely on the calibrated setting in their demonstrations. Follow-up works extended the algorithm to the uncalibrated setting [20].\n\nWeakness: Synthetic experiments with noise levels. \n\nWe have conducted synthetic experiments with different noise levels and report the results in Table 3 and Figure 1 in the attached PDF. Due to limited space, we can’t include too many details, but we will add an extensive analysis in the supplementary material if accepted. We can see that our algorithm can reasonably handle 20% noise, which is quite large compared to the error in many datasets. \n\nQ1: Explanation of better translation recovery, and on “optimization using points”\n\nAs described in [1] p386, trifocal tensors directly constrain the relative translation between the three cameras which fundamental matrices do not, so it is reasonable to achieve better translation recovery.  From our experience, the rotation quality depends on the quality and density of the trifocal tensor estimations. When we have high quality and high density, we can achieve good synchronization results for both rotation and translation. \n\nIt is unclear to us what “optimization using points” refers to. If it means bundle adjustment, we prefer to not use bundle adjustment in global methods. First for rigorousness we like to avoid it, as bundle adjustment has no guarantee regarding the quality of the reconstruction and requires a good initialization. Second, we want to be fair when comparing with other global methods, specifically [18]. \n\nQ2: Use of modern learning-based features.\n\nWe agree with the reviewer that the point correspondences are important. We applied a very recent work, Gluestick (Pautrat et al., ICCV, 2023), for feature matching on the EPFL dataset. We include new results for the synchronization in Tables 4 and 5 in the attached PDF. We still see an advantage of our algorithm over the two view methods we compared against for dense graphs. \n\nQ3: Better results than with two-view geometry? \n\nYes, especially in location estimation. Note that our two-view analog, [18], uses the rotations obtained by LUD and does not obtain them by synchronizing essential matrices, so to compare with [18] one should only look at the results of translations.  Please note that all of our comparisons are against two-view methods.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gDiHYVJron", "reviewer": "Reviewer_pYrN", "summary": "The paper studies the characterization of the block tensor of trifocal tensors. The paper shows that under the assumption that the scales are known and the block tensor is complete, the global camera parameters can be extracted using Tucker factorization. Since those assumptions don't apply to real-world problems, the authors suggest an iterative algorithm for estimating the scales and completing the block tensor.\nEven though the paper's contribution to real-world applications is limited in terms of runtime, number of input images, and accuracy, in my opinion, it is an important paper due to its contribution to our understanding of multiple-view geoemtry.", "questions": "Do your results include a global bundle adjustment step as post-processing?\nTable 3 in the appendix doesn't include Bold notation.", "limitations": "Yes, the authors mentioned their runtime and dataset size limitations.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "The papers suggest a novel approach for global camera pose estimation, an important and challenging task in computer vision.\nThe suggested algorithm is based on solid theory and contributes to our understanding of trifocal tensors.", "weaknesses": "The main weakness of the paper is its contribution to real-world applications in terms of runtime, accuracy, and input size.\nDue to the usage of block trifocal tensors, the algorithm is limited in the number of input cameras (up to 225), and its runtime is longer than most baselines.\nThe accuracy presented by the suggested algorithm is low. The rotation error for Phototourism is higher for every scene except Piccadilly. In addition, a comparison to more recent works for global pose recovery is missing, e.g. [18, 19, 20] mentioned in the paper, and even deep-based methods such as Neurora, PoGO-Net, ESFM, and GASFM.\n\nThe authors mentioned, \"There are many situations where accurate point correspondences are in short supply but there is a plethora of clear and distinct lines.\" However, they didn't provide any examples of such a situation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank you for your generally positive feedback.  \n\nQ1: The main weakness of the paper is its contribution to real-world applications in terms of runtime, accuracy, and input size. Due to the usage of block trifocal tensors, the algorithm is limited in the number of input cameras (up to 225), and its runtime is longer than most baselines. \n\nResponse:  As for all higher order methods, the runtime and scalability may all be more challenging than lower order methods. Our tensor based synchronization is no exception. We have included new results of distributedly synchronizing subproblems and merging the results on Photo Tourism in the attached PDF with figures and tables. As we can see, using a distributed synchronization approach may cut runtimes of some datasets by more than 10 times, making the runtime comparable to [18], and without sacrificing too much of the synchronization quality. We refer to Table 1 in the PDF of figures and tables for details. This suggests that with enough computing power, we may run larger datasets with faster speeds. However, note that our algorithm can’t handle very sparse or loosely connected graphs. The solution to that is beyond the scope of this paper. \n\nQ2: The accuracy presented by the suggested algorithm is low. The rotation error for Phototourism is higher for every scene except Piccadilly. In addition, a comparison to more recent works for global pose recovery is missing, e.g. [18, 19, 20] mentioned in the paper, and even deep-based methods such as Neurora, PoGO-Net, ESFM, and GASFM.\n\nResponse: We ran some more experiments using modern learning based feature detection/matching algorithms. The results are included in Tables 4 and 5 in the PDF of figures and tables. We can see that though our rotation estimation is not strong, we have better location estimations compared to two view methods, including LUD, NRFM, and BATA initialized with MPLS, in many of the tested EPFL / Photo Tourism datasets. Our algorithm is especially strong in dense graphs with accurate estimates (such as Fountain P11 and Entry P10). \n\nIn our experiments, we did compare against the CVPR 2017 spotlight paper [18] (abbreviated as NRFM and referenced as [18] in the manuscript). Our work is an interesting extension of [18], where the analogue of the constraints for the two view case has been discovered for the three view case. [18] has been followed up with many interesting developments such as references [19] and [20] in the manuscript, and have been able to improve gradually. We do not claim that our algorithm is superior over SOTA algorithms, and our main focus is to develop the novel theory and compare against the closest analogue [18]. We believe that with further developments, the tensor synchronization algorithm has potential to become state of the art.  \n\nQ3: The authors mentioned, \"There are many situations where accurate point correspondences are in short supply but there is a plethora of clear and distinct lines.\" However, they didn't provide any examples of such a situation.\n\nResponse: For a specific example where accurate point correspondences are in short supply but lines are abundant, we refer to datasets referenced in Liu, S., Yu, Y., Pautrat, R., Pollefeys, M. and Larsson, V., 3D  line mapping revisited, CVPR 2023, in particular, the stairs dataset in 7 scenes and other indoor datasets. We have also seen pictures of agricultural fields, where there are no clean point correspondences, but just lines of crops. Point based SfM methods have trouble with these images. \n\nQ4: Do your results include a global bundle adjustment step as post-processing? Table 3 in the appendix doesn't include Bold notation. \n\nResponse: We do not include a global bundle adjustment step as post-processing. We prefer to not use bundle adjustment in global methods. First for rigorousness we like to avoid it, as bundle adjustment has no guarantee regarding the quality of the reconstruction and requires a good initialization. Second, we want to be fair when comparing with other global methods. Lastly, thank you for the reminder of the lack of bold notation in one of the tables which will be fixed in the final version.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DXYqgfvh2Y", "reviewer": "Reviewer_fgc4", "summary": "The paper proposes a camera pose synchronization method based on trifocal tensors. The method first estimates trifocal tensors given a set of calibrated images. A HOSVD runs on the trifocal tensors to project them into a set of tensors with multilinear rank (6, 4, 4). The edge scales are then obtained from projected tensors.", "questions": "- L137 The scales are fixed to what?\n- Please try re-running some experiments with E matrices obtained from PoseLib or GC-RANSAC. Maybe, it would improve the accuracy.", "limitations": "Discussed.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The paper proposes a strong theoretical work for trifocal tensor synchronization.", "weaknesses": "I guess this is the case when the weak experiments are overwhelmed by the strong theory. \nI propose accepting the paper since I believe the theoretical part of the paper will be useful for the community. \nHowever, I don't think the method in its current form can compete with SOTA SfM methods. \n\nWeaknesses in the experiments:\n- The EPFL dataset (I used to know it as the Strecha dataset) is extremely simple, with all recent SfM methods having a few cm errors in the end. The fact that the proposed method fails on CastleP19 and CastleP30 shows that the proposed method does not really work in practice. CastleP19 or CastleP30 are easy with lots of features and, thus, accurate essential matrices. \n- I welcome the experiments on the PhotoTourism dataset, but the baselines used in the paper do not really allow me to judge how the method works. LUD is an old method, significantly outperformed by BATA. Also, it is unclear what rotation averaging method do the authors use. While LUD is a translation averaging method, as I remember, it also has some rotation averaging in their code, which is actually not particularly accurate. The good baseline would be rotation averaging from the Theia library (alternating IRLS + L1) and BATA translation averaging.\n- \"We observe that the algorithm performs better in the calibrated setting, and since the calibration matrix is usually known in practice, we restrict our scope of experiments to calibrated trifocal tensors\". While I know this is often done in global SfM papers, it goes very much against the SfM goals. For example, the authors can only apply their method on the PhotoTourism dataset since someone has run Bundler/COLMAP beforehand to get camera intrinsics, making it pointless to run another SfM afterward. I guess the proposed method fails entirely without calibration otherwise the authors would have shown something. Am I correct? \n- Note: I would not use MATLAB's built-in RANSAC. Use PoseLib or GC-RANSAC. It will likely improve the accuracy of the proposed method as well, given that the relative poses become significantly more accurate. \n- The method is extremely slow. Theia runs 1-2 orders of magnitude faster while being more accurate. \n\nMinor things:\n- L81 \"projection of X onto the image\" -> \"projection of X into the image\"\n- Missing citation for SfM with lines [a]\n\n[a] Liu, S., Yu, Y., Pautrat, R., Pollefeys, M. and Larsson, V., 2023. 3d line mapping revisited. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (pp. 21445-21455).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank you for the encouraging comments regarding our theory, which indeed is the main contribution of this work.  We also appreciate the observations regarding our experiments. \n\nQ1. The EPFL dataset (I used to know it as the Strecha dataset) is extremely simple, with all recent SfM methods having a few cm errors in the end. The fact that the proposed method fails on CastleP19 and CastleP30 shows that the proposed method does not really work in practice. CastleP19 or CastleP30 are easy with lots of features and, thus, accurate essential matrices.\n\nOur initial experiments were run with SIFT features, and we have now tried experiments using a modern learning based feature detection/matching algorithm, GlueStick. We also used the GC-RANSAC implemented in OpenCV to calculate the essential matrices. We compared with two-view methods, and can see an advantage on 3 of the EPFL datasets. We have also been able to run Castle P19 and P30 with the new features, yet we noticed that though there are abundant features, the essential matrix and trifocal tensor estimations contained a fair amount of poor estimations. The reason is that the dataset contains many repetitive features, and also the trajectory is basically a circle, so that there are many views that don’t overlap but have matched features, which makes the essential matrix estimation difficult. Our algorithm also doesn’t work very well on such datasets as the completion rate is low. Currently our main advantage is in dense graphs. \n\nQ2: I welcome the experiments on the PhotoTourism dataset, but the baselines used in the paper do not really allow me to judge how the method works.…  The good baseline would be rotation averaging from the Theia library (alternating IRLS + L1) and BATA translation averaging.\n\nWe thank you for the acute observation. The rotation averaging method in the LUD pipeline is an iterative application of the seminal rotation averaging method [8]. We have tried implementing the rotation averaging method from Theia, yet have not been able to complete the experiments due to the limited time and the offsets we experienced when setting up the local C++ environment for Theia to run. We have been able to apply another SOTA rotation averaging method, MPLS [9], and perform translation averaging with BATA. Table 2 in the attached PDF of figures and tables contains results for a few typical Photo Tourism datasets. We will update our baseline to the suggested alternating IRLS + L1 and BATA upon acceptance of the paper in the supplementary material. The general takeaways from the experiments are as before.\n\nQ3: While I know this is often done in global SfM papers, it goes very much against the SfM goals. For example, the authors can only apply their method on the PhotoTourism dataset since someone has run Bundler/COLMAP beforehand to get camera intrinsics, making it pointless to run another SfM afterward. I guess the proposed method fails entirely without calibration otherwise the authors would have shown something. Am I correct?\n\nOur theory of the low Tucker rank constraint does apply to the uncalibrated case.  That said, we have noticed that the application of the algorithm in the uncalibrated version is more difficult, as the algorithm  appears more sensitive to noise and completion rate in the uncalibrated case. However, we still believe that our current work has developed useful theory for the synchronization of trifocal tensors, and the current algorithm is still relevant to both cases. For reference, our work is an extension to the CVPR 2017 spotlight paper [18]. The rank constraints developed in their paper are applicable to both calibrated and uncalibrated settings, yet they focus solely on the calibrated setting in their experiments. To have a fair comparison, we follow their setting and only run experiments for the calibrated case. Similar to [18], our work focuses on theoretical development and opens up opportunities for further work to succeed in uncalibrated settings using the constraints we developed. But we feel this is beyond the scope of this manuscript.  We note that follow-up works of [18], such as [19] for the calibrated setting, and then [20] for the uncalibrated setting, did successfully extend the algorithm to be applicable in the uncalibrated setting, and hope that a similar succession of progress will stem from our work.\n\nQ4: Note: I would not use MATLAB's built-in RANSAC. Use PoseLib or GC-RANSAC. \n\nThank you for the suggestion. We have included results calculated using GC-RANSAC on the EPFL datasets in the attached PDF with figures and tables. The relative poses are significantly more accurate, and we have achieved much better synchronization results. \n\nQ5: The method is extremely slow. Theia runs 1-2 orders of magnitude faster while being more accurate.\n\nAs for all higher order methods, the runtime and scalability will be more challenging than with lower order methods. Our tensor based synchronization is no exception. As mentioned, we have included new results of distributedly synchronizing subproblems and merging the results on Photo Tourism. We refer to Table 1 in the PDF of figures and tables for details. \n\nQ6: L137 The scales are fixed to what?\n\nSince projective camera matrices are defined up to a scale, what we meant in L137 is that for the development of the rank constraint, we fix the scale to any real number. As long as it remains fixed, we will have a (6,4,4) multilinear rank. One of the main objectives of the synchronization algorithm is to retrieve these scales. The set of scales to be retrieved is not a sole solution; this is the role alpha, beta and gamma play in our Theorem 2. \n\nQ7: L81 \"projection of X onto the image\" -> \"projection of X into the image\", Missing citation for SfM with lines [a]\n\nWe appreciate the suggestion for our phrasing, and thank the reviewer for the citation of this recent development.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We would first like to thank all reviewers for all their valuable comments and time. There are some common issues brought up by you, and we would like to respond to some of them in this common rebuttal.  

1. We would like to clarify the intent of this work. Our main goal is theoretical: we would like to develop constraints on sets of noisy trifocal tensors that could be used to synchronize trifocal tensors accurately. We believe that trifocal tensors have the potential to improve SfM pipelines, especially for location estimation given the fact that trifocal tensors encode the relative scales of translations where fundamental matrices only encode the relative direction.  However, individual trifocal tensor estimates are often noisier than essential/fundamental matrix estimates. Indeed, we are unaware of any successful implementation for SfM, which fully incorporates trifocal tensors.  In our opinion, what appears to be missing are strong constraints on sets of noisy trifocal tensors, whose enforcement can be the basis of synchronization methods.  Our work’s main contribution is then fundamental: we introduce a new mathematical property for sets of trifocal tensors (Theorem 1) and demonstrate the sufficiency of this property to determine n camera poses despite scale ambiguities (Proposition 2 and Theorem 3).  For the synchronization procedure itself, we chose the most straightforward and simple procedures that enforce the low-rank constraints to have a basic setup for the experiments for clarity of the framework.  We sincerely hope the theoretical properties that we discovered and the trifocal tensor synchronization framework that we introduced can spark further investigation and interest in synchronization using trifocal tensors among the community.


2. The scalability of our algorithm: It is always true that tensor computations are more expensive than matrix computations, thus it is natural that our tensor synchronization algorithm is slower compared to two view methods. However, the synchronization problem can be solved in parallel.  Our tensor-based method could be significantly accelerated using parallelization.  To demonstrate this, we have developed a very simple distributed synchronization strategy and included the results on Photo Tourism in Table 1 (attached). The distributed procedure involves the following steps. First, partition the dataset randomly into k parts, so that each partition has roughly ~60 cameras. Then label the partitions and add 2 x k cameras from the (i+1)th partition into the ith partition, where the added cameras from the (i+1)th partition are densest connected cameras to the ith partition. Third, synchronize each sub dataset using the tensor synchronization algorithm. Finally, compute a homography using the overlapping cameras and bring all subproblems to the same projective frame to achieve a large reconstruction. There are more clever strategies to partition a hypergraph and would be worth investigating in the future. The results from our distributed approach on the same Photo Tourism datasets suggest that with almost no loss of accuracy, we can speed up the computation of some datasets by more than 10 times. Essentially, the computation speed would be limited by the size of each subproblem when enough cores are present. Due to limited space, we only include a subset of results in Table 1 in the global rebuttal PDF with figures and tables, and can include an extensive table in the supplementary material upon acceptance of the paper. 

3. We have tested our algorithm against two-view global synchronization methods using more SOTA algorithm components in the pipeline, as suggested by some reviewers. We completed a new set of experiments on the EPFL dataset using a modern learning based feature detection/matching algorithm, GlueStick. We estimated essential matrices using GC-RANSAC through the Python wrapper of OpenCV. We also added comparisons with BATA (initialized with another SOTA method MPLS [9]) for EPFL datasets and selected datasets of Photo Tourism.  Overall we have similar observations as before: our algorithm performs well on dense and clean graphs (such as Fountain P11 and Entry P10) compared to the two-view synchronization methods. 

4. Global Rebuttal PDF of figures and tables description: 
Results for the distributed synchronization to speed up computations (Table 1), new baseline results using MPLS +BATA on Photo Tourism (Table 2), a small sensitivity analysis to understand the effect of noise and completion rate of our algorithm (Table 3), results of our tensor synchronization reran on EPFL datasets with the Python opencv implementation of modern learning based feature detection/matching algorithm GlueStick (Table 4), and results of the two-view methods on EPFL datasets using GlueStick and GC-RANSAC (Table 5). We also show the convergence of a scenario of the sensitivity analysis (Figure 1), and a visualization of the estimated versus ground truth camera poses for Fountain P11 in EPFL (Figure 2).

Meta-review: This paper has received mixed reviews, with three reviewers providing positive feedback and one offering a negative assessment. The primary contribution of the paper lies in its theoretical development, which demonstrates how camera motion can be computed from a set of trifocal tensors using rank constraints and applying Higher-Order Singular Value Decomposition (HOSVD). Unlike traditional synchronization approaches that rely solely on two-view constraints, this novel approach has been acknowledged by all reviewers.

However, some questions and concerns were raised regarding the experiments, particularly in relation to how well the proposed approach performs compared to the state-of-the-art methods. Given that this is a well-studied problem, the expectation to outperform state-of-the-art Structure from Motion (SfM) methods is less critical. The paper introduces an alternative approach grounded in new theory for trifocal tensors, which is a valuable contribution in its own right.

The AC concurs with Reviewer fgc4 that the theoretical contribution presented in this paper has the potential to be beneficial to the research community. Therefore, acceptance is recommended.
Decision: Accept (poster)