Toroidal Constraints for Two-Point Localization under High Outlier Ratios
Federico Camposeco1

Torsten Sattler1 Andrea Cohen1 Andreas Geiger1,2 Marc Pollefeys1
1
Department of Computer Science, ETH Zürich
2
Autonomous Vision Group, MPI for Intelligent Systems Tübingen{federico.camposeco,torsten.sattler,andreas.geiger,marc.pollefeys}@inf.ethz.ch

Abstract
Localizing a query image against a 3D model at large
scale is a hard problem, since 2D-3D matches become more
and more ambiguous as the model size increases. This creates a need for pose estimation strategies that can handle very low inlier ratios. In this paper, we draw new insights on the geometric information available from the 2D3D matching process. As modern descriptors are not invariant against large variations in viewpoint, we are able to findthe rays in space used to triangulate a given point that areclosest to a query descriptor. It is well known that two correspondences constrain the camera to lie on the surface ofa torus. Adding the knowledge of direction of triangulation,
we are able to approximate the position of the camera fromtwo matches alone. We derive a geometric solver1 that cancompute this position in under 1 microsecond. Using thissolver, we propose a simple yet powerful outlier filter whichscales quadratically in the number of matches. We validate
the accuracy of our solver and demonstrate the usefulnessof our method in real world settings.

1. Introduction
Estimating the pose of a query image from a set of
2D-3D matches is a central task in image-based localization [4, 15, 21, 22, 26, 28], with many applications in, e.g.,
Structure-from-Motion (SfM) [12, 24, 25, 27], simultaneous
localization and mapping (SLAM) [3, 5], augmented reality [1, 17], or camera calibration [2]. Wrong 2D-3D correspondences are typically handled through RANSAC [9] aslong as the percentage of such outliers among all matches is
not too large.
Image-based localization approaches establish 2D-3D
correspondences by matching descriptors extracted fromthe query image (e.g., SIFT [16]) against descriptors associated with the 3D model points. However, at large scale or in
1 MATLAB sample code available atresearch/toroidal-constraints/

www.cvg.ethz.ch/complex scenes with many repetitive elements, establishing
2D-3D correspondences becomes a challenging task due tothe inherent ambiguities of the local appearance [15]. As it
becomes harder to distinguish between correct and incorrect
matches based on local descriptors alone [15], localization
algorithms must be able to cope with large outlier ratios inorder to enable reliable pose estimation. This in turn createsa strong need for developing efficient outlier filtering strategies which are able to identify and remove wrong matches.
In this paper, we derive a new previously unused geometric constraint that can aid large-scale localization. Exploiting this constraint, we present a novel filtering strategy that can cope with arbitrary outlier ratios, while retaining a runtime that scales quadratically with the numberof matches. Previous approaches either require knowledge
about the gravity direction in combination with a prior on
camera height [26, 28] or knowledge about the full camera
orientation [13]. In contrast, our approach does not depend
on such external information and can approximate the full
6 DOF pose from just two 2D-3D correspondences. For
our application, however, we only use the position from thepose to efficiently prune outliers (c.f . Section 3.5). Whereas
most reconstruction methods consider viewpoint variance[18] of descriptors as a weakness, we view it as a strength
useful to infer the viewpoint of the camera.
Our main observation is that, during the SfM processused to generate a 3D model, each 3D point is associatedwith the descriptors of the image features from which it
was triangulated. Thus, each of these descriptors is associated with the viewing direction under which the point wasobserved. Empirically, we found that the best matching descriptor of a 3D point for a given 2D feature provides agood approximation to the viewing direction of the query
image, c.f . Section 3.3 and Fig. 1, typically being within
10◦ of the closest match. We call this viewing direction
constraint the triangulation constraint. Additionally, given
two 2D-3D matches, it is known that the camera will lie on
the surface of a torus [7]. The toroidal constraint combinedwith the triangulation constraint allows us to formulate asolver that estimates the position of the camera from only

2. Related Work

Figure 1. Novel Geometric Information. For each query descriptor, dquery, we find the closest descriptor inside the track that proi
duced the 3D point pi . We do this for each match in S, yielding ouraugmented match set S̄ (see Section 3.3 for more details). Givena query measurement, bi and its matched 3D point pi we are able
to find an estimate of its closest ray in 3D by matching against all
images that triangulated pi . Thus, we constrain the query camera
position to lie near ray qinn .

two matches. While the resulting positions are approximations, they are accurate enough to enable efficient outlier
detection, which is a key task for pose estimation at large
scale.
This paper makes the following contributions: (i) We derive a novel two-point formulation to estimate the absolute
position of the camera which incorporates prior informationon the viewing directions. To the best of our knowledge,
ours is the first pose solver which directly incorporates thistype of information into the pose estimation task. (ii) While
computing an exact solution to this problem analyticallyis hard, we derive an approximate solver and empiricallyshow that it is able to recover near-optimal solutions. As
our solver only requires solving two quadratic problems, it
is very efficient with run-times of around ∼ 1µs. (iii) Basedon our solver, we propose a novel outlier filter, whose runtime is independent of the outlier ratio. Compared to previous approaches, it does not make any assumptions on theavailability of external information [13, 26, 28]. Besides, it
is significantly simpler to implement than [26, 28] and has
a lower computational complexity than [13, 26]. (iv) Lastly,
we show that the novel constraint is indeed meaningful forthe localization task by comparing its performance as an
outlier filter to the state-of-the-art.
The rest of this paper is organized as follows: Section 2
provides an overview of the related work. Section 3.1 introduces the problem of large-scale image-based localizationin the presence of large outlier ratios. Sections 3.2 and 3.3
provide a description of the toroidal and triangulation constraints. Section 3.4 describes our geometric solver which isthen used to design an efficient outlier filter in Section 3.5.
Section 4 validates our proposed method on both synthetic
and real-world datasets.

Recent work on scalable image-based localization has
dealt with ambiguities in the matching stage by relaxing
the matching criterion [15, 21, 26, 28]. They handle the resulting larger amount of wrong matches by detecting andfiltering incorrect correspondences before pose estimation.
These methods can be divided into approaches based on covisibility [15, 21, 22] and geometric reasoning [26, 28]. The
method proposed in this paper falls into the second category.
Visibility-based methods exploit the fact that the SfM process provides information about which 3D points can beobserved together. This information is encoded in the bipartite visibility graph [14] and the 2D-3D matches determine sets of connected components in this graph. Sattler
et al. [22] use only those correspondences falling into thelargest connected component for pose estimation. Rather
than using a single component, [21] computes poses frommultiple subsets of matches and then select the pose withthe largest number of inliers. Instead of deciding on a fixed
subset before pose estimation, Li et al. adopt a RANSAC
sampler to avoid computing a pose from points not covisible together [15]. Visibility filtering usually reduces thenumber of RANSAC iterations required to ensure a good
estimate is found. Yet, it does not remove the dependency
of RANSAC’s run-time on the outlier ratio.
Geometry-based approaches determine a subset ofmatches whose 3D points are geometrically consistent with
their corresponding 2D features. The main motivation isto design an approach whose run-time depends only on thenumber of matches and not on the outlier ratio. One way
to select such a subset are branch-and-bound algorithms[6,8,20], which often come with guarantees on the optimality of their solution. However, their algorithmic complexity only allows them to handle a relatively small number ofmatches given a limited computational budget.
Recently, more efficient outlier filters have been proposed that rely on additional information. Given the fullorientation of a camera, the method from Larsson et al. rejects outliers in O(n2 log n) [13], where n is the number ofmatches. They obtain a bound on the maximum number of
inliers for each single match. This, in turn, enables themto identify and remove correspondences that cannot be partof the maximum inlier set. Unfortunately, their method requires to repeatably determine the intersection between twocones, which is computationally involved. Similar to ourapproach, Larsson et al. thus employ an approximation algorithm that is more efficient to compute.
Svärm et al. [26] present an outlier filter based on a
known gravity direction and an estimate of the camera’sheight above ground. As a result, they can model pose estimation as a 2D registration problem. Similar to Larsson
et al., the approach of [26] determines the maximum number of correspondences geometrically consistent with eachmatch. Matches are rejected if this number falls below anadaptive threshold. While both, Svärm et al. and Larsson
et al., require O(n2 log n) steps, our approach has a computational complexity of O(n2 ). At the same time, it ismore general as it neither requires information about the fullcamera orientation, the gravity direction, nor the camera’sheight.
Following the same setup as [26], Zeisl et al. propose afiltering strategy based on voting that has an optimal asymptotic complexity of O(n) [28]. However, their voting strategy is rather involved, both in terms of implementation andconstant factors contributing to the running time. In order toaccelerate their method, they exploit additional constraints
provided by the local feature geometry, e.g., the scale andorientation of a 2D feature, as well as viewing direction constraints in order to reject matches before voting.
In contrast to Svärm et al. and Zeisl et al., our proposed
approach is both very efficient to compute and simple toimplement. It does not require any additional assumptions.
Instead, it leverages information that is readily available
but has not been previously exploited. This new insight allows us to formulate new constraints that can be efficiently
used in a simple setting, therefore avoiding more involved
schemes as the ones introduced by Zeisl et al. Our experiments show that we can achieve performance similar to [26]and [28] while maintaining low computational complexity.

3. Localization Using Two Points And Their
Directions of Triangulation
In the following, we first formulate the problem and provide a description of the toroidal and triangulation constraints. We then describe our geometric solver and the proposed outlier filter based on this solver.

3.1. Problem Formulation
Our aim is to localize an image of a scene given a SfM
model. To this end, we assume a set of 2D-3D correspondences S = {bi ↔ pi }N
i = O ∪ I, where O ∩ I = ∅denote the unknown sets of outlier and inlier matches. The
set {bi }Ni denotes the putative image projections of thematched landmarks {pi }N
i . Since we deal with calibrated
image features only, we view bi as a 3D unit vector in thecamera frame of reference that emanates from its center.
To identify the inlier set I and refine the pose from all inlier matches, the most popular approach is to use P3P plus
RANSAC [9]. However, as noted before, a large outlier ratio |O|/|S| greatly reduces the chances of finding a correctpose with such methods. This is because RANSAC-stylemethods are prone to getting stuck in local minima (i.e.,they do not converge to the optimal |I|).
Ideally, one would exhaustively search through all
triplets in S and vote for the pose with the highest consen-

sus. However, thisis prohibitively slow for most applications as up to 4 N3 = 2/3 N 3 poses (P3P returns up to 4
feasible solutions) need to be evaluated. The goal of ourapproach is to drastically reduce |O|, so that pose recovery
becomes an easier problem. We will now derive a solution which prunes the vast majority of outliers and scales
quadratically with the number of matches.

3.2. Toroidal Constraints
Given two matches m0 , m1 ∈ S, our goal is to find thecamera center location C represented in world frame coordinates. Let Π0 denote the 3D plane defined by the two
matched 3D points p0 and p1 , as well as the camera center
C. Since the angle θ between the rays of the features in
the camera frame θ = ](b0 , b1 ) is known from their pixel
position and the calibration parameters, the location of C isconstrained to lie on a circle (c.f . Fig. 2a). However, thiscircular constraint is still fulfilled if we rotate C around theline connecting p0 and p1 by any angle u (c.f . Fig. 2b).
Thus, C must lie on the surface of a torus T2 , yielding(R + r cos v) cos u(1)
C(u, v) =  (R + r cos v) sin u  ∈ T2 .
r sin v
Here v is the angle which parameterizes the circle, R denotes the major radius of the torus (corresponding to the
distance from the origin to the center of the circle) and r is
the radius of the circle. As it can be seen from Fig. 2, in thisparticular setting the torus will always be self-intersecting(i.e. r > R) since the axis of revolution always includes
two points on the circle. This yields sections of the torus
on which the camera can lie; if θ > π/2 the camera will
be constrained to the inner surface of the torus, otherwise it
will lie on the outside surface [7].
Without loss of generality, we make the implict assumption that p0 and p1 are aligned with the z-axis, and that their
midpoint is at the origin. This can be trivially achieved by
pre-rotating and translating p0 and p1 by a suitable amount.
After the location of the camera on T2 has been found, we
transform it back to the world frame of reference.
Without any additional constraints, the exact location of
the camera center C on the two-dimensional manifold T2
is unknown. In the following, we make use of previously
unutilized information from the matching process to find alikely location for C on the surface of the torus.

3.3. Triangulation-Ray Constraints
Any point pi of the SfM model has been obtained bytriangulating a set of M > 1 image measurements {qji }Mjwith associated descriptors Di = {dij }M
j , where we represent any qji as a 3D vector of unit length. Alternatively,
qji can be regarded as a vector emanating from pi towards

Figure 2. Toroidal Constraints From Two Matches. The circle in (a) describes the possible locations for C given two 2D-3D
correspondences. The camera is located on the red arc for anglesθ < π/2 and on the green arc otherwise. The z-axis is the axis ofrevolution for this circular constraint, yielding T2 , as seen in (b).
The unit vectors q0 and q1 are the directions from the points p0 , p1
to the cameras whose descriptor was matched to the query image
descriptors.

Figure 4. Approximate Solution for Camera Position. The cost
optimization on T2 is approximated by a two step procedure: finding the angle parameterized by u, then locating the point C(v) bysolving two square roots. The solver we propose minimizes theangles highlighted in green (b).

taken from exactly the same pose as a camera in the SfM
model.
Our goal is to find a point on the torus whose location iscompatible with the triangulation directions q0 and q1 . We
model the variation in Di as a product of viewpoint changesolely. Thus, the most compatible location on T2 for C
minimizes the angular distance, E, to both q0 and q1 :2

2

E(u, v) = ] (P0 (u, v), q0 ) + ] (P1 (u, v), q1 ) ,Figure 3. Accuracy of the Matched Ray. To validate our new
constraint, we show the cumulative density function of the angularerror between bk and qk for a real dataset with ground truth [23].

the center of camera j (c.f . Fig. 2b). For localization, most
methods exploit a single descriptor derived from this set,e.g., Diavg = mean(Di ) under the assumption that the variation in Di is small enough for this to be a valid approximation. However, we make the observation that the variability
within Di can be exploited to obtain previously unused but
geometrically meaningful information.
For a given match (bi ↔ pi ) ∈ S, we denote the associated query descriptor as dquery. We find the closestidescriptor to dquery
againstallM
descriptors
that generi
ated pi , i.e., we find dnn
∈
D
that
is
closestin descripii
tor space to dquery
(c.f
.
Fig.
1).
We
empiricallyobservedinnthat for SfM ray measurements associated with dnn
i , qiis close in space to the ray which has produced our querymeasurement bi (c.f . Fig. 3). Thus, we obtain the directionof triangulation for each observed feature match bi ↔ qi
(where for simplicity qi = qinn ). This augments the setof matches with noisy but informative orientation estimatesS̄ = {bi ↔ (pi , qi )}N
i .
Given two of these augmented matches, m̄0 and m̄1 , weaim to find C(u, v) ∈ T2 such that the angular distance to q0
and q1 is minimized. Notice that we do not strictly enforce
bi to be coincident with qi , as this is only possible for the
unrealistic noise-free case in which each query image was(2)

where Pi (u, v) = C(u, v) − pi , i.e., the vector from pi to C
and C(u, v) ∈ T, c.f . Fig. 4b.

3.4. A Geometric Solver
Minimizing the cost in Eq. 2 results in multiple local
minima. In particular, we are interested in two local minima, one located on the inside and the other on the outside of
the self-intersecting torus. Of these two, we select the one
which best fulfills the angular constraint of θ = ](b0 , b1 )as described in Section 3.2 (c.f . Fig. 2a). Since Eq. 2 needs
to be minimized for all N (N − 1)/2 match pairs, we needan efficient solver which yields a feasible solution within a
few microseconds. Extrema of the initial cost happen when
the gradient of the cost equals zero, and we can use this tobuild a system of polynomial equations. We initially pursued a Gröbner basis approach that would solve the systemof polynomial equations given by the gradient of the cost.
Depending on the parameterization (Lagrangian or trigonometric), we found this to yield between 24 and 32 solutions
by using Macaulay2 [10]. Therefore, a respective 24 to
32 square matrix needs to be eigen-decomposed, leading toruntimes of more than 2 milliseconds. Although this yields
the true global optima of Eq. 2, the runtime and number ofsolutions to consider render this method unpractical.
We thus propose an approximate solution by solving the
problem in two steps. By inspecting the projection of thetorus onto the xy-plane (c.f . Fig. 4a), one can see that both

triangulation rays emanate from the origin. Thus, a reasonable approximation û of the optimal angle u is the averageof the angles formed by the projections of q0 and q1 onto
the xy-plane.
Assuming the angle u around the z-axis to be known,
Eq. 2 can be reduced to a one dimensional cost function
E(v) =X arctan

i=0,1

qi,z
qi,x̂




− arctan

Pi,z
Px

(3)

2

X ∗ = arg min arctan (x) = arg min x2 ,1 + si xi (v),(6)

where si = qi,z /qi,x̂ and xi (v) = Pi,z /Px are the slopes of
the rays and the unknown point on the circle, respectively.
Setting the derivative of Eq. 6 w.r.t. v equal to zero we obtain an equation in terms of cos v and sin v,
X µi ρi φi∂ Ê
== 0 , where
∂v
ξi
i=0,1

µi = rs2i cos v + r cos v + Rs2i + R ,ρi = (pi,z sin v + r + R cos v) ,Complexwhere
λ1 = κ − τ,
λ2 = 2r(s0 + s1 )(p1z (s1 − s0 ) + Rs0 s1 + R),(8b)

λ3 = κ + τandκ = R2 s20 s21 − 1 + 4s0 s1 − s21 + 1 +
r2 s20 2s21 + 1 + 2s0 s1 + s21 + 2 −2Rp1z s20 s1 − s0 s21 + s0 − s1(8c)

τ = r(s0 s1 − 1)(p1z (s1 − s0 ) + Rs0 s1 + R) .

and dropping the arctan yields

i=0,1

(8a)

(5)

x

X  si − xi (v) 2

Valid roots: v ,v((s1 + s0 + t(4s0 s1 − 2) − t2 (s0 + s1)) · (fc (t))|{z
} | {z }Valid roots: v3 ,v4Knowing thatÊ(v) =

Invalid Roots}|{ z}| 1 2 {z
23
0 = (r + R + t (R − r)) · (λ1 + λ2 t + λ3 t2 ) ·2where qi,x̂ is the projection of the x coordinate of qi onto
the plane defined by û and the z-axis, denoted Π0 . Px =R + r cos v and Pi,z = r sin v − pi,z .
We can further simplify Eq. 3 by leveraging the fact that
α1 + α2arctan (α1 ) + arctan (α2 ) = arctan. (4)1 − α1 α2x

half-angle tangent substitution (i.e., t = tan (v/2)), Eq. 7
factors as(7)

φi = (rsi cos v − r sin v + Rsi − pi,z ) ,ξi = (si pi,z + rsi sin v + r cos v + R) 3 .
Groebner basis analysis (c.f . supplementary document)shows that Eq. 7 has at most 12 solutions. This is a great
improvement upon the 32 solutions of the initial problem.
Further, it turns out that 6 of the obtained 12 solutions
correspond to a repeated root, namely a root for an invalid
solution. This repeated root, r cos (v) = R, corresponds tothe solution coincident with the points p0 or p1 and arises
from the fact that at that point, Px is zero and thus the angle
is undefined. Manipulating the equations algebraically allows us to factor out (r cos (v) − R)3 , effectively removing
6 roots from the 12 algebraically possible ones (note that forthis factor, v and −v are both feasible solutions). Using the

The factor fc (t) in Eq. 8a is a term quadratic in t whoseroots are always complex. For details on the derivation, we
refer the reader to the supplementary document.
This approximate closed form solution is several ordersof magnitude faster w.r.t. the former methods, since it only
requires the solution of two quadratic polynomials in t. We
obtain a single solution by taking the minimum cost solution satisfying the inside/outside constraint of the camera.
Even though the proposed solver finds only an approximate
solution, albeit a pretty accurate one (c.f ., Fig. 6), this is
acceptable since we are only interested in a rough and fastestimate of the camera position to efficiently prune outliers.
The complete procedure for computing an estimate of thecamera position from two matches is given in Algorithm 1.
Algorithm 1 Compute C given bi ↔ (pi , qi )Require: Points p0 , p1 , rays q0 , q1 , measurements b0 , b1
1: Compute rotation and translation T s.t. Tp̂i = pi are on
the z-axis and their midpoint is the origin.
2: û ← (arctan(q0,y /q0,x ) + arctan(q1,y /q1,x ))/2
3: θ ← arccos(b0 · b1 )4: Compute V = {vi }4i=1 using Eq. 8a.
5: for all vi ∈ V do
6:
if vi on the side of the circle constrained by θ (Fig. 2)then7:Compute cost: costi ← E(û, vi ) using Eq. 2
8:end if
9: end for
10: v ∗ ← solution with minimum costi
11: return T−1 C(û, v ∗ )3.5. The Outlier Filter
For any pair of matches, we can follow the efficient procedure outlined in the previous section in order to obtain an
estimate of the camera position. Since our aim is to deal
with cases that have very low inlier ratios, we want to use
every possible match pair in order to fully explore the setof possible camera poses. A naı̈ve approach would simply
consider all Q = N (N − 1)/2 matching pairs, compute a
position estimate, and later cluster on the space of 3D positions. However, this method has a few drawbacks. Firstof all, for images with a very high number of feature detections, Q might be larger than 10 million pairs. Thus, clustering such a dense population of position hypotheses could
prove difficult. Second, clustering in 3D space would not
identify the inlier set required for pose refinement. In thispaper we therefore take a different approach by individually
scoring each 2D-3D match.
We use 3D occupancy information to discard gross outliers by using an octree, which is particularly suited for images with a very large number of matches. To this end, westore all Q position hypotheses in an octree of fixed depth.
Because of its fixed depth, the structure itself helps us discard position hypotheses far from a principal cluster. After
generating all hypotheses, we traverse the tree once to findthe most populated voxel, denoted V ∗ . For all remaining
operations, we only use point hypotheses that lie inside V ∗ .
After computing all camera hypotheses, for each matchmi ∈ S we have a set of NV position hypotheses in whichmatch mi participated and that lie inside V ∗ , denoted asV
Ci = {Cji }N
j . Using these putative camera positions, we
compute NV inverse depth measurements Wi = {kpi −V
Cj k−1 }N(c.f . Fig. 5) and use this to derive an inlier scorejfor each match individually. Given that outlier matches willproduce camera positions that are not clustered around any
particular point in space, the inverse depth measurements
they produce will not cluster around the true inverse depthof the feature pi . Rather, the inverse depths produced byoutliers will cluster around zero (since many outliers will
result in positions very far from the true position). On theother hand, an inlier match mi will necessarily present two
peaks, one near zero z0 (as produced when mi was pairedwith an outlier match), and a peak around the true inverse
depth value z1 (c.f . Fig. 5).
Our goal is therefore to find the number of inverse depth
measurements that are part of the true depth cluster, z1 . If
the support of the z1 cluster |Wiz1 | is high, then there is highevidence that the point pi is geometrically sound, i.e., it is aninlier. We thus define the score of the i-th match as the ratio|Wiz1 |/|Wi |. To produce the scores we then only need topartition Wi into two clusters. We use k-means with k = 2
for this purpose. For such simple one-dimensional twoclass clustering problems, k-means can be approximatedwith linear complexity by setting a fixed number of itera-

Figure 5. Inverse Depth Distribution for Inliers and Outliers.
Shown in blue are the inverse depths that were classified as outliers
and in orange the inliers, with their respective centroids z0 and z1 .
For inliers, the support for z1 will be high (a). On the other hand,the support of z1 for outliers will be very low (b). The data used
for this visualization was produced from a single image from [23].

Algorithm 2 Produce a score for match mi ∈ S
VRequire: A set of NV positions Ci = {Cji }N
ji
1: for all Cj ∈ Ci do
2:
Wji ← kpi − Cji k−1
3: end for
4: Initialize cluster centroids: z0 ← 0 and z1 ← 1
5: Run k-means over all Wjiz
6: Wi 0 ← members of cluster z0z
7: Wi 1 ← members of cluster z1z
8: return |Wi 1 |/|Wi |tions (equal to 20 for our case), and will converge in approximately 1µs per match.
The output of the procedure outlined above and summarized in Algorithm 2 is thus a score for each input match.
Notice that the position computation and the inverse depth
clustering are fully parallelizeable. Having obtained a setof scores, we can use a threshold tid ∈ [0, 1] to discard outliers, or leverage the statistics of the scores to keep a prescribed number of matches. From the remaining set, we run
RANSAC with P3P [11] to get a final pose estimate. Since
the outlier ratio of the remaining filtered set of matches ismuch lower compared to the initial set, RANSAC converges
quickly to the correct solution.

Figure 6. Accuracy of the Geometric Solver. The log10 angularerror in degrees of our approximate geometric solver against the
ground truth method, i.e., solving the cost in Eq. 2 using gradientdescent and using multiple initializations on a 100×100 grid. The
strongest approximation we make, that of the u angle, suffers mostfrom error. However, v has a very low approximation error.

Figure 8. Efficacy of our Method as an Outlier Filter. For aprescribed threshold tid , the inlier ratio can be increased althoughsome number of true inliers might be discarded. This graph showssuch trade-off when averaging inlier-ratio and recall for the dataset
in [23]. E.g., given a threshold we can get 80% of inliers with over
50% inlier ratio. A high threshold will reject the vast majority ofoutliers but might reject true inliers, and conversely for a low tid
threshold.

Figure 7. Synthetic Evaluation of the Filter. Precision and recall curves of the filter for different outlier ratios compared against
RANSAC. Precision is computed as number of correctly classified
inliers (CCI) over number of classified inliers. Recall is measured
as CCI over total number of true inliers.

4. Experiments
4.1. Synthetic Evaluation of the Solver
In order to validate the solver described in Section 3, wecompare the positions computed by our solver to the exact solution provided by an exhaustively initialized GaussNewton minimization. For this, we generate 106 random
synthetic scenes in the following manner. We sample two
3D points, p0 and p1 , from a uniform distribution inside the
cube [0, 10]3 . Afterwards, a random camera location, C ischosen from the same distribution and translated 10 units
away of the cube in the Z direction. We then simulate noisy
triangulation-ray matches by adding Gaussian noise to theunit vectors qi = (C − pi )/kC − pi k, i = 0, 1. The noise
was added to a plane perpendicular to qi with a standard deviation of 0.5. We have empirically observed that, for inlier
matches, these are adequate simulation parameters.
Fig. 6 shows the error between the ground truth estimator and our solver, which is statistically negligible whencompared to the angular distance from qi to bi .
Additionally, in order to validate the efficacy of our filter
as an outlier filter, we generate 3000 2D-3D matches andthen inject a varying amount of outliers. The performanceof our filter and of simple RANSAC were then comparedto validate the usefulness of the filter as an outlier rejection

Figure 9. Depth Range. Left: View with inlier matches in red.
Right: 3D model with inlier points (red) and camera in pink.

scheme. As it can be seen in Fig. 7, the filter is quite efficient for high outlier ratios.

4.2. Real-World Evaluation
In order to further validate our method and assess its performance w.r.t. the state of the art, we conduct experiments
on a publicly available real-world dataset. The dataset weused is the Dubrovnik dataset from [25], which consists of
800 query images with SIFT [16] features that are matchedagainst an SfM model with 1.89 million landmarks. Thisdataset is scaled in meters and each of the 800 query images have bundle adjusted ground-truth poses. We chose
this dataset since it is widely used for comparing localization methods, as it is a challenging dataset with ground truth
poses. Furthermore, this dataset is particularly challenging for our filter. Since the depth variation per view in thisdataset can be quite large (c.f . Fig. 9), this dataset allows us
to validate our method under such difficult conditions.
For each query image, we extract ground-truth inlier
matches by using the provided ground-truth pose. We firstevaluate the effect of different score thresholds tid ∈[0,1](c.f . Fig. 8). For this, we vary tid to obtain different performance points, where high score thresholds increase theinlier ratio but may prune out true inliers. We observe that

Method
Setting 1
Setting 2
Setting 3
RANSAC+P3P
Zeisl [28]Zeisl BA [28]Svärm [26]Sattler [22]Assumptions
V
S
R

•
•
•
•
•

•
•
•
•

Registration Statistics|I|>11

<18.3

>400

800
797
793
634
798
794
798
797

739
731
720
601
725
749
771
704

8
8
13
11
2
13
3
9

Error Quartiles [m]
1st
2nd
3rd
0.22
1.07
2.99
0.50
1.16
3.42
0.81
2.06
6.27
1.20
5.06
8.11
0.75
1.69
4.82
0.18
0.47
1.73
0.56
0.50
1.3
5.0

|S|

Time [s]

6210
8415
4766
4766
11265
49
4766
6 100

9.7
9.1
3.2
12.9
3.78
5.06
0.16

Table 1. Results for the Dubrovnik Dataset. We compare registration metrics for our method against the state-of-the-art. Here  and |I|
represent the translation error (in meters) and the number of inliers of the final image registration, respectively. Further, V denotes known
vertical direction, S known scale and R methods relying on a good SIFT ratio (i.e. relying on the discriminative power of features, whichis dataset-dependent).

the filter operates as expected; for a wide range of thresholds we can increase the inlier ratio while discarding only
very few inliers.
For the next evaluation, we draw several descriptive
statistics from our pose results in order to compare itagainst previously existing methods on the Dubrovnik
dataset (c.f . Table 1). Additionally, we compare to a simple
RANSAC+P3P method as a baseline. We run three different settings, the first one uses the octree method discussed
in Section 3.5 to discard gross outliers, while the second andthird do not.
Setting 1 For this setting, we use all available matches ascomputed by FLANN [19] and set tid =0.55.
Setting 2 Here we do not use an octree but still use all available matches.
Setting 3 Here we discard the matches for which the ratio
test [16] (the ratio of the first SIFT nearest neighbor overthe second neighbor) was more than 0.9 (this is the settingthat Svarm et al. use for their filter). Since now the numberof matches is lower, we do not use an octree.
For Settings 2 and 3, we set tid =0.35. Notice that wemay set a lower threshold for these two settings since a lotof outliers have already been removed by the octree or theratio test.
Since many true inliers are discarded using a ratio test
and our filter is designed to handle as many outliers asneeded, we perform better under the first setting. However,this means that the number of average matches per image
to be considered is much higher (|S| in Table 1), and assuch the runtime of our filter is higher. In many hard cases,
there may be a high number of approximate inlier matches.
These are matches that would not be inliers to a final P3P
position, but are not effectively discarded with our approximate positions. Thus, these matches are very close to being
geometrically sound, since their true projection is only afew pixels away, passing the proposed outlier filter. This
results in the final RANSAC solver retrieving a wrong local
minimum leading to a bad localization.
However, since our filter enforces matches to be con-strained by a strong geometric restriction, we observe better
median positional errors w.r.t. other methods that do not refine their final solution, such as [28] with voting only. Further, [26] propose an optimal pose estimation strategy under
low-outlier conditions that could also be used in conjunction with our filter. This would further improve our positional accuracy. Under Setting 2, we do not achieve suchhigh performance since the inverse depth data points are too
contaminated with outliers, rendering the choice of threshold more challenging. Finally, Setting 3 has lower recall
since we clearly prune out valuable inliers using the ratio
test. In terms of positional accuracy and successful localizations, we are able to produce competitive results for allof the settings used. Note that, in contrast to [26, 28], we donot make any assumptions about the data: no assumption of
known vertical, known scale, known ground plane, etc. Instead, we use geometrically meaningful information latentin the 2D-3D matches that was previously untapped.

5. Conclusions
In this paper we have presented a new 2D-3D geometricconstraint and its application to visual localization. Albeit
our outlier filter based on toroidal constraints is simple, it
effectively removes many outliers and performs on par withmore involved approaches. The proposed solution makes
no strong assumptions on the data and thus is widely applicable. Therefore, it can be used as a drop-in solution
in any localization pipeline to greatly increase the performance for difficult cases. Furthermore, even other pipelinesthat already employ a tailored approach for city-wide localization [22, 26, 28] can potentially benefit from this newly
derived constraint. The constraint presented can thus be regarded as a new additional and meaningful geometric insight useful for the localization task.
Acknowledgements. This research was funded by Google
Tango.

References[1] C. Arth, M. Klopschitz, G. Reitmayr, and D. Schmalstieg.
Real-Time Self-Localization from Panoramic Images on
Mobile Devices. In ISMAR, 2011.
[2] F. Camposeco, T. Sattler, and M. Pollefeys. Non-Parametric
Structure-Based Calibration of Radially Symmetric Cameras. In ICCV, 2015.
[3] F. Camposeco, T. Sattler, and M. Pollefeys. Minimal Solvers
for Generalized Pose and Scale Estimation from Two Rays
and One Point. In ECCV, 2016.
[4] S. Choudhary and P. J. Narayanan. Visibility Probability
Structure from SfM Datasets and Applications. In ECCV,
2012.
[5] A. J. Davison, I. D. Reid, N. D. Molton, and O. Stasse.
MonoSLAM: Real-Time Single Camera SLAM. PAMI,
29(6):1052–1067, 2007.
[6] O. Enqvist, E. Ask, F. Kahl, and K. Åström. Robust Fittingfor Multiple View Geometry. In ECCV, 2012.
[7] O. Enqvist and F. Kahl. Robust optimal pose estimation. In
ECCV, pages 141–153. Springer, 2008.
[8] L. Ferraz, X. Binefa, and F. Moreno-Noguer. Very Fast Solution to the PnP Problem with Algebraic Outlier Rejection.
In CVPR, 2014.
[9] M. Fischler and R. Bolles. Random sample consensus: aparadigm for model fitting with applications to image analysis and automated cartography. Comm. ACM, 24(6):381–
395, 1981.
[10] D. R. Grayson and M. E. Stillman. Macaulay 2, a softwaresystem for research in algebraic geometry, 2002.
[11] R. Haralick, C.-N. Lee, K. Ottenberg, and M. Nölle. Review
and analysis of solutions of the three point perspective pose
estimation problem. IJCV, 13(3):331–356, 1994.
[12] M. Havlena and K. Schindler. VocMatch: Efficient Multiview Correspondence for Structure from Motion. In ECCV,
2014.
[13] V. Larsson, J. Fredriksson, C. Toft, and F. Kajl. Outlier Rejection for Absolute Pose Estimation with Known Orientation. In BMVC, 2016.
[14] Y. Li, N. Snavely, and D. P. Huttenlocher. Location Recognition using Prioritized Feature Matching. In ECCV, 2010.
[15] Y. Li, N. Snavely, D. P. Huttenlocher, and P. Fua. Worldwide
Pose Estimation Using 3D Point Clouds. In ECCV, 2012.
[16] D. Lowe. Distinctive image features from scale-invariant
keypoints. IJCV, 60(2):91–110, 2004.
[17] S. Middelberg, T. Sattler, O. Untzelmann, and L. Kobbelt.
Scalable 6-DOF Localization on Mobile Devices. In ECCV,
2014.
[18] K. Mikolajczyk and C. Schmid. A performance evaluationof local descriptors. PAMI, 27(10):1615 –1630, 2005.
[19] M. Muja and D. G. Lowe. Fast Approximate Nearest Neighbors with Automatic Algorithm Configuration. In VISAPP,
2009.
[20] F. Pfeuffer, M. Stiglmayr, and K. Klamroth. Discrete andgeometric Branch and Bound algorithms for medical image
registration. Annals of Operations Research, 196(1):737–765, 2012.

[21] T. Sattler, M. Havlena, F. Radenovic, K. Schindler, and
M. Pollefeys. Hyperpoints and Fine Vocabularies for LargeScale Location Recognition. In ICCV, 2015.
[22] T. Sattler, B. Leibe, and L. Kobbelt. Efficient & Effective
Prioritized Matching for Large-Scale Image-Based Localization. PAMI, 2016 (accepted).
[23] T. Sattler, T. Weyand, B. Leibe, and L. Kobbelt. Image Retrieval for Image-Based Localization Revisited. In BMVC,
2012.
[24] J. L. Schönberger and J.-M. Frahm. Structure-from-Motion
Revisited. In CVPR, 2016.
[25] N. Snavely, S. M. Seitz, and R. Szeliski. Photo tourism: Exploring photo collections in 3D. In SIGGRAPH, 2006.
[26] L. Svärm, O. Enqvist, F. Kahl, and M. Oskarsson. CityScale Localization for Cameras with Known Vertical Direction. PAMI, 2016 (accepted).
[27] C. Sweeney, T. Sattler, M. Turk, T. Hollerer, and M. Pollefeys. Optimizing the Viewing Graph for Structure-fromMotion. In ICCV, 2015.
[28] B. Zeisl, T. Sattler, and M. Pollefeys. Camera Pose Voting
for Large-Scale Image-Based Localization. In ICCV, 2015.