Line Fitting

Random Sample Consensus

Algorithm

Algorithm Random Sample Consensus (RANSAC)

1. Sample (randomly) the minimum number of points required to fit the model ( in case of line fitting).
2. Solve for model parameters.
3. Score by the fraction of inliers within a preset threshold.
4. Repeat until the best model is found.

The number of repetition is determined by equation of probability: where is the probability that a point is an outlier, is the number of points in a sample and is the desired probability that we get a good sample.

Remark

Pros:

• Robust to outliers.
• Applicable for large number of parameters.

Cons:

• Computational time grows quickly with the fraction of outliers and the number of parameters.
• Not good for getting multiple line fits.
• Can rapidly find a good model, not necessarily a great model.

Common Applications: Computing a rotation and translation between two images (will be used later for fundamental matrix in 2-view geometry).

Hough Transform

Definition

Def Hough Transform Let be the image space, be the parameter space of the shapes we’re looking for. Let be the accumulator space, where each element represents a cell in the parameter space. Suppose . Define a voting function that takes a data point and a parameter vector in . The Hough Transform for a set of data points is defined as the following integral over the parameter space :

Remark

The voting function typically outputs if is consistent with the shape defined by , and otherwise. The integral essentially sums the votes for each cell (parameter vector) in the accumulator space . Cells with high values in correspond to parameters that likely describe shapes present in the data points .

Algorithm

Algorithm Hough Transform: Accumulator

Algorithm

Algorithm Hough Transform: Polar Form Use a polar representation for the parameter space: Then A point is mapped to a sinusoid in the polar parameter space

Remark

Hough Transform: Pros and Cons Pros:

• All points processed independently, so can cope with occlusion
• Some robustness to noise: noisy points are unlikely to contribute consistently to any single bin
• Can detect multiple instances of line/circle/ellipse in a single pass

Cons:

• Complexity of search time increases exponentially with the number of model parameters.
• Non-target shapes can produce spurious peaks in parameter space.
• Quantization: hard to pick a grid size