Metric for ellipse fitting in OpenCV

3
votes

OpenCV has a nice in-built ellipse-fitting algorithm called fitEllipse(const Mat& points)

However, it has some major shortcomings, limiting its usefulness. For example, it already requires selected points, so I already have to do a feature extraction myself. HoughCircles detects circles on a given image, pity there is no HoughEllipses.

The other major shortcoming, which stands in the center of my question, is that it does no provide any metric about how accurate the fitting was. It returns an ellipse which best fits the given points, even if the shape does not even remotely look like an ellipse. Is there a way to get the estimated error from the algorithm? I would like to use it as a threshold to filter out shapes which are not even close to be considered ellipses.

I asked this, because maybe there is a simple solution before I try to reinvent the wheel and write my very own fitEllipse function.

4
image-processingopencvcomputer-vision
An ellipse has 5 degrees of freedom, so the parameter space for a hough transform would be way too large. If you have few outliers, maybe a RANSAC algorithm would work. – Niki

4 Answers

3
votes

If you don't mind getting your hands dirty, you could actually modify the source code for fitEllipse(). The fitEllipse() function uses least-squares to determine the likely ellipses, and the least-squares solution is a tangible distance metric, which is what you want.

If that is something you're willing to do, it would be a very simple code change. Simply add a float whose value is passed back after the function call, where the float stores the current best least-squares value.

2
votes

fitEllipse gives you the ellipse as a cv::RotatedRect and so you know the angle of rotation of the ellipse, its center and its two axes.

You can compute the sum of the square of the distances between your points and the ellipse, that sum is the metric you are looking for.

The distance between a point and an ellipse is described here http://www.geometrictools.com/Documentation/DistancePointEllipseEllipsoid.pdf and the code is here http://www.geometrictools.com/GTEngine/Include/Mathematics/GteDistPointHyperellipsoid.h

You need to go from OpenCV cv::RotatedRect to Ellipse2 of Geometric Tools Engine and then you can compute the distance.

0
votes

Why don't you do a findContours() to reduce the memory space required? There's your selected points structure right there. If you want to further simplify you can run a ConvexHull() or ApproxPoly() on that. Fit the ellipse to those points, and then I suppose you can check similarity between the two structures to get some kind of estimate. A difference operator between the two Mats would be a (very) rough estimate?

0
votes

Depending on the application, you might be able to use CAMShift (or mean shift), which fits an ellipse to a region with similar colors.