Shape fitting
When the outlines have been extracted, the geometrical primitives must be extracted from them.
The main ones are:
- Fitting lines
- Fitting circles
- Fitting ellipses
Linear and circular fitting
In both cases, the most commonly used algorithm is minimization, with the least-squares of the distance of the data points from the line or from the circumference.
The calculation can be made with the same weight for each point
Or, the weight can depend on the distance between the points and the calculated line or circumference.
There are many functions to calculate the weights, the main ones being:
- Huber
Where c is a value chosen by the user, d is the distance of the point of the primitive.
- Tukey
normally the value of c is set at twice the standard deviation of the distribution of the distances.
The difference between Huber’s and Tukey’s functions is that in the former, the weights have a unit value for d less than or equal to c, and the function never reaches zero, while in Tukey the weights always have different values for d less than or equal to c, and zero elsewhere.
Sometimes, the RANSAC algorithm is used to build a robust fit.
Elliptical fitting
The most commonly used algorithm is an algebraic method, called the Fitzgibbon method.
The elliptical fitting poses a few problems if the points only belong to certain parts of the ellipse
Examples:
- Correct fit
- Ambiguous fit
The algorithm outcome may be the red ellipse, though the green ellipse is the correct one.