Sensitivity in Translation Averaging
Authors: Lalit Manam
Venu Madhav Govindu
Venue: NeurIPS 2023 poster (2023)
Keywords: sensitivity
translation averaging
structure from motion
3D computer vision
TL;DR: Skewed triangles lead to unreliable translation estimates, so remove such triangles.

Abstract: In 3D computer vision, translation averaging solves for absolute translations given a set of pairwise relative translation directions. While there has been much work on robustness to outliers and studies on the uniqueness of the solution, this paper deals with a distinctly different problem of sensitivity in translation averaging under uncertainty. We first analyze sensitivity in estimating scales corresponding to relative directions under small perturbations of the relative directions. Then, we formally define the conditioning of the translation averaging problem, which assesses the reliability of estimated translations based solely on the input directions. We give a sufficient criterion to ensure that the problem is well-conditioned. Subsequently, we provide an efficient algorithm to identify and remove combinations of directions which make the problem ill-conditioned while ensuring uniqueness of the solution. We demonstrate the utility of such analysis in global structure-from-motion pipelines for obtaining 3D reconstructions, which reveals the benefits of filtering the ill-conditioned set of directions in translation averaging in terms of reduced translation errors, a higher number of 3D points triangulated and faster convergence of bundle adjustment.

Sensitivity in Translation Averaging
Lalit Manam
Venu Madhav Govindu Indian Institute Science Bengaluru, India 560012 venug@iisc. ac.
Indian Institute of Science Bengaluru, India 560012 lal i tmanam@i isc. ac in
Abstract
In 3D computer vision, translation averaging solves for absolute translations given a set of pairwise relative translation directions. While there has been much work robustness outliers and studies the uniqueness of the solution, this paper deals with distinctly different problem of sensitivity in translation averaging under uncertainty. We first analyze sensitivity in estimating scales corresponding to relative directions under small perturbations of the relative directions. Then, we formally define the conditioning of the translation averaging problem, which assesses the reliability of estimated translations based solely on the imput directions. We give sufficient criterion ensure that the problem is well-conditioned. Subse- quently, we provide an efficient algorithm to identify and remove combinations of directions which make the problem ill-conditioned while ensuring uniqueness of the solution. We demonstrate the utility of such analysis in global structure- from- motion pipelines for obtaining 3D reconstructions, which reveals the benefits of filtering the ill-conditioned set of directions in translation averaging in terms of reduced translation errors, a higher number 3D points triangulated and faster convergence of bundle adjustment.
Introduction
The goal of the translation averaging problem is to recover absolute translations given a redundant set of pairwise relative translation directions. This problem has been relatively less studied compared to the case when pairwise displacements are available [31 12, 6 5T]. These methods belong to the
network with known pairwise relations between nodes and unknown node values to be estimated. For our specific problem of translation averaging, absolute translations T; E R3 i E V, and M edges, E, denoting the pairwise relative direction measurements between the nodes Viy 82 (i.j) E E. Here, all the relative directions Viş 's are in the same coordinate frame. Ideally, Vij should be the unit vector in the direction of TT T, Since the measurements made are directions, these networks are also called bearing-based networks. This problem finds a place in global methods 223 24 [8 [52) for solving Structure-from Cocturre-foo--Moee Motion (SfM) (28] 3D computer vision, where a network cameras is present with relative translation directions measured between the cameras.
category of averaging or map synchronization [43] 46), which can modelled
(V, E) represents a network, with V nodes, V. denoting the
Solving translation averaging is challenging problem since requires estimating translation scales in a context of dissimilarity in the input (directions) and output (absolute translations). Due to this dissimilarity, the solutions are defined upto global scale and choice of origin. The well- posedness of the bearing- based network problems has been studied under the lens of parallel rigidity theory [45] 19 36 42 56,1 2.. This theory determines whether a given of input directions will
have unique solution (upto global scale and an origin) for absolute translations.
Distinction from parallel rigidity and outlier detection: This paper takes the first step to deal with sensitivity in translation averaging under uncertainty, i.e. determining under what configuration of
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

input directions the solution is reliable. This can be seen as perturbation analysis of the translation averaging solution with respect to small changes in the imput directions. Although there have been empirical studies on small-scale datasets (3 to 20 cameras) on the effect of perturbing input directions [48] 40 [2] to the best of our knowledge, analysis on large-scale networks, both theoretical and empirical, has not been done for bearing- based networks. This analysis is independent of parallel rigidity [2] since parallel rigidity deals with uniqueness of the solution, while we deal with change in solution for small input perturbations. Parallel rigidity can be equivalently described with the algebraic rank of a specific matrix 22). which is similar to the analysis of uniqueness of a solution given a matrix obtained from linear system of equations, Sensitivity analysis is similar in spirit to the conditioning of a matrix while solving a linear system of equations (Az = b problem) where the reliability of a solution is studied. Sensitivity is also different from outlier detection in the data because it only deals with small perturbations of the given input directions and not with the noise/outlier levels. The issue of sensitivity remains relevant even without outliers.
Our contributions: We first analyze the sensitivity in estimating edge scales in translation averaging by small perturbations to input directions on the smallest solvable bearing-based network. Then, we characterize the conditioning of the translation averaging problem based only on input directions, without any perturbation, for the smallest solvable network i.e. 3 edges between all 3 nodes, and extend it to a general network. We provide a sufficient condition for the network to be well- conditioned. We propose an efficient algorithm to identify ill-conditioned parts of the network, filter them and extract the maximal parallel rigid graph without explicit computation that checks for parallel rigidity. Finally, we show the usefulness of such filter in the context of SIM with improved translation accuracy, more 3D points triangulated and faster convergence of bundle adjustment after removing ill-conditioned parts of the network.
2 Literature Review
In this section, we briefly discuss the relevant literature on translation averaging and parallel rigidity.
Translation averaging in SIM: In SfM, the input data contains relative translation directions that not aligned common reference frame. To get the input directions in common global frame,
absolute rotations for each node are estimated using rotation averaging methods [0)] 11 21 47)
Many translation averaging methods have been proposed over the last two decades. Govindu 23
minimized the cross-product between the input directions and directions obtained from absolute translations. Jiang el al. [32] considered triplets of nodes and used the constraints of triangle to formulate the problem. Wilson el al. (55] minimized the deviation between the input directions and directions estimated from absolute translations. Tron et al. [54] minimized the squared relative displacements and solved it in a distributed manner. Ozyesil et al. proposed the Least Unsquared Deviations (LUD) method, extending [54]. with L1 loss for robustness which made the problem as a convex program. Arrigoni et al. (5) minimized the squared error of the orthogonal projection of the estimated relative translations onto input directions. Goldstein et al. (22 also minimized the orthogonal projection using ADMM but used an L1 loss for robustness. Zhuang et al. [57] relaxed the cost in (55) by comparing estimated relative translations to that of the observed directions and called it Bilinear Angle-based Translation Averaging (BATA). Other methods include using two-view and three-view geometry (28 of the cameras to set up the problem [
40 estimating edge
scales through cycles in network before solving for absolute translations 3 4 or through point
correspondence constraints [13 [4], iteratively refining input directions (37], averaging matrices
obtained from two view geometry 33 34), and exploiting the structure of the matrix generated from
pairwise displacements [15]
Parallel rigidity: Several works about parallel rigidity are present in the literature arising from different communities: computer vision 42 2], robotics (36), computer-aided design [45 and
decision control [20] 19 53 56]. The bose- formulation is the classical way to approach parallel rigidity, which deals with absolute translations (also called point formation) 44 20 19]
The edge-based formulation is more recent approach which reasons about parallel rigidity based
on edge lengths in terms of the cycles in the network 35 g (33 Readers are referred to 2 for an
excellent survey on parallel rigidity.
2

---

3 Sensitivity in Scale Estimation from Directions
In this section, study the sensitivity in estimating edge scales in translation averaging. At first, define the notion of a consistent set of directions for a network G, which will be useful for further discussion.
Definition (Consistent Directions). set of relative directions, Vij. (1, & in a bearing-based network G, are said to be consistent if there exist absolute translations, Tr, E V, such that T,-T, IT,-T:11 =Vij
We consider the smallest possible searing-basede network which is solvable, i.e. network Ga of 3 nodes, VA- = {1, 2, 3,, with all possible edges, & {(1, 2), (2,3), ()) When these edges are consistent, they form triangle. Let V be the matrix containing relative directions Vij. (8, E & in its columns and be the vector containing edge scales 8ig- Then, the least squares problem to
estimate the scales can be written
min |s| s.t. |s|
(1)
where the unit norm constraint on is used to fix the global scale. The solution to the problem in Eqn. is given by the eigenvector corresponding to the smallest eigenvalue of VTV.
To analyze the sensitivity of the estimated scales, we perturb each direction in GA by a small 3D rotation 2R. E S0(3). therby ensuring that the perturbed vectors always lie on the unit sphere. Let n: E S and 50,5 be the rotation axis and angle for 8R.j. respectively. Then, the small rotation can be approximated to a first order, using Rodrigues' rotation formula, as &R.5 R I 50.g [n.y] x. where [nx]] E R is matrix such that [nsy]x h = n. X for any E R and the 3 x identity matrix. For small perturbations to Vij by öR.j. the following theorem holds:
Theorem 1. For a set of consistent directions, Vij. (i, Es. in Ga. the absolute change any eigenvalue of VTV, denoted as jō\], when the directions Vij are perturbed by small rotations öR.g. with nij and s0.3 > O being the rotation axis and angle, is bounded by
sin may (k.)..0.))
1811 <
Σ (KI))TTTAA)
800g I
11 By +
sin (1..6))(8.))
[(1 + [1+ (v) ((v)) (V (VG))N)))) - 4 V Va v
(2)
where TI(A) = (11,2,3), (2, 3, 1), (3, 1, p is the component of v orthogonal to nij. pij (k.)).(k:)) is the angle between n. Vii and Vij and ((k.))(k..) is the angle between Vki and Vaj-
ny
The proof of Thm. Jsees eigenvalue perturbation theory [30]. Please refer to the appendix for the proof. From Thm. [ can be observed that the bound for absolute change in any eigenvalue is inversely dependent on the square of the sine of angles of the triangle formed by the unperturbed directions. Since the scale estimate, s, is the eigenvector corresponding VTV, Thm. f reveals that scales are sensitive to small perturbation of directions when at least one angle in the triangle small. The term in the square root in Equ. 2 bounded due to the dot product of unit norm vectors and is strictly greater than zero since the unperturbed directions are consistent.
the smallest eigenvalue of
We note that the bound also directly proportional to the sine of the angle hetween the directions projected onto the orthogonal space of the rotation axis. This suggests that the effect of perturbation maximum when the rotation axis is orthogonal to the directions. This the same as the case in Cor. D when the perturbed directions are consistent.
Corollary 1. For set of consistent directions, Viji (i. E Es, in GD. the absolute change in any eigenvalue of VVV, denoted as (ō\|, when the directions Vij are perturbed by small rotations öR.g. with Dij and 80., > O being the rotation axis and angle, and nij being othogonal to Vui and Vag for all (i,j,k) TI()), is bounded by
|8>] <
Σ (KIJ)ETI(A)
80g
sin ((R
[11 (ViT
((vT)v))² + (v)))))))) - -4 V V v
(3)
3

---

A'
A'
A
B
C
B
(a) Well-conditioned triangle
(b) Ill-conditioned triangle (Type-I) (c) Ill-oonitioned triangle (Type-1l)
Figure Conditioning of triangles: analyzing change output with small perturbation input
direction (green: given direction; red: perturbed direction; change in output: from A to A').
where TI(A): = ((1, 2),), (2,3, 1). (3.1, and (k..)) is the angle between Vks and Vkj--
Cor. reveals that the scale estimates unstable with small angles, even in the when the perturbed directions are consistent. We call triangles with at least one small angle as skewed triangles. In Fig. show conditioning of the triangle under different scenarios, with green and red depicting the unperturbed and perturbed directions, respectively. For a well-conditioned triangle, a small change in direction leads small change in the absolute translation. But for ill-conditioned triangle (skewed triangle), a small change in the direction leads to a large change in the absolute translation. Fig. Ta shows well-conditioned triangle, Fig. Tb shows triangle with small angle due to which it is ill-conditioned (Type D) and Fig, [hows a triangle with two small angles making ill-conditioned (Type II). Such skewed triangles are known be problematic different fields. In numerical analysis [25] 8 the skewed triangles are termed as 'needle-like' triangles, and measuring their area and angles have numerical issues. In computational topology and computer graphics [17 (38] skewed triangles (also called sliver triangles) are often avoided, as in Delaunay triangulation, or are filtered out. We note that none of them deal with directions as input. Our aim is to quantify the conditioning of the triangle and the translation averaging problem based solely on the input directions, without actual perturbation, and filter out skewed triangles, which are discussed in subsequent sections.
4 Conditioning of Translation Averaging
In this section, first analyze the conditioning of the bearing- based network with 3 nodes and edges, i.e. GA (as defined in Sec. 3p. We define an angle matrix, Aga E R3x3 as follows:
(112))
(221))(2.3))
(112))(113)
O
(2.1).
(12))
Aga = (22.3).(211)
(33.2).(3.1) (2.3)
= 22.1). (1.2))
(3..))
(4)
(11,3),112))
(3,11),(3,1) (33.)).(3.2)
(3.2)).33.1
where (kk.))((k.) is the angle between Vki and Vky (as defined in Thm. T.. The rows and columns of Аga signify edges in GA and its entries are the angular differences between directions with angles being measured within the triangle using the common node between two edges as the reference point for measuring directions. Since ((k.)).(k..)) ((k.)).(k.)) = 0, Aça has zero diagonal entries. We quantify conditioning of the translation averaging problem Ga conditioning of the matrix Aga based on the following theorem:
((k.)).(k.d) Aç is symmetric, and since
Theorem 2. Consider the bearing based-network of 3 nodes and 3 edges, 9A = (Va,Es), EA), and the corresponding angle matrix Age- The conditioning of the matrix Aça signifies the skewness of the triangle formed using the directions in E
The proof of Thm. thm.2lime innvoles proving Aga being non son-singular for nor-zero angles using its deter- minant and checking for the closeness of columns relation to the angle values. We choose this approach instead of checking determinant since the later is not good measure of closeness of matrix to singularity [39]. Please refer to the appendix for the complete proof. Thm. reveelss that the conditioning of GA can be characterized by the condition number of matrix Aça-

---

We generalize the angle matrix and Thm. for any bearing- based network G. We assume all edges in are a part of least one triplet (a triplet consists of nodes with all possible edges between them). We use the terms triplet and triangle interchangeably since triplet forms a triangle for our specific problem. this assumption not satisfied, we remove the edges G. which are not a part of any triplet and consider its maximum connected component. This will enable us to use وR as the basic building block of G and thus characterizing the conditioning gf
We now expand the angle matrix to a general bearing- based network G in which every edge is a part of at least one triplet. We denote the angle matrix for the general network as Ag E RR-x (M is the number of edges in 9), where the rows and columns signify edges in G, and its entries, ag corresponding to the row for the edge (i,j) and the column for the edge (k: l), are defined as follows:
if (i,5) and (ks 1) belong to the same triplet with e E {i.j} n {ki, lf and c. E {i.j) (k,1) \ {ch: otherwise.
fj.kl 0g
(5)
0
In Ag. measure the angles between the directions formed by triplet. In such cases, to ensure that the directions are measured within the triangle, similar to Aga . the common node, c, is taken as reference and the directions are measured from
other nodes ei and cz. From Eqn. 5 is clear that
the diagonal entries are zero (0(K,)) (). = 0) and the matrix is symmetric (Ø ((..))(()))) ((k..).(k.)) Scaling
We note that Ag is not the same as that of the distance matrix used in (MDS) 77, 9.. In instances when a node appears in more than one triplet, angles between the edges belonging to the different triplets are not computed, but in MDS, such angles would also be considered. This restricts the angle matrix Ag to contain information only about triangles and not of other structures. Such a construction helps extend the findings from Ag, to Ag. We define the conditioning of the translation averaging problem as the condition number of angle matrix Ag. The following theorem states sufficiency condition for a well-conditionss angle matrix:
Theorem 3. Consider a bearing- bussed network G. with all edges contributing to triplets. The angle matrix Ag, corresponding to G, is well conditioned if the minimum angle (or equivalently all the angles) in all the triangles formed by the triplets are sufficiently large.
The proof for 3 is similar to the proof for Thm. 2 Here, we check for different combinations of columns based on the structure of G and check for their closeness. Please refer to the appendix for the proof.
We note that we do not need to be parallel rigid for the angle matrix Ag to be well conditioned, implying that sensitivity and parallel rigidity are different aspects of the bearing-based network. However, we need G be parallel rigid ensure a unique solution. In general, computing the maximal parallel rigid component is expensive. Since we remove edges in G not contributing to triplets, this can affect its parallel rigidity. We avoid such expensive computation since we deal with triplets. We construct triplet network Gr = (Vr, Ey) ), as done in [32, where nodes V/ denote triplet in G and edges &r connect the nodes if an edge is common between the triplets G. By construction, it can be seen that disconnected components in G will be disconnected in Gr since there cannot be shared edges among disconnected components. The following theorem enables extracting the maximal paraliel rigid graph when G contains all edges contributing to triplets:
Theorem 4. Given a bearing- based network G, with all edges contributing to triplets forming triangles, and its corresponding triplet network Gr, the maximal parallel rigid component of g can be determined by the edges in G contributing to the largest connected component of Gr.
Please refer to the appendix for proof of Thm. Based on Thms. 3 and 4 we develop an algorithm to identify and remove skewed triangles from the translation averaging problem while ensuring that the network is parallel rigid, which is discussed in the next section.
5 Proposed Method
In this section, we show how to efficiently identify skewed triangles in G. First, we get the list of nodes and edges contributing to each triplet in G, for which efficient implementations exist [52] 26) The brute force way to identify skewed triangles is to compute the angles in each triangle using the relative directions Vig and mark triangles with the minimum angle less than a threshold. The number
5

---

of triplets depends on the sparsity of the network G. which, in general, is large. This makes the brute force method time-consuming. In contrast with the brute force approach, we use vectorized operations to construct the angle matrix Ag and filter skewed triangles, making it time efficient. It observed that the vectorized version is ~ 100 times faster than the parallelized version (with 20 threads) of the brute force method for ~ 10 triplets coming from ~ 10 edges, and this gain increases significantly with an increase in the number of triplets and edges. A time comparison between the brute force method and our method is given in the appendix. In real-world data, the large-scale bearing-based networks are sparse, making Ag sparse. We present our method for sparse networks in the following steps and for dense networks in the appendix.
Step 1: The first step is to identify which entries are non-zero in the angle matrix Ag. Since we are considering only triplets, we require a matrix that captures which edges are part of triplet. In computational topology (29 16), higher order relationships in 9 = (V. E) (other than node-to- node relationship via edges) are studied using simplices. A k-simplex is subset of the vertex set V with (k + 1) elements. A finite collection of simplices, such as nodes (0-simplices), edges (1-simplices), and triangles (2-simplices), is called a simplicial complex. The boundary matrix B, of a simplicial complex encodes which (k- - -iimple contributes to k-simplex, In our case, we need the relationship between 1-simplices (edges) and 2 2-simplices (triangles). The (i element of the boundary matrix B E MMW, with M edges and W triplets, is given as:
By f1
if tt edge contributes to jth triangle; otherwise.
(6)
It is easy to compute B2 since we have the list of edges contributing to each triplet. The row and column indices of non-zero elements in B2B give us the edge pairs participating in triplets. Only these elements in Ag are to be computed (except diagonals in ByB, which are non-zero). The corresponding dot products between the edges are computed in a vectorized fashion and stored.
We need to identify the correct signs for the dot products to ensure that the dot products reflect the cosine of the angles of the triangles. Since the dot products are cos (kk.)) for edges (i..), (k, 1) E E in triplets, there will be one common node e E {i, n (k:, I]. The directions Vij and Vaz should be measured with reference to the common node get the angle of the triangle that
Step 2:
includes those edges. We need the dot product between Veef and Veef- where e E (i.j} \ {c) and
de E (k. () \ {c). Using v2 Yeek =V VejeVelee and Vij -ji we premultiply each dot product by mtikkl where fiikl is determined as follows:
if k or j = 1; i = k;;
m Gikt
otherwise.
Since edges (i, (k:, 1) are part of triplet, the third case in Eqn. 7 will not arise, but will be helpful in the dense network case. We premultiply mij.kf to the corresponding dot products. We take the inverse cosine of the sign-corrected dot products to get the angles and allocate Ag.
Step 3: It is easy to extract angles from Ag since edges corresponding to triplet known and Ag provides an easy way to index edges based on its rows and columns. Let Trp be the set of triplets in G. We check if the angles of the triangles are greater than a minimum threshold and remove the triplets having skewed triangles. This creates two sets of triplets TrpRet and T Rem denoting retained and removed triplets, both being mutually exclusive. Let the edges contributing to the two triplet sets be Eret and Erem, respectively, such that غ = Eret Uremm We note that Eret EErem is not necessarily empty. For parallel rigid G. the two edge sets are not mutually exclusive since there will be common edges between the triplets of Eyet and Erem, as a consequence of Thm. 4 Let the filtered network be denoted as Gp = (Vr, Ep). There are two ways to remove edges: one is to remove edges aggressively such that & = E Erem and the other way is non-aggressive i.e. Er = Eret- Since all operations are vectorized, this makes the whole process of extracting the angles and removal of skewed triangles time efficient. Next, we construct the triplet network Gr (as discussed in Sec. 4 from ÓF and extract the largest connected component of GT. to ensure that the network is connected and is parallel rigid. The edges of ŚF contributing to the largest connected component of GT gives the final network Gr = (Vr, Er). The whole process is summarized in Algo I In our experiments, the network G is sparse, and we choose the non aggresseee way of removing the edges, which ensures

---

Algorithm 1: Removal of Skewed Triangles from Sparse Networks
Input: Bearing-baa -ased network 9 = (V, containing only triplets and is parallel rigid, and the triplet list of g.
Output: Bearing-baan
network Gr (Vr; Er), containing only triplets and is parallel rigid,
without skewed triangles.
Compute the non-zero elements angle matrix Ag using the boundary matrix B2 (Eqn. 6
Compute the dot product for the non-zero elements in Ag.
Get the signs of the dot product i.e. m using Eqn. 7
Multiply dot products with their corresponding signs m
5
Take the inverse cosine of dot products.
Allocate the matrix Ag. Extract the angles of the triplets from Ag.
7 Filter out the triplets with the minimum angle less than a threshold to get وr- = (Vr, Er).
Construct the triplet network GT using Gr.
Get the largest connected component of 9r-
Get the edges of ÖF contributing to the largest connected component of Gr to get GF (Vp, EF), which connected and is parallel rigid.
10
that the connected component of OF is large. We note that with non-aggressive pruning, we still ensure that the nodes are estimated reliably since the nodes are also part of atleast one triplet, which belong to the set of non-skewed triangles.
6 Experiments
We consider SfM datasets provided in IDSFM 551 for the experiments. It provides the relative motions and a reference reconstruction using Bundler 49 50). Since Bundler was published more than ten years ago, we use COLMAP (44) to generate the pairwise relative rotations and translations and use COLMAP's solution the ground truth get better reconstruction. We take COLMAP solution and align it to the solution provided in 1DSfM to get absolute translations in meters. We compute absolute rotations using I1 and them to align the relative translation directions into a global coordinate frame. The output of this process gives us a bearing- network. Then, we extract triplets from the network and ensure parallel rigidity. Since the filtering process is independent of the cost function to solve the problem, we consider two representative cost functions. Revised LUD (an improvement on [1I, provided by (57]) compares relative displacements, and BATA (57), compares relative directions. Please refer to appendix for the problem formulations. Our code is implemented in MATLAB. All experiments are performed on PC with Intel Xeon Silver 4210 processor with 128 GB RAM. Finally, in each table, Mean-ATE and RMS-ATE denote the mean and RMS absolute translation errors, respectively, w/o and w/ filter denotes the network before and after removing skewed triangles and bold entries denote better performance between the solutions of the two networks.
6.1 Analysis Real Data
In this subsection, we first provide an illustrative example using COLMAP 44 reconstruction and then analyze the real data. Fig. 2 shows an illustrative example the existence of such skewed triangles in the SfM problem. For the Alamo dataset, most images capture the front part of the museum, and thus, the cameras are densely connected in the network. The blue triangle depicts a triplet which is Type-I ill-conditioned triangle and the green triangle shows Type- II ill-conditioned triangle.
Now, we analyze the real data to understand the frequency of occurrence of skewed triangles and their difference with outlier data. For the analysis, we compute the errors in relative directions with respect to ground truth. To check whether atleast one outlier is present in the triplet, we check the maximum error of relative directions each triplet, we compare the maximum error of relative directions with the minimum angle between directions for each triplet. In Fig. 3 we show seatter plots between the two compared quantities for all the triplets for three datasets with different edge densities. At first, we observe that there are
triplet. Since we identify skewed triangles with the minimum angle in
7

---

Facemae
Segresso
(a) Piccadilly (ed 1.16%)
(b) Tower of London (ed = 3.91%) (c) Union Square (ed 2. 2.76%)
Figure 3: Scatter plots of maximum error of relative directions in each triplet (with respect to ground truth) minimum angle between edges in each triplet on datasets from [55]. ed denotes edge density.
considerable number of skewed triangles in the network since there are many points in the scatter plot which are close to 0 in the x-axis (representing the minimum angle in triplets). Next, we can also see that the minimum angle between edges in the triplets is independent of the maximum error in the triplets, implying that the presence of an outlier and the skewness of a triangle have no relation. Also, it can be seen that triplets with minimum angle > 60" are clear outliers and all of them have high angular error with respect to ground truth. Based on this observation, we first provide results on outlier-free data, and then show the results on the real data with outliers in the next subsections.
6.2 Outlier-Free Data
In this subsection, we examine the impact of skewed triangles on the quality of the trans- lation estimate independent of outliers. First, we extract the component of the network for which the ground truth is available. For this experiment, to remove the effect errors com- ing from absolute rotation estimates, ground truth rotations to align the relative di- rections to a common reference frame. We consider the edges as outliers if the relative direction on the edge differs from its ground truth equivalent by more than 10" and remove them. Then, extract the triplets from the network and ensure parallel rigidity. This gives us network with no outliers but still contains skewed triangles. We call it the unfil- tered network. Now, we use Algo. to remove skewed triangles (minimum angle < 5") and denote the output as the filtered network and compare the solutions from the two networks.
Reference reconstruction of Alamo [55 using COLMAP [44 for displaying skewed trian- gles. Blue triangle: Ill-conditioned triangle (Type-I), Green triangle: Ill-conditioned triangle (Iype-II).
Figure 2:
In Table I we list the number of nodes and edges removed due to the removal of skewed triangles and check the absolute translation errors obtained using BATA. It can be seen with the removal of small number of nodes and edges, the mean and RMS errors of the absolute translations decrease consistently (see appendix for the number of nodes and edges of the networks). We also check the errors of the nodes the unfiltered network, which were removed due the removal of skewed triangles. It can be seen that the mean and RMS errors of the removed nodes are high compared to overall errors implying that absolute translations at these nodes are not well estimated. Absolute translation error obtained using Revised LUD is provided in the appendix, which also shows that removal of skewed triangles leads to improved translation estimates. This shows the impact of skewed triangles on the translation averaging and the benefits of removing them.

---

Table 1: Absolute translations errors (in meters) on IDSIM [55 datasets without outliers us-
ing BATA [57] Removed Node Errors: Errors of removed nodes in the unfiltered network, N NNrm:: # Mrm:: No. of nodes and edges removed.
Dataset
#Nrom #
Mean-ATE
RMS-ATE
Removed Node Errors
w/o filter
filler
filter
Alamo (ALM)
211
2.2
3,9
Ellis Island (ELS)
15
0,9
1.5
1.3
5.5
5.5
Gendarmennarkt (GMM)
9
67
5.1
4.8
8.5
7.9
19.2
21.8
Madrid Metropolis (MDR)
20
184
6.0
13.6
10.6
23.6
29.7
Montreal Notre Dame (MND)
2.3
3.8
NYC Library (NYC)
20
185
2.5
2.3
5.1
5.0
6.2
8.2
Notre Dame (ND)
17
536
2.5
2.4
5.0
4.8
7.6
11.8
Piazza del Popolo (PDP)
10
247
2.6
4.5
5.6
Piccadilly (PIC)
2.1
4.6
Roman Forum (ROF)
30
391
9.2
8.9
19.1
16.7
26.9
42.9
Tower of London (TOL)
11
96
8.0
7.5
16.2
14.3
37.8
53.5
Trafalgar (TFG)
184
1879
6,9
17.0
21.7
27.9
Union Square (USQ)
4.5
6.0
10.6
13.2
Vienna Cathedral (VNC)
19
275
7.2
7.4
10.6
10.4
15.0
18.0
Yorkminster (YKM)
13
181
4.9
4.8
13.4
14.8
17.5
26.5
Table Details of networks before and after removing skewed triangles from 1DSfM (55] datasets. # N Nemm: # Mrem: No. of nodes and edges removed, K2 (A):: condition number of the angle matrix with matrix-2 norm, liiterr time taken to remove skewed triangles.
Dataset
#Nodes
#Edges
# #Nrem
#M
AAp)
8 fyster (sec)
w/o filter
filter
filter
filter
filter
w/ filter
ALM
682
15619
15422
12
197
2.3c+08
2,4c+07
0.31
ELS
324
316
7411
7342
8
69
2.6c+07
3.8c406
0.14
GMM
950
926
13913
13656
24
257
2.7e+09
1.8e+08
0.20
377
4367
4170
7.2c+07
5.6e+06
0.05
MND
564
560
18297
18150
4
147
2.1c+08
3,4c+07
0.67
NYC
450
437
6228
6017
13
211
6.0c+07
4.0e406
0.08
70759
70651
5.4e+09
2.66
PDP
909
891
14770
14502
18
268
1,3e+08
3,1c+07
0.32
PIC
2706
2645
45306
44405
61
901
1.7c+09
6,5e408
0.55
2.5e+09
0.25
TOL
569
552
8710
8569
17
141
8.2c+07
2,0c+07
0.14
TFG
6327
6110
110876
108142
217
2734
1.5c+11
4.7c+09
1.83
USQ
12638
2.7e+09
2.6e+07
0.23
VNC
1015
986
24793
24511
29
282
1.3e+09
1.2c+09
0.65
YKM
964
930
12033
11670
34
363
1.0+112
1.0c+12
0.18
6.3 Real Data
In this subsection, we deal with real data in the context SIM, which is obtained as described the beginning of this section. We note that this data contain outliers, and our aim is to understand the impact of skewed triangles in the presence of outliers. We denote the network obtained as unfiltered and remove the skewed triangles (minimum angle < 5%) using Algo. calling it the filtered network. In Table 2 we provide details of the unfiltered and filtered network. It can be observed that the removal of small fraction of nodes and edges from skewed triangles leads to significant decrease in condition number of the angle matrix (with matrix-2 norm), K2 (Ag), for all datasets expect ND. We employ non-aggressive pruning due to which some skewed triangles can remain in the filtered network making the condition number (Ag) increase for ND and the same for YKM. We reiterate that non-agen aggressive pruning still ensures that the nodes well estimated (see Step in Sec. (5) This shows that the conditioning of the translation averaging improves for most datasets, even with the non-aggressive removal of skewed triangles.
In Table we present the absolute translation errors obtained using BATA without and with filtering skewed triangles. It can be observed that the mean and RMS errors improve for most of the datasets after the removal of skewed triangles. Also, emror of the removed nodes in the unfiltered network are high, which indicates that the absolute translations at these nodes are not reliable in the unfiltered network. We note that from Tables and the filtering time 1% of the time taken translation averaging, which shows the practicality of Algo. Next, perform 3D reconstruction using

---

Table Absolute translations errois (in meters) on IDSIM [5
datasets using BATA [57]. Removed
Node Errors: Errors of removed nodes in the unfiltered network, BATA time taken by BATA.
Dataset
Mean-ATE
RMS-ATR
Removed Node Eroos
ÍDATA (see)
w/o filler
w/ filler
w/o filter
w/ filter
Mean
RMS
ALM
4.7
4.5
11.1
10.5
22.9
39.5
17
ELS
23.2
22.1
50.7
51.8
98.6
118.1
7
GMM
50.6
40.9
77.8
61.1
149.7
190.8
14
MDR
13.9
12.7
29.4
26.1
54.2
61.2
5
MND
4.4
4.3
10.0
9.9
31.2
34.1
17
NYC
6.5
5.2
15.8
12.6
28.7
38.1
ND
3.3
3.3
6.4
6.9
7.0
PDP
8.0
8.0
13.0
13.1
15.0
17.3
16
PIC
5.3
5.1
11.0
10.8
20.8
29.2
68
ROF
12.8
10,4
27.0
19,6
65,4
100.5
24
TOL
15.6
14.5
32.2
30.3
63.7
90.3
10
TFG
20.3
14.5
62.6
31.8
65.0
130.8
287
USQ
24.8
18.1
34.5
49,9
14
VNC 10.2
10.2
17.8
18.4
21,4
27.5
28
YKM
20.4
19.3
29.5
28.3
44.0
51.4
13
Table 4: No. of points triangulated (Por x 10²) and bundle adjustment iterations (BAnter) using the solutions obtained by BATA for unfiltered and filtered networks on IDSMM [55] datasets.
Dataset
ALM
ELS
GMM
MDR
MND
NYC
ND
w/o filter
142
57
101
115
77
376
Pbs
filter
144
104
118
79
375
w/o filter
73
40
66
100
34
BAii
filter
54
33
21
83
37
74
22
PDP
PIC
ROF
TOL
USQ
VNC
YKM
w/o filter
91
231
196
107
219
175
Pers
w/ filter
94
234
196
110
56
222
168
BAttea 4
w/o filter
34
53
31
89
122
52
58
w/ filter
44
47
21
85
52
25
33
Theia [52] with the absolute translation solutions obtained in Table Theia removes the triangulated 3D points which have reprojection errors greater than 15 pixels. more 3D points are triangulated in the filtered networks for most of the datasets. We note that filtered networks have lesser nodes than unfiltered networks, which implies removal of nodes coming from skewed triangles leads to better conditioning for 3D point triangulation. We also see that the bundle adjustment converges faster for the filtered networks indicating absolute translations are more stable in the filtered networks compared to unfiltered networks.
be seen from Table that
Limitation: Our sensitivity analysis of translation averaging is based the triplets in the network. Although we do not lose much terms of 3D reconstruction SfM, further work is required to understand the sensitivity of general bearing- based network.
7 Conclusion
This paper deals with sensitivity in translation averaging under input uncertainty. We study sensitivity in estimating edge scales in bearing- based networks which suggests skewed triangles are unstable. We define the conditioning of the translation averaging problem and provide a sufficient criterion ensure that the problem is well-conditioned. Then, we propose an efficient algorithm to remove skewed triangles from the network while ensuring parallel rigidity. We demonstrate filtering scheme using cincture-rrommoole data without and with outliers leading to better absolute translation estimates, more 3D points triangulated and faster convergence of bundle adjustment for filtered networks.
effectiveness of our
10

---

Acknowledgments and Disclosure of Funding
Lalit Manam is supported by a Prime Minister's Research Fellowship, Government of India. This research was supported in part by a Core Research Grant from Science and Engineering Research Board, Department of Science and Technology, Government of India
References
[1] Mica Arie-Nachimson, Shahar Z Kovalsky, Ira Sanellmachhr-Shlizennnn Amit Singer, and Ronen Basri.
Global motion estimation from point matches. In 20/2 Second international conference on 3D imaging. modeling, processing visualization & transmission, pages 81-88. IEEE, 2012.
[2] Federica Arrigoni and Andrea Fusiello. Bearing-based network localizability: a unifying view. IEEE
transactions on pattern analysis and machine intelligence, 41(9):2049-2000 2069, 2018
[3] Federica Arrigoni, Andrea Fusiello, and Beatrice Rossi. On computing the translations norm in the epipolar graph. In 2015 International Conference on 3D Vision, pages 300-308. IEFF, 2015.
[4] Federica Arrigoni, Andrea Fusiello, and Beatrice Rossi. Camera motion from group synchronization. In 2016 Fourth International Conference 3D Vision (3DV), pages 546-555. IEEE, 2016.
[5] Federica Arrigoni, Beatrice Rossi, and Andrea Fusiello. Robust and efficient camera motion synchroniza- tion via matrix decomposition. In International Conference on Image Analysis and Processing, pages
444-455. Springer, 2015.
[6] Federica Arrigoni, Beatrice Rossi, and Andrea Fusiello. Spectral synchronization of multiple views in se
(3). SIAM Journal on Imaging Sciences, 9(4):1963-1990 2016.
[7] Richard Beals, David HI Krantz, and Amos Tversky. Foundations of multidimensional scaling. Psychologi-
cal review, 75(2):127, 1968.
[8] Sylvie Boldo. How to compute the area of a triangle: a formal revisit. In 2013 IEEE 21st Symposium on Computer Arithmetic, pages 91-999 98. IEEE, 2013.
[9] Ingwer Borg and Patrick JF Groenen. Modern muliidimensional scaling: Theory and applications. Springer
Science & Business Media, 2005,
[10] Avishck Chatterjec and Venu Madhav Govindu. Efficient and robust large-scale rotation averaging. In Proceedings of the IEEE International Conference Computer Vision, pages 521-528, 2013.
[1I] Avishek Chatterjee and Venu Madhav Govindu. Robust relative rotation averaging. IEEE transactions on pattern analysis and machine intelligence, 40(4):958 972, 2017.
[12] Robert Connelly. Generic global rigidity. Discrete & Computational Geometry, 33(4):549, 2005.
[13] Hainan Cui. Shuhan Shen, and Zhanyi Hu. Robust global translation averaging with feature tracks. In
2016 23rd International Conference on Puttern Recognition (ICPR), pages 3727-3732. IEEE, 2016.
[14] Zhaopeng Cui, Nianjuan Jiang, Chengzhou Tang, and Ping Tan. Linear global translation estimation with
feature tracks. In Proc. ECCV, volume 3, pages 61-75, 2014.
[15] Qiulei Dong, Xiang Gao, Hainan Cui, and Zhanyi Hu. Robust camera translation estimation via rank enforcement. JEEE transactions on cybernetics, 2020.
[16] H. Edelsbrunner and J. Harer. Computational Topology: An Introduction. Applicd Mathematics, American
Mathematical Society, 2010.
[17] Herbert Edelsbrunner, Xiang- Yang Li. Gary Miller, Andreas Stathopoulos, Datna Talmor, Shang- -uaa Teng, Alper Üngör, and Noel Walkington. Smoothing and cleaning up slivers. In Proceedings of the thirty-eccond annual ACM symposium on Theory of computing, pages 273-277. 2000.
[18] Olof Enqvist, Fredrik Kahl, and Carl Olsson. Non-sequential structure from motion. In 2011 IEFE International Conference on Computer Vision Workshops (ICCV Workshops), pages 264-271. I. IEEE, 2011.
[19] Tolga Eren, Walter Whiteley, and Peter N Belhumeur. Using angle of arrival (bearing) information in network localization. In Proceedings of the 45th IEEE Conference on Decision and Control, pages
4676-4681 Icee, 2006.
[20] Tolga Eren, Walter Whiteley, A Stephen Morse, Peter N Belhumeur, and Brian DO Anderson. Sensor and network topologies of formations with direction, bearing, and angle information between agents. In 42nd IEEE International Conference on Decision and Control (IEEE Cat. No. 03CH37475), volume 3. pages 3064-3066 IEEE, 2003.
[21] A. Eriksson, C. Olsson, F. Kahl, and T. Chin. Rotation averaging and strong duality. In 2018 IEEE/CVF
Conference on Computer Vision and Pattern Recognition (CVPR), pages 127-135, 2018
[22] Thomas Goldstein, Paul Hand, Choongbum Lee, Vladislav Voroninski, and Stefano Soatto. Shapefit and shapekick for robust, scalable strueture from motion. In European Conference on Computer Vision, pages
289-304. Springer, 2016.
[23] Venu Madhay Govindu. Combining two-view constraints for motion estimation. In Proceedings of the 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. CVPR 2001, volume 2. pages I1-11. IEEE, 2001.
[24] Venu Madhay Govindu. Lic-algebraic averaging for globally consistent motion estimation. In Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Puttern Recognition, 2004, CVPR 2004., volume 1, pages I-I. IEEE, 2004.
[25] Fred G Gustavson, José E Moreira, and Robert F Enenkel. The fused multiply-add instruction leads to algorithms for extended- deeedddd-rrecssion precision floating point: applications to java and perforperfoemncce computing.
11

---

IBM Thomas J. Watson Research Division, 1999.
[26] Aric A. Hagberg, Daniel A. Schult, and Pieter J. Swart. Exploring network structure, dynamics, and function using networkx. In Gaël Varoquaux, Travis Vaught, and Jarrod Millman, editors, Proceedings of the 7th Python in Science Conference, pages 11 11-15, Pasadena, CA USA, 2008
[27]
Richard Hartley. Khurrum Aftab, and Jochen Trumpf. LI rotation averaging using the weiszfeld algorithm.
In CVPR 20 pages 3041-3048. IEEE, 2011.
[28]
R. I. Hartley and A. Zisserman. Mulriple View Geometry in Computer Vision. Cambridge University Press,
ISBN: 0521540518, sccond edition, 2004,
129]
A. Hatcher. Algebraic Topology. Algebraic Topology. Cambridge University Press, 2002.
[30]
Roger A Horn and Charles R Johnson. Matrix analysis. Cambridge university press, 2012.
[31]
Xiangru Huang. Zhenxiao Liang. Chandrajit Bajaj. and Qixing Huang. Translation synchronization via
truncated least squares. Advances in nearal information processing systems, 30, 2017.
[32]
Nianjuan Jiang, Zhaopeng Cui, and Ping Tan. global linear method for camera pose registration. In Proceedings of the IEEE international conference on computer vision, pages 481 481-48 1488,, 2013.
[33] Yoni Kasten, Amnon Geifiman, Meirav Galun, and Ronen Basri. Algebraic characterization essential matrices and their averaging in multiview settings. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 5895-5903, 2019.
[34] Yoni Kasten, Amnon Geifman, Mcirav Galun, and Ronen Basri, Gpstm: Global projective sfm using algebraic constraints multi-view fundamental matrices. In Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition, pages 3264-3272. 2019.
[35] Bastian Katz, Marco Gaertler, and Dorothea Wagner. Maximum rigid components means for direction- based localization sensor networks. Lecture Notes in Computer Science, 4362:330, 2007.
[36] Ryan Kennedy, Kostas Daniilidis, Oleg Naroditsky, and Camillo J Taylor. Identifying maximal rigid components in bearing-basee localization. In 2012 IEEE/RSJ International Conference on Intelligent
Robots and Systems, pages 194-201. IEEE, 2012.
[37] Lalit Manam and Venu Madhav Govindu. Correspondence reweighted translation averaging. In European Conference on Computer Vision, Proceedings, Part XXXIII. pages 56-72. Springer, 2022.
[38] de Berg Mark. Cheong Otfried, van Kreveld Marc, and Overmars Mark. Computational geometry
algorithms and applications. Spinger, 2008
[39] Carl D Meyer. Marrix analysis and applied linear algebra, volume 71. Siam, 2000.
[40] Pierre Moulon, Pascal Monasse, and Renaud Marlet. Global fusion of relative motions for robust, accurate and scalable structure from motion. In Proceedings of the IEEE International Conference Computer Vision, pages 3248-3255, 2013.
[41] Onur Ozyesil and Amit Singer. Robust camera location estimation by convex programming. In Proceedings of the IEEE Conference on Computer Vision and Puttern Recognition, pages 2674-2683, 2015. Onur Ozyesil. Amit Singer. and Ronen Basri. Stable camera motion estimation using convex programming.
[42]
SIAM Journal on Imaging Sciences, 8(2): 122:112201222, 2015.
[43] Deepti Pachauri, Risi Kondor, Gautam Sargur, and Vikas Singh. Permutation diffusion maps (pdm)
with application to the image association problem computer vision. Advances in Neural Information Processing Systems, 27, 2014.
[44] Johannes Lutz Schonberger and Van-Michae! Frahm. Structure frouurre-fro--ooe from-mottonn revisited. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 4104-4113, 2016.
[45] Brigitte Servatius and Walter Whiteley. Constraining plane configurations in computer-aided design: Combinatories of directions and lengths. SIAM Journal on Discrete Mathematics,
1999.
[46] Yanyao Shen, Qixing Huang, Nati Srebro, and Sujay Sanghavi. Normalized spectral map synchronization. Advances in neural information processing systems, 29, 2016
[47] Yunpeng Shi and Gilad Lerman. Message passing least squares framework and its application to rotation synchronization. In International Conference on Machine Learning. pages 7796-8806. PMLR. 2020. [48] Kristy Sim and Richard Hartley. Recovering camera motion using innfyy minimization. In 2006 IEEE Computer Sociery Conference on Computer Vision and Pattern Recognition (CVPR'06) volume I, pages 1230-1237. IEEE, 2006.
[49] Noah Snavely, Steven M Seitz, and Richard Szeliski. Photo tourism: exploring photo collections 3d. In
ACM siggraph 2006 papers, pages 835 846. 2006.
[50] Noah Snavely, Steven Seitz, and Richard Szeliski. Modeling the world from internet photo collections.
International journal of computer vision, 80:189-210. 2008
[51] Yifan Sun, Jiacheng Zhuo, Arnay Mohan, and Qixing Huang. K-best transformation synchronization. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 10252-10261, 2019. [52] Christopher Sweeney, Tobias Hollerer, and Matthew Turk. Theia: A fast and scalable structureffrom-motton
library. In Proceedings of the 23rd ACM international conference on Multimedia, pages 693-696, 2015. [53] Roberto Tron, Luca Carlone, Frank Dellacrt, and Kostas Daniilidis. Rigid components identification and rigidity control in bearing-only localization using the graph cycle basis. In 2015 American Control Conference (ACC). pages 391 1-311.. IEEE, 2015.
[54] Roberto Tron and René Vidal. Distributed image-based 3-d localization of camera sensor networks. In Proceedings of the 48h IEEE Conference on Decision and Control (CDC) held jointly with 2009 28th Chinese Control Conference, pages 901-908. IEEE, 2009.
[55] Kyle Wilson and Noah Snavely. Robust global translations with Idsfm, In European Conference on Computer Vision, pages 61-75. Springer, 2014.
12

---

[56] Shiyu Zhao and Daniel Zelazo. Localizability and distributed protocols for bearing-basse based network localization in arbiurary dimensions. Automatica, 69:334-341, 2016.
[57] Bingbing Zhuang. Loong Fah Cheong, and Gim Hec Lec. Baseline desensitizing in translation averaging.
In Proceedings the IEEE Conference on Computer Vision and Pattern Recognition, pages 4539-45477
2018.
13

---

Sensitivity in Translation Averaging Appendix
Lalit Manam
Venu Madhav Govindu
Indian Institute of Science Bengaluru, India 560012
Indian Institute of Science Bengaluru. India 560012 venug@iisc. ac. in
lali ttmaamm@iiss isc. ac. in
8 Proofs for Theorems
Before prove the theorems, we first state the results, which will be helpful in proving Thm. We first state a result from first-order eigenvalue perturbation theory [30].
Result 1. Given a matrix X E MMM and a small additive perturbation on it by matrix 6' E RMXM the absolute change in eigenvalue, denoted (6X(X)), )), due the perturbation bounded by
[oX(X) S
W
where w, z CM,, and are the left and right eigenvectors of corresponding to the same eigenvalue, respectively.
Since w and z are eigenvectors, ||w||2 = 1 and ||z||2 1. For symmetric matrix X, the left and the right eigenvectors corresponding to any eigenvalue are the same due to which | z| |w w Hence, for symmetric matrix X, Result I can be rewritten as
(xX(X)
| maz (xX),
where max (8X) is the maximum singular value of 8X. Next, we provide our result on the singular value decomposition of a specific matrix, which will be used further.
Result 2. Given matrix X E 333 such that
0
a
X
0
b
(10)
a
b
the singular value decomposition of X is given as X USWT where
Va
+8
Va"
Va +
6
0
0
U
0
S
0
Va²
ba
0
and
Va
0
1
0
0
0
0
Va- b
W
b
V
+
Va b
Now, we prove the theorems stated in the main paper.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Theorem 1. For a set of consistent directions, Vaja (i,j) E Es. in Ga. the absolute change in any eigenvalue of VTV V, denoted as (o\), when the directions Vij are perturbed by small rotations öR.g. with nij and 60,g > 0 being the rotation axis and angle, is bounded by
T sin (R.0).0.)))
18\1 S
Σ (kI)))TI(A))
80.g V 11v]
sin ((R.)).(E.)))
[[1+ + (V ((v]) (()))))))))))))))))))))))) - 4. viL Vi,va viyvsal
(2)
where TI(A) = ((1,2,3), (2, 3, 1), (3, 1, v - is the component of v orthogonal to nij. mig-
miy- and Vij noyt and (1..)),(k3)) is the angle between Vki and Vaj- is the angle between Vii
(k.)).(k:))
Proof. Our goal is to check for the absolute change in the eigenvalue of V denoted as |o\] VTV is symmetric matrix. Using Result and Eqn. finding the matrix -2 norm the perturbation on VTV will give us the bound on the change in its eigenvalue.
Let us first look the case when edge is perturbed and then extend it later to all edges. We note that & = {(1,2) 2), (2, (3, 1)]. Without loss generality, we perturb V31 and denote the perturbed vector V31- Since the perturbation is made by small rotation 8R31, write the perturbed vector as
P 8Rai
31
= (I + 50g1 [nailx)
V31 + dw3i X V31
(1I)
where dw3i 8031 na1. From Eqn. 11 it can be seen that the perturbation can be treated as an
additive perturbation V3i V3i dv31, where dvai dwai x V3I. Let the perturbed matrix of the directions be V such that V = V + dVVs. where VV be written
[0 ōv31]. Then, (VP)TV can
(VP)TVP = -VV + oV (V +VV31)
>V + V 8V + +8V
31 V [ignoring second order terms]
-V"V + dal V),
(12)
where 1rg (V VV + +V V. After simplification of 851 (VT)), we get
0
dw (Va1 X V12)
831 (V
0
dw (V31 x V2s)
(13)
Tw (V31 V12) Sw (V31 V23)
It can be seen that dui (V has the same structure as that of the matrix in Eqn. 10 So, using
Result 2 we get
Tww (Var x v12) اوgl (Va1 x V23)
mmaz (VT V))
(14)
Since the directions are consistent, the three directions are coplanar. So, there exists and B such that
V31 QV12 8323.
(15)
We obtain a and by premultiplying Eqn. 15 by vfz and v2z to get the following set of equations
v V31 =ov 12 V22 Bv B2
(16)
22 V31
=av V12 8v V23.
(17)
Solving Eqns. 16 and 17 and using the fact that v Vi5 1, we get
(v V3n 22 V12)
V12
(18)
1 - (v V23)² )
31 V23
(19)
1 (Vi2
15

---

Also, using Eqn. 15 we get
V31 x V12 8V23 V12);
(20)
Vai x V23 - aV1222 x V23).
(21)
Using Eqns.
20 and 21 in Eqn.
14 get
B Swg (V23 x V12)
3.ng. 80031
n V23 x V12)
maz (631 v))
=
a Swgi (V12 X V2a]
a a. V12 V23
(22)
Let us decompose the directions as v vall + yn where vnll and vn denote parallel and perpendicular components of v to n, which be obtained
all = (v"n) Tn
(23)
vill v (v n)
(24)
Using Eqns. 23 and 24
we get
V23 X V12 (VVg D31
Bo1 ((V22 n311 vi2
V23
= ((v
m31) x ((vi2)s)) n&1) + (VIgns1) n111 x V2
1911
(v12 n31 + 23
x v
(V 031)
ny1 x 12n + (vig
(v3s a n&l) + (V23) 1
x va
(25)
Premultiplying n in Eqn. 25
we get
n (V23 x V12) n/gi
nay
|
nan + |I.
(26)
since, by construction, Dai get
x nai
x v
12
Daa
Using Equ.
26 into Eqn.
22
we
3 a
a Taan (631 (V V)) ())
= 80
I nag
12
x
23
Dai
(27)
Using the values of a and from Eqns 18 and
we get
| ms1
Omax (o21 50
V2a
1
V22222)
[(1 + (2))
((v22
(v (312 V31 )2) - 4 Vi2 vig vgi v12)
sin ney 1
580g1
||v
nai |
(2.3).
23
sin 22 (2211)
[[1 + v2)))))))
(av
va1)))))))
v vagvai v v
(28)
where a (2.1). is the angle between v21 and v2 and ((231)((23)) is the angle between V21
and V23-
Now, we perturb all three edges in Ga. Then, Eqn. 12 will change to
(VP.TVP = (V + 5V 12 5V + 5V of (V + &V + 2V vV VV + VV SVT V + V VV 23 + -VT + VT + +8 V
lignoring second order terms]
-V'V + d12 (1 V) + 62a v' + 531 V)
(29)
Using Result I we get,
|o\| < 0 / v) + 623 (V''v + 631 (V V)
<10012 + |لاb V V)ll2 + |1ób1 V) [using triangle inequality].
(30)
16

---

Following Eqn. 28 for each edge perturbation in Eqn.
30 we get
sin @ ney (k.)). sin (A.)))
[011 < Σ
80kg 1
nay
1|
ny
(((I)))TT(A))
[(1 (v vv))) ((v (v)))())) 4 VaL V. V.
where T((A) = ((1,2,3), (2, 3, 1), (3,1.
Corollary 1. For a set of consistent directions, Vaji (i.j) E Es, in G3. the absolute change in any eigenvalue of VTV, denoted as [ōλ|, when the directions Vij are perturbed by small rotations RR. with Daj and 60,, > O being the rotation axis and angle, and maj being othogonal to Vks and Vaj for all (i,j,k) k) (A),, is bounded by
|8>1 S
Σ (AII))TT((A)
801)
sin ((RR).A))
[11 [1++vv ((v ()))))))) - 4 V Viyua V5
(3)
where TI(A) ((1.2.)), (2, 1), (3,1,2)), and (kk,)).(k)) the angle between Vas and Vkj-
Proof. The unperturbed directions Vij are coplanar since the directions are consistent. Given that the rotation axis n,y for all the rotations RR are orthogonal Vks and Vaj for all (i.j.k) E (IAA), the rotation axis nij is orthogonal to Vas. for all (i.j), (k, 1) E &s. This ensures that the perturbed directions are still coplanar and, thus, are consistent. Since ny orthogonal to all the directions
Vija the component of directions parallel to the axis are zero, i.c. v O. So, Tn = v (refer to
Equs. 23 and 24 and sin Muy L Hence, using these in Eqn. we get
(k.i).(k.) sin (k..)).(k..)) Also, || ||
||v,l|l for all (i, E Es.
|ō\1 S
Σ
80
ssin cino0.a
(MI)))TT((A)
+1+ ((v + 4 v. viJva vijv,a]
Theorem 2. Consider the bearing based-network of nodes and 3 edges, 9A = (Vs, Es), and the corresponding angle matrix Aga- The conditioning of the matrix Aga signifies the skewness of the triangle formed using the directions E.-
Proof. The determinant of Aça is given as |Aaal= 2 22.1112)) (2.1). (3..)) The determinant will be zero and only if atleast one of the angles in the triangle zero. So, the matrix is non-singular when all the angles are non-zero.
It is known that the determinant is a good measure of the closeness of the matrix to singularity (39] So, we consider the closeness of any two columns in the matrix in terms of the cosine of the angles between the column vectors of Aça. Let aga be the column of Aga corresponding to the edge (i,j) E & In Ga, there is one node common for any pair of edges. So, the cosine of the angle be- (0.)). (t.....
ij
tween any two columns is given as cos <aa a
/ (a. can be clearly seen that the angle at the common node j is small, i.e. $0.0....) - 0 radian, then the two columns are very close or cos L(a ij nearly singular and its condition number high. all values of ((.,).(.)) are sufficiently large, then
ag3) + 1. Small values of d(..). make Aça
cos Laay, ag between any two columns will not be close to 1 making Aça well conditioned with a low condition number. Thus, the condition number of Ag, is reflective of the skewness of the triangle formed from the directions in Es.
Theorem 3. Consider a bearing-bused based network G. with all edges contributing to triplets. The angle matrix Ag, corresponding G, well conditioned if the minimum angle (or equivalently all the angles) in all the triangles formed by the triplets sufficiently large.
17

---

Proof. Let us assume that all the angles in all the triangles formed by the triplets in 9 are sufficiently large. In Ag. no two columns can have exactly the same set of non-zero elements. This is evident since the diagonal entries are 7ero. In real-world scenarios, G is sparse network, and thus Ag is sparse. two columns have exactly the same set of non-zero elements, then it means the two edges share exactly the same set of triplets. This is attained only when the two edges are connecting the same two nodes. But this is not possible since multiple edges between nodes are not allowed. Also, every column will have atleast two non-zero elements since every edge is part of atleast one triplet and angles measured with the common nodes between edges will be present. This makes the angle matrix non- -onnsingular when all the angles in all the triangles are sufficiently large.
1 be the column of Ag corresponding to the Next, we look at the conditioning of the matrix. Let ag edge (i, E &. We check the cosine of the angle between any two columns of Ag to understand the conditioning of Ag. We define triplets to be adjacent if they share a common edge, otherwise they are non-adjann non-adjacent. There are only three cases which arise between any two edges (i,j) and (k, 1). (i.j), (k: 1) E E, and are listed below:
1. (1,5) and (kt, belong to the same triplet,
2. (1,j) and (k; I) belong to adjacent triplets,
3. (1,j) and (k; belong to non-adjacent triplets.
Since each column in Ag represents edge, there are only the three cases, stated above, which occur for the pair of columns. For all three cases, the cosine angles between two columns checked. Let Trp be the set of all triplets in G.
Case 1: Edges (i,j) and (k, 1) belong to the same triplet.
cos <oaaaaa 41
V EprLSDEETT (Ras) + (mn.))
EatkLaper ( (PREnnatnn + Plesaa))
where c E {i.J} n (k, is the common node and ci e U tc) with of + cg are the other two nodes in the triplet.
It can be seen that for this case, if all the angles are sufficiently large, then cos <(a ag) cannot be close to and thus the two columns are not similar.
Case 2: Edges (1 and (k: 1) belong to adjacent triplets tr,, tr2 E Trp.
Part 1: When the edges (i, and (k, 1) share common node of the triplets trl and fr
cos <(a8)a 4
(inoline)) ((no))ines)
EmcassterVy (oos + (anio) . Eagkhaeeer (OR.D + P(As)
where e [1.j] n (k. the common node, cr E E is the common edge between fr1 and tr2, and ci E (i.j} (c), da E ( \ {c) are the other two nodes in the two triplets.
Part II: When the edges (i and (k, I) are connected by the common edge of the triplets trl and tr2:
cos <(aB, k!
EmCLSMEETT (ousnii + (an.m)) " EguhLgeerT ( + ((Ar)
18

---

where (2) E E is the common edge between tr1 and tr such that c2 E fi,j.k, Of with oi & 62 and cit of E ji k. 1 {d, 32) with of * ca2 are the other two nodes in the triplet such that (,, (2, ( E Trp.
It can be seen that for both parts in this case, if all the angles are sufficiently large, then cos <(ay) al) cannot be close 1, and thus the two columns are not similar.
Case 3: Edges (i and (k, 1) belong to non-adjacent triplets 1r1, lr2 E Trp.
By the construction of the matrix using Eqn. there would be no common non-zero elements in the two columns. So,
cos <(a ag') O.
Thus, if all the angles in all the triangles formed by the triplets in 9 are sufficiently large, then the angle matrix Ag is non-singular, and the columns are not similar implying that Ag is well-conditioned.
Theorem 4. Given a bearing-based based network G. with all edges contributing to triplets forming triangles, and its corresponding triplet network GT, the maximal parallet rigid component of G can be determined by the edges in G contributing to the largest connected component of GT.
Proof. It is known that the union of parallel rigid components is parallel rigid if the components
share atleast one edge [2]. Each triplet forming triangle in G is parallel rigid by itself. Also, by construction, each connected component of the triplet network Gr will have shared edges among triplets forming triangles, making every component parallel rigid independently. Thus, the maximal parallel rigid graph of G can be determined by the edges in 9 participating the maximum connected component of Gr.
Proposed Method for Dense Networks
In Sec. of the main paper, we presented the algorithm to remove skewed triangles from sparse network G. Here, we consider the case when G is dense (nearly all possible edges exist), making Ag dense. We provide the method for removing skewed triangles in the following steps.
Step 1: First, construct matrix V with columns the directions in G. The elements of VTV give the dot product between all possible directions. Then, construct the boundary matrix using Eqn. 6 The row and column indices of non-zero elements of the matrix By give us the edge pairs participating in triplets which are the non-zero elements in the angle matrix Ag. So, the zero elements of the matrix B, B,B can be used mask the elements in VTV. V. The net matrix generated Cg.
Step We identify the correct signs for the elements Cg to ensure that the dot products reflect the cosine of the angles of the triangles. We first create a matrix M consisting of m U. (Eqn. 7 as the elements corresponding to the row for (i,j)th edge and column for (As, edge. Then, the Hadamard product (element-wisg multiplication) of Ög and M gives Cg. Once the matrix Cg is formed, we take element-wise inverse cosine to get the angles as the entries and thus the angle matrix Ag-
Step 3: This step is the same as that provided in the main paper.
We summarize the method in Algo.
10 Formulations for Solving Translation Averaging
In Sec. 6 of the main paper, we used two formulations, Revised LUD 41 for the experiments. Here, we provide the optimization problems of those methods for ready reference.
57 and BATA
57
19

---

Algorithm 2: Removal of Skewed Triangles from Dense Networks
Input: Bearing-bar based network 9 = (V, containing only triplets and is parallel rigid, and the triplet list of g.
Output: Bearing- -aased network Gr (Vr; Er), containing only triplets and is parallel rigid, without skewed triangles.
Compute the non-zero elements angle matrix Ag using the boundary matrix B2 (Eqn. 6). Construct the matrix V. whose columns consists of directions Vij. (i.j) E.
Get dot products between all possible directions using VTV.
Use zero elements in B B2 to mask elements in v and denote as Čg.
5 Get the signs of the dot product for non-zero elements of Cg. i.e. mish using Eqn. Construct matrix M using m/j.ki
Perform element- wise multiplication of Cg with M get Cg.
Get the inverse cosine for every element in Cg to get Ag.
9 Extract the angles of the triplets from Ag.
10 Filter out the triplets with the minimum angle less than threshold to get &P = (VF, EF). Construct the triplet network GT using the filtered network 9p.
12 Get the largest connected component of Gr-
13 Get the edges of GF contributing to the largest connected component of Gr to get GF (Vr, EF), which connected and is parallel rigid.
Revised LUD
41
57
(compares relative displacements):
min T T...vv.As,tt.DE
Σ
IT, - T; - -
(31)
(K,))E
Σ T -0 Σ
(T, T Tú, Vij) 1, 20, v(i,)) E
(1J)EE
BATA 57
(compares relative directions):
min
Σ
p (T, TT) 7i - v.5l12)
(32)
(GJ)EE
s.t. Σ T -
Σ
(T - T,, Vij) = 1, mi 2 0, V(i.j) E
NEV
(JJEEE
The zero centroid and dot product constraints in Eqns. 31 and 32 fix the origin and the global seale ambiguities, respectively, denotes the Cauchy loss function. Xij and 7ay are non-negative variables that are ideally equal to baseline and inverse baseline for the edge (i,j), respectively.
11 Additional Results
As mentioned in the main paper, our filtering scheme uses only input directions and does not favour any specific cost function used for translation averaging. In Sec. of of the main paper, we presented the results using BATA [57]. In the following subsection, we present the results using Revised LUD [1 57] and observe a similar trend as seen for the BATA results.
11.1 Outlier-Free Data
In Sec. 6.2 of the main paper, we provided experimental results on outlier-free data. Here, Table [ we provide the details of the IDSfM [55] datasets without outliers. It can be seen that only small fraction of the nodes and edges are removed due to the removal skewed triangles. Also, can be seen that for many datasets, the condition number of the angle matrix (with matrix-2 norm) decreases. For remaining datasets, either increases is similar for both the unfiltered and filtered networks. As mentioned in Sec. 5 of the main paper, perform non-aggressive pruning, due to which some
20

---

Table Details of networks before and after removing skewed triangles from 1DSfM [55] datasets without outliers. #Nrem # rem: No. of nodes and edges removed, K2 (Ag): condition number of the angle matrix with matrix-2 norm, fxtter: time taken remove skewed triangles.
#Nodes
#Edges
# Nem
#Mam
Ag)
fpster (sec)
wio filter
filter
filter
filter
filter
w/ filter
ALM
560
543
7351
7140
17
211
L.c+12
1.0c+12
0.06
ELS
129
128
664
649
15
5.5e405
2.4c405
0.01
GMM
315
5231
5164
4.8c+07
2.5c+08
0.07
MDR
268
248
2545
2361
20
184
5.6c407
2,6c406
0.03
MND
445
439
10338
10175
6
163
7,8c+09
3.5e+09
0.25
317
3250
3065
20
185
9.9c+11
9.5e+11
0.02
ND
1199
1182
26414
25878
17
536
10c+11
1.0c+12
0.28
PDP
344
334
6196
5949
10
247
2.3e+08
3.3e+08
0.19
1844
1795
20880
20100
49
780
1.7e+11
1.2c+11
0.15
ROF
964
8696
8305
30
2.6c+100
2,6c+10
0.07
TOL
450
439
5017
4921
11
96
1.1e+09
5.6e+07
0.04
TFG
3962
3778
51450
49571
184
1879
1.le+12
4.5c+09
0.52
USQ
382
3921
3682
239
3.8c+11
3.3c+11
0.04
VNC 724
705
12176
11901
19
275
2.3e409
3,1e409
0.17
YKM
385
372
4073
3892
13
181
3.1e+08
1.5c+09
0.04
Table 6: Absolute translation errors (in meters) IDSfM SS datasets without outliers using Revised
LUD 57). Removed Node Errors: Errors of removed nodes in the unfiltered network (meters),
tRLUD: D: time taken by Revised LUD.
Dataset
Mean-All
RMS-ATE
Removed Node Errors
(RLUD (sec)
w/o filler
w/ filter
wlo filter
w/ filter
Mean
RMS
ALM
2.5
24
4.0
3,5
9.3
10.9
6
FLS
1.4
1.5
1.8
2.0
1.5
1.5
GMM
5.8
5.3
20.6
24.0
MDR
8.8
7.9
18.1
16.2
26.9
35.9
MND
2.3
2.2
3.2
3.2
4.7
5.7
7
NYC
2.7
2.6
5.6
5.4
5.6
7.4
3
ND
3.5
3.5
5.7
5.5
6.7
8.8
28
PDP
2.6
2.4
3.9
6.3
8.1
PIC
2.9
2.8
6.2
8.2
ROF
16.5
17.3
29.6
30.5
43.4
59.4
TOL.
11.1
10.9
23.3
23.2
42.5
60.1
TFG
7.9
7.2
17.1
16.3
21.8
27.3
63
USQ
5.2
5.0
7.0
6.8
10.7
13.0
VNC
7.6
7.5
11.8
10.8
13.8
18.9
11
YKM
8.2
8.3
21.4
21.1
25.9
44.6
skewed triangles still present. We re-emphasize that non-aggressive pruning still ensures that the nodes are estimated reliably since the nodes are also a part of atleast one triplet, which belongs to the of non-skewed triangles.
we provide the results obtained from Revised LUD. It can be seen that the absolute translation errors decrease for most of the datasets after the removal of skewed triangles. Moreover, errors of the removed nodes in the unfiltered network are high compared to the overall errors, indicating that the removed nodes are not estimated reliably in the unfiltered network. We also observe that the time taken to filter skewed triangles (from T) is ~ 1% of the time taken for translation averaging by Revised LUD (Table which shows the efficiency of Algo. of the main paper.
In Table 6
11.2 Real Data
In Sec. 6.3 of the main paper, we provided the details the datasets and the translation averaging results using BATA [57]. In Table 7 we present the results using Revised LUD. It can be seen that similar to the trend in BATA results, the absolute translation estimates improve for most datasets. Also, the emros of the nodes removed due to filtering are high compared to the overall errors in the unfiltered network, indicating that the filtered nodes are not estimated reliably in the unfiltered network.
21

---

Table 7: Absolute translations errors (in meters) on IDSMM [55] datasets using Revised LUD 41 Removed Node Errors: Errors of removed nodes in the unfiltered network (meters), RRLED: time taken by Revised LUD.
Dataset
Mcan-ATE
RMS-ATE
Removed Node Emors
fRLUD (sce)
w/o filler
w/ filler
w/o filter
w/ filter
Mean
RMS
ALM
4.4
4.3
8.0
7.6
10.5
15.3
12
ELS
20.3
19.6
37.5
42.1
82.6
97.9
GMM
41.9
45.5
60.6
66.6
69.3
86.0
10
MDR
15.6
14.5
29.5
27.5
39.8
43.2
MND
3.9
3.8
5.8
5,8
12.7
13.4
12
NYC
4.5
4.2
8.2
7.3
18.9
24.9
5
ND
4.0
3.9
6.5
6.5
10.1
13.0
68
PDP
7.8
7.7
11.6
11.5
16.5
18.5
11
5.0
4.9
9.2
9.3
14.4
18.0
15.7
32.5
28.7
45.7
58.0
TOL
18.5
17.4
36.7
33.7
69.3
100.9
TFG
19.6
13.1
68.5
25.5
58.8
137.2
214
USQ
12.9
12.3
20.0
19.3
32.8
42.3
9
VNC
9.6
10.2
14.0
15.3
15.4
16.8
19
YKM
20.6
20.0
30.0
29.0
42.1
52.9
Table 8: Details networks after applying IDSIM outlier filter [55] without and with removal of skewed triangles (Algo. # Nrem: # Mrem: No. of nodes and edges removed.
Dataset
#N..
#MM.m
filter
filter
filter
w/o filter
w/ filter
ALM
36
269
416
ELS
2
13
368
427
GMM
76
1062
1470
MDR
32
136
326
MND
3
7
1242
1312
NYC
2
17
251
443
ND
3790
3832
PDP
32
504
827
PIC
101
$229
6443
ROF
17
75
1953
2429
TOL
1
21
339
449
USQ
130
166
1769
1991
VNC
2
2120
2120
YKM
313
389
3223
3872
the datasets to study the complementary benefits of removal skewed triangles after applying an outlier filter. We reiterate that the removal of skewed triangles and outlier edges two distinct aspects of the problem. In Table & provide the network details after applying IDSMM outlier filter without and with the removal of skewed triangles and compare their performance in Table g It can be seen that applying the IDSfM outlier filter and then removing skewed triangles with our filter leads to better translation estimates. Moreover, our filter IDSfM outlier filter removes the nodes which are poorly estimated than only IDSfM outlier filter, as seen from removed node errors in the unfiltered network in Table 9 Since both outliers and skewed triangles different issues, combining filters for both types improves accuracy.
Next, apply IDSIM outlier filter (Algo. 2, 155
In Sec. 5 we mentioned the improved speed using Algo. Algo. compared to the brute force method. In Table [O] compare the time taken by the brute force method to remove skewed triangles to that of our method in Algo.
the brute force method, all three angles in every triangle are computed, and then the skewed triangles are identified and removed. We used 20 threads in parallel for the brute force method, while our method is based only on vectorized operations without any parallelization. be seen that Algo. is significantly faster than the brute force method with 100 times faster for most datasets and 1000 times faster for large scale datasets. This shows the efficiency of Algo. [
Finally, we show the differences in reconstructions obtained without and with using our filter. In Fig. 4 the arch in the Notre Dame reconstruction is misplaced due to improper translation estimates, seen in the lateral view. Using our filter removes such misplaced arch. In Fig, the wall in the
22

---

Table Absolute translations errors (in meters) after applying IDSIM [55 with removal of skewed triangles (Algo. D. Removed Node Errors: Errors of removed nodes in the unfiltered network.
outlier filter without and
Dataset
Meun
ATE
Removed Nodes Errors (Mean)
Removed Nodes Errors (RMS)
filter
filter
filter
wio filter
filter
filter
filter
filter
w/ filter
ALM
4.6
10.5
10.5
12.4
11.8
25.2
23.7
ELS
23.3
21.5
51.2
50,5
15.9
70.6
15.9
96.8
GMM
42.4
41.1
64.2
60.6
20.7
121.1
33.3
158.1
MDR
13.6
28.2
26.0
20.2
48.5
20.2
57.1
MND
4.5
4.3
10.0
9.8
9.5
20.9
15.3
26.5
NYC
6.6
5.2
15.4
12.1
9.4
36.8
9.4
46.4
3.3
6,4
9.0
PDP
7.9
8.0
13,0
13.1
10.1
12.6
11.6
14.9
PIC
5.4
5.2
11.1
10.8
8.3
17.7
13.3
25.6
ROF
14.3
26.8
57.8
57.5
67.9
TOL
15.6
14.3
32.4
29.7
7.3
54.9
7.3
81.2
USQ
9.7
10.9
14.5
18.2
23.6
23.8
37.3
36.2
VNC
10.8
18.1
18.4
13.5
19.2
14.6
25.1
YKM
13.9
26.6
22.7
34.5
34.8
38.2
Table 10: Time taken (in sec) for removal of skewed triangles with brute force method and Algo.
Dataset
Brute Force
Algo
ALM
20.55
0.31
ELS
5.28
0.14
GMM
12.40
0.20
MDR
0,96
0.05
MND
55.18
0.67
NYC
2.16
0.08
ND
1047.90
2.66
PDP
16.07
0.32
PIC
118.46
0.55
ROF
17.87
0.25
TOL
4.27
0.14
THG
1110.40
1.83
USQ
11.33
0.23
72.63
0.65
7.36
0.18
Piazza del Popolo reconstruction is misplaced, but such effect is not seen after applying filter. This reveals that removing skewed triangles helps get more accurate reconstructions.
23

---

(a) Without Algo. 1
(b) With Algo. 1
(c) Reference reconstruction
Figure 4: Lateral view of Notre Dame [55] reconstruction. Improper reconstruction of the arch (red ellipse) obtained due to incorrect estimation of camera translation, which is not present after filtering skewed triangles with our method (Algo. T. Reference reconstruction shows the position the arch.
(a) Without Algo.
(b) With Algo. !
reconstruction. A misplaced wall (red ellipse) obtained due to incorrect estimation of camera translations, which is not present after filtering skewed triangles with our method (Algo.
Figure 5: Plan view of Piazza del Popolo 555
24


Reviews:
[{"review_id": "ef50chyDYZ", "reviewer": "Reviewer_5RZJ", "summary": "The authors propose the sensitivity theory for the Translation Average problem (i.e., input is a large number of coordinate vertex point pairs in relative directions observations and the output is the absolute vertex coordinates with consistent scales), which can be used to efficiently identify the inputs that would make the problem ill-condition (i.e., too small relative direction angles and too large uncertainty to form valid constraints) and remove them to improve the overall algorithm accuracy and convergence speed.", "questions": "1.I completely missed the meaning of what is shown in Figure 1, could author reintroduce it\n2.Whether this uncertainty can be explicitly modeled as uncertainty of Gaussian distribution and incorporated into the optimization framework for solving absolute vertex positions.", "limitations": "1.I think the biggest problem of the paper is that this problem is not a very important problem, first of all, there must be similar methods inside other SFM works to avoid the uncertainty caused by too small parallax. Secondly, whether this extreme case is more common in real scenes is doubtful. Thirdly, if a vertex is observed by more than one other vertex, then the observation in other directions can be used to constraint the absolute vertex solution. So, the authors should explain again why it is an important question which I think may be proved using qualitative experiments.\n2.Some parts of the paper are too obscure, it is suggested to add more intuition descriptions, and visual diagrams to aid understanding.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1.The paper has solid theory, elegant derivation, and creative use of mathematical tools to analyze its uncertainty.\n2.The experiments fully confirm the authors’ claim which effectively improve the accuracy of the algorithm and accelerate the convergence speed.", "weaknesses": "1.The motivation of this article is not sufficient, I can understand that by comparing the direction of the angle we can determine whether it is an ill condition problem or not, but I do not know whether this situation often occurs in practical applications (from the experimental point of view, the improvement of accuracy is very limited).\n2.The article is rather obscure and difficult to understand, especially section4 and section5.\n3.Lack of qualitative experiments to demonstrate the importance of such problems and the superiority of the method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. Fig. 1 of the main paper: We analyze the real data to understand how frequently skewed triangles occur in real data and whether skewed triangles have any relation to the presence of outliers. For this, we provide scatter plots between the minimum angle in a triangle on the x-axis (which reveals the skewness of the triangle, a smaller minimum angle means a more skewed triangle) and the maximum error of the directions in the triangle (which reveals the presence of outlier, a larger maximum error means the presence of outlier). It can be seen that there are many triplets whose minimum angle is close to zero which reveals that the presence of skewed triangles is common (lines 274-276 of the main paper). Also, the scatter plots imply that there is no relation between the skewness of a triangle and a presence of an outlier in a triangle.\n\n2. Uncertainty modelling: Given the nature of input (relative directions) and output (absolute translations), modelling uncertainty on absolute translations as Gaussian may not be reflective of the true uncertainty. Even then, if it is modelled as a Gaussian and incorporated into the optimization routine small inaccuracies in the uncertainty estimates can lead to a drastic change in the output when the triangles are skewed, as an implication of Thm. 1, which is undesirable.\n\n3. Small parallax and occurrence of skewed triangles: Although small parallax is handled in SfM pipelines which could lead to skewed triangles, the existence of skewed triangles is not limited to small parallax. As shown in Fig. R2 (in rebuttal pdf), even cameras with large baselines can lead to skewed triangles. Fig. 1 (of the main paper) also discloses the same where there are many triplets having the minimum angle of the triangle close to zero, denoting the existence of skewed triangles (lines 274-276 of the main paper).\n\n4. Vertex constraint: If a vertex is constrained by atleast two other vertices, which is always the case for parallel rigid networks, we can get a perfect solution when there is no noise in the directions and no numerical errors. But, in practice, the directions are noisy and rounding-off or truncation errors during computation can lead to errors in the solution of the vertex. This is similar in spirit to the conditioning of a matrix while solving a linear system of equations ($Ax=b$ problem), where numerical issues arise when a matrix is not well-conditioned. Thus, constraining the vertex is not adequate to obtain a reliable solution.\n\n5. Intuitive descriptions: Fig. R1 (in rebuttal pdf) shows the conditioning of the triangle under different scenarios, which provides examples of well-conditioned and ill-conditioned triangles. Fig. R2 shows an illustrative example of the existence of such skewed triangles by considering the Alamo dataset, where two different cases of ill-conditioned triangles (one small angle and two small angles in a triangle) are shown.\n\n6. Qualitative results: In Figs. R3 and R4 of the rebuttal pdf, we provide some qualitative results. In Fig. R3, the arch in the Notre Dame reconstruction is misplaced due to improper translation estimates, as seen in the lateral view. Using our filter removes such a misplaced arch. In Fig. R4, the wall in the Piazza del Popolo reconstruction is misplaced, but such an effect is not seen after applying our filter. This reveals that removing skewed triangles improves the reconstruction quality."}, {"review_id": "9maF96t9Cu", "reviewer": "Reviewer_Ah44", "summary": "The translation averaging problem is considered, i.e recover absolute translations from pairwise relative translation directions. The paper focuses on analyzing the change in solution with small changes in the input relative directions. The smallest problem (3 nodes) is initially considered which allows to understand that skewed triangles (triplets) are problematic. In order to move to a general problem, the authors propose to consider the case of a network containing only triplets. It allows them to defined the conditioning of the translation averaging problem as the condition number of the \"angle matrix\". They prove a problem is well conditioned if the minimum angle in all triangles are sufficiently large. Thus, they propose a method to remove such triangles. They experimentally demonstrate that including the proposed method within a classical sfm pipeline allows to obtain better absolute translations, as well as more 3D points triangulated and faster BA.", "questions": "Please see \"weaknesses\"", "limitations": ".", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. Analyzing the sensitivity is a non-trivial problem.\n2. Several theorems are proven that allow to identify skewed triangles as problematic.\n3. The theorems are important to motivate the proposed skewed-triangle-removal algorithm.\n4. The experiments consider both the case of outlier free data and real data.\n5. The paper is well written and easy to read.", "weaknesses": "The proposed algorithm consists in removing information to obtain a problem that is better conditioned. But it is said in the experiments that the skewness of a triangle is not related to the presence of outliers. So if I understood correctly, the removed triangles are not necessarily outliers and thus may contain important information. Thus the proposed algorithm may harm the final reconstruction. Could you please comment on this?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. Important information in removed triangles: The triangles which are filtered using our method are not necessarily outliers. From Tables 1 and 3 of the main paper, it can be seen that the error of the removed nodes are high (Removed Node Errors column) compared to the errors of all the cameras, even if there is no outlier (Table 1), which indicates that the removed nodes are not estimated properly. Since the removed nodes are not reliable, removing such nodes improves the reconstruction, which is validated by more points triangulated and fewer iterations of bundle adjustment in Table 4 of the main paper."}, {"review_id": "I8zsBxMNJX", "reviewer": "Reviewer_vxHs", "summary": "This paper analyzed the sensitivity problem in translation averaging. Built upon the theoretical analysis of the skew triangles in a bearing network, this paper also proposes an efficient algorithm to identify and remove edges that can make the translation averaging problem ill-conditioned. The proposed algorithm is integrated into a global SfM pipeline. The experiments are conducted on the 1DSfM dataset, with different translation averaging solvers (RevisedLUD and BATA) used to solve for global positions. The quantitative results show the proposed algorithm effectively reduced the condition number of the angle matrix, and the translation errors are reduced consistently.", "questions": "I have no more questions regarding the details of the proposed method. My question is on the experiment part. The authors evaluated their method on the 1DSfM dataset, which has been always used in many structure-from-motion methods. However, I think the dataset is out of date though it is very popular a decade ago. I would like to know did the authors evaluate their method on other more realistic datasets, such as some SLAM datasets and aerial datasets.", "limitations": "The limitation is that the proposed algorithm is based on the triplets in the graph. I would like to see an improved version of this paper can be extended to more general graphs. For now, I have to say the method contributes not significantly to the NeurIPS community since it has limited application and is less important than the parallel rigidity analysis.", "rating": 6, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "This paper analyzed the sensitivity problem in translation averaging, which is different from the parallel rigidity problem and has not been considered before. Strict proofs are given for the theorems proposed in the paper. The proposed edge filtering algorithm is very efficient and effective.", "weaknesses": "The main limitation is that the analysis and the proposed algorithm are based on the triplets in the graph, where the requirements are not always held in the real world. The sensitivity analysis in the translation averaging problem is useful, however, is less important than the parallel rigidity problem in my point of view. The paper gives sufficient quantitative results to support their method but is lack qualitative results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. Dataset for evaluation: We use 1DSfM dataset for evaluation. We recompile the input and the ground truth using Colmap (lines 251-254 of the main paper) to get a more reliable reconstruction than the one provided using Bundler. For any dataset which is sequential in nature, like SLAM or aerial datasets, the parallel rigidity of the network is not maintained in general. For instance, estimating scales during colinear translations in SLAM is not feasible based solely on directions as input since infinitely many solutions exist, implying that the network is not parallel rigid and, thus, translation averaging cannot be applied. Also, if the parallel rigid network is extracted in such datasets, the maximal network obtained will be very small compared to the full network, which will make the problem unrealistic.\n\n2. Analysis based on triplets of graph: In general graphs, many different structures occur in 2D and 3D (apart from triangles and structures derived from triangles), each needing an individual analysis in terms of conditioning of the problem. Also, once the properties of each of those structures are known, it will be a combinatorial problem to analyze the sensitivity of the graph based on these structures since general graphs will be a combination of those structures. Considering triplets of a network has many advantages. At first, we only get a single structure i.e. a triangle which can be used as a building block of the network. Next, it is relatively easy to analyze the sensitivity of a triangle since it is planar (Thms. 1 and 2) and then extend it to a triplet network (Thm. 3). Lastly, we can ensure parallel rigidity based only on the network structure (Thm. 4), making it efficient for practical usage. We take a first step to deal with the issue of sensitivity in translation averaging, and using triplet graphs for analysis has shown many insights into the problem.\n\n3. Importance of sensitivity analysis: Sensitivity analysis deals with the reliability of the solution based on the input directions, while parallel rigidity addresses an important issue of the uniqueness of the solution. Sensitivity analysis is similar in spirit to the conditioning of a matrix while solving a linear system of equations ($Ax=b$ problem) where the reliability of a solution is studied. Parallel rigidity can be equivalently described with the algebraic rank of a specific matrix [2], which is similar to the analysis of the uniqueness of a solution given a matrix obtained from a linear system of equations. Both are different aspects of translation averaging that need to be taken care of. In our experiments, we have considered only parallel rigid graphs (lines 256-257 of the main paper). In Tables 1 and 3 of the main paper, it can be seen that removing the triangles which are skewed leads to improvements in the translation estimates. Moreover, the nodes which were removed due to the removal of skewed triangles are not estimated properly, as seen in the column ``Removed Node Errors\" of the tables. Such filtering also leads to improvement of the reconstructions and faster convergence of bundle adjustment (Table 4 of the main paper). So, we believe that sensitivity analysis is an important aspect of translation averaging, which is as important as parallel rigidity and outlier detection."}, {"review_id": "kundabFMLZ", "reviewer": "Reviewer_Jy8r", "summary": "The paper proposed a method to efficiently remove view triplets from a pose graph where the minimum angle falls below a threshold. This is relevant to global SfM algorithms, where such triplets (i.e., triangles) lead to highly uncertain translation scale estimation. The method's performance has been demonstrated on the 1DSfM dataset.", "questions": "- I don't call this a major issue, but it is definitely something that should be discussed in the manuscript. It is unclear why the authors removed skewed triangles instead of deleting a single edge. The choice of triangle removal should be justified.", "limitations": "Discussed.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The proposed method is a nice solution to a simple idea. Even though I feel the description has been written in an overcomplicated way, I like the idea and the method. \n- The problem is relevant to global SfM methods where the translation averaging part is currently one of the main bottlenecks of achieving good accuracy. \n- The proposed solution is ~100 times faster than the trivial brute-force solution.", "weaknesses": "I have two major problems with the proposed method, and both are regarding the provided experiments:\n- First, the proposed method is not compared to any other filters (e.g., 1DSfM), which really makes it hard to understand how much it actually improves the SOTA (if it does). I know that the proposed solver can be easily combined with 1DSfM, but I am not convinced it leads to noticeable improvements in that case. To understand this, the authors should provide results of other filters with and without the proposed one. \n- Second, the authors use the 1DSfM dataset in their experiments where the addressed problem of skewed triangles is not really present. This can be seen in Table 2, which shows that actually only a few edges are removed from the pose graphs (it is surprising that removing such few edges can lead to an improvement in the final global SfM accuracy). I think it would make more sense to showcase the method on datasets where SfM is actually often failing due to the coinciding translation directions, e.g., on KITTI, which presents the trajectory of a moving vehicle. There, scale estimation is challenging. On the 1DSfM dataset, most global methods work reasonably well. Making global SfM work on such cases would have an impact.\n\nWithout comparison to baselines, the paper is a clear rejection to me. In case such a comparison is provided, I am willing to improve my rating. \n\nMinor things/comments:\n- The brute-force solution's timing should be compared to the proposed method. I know that the authors mentioned this in the text, but it would be helpful to show the actual run-time, given that the speed-up is the main contribution of the paper, while accuracy-wise, the brute-force method should be similarly good.\n- L109 \"being the rotation axis angle\" -> \"being the rotation axis and angle respectively\"\n- Fig.1 How can the minimum angle in a triangle be close to 180°? Maybe I misunderstood the figure.\n- L294 BATA is first mentioned here (aside from a half sentence in the introduction). It should be written down that BATA is used for estimating the global positions from the directions.\n- Eq.2 is quite something that could be visualized by a figure and it would help a lot in understanding it.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. Results with 1DSfM filter: 1DSfM filter is designed to remove outlier edges while our method removes skewed triangles, which are two distinct aspects of the problem. We apply 1DSfM and then compare the solutions without and with applying our filter on real data. In Table R1 of the rebuttal pdf, we provide the comparison. It can be seen that applying both the 1DSfM filter and our filter leads to the overall best accuracy. Moreover, the improvements are significant for the datasets where the performance is better, while the accuracy is almost similar for the datasets where improvement is not seen. As noted earlier, since both outliers and skewed triangles are distinct issues, combining filters for both types leads to improved accuracy.\n\n2. 1DSfM dataset for evaluation: In Fig. R2 of the rebuttal pdf, we show an illustrative example of the existence of such skewed triangles in the SfM problem on Alamo, which is a part of the 1DSfM dataset. Occurrences of skewed triangles are common in SfM, which is depicted in Fig. 1 of the main paper, where the scatter plots show many triplets having minimum angles of the triangles (represented on the x-axis) close to zero (lines 274-276 of the main paper). We adopt a non-aggressive strategy to prune the network (lines 238-241 of the main paper) where we retain all the edges of the network ($\\mathcal{E}_{ret}$), which are a part of non-skewed triangles. So, even if an edge is a part of both non-skewed and skewed triangles, it will be retained. In this process, only those nodes are retained, which are a part of atleast one triplet which belongs to the set of non-skewed triangles (lines 244-248 of the main paper). Thus, relatively few edges are removed compared to the total edges participating in the skewed triangles. In cases where the directions coincide, like KITTI, the network is not parallel rigid, which means no unique solution exists. Thus, translation averaging cannot be used in such scenarios.\n\n3. Time comparison with brute-force method: The timing of the brute-force method will be added in the supplementary material.\n\n4. Minimum angle close to $180^{\\circ}$: Fig. 1 of the main paper shows the scatter plots on real data, which contains outliers. Some triplets containing outliers do not form a triangle, and directions in such triplets are far away from being on a plane. Such triplets do not satisfy the constraint of a triangle, i.e. the sum of angles equal to $180^{\\circ}$.\n\n5. Visualizing Eqn. 2: In Fig. R1 (in the rebuttal pdf), we show an intuitive explanation of the conditioning of a triangle under different scenarios. For a well-conditioned triangle, where no angle is close to zero, a small change in direction (green to red) leads to a small change in the absolute translation. But for an ill-conditioned triangle, where atleast one angle is close to zero, a small change in direction leads to a large change in the absolute translation.\n\n6. Removal of skewed triangles: An edge can participate in more than one triplet. When a triangle is identified as skewed, it is marked for removal. Specifically, identifying which edges are leading to a skewed triangle can be time consuming. We adopt an efficient approach where we classify triangles as skewed or non-skewed. Since an edge can participate in both non-skewed and skewed triangles, the intersection of edges participating in the two classes of triangles is not empty. Now, we can remove the edges either participating in skewed triangles (aggressive) or retain the edges participating in non-skewed triangles (non-aggressive) (lines 238-241 of the main paper). We employ the non-aggressive removal of edges (lines 244-248 of the main paper). So, in effect, we only delete edges without explicitly maintaining a set of edges participating in skewed triangles and do not delete all the edges of the skewed triangles."}]

Author rebuttal:
We thank the reviewers for their comments. In this section, we provide descriptions for the table and figures presented in the rebuttal pdf (which have the prefix ``R" in their enumeration) and address individual concerns in the individual rebuttal sections.

1. Results with 1DSfM filter (Table R1): Our method removes skewed triangles, while 1DSfM is designed to remove outlier edges, both of which are two distinct aspects of the problem. We apply the 1DSfM filter on real data and then compare without and with our filter in Table R1 using BATA [56]. It can be seen that after applying the 1DSfM filter and then our filter, the translations are estimated in a better manner.  Moreover, our filter + 1DSfM filter removes the nodes which are poorly estimated than only 1DSfM filter, as seen from removed node errors in the unfiltered network in Table R1. Since both outliers and skewed triangles are different issues, combining filters for both types improves accuracy.

2. Practical applicability (Fig. 1 in main paper and Figs. R1, R2): In Fig. R1, we show conditioning of the triangle under different scenarios, with green and red depicting the unperturbed and perturbed directions, respectively. For a well-conditioned triangle, a small change in direction leads to a small change in the absolute translation. But for an ill-conditioned triangle, a small change in the direction leads to a large change in the absolute translation. Fig. R1(a) shows a well-conditioned triangle, Fig R1(b) shows a triangle with one small angle due to which it is ill-conditioned and Fig R1(c) shows a triangle with two small angles making it ill-conditioned (these conditions are also inferred by Thm. 1). Fig. R2 shows an illustrative example of the existence of such skewed triangles in the SfM problem. For the Alamo dataset, most images capture the front part of the museum, and thus, the cameras are densely connected in the network. The BLUE triangle depicts a triplet which is Type-I ill-conditioned triangle and the GREEN triangle shows Type-II ill-conditioned triangle. In Fig. 1 of the main paper, it can be seen from the scatter plots that there are many triplets whose minimum angle (represented on x-axis) is close to zero (lines 274-276 of the main paper). This reveals that the existence of skewed triangles is very common in unordered image collections and thus affects the ability to carry out accurate reconstructions.

3. Qualitative results (Figs. R3, R4): We provide some qualitative results in the rebuttal pdf. In Fig. R3, the arch in the Notre Dame reconstruction is misplaced due to improper translation estimates, as seen in the lateral view. Using our filter removes such a misplaced arch. In Fig. R4, the wall in the Piazza del Popolo reconstruction is misplaced, but such an effect is not seen after applying our filter. This reveals that removing skewed triangles helps get more accurate reconstructions, which is also revealed by more points triangulated for most datasets, as shown in Table 4 of the main paper. 

Meta-review: This submission received the scores BR, A, WA, BA

All the reviewers are impressed by the theory.

The negative reviewer (BR) proposed to reject the paper because s/he thought the problem was not important, however the other reviewers thought otherwise.

Two reviewers (WA, BA) had some concerns about the experiments even after rebuttal, however their concerns are minor enough for them to still recommend acceptance. The authors should make an effort to fix these aspects and to emphasize the importance of the problem, as this will make the paper stronger.
Decision: Accept (poster)