{%hackmd SybccZ6XD %}

# ROBIN: a Graph-Theoretic Approach to Reject Outliers in Robust Estimation using Invariants

###### tags: `paper`

## Abstract


### why
many methods can deal with moderate outliers, but they fail to solve enormous anounts of outliers.

### goal
- prune outliers in generic estimation problems.
- boost the performance of existing techniques

### how
- invariance: check a subset of mearsurements can solve the corresponding estimation problem.
- graph-theoretic framework: measurements are modeled as vertices and mutual compatibility is captured by edges in a graph.
- combine above two destributions

## introduction

### Robust estimation
- Problem:
unknown variable x lead to noisy and corrupted result
- example:
- 3D perception problems: x may be the pose of an unknown object while the measurements are features of the object
- In Simultaneous Localization and Mapping: x might denote the trajectory of the robot and the location of landmarks
- 根據機器人自身位置與附近景觀，達成定位與建構地圖
- (?)In machine learning: x can be a description of a model regressing the data
- conclusion:
$y_i = h_i(x, \epsilon_i)$
y: the result of the preprocessing of raw sensor data

### two methods of solving estimation problem
- fast heuristics
- upside: fast
- downside: fail to deal with many outliers
- globally-optimally
- upside: tolerate extreme outlier rates
- downside: slow

### goal
real- time operation and rebust more than 95% outliers

## RELATED WORK

### Consensus Maximization
- find the largest set of measurements with errors below a user-defined threshold.
- NP-hard, so it uses randomized approaches, RANSAC
- RANSAC
- upside: minimal set is small and there are not many outliers
- downside: the number of iterations increases exponentially with the percentage of outliers

### M-estimation
- estimation by optimizing a robust cost function that reduces the influence of the outliers

### Graph algorithms
- used in robot perception and vision
- graph-cut: improve performance against noise and outliers

## MEASUREMENT INVARIANTS

### From Measurements to Invariants
$S_j$: the j-th element of this subset
:::success
Definition 1 (n-Invariant)
n-invariant function: $f(y_s) = (h_s(x,\delta_S))$
f: in order to compute a quantity that **no longer depend on x**, so it suitable for any x

ex.
Single rotation averaging: pairwise invariant
Point cloud registration: pairwise invariant
2D-3D camera pose estimation: 4 invariant
:::

### example of invariants

#### ==Single rotation averaging==

:::warning
補充 (Single rotation averaging)
有很多Ri measurement，找到一個R讓cost變小
:::

**measurement model**
$R_i=R*Exp(\epsilon_i)$
Exp: maps a 3D vector to rotation matrix
- rotation matrix: 乘以一個向量的時候有改變向量的方向但不改變大小

R: unknown rotation
Ri: noisy measurements
$\epsilon_i$: measurement noise

#### ==Point cloud registration==

:::warning
補充 (Least-Squares Fitting of Two 3-D Point Sets)
找point cloud轉換公式
:::

**measurement model**
$b_i=Ra_i+t+\epsilon_i$
$\epsilon_i$: isotropic(即在不同方向所測得的性能數值是相同的)
**invariant**
$f(b_i, b_j)=||b_j-b_i||=||a_j-a_i+\delta_j-\delta_i||$

#### ==Point-with-normal registration==
Every point transformation correspond normal transformation

#### ==2D-3D camera pose estimation==

:::warning
補充 (2D-3D camera pose)
find camera pose using the 4 3D points
:::

### From Invariants to Compatibility for Outlier Rejection

- In the previous section, propose variants without distinguishing inliers from outliers.
- In this sector, use invariants to check the outliers where they. this process is called compatibility test.

:::info
Definition 7 (Inliers and Outliers)
Given measurements (1) and a threshold $\beta$ > 0, a measurement i is called an inlier if the corresponding noise satisfies $||\epsilon_i||\leq \beta$ and is called an outlier otherwise.
This process of checking is called **compatibility test**.
:::

#### ==Compatibility test for point cloud registration==

$||b_j-b_i|| = ||a_j-a_i+\delta_j-\delta_i||$

apply the triangle inequality $||a_j-a_i+\delta_j-\delta_i|| \leq ||a_j-a_i|| + ||\delta_j-\delta_i||$
$-||\delta_j-\delta_i||\leq ||b_j-b_i||-||a_j-a_i||\leq ||\delta_j-\delta_i||$

$||\delta_j||\leq \beta$ and $||\delta_i||\leq \beta$
so, $||\delta_j-\delta_i||\leq 2\beta$
$-2\beta \leq ||b_j-b_i||-||a_j-a_i||\leq 2\beta$
pairs of points having similar distance in the two point clouds.

:::info
Definition 8 (Compatibility Test)
Given a subset of n measurements and the corresponding n-invariant, a compatibility test is a binary condition involving the invariant, such that if the condition fails the set of measurements must contain at least one outlier.
:::

test property
- sound: 檢測只有inliers的時候，不會有outliers的結果
- complete: 檢測有outliers的時候，檢測結果通過

## COMPATIBILITY GRAPH FOR OUTLIER REJECTION

- Point out which measurements are outliers
- propose the use of maximum clique and maximum k-core to find inliers

### From Compatibility Tests to Compatibility Graph

- compatibility graph: the result of the compatibility tests for all subsets of n measurements
- advantage: Fast, because it only checks boolean condition without computing an estimate (as opposed to RANSAC)

:::info
Define
compatibility graph $\mathcal{G}(\mathcal{V}, \mathcal{E})$ as an undirected graph
vertex set $\mathcal{V}$: measurement
an edge (i, j) in the edge set E is present in the graph if measurements i and j were involved in at least one of the subsets of measurements that passed the compatibility tests.
:::

:::warning
補充 (Graph)
- directed graph(有向圖)：edge的方向性表示資料間的關係，若vertex(A)與vertex(B)之關係是「單向的」，那麼連結vertex(A)與vertex(B)的edge即具有方向性。
- undirected graph(無向圖)：edge的方向性表示資料間的關係，若vertex(A)與vertex(B)的關係是「雙向的」，那麼連結vertex(A)與vertex(B)之edge就不具有方向性。
- 
- vertex：稱每一個「資料節點」為vertex(或是node)，並定義所有的vertex所形成之集合(Set)為V或V(G)；
- edge：稱每一個「線段(箭號)」為edge(實際上是用一對vertex表示edge，例如(Vi,Vj)即為連結Vi與Vj的edge)，並定義所有的edge所形成之集合(Set)為E或E(G)；
:::

### Inlier Structures in Compatibility Graphs

- prune many outliers by computing the maximum clique of the compatibility graph

:::info
Definition 9 (Maximum Clique)
The maximum clique of G is the clique with the largest number of vertices.
:::

:::info
Theorem 10 (Inliers and Cliques) (我覺得這段有點廢話)
Assume we are given measurements (1) and the corresponding n-invariants; call G the corresponding compatibility graph. Then, assuming there are at least n inliers, the inliers form a clique in G.

- maximum clique is too expensive to compute, so they propose the maximum k-core (defined below) instead
:::

:::info
Definition 11 (k-core, Fig. 1)
:::


## EXPERIMENTS

- ROBIN boosts the robustness of GNC to more than 95% outliers and dominates the state of the art
- runs in tens of milliseconds on challenging large-scale datasets

### Single Rotation Averaging

==Setup.==

ground truth: $R\in SO(3)$
measurement: Ri, i = 1...1000 with increasing outlier rates from 0%~99%
- inlier measurement: $R_i = R Exp(\theta_iu_i)$
$u_i$: random 3D unit vector
$\theta_i \sim N(0,\sigma^2)$ random rotation angle ($\sigma$ =5)
- outlier measurement: random 3D rotation

==result==


### Registration With Correspondences

==Benchmarks==
model source: Bunny model from the Stanford 3D scanning repository
- downsample the model to 1000 points and resize
- apply a random transformation (R, t)
- R: SO(3)
- $||t||\leq 1$
- apply noise
- $\epsilon_i \sim N(0,\sigma^2I)$, $\sigma = 0.01$
- $\epsilon_i \leq \beta$, $\beta = 5.54\sigma$
- generate outliers: replace some bi’s with vectors uniformly sampled in a sphere with radius 5.

==result==

### Registration Without Correspondences
==Setup==
point clooud source: TeddyBear model from HomebrewedDB, which provide normal
- downsample the TeddyBear to 100 points to obtain the source point cloud
- apply a random transformation (R, t)
- To simulate a partial overlap, we randomly discard a percentage of the transformed point cloud.
- to simulate a 80% overlap, we randomly discard 20% of the transformed points.

:::warning
補充 (overlap)
:::

==result==

### 2D-3D Pose Estimation

==setup==
- image plane: 640*480
- apply 100 collinear 3D points and ensure they are in the field of view of the camera
- We then project the 3D points back to the image plane to have 2D-3D correspondences.
- Bounded random noise
- $\epsilon_i \sim N(0,\sigma^2I)$, $\sigma = 0.1$
- $||\epsilon_i||\leq \beta = 0.25$
- to generate outliers: replacing some of the 2D points with randomly sampled points in the image.

==result==