# RLSAC: Reinforcement Learning enhanced Sample Consensus
for End-to-End Robust Estimation

Chang Nie1, Guangming Wang1, Zhe Liu2∗, Luca Cavalli3, Marc Pollefeys3,4,
Hesheng Wang1
1Department of Automation, Key Laboratory of System Control
and Information Processing of Ministry of Education, Shanghai Jiao Tong
University
2 MoE Key Lab of Artificial Intelligence, AI Institute, Shanghai Jiao Tong
University
3 Department of Computer Science, ETH Zürich 4 Microsoft Mixed Reality and AI
Zürich Lab
<EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS>Corresponding Authors. The first
two authors contributed equally.

###### Abstract

Robust estimation is a crucial and still challenging task, which involves
estimating model parameters in noisy environments. Although conventional
sampling consensus-based algorithms sample several times to achieve
robustness, these algorithms cannot use data features and historical
information effectively. In this paper, we propose RLSAC, a novel
Reinforcement Learning enhanced SAmple Consensus framework for end-to-end
robust estimation. RLSAC employs a graph neural network to utilize both data
and memory features to guide exploring directions for sampling the next
minimum set. The feedback of downstream tasks serves as the reward for
unsupervised training. Therefore, RLSAC can avoid differentiating to learn the
features and the feedback of downstream tasks for end-to-end robust
estimation. In addition, RLSAC integrates a state transition module that
encodes both data and memory features. Our experimental results demonstrate
that RLSAC can learn from features to gradually explore a better hypothesis.
Through analysis, it is apparent that RLSAC can be easily transferred to other
sampling consensus-based robust estimation tasks. To the best of our
knowledge, RLSAC is also the first method that uses reinforcement learning to
sample consensus for end-to-end robust estimation. We release our codes at
https://github.com/IRMVLab/RLSAC.

##  1 Introduction

Figure 1: RLSAC remodel the sampling consensus process. By modeling the
sampling consensus as a reinforcement learning process, RLSAC can achieve end-
to-end learning on various robust estimation tasks.

As a fundamental module in computer vision, robust estimation is crucial for
many tasks, such as camera pose estimation [10, 33, 31, 32], motion
segmentation [26, 19, 29, 30], short and wide baseline matching [22, 28],
plane fitting [18], and line fitting [12, 20]. However, it is still difficult
to exclude disturbances while estimating accurate models. To address this
issue, sampling consensus-based algorithms are widely used, which are
represented by the RANdom SAmple Consensus (RANSAC) [16] algorithm. It first
samples the minimum set required for the task, _e.g._ , a minimum set size of
2 for 2D line fitting. Then, the hypothesis is solved by the minimum set.
Next, all data is divided into inliers and outliers, according to their
residuals to the hypothesis. Finally, the above process is repeated and the
best hypothesis is selected based on the highest inlier ratio. RANSAC can
provide strong robustness and generalization, but as the outlier rate
increases, the probability of sampling inliers decreases. As a result, the
performance of RANSAC degrades rapidly. This is because RANSAC samples each
data evenly, regardless of data features that can be used for classifying
inliers and outliers. Additionally, the non-differentiable deterministic
random sampling of RANSAC also limits it to be integrated into the learning-
based pipeline.

Since sampling the minimum set from the data is quite similar to the process
of sampling an action from the action space in reinforcement learning [17,
13], the sampling consensus can be integrated into the reinforcement learning
framework. Sampling in reinforcement learning can be achieved through a neural
network, which extracts the data features. In addition, the reward from the
environment can be used to train the reinforcement learning framework without
differentiation. Therefore, to learn from data features and avoid
differentiating, we propose the RLSAC: Reinforcement Learning enhanced SAmple
Consensus for end-to-end robust estimation. As shown in Figure 1, RLSAC
regards sampling consensus as the process of interaction between the agent and
environment in reinforcement learning. Specifically, the agent uses a neural
network to sample the minimal set from the data as an action. The environment
then performs model generation and evaluation based on the action and outputs
the next state, which is used in the next iteration.

However, designing appropriate reward and state are very important and
challenging in reinforcement learning. To achieve reinforcement learning
enhanced sampling consensus, RLSAC proposes new state transition and reward
modules. Specifically, the state is encoded by augmenting the original data
features with memory features, including the current action, data residuals,
and historical information. When the state is input into the agent, these
features can provide more information about the quality of the previous
action. This allows RLSAC to gradually explore a better hypothesis by
utilizing this memory information.

Additionally, the evaluation result of the generated hypothesis can be used as
the reward signal to train the neural network without differentiation. The
reward signal enables the learning-based sampling consensus for end-to-end
robust estimation. Furthermore, the evaluation result is the feedback from the
downstream task. Thus, the neural network can learn to effectively use the
data features and optimize the output to meet the requirements of the
downstream task.

Moreover, instead of directly predicting the final result from the data in one
shot [27], RLSAC employs multiple episodes, each containing several sampling
processes. In addition, RLSAC performs one random sampling at the beginning of
each episode to form the initial state. This approach preserves the robustness
of multiple random sampling and provides basic performance for RLSAC. Besides,
RLSAC can be extended to other robust estimation tasks since it is not
restricted to any specific task.

The proposed RLSAC is tested on two classic robust estimation tasks, which are
the 2D line fitting task and the fundamental matrix estimation task. The
experimental results show that RLSAC achieves great performance.

Our main contributions are as follows:

  * •

We propose RLSAC: a novel Reinforcement Learning enhanced SAmple Consensus
framework for end-to-end robust estimation. It learns data features to sample
the minimum set. RLSAC retains the robustness of the multiple sampling
process, while the initial random sampling can provide the basic performance.

  * •

RLSAC proposes an approach for state encoding, which includes both current and
historical information. This enables the agent to assess the quality of the
previous actions and gradually explore better hypotheses. RLSAC is trained
unsupervised using the reward function, which avoids differentiating the
sampling process and achieves end-to-end robust estimation.

  * •

RLSAC is evaluated on two robust estimation tasks. The 2D line fitting task
demonstrates its robustness to disturbances and effective progressive
exploration capability. In the fundamental matrix estimation task, RLSAC
achieves state-of-the-art performance. Furthermore, RLSAC can be easily
applied to other sampling consensus-based robust estimation tasks.

##  2 Related Work

Figure 2: The pipeline of the proposed RLSAC. The fundamental matrix
estimation problem is used as an example. The black, green, and blue lines
represent outliers, inliers, and the minimum set, respectively. The yellow
arrows are only used once during initialization. The red and orange arrows
indicate the loop in an episode. The initial states are randomly sampled. The
best hypothesis for this scene is selected by scoring all hypotheses. The
collected experience is recorded in the replay buffer for training.

Robust estimation is a basic module for many tasks. Although the simple
repetitive random sampling strategy of RANSAC [16] is robust and generalized,
it has some limitations, such as no further optimization, inefficient
sampling, and non-differentiability.

There are several methods observing that local features help to optimize the
sampling result. LO-RANSAC [15] continues to sample in the inliers with a
smaller threshold after sampling the best model so far, aiming to find a
better hypothesis near the current one. NAPSAC [25] uses a fixed hypersphere
to acquire local data and samples from it, but this approach loses global
features and may get stuck in local data. To address this, progressive NAPSAC
[4] gradually expands the hypersphere to extend the sampling from local to
global. GC-RANSAC [5] considers spatial continuity between inliers and
surrounding points, modeling the connections of the data through graph-cut to
divide inliers and outliers. MAGSAC++ [6] assesses the model quality by
weighting various thresholds to reduce the sensitivity to the choice of a
specific noise scale.

To improve sampling efficiency, some methods use guided sampling instead of
random sampling. PROSAC [14] sorts the data based on a quality function and
then samples the sorted data sequentially to improve efficiency. USAC [24]
integrates the advantages of various methods to achieve robustness and
efficiency. To learn from the data, Yi et al. [36] are the first to use a
neural network based on PointNet to directly classify inliers and outliers.
Then, Zhang et al. [37] improve this work by proposing pooling and unpooling
blocks to learn the local context of correspondences. NG-RANSAC [9] uses a
neural network to calculate the sample probability for each point, achieving
probability-based sampling. The neural network is trained using reinforcement
learning, but it did not use reinforcement learning to achieve sampling
consensus and progressive exploration. Barath et al. [2] propose the MQ-Net to
learn from residual histograms and evaluate the quality of the model.
Additionally, the authors design the MF-Net to learn to reject bad minimum
sets early, further improving efficiency. NeFSAC [11] uses a neural network to
reject the motion-inconsistent and poorly-conditioned minimal samples.

The non-differentiability of RANSAC makes it challenging to integrate into an
end-to-end learning pipeline. Some methods propose the differentiable RANSAC.
For example, DSAC [8] replaces the deterministic selection process with
probabilistic selection, allowing for differentiation with respect to the
data. Wei et al. [35] achieve gradient propagation by predicting the
probabilities of being inliers to guide sampling. To avoid differentiation,
some methods use the loss as reward signals through reinforcement learning to
train the network. Bhowmik et al. [7] use reinforcement learning to train the
feature point detection network but not for the sampling consensus process.
Truong et al. [27] iteratively delete points with reinforcement learning,
seeking the maximum consensus model that meets the threshold. However, the
authors encode the attributes of the points into the state, but does not
include long-range historical information or the position of the hypothesis in
the state space. In addition, this method does not include the sampling
consensus process and may overlook better solutions.

##  3 Method

###  3.1 Problem Formulation

Robust estimation can be considered as generating a good hypothesis $h$ given
a set of data $\chi=\left\\{{{{\rm{x}}_{i}}}\right\\}_{i=1}^{N}$, which may be
disturbed by noise. For instance, the hypothesis $h$ could represent the
parameters of a 2D line, and $\chi$ could be all the points in the 2D plane.
Or $h$ could be the fundamental matrix that represents the epipolar geometry
of a pair of images, and $\chi$ could be all the correspondences. Similarly,
the data contained in ${{\rm{x}}_{i}}$ varies with the task. As a commonly
used robust estimation method, the sampling consensus method samples $n$
minimum sets $\mathcal{M}$ from $\chi$. The size $m$ of a minimum set varies
depending on the task. For example, when fitting a 2D line, the size $m=2$.
Then, these minimum sets $\mathcal{M}$ are solved by the minimum solver $S$ to
output hypotheses:

$H=\left\\{{S\left({{\mathcal{M}_{j}}}\right)\left|{{{\mathcal{M}_{j}}}\in
M,j=1,2,...,n}\right.}\right\\}.$ (1)

Next, the hypotheses $H$ are evaluated using a scoring function $f$. The
residuals of all data points $\chi$ can be computed and used to calculate the
inlier ratio, which is commonly used as a metric for the hypothesis quality
[16]. Finally, the hypothesis with the highest score is chosen as the best
hypothesis $h_{Best}$:

${h_{Best}}=\mathop{\arg\max}\limits_{h\in H}f\left({h,\chi}\right).$ (2)

By solving the problem using several minimum sets $\mathcal{M}$, the model can
achieve robust estimation, which is less sensitive to outliers and can lead to
more accurate results.

The RANSAC [16] algorithm performs random sampling to sample the minimum sets
$\mathcal{M}$, which cannot fully exploit the data features. As shown in
Figure 1, One alternative is to consider the sampling of a minimum set as an
action taken by an agent based on the current state, within the reinforcement
learning framework:

$a_{t+1}\sim\pi_{\phi}\left(a_{t}\mid s_{t}\right).$ (3)

Here, the policy network $\pi_{\phi}$ depends on the weights $\phi$. The
action $a_{t+1}$ is sampled by the policy $\pi_{\phi}$ from the state $s_{t}$
and $a_{t}$ at time $t+1$, which can also be viewed as the process of sampling
a minimum set $\mathcal{M}_{j}$ from all data $\chi$. So the Eq. 2 can be
rewritten that the best hypothesis is selected by a reinforcement learning
enhanced sample consensus method:

$h_{Best}=\mathop{\arg\max}\limits_{t=1,2,...,j}f\left({S\left({{a_{t}}}\right),\chi}\right).$
(4)

In addition, the policy $\pi_{\phi}$ is a trainable neural network, and the
state $s_{t}$ contains the features of the data $\chi$. Therefore, the minimum
set can be selected based on sufficient learned knowledge of the data
features, rather than being chosen randomly. Furthermore, the evaluation
result $f\left({S\left({{a_{t}}}\right),\chi}\right)$ of the minimum solver
$S$ can serve as the reward in reinforcement learning to achieve unsupervised
learning.

###  3.2 System Framework

With the problem formulation of modeling the process of sampling consensus as
a reinforcement learning problem, we introduce RLSAC, which is illustrated in
Figure 2. Although the fundamental matrix estimation task is used as an
example, the pipeline is also applicable to other robust estimation tasks.
Firstly, RLSAC initiates multiple episodes for the correspondences of a pair
of images $\chi$ at \raisebox{-0.7pt}{1}⃝. An episode contains many steps. At
the start of each episode, a random sampling of the minimum set
$\mathcal{M}_{0}$ is performed to generate the initial state ${s_{0}}$ through
state transition at \raisebox{-0.7pt}{2}⃝. Specifically, the initial state
${s_{0}}$ is obtained by concatenating each data point with the memory
features, which are consisting of action, residual, and historical features
(see Section 3.5).

Next, the initial state ${s_{0}}$ is input into the sampling consensus loop.
The agent receives the current state ${s_{t}}$ and feeds it into the policy
network $\pi_{\phi}$ at \raisebox{-0.7pt}{3}⃝, as shown in Section 3.3. The
network generates a probability for each data point. The $m$ points with the
highest probabilities are selected as the minimum set $\mathcal{M}_{t}$,
instead of random sampling.

Then, the minimum set $\mathcal{M}_{t}$ serves as the action $a_{t}$ for the
agent, which generates a hypothesis ${h_{t}}$ in the environment at
\raisebox{-0.7pt}{4}⃝, as shown in Section 3.4. The residuals of points to the
hypothesis are compared with a threshold to classify points into inliers and
outliers at \raisebox{-0.7pt}{5}⃝. The ratio of inliers is utilized as the
reward $r_{t}$ for the current action $a_{t}$ to train the policy network
$\pi_{\phi}$ at \raisebox{-0.7pt}{6}⃝. Additionally, the action, inliers, and
residuals are used for the state transition to generate the next state
${s_{t+1}}$ at \raisebox{-0.7pt}{7}⃝, as shown in Section 3.5. Finally, the
environment outputs the next state ${s_{t+1}}$ and the reward $r_{t}$, which
are used by the agent to start the next step at \raisebox{-0.7pt}{8}⃝.

Furthermore, the state ${s_{t}}$, action $a_{t}$, reward $r_{t}$, and the next
state ${s_{t+1}}$ in every step are collected as experiences in the replay
buffer [13] for training. After all episodes are complete, the hypothesis with
the highest inlier ratio across all episodes is output as the best hypothesis
${h_{Best}}$ for this pair of images.

###  3.3 Sampling Minimum Set by Agent

The agent receives the state ${s_{t}}\in{\mathbb{R}^{N\times C}}$, where $N$
is the number of the correspondences of a pair of images. The channel $C=c+3$,
with $c$ denoting the dimension of data features and $3$ representing the
dimension of memory features (see Section 3.5). In addition, the first
hypothesis $h_{0}$ of each episode is generated using a randomly sampled
minimum set, which provides a basic performance for RLSAC.

Then the state ${s_{t}}$ is fed into the policy network $\pi_{\phi}$. To
achieve permutation invariance for the input data, RLSAC uses edge convolution
(EdgeConv) from the DGCNN [34] as the basic module to establish the policy
network $\pi_{\phi}$. The EdgeConv can model the interrelationship of
correspondences by graph neural networks. It can extract features from
neighboring nodes in a graph and aggregate them into a central node. The
policy network $\pi_{\phi}$ extracts data features and calculates the
probabilities by softmax for each point of being in the minimum set. The
probability can be interpreted as the probability of obtaining a greater
return on the action for the long term, rather than the probability of
achieving the best result in the current state. Consequently, the $m$ points
with the highest probability are selected as the minimum set $\mathcal{M}_{t}$
in the current state ${s_{t}}$. Importantly, all previously used minimum sets
are recorded to avoid selecting a duplicate minimum set. Thus, when a new
minimum set is selected, it is checked whether it has been used. If the new
minimum set has already been used, then another $m$ data set is selected
following the probability, which will be checked as well. Until the unused
data set is found, it is output as the minimum set. Ultimately, the minimum
set is as the action $a_{t}\in{\mathbb{R}^{m\times C}}$ output by the agent.

###  3.4 Evaluating Hypothesis in Environment

The environment generates a hypothesis $h_{t}$ based on the received action
$a_{t}$ from the agent. Next, the residuals $R$ are calculated for all data
$\chi$ with respect to the hypothesis:

$R_{t}=\left\\{{D\left({{x_{i}},{h_{t}}}\right)\left|{{x_{i}}\in\chi,i=1,2,...,N}\right.}\right\\},$
(5)

where the function $D$ is for residual calculation. The scalar valued
residuals $R$ are calculated at all data $\chi$. With the pre-defined
threshold, the data $\chi$ is divided into inliers
$I_{t}\in{\mathbb{R}^{z\times C}}$ and outliers
$O_{t}\in{\mathbb{R}^{\left({N-z}\right)\times C}}$ based to the residuals.

In the sampling consensus methods, the inlier ratio commonly represents the
quality of the hypothesis. Since the hypothesis $h_{t}$ is generated by the
action $a_{t}$ in RLSAC, the inlier ratio can be considered as the reward
$r_{t}$ of the current action $a_{t}$ to train the policy network $\pi_{\phi}$
without ground truth.

With the hypotheses related-rewards, RLSAC can update weights $\phi$ of the
policy network $\pi$ without differentiating the sampling process. By modeling
sampling consensus as an interactive process in reinforcement learning, RLSAC
achieves end-to-end robust estimation while avoiding differentiating.

Figure 3: The state transition in RLSAC. To form the next state, the data
features are added with the memory features, which contain action features,
residual features, and historical features.

###  3.5 State Transition

The state transition module allows RLSAC to encode the previous state and
action, enabling RLSAC to explore the state space effectively. As illustrated
in Figure 3, the next state $s_{t+1}$ is obtained by concatenating the
original data features $N\times c$ with memory features
$\left\\{{A,R,\mathcal{H}}\right\\}$, which comprise action features $N\times
1$, residual features $N\times 1$ and historical features $N\times 1$.

The action features are derived from the current action $a_{t}$. If a data
point $x_{i}$ is used in the action $a_{t}$, the corresponding entry in the
action features ${\alpha_{i}}$ is set to $1$, otherwise it is $-1$:

$A_{t}=\left\\{{{\alpha_{i}}}\right\\},{\alpha_{i}}=\left\\{{\begin{array}[]{*{20}{l}}1&{{\rm{if\
}}{x_{i}}\in{a_{t}}}\\\
{-1}&{{\rm{otherwise}}}\end{array}}\right.,i=1,2,...,N.$ (6)

The action features could provide the agent with information on the current
action, like the current location in the data for the next state.

The residual features are obtained from the residuals $R_{t}$ computed in Eq.
5. They encode the relative relationship between the hypothesis and the data,
which can be thought of as the direction for the agent.

The historical features collect how often is a data point used up to the
current step. They are initialized to $0$ and updated as follow: for each data
point $x_{i}$ used in the current action $a_{t}$, the corresponding entry in
the historical features ${\tau_{i}}$ is incremented by $1$:

${\mathcal{H}_{t}}=\left\\{{{\tau_{i}}}\right\\},{\tau_{i}}={\tau_{i}}+1{\rm{\
if\ }}{x_{i}}\in{a_{\rm{t}}},i=1,2,...,N.$ (7)

The historical features can provide the agent with information on the actions
taken so far, enabling it to keep track of its path through the data.

By encoding the state in this way, the agent has access to both current and
historical information, allowing it to reach the goal state. Furthermore, the
memory features serve as a director of local navigation, guiding the agent to
explore the data features and reach its destination gradually.

##  4 Experiments

We evaluate the performance of RLSAC on classic tasks, including 2D line
fitting and fundamental matrix estimation. The 2D line fitting task serves as
a basic benchmark to assess the performance of the robust estimation algorithm
and provides visualization of the sampling process. The fundamental matrix
estimation task can show the performance of algorithms on complex camera pose
estimation task in the real world, which is a critical task in computer
vision.

Table 1: 2D line fitting. The<EMAIL_ADDRESS>and median error(∘) on various outlier rates are reported. Method | 0.1 | 0.2 | 0.3 | 0.4 | 0.5 | 0.6 | 0.7
---|---|---|---|---|---|---|---
mAA ↑ | Mid. ↓ | mAA ↑ | Mid. ↓ | mAA ↑ | Mid. ↓ | mAA ↑ | Mid. ↓ | mAA ↑ | Mid. ↓ | mAA ↑ | Mid. ↓ | mAA ↑ | Mid. ↓
RANSAC [16] | 0.870 | 0.049 | 0.863 | 0.052 | 0.850 | 0.056 | 0.829 | 0.061 | 0.796 | 0.071 | 0.746 | 0.087 | 0.608 | 0.135
Ours | 0.875 | 0.047 | 0.874 | 0.049 | 0.872 | 0.048 | 0.865 | 0.050 | 0.858 | 0.052 | 0.845 | 0.056 | 0.824 | 0.062
Ours-0.5 | 0.849 | 0.053 | 0.850 | 0.055 | 0.854 | 0.053 | 0.858 | 0.052 | 0.858 | 0.052 | 0.864 | 0.050 | 0.849 | 0.054

###  4.1 Settings

RLSAC is built on the widely used reinforcement learning framework SAC-
Discrete [13]. As shown in Figure 2, the collected replay buffer is retrieved
for off-policy to update the actor and critic network in reinforcement
learning.

Since RLSAC uses the inlier ratio as the reward for training, it is an
unsupervised method. To explore more images, only one episode with multiple
steps is collected per image pair during training. The framework is trained
for 100 epochs. During training, the episode termination conditions are set as
follows: (i) if the number of inliers is unchanged for $\kappa=2$ steps; (ii)
if the inlier ratio does not exceed the maximum inlier ratio in the episode
for $\varsigma=3$ steps; (iii) if the maximum number of steps $\psi=15$ is
reached. During testing, only the third condition is valid, and each pair of
images can be tested in $\nu$ episodes.

As with the standard reinforcement learning [13], RLSAC uses probabilistic
sampling during training and max sampling during testing. For the EdgeConv
module in the policy network, the value of k-nearest neighbors is set to
$k=15$. The network architecture and additional information can be found in
the supplementary material. Moreover, we have included ablation experiments to
analyze the impact of specific network details, also provided in the
supplementary material. Similar to the RANSAC implementation, RLSAC also
employs refinement using the inliers of the final best hypothesis as the final
model polishing.

The experiments are conducted on a Linux computer with an Intel i7 3.6GHz CPU
and an NVIDIA RTX 2080Ti GPU. Our implementation is based on PyTorch.

###  4.2 Case Study 1: 2D Line Fitting

The 2D line fitting task is a basic problem in robust estimation, which can
visualize the process of robust estimation and assess the robustness
quantitatively to different outlier rates. In this task, each data point
contains only the coordinates, thus all data points can be expressed as:
$\chi=\left\\{{\left[{{x_{i}},{y_{i}}}\right]\left|{\
i=1,2,...,N}\right.}\right\\}$, where $\chi$ represents the data features
$N\times c$, with $c=2$. Since two points are sufficient to determine a 2D
line, the agent can generate a hypothesis by selecting two points from the set
of all data points as the minimum set $N\times m$, where $m=2$. For
comparison, the RANSAC [16] algorithm is evaluated with the same task.

To evaluate the performance of RLSAC in the 2D line fitting task, we
synthesize $N=100$ data points for both training and testing. Specifically, a
ground truth 2D line is randomly generated in a $10\times 10$ picture. True
inliers are then randomly generated on the line based on the set outlier rate.
Next, the true inliers are uniformly disturbed within a range of 0.1 around
the line. Thus, the inlier threshold could be set to $\varepsilon=0.1$.
Additionally, true outliers are randomly scattered throughout the picture.
Moreover, it is possible for true outliers to be located within the inlier
region, as is often the case in real-world scenes.

For accurately evaluating and comparing the performance of different methods,
we adopt the mean Average Accuracy (mAA) metric in [2]. The angular difference
between the estimated line and the ground truth line is used as the error
metric, which is used to calculate the mAA metric with a tolerance threshold
of $0.5^{\circ}$.

The performance of RLSAC and RANSAC at different outlier rates with 150
iterations is evaluated and the results are presented in Table 1. When the
outlier rate is lower than 0.5, RANSAC can achieve a similar performance to
RLSAC. This is because the repeated random selection of the minimum set can
achieve good performance in simple low outlier rate scenes. However, the
performance of RANSAC degrades more quickly than that of RLSAC as the outlier
rate increases. This suggests that RLSAC can explore hypotheses closer to the
ground truth in noisy scenes.

As the outlier rate increases beyond 0.5, RLSAC can still maintain a low error
and high mAA score. This indicates that RLSAC is more robust to disturbances,
providing a more stable performance compared to RANSAC.

Figure 4: The qualitative results of RLSAC on 2D line fitting. The hypothesis
converges to the ground truth as the number of steps increases. The green
points represent inliers, while the red points represent outliers. The sampled
minimum set points are denoted by black edges. The ground truth is represented
by a yellow line, while the hypothesis and inlier threshold are represented by
blue and dashed lines respectively.

The qualitative results of RLSAC are shown in Figure 4, which demonstrates its
ability to quickly find the better hypothesis even from a bad initial state.
This means that the memory features can serve as a director of local
navigation, allowing RLSAC to move towards a better state through outputting
actions. Moreover, once RLSAC finds a high inlier ratio hypothesis that is
close to the ground truth, it continues to explore the local state to further
improve the result, rather than randomly transitioning to other states.

The results of the 2D line fitting task show that RLSAC can effectively
utilize both data features and memory features, maintaining robust and stable
performance in noisy environments. In addition, it can gradually explore a
better hypothesis with the help of memory features.

###  4.3 Case Study 2: Fundamental Matrix Estimation

The fundamental matrix estimation is a crucial robust estimation task in
computer vision, which solves the fundamental matrix by correspondences in a
pair of images. In this study, we use the data and settings in CVPR tutorial
RANSAC in 2020 [3], where the correspondences are detected by RootSIFT [1] and
matched by the nearest neighbor. The training data comprises 12 scenes, each
with 100k image pairs, while the test data includes 2 scenes, with 4950 image
pairs. The dataset uses Second Nearest Neighbor (SNN) ratio as the matching
score. The correspondences are sorted in descending order by SNN. Then the top
$N=150$ SNN correspondences are selected. Next, each point extracts a
128-dimensional descriptor $desc$ through the SIFT algorithm. Thus, the data
points are:
$\chi=\left\\{{\left[{x_{1}^{i},y_{1}^{i},x_{2}^{i},y_{2}^{i},SNN^{i},desc_{1}^{i},desc_{2}^{i}}\right]\left|{i=1,2,...,N}\right.}\right\\}\in{\mathbb{R}^{N\times
c}}$, where $c=261$. The 8-point solver is used to solve the hypotheses [21].
The inlier threshold of RLSAC is set to $\varepsilon=4$. The evaluation
settings follow [3]. To compare with other methods, RANSAC [16], USAC [24],
MAGSAC++ [6] are tested, which use the recommended settings in [3].

Table 2: Fundamental matrix estimation. The mAA@$10^{\circ}$ and median error(${\epsilon_{\textbf{R}}}$ and ${\epsilon_{\textbf{t}}}$) of rotation and the direction of translation at 1k iterations are reported in degrees. Method |  mAA@$10^{\circ}$ ↑ |  Median (∘) ↓
---|---|---
R | t | ${\epsilon_{\textbf{R}}}$ | ${\epsilon_{\textbf{t}}}$
RANSAC[16] | 0.644 | 0.488 | 2.307 | 5.100
USAC[24] | 0.741 | 0.604 | 1.036 | 2.157
MAGSAC++[6] | 0.753 | 0.614 | 0.924 | 1.895
Ours | 0.760 | 0.622 | 0.926 | 1.751
Figure 5: The mAA@$10^{\circ}$ at different iterations. The results on the
fundamental matrix estimation task at different iterations. Figure 6: The
qualitative results of RLSAC on the fundamental matrix estimation task. Inlier
rate, rotation and translation errors are reported. The blue lines represent
the sampled minimum set points, and the green lines represent the inliers.
Figure 7: The step results of RLSAC on the fundamental matrix estimation task.
The meaning of the lines and the evaluation metrics are consistent with Figure
6.

As shown in Figure 5, RLSAC outperforms other methods in estimating both the
rotation matrix and translation vector. Remarkably, RLSAC can achieve high
accuracy with only 100 iterations. Comparisons reveals that RLSAC possesses a
higher upper bound in performance than MAGSAC.

The quantitative results of the methods at 1k iterations are presented in
Table 2. RLSAC achieves great performance with small errors, a little higher
than MAGSAC++[6]. Specifically, RLSAC shows high performance in estimating the
direction of the translation vector compared to other methods. Since RLSAC
could effectively learn features from the data to exclude noise disturbances,
it has significant performance on translation vector estimation.

Figure 6 shows the qualitative results of the fundamental matrix estimation of
RLSAC in each scene. The figure demonstrates that RLSAC selects rigid and
fixed feature points on buildings as the minimum sets, which can help to find
better poses. Furthermore, the step-by-step fundamental matrix estimation
results of RLSAC are visualized in Figure 7. It demonstrates a gradual
increase in the inlier ratio of the hypothesis and a decrease in the rotation
and translation errors. This illustrates that RLSAC can progressively explore
the state space to find a better hypothesis.

##  5 Ablation Study

We perform ablation studies by modifying or removing modules to analyze their
effectiveness. The experimental data and settings remain the same as in
Section 4.

Robustness and Generalization of RLSAC in 2D Line Fitting: The _Ours-0.5_ in
Table 1 shows the result of evaluating the robustness and generalization of
RLSAC in 2D Line Fitting. We train RLSAC on data with the outlier rate of 0.5
and then test it on various outlier rates. In most cases, _Ours-0.5_ can
outperform RANSAC. Notably, when the outlier rate exceeds 0.5, _Ours-0.5_
performs even better than the model trained at that outlier rate. This is
because, in scenes with high outlier rates, the point distribution is closer
to a uniform distribution, which lacks the features of a dense distribution.
As a result, the model $RLSAC_{High}$ trained on high outlier rates may not
have learned the dense distribution in low outlier rates. This results in a
mediocre performance of $RLSAC_{High}$ in low outlier rates scenes.
Conversely, scenes of low outlier rates exhibit both sparse and dense point
distributions in different regions, providing more diverse features for the
model $RLSAC_{Low}$ to learn. Consequently, the $RLSAC_{Low}$ can predict
better results when the dense distribution of points is occasionally present
in the high outlier scene. These results demonstrate that RLSAC can
effectively learn the distribution in point groups to classify inliers and
outliers.

Table 3: The ablation study results of RLSAC on fundamental matrix estimation. | Method |  mAA@$10^{\circ}$ ↑ |  Median (∘) ↓
---|---|---|---
R | t | ${\epsilon_{\textbf{R}}}$ | ${\epsilon_{\textbf{t}}}$
(a) | Ours (w/o descriptors) | 0.702 | 0.568 | 1.400 | 2.963
Ours (full, with 128 DIM descriptors) | 0.760 | 0.622 | 0.926 | 1.751
(b) |  Ours (with max sampling in training and max sampling in testing) | 0.730 | 0.591 | 1.132 | 2.331
Ours (with max sampling in training and probabilistic sampling in testing) | 0.706 | 0.531 | 1.415 | 2.893
Ours (with probabilistic sampling in training and probabilistic sampling in testing) | 0.720 | 0.581 | 1.150 | 2.508
Ours (full, with probabilistic sampling in training and max sampling in testing) | 0.760 | 0.622 | 0.926 | 1.751
(c) | Ours (with N=100 points) | 0.727 | 0.588 | 1.216 | 2.464
Ours (with N=200 points) | 0.747 | 0.604 | 1.050 | 2.108
Ours (with N=300 points) | 0.733 | 0.594 | 1.180 | 2.364
Ours (full, with N=150 points) | 0.760 | 0.622 | 0.926 | 1.751

Effect of Descriptors: To investigate the effect of descriptors with image
semantic features, we conduct experiments as shown in Table 3 (a). This
suggests that descriptors with semantic features are helpful for RLSAC to
effectively learn and sample minimum sets.

Different Sampling Approaches: In Table 3 (b), four different sampling
strategies are compared. The results illustrate that the best performance can
be achieved by probabilistic sampling during training and max sampling during
testing. This is consistent with the sampling strategy for actions in
reinforcement learning. Specifically, probabilistic sampling can provide
randomness and exploratory during training, while max sampling can output the
optimal strategy during testing to improve performance and efficiency.

Number of State Points: In RLSAC, the state points are selected from the top
$N$ correspondences sorted by SNN. Different values of $N$ are evaluated in
Table 3 (c). The best performance is obtained when $N=150$. We count the
number of correspondences in images at $SNN<0.8$ recommended in [3], which is
also around 150 points. This is reasonable that a smaller number of points may
exclude points, which would solve the better hypothesis. While more points
will introduce more noise, making it more difficult for RLSAC to learn
effective sampling strategies.

##  6 Discussion

The methods of estimating results directly with neural networks in one shot
[23] are not robust and generalized in the scenes that have not been learned.
Moreover, their poor interpretability leads to poor practicality in
engineering applications. In contrast, traditional methods based on
mathematical theory, such as multiple sampling consensus for model estimation
and noise covariance matrix estimation in simultaneous localization and
mapping (SLAM), offer clear interpretability and well-defined scopes of
application. However, many traditional methods cannot be integrated into a
learning-based framework due to their non-differentiability.

Therefore, combining these traditional methods with learning-based methods can
provide both interpretability and high performance. RLSAC combines sampling
consensus with reinforcement learning to avoid differentiation of sampling
while better extracting data features and memory features. In addition, RLSAC
can be easily transferred to other sampling consensus tasks due to:

  * •

The input data of RLSAC is not limited to coordinates and descriptors.
Additional features such as depth estimation information and semantic
segmentation information can also be used as input for the policy network.

  * •

RLSAC retains random sampling at the beginning of each episode and each sample
result is de-duplicated. This provides basic performance for sampling
consensus-based tasks.

  * •

The rewards in RLSAC are linked with the evaluation of the hypothesis.
Therefore, RLSAC can be extended to other robust estimation tasks, which
require different evaluation methods. Moreover, RLSAC does not require
differentiation of the sampling process, the hypothesis solving process, and
the evaluation process.

In this way, RLSAC enables end-to-end learning that incorporates traditional
methods. This allows for consistent optimization objectives across modules.

##  7 Conclusion

In this paper, we propose RLSAC, a reinforcement learning enhanced sample
consensus framework for end-to-end robust estimation. RLSAC models the
sampling consensus process as a reinforcement learning task to achieve end-to-
end robust estimation. The basic performance of RLSAC is provided by the
initial random sampling in each episode. In RLSAC, a new state transition
strategy is designed to effectively extract current and historical
information, which can guide RLSAC to explore state space. Furthermore, the
inlier ratio of the hypothesis is used as a reward to realize unsupervised
policy network learning. In experiments, the 2D line fitting task illustrates
that RLSAC is robust to various disturbances and exhibits strong
generalization. The visualization of the sampling process shows that RLSAC can
progressively explore to better models and continues to explore locally.
Additionally, the fundamental matrix estimation task demonstrates that RLSAC
outperforms other methods in the complex camera pose estimation problem.
Notably, RLSAC is not limited to specific tasks and can easily perform end-to-
end learning on various sampling consensus-based tasks. In future work, it is
worthwhile to explore the integration of traditional and learning-based
methods within this framework, while trying to maintain the strengths of each
method.

##  8 Acknowledgement

This work was supported in part by the Natural Science Foundation of China
under Grant 62225309, 62073222, U21A20480 and U1913204. The authors gratefully
appreciate the contribution of Yiqing Xu from CUMT.

## References

  * [1] Relja Arandjelović and Andrew Zisserman.  Three things everyone should know to improve object retrieval.  In 2012 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 2911–2918, 2012.
  * [2] Daniel Barath, Luca Cavalli, and Marc Pollefeys.  Learning to Find Good Models in RANSAC.  In 2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 15723–15732, 2022.
  * [3] D Barath, TJ Chin, O Chum, D Mishkin, R Ranftl, and J Matas.  RANSAC in 2020 tutorial.  In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2020.
  * [4] Daniel Barath, Maksym Ivashechkin, and Jiri Matas.  Progressive NAPSAC: sampling from gradually growing neighborhoods.  arXiv preprint arXiv:1906.02295, 2019.
  * [5] Daniel Barath and Jiří Matas.  Graph-cut RANSAC.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 6733–6741, 2018.
  * [6] Daniel Barath, Jana Noskova, and Jiri Matas.  Marginalizing Sample Consensus.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 44(11):8420–8432, 2022.
  * [7] Aritra Bhowmik, Stefan Gumhold, Carsten Rother, and Eric Brachmann.  Reinforced feature points: Optimizing feature detection and description for a high-level task.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 4948–4957, 2020.
  * [8] Eric Brachmann, Alexander Krull, Sebastian Nowozin, Jamie Shotton, Frank Michel, Stefan Gumhold, and Carsten Rother.  DSAC — Differentiable RANSAC for Camera Localization.  In 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 2492–2500, 2017.
  * [9] Eric Brachmann and Carsten Rother.  Neural-guided RANSAC: Learning where to sample model hypotheses.  In Proceedings of the IEEE/CVF International Conference on Computer Vision (CVPR), pages 4322–4331, 2019.
  * [10] Federico Camposeco, Andrea Cohen, Marc Pollefeys, and Torsten Sattler.  Hybrid Camera Pose Estimation.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 136–144, 2018.
  * [11] Luca Cavalli, Marc Pollefeys, and Daniel Barath.  NeFSAC: Neurally Filtered Minimal Samples.  In Computer Vision – ECCV 2022, pages 351–366, 2022.
  * [12] Tat-Jun Chin, Hanzi Wang, and David Suter.  Robust fitting of multiple structures: The statistical learning approach.  In 2009 IEEE 12th International Conference on Computer Vision (ICCV), pages 413–420, 2009.
  * [13] Petros Christodoulou.  Soft actor-critic for discrete action settings.  arXiv preprint arXiv:1910.07207, 2019.
  * [14] Ondrej Chum and Jiri Matas.  Matching with PROSAC-progressive sample consensus.  In 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR), pages 220–226, 2005.
  * [15] Ondřej Chum, Jiří Matas, and Josef Kittler.  Locally optimized RANSAC.  In Joint Pattern Recognition Symposium, pages 236–243, 2003.
  * [16] Martin A Fischler and Robert C Bolles.  Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography.  Communications of the ACM, 24(6):381–395, 1981.
  * [17] Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine.  Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor.  In Proceedings of the 35th International Conference on Machine Learning, pages 1861–1870, 2018.
  * [18] M. Hofer, B. Odehnal, H. Pottmann, T. Steiner, and J. Wallner.  3D shape recognition and reconstruction based on line element geometry.  In Tenth IEEE International Conference on Computer Vision (ICCV’05), pages 1532–1538, 2005.
  * [19] Chaokang Jiang, Guangming Wang, Yanzi Miao, and Hesheng Wang.  3D scene flow estimation on pseudo-lidar: Bridging the gap on estimating point motion.  IEEE Transactions on Industrial Informatics, pages 7346–7354, 2022\.
  * [20] Hongdong Li.  Consensus set maximization with guaranteed global optimality for robust geometry estimation.  In 2009 IEEE 12th International Conference on Computer Vision (ICCV), pages 1074–1080, 2009.
  * [21] H Christopher Longuet-Higgins.  A computer algorithm for reconstructing a scene from two projections.  Nature, 293(5828):133–135, 1981.
  * [22] Dmytro Mishkin, Jiri Matas, and Michal Perdoch.  MODS: Fast and robust method for two-view matching.  Computer Vision and Image Understanding, 141:81–93, 2015.
  * [23] Omid Poursaeed, Guandao Yang, Aditya Prakash, Qiuren Fang, Hanqing Jiang, Bharath Hariharan, and Serge Belongie.  Deep Fundamental Matrix Estimation without Correspondences.  In Proceedings of the European Conference on Computer Vision (ECCV) Workshops, 2018.
  * [24] Rahul Raguram, Ondrej Chum, Marc Pollefeys, Jiri Matas, and Jan-Michael Frahm.  USAC: A Universal Framework for Random Sample Consensus.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 35(8):2022–2038, 2013.
  * [25] Philip Hilaire Torr, Slawomir J Nasuto, and John Mark Bishop.  Napsac: High noise, high dimensional robust estimation-it’s in the bag.  In British Machine Vision Conference (BMVC), page 3, 2002.
  * [26] P. H. S. Torr and A. Zisserman.  MLESAC: A New Robust Estimator with Application to Estimating Image Geometry.  Computer Vision and Image Understanding, 78(1):138–156, 2000.
  * [27] Giang Truong, Huu Le, Erchuan Zhang, David Suter, and Syed Zulqarnain Gilani.  Unsupervised Learning for Maximum Consensus Robust Fitting: A Reinforcement Learning Approach.  IEEE Transactions on Pattern Analysis and Machine Intelligence, pages 3890–3903, 2022.
  * [28] Guangming Wang, Jiahao Qiu, Yanfeng Guo, and Hesheng Wang.  Fusionnet: Coarse-to-fine extrinsic calibration network of lidar and camera with hierarchical point-pixel fusion.  In 2022 International Conference on Robotics and Automation (ICRA), pages 8964–8970, 2022.
  * [29] Guangming Wang, Shuaiqi Ren, and Hesheng Wang.  Unsupervised learning of optical flow with non-occlusion from geometry.  IEEE Transactions on Intelligent Transportation Systems, 23(11):20850–20859, 2022.
  * [30] Guangming Wang, Xiaoyu Tian, Ruiqi Ding, and Hesheng Wang.  Unsupervised learning of 3d scene flow from monocular camera.  In 2021 IEEE International Conference on Robotics and Automation (ICRA), pages 4325–4331, 2021.
  * [31] Guangming Wang, Xinrui Wu, Shuyang Jiang, Zhe Liu, and Hesheng Wang.  Efficient 3d deep lidar odometry.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(5):5749–5765, 2022.
  * [32] Guangming Wang, Xinrui Wu, Zhe Liu, and Hesheng Wang.  Pwclo-net: Deep lidar odometry in 3d point clouds using hierarchical embedding mask optimization.  In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition (CVPR), pages 15910–15919, 2021.
  * [33] Guangming Wang, Jiquan Zhong, Shijie Zhao, Wenhua Wu, Zhe Liu, and Hesheng Wang.  3D hierarchical refinement and augmentation for unsupervised learning of depth and pose from monocular video.  IEEE Transactions on Circuits and Systems for Video Technology, 33(4):1776–1786, 2022.
  * [34] Yue Wang, Yongbin Sun, Ziwei Liu, Sanjay E Sarma, Michael M Bronstein, and Justin M Solomon.  Dynamic graph cnn for learning on point clouds.  Acm Transactions On Graphics (tog), 38(5):1–12, 2019.
  * [35] Tong Wei, Yash Patel, Jiri Matas, and Daniel Barath.  Fully Differentiable RANSAC.  arXiv preprint arXiv:2212.13185, 2022.
  * [36] Kwang Moo Yi, Eduard Trulls, Yuki Ono, Vincent Lepetit, Mathieu Salzmann, and Pascal Fua.  Learning to find good correspondences.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 2666–2674, 2018.
  * [37] Jiahui Zhang, Dawei Sun, Zixin Luo, Anbang Yao, Lei Zhou, Tianwei Shen, Yurong Chen, Long Quan, and Hongen Liao.  Learning two-view correspondences and geometry using order-aware network.  In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV), pages 5845–5854, 2019.


out}$, we have $\tau_{d}\gg 1$ for all but the least massive discs and the gap
filling is by horizontal diffusion. If $\tau_{d}\approx 1$ then the gap
filling is not diffusive and therefore even quicker. We conclude that Equation
25 is correct and may be regarded as an upper-limit timescale.

##  Appendix C Gravitational instabilities

Self gravity is important when the Toomre $Q$ is close to $1$. For gaseous
discs, the Toomre $Q$ parameter is given by

$Q=\frac{c_{s}\Omega}{\pi G\Sigma}=\frac{c_{s}^{2}}{\pi G\Sigma
h}\approx\frac{c_{s}^{2}r_{\rm out}^{2}}{\pi GMh},$ (28)

where the total compact disc mass is $M\sim\Sigma r_{{\rm out}}^{2}$. Taking
plausible values $c_{s}\sim 1{\rm km/s}$ and $h\sim 1000$ km, the compact disc
mass $M$ has to be larger than $\sim 10^{29}$ g, which is much more massive
than any disc in our study.

For dusty debris discs, the sound speed is replaced by the appropriate
dispersion velocity. The smallest dispersion velocity is the vertical one,
$v_{\rm z}$, which minimizes $Q$. It is comparable to the aforementioned sound
speed for scale height of $h\sim 10^{3}\ \rm km$, since $v_{\rm z}\cong v_{\rm
K}f\approx v_{\rm K}h/r_{\rm out}$, or $\sqrt{GM_{\rm WD}}h/r_{\rm
out}^{3/2}$.

Q$\approx$1 from Equation 28 then yields the limit for the scale height as

$h=\frac{\pi r_{\rm out}M}{M_{\rm WD}}\cong 1~{}\rm{m}.$ (29)

where we take $M=10^{24}$ g, the largest mass in our parameter space and
$M_{\rm WD}=0.6M_{\odot}$, a typical WD mass. The conclusion is that close to
the Roche radius, the discs are well stable unless $h$ is smaller than about a
meter, or much less if we take a smaller $M$.

##  Appendix D Effective shattering yield

The shattering yield, first discussed in Section 5.3, is defined as the
excavated (fragment) dust mass over the impactor dust mass. The study of
Koschny & Grün (2001) provides an estimate for the shattering yield $Y_{shat}$
for pure dust by the following formula:

$Y=10^{-9}\rho_{\rm d}2^{-b}m_{d}^{b-1}v_{\rm rel}^{2b},$ (30)

where $\rho_{d}$ and $m_{d}$ are the dust grain density and mass. The
parameter $b$ depends on the material fraction of silicate versus ice. We
adopt $b\cong 1.5$ for pure silicate (Smrekar et al., 1985). Typical relative
velocities $v_{\rm rel}$ from Section 5.3 are of the order of a few $\sim
10^{2}$ m $\times$ s-1, leading to a shattering yield of approximately $Y=\sim
3000$ for micron-sized particles.

However, the effective yield is lower than this value. The excavated material
forms a dust cloud shielding the fragment surface. This ejecta in turn
encounters more compact disc dust grains. At these velocities grain-grain
collisions result in complete vaporization. In the event of full shielding, no
other compact disc dust grain is able to impact the fragment’s surface until
the ejecta is fully vaporized, and only then a subsequent grain can reach the
surface, giving an actual effective yield of $Y_{\rm eff}=1$. We will
demonstrate this quantitatively.

In the fragment’s frame of reference, consider the projectile compact disc
dust grains with number density $n_{1}$ and cross section $A=\pi r_{d}^{2}$
hitting a fragment of size $R\gg r_{d}$ at velocity $v_{1}=v_{\rm rel}$. Each
impact liberates $Y$ dust particles of the same size (for simplicity) from the
fragment with velocity $v_{2}$. $Y$ is the yield, which is taken roughly as
$3000$ (initially). From energy balance, if all the kinetic energy
$0.5m_{d}v_{1}^{2}$ went into the kinetic energy of the fragments,
$0.5Ym_{d}v_{2}^{2}$, we get $v_{2}=v_{1}/\sqrt{Y}$.

Consider now a swarm of ejecta particles formed at time $dt$ with total mass
$dm_{\rm ejecta}=\rho_{\rm ejecta}Av_{2}dt$. It was formed by compact disc
projectile dust grains of mass $dm_{\rm disc}=\rho_{\rm disc}Av_{1}dt$. The
mass ratio is exactly the initial yield:

$Y=\frac{dm_{\rm ejecta}}{dm_{\rm disc}}=\frac{\rho_{\rm ejecta}}{\rho_{\rm
disc}}\frac{v_{2}}{v_{1}}=\frac{\rho_{\rm ejecta}}{\sqrt{Y}\rho_{\rm disc}}.$
(31)

If both the compact disc particles and the ejecta particles are "optically
thick" such that the mean free path is very small, we have from Equation 24,
$\lambda_{\rm disc}\sim(\rho_{\rm d}/\rho_{\rm disc})r_{\rm d}$ for the disc
particles and

$\lambda_{\rm ejecta}\sim\frac{\rho_{\rm d}}{\rho_{\rm ejecta}}r_{\rm
d}=\lambda_{\rm disc}\frac{\rho_{\rm disc}}{\rho_{\rm
ejecta}}=\frac{\lambda_{\rm disc}}{Y^{3/2}},$ (32)

where the last substitution came from rearranging Equation 31.

In terms of the compact disc mass $M_{\rm disc}$ and the scale height $h$,
from Equation 24 we obtain

$\lambda_{\rm disc}\approx\left(\frac{10^{22}~{}\rm{g}}{M_{\rm
disc}}\right)\left(\frac{h}{10^{3}~{}\rm{km}}\right)~{}\rm{cm}$ (33)

Finally, the timescale for the ejecta particles to become "optically thick" is

$t\approx\frac{\lambda_{\rm ejecta}}{v_{2}}=\frac{\lambda_{\rm
disc}}{Yv_{1}}\approx\left(\frac{10^{16}~{}\rm{g}}{M_{\rm
disc}}\right)\left(\frac{h}{10^{3}~{}\rm{km}}\right)10^{-6}~{}\rm{s}$ (34)

For a fragment crossing the compact disc face-on, the flight time through the
disc is simply $t_{\rm flight}=h/v_{\rm rel}$. For typical fragment
velocities, an optically thick ejecta blanket would form within a fraction of
$t/t_{\rm flight}$ of the flight time, i.e. 1 millionth or less of the flight
time.

If an optically thick cloud is present, as was just established, then only a
small fraction of the projectile compact disc dust grains may hit the fragment
and the effective yield $Y_{\rm eff}$ will then be much lower than 3000. To
estimate $Y_{\rm eff}$, we want the number of ejecta grains to be in steady
state, namely the generation rate $\mathcal{R}_{\rm gen}$ must be balanced by
the encounter, or vaporization rate $\mathcal{R}_{\rm evap}$. For the
generation rate, it is just the nominal hitting rate times the effective
yield, $\mathcal{R}_{\rm gen}=Y_{\rm eff}n_{1}Av_{1}$, while for the
vaporization rate, in the rest frame of the ejecta swarm, it is
$\mathcal{R}_{\rm evap}=n_{1}A(v_{1}+v_{2})$, since the relative velocity
between the grains is $v_{1}+v_{2}$. Comparing the rates and plugging in the
velocities, we get that the effective yield is $Y_{\rm
eff}=(v_{1}+v_{2})/v_{1}=1+\sqrt{1/Y}\approx 1$. The effective yield cannot
exceed much more than unity if a thick could is present.


# Pain Assessment based on fNIRS using Bidirectional LSTMs

Raul Fernandez Rojas1, Julio Romero1, Jehu Lopez-Aparicio2, and Keng-Liang
Ou3,4,5 1Human-Centred Technology Research Centre, Faculty of Science and
Technology, University of Canberra, ACT, Australia.
<EMAIL_ADDRESS>of Science, National Autonomous
University of Mexico, Mexico City, Mexico.3Department of Dentistry, Taipei
Medical University Hospital, Taipei, Taiwan.4Department of Dentistry, Taipei
Medical University-Shuang Ho Hospital, New Taipei City, Taiwan.53D Global
Biotech Inc., New Taipei City, Taiwan.*This work was partially supported by 3D
Global Biotech Inc.

###### Abstract

Assessing pain in patients unable to speak (also called non-verbal patients)
is extremely complicated and often is done by clinical judgement. However,
this method is not reliable since patients’ vital signs can fluctuate
significantly due to other underlying medical conditions. No objective
diagnosis test exists to date that can assist medical practitioners in the
diagnosis of pain. In this study we propose the use of functional near-
infrared spectroscopy (fNIRS) and deep learning for the assessment of human
pain. The aim of this study is to explore the use deep learning to
automatically learn features from fNIRS raw data to reduce the level of
subjectivity and domain knowledge required in the design of hand-crafted
features. Four deep learning models were evaluated, multilayer perceptron
(MLP), forward and backward long short-term memory net-works (LSTM), and
bidirectional LSTM. The results showed that the Bi-LSTM model achieved the
highest accuracy ($90.6\%$)and faster than the other three models. These
results advance knowledge in pain assessment using neuroimaging as a method of
diagnosis and represent a step closer to developing a physiologically based
diagnosis of human pain that will benefit vulnerable populations who cannot
self-report pain.

##  I INTRODUCTION

Assessing pain in patients unable to speak (also called non-verbal patients)
is extremely complicated and often is done by clinical judgement. However,
this method is not reliable since patients’ vital signs, including blood
pressure, heart rate, and respiration, fluctuate significantly due to
underlying medical conditions [2]. In addition, assessing pain in non-verbal
patients becomes extremely difficult in situations where the patient is in
endotracheal intubation, in mechanical ventilation, in comma, under surgery,
or with cognitive impairment such as dementia. These situations limit
healthcare professionals’ ability to appropriately respond to and treat the
patient’s discomfort [14]. Untreated pain might lead to health deterioration,
unnecessary suffering, delay recovery, worsen cognitive impairments, or
increase the risk of death. These medical conditions and the obstacle to
evaluate and manage patient’s pain experience in an appropriate manner calls
for the need for a reliable and objective pain assessment.

Possible methods to measure and assess pain objectively have been proposed in
the literature. In a recent study [12], different pain biomarkers in the
saliva of subjects were explored, with concentrations of secretory
immunoglobulin A and tumor necrosis factor-alpha presenting acceptable levels
of reproducibility in healthy subjects; however, salivary-based biomarker
variations are not only due to pain-related information [12]. Another example
is the use of cerebrospinal fluid which has been reported to identify pain in
patients with neuropathic pain and movement disorders in patients with complex
regional pain syndrome [4]. For gastrointestinal disorders, the use of
pharmacological agents such as fentany and octrotide has showed magnitudes of
change in sensory end points, however, there is no clear evidence of an
effective biomarker of visceral pain [4]. Another proposed biomarker of pain
is the use serum of catecholamine (stress hormone) which reflects sympathetic
activation [3]. These examples have shown that biological samples can be used
as possible indicators of human pain.

Recently, neuroimaging methods such as, magnetic resonance imaging (MRI),
positron-emission tomography (PET), electroencephalography (EEG), or
functional near-infrared spectroscopy (fNIRS), have gained recognition due to
their ability to gain insights into the human brain (noninvasively) and
understand the components involved in pain processing. In this context, fNIRS
has demonstrated that external pain stimulation can evoke changes of
oxygenation levels in distinctive cortical regions [8]. fNIRS measures brain
activity by reading cerebral haemodynamics and oxygenation. Specifically, it
measures changes in chromophore mobilization, oxygenated haemoglobin (HbO) and
deoxygenated haemoglobin (HbR) simultaneously [9]. In addition, fNIRS offers
advantages over the other technologies such as, better temporal and spatial
resolution, less exposure to ionising radiation, safe to use over long periods
and many times, relatively inexpensive, and portable; advantages that make
fNIRS a possible candidate for the development of a bedside monitor for the
diagnosis of pain.

Partially responsible to the success of fNIRS and other neurimaging methods to
assess human pain is the use of machine learning. In pain research, machine
learning and fNIRS has successfully been applied for detection and prediction
of pain. For instance, Pourshoghi et al., [6] used a SVM classifier to
classify low pain and high pain from 19 subjects using coefficients from
functional data analysis (FDA) as features with $94\%$ accuracy. In another
study [10], Rojas et al., used LDA, KNN and SVM classifiers to explore
features in time, frequency, and wavelet domain, showing that SVM achieved
$88.41\%$ accuracy to classify heat and cold pain-related data.

In these examples, machine learning was used to discover a mapping of features
from fNIRS data, and then to determine a pain neural representation than can
be used to assess or predict new data. However, a limitation of machine
learning models is the use of hand-crafted feature extraction, which requires
human intervention to design and select the most relevant features that enable
the learning models to solve the task at hand. Therefore, deep learning
methods that can learn features automatically from fNIRS data are expected to
reduce subjectivity in the design of hand-crafted features and improve overall
model performance.

This paper contributes to the development of an objective assessment of pain
for non-verbal patients. In particular, we explore the use of deep learning
methods to reduce the level of subjectivity and domain knowledge to design
hand-crafted features, and instead, process directly raw fNIRS data.
Therefore, the main objective of this study is to examine different deep
learning models to identify an improved method for the assessment of pain.
This study represents a step closer to developing a physiologically-based
assessment of human pain that would benefit non-verbal patients.

##  II METHODOLOGY

###  II-A Subjects

Eighteen right-handed volunteers (three females) were considered in the study,
with mean age $\pm$ standard deviation (31.9 $\pm$ 5.5). The reason to include
right-handed participants was to avoid any variation in functional response
due to lateralisation of brain function. Written informed consent was obtained
from all volunteers. This research study was approved by the Taipei Medical
University (TMU) and full-board review process of the TMU-Joint Institutional
Review Board under contract number 201307010.

###  II-B Experimental Procedure

In this study, thermal pain perceptions were investigated following the
standard procedures of the QST protocol [11]. The pain experiment involved
applying cold and heat to the skin to induce pain. Subjects were exposed to
gradually increasing or decreasing temperatures with a thermode and pressed a
button when they experienced pain (threshold test) and highest intensity of
pain (tolerance test). The experimental protocol was split into two tests, the
thermal pain threshold (low pain) and the thermal pain tolerance (high pain),
with a 2-min rest between both tests. After an initial 60-s rest, the
experiment started with a random selection of three consecutive trials of cold
or heat stimulation, with a 60-s rest between tests. Based on the threshold
and tolerance of cold and heat stimuli, the fNIRS data were organized into
four categories: (1) low-cold (low pain), (2) low-heat (low pain), (3) high-
cold (high pain), and (4) high-heat (high pain). These categories were used to
label the database for the classification task.

###  II-C fNIRS Equipment

Cortical haemodynamic data were collected using an optical topography system,
Hitachi ETG-4000 (Hitachi Medical Corporation, Japan). The spectrometer system
is equipped with a 24-channel cap configured in 12 channels per hemisphere.
The measurement area was the somatosensory cortex, using the international
10-20 system, probes were centred on the C3 and C4 positions. Only raw
Oxyhaemoglobin (Oxy-Hb) was used in the analysis due to its higher signal-to-
noise ratio compared to Deoxyhaemoglobin (Deoxy-Hb). The sampling frequency
was $10Hz$ and no pre-processing was applied to the fNIRS data.

###  II-D Deep Learning Models

In this section the fundamentals of the models are introduced. Three deep
learning models are explored, multi-layer perceptron (MLP), long short-term
memory (LSTM) networks, and bidirectional LSTM (Bi-LSTM).

####  II-D1 MLP

They are a computational model that processes information using a number of
interconnected nodes. These nodes are grouped into layers and associated
through weighted connections. Nodes in each layer apply non-linear operations
to project the data into a space where the data becomes linearly separable
[5]. Every neuron (or computational unit) can be defined in terms of the
following function:

$a^{l+1}=\sigma(W^{l}a^{l}+b^{l}),$ $None$

where $a^{l}$ refers to the activation value for the neurons in the layer $l$,
$W$ is the weight matrix, $b{l}$ is the bias of neurons in layer $l$, and
$\sigma$ is the activation function. In the topology of MLPs fully-connected
layers are employed, in these, each unit in layer $l+1$ is connected with
every unit in layer $l$. The MLP model will be used as baseline model and to
obtain reference values to compare the LSTM and Bi-LSTM models.

####  II-D2 LSTM

These networks are a type of recurrent neural network (RNN) and suitable for
processing time series data. LSTMs were designed to overcome the problem of
long-term dependency in RNN, which made long sequences difficult to learn
using RNN due to the vanishing/exploding gradient problem [1]. LSTMs use a
gated cell to control what information should be remembered and what
information should be forgotten, this is achieved by three gates. The first
gate is a forget gate to determine the information to be removed from the cell
state using a $sigmoid$ layer

$f_{t}=\sigma(W_{f}\cdot[h_{t-1},x_{t}]+b_{f}),$ $None$

The second gate is an input gate that uses a $sigmoid$ layer to determine the
values that are updated, and a $tanh$ layer to define new updated values,
formally defined as:

$i_{t}=\sigma(W_{f}\cdot[h_{t-1},x_{t}]+b_{i}),$ $None$
$\tilde{c_{t}}=\tanh(W_{c}\cdot[h_{t-1},x_{t}]+b_{c}).$ $None$

The cell state is then updated by:

$c_{t}=f_{t}*c_{t-1}+i_{t}*\tilde{c_{t}}$ $None$

The output gate determines the output in the current stated using the cell
state (Equation 5) and a sigmoid layer:

$o_{t}=\sigma(W_{o}\cdot[h_{t-1},x_{t}]+b_{o}),$ $None$
$h_{t}=o_{t}*\tanh(c_{t}),$ $None$

where $x_{t}$ is the input sequence at time $t$, $h_{t-1}$ refers to the past
hidden state and $b_{f}$, $b_{i}$, $b_{c}$, $b_{o}$ are the bias vectors in
each layer.

In this study, the forward LSTM (standard method) and the backward LSTM
(reversed input sequences) will be implemented to compare the performance to
the Bi-LSTM.

####  II-D3 Bi-LSTM

This model is a combination of a forward and a backward LSTM, in other words,
at every time step, data are input in both forward and reverse directions at
the same time. This model concatenates the outputs of the standard and reverse
LSTM by specifying the merge mode in Keras. Bi-LSTMs preserve information from
both past and future as data flows in two ways. It is expected that this
property will make the Bi-LSTM have higher precision than conventional LSTMs,
as LSTMs run inputs in an unidirectional way.

###  II-E Architectures

For comparison purposes, all four models share a similar architecture with an
input layer, two main hidden layers, and an output layer. In addition, network
architectures were determined empirically by multiple experimental
adjustments. However, a number of hyper parameters were left constant (default
value in Keras) across all three models. This is done with the idea that
differences in performance between the models are the result of architectural
difference and not due to better optimisation, pre-processing or ad hoc
customisation.

The input layers in all models are fed with raw fNIRS data. Each data input
was segmented using a sliding window approach with $50\%$ overlap, with each
window containing 300 samples. The input data for the MLP model were in the
form of a $m\times n$ matrix, where $m$ is the number of samples and $n$
refers to the number of fNIRS channels. The LSTM models expect the data in the
form of $m\times k\times n$ where $k$ refers to the time steps.

The proposed MLP model consists of two fully connected layers. The first layer
and second layer have 64 and 32 neurons, respectively, and a rectifier linear
activation unit (ReLu) was used in these two layers. A dropout layer with a
$50\%$ dropout rate was used to prevent over-fitting [13]. Similarly, the
architecture of the LSTM networks consists of two LSTM layers. The two LSTM
layers consist of 64 neurons and 32 neurons respectively, and both layers with
a ReLU activation function. Then a dropout layer with $50\%$ dropout rate
after the second LSTM layer.

Finally, the output layer in all three architectures includes a fully
connected layer with four neurons corresponding to the four pain classes in
the experiment and Softmax activation for classification. In addition, all
models are trained using Adam algorithm to optimise the networks and the
categorical cross entropy loss function for the multi-class classification
task.

##  III RESULTS

In order to evaluate the deep learning models, the dataset was randomly
divided into training set ($70\%$) for and test data ($30\%$). 10-fold cross
validation was used on all networks to avoid over-fitting. Training was done
for 300 epochs with an early stopping criterion of halting training when there
is no decrease in error during the last 50 epochs. The network with the
highest accuracy is chosen as the final model. The deep learning models were
trained with a learning rate of 0.001, decay factor of 0.9, and batch size of
64.

The performance on the test set of the MLP, backward LSTM, forward LSTM, and
Bi-LSTM are listed in Table I. In this table, accuracy, sensitivity and
specificity were used as the evaluation methods for the test data. Overall,
the Bi-LSTM showed the highest accuracy with $90.6\%$, the forward LSTM
(standard) with $85.6\%$, and the backwards LSTM with $82.2\%$, and the
baseline model (MLP) with $71.7\%$.

TABLE I: Comparison of the performance of CNN, forward LSTM (F-LSTM), backward LSTM (B-LSTM), and Bi-LSTM models. Model | Accuracy ($\%$) | Sensitivity ($\%$) | Specificity ($\%$)
---|---|---|---
MLP | $71.7$ | $57.3$ | $75.4$
F-LSTM | $85.6$ | $77.9$ | $88.2$
B-LSTM | $82.2$ | $73.4$ | $86.6$
Bi-LSTM | $90.6$ | $84.6$ | $90.4$

Figure 1: Average accuracy on the validation set over 300 epochs from the deep
learning models.

The performance of the training process of all networks with different number
of iterations is presented in Figure 1. During the training/validation process
the Bi-LSTM achieved $93.1\%$ accuracy using around 100 epochs, this was twice
faster than the other two LSTMs ($\sim$ 200 epochs) to reach comparable
results at $90\%$. This might allow a reduction in the number of epochs
required in the training process, which can be important in training larger
datasets using similar architectures. Similar results can be observed in
Figure 2, where the Bi-LSTM reached a more stable loss faster that the other
three networks.

These results showed that the deep learning models exhibited comparable
results with previous work. For example, in [6] the authors achieved $94\%$
accuracy using a SVM with a total of 120 features generated by functional data
analysis decomposition. Similarly, in [10] $88.41\%$ accuracy was obtained
with a Gaussian SVM with 69 features. An advantage of the present study is
that the deep learning models are fed with raw fNIRS data, while these
previous studies used pre-processed fNIRS data and hand-crafted features.

Figure 2: Average loss on the validation set over 300 epochs from the deep
learning models.

It is also important to highlight that this study has some limitations. Direct
comparisons with other published studies in the literature are difficult due
to the use of different experimental conditions, different neuroimaging
methods (e.g., fMRI, PET), number of subjects, or learning models. Another
limitation in this study is the lack of control for any skin blood flow
contributions and intracerebral haemodynamics to the fNIRS signals. Recent
studies have highlighted the issue that fNIRS signals encompass not only
haemodynamic fluctuations due to neurovascular coupling but also due to skin
blood flow and task-related systemic activity of cortex [7]. However, it was
expected that the use of deep learning models will learn the neural
representation of pain from raw fNIRS data.

##  IV CONCLUSIONS

In this study, we explored the use of deep learning models to learn features
automatically from fNIRS raw data and also to identify an improved method of
the assessment of pain for non-verbal patients. The experimental results
showed that the combination of backward and forward information in the
architecture of the Bi-LSTM model achieve better results than the one-
directional LSTMs (fordward/backward). In addition, the use of deep learning
models did not require complex feature extraction procedures to obtain
satisfactory results, this also reduces the level of subjectivity in the
design of hand-crafted features. These results advance knowledge in pain
assessment using neuroimaging as a method of diagnosis and represent a step
closer to developing a physiologically based diagnosis of human pain that
would benefit vulnerable population who cannot self-report pain.

Future work will focus on using different sensor modalities (e.g., heart rate,
respiration, galvanic skin response, electroencephalogram). A multimodal
approach that combines data from several sensors together can be more robust
and/or more comprehensive for real-time assessment of human pain. This
multimodal approach will help identify possible relationships between
different sensor modalities, or complement each other in case of artifacts or
signal quality issues. In addition, the use of multimodal data fusion
techniques will help unlock the potential of multiple sensors in our future
work.

## References

  * [1] Salma Alhagry, Aly Aly Fahmy, and Reda A El-Khoribi.  Emotion recognition based on eeg using lstm recurrent neural network.  Emotion, 8(10):355–358, 2017.
  * [2] Caroline Arbour and Céline Gélinas.  Are vital signs valid indicators for the assessment of pain in postoperative cardiac surgery icu adults?  Intensive and Critical Care Nursing, 26(2):83–90, 2010.
  * [3] David S Goldstein, Courtney Holmes, and Yehonatan Sharabi.  Cerebrospinal fluid biomarkers of central catecholamine deficiency in parkinson’s disease and other synucleinopathies.  Brain, 135(6):1900–1913, 2012.
  * [4] Kewal K Jain and Kewal K Jain.  The handbook of biomarkers.  Springer, 2010.
  * [5] Francisco Javier Ordóñez and Daniel Roggen.  Deep convolutional and lstm recurrent neural networks for multimodal wearable activity recognition.  Sensors, 16(1):115, 2016.
  * [6] Ahmad Pourshoghi, Issa Zakeri, and Kambiz Pourrezaei.  Application of functional data analysis in classification and clustering of functional near-infrared spectroscopy signal in response to noxious stimuli.  Journal of Biomedical Optics, 21(10):101411, 2016.
  * [7] Raul Fernandez Rojas, Xu Huang, Jesus Hernandez-Juarez, and Keng-Liang Ou.  Physiological fluctuations show frequency-specific networks in fnirs signals during resting state.  In 2017 39th Annual International Conference of the IEEE Engineering in Medicine and Biology Society (EMBC), pages 2550–2553. IEEE, 2017\.
  * [8] Raul Fernandez Rojas, Xu Huang, and Keng Liang Ou.  Spatiotemporal analysis of brain activity response using near infrared spectroscopy.  International Journal of Pharma Medicine and Biological Sciences, 5(1):1, 2016.
  * [9] Raul Fernandez Rojas, Xu Huang, and Keng-Liang Ou.  Toward a functional near-infrared spectroscopy-based monitoring of pain assessment for nonverbal patients.  Journal of biomedical optics, 22(10):106013, 2017.
  * [10] Raul Fernandez Rojas, Xu Huang, and Keng-Liang Ou.  A machine learning approach for the identification of a biomarker of human pain using fnirs.  Scientific reports, 9(1):1–12, 2019.
  * [11] R Rolke, R Baron, Cet al Maier, TR Tölle, R-D Treede, A Beyer, A Binder, N Birbaumer, F Birklein, IC Bötefür, et al.  Quantitative sensory testing in the german research network on neuropathic pain (dfns): standardized protocol and reference values.  Pain, 123(3):231–243, 2006.
  * [12] Eva M Sobas, Amanda Vázquez, Sebastián Videla, Roberto Reinoso, Itziar Fernández, Carmen Garcia-Vazquez, Miguel J Maldonado, and J Carlos Pastor.  Evaluation of potential pain biomarkers in saliva and pain perception after corneal advanced surface ablation surgery.  Clinical Ophthalmology (Auckland, NZ), 14:613, 2020.
  * [13] Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov.  Dropout: a simple way to prevent neural networks from overfitting.  The journal of machine learning research, 15(1):1929–1958, 2014\.
  * [14] Regina LM van Boekel, Ewald Vissers, Jos GC Lerou, and Monique AH Steegers.  Moving beyond pain scores: Multidimensional pain assessment is essential for adequate pain management after surgery.  PLoS One, 12(5):e0177345, 2017.