Sampling based Bundle Adjustment using Feature Matches
between Ground-view and Aerial Images
Hideyuki Kume, Tomokazu Sato and Naokazu Yokoya
Nara Institute of Science and Technology, 8916-5 Takayama, Ikoma, Nara, Japan{hideyuki-k, tomoka-s, yokoya}@is.naist.jp

Keywords:

Structure-from-Motion, Bundle Adjustment, Aerial Image, RANSAC.

Abstract:

This paper proposes a new pipeline of Structure-from-Motion that uses feature matches between groundview and aerial images for removing accumulative errors. In order to find good matches from unreliablematches, we newly propose RANSAC based outlier elimination methods in both feature matching and bundle
adjustment stages. To this end, in the feature matching stage, the consistency of orientation and scale extracted
from images by a feature descriptor is checked. In the bundle adjustment stage, we focus on the consistency
between estimated geometry and matches. In experiments, we quantitatively evaluate performances of the
proposed feature matching and bundle adjustment.

1

INTRODUCTION

Structure-from-Motion (SfM) is one of key technologies developed in computer vision field, and SfM
has been used to achieve great works such as ‘building Rome in a day’ (Agarwal et al., 2009) and‘PTAM’ (Klein and Murray, 2007). In SfM, one essential problem is accumulation of estimation errors
for a long image sequence. Although many kindsof methods that reduce accumulative errors are proposed, SfM methods essentially cannot be free fromaccumulative errors unless some external references(e.g., like GPS, aerial images, and feature landmarks)
are given.
The techniques that remove accumulative errors
in the bundle adjustment (BA) stage of SfM using
some external references are called as extended bundle adjustment (extended-BA), and earlier researchesof extended-BA mainly focused on the combinationof GPS and SfM (Lhuillier, 2012). In this paper, we
employ the framework of extended-BA to the SfM
problem that uses an aerial image as an external reference. In order to successfully use an aerial image
as a reference of SfM, successful matching between
aerial image and ground-view image is very important. To find good matches from unreliable matches,in addition to the use of GPS and gyroscope sensors
embedded in most of recent smartphones, we newly
use two methods: (1) RANSAC (Fischler and Bolles,
1981) based outlier elimination in the feature matching stage by focusing on consistency of orientationand scale extracted from images by feature descriptor
like SIFT (Lowe, 2004) and (2) RANSAC based outlier elimination in the BA stage using consistency of
estimated geometry and matches.

2 RELATED WORK
In order to reduce accumulative errors in SfM, loop
closing techniques (Williams et al., 2009) are sometimes employed with the BA. Although these techniques can reduce accumulative errors, it is essentiallydifficult for the techniques that rely on only images toremove accumulative errors for a long sequence without the loop.
In order to reduce accumulative errors in general movement of camera, several kinds of externalreferences such as GPS (Lhuillier, 2012) and roadmaps (Brubaker et al., 2013) are used with SfM.
Lhuillier (Lhuillier, 2012) proposed extended-BA using GPS that minimizes the energy function definedas the sum of reprojection errors and a penalty termof GPS. This method can globally optimize camera
parameters and reduce accumulative errors by updating parameters so as to minimize the energy function. However, the accuracy of this method is directly
affected by errors of GPS positioning, which easily
grow to the 10m level in urban areas. Brubaker etal. (Brubaker et al., 2013) proposed the method thatuses community developed road maps. Although thismethod can reduce accumulative errors by matching
trajectory from SfM to road maps, there are ambiguities for some scenes such as straight roads or Manhattan worlds.
On the other hand, in order to estimate absolute camera positions and postures, some methods
estimate camera parameters directly from references
without SfM (Pink et al., 2009; Noda et al., 2010).
Pink et al. (Pink et al., 2009) used aerial images asreferences and estimated camera parameters based onfeature matching between input images and aerial images. However, it is not easy to find good matches
for all the images of a long video sequence especiallyfor the scenes where unique landmarks cannot be observed. Although Mills (Mills, 2013) proposed a robust feature matching procedure that compares orientation and scale of each matches with dominant orientation and scale identified by histogram analysis,
it cannot work well when there exist a huge number of outliers. Noda et al. (Noda et al., 2010) relaxed the problem by generating mosaic images of
the ground from multiple images for feature matching. However, accumulative errors are not consideredin this work. Unlike previous works, we estimate
relative camera poses for all the frames using SfM,
and we remove accumulative errors by selecting correct matches between aerial image and ground-view
image from candidates by employing a multi-stage
RANSAC scheme.

3

FEATURE MATCHINGBETWEEN GROUND-VIEW
AND AERIAL IMAGESIn this section, we propose a robust method to obtainfeature matches between ground-view and aerial images. As shown in Figure 1, the method is composedof (1) ground-view image rectification by Homography, (2) feature matching, and (3) RANSAC. Here,in order to achieve robust matching, we propose newcriteria for RANSAC with consistency check of orientation and scale from a feature descriptor. It should
be noted that matching for all the input frames are notnecessary in our pipeline. Even if we can find only
several candidates of matched frames, they can be effectively used as references in the BA stage.

3.1

Image Rectification by Homography

Before calculating feature matches using a feature detector and a descriptor, as shown in Figure 1, we rectify ground-view images so that texture patterns are

similar to those of the aerial image. In most cases,
aerial images are taken very far away from the groundand thus they are assumed to be captured by an orthographic camera whose optical axis is directed to gravity direction. In order to rectify ground-view images,
we also assume that the ground-view images containthe ground plane whose normal vector is directed togravity direction. Then, we compute Homographymatrix using the gravity direction in camera coordinate system which can be estimated from the vanishing points of parallel lines or a gyroscope.

3.2 Feature Matching
Feature matches between rectified ground-view images and the aerial image are calculated. Here, we
use GPS data corresponding to the ground-view images to limit searching area in the aerial image. Moreconcretely, we select the region whose center is GPS
position and its size is l × l. In the experiment described later, l is set to 50 [m]. Feature matches arethen calculated by a feature detector and a descriptor.
We employ SIFT (Lowe, 2004) in the experiment because of its robustness for changes in scale, rotationand illumination.

3.3 RANSAC with Orientation and
Scale Check
As shown in Figure 1, tentative matches often include
many outliers. In order to remove outliers, we use
RANSAC with consistency check of orientation andscale parameters.
For matches between rectified ground-view images and the aerial image, we can use the similarity
transform which is composed of scale s, rotation θ
and translation τ . In RANSAC procedure, we randomly sample two matches (minimum number to estimate similarity transform) to compute the similarity
transform (s, θ, τ ). Here we count the number of inliers which satisfy|aak − (sR(θ)ggk + τ)| < dth ,(1)

where a k and g k are the 2D positions of the k-th matchin the aerial image and the rectified ground-view image, respectively. R(θ) is the 2D rotation matrix withrotation angle θ and dth is a threshold. After repeating
random sampling process, the sampled matches withthe largest number of inliers are selected.
The problem here is that the distance-based criterion above cannot successfully find correct matches
when there exist a huge number of outliers. In order to achieve more robust matching, we modify thecriterion of RANSAC by checking the consistency ofAerial image

matches in principle because there may exist repetitive and similar patterns, e.g., road signs in real environments. In order to overcome this difficulty, we also
employ RANSAC for the BA stage by focusing on
consistency between feature matches and estimatedcamera poses from images.

Ground-view image(1) Homography

4.1 Definition of Energy Function
In order to consider the matches between groundview and aerial images, here, an energy function isdefined and minimized. The energy function E isdefined by using reprojection errors for ground-view(perspective) images Φ and the aerial (orthographic)
image Ψ as follows:(2) Feature matching

Ri ,tt i }Ii=1 , {pp j }Jj=1 ) =E({RRi ,tt i }Ii=1 , {pp j }Jj=1 ) + ωΨ({pp j }Jj=1 ), (4)Φ({Rwhere R i and t i represent rotation and translation fromworld coordinate system to camera coordinate system
for the i-th frame, respectively. p j is a 3D positionof the j-th feature point. I and J are the number offrames and feature points, respectively, and ω is aweight that balances Φ and Ψ. Since the energy function is non-linearly minimized in BA, good initial values of parameters are required to avoid local minima.
Before minimizing the energy function, we fit the parameters estimated by SfM to the positions from GPS
by 3D similarity transform. In the following, the energy associated with reprojection errors Φ and Ψ aredetailed.

(3) RANSAC withorientation and scale check

Figure 1: Flow of feature matching.

orientation and scale from a feature descriptor. Concretely, we count the number of inliers which simultaneously satisfy Equation (1) and the following two
conditions.
()
sgk · s sakmax,< sth ,
(2)
sak sgk · saad(θgk + θ, θak ) < θth ,(3)

where (sak , sgk ) and (θak , θgk ) are the scale and orientation of feature points for the k-th match on the aerial
image and the rectified ground-view image, respectively. The function ‘aad’ returns the absolute angle
difference in the domain [0◦ , 180.0◦ ]. sth and θth are
thresholds for scale and angle, respectively.

4

SAMPLING BASED BUNDLE
ADJUSTMENT

Even by the modified RANSAC proposed in previous
section, it is not possible to remove all the incorrect

4.1.1 Reprojection Errors for Ground-view
Images
The commonly used reprojection errors employ thepinhole camera model which cannot deal with projections from behind the camera. Projections from behind the camera often occur in BA with references due
to dynamic movement of camera parameters by references. Here, instead of common squared distance errors on image plane, we employ the reprojection error
by using angle of rays as follows:
Ri ,tt i }Ii=1 , {pp j }Jj=1 ) =
Φ({R

1

I

∑ ∑ Φi j , (5)Pi | i=1 j∈PPi∑Ii=1 |P(( ) ( ))2(( ) ( ))2
xi j
Xi j
yi j
Y
Φi j = ∠
,
+∠
, ij
,
fi
Zi j
fi
Zi j
(6)
(Xi j ,Yi j , Zi j )T = R i p j + t i ,(7)where P i is a set of feature points detected in the ith frame. Function ∠ returns an angle between twovectors, (xi j , yi j )T is a detected 2D position of the jth feature points in the i-th frame, and fi is the focal
length of the i-th camera.
Here, we split the angular reprojection error
into xz component and yz component because Jacobian matrix of E required by non-liner least squares
method such as Levenberg-Marquardt method becomes simple. Especially, the first term of Φi j does
not depend on the y component of t i and the second term does not depend on the x component of t iin this definition. We have experimentally confirmedthat this splitting largely affects the performance of
convergence.
4.1.2

GPS on iPhone
RTK-GPS (Ground truth)
BA without references
BA with references without RANSAC
BA with references and RANSAC
Correctly matched feature point
on aerial image
Incorrectly matched feature point
on aerial image

Reprojection Errors for Aerial Image

The reprojection errors for the aerial (orthographic)
image are defined as follows:Ψ({pp j }Jj=1 ) =1∑∑
Ai | i∈M
∑i∈M
M |A
M j∈A
Ai

2

a j − prxy (pp j ) ,(8)where M is a set of frames in which feature matches
between ground-view and aerial images are obtained.
Ai is a set of feature points which are matched to theaerial image in the i-th frame. a j is the 2D positionof the j-th feature point in the aerial image. prxy is afunction that projects a 3D point onto xy plane (aerial
image coordinate system).

4.2

RANSAC for Bundle Adjustment

(9)

Ai
j∈A

(
)
∠ RTi (0, 0, 1)T , oi < βth ,After repeating the random sampling process atgiven times, sampled frames with the largest numberof inlier frames are selected. Finally, camera poses
are refined by redoing BA using feature matches withselected inlier frames as references.

5 EXPERIMENTSRANSAC scheme is introduced in BA by using theconsistency between feature matches and estimatedcamera poses from images. First, we randomly sample n frames from the candidates of matched frames
and do BA using feature matches included in sampled
frames, i.e., using a set of selected frames M ′ insteadof M in Equation (8). Then we count the number of
inlier frames which satisfy the following two conditions.
average(αi j ) < αth ,Figure 2: Experimental environment and results.

(10)

where αi j is an angular reprojection error of the j-thfeature point on aerial image coordinate system. o iis the direction of optical axis in world coordinate
system calculated from Homography and similarity
transform estimated in the feature matching stage. αthand βth are thresholds. Here, αi j is computed as follows:(())
RTi t i ), prxy R Ti (xi j , yi j , fi )T .
αi j = ∠ a j − prxy (−R(11)

In order to validate the effectiveness of the proposed
method, we quantitatively evaluated performances ofsampling based BA as well as the feature matchingprocess.

5.1 Experimental Setup
We used iPhone 5 (Apple) as a sensor unit including a camera, GPS and gyroscope. The camera captured video images (640 × 480 pixels, 2471 frames,
494 seconds). GPS and gyroscope measured position
at 1 Hz and gravity direction for every frame, respectively. We also used RTK-GPS (Topcon GR-3, 1 Hz,
accuracy of horizontal positioning is 0.03 [m]) to obtain the ground truth positions. Positions from GPSdata were assigned temporally to the nearest frame.
As the external reference, we downloaded the aerial
image covering the area used in this experiment from
Google Maps [maps.google.com] whose coordinate
system is associated with the metric scale, i.e., 19.2
[pixel] = 1 [m]. Figure 2 shows an aerial image andGPS positions.

Similarity transform
Angle [ ] Scale
325.56 0.06

Similarity transform
Angle [ ] Scale
158.71 1.19

SIFT keypoints

SIFT keypoints

Angle [ ] Scale
334.02 0.85
332.84 0.91
330.88 0.84
352.56 0.43
156.73 1.06

Angle [ ] Scale
159.92 1.11
154.96 0.89
154.24 1.25
148.45 1.12(a) Without orientation and scale check

Similarity transform
Angle [ ] Scale
66.47 0.07(b) With scale check, with/without orientation check

Similarity transform
Angle [ ] Scale
336.34 0.96

SIFT keypoints

SIFT keypoints

Angle [ ] Scale
164.35 0.86
334.38 0.82
334.94 0.78
329.40 0.68
171.96 0.46

Angle [ ] Scale
342.27 0.90
338.34 0.90
339.67 0.73
341.82 0.77
333.08 0.77(c) Without orientation and scale check(d) With orientation check, with/without scale check

Figure 3: Selected inliers for example images. Solid and dashed lines are correct and incorrect matches, respectively. Relative
angle and scale of matched feature points are shown in bottom right table with corresponding lines’ colors. Green points are
ground truths of camera positions. RANSAC with/without orientation check for (b) and scale check for (d) gave the same
results.

Similarity transform
Angle [ ] Scale
3.87 0.89

Similarity transform
Angle [ ] Scale
169.41 1.07

SIFT keypoints

SIFT keypoints

Angle [ ] Scale
343.16 1.63
19.02 0.80
12.64 1.22
13.32 0.93

Angle [ ] Scale
169.48 0.99
168.87 1.15
163.06 1.17
170.35 1.04

Figure 4: Examples of incorrect matches by RANSAC with orientation and scale check. The interpretations of symbols are
the same as Figure 3.

In order to obtain initial values for BA, we employed VisualSFM (Wu, 2011) as a state-of-the-art
implementation of SfM. For non-linear minimization,
we used ceres-solver (Agarwal et al., 2013).

5.2

Result of Feature Matching

In this experiment, we evaluate the effectivenessof proposed feature matching process including
RANSAC with scale and orientation check describedin Section 3. Here, we have compared four types of
RANSAC by enabling and disabling scale and orientation check. In order to count the number of correctly

matched frames, we first selected frames which havefour or more inlier matches after RANSAC. Fromthese frames, we manually counted frames whosematches are correct. Here, we set dth = 2 [pixel],
sth = 2 and θth = 40 [◦ ].
Table 1 shows rates of frames in which all the selected matches are correct. From this table, we canconfirm that the rates are significantly improved byscale and orientation check. Figure 3 shows effects ofscale and orientation check for sampled two images.
In both cases, RANSAC without scale and orientation
check could not select correct matches and proposed
RANSAC with scale and orientation check could se-Result of Bundle Adjustment

In this experiment, we evaluate the effectiveness of
BA with RANSAC described in Section 4. In thisstage, the frames with GPS data were sampled (650of 2471 frames) and used in order to reduce computational time. As external references, we usedframes and feature matches selected with orientationand scale check described in previous section. Here,
we set ω = 10−5 , αth = 10.0 [◦ ], βth = 150.0 [◦ ], andn = 2.
We first evaluate the proposed RANSAC in termsof capability to select frames whose matches are correct. Here, as shown in Table 1, 10 of 14 frames
have correct matches. We tested all the pairs of 14
frames as samples of RANSAC, and the number of
inlier frames that are selected in each trial is checked.
Figure 5 shows the number of trials and inlier frames
derived by each trial. From this figure, we can see thatthe sampled frames without incorrect matches tend toincrease the number of inlier frames. We also confirmed that the trials which derive the largest number of inlier frames successfully selected all of correct
matches.
Next, we evaluate the accuracy of the proposed
method by comparing the following methods.
• BA without references (Wu, 2011),• BA with references without RANSAC which uses
all the matches obtained by feature matching process,• BA with references and RANSAC.
Since the BA without reference cannot estimate themetric scale, we fitted the camera positions estimatedby SfM to the ground truths by similarity transform.
Figures 2 and 6 show the estimated camera positions
and horizontal position errors for each frame, respectively. From these results, it is confirmed that estimated camera positions by BA without references
Table 1: Rates of frames in which all the selected matches
are correct. Number of frames in which all the selected
matches are correct / number of frames which have four ormore inlier matches are shown in bracket.

w/ scalecheck
w/o scalecheck

w/ orientation
check
0.714
(10 / 14)0.134
(9 / 67)

w/o orientation
check
0.103
(9 / 87)
0.005(2 / 380)

Number of trials

5.3

20
15
10
5
0
0
3
5
6
7
8
1
2
4
Number of inlier frames
Sampled frames without incorrect matches
Sampled frames with incorrect matches

910

Figure 5: Number of trials and inlier frames derived by eachtrial.
Horizontal position error [m]lect correct matches. However, as shown in Figure
4, incorrect matches still remain even if we use bothscale and orientation check.

50
40
30
20
10
0
0

500

1000
1500
Frame number

BA w/o references
BA w/ references w/o RANSAC

2000

BA w/ references and RANSAC

Figure 6: Horizontal position error in each frame.

are affected by accumulative errors. The BA without RANSAC is affected by incorrect matches. The
proposed BA with RANSAC can reduce the accumulative errors. It should be noted that, in the end of thesequence, the accumulative errors are still remained
because there are no available matches.

6 CONCLUSION
In this paper, we have proposed a method to remove
accumulative errors of SfM by using aerial images asexternal references that already exist for many placesin the world. To this end, we have proposed SfM
method that uses feature matches between groundview and aerial images. In order to find correct
matches from unreliable matches, we have introduced
the new RANSAC schemes to both feature matching
and bundle adjustment stages. In experiments, wehave confirmed that the proposed method is effective
for estimating camera poses of real video sequencetaken in an outdoor environment. In the future, wewill test the effectiveness of the proposed method in
various environments including roadways.

ACKNOWLEDGEMENTS
This research was partially supported by JSPS Grantin-Aid for Scientific Research No. 23240024 and“Ambient Intelligence” project granted from MEXT.

REFERENCES
Agarwal, S., Mierle, K., and Others (2013). Ceres solver.
https://code.google.com/p/ceres-solver.
Agarwal, S., Snavely, N., Simon, I., Seitz, S. M., andSzeliski, R. (2009). Building Rome in a day. In Proc.
Int. Conf. on Computer Vision, pages 72–79.
Brubaker, M. A., Geiger, A., and Urtasun, R. (2013).
Lost! leveraging the crowd for probabilistic visualself-localization. In Proc. IEEE Conf. on Computer
Vision and Pattern Recognition, pages 3057–3064.
Fischler, M. A. and Bolles, R. C. (1981). Random sample
consensus: a paradigm for model fitting with applications to image analysis and automated cartography.
Communications of the ACM, 24(6):381–395.
Klein, G. and Murray, D. (2007). Parallel tracking and mapping for small AR workspaces. In Proc. Int. Symp. on
Mixed and Augmented Reality, pages 225–234.
Lhuillier, M. (2012). Incremental fusion of structure-frommotion and GPS using constrained bundle adjustments. IEEE Trans. on Pattern Analysis and MachineIntelligence, 34(12):2489–2495.
Lowe, D. G. (2004). Distinctive image features fromscale-invariant keypoints. Int. J. Computer Vision,
60(2):91–110.
Mills, S. (2013). Relative orientation and scale for improved
feature matching. In Proc. IEEE Int. Conf. on Image
Processing, pages 3484–3488.
Noda, M., Takahashi, T., Deguchi, D., Ide, I., Murase,
H., Kojima, Y., and Naito, T. (2010). Vehicle egolocalization by matching in-vehicle camera images toan aerial image. In Proc. ACCV2010 Workshop on
Computer Vision in Vehicle Technology: From Earthto Mars, pages 1–10.
Pink, O., Moosmann, F., and Bachmann, A. (2009). Visual features for vehicle localization and ego-motion
estimation. In Proc. IEEE Intelligent Vehicles Symposium, pages 254–260.
Williams, B., Cummins, M., Neira, J., Newman, P., Reid, I.,
and Tardós, J. (2009). A comparison of loop closing
techniques in monocular SLAM. Robotics and Autonomous Systems, 57(12):1188 – 1197.
Wu, C. (2011). VisualSFM: A visual structure from motion
system. http://ccwu.me/vsfm/.