OpenCV's fitEllipse() sometimes returns completely wrong ellipses

Question

My goal is to recognize all the shapes present in an image. The idea is:

1. Extract contours
2. Fit each contour with different shapes
3. The correct shape should be the one with area closest to the contour's area.

Example image:

I use fitEllipse() to find the best fit ellipse to the contours, but the result is a bit messy:

The likely-correct ellipses are filled with blue, and the bounding ellipses are yellow. The likely-incorrect contours are filled with green, and the (wrong) bounding ellipses are cyan.

As you can see, the ellipse bounding the triangle in the first row looks pretty good for the best fit. The bounding ellipse of the triangle in the third row doesn't seem to be the best fit, but still acceptable as a criteria for rejecting an incorrect ellipse.

But I can't understand why the remaining triangles have bounding ellipse completely outside their contour. And the worst case is the third triangle in the last row: The ellipse is completely wrong but it happens to have the area close to the contour's area, so the triangle is wrongly recognized as an ellipse.

Do I miss anything? My code:

#include <iostream>
#include <opencv/cv.h>
#include <opencv/highgui.h>

using namespace std;
using namespace cv;

void getEllipses(vector<vector<Point> >& contours, vector<RotatedRect>& ellipses) {
    ellipses.clear();
    Mat img(Size(800,500), CV_8UC3);
    for (unsigned i = 0; i<contours.size(); i++) {
        if (contours[i].size() >= 5) {
            RotatedRect temp = fitEllipse(Mat(contours[i]));
            if (area(temp) <= 1.1 * contourArea(contours[i])) {
                //cout << area(temp) << " < 1.1* " << contourArea(contours[i]) << endl;
                ellipses.push_back(temp);
                drawContours(img, contours, i, Scalar(255,0,0), -1, 8);
                ellipse(img, temp, Scalar(0,255,255), 2, 8);
                imshow("Ellipses", img);
                waitKey();
            } else {
                //cout << "Reject ellipse " << i << endl;
                drawContours(img, contours, i, Scalar(0,255,0), -1, 8);
                ellipse(img, temp, Scalar(255,255,0), 2, 8);
                imshow("Ellipses", img);
                waitKey();
            }
        }
    }
}

int main() {
    Mat img = imread("image.png", CV_8UC1);
    threshold(img, img, 127,255,CV_THRESH_BINARY);
    vector<vector<Point> > contours;
    vector<Vec4i> hierarchy;
    findContours(img, contours, hierarchy, CV_RETR_EXTERNAL, CV_CHAIN_APPROX_SIMPLE);
    vector<RotatedRect> ellipses;
    getEllipses(contours, ellipses);
    return 0;
}

Answer 1

Keep in mind, that fitEllipse is not the computation of a boundingEllipse but a least square optimization that assumes the points to lie on an ellipse.

I can't tell you why it fails on the 3 triangles in the last row so badly but "works" on the triangle one line above, but one thing I've seen is, that all 3 triangles in the last row were fitted to a rotatedRect with angle 0. Probably the least square fitting just failed there.

But I don't know whether there is a bug in the openCV implementation, or wether the algorithm can't handle those cases. This algorithm is used: http://www.bmva.org/bmvc/1995/bmvc-95-050.pdf

My advice is, to only use fitEllipse if you are quite sure that the points really belong to an ellipse. You wont either assume to get reasonable results from fitLine if you have random data points. Other functions you might want to look at are: minAreaRect and minEnclosingCircle

if you use RotatedRect temp = minAreaRect(Mat(contours[i])); instead of fitEllipse you will get an image like this:

maybe you can even use both methods and refuse all ellipses that fail in both versions and accept all that are accepted in both versions, but investigate further in the ones that differ?!?

Answer 2

If you are having problems with cv::fitEllipse(), this post discuss a few methods to minimize those errors that happen when the cv::RotatedRect is draw directly without any further tests. Turns out cv::fitEllipse() is not perfect and can have issues as noted in the question.

Now, it's not entirely clear what the constraints of the project are, but another way to solve this problem is to separate these shapes based on the area of the contours:

This approach is extremely simple yet efficient on this specific case: the area of a circle varies between 1300-1699 and the area of a triangle between 1-1299.

#include "opencv2/highgui/highgui.hpp"
#include "opencv2/imgproc/imgproc.hpp"
#include <iostream>

int main()
{
    cv::Mat img = cv::imread("input.png");
    if (img.empty())
    {
        std::cout << "!!! Failed to open image" << std::endl;
        return -1;
    }

    /* Convert to grayscale */

    cv::Mat gray;
    cv::cvtColor(img, gray, cv::COLOR_BGR2GRAY);

    /* Convert to binary */

    cv::Mat thres;
    cv::threshold(gray, thres, 127, 255, cv::THRESH_BINARY);

    /* Find contours */

    std::vector<std::vector<cv::Point> > contours;
    cv::findContours(thres, contours, cv::RETR_LIST, cv::CHAIN_APPROX_SIMPLE);

    int circles = 0;
    int triangles = 0;
    for (size_t i = 0; i < contours.size(); i++)
    {
        // Draw a contour based on the size of its area:
        //  - Area > 0 and < 1300 means it's a triangle;
        //  - Area >= 1300 and < 1700 means it's a circle;

        double area = cv::contourArea(contours[i]);
        if (area > 0 && area < 1300)
        {
            std::cout << "* Triangle #" << ++triangles << " area: " << area << std::endl;
            cv::drawContours(img, contours, i, cv::Scalar(0, 255, 0), -1, 8); // filled (green)
            cv::drawContours(img, contours, i, cv::Scalar(0, 0, 255), 2, 8); // outline (red)
        }
        else if (area >= 1300 && area < 1700)
        {
            std::cout << "* Circle #" << ++circles << " area: " << area << std::endl;
            cv::drawContours(img, contours, i, cv::Scalar(255, 0, 0), -1, 8); // filled (blue)
            cv::drawContours(img, contours, i, cv::Scalar(0, 0, 255), 2, 8); // outline (red)
        }
        else
        {
            std::cout << "* Ignoring area: " << area << std::endl;
            continue;
        }

        cv::imshow("OBJ", img);
        cv::waitKey(0);
    }   

    cv::imwrite("output.png", img);
    return 0;
}

You can invoke other functions to draw more precise outline (borders) of the shapes.

Answer 3

Changing cv::CHAIN_APPROX_SIMPLE to cv::CHAIN_APPROX_NONE in the call to cv::findContours() gives me much more reasonable results.

It makes sense that we would get a better ellipse approximation with more points included in the contour but I am still not sure why the results are so off with the simple chain approximation. See opencv docs for explanation of the difference

It appears that when using cv::CHAIN_APPROX_SIMPLE, the relatively horizontal edges of the triangles are almost completely removed from the contour.

As to your classification of best fit, as others have pointed out, using only the area will give you the results you observe as positioning is not taken into account at all.

Answer 4

It may be a better idea to get a pixel-by-pixel comparison i.e. what percentage is the overlap between the contour and the "fitted" ellipse.

Another, simpler idea is to also compare the centroids of the contour and its ellipse fit.