Barath D, Matas J. Graph-cut RANSAC.
In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition 2018 (pp. 6733-6741)

Graph-Cut RANSAC
Daniel Barath12 and Jiri Matas2
1
Machine Perception Research Laboratory, MTA SZTAKI, Budapest, Hungary
2Centre for Machine Perception, Czech Technical University, Prague, Czech Republic

Abstract
A novel method for robust estimation, called Graph-Cut
RANSAC1 , GC-RANSAC in short, is introduced. To separate inliers and outliers, it runs the graph-cut algorithm inthe local optimization (LO) step which is applied when a sofar-the-best model is found. The proposed LO step is conceptually simple, easy to implement, globally optimal andefficient. GC-RANSAC is shown experimentally, both on
synthesized tests and real image pairs, to be more geometrically accurate than state-of-the-art methods on a range ofproblems, e.g. line fitting, homography, affine transformation, fundamental and essential matrix estimation. It runs
in real-time for many problems at a speed approximately
equal to that of the less accurate alternatives (in milliseconds on standard CPU).

1. Introduction
The RANSAC (RANdom SAmple Consensus) algorithm proposed by Fischler and Bolles [7] in 1981 has become the most widely used robust estimator in computer
vision. RANSAC and similar hypothesize-and-verify approaches have been successfully applied to many visiontasks, e.g. to short baseline stereo [27, 29], wide baseline
stereo matching [22, 17, 18], motion segmentation [27], image mosaicing [9], detection of geometric primitives [25],multi-model fitting [31], or for initialization of multi-model
fitting algorithms [12, 21]. In brief, the RANSAC approach
repeatedly selects random subsets of the input data and fitsa model, e.g. a line to two points or a fundamental matrix toseven point correspondences. In the second step, the model
support, i.e. the number of inliers, is obtained. The modelwith the highest support, polished e.g. by a least squares fit
on inliers, is returned.
In the last three decades, many modifications of
RANSAC have been proposed.
For instance, NAPSAC [20], PROSAC [4] or EVSAC [8] modify the sampling strategy to increase the probability of selecting an all-inlier sample earlier. NAPSAC considers spatial coherencein the sampling of input data points, PROSAC exploits theordering of the points by their predicted inlier probability,
EVSAC uses an estimate of the confidence in each point.
Modifications of the model support step has also been proposed. In MLESAC [28] and MSAC [10], the model quality
is estimated by a maximum likelihood process, albeit undercertain assumptions, with all its beneficial properties. In
practice, MLESAC results are often superior to the inlier
counting of plain RANSAC and less sensitive to the userdefined threshold. The termination of RANSAC is controlled by a manually set confidence value η and the sampling stops when the probability of finding a model withhigher support falls below η 2 .
Observing that RANSAC requires in practice more samples than theory predicts, Chum et al. [5] identified a problem that not all all-inlier samples are “good”, i.e. lead to amodel accurate enough to distinguish all inliers, e.g. due topoor conditioning of the selected random all-inlier sample.
They address the problem by introducing the locally optimized RANSAC (LO-RANSAC) that augments the original approach with a local optimization step applied to theso-far-the-best model. In the original paper [5], local optimization is implemented as an iterated least squares refitting with a shrinking inlier-outlier threshold inside an
inner RANSAC applied only to the inliers of the current
model. In the reported experiments, LO-RANSAC outperforms standard RANSAC in both accuracy and the required
number of iterations. The number of LO runs is close to
the logarithm of the number of verifications, and it does notcreate a significant overhead in the processing time in mostof the cases tested. However, it was shown by Lebeda etal. [15] that for models with high inlier counts the local optimization step becomes a computational bottleneck due tothe iterated least squares model fitting. This is addressedby using a 7m-sized subset of the inliers in each LO step,
where m is the size of a minimum sample; the factor of
7 was set by exhaustive experimentation. The idea of local
optimization has been included in state-of-the-art RANSAC
approaches like USAC [23]. Nevertheless, the LO proce-

1 Available at https://github.com/danini/graph-cut-ransac

2 This interpretation of η holds for the standard cost function only.

6733

dure is ad hoc, complex and needs multiple parameters.

2. Local Optimization and Spatial Coherence

In this paper, we combine two strands of research toobtain a state-of-the-art RANSAC. In the large body of
RANSAC-related literature, the inlier-outlier decision has
always been a function of the distance to the model, done
individually for each data point. Yet both inliers and outliers are spatially coherent, a point near an outlier or inlier
is more likely to be an outlier or inlier respectively. Spatial coherence, leading to the Potts model [3], has been exploited in many vision problems, for instance, in segmentation [30], multi-model fitting [12, 21] or sampling [20]. In
RANSAC techniques, it has only been used to improve efficiency of sampling in NAPSAC [20]. It is computationallyprohibitive to formulate the model verification in RANSAC
as a graph-cut problem. But when applied as the LO step in[5] just to the so-far-the-best model, the number of graphcuts is only the logarithm of the number of sampled andverified models, and can be achieved in real-time.

In this section, we formulate the inlier selection of
RANSAC as an energy minimization considering point-topoint proximity. The proposed local optimization is seen as
an iterative energy minimization of a binary labeling (outlier – 0 and inlier – 1). For the sake of simplicity, we startfrom the original RANSAC scheme and then formulate themaximum likelihood estimation as an energy minimization.
The term considering the spatial coherence will be included
into the energy.

The proposed method, called Graph-Cut RANSAC (GCRANSAC), is a locally optimized RANSAC alternating
graph-cut and model re-fitting as the LO step. GCRANSAC is superior to LO-RANSAC in a number of aspects. First, it is capable of exploiting spatial coherenceof inliers and outliers. The LO step is conceptually a simple, easy to implement, globally optimal and computationally efficient graph-cut with only a few intuitive and learnable parameters unlike the ad hoc, iterative and complex
LO steps [5]. Third, we show experimentally that GCRANSAC outperforms LO-RANSAC and its recent variants in both accuracy and the required number of iterations
on a wide range of publicly available datasets. On many
problems, it is faster than the competitors in terms of thewall-clock time. Finally, we were surprised to observe that
GC-RANSAC terminates before the theoretically expected
number of iterations. The reason is that the local optimization that takes spatial proximity into account is often capable of converging to a “good” model even when startingfrom a sample that is not all-inlier, i.e. it contains outliers.
PEARL [12] introduced pair-wise energy to geometricmodel fitting. However, it cannot be used for problems
solved by RANSAC – in PEARL, the user has to manually set the number of hypotheses tested to the worst-case,i.e. corresponding to the lowest inlier ratio possible. The
α-expansion step just in the first iteration of PEARL executes a graph-cut as many times as the number of hypotheses tested. The number is calculated from the worst-casescenario and is typically orders of magnitude higher than thenumber of iterations determined by the RANSAC adaptive
termination criterion. Moreover, in GC-RANSAC, applying the local optimization to only the so-far-the-best models
ensures that the graph-cut is executed only very few times,
paying only a small penalty.

2.1. Formulation as Energy Minimization
Suppose that a point set P ⊆ Rn (n > 0), a model
represented by a parameter vector θ ∈ Rm (m > 0) and a
distance function φ : P × Rm → R measuring the point-tomodel assignment cost are given.
For the standard RANSAC scheme which applies a tophat fitness function (1 – close, 0 – far), the implied unaryenergy is as follows:
X||Lp ||{0;1} ,E{0;1} (L) =
p∈P

where
||Lp ||{0;1} =



0



1

if (Lp = 1 ∧ φ(p, θ) < ǫ) ∨(Lp = 0 ∧ φ(p, θ) ≥ ǫ)otherwise.

Parameter L ∈ {0, 1}|P| is a labeling, ignored in standard
RANSAC, Lp ∈ L is the label of point p ∈ P, |P| is thenumber of points, and ǫ is the inlier-outlier threshold. Using
energy E{0,1} we get the same result as RANSAC since itdoes not penalize only two cases: (i) when p is labeled inlier
and it is closer to the model than the threshold, or (ii) when
p is labeled outlier and it is farther from the model than ǫ.
This is exactly what RANSAC does.
Since the publication of RANSAC, several papers discussed, e.g. [15], replacing the {0, 1} loss with a kernel
function K : R × R → [0, 1], e.g. the Gaussian-kernel.
Such choice is close to maximum likelihood estimation as
proposed in MLESAC [28]. This improves the accuracy
and reduces the sensitivity to threshold ǫ. Unary term EK
exploiting
this continuous loss is as follows: EK (L) =P
p∈P ||Lp ||K , where(
1 − K(φ(p, θ), ǫ) if Lp = 1||Lp ||K =(1)
K(φ(p, θ), ǫ)
if Lp = 0andδ2K(δ, ǫ) = e− 2ǫ2 ,(2)which equals to one if the distance is zero. In GCRANSAC, we use EK as the unary energy term in the graphcut-based verification.

6734

2.2. Spatial Coherence
Benefiting from a binary labeling energy minimization,
additional energy terms, e.g. to consider spatial coherenceof the points, can be included yet keep the problem solvableefficiently and globally via the graph-cut algorithm.
Considering point proximity is a well-known approachfor sampling [20] or multi-model fitting [12, 21, 1]. To thebest of our knowledge, there is no paper exploiting it in thelocal optimization step of methods like LO-RANSAC. Applying the Potts model which penalizes all neighbors having
different labels would be a justifiable choice to be the pairwise energy term. The problem arises when the data contains significantly more outliers close to desired model thaninliers. In that case, penalizing differently labeled neighbors using the same penalty for all classes many times leads
to the domination of outliers forcing all inliers to be labeled
outlier. To overcome this problem, we modified the Potts
model to use different penalties for each neighboring point
pair on the basis of their inlier probability. The proposed
pair-wise energy term is
if Lp 6= Lq
1
X 
1
ES (L) =
(K
+
K
)
if
Lp = Lq = 0 ,q2 p(p,q)∈A 1 − 1 (K + K ) if L = L = 1
p
q
p
q
2
(3)
where Kp = K(φ(p, θ), ǫ), Kq = K(φ(q, θ), ǫ) and (p, q)
is an edge of neighborhood graph A between points p andq. In ES , if both points are labeled as outliers the penalty
is 12 (Kp + Kq ) thus “rewarding” label 0 if the neighboring
points are far from the model. The penalty of considering apoint as inlier is 1 − 12 (Kp + Kq ) which rewards the label
if the points are close to the model.
The proposed overall energy measuring the fitness ofpoints to a model and considering spatial coherence is
E(L) = EK (L) + λES (L), where λ is a parameter balancing the terms. The globally optimal labeling L∗ =arg minL E(L) can easily be determined in polynomial
time using the graph-cut algorithm.

3. GC-RANSAC
In this section, we include the proposed energy
minimization-based local optimization into RANSAC. Benefiting from this approach, the LO step is simpler andcleaner than that of LO-RANSAC.
The main algorithm is shown in Alg.1. The first step isthe determination of neighborhood graph A for which weuse a sphere with a predefined radius r – this is a parameterof the algorithm – and Fast Approximate Nearest Neighbors
algorithm [19]. In Alg. 1, function H is as follows [7]:H(|L∗ |, µ) =log(µ),
log(1 − PI )

(4)


∗ 
|
where PI = |Lm | / |Pm . It calculates the required iteration
number of RANSAC on the basis of desired probability µ,
the size of the required minimal point set m and the inlier
number |L∗ | regarding to the current so-far-the-best model.
Note that norm | · | applied to the labeling counts the inliers.
Every kth iteration draws a minimal sample using a sampling strategy, e.g. PROSAC [4], then computes the parameters θk of the implied model and its support
X
K(φ(p, θk ), ǫ)
(5)
wk =
p∈P

w.r.t. the data points, where function K is a Gaussian-kernel
as proposed in Eq. 2. If wk is higher than that of the so-farthe-best model w∗ , this model is considered the new so-farthe-best, all parameters are updated, i.e. the labeling, model
parameters and support, and local optimization is applied
if needed. Note that the application criterion of the local
optimization step is discussed later.
The proposed local optimization is written in Alg. 2. The
main iteration can be considered as a grab-cut-like [24] alternation consisting of two major steps: (i) graph-cut and(ii) model re-fitting. The construction of problem graph G
using unary and pair-wise terms Eqs. 1, 3 is shown in Alg. 3.
Functions AddTerm1 and AddTerm2 add unary (Eq. 1) andbinary (Eq. 3) costs, respectively, to the problem graph.
Such graph construction is covered in depth in [13] (Section
4). Graph-cut is applied to G determining the optimal labeling L which considers the spatial coherence of the points
and their distances from the so-far-the-best model. Modelparameters θ are computed using a 7m-sized random subsetof the inliers in L, thus speeding up the process, similarly
to [15] does, where m is the size of a minimal sample, e.g.
m = 2 for lines. Note that 7m is set by exhaustive experimentation in [15] and this value also suited for us. Finally, the support w of θ is computed and the so-far-the-bestmodel is updated if the new one has higher support, otherwise the process terminates. After the main algorithm, a local optimization step is performed if it has not been yet applied to the obtained so-far-the-best model. Then the model
parameters are re-estimated using the whole inlier set similarly to what plain RANSAC does.
Remark: Adding to the local optimization step a
RANSAC-like procedure selecting 7m-size samples isstraightforward. In our experiments, it had a high computational overhead without adding significantly to accuracy.
The criterion for applying the LO step was proposed
to be: (i) the model is so-far-the-best and (ii) after a userdefined iteration limit, in [15]. However, in our experiments, this approach still spends significant time on optimizing models which are not promising enough. We introduce a simple heuristic for replacing the iteration limit witha data driven strategy which allows to apply LO only a few
times without deterioration in accuracy.

6735

Algorithm 1 The GC-RANSAC Algorithm.
Input: P – data points; r – sphere radius, ǫ – thresholdǫconf – LO application threshold, µ – confidence;
Output: θ - model parameters; L – labeling
1: w ∗ , nLO ← 0, 0.
2: A ← Build neighborhood-graph using r.
3: for k = 1 → H(|L∗ |, µ) do
4:Sk ← Draw a minimal sample.
5:θk ← Estimate a model using Sk .
6:
wk ← Compute the support of θk .

⊲ Eq. 4

⊲ Eq. 5
if wk > w∗ thenθ ∗ , L∗ , w ∗ ← θ k , Lk , w k
if µ12 > ǫconf then
⊲ Eq. 6
θLO , LLO , wLO ← Local opt.
⊲ Alg. 2
nLO ← nLO + 1.
12:
if wLO > w∗ then13:θ∗ , L∗ , w∗ ← θLO , LLO , wLO
14: if nLO = 0 then15:θ∗ , L∗ , w∗ ← Local opt.
⊲ Alg. 2∗
16: θ ← least squares model fitting using L∗ .

7:
8:
9:
10:
11:

Algorithm 2 Local optimization.
Input: P – data points, L∗ – labeling,w∗ – support, θ∗ – model;∗∗
Output: L∗LO – labeling, wLO– support, θLO– model;∗∗
1: wLO, L∗LO , θLO, changed ← w∗ , L∗ , θ∗ , 1.
2: while changed do
3:
G ← Build the problem graph.

4:
5:
6:
7:
8:
9:
10:

⊲ Alg. 3
L ← Apply graph-cut to G.
I7m ← Select a 7m-sized random inlier set.
θ ← Fit a model using labeling I7m .
w ← Compute the support of θ.
changed ← 0.
∗
if w > wLO
then∗∗θLO , L∗LO , wLO, changed ← θ, L, w, 1.

Algorithm 3 Problem Graph Construction.
Input: P – data points, A – neighborhood-graphθ – model parameters, θ∗ – model;
Output: G – problem graph;
1: G ← EmptyGraph().
2: for p ∈ P do

c0 , c1 ← K(φ(p, θ), 1 − K(φ(p, θ), ǫ)G ← AddTerm1(G, p, c0 , c1 ).
5: for (p, q) ∈ A do
6:c01 , c10 ← 1, 1.
7:
c00 ← 0.5(K(φ(q, θ) + K(φ(p, θ)).
8:c11 ← 1 − 0.5(K(φ(q, θ) + K(φ(p, θ)).
9:G ← AddTerm2(G, p, q, c00 , c01 , c10 , c11 ).
3:
4:

As it is well-known for RANSAC, the required iteration
number k, w.r.t. the inlier ratio η, sample size m and confidence µ, is calculated as k = log(1 − µ)/ log(1 − η m ).
Re-arranging this formula to µ leads to equation µ = 1 −m
10k log(1−η ) which determines the confidence of finding
the desired model in the kth iteration if the inlier ratio is η.
Suppose that the algorithm finds a new so-far-the-bestmodel with inlier ratio η2 in the k2 th iteration, whilst theprevious best model was found in the k1 th iteration withinlier ratio η1 (k2 > k1 , η2 > η1 ). The ratio of the confidences µ12 in those two models is calculated as follows:
m

µ12 =

1 − 10k2 log(1−η2 )
µ2
=
m .
µ1
1 − 10k1 log(1−η1 )(6)In experiments, we observed that a model that leads to termination if optimized often shows a significant increase in
the confidence. Replacing the parameter blocking LO in
the first k iterations, we adopt a criterion µ12 > ǫconf , whereǫconf is a user-defined parameter determining a significant
increase.

4. Experimental Results
In this section, GC-RANSAC is validated both on synthesized and publicly available real world data and compared with plain RANSAC [7], LO-RANSAC [5], LO+ RANSAC, LO’-RANSAC [15], and EP-RANSAC [14]. For
EP-RANSAC, we tuned the threshold parameter to achieve
the lowest mean error and the other parameters were set
to the values reported by the authors. Note that the comparison of the processing time with this method is affectedby the availability of a Matlab implementation only. All
methods apply PROSAC [4] sampling and use MSAC-liketruncated quadratic distances with threshold set to ǫ = 0.3
pixels (similarly as in [15]). EP-RANSAC uses inlier maximization strategy since its cost function cannot be replacedstraightforwardly. The radius of the sphere to determine
neighboring points is 20 pixels and it is applied to the concatenated 4D coordinates of the correspondences. Parameter λ for GC-RANSAC was set to 0.1 and ǫconf = 0.1.
Synthetic Tests on 2D Lines. To compare GC-RANSAC
with the state-of-the-art in a fully controlled environment,
we chose two simple tests: detection of a 2D straight ordashed line. For each trial, a 600 × 600 window and arandom line was generated in its implicit form, sampled at
100 locations and zero-mean Gaussian-noise with σ standard deviation was added to the coordinates. For a straight
line, the points were generated using uniform distribution(see Fig. 2a). For a dashed line, 10 knots were put randomly into the window, then the line is sampled at 10 locations with uniform distribution around each knot, at most
10 pixels far (see Fig. 2b). Finally, k outliers were added tothe scene. 1000 tests were performed on every noise level.

6736

0.25

0.25

GC−RSC
LO−RSC
LO+−RSCLO‘−RSC

0.15

0.1

0.05

0

GC−RSC
LO−RSC
LO+−RSCLO‘−RSC

0.2

Angular Error (°)

Angular Error (°)

0.2

0.15

0.1

0.05

0

1

2

3

4

5

6

7

8

0

9

0

1

2

3

Noise (px)

(a)

6

7

8

9

0.35

GC−RSC
LO−RSC
LO+−RSCLO‘−RSC

0.25

GC−RSC
LO−RSC
LO+−RSCLO‘−RSC

0.3

0.25

Angular Error (°)

0.3

Angular Error (°)

5

(b)

0.35

0.2

0.15

0.1

0.05

0

4

Noise (px)

(a)

(b)

Figure 2: An example input for (a) straight and (b) dashedlines. The 1000 black points are outliers, the 100 red ones
are inliers. Best viewed in color.

0.2

0.15

0.1

0.05

0

1

2

3

4

5

6

7

8

9

0

0

1

2

3

4

5

Noise (px)Noise (px)

(c)

(d)

6

7

8

9

Figure 1: The mean angular error (in degrees) of the obtained 2D lines plotted as the function of noise σ (in pixels).
On each noise σ, 1000 runs were performed. The line typeand outlier number is (a) straight line, 100%, (b) straight
line, 500% (c) dashed line, 100% and (c) dashed line, 500%.

L
F

LO
6%
29%

LO+
5%
30%

LO’
4%
24%

GC
15%
32%

Table 1: Percentage of “not-all-inlier” minimal samples
leading to the correct solution during line (L) and fundamental matrix (F) fitting. For lines, the average over 1000
runs on three different outlier percentage (100%, 500%,
1000%) and noise levels 0.0−9.0 px is reported, thus 15000
runs were performed. For F, the mean of 1000 runs on the
AdelaideRMF dataset is shown.
Fig. 1 shows the mean angular error (in degrees) plotted as the function of the noise σ. The first and secondrows report the results of the straight and dashed line cases.
For the two columns, 100 and 500 outliers were added, respectively. According to Fig. 1, GC-RANSAC obtains moreaccurate lines than the competitor algorithms.
Estimation of Fundamental Matrix. Evaluating the performance of GC-RANSAC on fundamental matrix estimation, we used kusvod2 (24 pairs)3 , Multi-H4 (5 pairs),
and AdelaideRMF5 (19 pairs) datasets (see Fig. 3 for examples). Kusvod2 consists of 24 image pairs of different
sizes with point correspondences and fundamental matrices
3 http://cmp.felk.cvut.cz/data/geometry2view/
4 http://web.eee.sztaki.hu/ dbarath/
5 cs.adelaide.edu.au/ hwong/doku.php?id=data

estimated using manually selected inliers. AdelaideRMF
and Multi-H consist a total of 24 image pairs with point
correspondences, each assigned manually to a homography(or the outlier class). For them, all points which are assigned to a homography were considered as inliers and others as outliers. In total, the proposed method was tested
on 48 image pairs from three publicly available datasets for
fundamental matrix estimation. All methods applied the 7point method [10] to estimate F, thus drawing minimal setsof size seven in each RANSAC iteration. For the model
re-estimation from a non-minimal sample in the LO step,
the normalized 8-point algorithm [11] is used. Note that all
fundamental matrices were discarded for which the oriented
epipolar constraint [6] did not hold.
The first three blocks of Table 2, each consisting of fourrows, report the quality of the epipolar geometry estimation on each dataset as the average of 1000 runs on every image pair. The first two columns show the name of
the tests and the investigated properties: (1) LO: the number of applied local optimization steps (graph-cut steps areshown in brackets). (2) E is the geometric error (in pixels)of the obtained model w.r.t. the manually annotated inliers.
For fundamental matrices and homographies, it is definedas the average Sampson distance and re-projection error,
respectively. For essential matrices, it is the mean Sampson distance of the implied fundamental matrix and the correspondences. (3) T is the mean processing time in milliseconds. (4) S is the average number of minimal samples
have to be drawn until convergence, basically, the numberof RANSAC iterations.
It can be clearly seen that for fundamental matrix estimation GC-RANSAC always obtains the most accurate modelusing fewer samples than the competitive methods.

6737

(a) Homography; homogr dataset(b) Homography; EVD dataset(c) Fundamental matrix; kusvod2 dataset(d) Fundamental matrix; AdelaideRMF dataset(e) Essential matrix; Strecha dataset(f) Affine transformation; SZTAKI dataset

Figure 3: Results of GC-RANSAC on example pairs fromeach dataset and problem. Correspondences are drawn bylines and circles, outliers by black lines and crosses, every
third correspondence is drawn.

Estimation of Homography. In order to test homography
estimation we downloaded homogr6 (16 pairs) and EVD7
(15 pairs) datasets (see Fig. 3 for examples). Each consists of image pairs of different sizes from 329 × 278 up
to 1712 × 1712 with point correspondences and manually
selected inliers – correctly matched point pairs. Homogr
dataset consists of short baseline stereo pairs, whilst thepairs of EVD undergo an extreme view change, i.e. widebaseline. All methods apply the normalized four-point algorithm [10] for homography estimation both in the model
generation and local optimization steps. Therefore, eachminimal sample consists of four correspondences.
The 4th and 5th blocks of Table 2 show the mean results
computed using all the image pairs of each dataset. It can beseen that GC-RANSAC obtains the most accurate models
for all but one, i.e. EVD dataset with time limit, test cases.
Estimation of Essential Matrix. To estimate essential
matrices, we used the strecha dataset [26] consisting ofimage sequences of buildings. All image sizes are 3072 ×
2048. The ground truth projection matrices are provided.
The methods were applied to all possible image pairs ineach sequence. The SIFT detector [16] was used to obtaincorrespondences. For each image pair, a reference point
set with ground truth inliers was obtained by calculating
the fundamental matrix from the projection matrices [10].
Correspondences were considered as inliers if the symmetric epipolar distance was smaller than 1.0 pixel. All image
pairs with less than 20 inliers found were discarded. In total,
467 image pairs were used in the evaluation.
The results are reported in the 6th block of Table 2. The
reason of the high processing time is that the mean inlier
ratio is relatively low (27%) and there are many correspondences, 2323, on average. GC-RANSAC obtains the mostaccurate essential matrices both in the wall-clock time limited and solution confidence above 95% experiments. A significant drop can be seen in accuracy for all methods if atime limit is given.
Estimation of Affine Transformation. The SZTAKI
Earth Observation dataset8 [2] (83 image pairs of size
320 × 240) was used to test affine transformation estimation. The dataset contains images of busy road scenes takenfrom a balloon. Due to the altitude of the balloon, the image pair relation is well approximated by an affine transformation. Point correspondences were detected by the SIFT
detector. For ground truth, 20 inliers were selected manually. Point pairs with distance from the ground truth affine
transformation lower than 1.0 pixel were defined as inliers.
6 http://cmp.felk.cvut.cz/data/geometry2view/
7 http://cmp.felk.cvut.cz/wbs/
8 http://mplab.sztaki.hu/remotesensing

6738

The estimation results are shown in the 7th block of Table 2. The reported error is |Ap1 − p2 |, where A is the estimated affine transformation and pk is the point in the kth
image (k ∈ {1, 2}). The methods obtained fairly similar results, however, GC-RANSAC is slightly more accurate. It
is marginally slower due to the neighborhood computation.
However, it is still faster than real time.

λ=0
λ = 0.1
λ=1
λ = 10λ = 100

100(a)Ratio (%)

80
60
40
20
0

L

F

E

H

A

ProblemConvergence from a Not-All-Inlier Sample. Table 1 reports the frequencies when a “not-all-inlier” sample led tothe correct model. For lines (L), it is computed using 1000
runs on each outlier (100, 500 and 1000) and noise level(from 0.0 up to 9.0 pixels). Thus 15000 runs were performed. A minimal sample is counted as a “not-all-inlier”
if it contains at least one point farther from the ground truth
model than the ground truth noise σ.
For fundamental matrices (F), the frequencies of successfrom a “not-all-inlier” sample are computed as the mean of1000 runs on all pairs of the AdelaideRMF dataset. In thisdataset, all inliers are labeled manually, thus it is easy tocheck whether a sample point is inlier or not.

120

(b)

Evaluation of the criterion for the local optimization.
The proposed criterion (Eq. 6) ensuring that local optimization is applied only to the most promising model candidates
is tested in this section. We applied GC-RANSAC to all
problems combined with the proposed and the standard approaches. The standard technique sets an iteration limit (default value: 50) and the LO procedure is afterwards applied
to all models that are so far the best. Fig. 4b reports theratio of each property (processing time – dark blue, LO –light blue, and GC steps – yellow, geometric error – brown)of the proposed and standard approaches. The new criterion
leads to significant improvement in the processing time withno deterioration in accuracy.
Processing Time. Fig. 4c shows the breakdown of theprocessing times of GC-RANSAC applied to each problem.
The time demand of the neighborhood computation (darkblue) linearly depends on the point number. The light blue
one is the time demand of the sampling and model fitting

Ratio (%)

80
60
40
20
0

L

F

E

H

A

ProblemNeighborhood Calc.
Fitting and Sampling
Model Verification
Graph Cut100

Ratio (%)

80(c)
Evaluation of the λ setting. To evaluate the effect of the
λ parameter balancing the spatial coherence term, we applied GC-RANSAC to all problems with varying λ. The
evaluated values are: (i) λ = 0, which turns off the spatial
coherence term, (ii) λ = 0.1, (iii) λ = 1, (iv) λ = 10, and(v) λ = 100. Fig. 4a shows the ratio of the geometric errors for λ 6= 0 and λ = 0 (in percent). For all investigatednon-zero λ values, the error is lower than for λ = 0. Since
λ = 0.1 led to the most accurate results on average, wechose this setting in the tests.

Processing Time
LO Number
GC Number
Geometric Error

100

60
40
20
0

L

F

E

H

A

Problem

Figure 4: (a) The effect of the λ choice weighting the spatial term. The ratio of the geometric error (in percentage)compared to the λ = 0 case (no spatial coherence) for eachproblem (L – lines, F – fundamental matrix, E – essential
matrix, H – homography, A – affine transformation). (b)The effect of replacing the iteration limit before the first LO
applied with the proposed criterion, i.e. the confidence radically increases. The ratios (in percentage) of each propertyof the proposed and that of standard approaches. (c) The
breakdown of the processing times in percentage w.r.t. thetotal runtime. All values were computed as the mean of all
tests. Best viewed in color.

step, the yellow and brown bars show the model verification(support computation) and the proposed local optimization
step, respectively. The sampling and model fitting part dominates the process.

5. Conclusion
GC-RANSAC was presented. It is more geometricallyaccurate than state-of-the-art methods. It runs in real-time
for many problems at a speed approximately equal to theless accurate alternatives. It is much simpler to implement in a reproducible manner than any of the competitors(RANSAC’s with local optimization). Its local optimiza-

6739

F, #24
F, #19F, #4
H, #15E, #467
A, #52

H, #16

kusvod2
Adelaide
Multi-H
EVD
homogr
strechaSZTAKI

LO
E
T
S
LO
E
T
S
LO
E
T
S
LO
E
T
S
LO
E
T
S
LO
E
T
S
LO
E
T
S

Approx. 60 FPS (or 99% confidence)
RSC
LO
LO+
LO’
GC
–
2
2
2 1 (3)
5.01
4.95
4.97
5.02 4.65
6.2
6.1
6.3
5.9
4.6
117
96
99
111
70
–
2
2
2 1 (3)
0.55
0.53
0.52
0.55 0.50
14.2
14.8
14.9
14.1 18.9
124
113
113
122
116
–
1
1
1 1 (3)
0.35
0.34
0.34
0.34 0.32
10.3
11.5
11.1
10.3 14.6
83
76
76
82
74
–
2
2
2 2 (2)
1.53
1.63
1.51
1.58 1.53
16.8
18.3
18.0
16.8 19.2
320
298
301
318
301
–
2
2
2 1 (3)
0.53
0.53
0.53
0.53 0.51
7.1
10.4
9.8
7.1
7.6
193
175
175
189
159
–
1
1
1 1 (1)11.81 12.34 12.07 12.12 11.6
11.6
17.3
17.2
17.2 17.3
31
30
31
31
30
–
1
1
1 1 (3)
0.41
0.41
0.41
0.41 0.40
3.5
3.2
3.2
3.2 10.3
26
26
26
26
26

RSC
–
5.18
4.9
93
–
0.44
262.7
1 363
–
0.33
12.8
107
–
0.96
247.3
4 303
–
0.50
17.1
450
–
3.03
3 581.9
3 654
–
0.45
1.7
9

LO
1
5.08
5.2
76
2
0.45
194.2
1 126
2
0.33
15.1
89
4
0.95
248.0
4 203
2
0.50
10.1
212
7
2.95
3 638.5
3 646
1
0.46
1.7
9

Confidence 95%
LO+
LO’
1
1
5.03
5.22
5.1
4.9
78
87
2
3
0.43
0.44
210.9
237.1
1 205 1 305.00
1
2
0.33
0.34
14.1
12.4
90
100
4
4
0.95
0.96
251.3
247.0
4 248
4 291
2
2
0.49
0.50
9.9
8.5
214
226
7
7
2.94
2.87
3 648.4
3 570.0
3 634
3 653
1
1
0.44
0.45
1.7
1.7
9
9

EP-RSC
–
7.87
439.9
–
–
0.71
2 121.9––
0.44
2 371.8
–
–
1.17
> 104
–
–
0.58
3 339.7
–
–
3.32
> 106
–
–
0.48
4 718.2
–

GC
2 (3)
4.69
3.6
53
2 (4)
0.43
227.1
1 115
1 (3)
0.32
36.0
78
3 (6)
0.92
249.9
4 204
1 (4)
0.47
7.9
165
7 (7)
2.83
3 466.4
3 651
1 (3)
0.41
10.2
9

Table 2: Fundamental matrix estimation applied to kusvod2 (24 pairs), AdelaideRMF (19 pairs) and Multi-H (4 pairs)
datasets, homography estimation on homogr (16 pairs) and EVD (15 pairs) datasets, essential matrix estimation on thestrecha dataset (467 pairs), and affine transformation estimation on the SZTAKI Earth Observation benchmark (52pairs). Thus the methods were tested on total on 597 image pairs. The datasets, the problem (F/H/E/A), the number ofthe image pairs (#) and the reported properties are shown in the first three columns. The next five report the results at 99%
confidence with a time limit set to 60 FPS, i.e. the run is interrupted after 1/60 secs (EP-RANSAC is removed since it cannot
be applied in real time). For the other columns, there was no time limit but the confidence was set to 95%. Values are themeans of 1000 runs. LO is the number of local optimizations and the number of graph-cut runs are shown in brackets. The
geometric error (E, in pixels) of the estimated model w.r.t. the manually selected inliers is written in each second row; themean processing time (T , in milliseconds) and the required number of samples (S) are written in every 3th and 4th rows.
The geometric error is the Sampson distance for F and E, and the projection error for H and A.
tion step is globally optimal for the so-far-the-best model
parameters. We also proposed a criterion for the application of the local optimization step. This criterion leads toa significant improvement in processing time with no deterioration in accuracy. GC-RANSAC can be easily inserted
into USAC [23] and be combined with its ”bells and whistles“ like PROSAC sampling, degeneracy testing and fastevaluation with early termination.

Acknowledgement

D. Barath was supported by the European Union,
co-financed by the European Social Fund (EFOP-3.6.3VEKOP-16-2017-00001) and the Hungarian National Research, Development and Innovation Office grant VKSZ 141-2015-0072. J. Matas was supported by the Czech Science
Foundation Project GACR P103/12/G084.

6740

References[1] D. Barath, J. Matas, and L. Hajder. Multi-H: Efficient recovery of tangent planes in stereo images. In British Machine
Vision Conference, 2016.
[2] C. Benedek and T. Szirányi. Change detection in optical aerial images by a multilayer conditional mixed markov
model. Transactions on Geoscience and Remote Sensing,2009.
[3] Y. Boykov, O. Veksler, and R. Zabih. Markov random fields
with efficient approximations. In Computer Vision and Pattern Recognition. IEEE, 1998.
[4] O. Chum and J. Matas. Matching with PROSAC-progressive
sample consensus. In Computer Vision and Pattern Recognition. IEEE, 2005.
[5] O. Chum, J. Matas, and J. Kittler. Locally optimized ransac.
In Joint Pattern Recognition Symposium. Springer, 2003.
[6] O. Chum, T. Werner, and J. Matas. Epipolar geometry estimation via RANSAC benefits from the oriented epipolar
constraint. In International Conference on Pattern Recognition, 2004.
[7] M. A. Fischler and R. C. Bolles. Random sample consensus: a paradigm for model fitting with applications to image
analysis and automated cartography. Communications of theACM, 1981.
[8] V. Fragoso, P. Sen, S. Rodriguez, and M. Turk. EVSAC:
accelerating hypotheses generation by modeling matchingscores with extreme value theory. In International Conference on Computer Vision, 2013.
[9] D. Ghosh and N. Kaabouch. A survey on image mosaicking techniques. Journal of Visual Communication and Image
Representation, 2016.
[10] R. Hartley and A. Zisserman. Multiple view geometry incomputer vision. Cambridge university press, 2003.
[11] R. I. Hartley. In defense of the eight-point algorithm. Transactions on Pattern Analysis and Machine Intelligence, 1997.
[12] H. Isack and Y. Boykov. Energy-based geometric multimodel fitting. International Journal of Computer Vision,
2012.
[13] V. Kolmogorov and R. Zabin. What energy functions can be
minimized via graph cuts? Pattern Analysis and MachineIntelligence, 2004.
[14] H. Le, T.-J. Chin, and D. Suter. An exact penalty method for
locally convergent maximum consensus.
[15] K. Lebeda, J. Matas, and O. Chum. Fixing the locally optimized ransac. In British Machine Vision Conference. Citeseer, 2012.
[16] D. G. Lowe. Object recognition from local scale-invariant
features. In International Conference on Computer vision.
IEEE, 1999.
[17] J. Matas, O. Chum, M. Urban, and T. Pajdla. Robust widebaseline stereo from maximally stable extremal regions. Image and Vision Computing, 2004.
[18] D. Mishkin, J. Matas, and M. Perdoch. MODS: Fast androbust method for two-view matching. Computer Vision andImage Understanding, 2015.

[19] M. Muja and D. G. Lowe. Fast approximate nearest neighbors with automatic algorithm configuration. International
Conference on Computer Vision Theory and Applications,2009.
[20] D. Nasuto and J. M. B. R. Craddock. NAPSAC: High noise,high dimensional robust estimation - its in the bag. 2002.
[21] T. T. Pham, T.-J. Chin, K. Schindler, and D. Suter. Interacting
geometric priors for robust multimodel fitting. Transactions
on Image Processing, 2014.
[22] P. Pritchett and A. Zisserman. Wide baseline stereo matching. In International Conference on Computer Vision. IEEE,
1998.
[23] R. Raguram, O. Chum, M. Pollefeys, J. Matas, and J.-M.
Frahm. USAC: a universal framework for random sample
consensus. Transactions on Pattern Analysis and MachineIntelligence, 2013.
[24] C. Rother, V. Kolmogorov, and A. Blake. Grabcut: Interactive foreground extraction using iterated graph cuts. In
Transactions on Graphics. ACM, 2004.
[25] C. Sminchisescu, D. Metaxas, and S. Dickinson. Incremental
model-based estimation using geometric constraints. PatternAnalysis and Machine Intelligence, 2005.
[26] C. Strecha, R. Fransens, and L. Van Gool. Wide-baseline
stereo from multiple views: a probabilistic account. In Conference on Computer Vision and Pattern Recognition. IEEE,
2004.
[27] P. H. S. Torr and D. W. Murray. Outlier detection and motion segmentation. In Optical Tools for Manufacturing andAdvanced Automation. International Society for Optics andPhotonics, 1993.
[28] P. H. S. Torr and A. Zisserman. MLESAC: A new robust estimator with application to estimating image geometry. Computer Vision and Image Understanding, 2000.
[29] P. H. S. Torr, A. Zisserman, and S. J. Maybank. Robust detection of degenerate configurations while estimating the fundamental matrix. Computer Vision and Image Understanding,1998.
[30] R. Zabih and V. Kolmogorov. Spatially coherent clustering
using graph cuts. In Conference onComputer Vision and Pattern Recognition. IEEE, 2004.
[31] M. Zuliani, C. S. Kenney, and B. S. Manjunath. The multiransac algorithm and its application to detect planar homographies. In International Conference on Image Processing.
IEEE, 2005.

6741