(1) RANSAC

RANSAC (RANdom SAmple Consensus) is a learning technique to estimate parameters of a model by random sampling of observed data.

The RANSAC Algorithm is as follows:

1. Sample the number of points required to fit the model.
2. Solve for model parameters using samples.
3. Score by the fraction of inliers within a preset threshold of the model.

Repeat 1-3 until the best model is found with high confidence.

Let's set the number of points to sample to 2.
Select points $(x1, y1), (x2, y2)$ randomly.
Then you can find model parameters $a$ and $b$ by substituting the sample points $(x1, y1), (x2, y2)$ into the equation $y = ax + b$.

Use the preset threshold to obtain the fraction of inliers:
If the distance between the point and y=ax+b is less than the preset threshold value,
the point is considered as an inlier.

A model with a high percentage of inliers is considered as an optimal model.

How to choose the number of trials S?

How many times do we have to repeat this algorithm?
For the number of sampled points $k$,
outlier ratio $e$,
probability of having one or more outliers in a single subset of samples $1-P$,
S is as follows :

$S = \frac{log(1-P)}{log(1-(1-e)^k)}$

✔ Since inlier ratio is $1-e$ and the number of sampling is $k$,
the probability that the sample subset contains only inliers is $(1-e)^k$.

👍 Good

1. RANSAC is robust to outliers: not heavily influenced by outliers.
2. RANSAC is applicable for larger number of objective function parameters than Hough transform.
3. Optimization parameters are easier to choose than Hough transform.

👎 Bad

1. Computational time grows quickly in proportion to fraction of outliers and the number of parapeters.
2. RANSAC is not good for getting multiple fits.

(2) Hough Transform

If $y_1 = a\times x_1 + b$ is converted to an vector space of a and b, the equation is $b = -x_1\times a + y_1$.
All straight lines that the point $(x_1,y_1)$ is included can be expressed as one straight line, $b = -x_1\times a + y_1$, at the vector space for a and b.

Then what does the intersection of the two straight lines means in the vector space of a and b?
If the intersection of $b = -x_1\times a + y_1$ and $b = -x_2\times a + y_2$ is $(a_1, b_1)$,
the point $(x_1, y_1)$ and $(x_2, y_2)$ will be on the straight line $y = a_1\times x + b_1$.

This means that the more straight lines overlap at the intersection $(a_1,\, b_1)$, the higher the possibility that a straight line $y = a_1\times x + b_1$ exists in the image.

Hough Transform use a polar representation for the parameter space.
Hough space is nearly equal to a-b vector space described above,
but each parameter has a finite range :

$-90<=\theta<=90$ and $0<r<d$ (d: the diagonal length of the bitmap)

There are too many possible $(r,\theta)$ , we just use a few number of quantized $(r,\theta)$. (ex) -45, 0, 45, 90
The accumulator array contains how many times each value of $(r,\theta)$ appears in the table.
The more values appear in $(r_1,\, \theta_1)$, the higher the possibility that a straight line $y = -\frac{cos\theta_1}{sin\theta_1}x+\frac{r_1}{sin\theta_1}$ exists in the image.
The following is the example of table :

If there are spurious peaks due to uniform noise, user needs to adjust grid size larger or smooth the image.

The Hough Transform Algorithm is as follows :

1. Create a grid of parameter values.
2. Each point votes for a set of parameters, incrementing those values in grid.
3. Find maximum or local maxima in grid.

👍 Good

1. Robust to outliers: each point votes separately.
2. Fairly efficient (much faster than trying all sets of parameters).
3. Provides multiple good fits.

👎 Bad

1. Some sensitivity to noise.
2. Bin size trades off between noise tolerance, precision, and speed/memory.
   : Can be hard to find sweet spot
3. Not suitable for more than a few parameters.
   : grid size grows exponentially