cv::fitEllipse sometimes completely fails

[zvrba]

Please state the information for your system

• OpenCV version: 3.x (3.1)
• Host OS: Linux (Arch Linux)

In which part of the OpenCV library you got the issue?

The function cv::fitEllipse sometimes completely fails, returning bogus fit.

Additional description

A fit is returned which is concave against the dataset. To reproduce, please clone the following repository: https://github.com/zvrba/ellipse_fitting; it is a netbeans project and you may need to adjust makefiles to link it on platforms other than Arch. You will also need to install Eigen matrix library v3.2 to compile it.

The program contains a hard-coded dataset which demonstrates the failure nicely; run it with ellipsefitting FAIL 1. The fit produced by my implementation of paper [1] is displayed with thick line; the fit produced by OpenCV is displayed with thin line. The dataset are small circles. As you can see from the image, the OpenCV fitting has completely failed.

[1] http://autotrace.sourceforge.net/WSCG98.pdf

Note: the program compares the two fitting procedures. If you replace FAIL with some number, it will generate that many random points with added gaussian noise with sigma=1 (the 2nd parameter) and plot the results.

[arrybn]

I created test for this issue in this PR: #6915

[arrybn]

Current status is next:
There are 2 bugs for fitEllipse(): this and #4515. Both bugs contain set of points which leads to fitEllipse() fail.
Author of #4515 suggests relatively small changes but his fixes don't correct this bug. Moreover, I have not found articles or any explanations for current implementation of fitEllipse(). Documentation points to article in which some different algorithm is described.
In this bug author suggests total change of fitEllipse() algorithm.
I've added 2 tests for both issues.