11institutetext: Faculty of Informatics, Eotvos Lorand University
22institutetext: Department of Computer Science, ETH Zurich 33institutetext:
VRG, Faculty of Electrical Engineering, Czech Technical University in Prague
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
# Deep MAGSAC++

Wei Tong1 Jiri Matas3 and Daniel Barath2

###### Abstract

We propose Deep MAGSAC++ combining the advantages of traditional and deep
robust estimators. We introduce a novel loss function that exploits the
orientation and scale from partially affine covariant features, e.g., SIFT, in
a geometrically justifiable manner. The new loss helps in learning higher-
order information about the underlying scene geometry. Moreover, we propose a
new sampler for RANSAC that always selects the sample with the highest
probability of consisting only of inliers. After every unsuccessful iteration,
the probabilities are updated in a principled way via a Bayesian approach. The
prediction of the deep network is exploited as prior inside the sampler.
Benefiting from the new loss, the proposed sampler and a number of technical
advancements, Deep MAGSAC++ is superior to the state-of-the-art both in terms
of accuracy and run-time on thousands of image pairs from publicly available
real-world datasets for essential and fundamental matrix estimation.

###### Keywords:

RANSAC; epipolar geometry; inlier probability prediction; sampler

##  1 Introduction

The RANSAC (RANdom SAmple Consensus) algorithm proposed by Fischler and Bolles
[16] in 1981 has become the most widely used robust estimator in computer
vision. RANSAC and its variants have been successfully applied in a wide range
of vision applications, _e.g._ , short baseline stereo [45, 47], wide baseline
matching [34, 28, 30], to perform [54, 8] or initialize multi-model fitting
algorithms [23, 33], image mosaicing [19], pose-graph initialization for SfM
pipelines [40, 41], motion segmentation [45]. Briefly, RANSAC repeatedly
selects random minimal subsets of the data points, and fits a model, _e.g._ ,
a 3D plane to three points or an essential matrix to five 2D point
correspondences. The quality of the model is then measured, for instance, as
the cardinality of its support, _i.e._ , the number of data points closer than
a manually set inlier-outlier threshold. Finally, the model with the highest
quality, polished, _e.g._ , by least-squares fitting on all inliers, is
returned.

Since the publication of RANSAC, a number of modifications have been proposed
replacing components of the original algorithm. To improve the accuracy by
better modelling the noise in the data, different model quality calculation
techniques have been investigated. For instance, MLESAC [46] estimates the
quality by a maximum likelihood procedure with all its beneficial properties.
In MSAC [46], the loss is formulated as a truncated quadratic error by
assigning constant loss to the outliers (_i.e._ , points with residuals larger
than the inlier-outlier threshold) and a quadratic one to the inliers. In the
recently proposed MAGSAC++ [9], the model quality calculation is formulated as
a marginalization over a range of noise scales. It allows MAGSAC++ to be
significantly less sensitive to the inlier-outlier threshold than other robust
estimators. According to a recent survey [26], MAGSAC++ is currently the most
accurate robust estimator. In this paper, we focus on combining MAGSAC++ with
deep learning improvements trained on a new loss and combined with a new
sampler.

Improving the sampler accelerates the robust estimation procedure via
selecting a good sample early and triggering the termination criterion. The
NAPSAC [31] sampler assumes that inliers are spatially coherent and, thus, it
draws samples from a hyper-sphere centered at the first, randomly selected,
location-defining point. The GroupSAC algorithm [32] assumes that inliers are
often “similar” and, thus, can be separated into groups. PROSAC [14] exploits
an a priori predicted inlier probability rank of each point and starts the
sampling with the most promising ones. Progressively, samples that are less
likely to lead to the sought model are drawn. The sampler used in [13] assumes
that we are given prior knowledge, _e.g._ , from a deep network, about the
inlier probability of each point. It selects samples according to the
probability assuming that it follows a categorical distribution over the
discrete set of observations.

Figure 1: Deep MAGSAC++. The point coordinates, SIFT orientations and scales
and other information (_e.g._ , SNN ratio [25]) are fed into the network. The
predicted inlier probabilities are used as prior and updated inside MAGSAC++
[9] by the proposed AR-sampler (see Section 4). The estimated model, _e.g._
relative pose, is used to calculate the loss that combines the proposed Affine
Loss (see Section 3) and other widely used ones.

Recently, several algorithms were proposed approaching the robust relative
pose estimation problem using neural networks. Context normalization networks
[50] is the first paper on the topic which proposes to use PointNet (MLP) with
batch normalization [22] as context mechanism. Attentive context normalization
networks [43] introduces a special architectural block for the task. Deep
Fundamental matrix estimation [35] uses differentiable iteratively re-weighted
least-squares with predicted weights. The OANet algorithm [52] introduces
several architectural blocks for the correspondence filtering. Neural Guided
RANSAC [13] uses a CNe-like architecture with a different training objective.
The predicted correspondence scores are exploited inside RANSAC by using a
guided sampling algorithm that helps in finding accurate models early. CLNet
[53] introduces several algorithmic and architectural improvements first to
remove gross outliers with iterative pruning. These techniques, in general,
provide alternatives for tentative correspondence pre-filtering and weighting.
However, they do not replace standard robust estimation as it is shown in [3].

This paper has three main contributions. First, we focus on combining two
state-of-the-art algorithms, _i.e._ , MAGSAC++ [9] and NG-RANSAC [13], in
order to improve the relative pose accuracy on a wide range of scenes. Second,
we propose a way of incorporating the orientation and scale from, _e.g._ ,
SIFT features, in a geometrically meaningful manner directly in the loss
function minimized during training. The new loss leads to more accurate
results than simply using pose or epipolar errors. Third, we propose a new
sampler that exploits the predicted inlier probabilities in a more effective
way than [14, 13]. The new sampler leads to the best results even when the SNN
[25] ratio is considered as the inlier probability without using neural
networks. It outperforms the widely used PROSAC sampler [14] even in this
standard scenario.

##  2 Deep MAGSAC++

We propose a learning-based approach for robust model fitting, see Fig. 1.
Even though we will describe it focusing on epipolar geometry estimation, the
method is general.

The MAGSAC++ algorithm formulates the robust estimation problem as an
iteratively re-weighted least-squares (IRLS) approach. Both the model quality
calculation and inlier selection are done without making strict inlier-outlier
decisions. The model parameters $\theta_{i+1}$ in the $(i+1)$ th step of the
IRLS are calculated from the point-to-model residual function,
$D(\theta_{i},\textbf{p})$, where p is a point from the input sets, as
follows:

$\theta_{i+1}=\text{arg
min}_{\theta}\sum_{\textbf{p}\in\mathcal{P}}w(D(\theta_{i},\textbf{p}))D^{2}(\theta,\textbf{p}),$
(1)

where the weight of point p is determined by marginalizing over the noise
scale $\sigma$ as

$w(D(\theta_{i},\textbf{p}))=\int_{0}^{+\infty}\text{P}(\textbf{p}\;|\;\theta_{i},\sigma)f(\sigma){\mathrm{d}\sigma}$
(2)

and $\theta_{0}=\theta$, _i.e._ , the initial model from the minimal sample.

The inlier residuals are assumed to be calculated as the sum of normally
distributed squared variables (_e.g._ , re-projection error), thus having
$\chi^{2}$-distribution. The noise standard deviation $\sigma$ is assumed to
be uniformly distributed within interval $(0,\sigma_{\text{max}})$. The weight
function defined in (2) is the marginal density of the inlier residuals as
follows:

$\displaystyle
w(r)=\int_{0}^{+\infty}g(r\;|\;\sigma)f(\sigma){\mathrm{d}\sigma}.$ (3)

Let $\tau(\sigma)=k\sigma$ be the chosen quantile of the $\chi$-distribution.
For residual $0\leq r\leq k\sigma_{\text{max}}$,

$\displaystyle
w(r)=\frac{1}{\sigma_{\text{max}}}\int_{r/k}^{\sigma_{\text{max}}}g(r\;|\;\sigma){\mathrm{d}\sigma}=$
$\displaystyle\frac{1}{\sigma_{\text{max}}}C(\nu)2^{\frac{\nu-1}{2}}\left({\Gamma}\left(\frac{\nu-1}{2},\frac{r^{2}}{2\sigma^{2}_{\text{max}}}\right)-{\Gamma}\left(\frac{\nu-1}{2},\frac{k^{2}}{2}\right)\right)$

and, for $r>k\sigma_{\text{max}}$, weight $w(r)=0$. Function

$\Gamma(a,x)=\int_{x}^{+\infty}t^{a-1}\exp{(-t)}{\mathrm{d}t}$

is the upper incomplete gamma function. Due to the design choices, weight
$w(r)$ is positive and decreases on interval
$[0,\;\tau(\sigma_{\text{max}})]$. There is a $\rho$-function of an
M-estimator which is minimized by IRLS using $w(r)$, and each iteration
guarantees a non-increase in its loss function (chapter 9 of [27]).
Consequently, it converges to a local minimum.

The IRLS in Eq.(1) where $w(r)$ is defined by (3) with
$\tau(\sigma)=3.64\sigma$ (where $3.64$ is the $0.99$ quantile of the
$\chi$-distribution with $\nu=4$), is called $\sigma$-consensus++ for problems
using point correspondences. Parameter $\sigma_{\text{max}}$ is a user-defined
maximum noise level parameter. The $\sigma$-consensus++ algorithm is applied
for fitting non-minimal samples and, also, as a post-processing to improve the
output of any robust estimator.

In order to improve MAGSAC++ using recent neural network-based techniques, we
adopt the Neural Guided RANSAC (NG-RANSAC) architecture [13]. The NG-RANSAC
algorithm predicts the probability of each point correspondence being inlier
and uses a weighted sampling approach to incorporate this information in the
robust estimation procedure. Due to the neural network and the robust
estimator being loosely connected in such a manner, we develop an efficient
learning-based robust estimator using MAGSAC++ as the core algorithm.

While training the weights with sparse correspondences end-to-end, the inlier
masks and selected samples are used to update the gradients of the neurons and
generate point probabilities as weights for the consequent epochs. We use
additional side information as well, namely, the scale and orientation of each
SIFT feature. In the next sections, we focus on improving the network by
considering new geometry-induced loss functions and, also, propose a new
sampler more efficiently exploiting the predicted probabilities than the
importance sampler from [13] and PROSAC proposed by Chum _et al._ [14].

##  3 Scale and Orientation Loss

We propose a new loss function considering that, in most of the two-view
cases, we apply feature detectors that provide more information about the
underlying scene geometry than simply the point coordinates. For instance, ORB
[39] features contain the orientation of the image patches centered on the
detected points in the two images. In addition to the feature orientation, the
SIFT [25] and SURF [12] detectors return a uniform scaling parameter. Even the
full affine warping of the patch can be recovered when using affine-covariant
feature detectors, _e.g._ , Hessian-Affine [29] or MODS [30]. The point
correspondence and the affine warp is the so-called affine correspondence [6].

To the best of our knowledge, the additional information that such features
provide has not yet been exploited in a geometrically meaningful manner to
minimize the training loss. Recent deep networks, _e.g._ , [13], only use it
as side information added to the learned feature vectors or for pre-filtering
correspondences.

Figure 2:  (Left) Visualization of the orientation- and scale-covariant
features. Point P and the surrounding patch projected into cameras
$\textbf{K}_{1}$ and $\textbf{K}_{2}$. The rotation of the feature in the
$i$th image is $\alpha_{i}\in[0,2\pi)$, with size, $q_{i}\in\mathbb{R}$,
$i\in\\{1,2\\}$. (Right) The geometric interpretation of the relations of
local affine transformations and the epipolar geometry (Eq. (5); proposed in
[5]). The normal $\mathbf{n}_{1}$ of epipolar line $\mathbf{l}_{1}$ is mapped
by affinity $\mathbf{A}\in\mathbb{R}^{2\times 2}$ into the normal
$\mathbf{n}_{2}$ of epipolar line $\mathbf{l}_{2}$.

###  3.1 Affine Epipolar Error

In order to interpret fully or partially affine-covariant features, we adopt
the definition from [5] and the affine transformation model from [4]. We
consider an affine correspondence (AC) a triplet:
$(\mathbf{p}_{1},\mathbf{p}_{2},\mathbf{A})$, where
$\mathbf{p}_{1}=[u_{1},\quad v_{1},\quad 1]^{\text{T}}$ and
$\mathbf{p}_{2}=[u_{2},\quad v_{2},\quad 1]^{\text{T}}$ are a corresponding
homogeneous point pair in the two images, and

$\displaystyle\begin{array}[]{lcl}\mathbf{A}&=&\begin{bmatrix}a_{1}&a_{2}\\\
a_{3}&a_{4}\end{bmatrix}=\begin{bmatrix}\cos(\alpha)&-\sin(\alpha)\\\
\sin(\alpha)&\cos(\alpha)\end{bmatrix}\begin{bmatrix}q_{u}&w\\\
0&q_{v}\end{bmatrix},\end{array}$ (5)

is a $2\times 2$ linear transformation describing the relationship of the
infinitesimal image patches centered on points $\mathbf{p}_{1}$ and
$\mathbf{p}_{2}$, where $\alpha$ is rotation, $q_{u}$ and $q_{v}$ are the
scales along the axes, and $w$ is the shear parameter. Formally, $\mathbf{A}$
is defined as the first-order Taylor-approximation of the
$\text{3D}\to\text{2D}$ projection functions. For perspective cameras,
$\mathbf{A}$ is the first-order approximation of the related $3\times 3$
homography.

The relationship of affine correspondences and epipolar geometry is shown in
[36, 5], with [5] providing a geometrically interpretable definition of the
constraint as

$\mathbf{A}^{-\text{T}}\mathbf{n}_{1}=-\mathbf{n}_{2}$ (6)

where $\mathbf{n}_{1}=(\mathbf{F}^{\text{T}}\mathbf{p}_{2})_{[1:2]}$ and
$\mathbf{n}_{2}=(\mathbf{F}\mathbf{p}_{1})_{[1:2]}$ are the normals of the
epipolar lines in the two images, and lower-index $\mathbf{v}_{[1:2]}$ selects
the first two coordinates of a vector $\mathbf{v}$. See the right plot of Fig.
2.

While constraint (6) is originally formulated as two linear equations in [5]
to simplify the estimation, it can be re-written to two geometrically
meaningful constraints that we can use in the loss function. First, (6)
implies that $\mathbf{A}^{-\text{T}}$ rotates the normal in the first image to
its corresponding pair in the second one as
$(\mathbf{A}^{-\text{T}}\mathbf{n}_{1})\times\mathbf{n}_{2}=0$, where the
angle between $\mathbf{A}^{-\text{T}}\mathbf{n}_{1}$ and $\mathbf{n}_{2}$ can
be used as an error for an estimated fundamental matrix $\mathbf{\widehat{F}}$
as follows:

$f(\mathbf{A},\mathbf{\widehat{F}},\mathbf{p}_{1},\mathbf{p}_{2})=\cos^{-1}\frac{\left(\mathbf{A}^{-\text{T}}(\mathbf{\widehat{F}}^{\text{T}}\mathbf{p}_{2})_{[1:2]}\right)(\mathbf{\widehat{F}}\mathbf{p}_{1})_{[1:2]}}{\left|\mathbf{A}^{-\text{T}}(\mathbf{\widehat{F}}^{\text{T}}\mathbf{p}_{2})_{[1:2]}\right|\left|(\mathbf{\widehat{F}}\mathbf{p}_{1})_{[1:2]}\right|}.$
(7)

Second, (6) implies that the scale change is

$\sqrt{\det\mathbf{A}}=\frac{|\mathbf{n}_{2}|}{|\mathbf{n}_{1}|}=\frac{\left|(\mathbf{F}\mathbf{p}_{1})_{[1:2]}\right|}{\left|(\mathbf{F}^{\text{T}}\mathbf{p}_{2})_{[1:2]}\right|}$
(8)

providing another geometrically meaningful error as

$g(\mathbf{A},\mathbf{\widehat{F}},\mathbf{p}_{1},\mathbf{p}_{2})=\sqrt{\det\mathbf{A}}-\frac{\left|(\mathbf{\widehat{F}}\mathbf{p}_{1})_{[1:2]}\right|}{\left|(\mathbf{\widehat{F}}^{\text{T}}\mathbf{p}_{2})_{[1:2]}\right|}.$
(9)

Overall, these errors can be used to measure the quality of a fundamental or
essential matrix given an affine correspondence.

###  3.2 Affine Loss Function

In practice, we are usually given partially affine-covariant features, _e.g._
, SIFT, that do not allow using error functions (7) and (9) directly. In order
to define a justifiable loss, we first approximate the local affine
transformation $\widehat{\mathbf{A}}$ using the rotations $\alpha_{1}$,
$\alpha_{2}$ and scales $q_{1}$, $q_{2}$ from the SIFT features via the affine
transformation model in (5) assuming that shear $w=0$, rotation
$\alpha=\alpha_{2}-\alpha_{1}$, and $q_{u}=q_{v}=q_{2}/q_{1}$ is a uniform
scaling along the axes similarly as in [4], see the left plot of Fig. 2. It is
important to note that directly using $\widehat{\mathbf{A}}$ to measure the
error of the prediction is still not viable since $\widehat{\mathbf{A}}$ is
only an approximation and, thus, (7) and (9) are not zero even if the ground
truth fundamental matrix is used. We, therefore, define our orientation loss
as

$L_{\text{ori}}({\dots})=\left|f(\widehat{\mathbf{A}},\mathbf{\widehat{F}},\mathbf{p}_{1},\mathbf{p}_{2})-f(\widehat{\mathbf{A}},\mathbf{F},\mathbf{p}_{1},\mathbf{p}_{2})\right|,$

and the scale loss as

$L_{\text{scale}}({\dots})=\left|g(\widehat{\mathbf{A}},\mathbf{\widehat{F}},\mathbf{p}_{1},\mathbf{p}_{2})-g(\widehat{\mathbf{A}},\mathbf{F},\mathbf{p}_{1},\mathbf{p}_{2})\right|,$

where $\mathbf{F}$ is the ground truth fundamental matrix used as a target for
the network and $\mathbf{\widehat{F}}$ is the prediction. Measuring the error
in this way allows ignoring the approximative nature of
$\widehat{\mathbf{A}}$. The final loss minimized when training the network is

$\displaystyle
L(\mathbf{F},\mathbf{\widehat{F}},\mathcal{P})=\sum_{(\mathbf{p}_{1},\mathbf{p}_{2},\widehat{\mathbf{A}})\in\mathcal{P}}w_{\text{ori}}L_{\text{ori}}(\mathbf{F},\mathbf{\widehat{F}},\widehat{\mathbf{A}},\mathbf{p}_{1},\mathbf{p}_{2})+w_{\text{scale}}L_{\text{scale}}(\mathbf{F},\mathbf{\widehat{F}},\widehat{\mathbf{A}},\mathbf{p}_{1},\mathbf{p}_{2})+\cdots$

where
$\mathcal{P}=\\{(\mathbf{p}_{1},\mathbf{p}_{2},\alpha_{1},\alpha_{2},q_{1},q_{2})\;|\;\mathbf{p}_{1},\mathbf{p}_{2}\in\mathbb{R}^{2}\wedge\alpha_{1},\alpha_{2}\in[0,2\pi]\wedge
q_{1},q_{2}\in\mathbb{R}^{+}\\}$ is the set of SIFT correspondences,
$w_{\text{ori}}$ and $w_{\text{scale}}$ are weighting parameters, and $\cdots$
represents other frequently used error metrics, _e.g._ , epipolar or pose
error, or inlier number. To propagate the gradient, the training objective
$L(w)$ is defined as the minimization of the expected task loss, similarly as
in [13]. Since integrating over all possible hypotheses to calculate the
expectation is infeasible, the gradients for the categorical distribution over
the discrete set of observations are approximated by drawing $K$ samples as

$\partialderivative{w}L(w)\approx\frac{1}{K}\sum^{K}_{k=1}[l(\hat{h})\partialderivative{w}\log
p(H_{k};w)],$

where $K$ is the number of samples used for approximating the gradients. The
task loss is $l(\hat{h})$, and $p(H_{k};w)$ denotes the learned distribution
of the $k$th sample.

##  4 Adaptive Re-ordering Sampler

In this section, we describe a new sampler that always selects the sample with
the highest probability of containing only inliers. This probability is
updated adaptively according to the success or failure of the current minimal
sample in the robust estimation procedure. The new sampler will be called AR-
Sampler in the remainder of the paper.

Let us assume that we are given point correspondences $p_{i_{1}^{t}}$,
$p_{i_{2}^{t}}$, $\dots$, $p_{i_{n}^{t}}\in\mathcal{P}$ with inlier
probabilities $\mu_{i_{1}^{t}}$, $\mu_{i_{2}^{t}}$, $\dots$,
$\mu_{i_{n}^{t}}\in[0,1]$ such that
$\mu_{i_{1}^{t}}\geq\mu_{i_{2}^{t}}\geq\dots\geq\mu_{i_{n}^{t}}$, where
$i_{1}^{t},\dots,i_{n}^{t}\in[1,n]$ are indices in the $t$th RANSAC iteration
ensuring that the points are ordered by the inlier probabilities in a
descending order. The probability of sample
$S=(p_{j_{1}},p_{j_{1}},\dots,p_{j_{m}})\in\mathcal{P}^{\times}$ consisting
only of inliers is calculated as $\mu_{S}=\prod_{k=1}^{m}\mu_{j_{k}}$, where
$m$ is the sample size, _e.g._ , $m=5$ for essential matrix estimation.
Consequently, the optimal sampler maximizes the sample probability of
$S^{*}_{t}=(p_{i_{1}^{t}},p_{i_{1}^{t}},\dots,p_{i_{m}^{t}})$ in the $t$th
iteration to increase the probability of finding the sought model early.

Every unsuccessful RANSAC iteration reduces the inlier probability of the
points in the minimal sample. This stems from the fact that in case of having
an all-inlier sample that is good enough to find the sought model, RANSAC
terminates.111Precisely, RANSAC either terminates immediately when it finds
the sought model or runs until the confidence in the result exceeds the
manually set confidence threshold. In the latter case, the iterations done
after finding the sought model do not change the result.  Otherwise, the
sample is not all-inlier. Therefore, of all the possible inlier-outlier
configurations in the sample, the “all points are inliers” is ruled out, and,
consequently, the inlier probabilities of the sample points decrease,
typically very modestly. In order to model this in a principled way, we update
the probabilities using the Bayesian approach after each RANSAC iteration. We
note that the Bayesian approach ignores the dependencies between points that
appeared in a sample. As prior knowledge, we can either consider the output of
the deep network or even the point ordering that the SNN ratio [25] implies.
In each update, only the points from the current minimal sample are considered
and, thus, the probability of other points remain unchanged in the $t+1$-th
iteration as we did not gather additional information about them.

1:Input: $p_{1},\dots,p_{n}$ – points; $\mu_{1},\dots,\mu_{n}$ – probabilities

2:Input: $S$ – minimal sample; $N_{1},\dots,N_{n}$ – usage numbers

3:Input: $(a_{1},b_{1}),\dots,(a_{n},b_{n})$ – initial distribution parameters

4:Output: $\mu_{1}^{\prime},\dots,\mu_{n}^{\prime}$ – updated inlier
probabilities

5:

6:for $i\in[1,n]$ do

7: if $p_{i}\in S$ then$\triangleright$ Decrease inlier probability $\mu$ for
all points in the sample

8: $a_{i}^{\prime}\leftarrow a_{i}$; $b_{i}^{\prime}\leftarrow b_{i}+N_{i}$

9: $\mu_{i}^{\prime}\leftarrow a_{i}^{\prime}/(a_{i}^{\prime}+b_{i}^{\prime})$

10: else$\triangleright$ Other points have the same probability $\mu$ as
before

11: $\mu_{i}^{\prime}\leftarrow\mu_{i}$

Algorithm 1 Probability Update.

1:Input: $p_{1},\dots,p_{n}$ – points; $\mu_{1},\dots,\mu_{n}$ – inlier probs.

2:Input: $m$ – sample size ; $N_{1},\dots,N_{n}$ – usage numbers

3:Input: $(a_{1},b_{1}),\dots,(a_{n},b_{n})$ – initial distribution parameters

4:Output: $S^{*}$ – minimal sample

5:

6:$i_{1},\dots,i_{n}\leftarrow\text{sort}(\mu_{1},\dots,\mu_{n})$
$\triangleright$ Sort points according to the inlier probability

7:$S^{*}\leftarrow\\{p_{i_{j}}\;|\;j\in[1,m]\\}$$\triangleright$ Sample the
points with the highest probabilities

8:for $p_{i_{j}}\in S^{*}$ do

9: $N_{i_{j}}\leftarrow N_{i_{j}}+1$$\triangleright$ Increase the usage number
of the points in sample $S^{*}$

10:
$\mu_{i_{j}}\leftarrow\text{Update}(a_{i_{j}},b_{i_{j}},\mu_{i_{j}},N_{i_{j}})$
$\triangleright$ Algorithm 1

Algorithm 2 Adaptive Re-ordering Sampler.

The probability of point p being inlier in the $t$th iteration follows the
Bernoulli distribution. Consequently, after being selected $n_{p}$ times
during the robust estimation, it follows the binomial distribution with
parameters $\mu_{p}(n_{p})$ and $n_{p}$. The usual conjugate prior for a
binomial distribution is a beta distribution with prior hyper-parameters
$a(n_{p})$ and $b(n_{p})$, with expectation $a(n_{p})/(a(n_{p})+b(n_{p}))$,
variance

$v=\frac{a(n_{p})b(n_{p})}{(a(n_{p})+b(n_{p}))^{2}(a(n_{p})+b(n_{p})+1)},$

and posterior hyper-parameters $a(n_{p})$ and $b(n_{p})$. The posterior
distribution parameters are $a(n_{p}+1)=a(n_{p})$, $b(n_{p}+1)=b(n_{p})+1$.
The best estimator for $\mu_{p}(n_{p}+1)$ using a quadratic loss function is
an expectation of the posterior distribution. Consequently,

$\mu_{p}(n_{p}+1)=\frac{a(n_{p}+1)}{a(n_{p}+1)+b(n_{p}+1)}.$

For each point p, the initial parameters of the beta distribution $a(1)$ and
$b(1)$ are set using the predicted inlier ratio $\mu_{p}(1)=\mu_{p}^{1}$. We
assume that the inlier probability prediction provides the expectation of the
prior beta distribution and with the same mean precision for all points.
Therefore, the variance $v$ of all these initial beta distributions is equal
and can be learned in advance. Given the learned variance, equations

$\displaystyle\mu_{p}(1)=\frac{a(1)}{a(1)+b(1)},\quad
v=\frac{a(1)b(1)}{(a(1)+b(1))^{2}(a(1)+b(1)+1)}.$

lead to

$\displaystyle a(1)=\frac{(\mu_{p}(1))^{2}(1-\mu_{p}(1))}{v}-\mu_{p}(1),\quad
b(1)=a(1)\frac{1-\mu_{p}(1)}{\mu_{p}(1)}.$

Parameters $a(1)$ and $b(1)$ are calculated prior to the robust estimation
procedure. The sampler and the probability update are shown, respectively, in
Algorithms 2 and 1. Both methods contain only a few calculations and, thus,
are very efficient. This is expected from a sampler in a RANSAC-like robust
estimator where it runs in every iteration, often thousands of times. Note
that we found that the sampler works better if the probabilities are shuffled
by adding a small random number $\epsilon$. Setting $\epsilon$ so it is
uniformly distributed in-between -0.0005 and 0.0005 works well in all our
experiments.

##  5 Experimental Results

This section evaluates the accuracy and speed of Deep MAGSAC++ and the impact
of each individual improvement proposed in this paper, _e.g._ , AR-Sampler and
affine loss. The compared methods are the OpenCV RANSAC [16] and LMEDS [37],
the implementations provided by the authors of GC-RANSAC [7], MAGSAC [10] and
MAGSAC++ [9], NG-RANSAC [13], OANet [52] and the recently published EAS [15],
and CLNet [53] algorithms. We re-trained NG-RANSAC, OANet and CLNet on the
same data as used for Deep MAGSAC++. Also, we will show their results with the
provided models trained on significantly more image pairs than what we use for
training Deep MAGSAC++. All the experiments were conducted on Ubuntu 20.04
with GTX 3090Ti, OpenCV 4.5/3.4, and PyTorch 1.7.1.

#### Technical details.

We use RootSIFT [2] features to improve the estimation accuracy and help the
deep network to learn accurate weights. RootSIFT is a strategy normalizing the
SIFT [25] descriptors, thus, helping the feature matcher to find good
tentative correspondences. When training, we provide the network with the
feature scales and orientations as a learned side-information. Also, we do SNN
ratio [25] filtering on the correspondences as a preliminary step. In the SNN
test, the correspondences are discarded if the distance between the first and
the second nearest neighbors is larger than a manually set threshold, which
works well as we set to $0.8$ in all of our experiments.

###  5.1 Essential Matrix Estimation

In order to test the essential matrix estimation performance of the proposed
algorithm, we downloaded the 13 scenes from the CVPR IMW 2020 PhotoTourism
challenge [42]. These scenes were also used in the recent CVPR tutorial RANSAC
in 2020 [1] to compare robust estimators. The dataset contains tentative
correspondences formed by mutual nearest neighbors matching RootSIFT
descriptors. It also provides SIFT orientations and scales that we can use for
training the proposed method. Besides the image matches, the ground-truth
intrinsic camera parameters and relative poses are also provided. We use scene
St. Peter’s Square, consisting of $4950$ image pairs, for training Deep
MAGSAC++ and retraining NG-RANSAC, CLNet, and OANet for comparison. We use the
provided validation set when training the deep learning-based algorithms. We
tuned the hyper-parameters, _e.g._ inlier-outlier threshold, on the validation
set. For testing, we use $1000$ randomly chosen image pairs from each of the
remaining $12$ scenes. Thus, the methods are tested on a total of $12\,000$
image pairs.

Before applying the main end-to-end training, we initialize our deep model by
minimizing the Kullback–Leibler divergence [49] of the prediction and the
target distribution using a 1000-epoch long initial training process. To our
experiments, this procedure improves the convergence speed of the end-to-end
training. The end-to-end Deep MAGSAC++ framework is trained on the RootSIFT
correspondences of St. Peter’s Square ($4950$ pairs) for 10 epochs, with its
inlier-outlier threshold upper bound set to $0.75$ pixels, Adam optimizer
[24], a batch size of $32$, and $10^{-5}$ learning rate are used.

In each iteration of the training, the pre-filtered correspondences are re-
ordered according to the predicted weights, and MAGSAC++ with AR-Sampler is
applied to estimate the essential matrix. The network can be trained both in a
supervised and self-supervised manner. We report the errors of the model
trained in a supervised way where the loss is a combination of the proposed
affine loss (Section 3.1), and pose error. For calculating the affine loss, we
used the SIFT orientation and scale and the ground truth essential matrix. The
pose error is calculated as the maximum of the rotation
$\epsilon_{\widehat{\textbf{R}}}=(180/\pi)\cos^{-1}((\text{tr}(\widehat{\textbf{R}}\textbf{R}^{\text{T}})-1)/2)$,
and the translation errors
$\epsilon_{\hat{\textbf{t}}}=(180/\pi)\cos^{-1}\frac{\textbf{t}^{\text{T}}\hat{\textbf{t}}}{|\textbf{t}||\hat{\textbf{t}}|}$,
in degrees, where $\widehat{\textbf{R}}\in\text{SO}(3)$ is the 3D rotation
matrix and $\hat{\textbf{t}}\in\mathbb{R}^{3}$ is the translation, both
decomposed from the estimated essential matrix $\widehat{\mathbf{E}}$. Note
that we use the angular translation error since the length of
$\hat{\textbf{t}}$ can not be recovered from two views [20]. Also, note that
the scale and orientations of the features have to be normalized together with
the point correspondences by the intrinsic camera matrices $\textbf{K}_{1}$
and $\textbf{K}_{2}$ as proposed in [6]. While the rotation angle remains
unchanged, the scale is normalized by $f_{2}/f_{1}$, where $f_{i}$ is the
focal length of the $i$th camera, $i\in[1,2]$.

Dataset / Method |  | LMEDS
---
[38]
| RSC
---
[17]
| GC-RSC
---
[7]
| MSC
---
[10]
| MSC++
---
[9]
| EAS
---
[15]
| OANet
---
[52]
| CLNet
---
[53]
| NG-RSC
---
[13]
| Deep
---
MAGSAC++
Avg. time (ms) | 26.7 | $88.1$ | $175.1$ | $239.4$ | $113.4$ | $317.5$ | $163.3$ | $138.9$ | $79.8$ | $33.9$
Buckingham Palace | $0.19$ | $0.20$ | $0.20$ | $0.27$ | $0.26$ | $0.09$ | $0.18$ | $0.25$ | $0.28$ | 0.33
Brandenburg Gate | $0.34$ | $0.42$ | $0.48$ | $0.53$ | $0.54$ | $0.29$ | $0.48$ | $0.54$ | $0.55$ | 0.61
Colosseum Exterior | $0.25$ | $0.25$ | $0.27$ | $0.32$ | $0.31$ | $0.13$ | $0.29$ | $0.32$ | $0.32$ | 0.36
Grand Place Brussels | $0.14$ | $0.14$ | $0.17$ | $0.22$ | $0.21$ | $0.06$ | $0.18$ | $0.22$ | $0.22$ | 0.32
Notre Dame Front Facade | $0.24$ | $0.27$ | $0.38$ | $0.40$ | $0.41$ | $0.13$ | $0.32$ | $0.37$ | $0.34$ | 0.49
Palace of Westminster | $0.19$ | $0.31$ | $0.36$ | $0.37$ | $0.37$ | $0.20$ | $0.21$ | $0.31$ | $0.38$ | 0.43
Pantheon Exterior | $0.49$ | $0.41$ | $0.48$ | $0.62$ | $0.62$ | $0.20$ | $0.48$ | $0.57$ | $0.62$ | 0.72
Prague Old Town Square | $0.10$ | $0.11$ | $0.12$ | $0.16$ | $0.16$ | $0.07$ | $0.09$ | $0.15$ | $0.17$ | 0.20
Sacre Coeur | $0.52$ | $0.64$ | $0.68$ | $0.71$ | $0.71$ | $0.55$ | $0.56$ | $0.64$ | $0.63$ | 0.75
Taj Mahal | $0.36$ | $0.48$ | $0.52$ | $0.52$ | $0.55$ | $0.37$ | $0.48$ | $0.58$ | $0.55$ | 0.67
Trevi Fountain | $0.28$ | $0.29$ | $0.30$ | $0.37$ | $0.35$ | $0.17$ | $0.32$ | $0.42$ | $0.38$ | 0.43
Westminster Abbey | $0.46$ | $0.36$ | $0.49$ | $0.51$ | $0.51$ | $0.20$ | $0.38$ | $0.44$ | $0.49$ | 0.70
Avg. over all scenes | $0.30$ | $0.32$ | $0.37$ | $0.42$ | $0.42$ | $0.21$ | $0.33$ | $0.40$ | $0.41$ | 0.50

Table 1:  Essential matrix estimation on the PhotoTourism dataset [42]. We
report the AUC scores [51] at $10^{\circ}$ (higher is better) calculated from
the pose error, _i.e._ , the max. of the relative rotation and translation
errors in degrees. The first row shows the average run-times (ms). The last
one reports the scores averaged over all scenes. For RANSAC, GC-RANSAC, MAGSAC
and MAGSAC++, we use the threshold tuned in [11]. For EAS, the default
thresholds are used. We trained OANet, CLNet, NG-RANSAC, and Deep MAGSAC++ on
the same datasets. The results with the pre-trained models provided by the
authors are in Table 2.

The network can also be trained in a self-supervised way by using the minus
inlier number as the loss function maximizing the number of inliers. The
proposed affine loss suits this scenario as well. However, the supervised
version leads to higher accuracy in our experiments.

We adopted the neural network from [13] and [51], a typical and commonly used
neural network for geometry data, which comprises 12 residual blocks that
connects information from different layers and several multi-layer perceptions
(MLPs). Each block is constructed by two linear layers, a batch normalization
layer, and a ReLU activation function [21]. Besides, the global context is
included by adding the instance normalization [48] layer into each block. The
inlier probabilities of the matches are mapped by a sigmoid function. Finally,
MAGSAC++ with the proposed AR-Sampler estimates the essential matrix with its
iteration number fixed to $1000$.

The training objective is defined as the minimization of the expected task
loss, shown in [13]. We approximate the gradients for the categorical
distribution over the discrete set of observations. The number of times each
correspondence was selected in a minimal sample is back-propagated and used to
update the weights and contribute to distribution learning for the next
iteration.

Figure 3:  The cumulative distribution functions (CDF) of the angular errors
(left) for $\mathbf{E}$ estimation; epipolar errors (middle; in pixels) and F1
score (right; in percentages) for $\mathbf{F}$ estimation. Essential matrix
estimation is tested on $12\,000$ image pairs from the PhotoTourism [42]
dataset. Fundamental matrix estimation is tested on $9690$ pairs from the
KITTI [18] dataset. We use the thresholds tuned in [11] for the traditional
algorithms. We trained OANet, CLNet, NG-RANSAC, and Deep MAGSAC++ on the same
datasets. In the left two plots, being close to the top-left corner indicates
accurate results. In the right one (F1 score), the bottom-right corner is
preferable.

To measure the accuracy of the estimated essential matrices, we decompose them
to rotation and translation and calculate the pose error. Finally, we
calculate the AUC scores at $5^{\circ}$, $10^{\circ}$ and $20^{\circ}$ from
the pose errors as the area under the recall curves [13]. The AUC@$10^{\circ}$
scores on each scene from the PhotoTourism dataset [42] are reported in Table
1. Also, we show the run-time (in milliseconds) and the AUC scores averaged
over all scenes. The proposed Deep MAGSAC++ is superior to the state-of-the-
art, _i.e._ EAS, MAGSAC++, CLNet and NG-RANSAC, by a large margin both in
terms of run-time and accuracy. It is the most accurate on all scenes. Its
average score is higher by $8$ AUC points than that of the second most
accurate method (_i.e._ , MAGSAC++). The only method faster is LMEDS that has
the second lowest accuracy.

The left plot of Fig. 3 shows the cumulative distribution functions (CDF) of
the angular pose errors of the estimated essential matrices on all tested
scenes. Being accurate is indicated by a curve close to the top-left corner.
Deep MAGSAC++ is significantly more accurate than the other compared methods.

Furthermore, Table 2 shows the performance comparison of Deep MAGSAC++ with
NG-RANSAC, CLNet and OANet when using the pre-trained models that their
authors provide. CLNet and OANet was trained on $541\,184$ image pairs from
the YFCC [44] dataset. NG-RANSAC was trained on a total of $10\,000$ pairs
from the same scene as what we use for Deep MAGSAC++. As a reminder, Deep
MAGSAC++ was trained on $4950$ image pairs in total. Even in this unfair
comparison, the proposed method leads to the most accurate results in the
AUC@$5^{\circ}$ and AUC@$10^{\circ}$ cases by a large margin – in the
AUC@$5^{\circ}$ case, it is better than CLNet (_i.e._ , the second best) by
$6$ AUC points. This clearly shows that the Deep MAGSAC++ generalizes better
than the state-of-the-art learning-based approaches and is able to learn the
underlying scene geometry better thanks to the number of proposed
improvements.

In the left plot of Fig. 4, we show the accuracy gained from each component of
the algorithm. We show the AUC scores and their standard deviations at
$5^{\circ}$, $10^{\circ}$ and $20^{\circ}$ averaged over 12 scenes. The
proposed affine loss plays an important role in improved accuracy. Also, it
confirms that the widely used techniques, _e.g._ , SNN filtering, RootSIFT,
initial training, are important steps to achieve state-of-the-art results.

In the right plot of Fig. 4, we show the results of different samplers used
within Deep MAGSAC++. The compared samplers are the uniform one from [16], the
NG-RANSAC sampler [13], PROSAC [14], and the proposed AR-Sampler. It can be
seen that the proposed AR-Sampler leads to the best accuracy. Interestingly,
PROSAC significantly outperforms the recently proposed sampler of NG-RANSAC,
which is just marginally more accurate than the uniform sampler when used
inside Deep MAGSAC++.

###  5.2 Fundamental Matrix Estimation

Figure 4: The AUC scores (and their std.) at 5∘, 10∘ and 20∘ of $\mathbf{E}$
estimation on the PhotoTourism dataset [42]. Left: the impact of each
component of Deep MAGSAC++. Right: results using the Uniform [16], NG-RANSAC
sampler [13], PROSAC [14] and the proposed AR-Sampler.

Threshold | OANet [52] | CLNet [53] | NG-RANSAC [13] | Deep MAGSAC++
---|---|---|---|---
@$5^{\circ}$ | $0.38$ | $0.41$ | $0.38$ | 0.47
@$10^{\circ}$ | $0.44$ | $0.48$ | $0.43$ | 0.50
@$20^{\circ}$ | $0.51$ | 0.56 | $0.49$ | $0.54$

Table 2: AUC scores [51] of essential matrix estimation using the pre-trained
models provided by the authors of NG-RANSAC, OANet and CLNet. CLNet and OANet
was trained on $541\,184$ image pairs from the YFCC [44] dataset. NG-RANSAC
was trained on $10\,000$ pairs from scene St. Peter’s Square of PhotoTourism
dataset [42]. Deep MAGSAC++ was trained on $4950$ pairs.

We evaluate Deep MAGSAC++ for fundamental matrix estimation on the KITTI
benchmark [18]. As in [51, 13], Sequences ’00-05’ and ’06-10’ are regarded as
the training and testing sets, respectively. The KITTI dataset consists of
consecutive frames of high-resolution cameras rigidly mounted to a moving
vehicle in a mid-size city, rural areas and highways [18]. The images are of
resolution $1226\times 370$. Image correspondences are detected between
subsequent images by RootSIFT. In total, we use $14\,130$ image pairs from
KITTI for training, and another $9060$ for testing.

Fundamental matrix estimation runs on the same architecture as what we
described in Section 5.1. In this case, neither the point coordinates, nor the
orientation and scale are normalized. In contrast to essential matrix
estimation, we do apply initial training as it does not improve the accuracy
when estimating fundamental matrices.

Method |  | LMEDS
---
[38]
| RSC
---
[17]
| GC-RSC
---
[7]
| MSC
---
[10]
| MSC++
---
[9]
| EAS
---
[15]
| OANet
---
[52]
| CLNet
---
[53]
| NG-RSC
---
[13]
| Deep
---
MAGSAC++
F1 Score (%) | $38.55$ | $56.83$ | $66.90$ | $57.80$ | $60.65$ | $55.16$ | $64.10$ | $64.47$ | $69.50$ | 69.93
AUC |  1$0.45$ |  1$0.78$ |  1$0.91$ |  1$0.76$ |  1$0.83$ |  1$0.83$ |  1$0.94$ |  1$0.95$ |  1$0.92$ |  10.97
Median epipolar error (px) |  1$3.15$ |  1$0.98$ |  1$0.42$ |  1$0.84$ |  1$0.75$ |  1$0.88$ |  1$0.57$ |  1$0.54$ |  1$0.41$ |  10.29
Time (ms) |  1$20$ |  1$32$ |  1$56$ |  1$233$ |  1$413$ |  1$310$ |  1$17$ |  1$13$ |  1$18$ |  112

Table 3: The F1 score, AUC score at $10^{\circ}$, and median symmetric
epipolar error (in pixels) of fundamental matrix estimation on $9690$ images
pairs from the KITTI benchmark [18].

Table 3 reports the run-time, the median symmetric epipolar error in pixels,
the AUC and F1 scores of the estimated fundamental matrices compared to the
ground truth ones. Deep MAGSAC++ leads to the highest accuracy in all metrics.
Interestingly, while F1 score is only marginally higher than that of NG-
RANSAC, while the AUC score is better by $5\%$. This implies that the F1 score
is not in perfect agreement with the actual camera pose error captured in the
AUC score. The run-time of Deep MAGSAC++ is the lowest, being $33\%$ faster
than NG-RANSAC. These timings exclude the prediction time which is at most
$1-2$ milliseconds. Fig. 3 shows the CDFs of the epipolar errors (middle) and
the F1 scores (right) on the $9060$ image pairs. Deep MAGSAC++ leads to the
lowest errors and highest F1 scores.

###  5.3 Sampler Comparison

We test the proposed sampler on the $4950$ image pairs from scene Sacre Coeur
when using the standard second nearest neighbor (SNN) ratio to order the
points according to the inlier probabilities. To our experiments, considering
the SNN ratio directly as prior inlier probability does not lead to an
improvement compared to PROSAC. However, exploiting the point ranks implied by
the SNN ratio works well. Assume that we are given $n$ points
$\textbf{p}_{i_{1}},\dots,\textbf{p}_{i_{n}}$ ordered by their SNN ratios
$s_{i_{1}},\dots,s_{i_{n}}$. Thus, $s_{i_{1}}\leq s_{i_{2}}\leq\dots\leq
s_{i_{n}}$. We calculate the prior probability of the $i_{j}$th point as
$\mu_{i_{j}}=1-(j-1)/(n-1)$, $j\in[1,n]$. Consequently, the first point, when
ordered by the SNN ratio, has $1$ as prior probability. Conversely, the last
one is assigned to zero.

The inlier numbers and run-times of the original MAGSAC++ when used together
with the uniform [16], PROSAC [14], NG-RANSAC samplers [13], and the proposed
one are shown in Fig. 5. The horizontal axis is the maximum iteration number
which is a strict upper bound on the iteration number that is controlled by
the RANSAC confidence parameter. The curve of the proposed sampler starts from
a higher inlier number, both for essential and fundamental estimation, than
that of the others, _i.e._ , it leads to finding good samples earlier than the
other methods. As expected, after many iterations, all methods converge to the
similar results. Due to being extremely efficient, AR-Sampler leads to the
fastest robust estimation, as shown in the right plot of Fig. 5.

Figure 5:  Left, middle: the inlier numbers (vertical axis) plotted as a
function of the maximum iteration number (horizontal) used in the original
MAGSAC++ algorithm [9] when combined with Uniform [16], NG-RANSAC [13], PROSAC
[14] and the proposed AR-Sampler. Right: the robust estimation time, in
seconds, versus the maximum iteration number. The SNN ratio [25] provides the
inlier probabilities here, without using any learning algorithms.

##  6 Conclusion

In this paper, we propose the Deep MAGSAC++ algorithm that achieves state-of-
the-art accuracy while having comparable or better processing time to its less
accurate alternatives. It runs in real-time on most of the tested problems.
Moreover, we show that exploiting additional geometric information (_e.g._ ,
SIFT orientations and scales) in the loss function helps in capturing the
underlying scene geometry. This extra information is available for free when
using partially affine covariant feature detectors, _e.g._ , SIFT. The
proposed AR-Sampler is superior to the traditional ones both when using
predicted weights or SNN ratios as inlier probabilities. It is also
demonstrated that the proposed Deep MAGSAC++ generalizes better than the
state-of-the-art learning-based approaches and is able to learn the underlying
scene geometry better thanks to the number of proposed improvements. We will
make the source code and the models public.

## References

  * [1] Ransac tutorial 2020- data. https://github.com/ducha-aiki/ransac-tutorial-2020-data
  * [2] Arandjelović, R., Zisserman, A.: Three things everyone should know to improve object retrieval. In: 2012 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). pp. 2911–2918. IEEE (2012)
  * [3] Barath, D., Chin, T.J., Chum, O., Mishkin, D., Ranftl, R., Matas, J.: RANSAC in 2020 tutorial. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR) (2020), http://cmp.felk.cvut.cz/cvpr2020-ransac-tutorial/
  * [4] Barath, D.: Five-point fundamental matrix estimation for uncalibrated cameras. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR). pp. 235–243 (2018)
  * [5] Barath, D., Hajder, L.: Efficient recovery of essential matrix from two affine correspondences. IEEE Transactions on Image Processing 27(11), 5328–5337 (2018)
  * [6] Barath, D., Kukelova, Z.: Homography from two orientation-and scale-covariant features. In: The IEEE International Conference on Computer Vision (ICCV). pp. 1091–1099 (2019)
  * [7] Barath, D., Matas, J.: Graph-cut RANSAC. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR). pp. 6733–6741 (2018)
  * [8] Barath, D., Matas, J.: Progressive-X: Efficient, anytime, multi-model fitting algorithm. In: The IEEE International Conference on Computer Vision (ICCV). pp. 3780–3788 (2019)
  * [9] Barath, D., Noskova, J., Ivashechkin, M., Matas, J.: Magsac++, a fast, reliable and accurate robust estimator. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR). pp. 1304–1312 (2020)
  * [10] Barath, D., Noskova, J., Matas, J.: MAGSAC: marginalizing sample consensus. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR) (2019), https://github.com/danini/magsac
  * [11] Barath, D., Noskova, J., Matas, J.: Marginalizing sample consensus. IEEE Transactions on Pattern Analysis and Machine Intelligence (2021)
  * [12] Bay, H., Tuytelaars, T., Van Gool, L.: SURF: Speeded up robust features. In: The European Conference on Computer Vision (ECCV). pp. 404–417. Springer (2006)
  * [13] Brachmann, E., Rother, C.: Neural-guided ransac: Learning where to sample model hypotheses. In: The IEEE International Conference on Computer Vision (ICCV). pp. 4322–4331 (2019)
  * [14] Chum, O., Matas, J.: Matching with PROSAC-progressive sample consensus. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR). IEEE (2005)
  * [15] Fan, A., Ma, J., Jiang, X., Ling, H.: Efficient deterministic search with robust loss functions for geometric model fitting. IEEE Transactions on Pattern Analysis and Machine Intelligence (2021)
  * [16] Fischler, M.A., Bolles, R.C.: Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography. Communications of the ACM (1981)
  * [17] Fischler, M.A., Bolles, R.C.: Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography. Commun. ACM 24(6), 381–395 (Jun 1981). https://doi.org/10.1145/358669.358692, https://doi.org/10.1145/358669.358692
  * [18] Geiger, A., Lenz, P., Urtasun, R.: Are we ready for autonomous driving? the KITTI vision benchmark suite. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR). IEEE (2012)
  * [19] Ghosh, D., Kaabouch, N.: A survey on image mosaicking techniques. Journal of Visual Communication and Image Representation (2016)
  * [20] Hartley, R., Zisserman, A.: Multiple view geometry in computer vision. Cambridge university press (2003)
  * [21] He, K., Zhang, X., Ren, S., Sun, J.: Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. In: The IEEE International Conference on Computer Vision (ICCV). pp. 1026–1034 (2015)
  * [22] Ioffe, S., Szegedy, C.: Batch normalization: Accelerating deep network training by reducing internal covariate shift. In: Proceedings of the 32nd International Conference on Machine Learning. Proceedings of Machine Learning Research, vol. 37, pp. 448–456. PMLR, Lille, France (07–09 Jul 2015), https://proceedings.mlr.press/v37/ioffe15.html
  * [23] Isack, H., Boykov, Y.: Energy-based geometric multi-model fitting. International Journal of Computer Vision (IJCV) (2012)
  * [24] Kingma, D.P., Ba, J.: Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980 (2014)
  * [25] Lowe, D.G.: Object recognition from local scale-invariant features. In: The IEEE International Conference on Computer Vision (ICCV). IEEE (1999)
  * [26] Ma, J., Jiang, X., Fan, A., Jiang, J., Yan, J.: Image matching from handcrafted to deep features: A survey. International Journal of Computer Vision (IJCV) 129(1), 23–79 (2021)
  * [27] Maronna, R.A., Martin, R.D., Yohai, V.J., Salibián-Barrera, M.: Robust statistics: theory and methods (with R). John Wiley & Sons (2019)
  * [28] Matas, J., Chum, O., Urban, M., Pajdla, T.: Robust wide-baseline stereo from maximally stable extremal regions. IVC (2004)
  * [29] Mikolajczyk, K., Tuytelaars, T., Schmid, C., Zisserman, A., Matas, J., Schaffalitzky, F., Kadir, T., Van Gool, L.: A comparison of affine region detectors. International journal of computer vision 65(1), 43–72 (2005)
  * [30] Mishkin, D., Matas, J., Perdoch, M.: MODS: Fast and robust method for two-view matching. Computer Vision and Image Understanding 141, 81–93 (2015)
  * [31] Myatt, D., Torr, P., Nasuto, S., Bishop, J., Craddock, R.: NAPSAC: High noise, high dimensional robust estimation-it’s in the bag. In: Proceedings of the British Machine Vision Conference. pp. 44.1–44.10. BMVA Press (2002)
  * [32] Ni, K., Jin, H., Dellaert, F.: GroupSAC: Efficient consensus in the presence of groupings. In: The IEEE International Conference on Computer Vision (ICCV). pp. 2193–2200. IEEE (2009)
  * [33] Pham, T.T., Chin, T.J., Schindler, K., Suter, D.: Interacting geometric priors for robust multimodel fitting. IEEE Transactions on Image Processing 23(10), 4601–4610 (2014)
  * [34] Pritchett, P., Zisserman, A.: Wide baseline stereo matching. In: The IEEE International Conference on Computer Vision (ICCV). IEEE (1998)
  * [35] Ranftl, R., Koltun, V.: Deep fundamental matrix estimation. In: The European Conference on Computer Vision (ECCV) (2018)
  * [36] Raposo, C., Barreto, J.P.: Theory and practice of structure-from-motion using affine correspondences. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR). pp. 5470–5478 (2016)
  * [37] Rousseeuw, P.J.: Least median of squares regression. Journal of the American statistical association 79(388), 871–880 (1984)
  * [38] Rousseeuw, P.J., Leroy, A.M.: Robust regression and outlier detection, vol. 589. John wiley & sons (2005)
  * [39] Rublee, E., Rabaud, V., Konolige, K., Bradski, G.: ORB: An efficient alternative to SIFT or SURF. In: 2011 International Conference on Computer Vision (ICCV). pp. 2564–2571. Ieee (2011)
  * [40] Schönberger, J.L., Frahm, J.M.: Structure-from-motion revisited. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR) (2016)
  * [41] Schönberger, J.L., Zheng, E., Pollefeys, M., Frahm, J.M.: Pixelwise view selection for unstructured multi-view stereo. In: The European Conference on Computer Vision (ECCV) (2016)
  * [42] Snavely, N., Seitz, S.M., Szeliski, R.: Photo tourism: exploring photo collections in 3d. In: ACM siggraph 2006 papers, pp. 835–846. Association for Computing Machinery, New York, NY, United States (2006)
  * [43] Sun, W., Jiang, W., Tagliasacchi, A., Trulls, E., Yi, K.M.: Attentive context normalization for robust permutation-equivariant learning. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR) (2020)
  * [44] Thomee, B., Shamma, D.A., Friedland, G., Elizalde, B., Ni, K., Poland, D., Borth, D., Li, L.J.: Yfcc100m: The new data in multimedia research. Communications of the ACM 59(2), 64–73 (2016)
  * [45] Torr, P.H.S., Murray, D.W.: Outlier detection and motion segmentation. In: Optical Tools for Manufacturing and Advanced Automation. International Society for Optics and Photonics (1993)
  * [46] Torr, P.H.S., Zisserman, A.: MLESAC: A new robust estimator with application to estimating image geometry. Computer Vision and Image Understanding (CVIU) (2000)
  * [47] Torr, P.H.S., Zisserman, A., Maybank, S.J.: Robust detection of degenerate configurations while estimating the fundamental matrix. Computer Vision and Image Understanding (CVIU) (1998)
  * [48] Ulyanov, D., Vedaldi, A., Lempitsky, V.: Instance normalization: The missing ingredient for fast stylization. arXiv preprint arXiv:1607.08022 (2016)
  * [49] Van Erven, T., Harremos, P.: Rényi divergence and kullback-leibler divergence. IEEE Transactions on Information Theory 60(7), 3797–3820 (2014)
  * [50] Yi*, K.M., Trulls*, E., Ono, Y., Lepetit, V., Salzmann, M., Fua, P.: Learning to find good correspondences. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR) (2018)
  * [51] Yi, K.M., Trulls, E., Ono, Y., Lepetit, V., Salzmann, M., Fua, P.: Learning to find good correspondences. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR). pp. 2666–2674 (2018)
  * [52] Zhang, J., Sun, D., Luo, Z., Yao, A., Zhou, L., Shen, T., Chen, Y., Quan, L., Liao, H.: Learning two-view correspondences and geometry using order-aware network. The IEEE International Conference on Computer Vision (ICCV) (2019)
  * [53] Zhao, C., Ge, Y., Zhu, F., Zhao, R., Li, H., Salzmann, M.: Progressive correspondence pruning by consensus learning. In: The IEEE International Conference on Computer Vision (ICCV) (2021)
  * [54] Zuliani, M., Kenney, C.S., Manjunath, B.S.: The multiRANSAC algorithm and its application to detect planar homographies. In: IEEE International Conference in Image Processing (ICIP). IEEE (2005)


# A Generative Adversarial Model for Right Ventricle Segmentation

Nicoló Savioli 1 Miguel Silva Vieira1, Pablo Lamata1, Giovanni Montana1 2
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>1King’s College London, Division of Imaging Sciences
and Biomedical Engineering, UK  2 WMG, University of Warwick, UK

###### Abstract

###### Abstract

The clinical management of several cardiovascular conditions, such as
pulmonary hypertension, require the assessment of the right ventricular (RV)
function. This work addresses the fully automatic and robust access to one of
the key RV biomarkers, its ejection fraction, from the gold standard imaging
modality, MRI. The problem becomes the accurate segmentation of the RV blood
pool from cine MRI sequences. This work proposes a solution based on Fully
Convolutional Neural Networks (FCNN), where our first contribution is the
optimal combination of three concepts (the convolution Gated Recurrent Units
(GRU), the Generative Adversarial Networks (GAN), and the L1 loss function)
that achieves an improvement of 0.05 and 3.49 mm in Dice Index and Hausdorff
Distance respectively with respect to the baseline FCNN. This improvement is
then doubled by our second contribution, the ROI-GAN, that sets two GANs to
cooperate working at two fields of view of the image, its full resolution and
the region of interest (ROI). Our rationale here is to better guide the FCNN
learning by combining global (full resolution) and local Region Of Interest
(ROI) features. The study is conducted in a large in-house dataset of $\sim$
23.000 segmented MRI slices, and its generality is verified in a publicly
available dataset.

##  I Introduction

Cardiovascular diseases (CV) remain the leading cause of death worldwide [1],
accounting for 17.3 million total deaths worldwide. In the management of these
conditions, cardiac magnetic resonance (CMR) is considered the gold standard
for the assessment of key biomarkers such as the volume or ejection fraction
(EF) of the ventricular chambers of the heart [2]. The fully automatic and
robust access to this important diagnostic and prognostic information is
nevertheless missing in the clinical armamentarium.

The Left Ventricle (LV) has traditionally focused the clinical interest for
the characterization of the disease progression, but in recent years a strong
shift of attention to the Right Ventricle (RV) has led to important findings
for the management of conditions such as pulmonary hypertension, coronary
heart disease, dysplasia and cardiomyopathies [3, 4].

Compared to the LV, the RV is a much more challenging anatomical structure to
be characterized, mainly because of a much larger morphological variability
and the much thinner myocardial walls [5]. The RV biomarker of volume, EF or
cardiac output is conventionally accessed through the acquisition of a stack
of short-axis (SA) slices of the heart. The problem of interest then becomes
the automatic RV segmentation in CMR SA slices, where the goals are the
removal of the (intro- and inter-) observer variability and the immediate
access to this information right after acquisition.

The attention on RV segmentation was initiated with a-priori probabilistic
atlases [6, 7], using both shape and appearance information. The strength and
weakness of this approach lay on the suitability of the cohort used to build
the atlas: this solution will render a low performance in new anatomical
configurations not accounted in the training dataset. In an attempt to
alleviate this limitation, manifold learning techniques have been applied to
better capture the variability of shape models, for example using Markov
Random Field (MRF)[8]. Image gradient algorithms[9], region-merging[10] and
graph-cut[11] based methods have been shown to be more compelling. The
implementation of these ideas led to popular concepts such as active contours
able to reach reasonable performance, but with a dependence on the actual
choice of weighting factors and the optimal initialization point.

In the last few years, deep-learning (DL) methods are being developed for
extracting automatic spatial features. Particularly, Fully Convolution Neural
Networks (FCNN) can be considered the state of the art or the automatic
segmentation of the RV [12, 13, 14].

In this work we want to further extend the capability of FCNNs, exploring two
main ideas: first, modeling and exploiting the spatial redundancy between
adjacent SA slices; and second, guiding the FCNN to the useful RV features
without the need of an automatically pre-localisation of the RV region of
interest (ROI). The approach to exploit spatial redundancy is the
incorporation of a recurrent unit in the middle of up-sampling and down-
sampling path of the FCNN, an R-FCNN, a strategy that has been shown to
improve the LV segmentation, especially at the apex [15].

Guiding an FCNN to the correct image features is a much more complex goal. The
explicit ROI extraction is an approach followed by RV segmentation [16] and
many medical applications [17, 18, 19] to facilitate the segmentation task.
Mask-RCNN [20] is an example where the segmentation obtained from an FCNN is
in close combination with an ROI-pooling mechanism able to locally identify
the bounding box of each object. Our rationale is that there are still useful
image features outside the ROI that can guide the FCNN, and that approaches
that jointly learn detection and segmentation are desirable, avoiding the only
focus on the ROI features. Some works explore this idea, where ROI pre-
localisation becomes an additional sequential task in an end-to-end training
chain [21, 22], but without an explicit use for guiding the segmentation.
While a dual FCNN within local and global downsampling pathways at two
different MRI resolution was used for atrial segmentation problem [23].
However, in this work, the local path only helps to scan every single patch of
the image in order to classify it as negative or positive. In truth, this
method differs from the principle of FCNN (i.e uses downsampling filters to
scan the whole pixel image) and approaches more to prior old segmentation
techniques, where the adding the global path works as a multiscale integration
of global contexts.

The strategy to guide the FCNN to features within the ROI, without losing the
features outside it, is inspired in the concept of the Coupled Generative
Adversarial Networks (CoGAN) [24, 25], where a pair of corresponding images in
different domains can be mapped in the same representation within a shared
parameters strategy between two Generative Adversarial Networks (GAN). We
adopt this concept by taking two versions of the same image, one at full
resolution and another at the exact ROI around the segmentation mask, and we
call it the ROI-GAN. Note that the second image will only be needed at the
training stage.

In this work, we thus explore the use of three existing concepts, a recurrent
unit (R-FCNN) to exploit the spatial redundancy of a stack of SA slices, the
concept of adversarial training (FCNN-GAN) to better guide the selection of
features, and the use of the L1 loss [26, 27]. And we propose the ROI-GAN as a
solution to maximize the performance of FCNNs for the task of RV segmentation.

##  II Material and methods

In this section, we present the datasets used in this work, and we review the
concepts of the FCNN, the R-FCNN, the L1 loss, and the GAN training strategy
using either FCNN or an R-FCNN. Finally, our ROI-GAN architecture is
explained, with 3 possible variants that will be analyzed.

###  II-A Datasets

Two datasets are used, a large in-house Twins-UK dataset to exhaustively
develop and test the DL solution, and a small public RV MICCAI dataset [5] to
test the generality of findings.

Twins-UK is a nation-wide voluntary registry that includes >12,000 twins [28].
The study was approved by the local institutional research ethics committee
(South East London Research Ethics Committee, EC04/015), and informed consent
was obtained from all participants prior to scanning. In particular, 68
consecutive female patients (mean age $62\pm 9$ years) were recruited from the
Twins-UK cohort.

All scans were performed on a 1.5-T clinical scanner (Achieva, Philips
Healthcare, Best, The Netherlands). All measurements were performed in the
supine position using a 5-channel cardiac surface coil. ECG-gated steady-state
free-precession (SSFP) end-expiratory breath-hold 2D CINE were acquired. 12 to
14 equidistant and contiguous slices from the atrioventricular (AV) ring to
the apex, completely covering both ventricles (slice thickness 8 mm; no gap
mm; field of view was $360\times 480$ mm and matrix size $156\times 144$),
were acquired. The imaging was performed a temporal resolution of 25-35
milliseconds at a heart rate of 60-80 beats per minute.

The RV endocardial borders were delineated in all planes and in all cardiac
phases by Dr. Miguel Silva Vieira (6 years of CMR experience, SCMR and Euro
CMR level 3 certification). In detail, the ventricular blood pool was
segmented using a semi-automated threshold-based contouring technique, which
enables to capture details of the endocardial configuration (e.g
trabeculations). Of note, papillary muscles were excluded from the volumetric
analysis (equivalent to blood pool techniques).

The Twins-UK dataset of 23.000 slices with segmentation ground truth was
randomly divided into training, validation and testing sets of sizes $70\%$,
$15\%$ and $15\%$, respectively.

On the other hand, the public RV MICCAI dataset was used to refine weights (16
subjects with two-time points segmented, 250 slices) and to evaluate
performance on the Test2Set blind cohort used for benchmarking (another set of
16 subjects, a similar number of slices). This public dataset is composed of
subjects with a variety of disease conditions, with an average age of $55.5\pm
17.5$ and where $70\%$ of them were male.

###  II-B The FCNN/R-FCNN

An FCNN is the core of the DL solution, taking a stack of SA slices as input
and returning the segmentation mask. An FCNN extract features from the image
in a first decoding path, and these are gradually restored to the original
image size, through a decoding block used to infer the final binary mask. One
of the key features of an FCNN are the skip paths connections between
convolution and deconvolution layers for fusing mid-height level features
together. Each connection concatenates feature maps from the encoding to the
decoding blocks.

The FCNN (Fig. 1 panel (a)) considers each slice of the SA input
independently. The extension in an R-FCNN (Fig. 1 panel (b)) is to take the
full SA stack as an input, as a sequence of slices from base to apex where the
current slice depends on the previous observed ones [15].

The R-FCNN has the same encoding and decoding structure of an FCNN (i.e six
encoding and decoding blocks followed by ReLU and Batch Normalization (BN)
operators) but, in the middle of both, a Convolution Gated Recurrent Unit
(C-GRU) [29, 30] is used. The C-GRU unit presents two specific gates designed
to control the information inside: a rest gate $r_{s}$ and an update gate
$z_{s}$ defined as follow:

$\displaystyle r_{s}$
$\displaystyle=\sigma(W_{hr}*h_{s-1}+W_{xr}*x_{s}+b_{r})$ $\displaystyle
z_{s}$ $\displaystyle=\sigma(W_{hz}*h_{s-1}+W_{xz}*x_{s}+b_{z})$

Here, $\sigma(\cdot)$ is the sigmoid function and the $h_{s-1}$ represents the
hidden activation learned at the previous SA slice $s-1$. The $W_{hr}$ and
$W_{hz}$ are the weight matrices of dimension $D\times 8\times 8$, with D
numbers of features maps in the down-sample layer, and $b$ a bias vector.

In this notation, $*$ defines the convolution operation. The reset gate switch
(on or off) the signal coming in input to $\hat{h_{s}}$; where $\hat{h_{s}}$
is called the candidate activation, defined as:

$\hat{h}_{t}=\tanh(W_{h}*(r_{s}\odot h_{s-1})+W_{x}*x_{s}+b)$

The $\odot$ denotes the dot product and $W_{x}$. Then the final activation is:

$h_{s}=(1-z_{s})\odot h_{s-1}+z_{s}\odot\hat{h_{s}}.$

Figure 1: FCNN and RFCNN architectures. The FCNN (panel a) is a combination of
a decoder and encoder paths. The decoder path (blue trapezoid) consists of six
convolution layers (stride of 2) following by ReLU and Batch Normalization
(BN). The up-convolution path (green trapezoid) consists of deconvolution
layers in combination with LeakyReLU (set to $0.2$) and Batch Normalization.
The R-FCNN (panel b) is similar to FCNN but a convolution-GRU (yellow
rectangle) is used in between the decoder and encoder in order to model and
exploit the spatial MRI redundancy.

###  II-C The L1 loss

The training of a network is guided by the metric used to define the error,
and the L1 loss [26, 27] has shown to be a good addition to the total loss.
The L1 distance used is given as:

$L_{L1}=\frac{\beta}{n}\mid x_{i}-y_{i}\mid$ (1)

This metric measures the mean absolute value of element-wise difference among
the network output $x^{i}$ and ground truth $y^{i}$, where, $\beta$ is a
regularization constant parameter (set to $5e^{-6}$) for controlling the
quantity of L1 loss used.

###  II-D The GAN

Two neural net architectures, the generative and the discriminative, compete
in a GAN to perform a task. We adopt this concept to our problem so that the
FCNN or R-FCNN become generators of binary masks (note that their input here
is not a distribution of random numbers, but the distribution of MRI images),
and we add a new CNN to act as discriminator that will try to identify if the
binary mask is “fake” (i.e. output of the generator) or “real” (i.e. the
ground truth mask). See the top of Fig. 2 for an illustration of a GAN
architecture.

The discriminator CNN network is thus trained to distinguish how much the
ground truth deviates from that produced by the FCNN generator. This
information generated by the discriminator is back-propagated towards the
generator, which then uses this knowledge for producing indistinguishably
masks from the corresponding ground truth. Besides, in order to avoid
deterministic generators, Gaussian Noise (GN) is added by dropping the first
three up-sampling layers of the generator.

The adversarial process is summarized by the maximization of the following
loss:

$\displaystyle min_{G}\thinspace\thinspace max_{D}L_{GAN}(D,G)=$ (2)
$\displaystyle=E_{x\sim{MRI_{real}(x)}}[log(D(x))]+$
$\displaystyle+E_{x\sim{MRI_{fake}}(x)}[log(1-D(G(x)))]$

where $D$ represent the discriminator, $G$ the discriminator and $x$ is the
set of binary masks sampling form $MRI_{real}(x_{k})$ and $MRI_{fake}(x)$.

This adversarial loss is also combined within the minimum squared error $MSE$
loss function between the generator output and the ground truth:

$L_{MSE}(G)=\frac{1}{n}\sum_{i=1}^{n}(x_{i}-y_{i})^{2}$ (3)

where $n$ is the set of training spatial sequences cases (i.e. slices), $x$ is
the generated binary mask and $y$ is the ground truth segmentation. The two
loss functions are combined through a $\lambda$ regularization parameter (set
to $5e^{-3}$) able to control the amount of GAN loss taken into account:

$\displaystyle L_{TOTAL}(G,D)=(L_{MSE}(G)+\lambda L_{GAN}(D,G))$ (4)

Figure 2: The three ROI-GAN architectures studied in this work. TOP: basic GAN
architecture. BOTTOM LEFT: the ROI-GAN-A, where masks at two different sizes
are feeding the same discriminator CNN. BOTTOM RIGHT: the ROI-GAN-B/C
architectures, where two different CNN are used as discriminators, one for
each image size, either in coordination (i.e. sharing parameters) in B
configuration, or independently in C configuration.

###  II-E The ROI-GAN

The ROI-GAN model (Fig. 2), takes inspiration from the concept of CoGAN [24,
25], which is adapted to working with the same image but at two different
fields of view: one a the global level (i.e. original full resolution MRI
image), and another at the region of interest (ROI) local level. We will thus
refer to the global (working with the full resolution) or local (working with
the cropped image) generators and discriminators in each of the two
collaborative GANs.

Note that the cropped images needed for the second set of images, the ROIs,
are simply the bounding boxes containing the ground truth segmentation, and
are only needed for the training phase of the architecture.

The idea is that the local GAN will inform and better guide the global GAN.
And this is articulated through a mechanism of parameter sharing between the
generators and discriminators of the two GANs in an attempt to intensify the
attention on the correct subset of mid-level features.

The training process is sequential: first, the cropped MRI images are
segmented (i.e forward pass on the local generator) with a corresponding
backward propagation of the loss by comparison to the segmentation ground
truth. Second, the updated parameters of the local generator are passed to the
global generator by using the weights-sharing connections that are enabled on
the first three up-sampling layers. Then, the global generator repeats the
forward and backward process. The third step is the training of the
discriminator and the backpropagation of the total network gradient from the
discriminator to both generators.

Three different strategies (identified by the surname A, B or C) for the
discriminator third step are designed and compared in this work. ROI-GAN-A
(Fig. 2 bottom left) uses one single discriminator fed by the images at both
fields of view (full and ROI), motivated by the idea of maximizing the
interplay between the two generators by sharing the same discriminator. The
alternative is to use two discriminators (Fig. 2 right), one per generator, in
the ROI-GAN-B. The third option is an intermediate solution, where the two
discriminators are allowed to share weights between them, as set in the ROI-
GAN-C.

##  III Results

The baseline for this study is the performance of the FCNN to fully
automatically segment the RV. This section presents the gradual improvement
from this baseline by applying the concepts of recurrence, L1 loss, GAN and
finally the proposed ROI-GAN. Results will show how these concepts do not
always complement each other. Illustrative examples of the segmentation
performance are provided in Fig. 3 and Fig. 4.

Figure 3: Illustrative segmentation results on our in-house Twins-UK dataset,
comparing neural networks predictions (green line) to the ground truth (red
line). The ROI-GAN-A (last column) shows a good match both in an easy case
(first row, a slice from the top of the RV) and in a difficult case (third row
from the apical low region or the RV). Figure 4: Examples of the reconstructed
3D anatomies of the RV, where the model prediction (green surface) is compared
to the ground truth contours (red points).

###  III-A Metrics

Segmentation performance is evaluated for endocardial contours with two
different metrics: Dice Index (DI) and Hausdorff Distance (HD). The DI is
defined as twice intersection over the sum of cardinalities (i.e. a number of
elements) of two binary masks $A$ and $B$,

$DI=\frac{2|A\cdot B|}{|A|+|B|}.$

The HD is the greatest of all the distances from a point in one set to the
closest point in the other set. It is defined as the $max(d_{a},d_{b})$, where
$d_{a}$ is the distance from the automatic contour points to the closest point
of the manual contour, and $d_{b}$ is the opposite. HD is measured in $mm$ in
this work.

These metrics are provided for three anatomical regions of the heart because
of the different challenges that they face. The middle of the right ventricle
is the most stable and consistent part, but the top (base of the ventricle)
suffers from quite a bit of variability in the shape of contours, and the
bottom (apex of the ventricle) usually renders the worst performance due to
the small size of the contour and poor contrast in the image.

###  III-B The added value of a recurrent unit, GAN and L1 loss

Fig. 6 shows how the R-FCNN introduces a significant improvement over the FCNN
in the RV apical (low) region, with an increase of DI of a 52% (from $0.38$ to
$0.58$), and a reduction of the HD in a 72% (from $13.60$ to $3.82$). The
other two regions, top and mid, show a similar performance being only slightly
worse at the DI of the top region.

The addition of the L1 loss to the baseline FCNN also improves the performance
at the apical region of the RV, both in DI and HD, with a small gain in both
metrics at the mid-region, but with a drop of 0.03 in DI at the top region.

Finally, the GAN-FCNN improves the performance with respect to the FCNN in all
regions and metrics, but with a small impact (DI jumps of 0.01-0.02, HD
reduced in 0.5-1 mm) except for the large reduction of the HD in the apical
region.

The combination of L1 and R-FCNN leads to worse results than using any of
these two concepts in isolation at the apical region but matches the best
performance of the other two concepts in the other two regions.

On the contrary, the combination of L1 and GAN leads to better results than
using any of these two concepts in isolation, in all regions and using both
metrics. The best performance this is the one provided by the FCNN+GAN+L1 and
will be used as a baseline for the next experiments.

Fig. 8 shows how the GAN and R-FCNN combination does not have any benefit, and
that the performance of adding the L1 loss is even worse.

Figure 5: Examples of automatic segmentation results in images from the RV
MICCAI dataset. These are instances where ROI-GAN-A showed superior
segmentation results in comparison with the baseline FCNN.

###  III-C ROI-GAN with an R-FCNN provides the best performance

The three versions of the ROI-GAN architecture are first evaluated with an
FCNN as the generator, showing a drop in performance with respect to the
FCNN+GAN+L1, see Fig. 8. On the contrary, the ROI-GAN using R-FCNNs as
generators improve the performance, see Fig. 7, being the ROI-GAN-A the best
in average in all regions.

In more detail, ROI-GAN-A delivers the best in all scores but in the DI of the
mid-region, where ROI-GAN-B gets the best results, and the HD in the low
apical region, where the FCNN+GAN+L1 delivers the best score.

###  III-D Generalization of results

To confirm the results obtained in our in-house dataset, the performance of
the baseline FCNN and of proposed ROI-GAN-A architecture are tested in the RV
MICCAI Challenge 2012. Illustrative examples are provided in Fig. 5.

Table I shows how the ROI-GAN-A clearly improves over the FCNN in DI and HD,
with gains of $0.05$ and of $5.09$ mm respectively. This improvement in
performance is of similar magnitude than the one observed in our in-house
dataset, where an average of $0.05$ and $3.49$ mm was observed.

The performance of the ROI-GAN-A, a fully automatic method, is close to the
best methods of the literature, some of them semi-automatic (see Table I),
which are able to further improve the DI in $0.03$ and reduce the HD in
$0.75$mm).

One last test is performed to evaluate the robustness in the extraction of
clinical indexes such as volume or EF: a linear regression analysis between
manual and automated endocardiac areas, for both ROI-GAN-A and FCNN, reveal a
$R$ correlation coefficient of $0.9642$ and $0.8899$ respectively.

Methods | FA/SA** | DM | HD
---|---|---|---
ROI-GAN-A | FA | 0.80 (0.22) | 8.03(4.41)
FCNN [Our baseline] | FA | 0.75(13.12) | 13.12(10.36)
Avendi et al. [31] | FA | 0.82 (0.16) | 8.03 (4.41)
Ringenberg et al 2014 [32] | FA | 0.83 (0.18) | 8.73 (7.62)
Zuluaga et al 2013 [33] | FA | 0.73 (0.27) | 12.50 (10.95)
Wang et al 2012 [34] | FA | 0.61 (0.34) | 22.20 (21.74)
Ou et al 2012 [35] | FA | 0.61 (0.29) | 15.08 (8.91)
Maier et al 2012 [10] | SA | 0.77 (0.24) | 9.79 (5.38)
Nambakhsh et al 2013 [36] | SA | 0.56 (0.24) | 22.21 (9.69)
Bai et al 2013 [37] | SA | 0.76 (0.23) | 9.77 (5.59)
Grosgeorge et al 2013 [9] | SA | 0.81 (0.16) | 7.28 (3.58)

TABLE I: Segmentation performance results on the RV Test2Set MICCAI of public dataset. DI: Dice Index; HD: Hausdorff Distance (mm); FA: fully automatic; SA: semi automatic. |  | TOP | TOP | MID | MID | LOW | LOW
---|---|---|---|---|---|---|---
METHODS | FA/SA** | DM | HD | DM | HD | DM | HD
FCNN | FA | 0.87(0.20) | 3.19(6.20) | 0.73(0.28) | 5.01(12.98) | 0.38(0.37) | 13.60(22.79)
R-FCNN | FA | 0.86(0.21) | 2.79(3.03) | 0.73(0.28) | 4.50(10.76) | 0.58(0.30) | 3.82(10.83)
FCNN+L1 | FA | 0.84(0.25) | 3.33(6.12) | 0.74(0.26) | 3.33(8.78) | 0.47(0.36) | 4.12(10.30)
R-FCNN+L1 | FA | 0.86(0.24) | 2.90(2.79) | 0.74(0.27) | 5.00(12.66) | 0.45(0.36) | 8.38(17.44)
FCNN+GAN | FA | 0.88(0.17) | 2.87(4.65) | 0.75(0.27) | 3.92(10.03) | 0.40(0.36) | 4.63(9.06)
R-FCNN+GAN | FA | 0.87(0.20) | 2.86(5.57) | 0.72(0.28) | 4.61(12.33) | 0.43(0.36) | 9.17(18.50)
FCNN+GAN+L1 | FA | 0.88(0.18) | 2.68(3.99) | 0.76(0.25) | 3.81(10.44) | 0.42(0.38) | 2.68(3.99)
R-FCNN+GAN+L1 | FA | 0.87(0.20) | 3.31(7.63) | 0.72(0.27) | 5.10(13.55) | 0.41(0.33) | 14.46(25.01)
ROI-GAN-A-FCNN | FA | 0.85(0.22) | 3.30(6.61) | 0.75(0.27) | 3.35(8.64) | 0.46(0.35) | 3.30(6.61)
ROI-GAN-A-R-FCNN | FA | 0.89(0.18) | 2.43(2.21) | 0.77(0.22) | 2.67(6.67) | 0.49(0.33) | 6.03(14.49)
ROI-GAN-B-FCNN | FA | 0.87(0.21) | 2.72(3.41) | 0.75(0.27) | 3.77(9.76) | 0.37(0.37) | 9.07(17.23)
ROI-GAN-B-R-FCNN | FA | 0.87(0.22) | 2.84(4.60) | 0.78(0.22) | 2.64(6.42) | 0.47(0.35) | 4.29(9.89)
ROI-GAN-C-FCNN | FA | 0.86(0.23) | 2.75(2.75) | 0.71(0.29) | 5.70(14.49) | 0.37(0.37) | 11.56(20.51)
ROI-GAN-C-R-FCNN | FA | 0.85(0.25) | 3.33(7.24) | 0.76(0.25) | 3.88(10.93) | 0.47(0.364) | 7.29(16.56)

TABLE II: Segmentation performance results on the Twins-UK dataset. DI: Dice
Index; HD: Hausdorff Distance (mm); FA: fully automatic; SA: semi automatic.

Figure 6: Evaluation of the added value of a recurrent unit (R-FCNN), the
adversarial training (FCNN+GAN), and their combination with the L1 loss. Note
that the HD bars in the LOW region for FCNN and R-FCNN+L1 reach larger values
than the ones displayed in the plot.

Figure 7: Benefit of the ROI-GAN over the baselines FCNN and FCNN+GAN+L1. Note
how the gain from an FCNN to an FCNN+GAN+L1 is doubled with an ROI-GAN-A with
an R-FCNN in all metrics but the HD of the low apical region.

Figure 8: Strategies that do not improve the FCNN+GAN+L1 performance: the
addition of the recurrent unit, or the ROI-GAN without a recurrent unit.

##  IV Discussion

The performance of the FCNN for the task of RV segmentation has been improved
by the combination of the three existing concepts (R-FCNN, FCNN-GAN, L1 norm)
through the ROI-GAN, a novel interpretation of the coGAN where two GANs are
set to cooperate at two fields of view (general and local, or full resolution
and ROI-focus). The best combination of the three existing concepts achieved
an improvement of $0.05$ and $3.49$ mm in DI and HD respectively with respect
to the baseline FCNN and this improvement was doubled with the ROI-GAN-A
architecture.

The combination of local and global features through an ROI-GAN has thus
provided a benefit. The rationale sought was to enable the global FCNN to
learn the useful features through the help of the local FCNN, coordinating
their training with a generative adversarial game and sharing parameters (i.e.
a CoGAN). CoGANs were proposed to avoid the need for paired datasets during
the learning stage and reported excellent performance in the problem of
Unsupervised Domain Adaptation [24]. The problem of image segmentation at two
different fields of views in this work do share many more features than images
from very different modalities (i.e. depth and color image, as in [24]), and
we interpret this to be the main reason why sharing parameters was actually
only beneficial at the generator, and not at the discriminator of the GANs
(performance of ROI-GAN-A being superior to the ROI-GAN-C).

An interesting experimental finding was that the ROI-GAN-A architecture
achieved the constructive coordination of the R-FCNN and GAN, which otherwise
would result in a drop in segmentation performance (see Table II). The GANs
have been proved to be strategical for enhancing the learning generalization
(i.e. a better loss regularisation) [26, 27], and an R-FCNN models the spatial
coherence as a set of connections to the previous slices (data input prepared
with image slices from top to bottom of the heart) - these two concepts are
not in apparent conflict, and the reason why these to concepts did not work
together in a single FCNN, remains elusive to us. A possible explanation is
the strong penalty that the GAN term imposes on MSE loss, that will be
detrimental for a proper back-propagation through the C-GRU unit.

In this work, we illustrate that the problem of RV segmentation is, in fact,
the combination of 3 problems, each of the 3 sections of the RV presents
different challenges. While the top basal slices present a minor difficulty in
localization but a great anatomical variability, the bottom apical slices
present a great difficulty in localization but a much simpler shape (i.e RV
collapses towards a circular structure), and mid slices will be an
intermediate problem. As a consequence, there is not a single architecture
being the optimal solution for all these 3 problems. In the top and middle
slices, an ROI-GAN solution outperforms the rest (A or B configurations for
top or mid slices), but the best solution to capture the apex of the RV is the
R-FCNN. Further research is needed to design the architecture that adapts to
the anatomical region present in the image.

Redundancy across space, or time [38], is clearly a useful resource in the
segmentation task. Exploiting the spatial redundancy is the rationale of the
R-FCNN, and our results confirm the initial findings at the apex of the Left
Ventricle (LV), where the main gain was observed compared to the rest of the
anatomy [15]. The RV has a much greater anatomical variability, but this did
not prevent a recurrent unit to better constrain the segmentation in the
challenging apical slices. Nevertheless, the use of recurrent unit may not be
an optimal solution, since is continuously limited by the problem of vanishing
gradient that may decrease the overall performances [39]. Further research is
needed to study alternatives such as 3D FCNNs, where 3D convolution capture
all the spatial coherence/redundancy [40].

The evaluation methodology followed in this work was designed to examine the
concepts proposed while minimizing possible confounding factors regarding the
learning rate. All FCNNs had the same number of convolution layers, up-
convolutions, ReLU and BN units. Besides, the number of epochs and the
learning rate were equal in the two datasets used, where at every batch size
each network take as input a sequence of consecutive SA images (or the
corresponding number of stack images in an R-FCNN). Nevertheless, we cannot
claim an independence of all confounding factors (i.e. the characteristics of
the datasets used).

Initial evidence of the generality of our findings was provided by testing the
final proposed solution in the best public dataset available to our knowledge,
where a distinct improvement in comparison with the baseline FCNN was found
(i.e. 0.80 (0.22) vs 0.75 (13.12) in DI and HD respectively). This experiment
also showed that another solution, based on classical and simple concepts such
as thresholding, still achieves better results [32], motivating the hypothesis
that a combination of classical and deep learning approaches is an interesting
direction of further research.

Future works could also explore the use of 3D convolutions within the ROI-GAN,
where the 3D generators (i.e global and local) should extract the spatial
information in the better way without any R-FCNN vanishing gradient problem
[39], or the idea of multiple generators able to see different cropping scales
of the input MRI sequences.

## References

  * [1] Catherine Kreatsoulas and Sonia S. Anand.  The impact of social determinants on cardiovascular disease.  Canadian Journal of Cardiology, 26:8–13, 2010.
  * [2] Hundley WG. Stacey RB.  Magnetic resonance (cmr) and computed tomography (cct) in facilitating heart failure management. current treatment options in cardiovascular medicine.  doi:10.1007/s11936-013-0253-6., 2013;15(4):373-386.
  * [3] Jianxu Chen, Lin Yang, Yizhe Zhang, Mark S. Alber, and Danny Z. Chen.  Combining fully convolutional and recurrent neural networks for 3d biomedical image segmentation.  CoRR, abs/1609.01006, 2016.
  * [4] P A Davlouros, K Niwa, G Webb, and M A Gatzoulis.  The right ventricle in congenital heart disease.  Heart, 92(suppl 1):i27–i38, 2006.
  * [5] Right ventricle segmentation from cardiac mri: A collation study.  Medical Image Analysis, 19(1):187 – 202, 2015.
  * [6] Maria Lorenzo-Vald s, Gerardo I. Sanchez-Ortiz, Andrew G. Elkington, Raad H. Mohiaddin, and Daniel Rueckert.  Segmentation of 4d cardiac mr images using a probabilistic atlas and the em algorithm.  Medical Image Analysis, 8(3):255 – 265, 2004.  Medical Image Computing and Computer-Assisted Intervention - MICCAI 2003\.
  * [7] S. C. Mitchell, B. P. F. Lelieveldt, R. J. van der Geest, H. G. Bosch, J. H. C. Reiver, and M. Sonka.  Multistage hybrid active appearance model matching: segmentation of left and right ventricles in cardiac mr images.  IEEE Transactions on Medical Imaging, 20(5):415–423, May 2001.
  * [8] Hamilton M Bucciarelli-Ducci C. Moolan-Feroze O, Mirmehdi M.  Segmentation of the right ventricle using diffusion maps and markov random fields.  In Medical image computing and computer-assisted intervention?MICCAI 2014., New York: Springer; 2014. p 682?689.
  * [9] Dacher J-N Ruan S. Grosgeorge D, Petitjean C.  Graph cut segmenta- tion with a statistical shape model in cardiac mri. comput vis image.  Comput Vis Image Underst, 2013.
  * [10] Santos A-Ledesma-Carbayo MJ. Maier OMO, Jimenez D.  Segmenta- tion of rv in 4d cardiac mr volumes using region-merging graph cuts.  Comput. Cardiology, 2012.
  * [11] D. Mahapatra and J. M. Buhmann.  Automatic cardiac rv segmentation using semantic information with graph cuts.  pages 1106–1109, April 2013.
  * [12] Phi Vu Tran.  A fully convolutional neural network for cardiac segmentation in short-axis mri.  CoRR, abs/1604.00494, 2016.
  * [13] G. Luo, R. An, K. Wang, S. Dong, and H. Zhang.  A deep learning network for right ventricle segmentation in short-axis mri.  pages 485–488, Sept 2016.
  * [14] Jesse Lieman-Sifry, Matthieu Lê, Felix Lau, Sean Sall, and Daniel Golden.  Fastventricle: Cardiac segmentation with enet.  CoRR, abs/1704.04296, 2017.
  * [15] Rudra P. K. Poudel, Pablo Lamata, and Giovanni Montana.  Recurrent fully convolutional neural networks for multi-slice MRI cardiac segmentation.  Reconstruction, Segmentation, and Analysis of Medical Images-First International Workshops, RAMBO 2016 and HVSMR 2016, Held in Conjunction with MICCAI 2016, Athens, Greece, October 17, 2016, Revised Selected Papers, pages 83–94, 2016.
  * [16] MR Avendi, Arash Kheradvar, and Hamid Jafarkhani.  Fully automatic segmentation of heart chambers in cardiac mri using deep learning.  Journal of Cardiovascular Magnetic Resonance, 18(1):P351, Jan 2016\.
  * [17] Fully automatic roi extraction and edge-based segmentation of radius and ulna bones from hand radiographs.  Biocybernetics and Biomedical Engineering, 37(4):718 – 732, 2017\.
  * [18] Zehan Wang, Lijun Zhu, and Jiandong Qi.  Roi extraction in dermatosis images using a method of chan-vese segmentation based on saliency detection.  274:197–203, 01 2014.
  * [19] Seokwon Yeom.  Multi-level segmentation of infrared images with region of interest extraction.  International Journal of Fuzzy Logic and Intelligent Systems, 16(4):246–253, 2016.
  * [20] Kaiming He, Georgia Gkioxari, Piotr Dollár, and Ross B. Girshick.  Mask R-CNN.  CoRR, abs/1703.06870, 2017.
  * [21] Marvin Teichmann, Michael Weber, J. Marius Zöllner, Roberto Cipolla, and Raquel Urtasun.  Multinet: Real-time joint semantic reasoning for autonomous driving.  CoRR, abs/1612.07695, 2016.
  * [22] Nikita Dvornik, Konstantin Shmelkov, Julien Mairal, and Cordelia Schmid.  Blitznet: A real-time deep network for scene understanding.  CoRR, abs/1708.02813, 2017.
  * [23] Z. Xiong, V. V. Fedorov, X. Fu, E. Cheng, R. Macleod, and J. Zhao.  Fully automatic left atrium segmentation from late gadolinium enhanced magnetic resonance imaging using a dual fully convolutional neural network.  IEEE Transactions on Medical Imaging, pages 1–1, 2018.
  * [24] Ming-Yu Liu and Oncel Tuzel.  Coupled generative adversarial networks.  CoRR, abs/1606.07536, 2016.
  * [25] Ming-Yu Liu, Thomas Breuel, and Jan Kautz.  Unsupervised image-to-image translation networks.  CoRR, abs/1703.00848, 2017.
  * [26] Deepak Pathak, Philipp Krähenbühl, Jeff Donahue, Trevor Darrell, and Alexei A. Efros.  Context encoders: Feature learning by inpainting.  CoRR, abs/1604.07379, 2016.
  * [27] Phillip Isola, Jun-Yan Zhu, Tinghui Zhou, and Alexei A. Efros.  Image-to-image translation with conditional adversarial networks.  CoRR, abs/1611.07004, 2016.
  * [28] Valdes AM-Spector TD. Cohort Profile Moayyeri A, Hammond CJ.  Cohort profile: Twinsuk and healthy ageing twin study.  nt J Epidemiol. 2013 Feb;42(1):76-85.
  * [29] Junyoung Chung, Çaglar Gülçehre, KyungHyun Cho, and Yoshua Bengio.  Empirical evaluation of gated recurrent neural networks on sequence modeling.  abs/1412.3555, 2014, http://arxiv.org/abs/1412.3555.
  * [30] Mennatullah Siam, Sepehr Valipour, Martin Jäampersand, and Convolutional Gated Recurrent Networks for Video Segmentation Nilanjan Ray.  Convolutional gated recurrent networks for video segmentation.  CoRR, abs/1611.05435, 2016, http://arxiv.org/abs/1611.05435.
  * [31] M. R. Avendi, Arash Kheradvar, and Hamid Jafarkhani.  Automatic segmentation of the right ventricle from cardiac mri using a learning-based approach.  Magnetic resonance in medicine, 78 6:2439–2448, 2017.
  * [32] Jordan Ringenberg, Makarand Deo, Vijay Devabhaktuni, Omer Berenfeld, Pamela Boyers, and Jeffrey Gold.  Fast, accurate, and fully automatic segmentation of the right ventricle in short-axis cardiac mri.  Computerized Medical Imaging and Graphics, 38(3):190 – 201, 2014\.
  * [33] Modat M Ourselin S Zuluaga MA, Cardoso MJ.  Multi-atlas propaga- tion whole heart segmentation from mri and cta using a local nor- malized correlation coefficient criterion. in: Functional imaging and modeling of the heart.  New York: Springer; 2013, 174?181., 2013.
  * [34] Chen H Wang C, Peng C.  A simple and fully automatic right ventri- cle segmentation method for 4-dimensional cardiac mr images.  a MICCAI Segmentation Challenge, 2012.
  * [35] Erus G Davatzikos C u Y, Doshi J.  Multi-atlas segmentation of the cardiac mr right ventricle. proceedings of 3d cardiovascular imaging: a miccai segmentation challeng.  Nice, France, 2012.
  * [36] Punithakumar K Goela A Rajchl M Peters TM Ayed IB Nambakhsh CM, Yuan J.  Left ventricle segmentation in mri via convex relaxed distribution matching.  Med Image Anal 2013, 17:1010?1024, 2013.
  * [37] O?Regan DP Tong T Wang H Jamil-Copley S Peters NS Rueckert D. Bai W, Shi W.  A probabilistic patch-based label fusion model for multi-atlas segmentation with registration refinement:application to cardiac mr images.  IEEE Trans Med Imaging 2013, 32:1302?1315, 2013.
  * [38] Nicolo Savioli, Miguel Silva Vieira, Pablo Lamata, and Giovanni Montana.  Automated segmentation on the entire cardiac cycle using a deep learning work-flow.  IEEExplore, 2018.
  * [39] Junyoung Chung, Çaglar Gülçehre, KyungHyun Cho, and Yoshua Bengio.  Empirical evaluation of gated recurrent neural networks on sequence modeling.  CoRR, abs/1412.3555, 2014.
  * [40] Nicolo Savioli, Giovanni Montana, and Pablo Lamata.  V-fcnn: Volumetric fully convolution neural network for automatic atrial segmentation.  MICCAI 2018 Atrial Segmentation Challenge, Springer, 2018.