hough ellipse fit inaccurate?

[Arno Dietz]

Hello,

I'm working on a project where I need to test various methods to fit ellipses as accurate as possible. The hough ellipse fit from scikit-image for my images with perfect Ellipses is quite inaccurate as you can see in the examples.

The white ellipse is my edge image. The red are the fitted ones.

 

Why is there always a offset although my source image has perfect ellipses? I tried to vary the parameters but without success.
Thank you so far.best regardsArno

[Stéfan van der Walt]

Hi Arno

On Wed, Mar 4, 2015 at 2:44 PM, Arno Dietz <arnod...@googlemail.com> wrote:

I'm working on a project where I need to test various methods to fit ellipses as accurate as possible. The hough ellipse fit from scikit-image for my images with perfect Ellipses is quite inaccurate as you can see in the examples.

The white ellipse is my edge image. The red are the fitted ones.

Please provide us with a minimal code snippet, then we can see where the problem is.

Thanks

Stéfan

[Arno Dietz]

 Ok sorry. Here is my code:

from skimage import color
from skimage.filter import canny
from skimage.transform import hough_ellipse
from skimage.draw import ellipse_perimeter
from skimage import io
from skimage.viewer import ImageViewer
# load image
img = io.imread('ellipse.png')
cimg = color.gray2rgb(img)
# edges and ellipse fit
edges = canny(img, sigma=0.1, low_threshold=0.55, high_threshold=0.8)
result = hough_ellipse(edges, accuracy=4, threshold=25, min_size=47, max_size=60)
result.sort(order='accumulator')
# Estimated parameters for the ellipse
best = result[-1]
yc = int(best[1])
xc = int(best[2])
a = int(best[3])
b = int(best[4])
orientation = best[5]
# Draw the ellipse on the original image
cy, cx = ellipse_perimeter(yc, xc, a, b, orientation)
cimg[cy, cx] = (0, 0, 255)
# Draw the edge (white) and the resulting ellipse (red)
edges = color.gray2rgb(edges)
edges[cy, cx] = (250, 0, 0)
viewer = ImageViewer(edges)
viewer.show()

I noticed, that the ellipse center is detected only in half pixel accuracy. Maybe this is the Problem? Is there a possibility to get the ellipse center with sub-pixel accuracy?

regards Arno 

[Kevin Keraudren]

Hi Arno,

The first source of inaccuracy comes from your code, you need to round the values instead of truncating them:

#yc = int(best[1])                                                              

#xc = int(best[2])                                                              

#a = int(best[3])                                                               

#b = int(best[4])                                                               

yc = int(round(best[1]))

xc = int(round(best[2]))

a = int(round(best[3]))

b = int(round(best[4]))

See resulting image attached.

Kind regards,

Kevin

--
You received this message because you are subscribed to the Google Groups "scikit-image" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scikit-image...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Kevin Keraudren]

A second source of inaccuracy comes from your input ellipse: it is not a perfect ellipse because you drew it using anti-aliasing.

[Johannes Schoenberger]

Third, you could fit an ellipse using RANSAC. How does this approach work for you: http://stackoverflow.com/questions/28281742/fitting-a-circle-to-a-binary-image/28289147#28289147

[Arno Dietz]

Thank you very much Kevin and Johannes.

I see the rounding Problem, but it is just for the ellipse drawing. In my actual code I just use the Ellipse center like best [1] and best[2] without rounding. This still produces much more inaccurate ellipse center results than other methods like center of mass for example, although I also use the anti-aliased input image. So is there any possibility to get more accurate results from the hough ellipse fit approach? If not, this is also ok, I just want to be on the safe side that it's not my fault. In that case I will have a look at the suggested approach from Johannes.

Am Donnerstag, 5. März 2015 01:21:48 UTC+1 schrieb Kevin Keraudren:

Hi Arno,

The first source of inaccuracy comes from your code, you need to round the values instead of truncating them:

#yc = int(best[1])                                                              

#xc = int(best[2])                                                              

#a = int(best[3])                                                               

#b = int(best[4])                                                               

yc = int(round(best[1]))

xc = int(round(best[2]))

a = int(round(best[3]))

b = int(round(best[4]))

See resulting image attached.

Kind regards,

Kevin

A second source of inaccuracy comes from your input ellipse: it is not a perfect ellipse because you drew it using anti-aliasing. 

 

Third, you could fit an ellipse using RANSAC. How does this approach work for you: http://stackoverflow.com/questions/28281742/fitting-a-circle-to-a-binary-image/28289147#28289147  

[Kevin Keraudren]

Hi Arno,

In order to stay on the safe side, why don't you post your actual code, with a test case highlighting the error you measure between the true centre of the ellipse and the detected one?

Kind regards,

Kevin

--

[Kevin Keraudren]

By the way, your ground truth is the values you used when drawing the ellipse, not the values you detect with a different detection method.

[Arno Dietz]

Ok sorry, maybe I need to explain my project better.

I have a Autodesk Maya Model of a simplified eyeball with the pupil (see image). I render the images of the eyeball from different angles and try to detect the pupil center as accurate as possible. Since I know the geometry and rotation of the eyeball, I can calculate the mapping of the real center of the pupil on my virtual maya camera sensor. I proved the validity of my calculation with several other methods of ellipse center detection (center of mass, distance transform, opencv ellipse fit, starbust) where I get errors between my calculation and measurement with sometimes less than 0.02 pixels.

But nevertheless I want to try the hough ellipse approach, because it may be more robust against noise or other errors I want to simulate later. And it seems so far only the hough ellipse approach is quite inaccurate so I was wondering why. I think the reason could be the ellipse center detection has only a half pixel accuracy while my other approaches have sub-pixel accuracy.

I think posting the calculation code would be too much, but I am quite sure the calculation is right.

Kind regards

Arno

[Kevin Keraudren]

Hi Arno,

Looking at the code, I would ask: Did your score improve by setting accuracy=1 ?

https://github.com/scikit-image/scikit-image/blob/master/skimage/transform/_hough_transform.pyx

Considering that you are asking for accuracy below half a pixel, I would not be surprised if the voting process of the Hough transform is not that accurate. A least-square fitting (Opencv fitellipse) might be more accurate than a voting process for a perfect ellipse.

Aren't the eyeball and the pupil both balls? If you slice them in any way, wouldn't you obtain disks? So why detecting elllipses and not circles? Maybe hough_circle will be more accurate.

Sorry I cannot provide any proof or certitude on how accurate hough_ellipse is.

Kind regards,

Kevin

[Johannes Schoenberger]

Well, there is not reason to use `fit ellipse` from OpenCV, you can use `skimage.measure.EllipseModel`.

[Arno Dietz]

Hi Kevin and Johannes,

no the accuracy parameter has no effect on my measure accuracy.

Yes I tried opencv fitellipse and it is much more accurate. But I want to test several methods and I heard that the hough transform is quite robust.

The eyeball is a sphere and the Pupil a flat circle on the flat white plane. Since I view the circle from different angles it always appears as a ellipse. So circle detection is not an option.

Ok Thank you..it seams the skimage hough ellipse fit just isn't that accurate. 

@Johannes: I tried the EllipseModel with ransac from your link today and I like it very much.

But I have some problems with greater angles. I always have a set of 25 images where the eye is looking at different targets on a display. I plot the difference between the true center and the measured center in one error diagram (see images).

When the camera is located directly in front of the eye, so the angles are not to big, it works fine with low errors (see image 1).

But when I move the camera down so that the pupil appear more elliptical I always get some outliers with bigger errors like Point 2, 7, 12, etc. (see image 2).

I tried to vary the parameters (min_samples, residual_threshold and max_trials) but there are always some outliers, but every time at different images.

Do you have an idea where this comes from? 

Thank you so far.

Kind regards

Arno

[Johannes Schoenberger]

Hi Arno,

So, I just figured, that there was a bug in the most recent addition of RANSAC. The iteration terminated early, even if stop_probability was set to 1.

Should be fixed in https://github.com/scikit-image/scikit-image/pull/1411

You may want to update your local installation with that changeset, and let RANSAC run for a sufficient number of iterations to get reliable estimates.

Best,
Johannes

> --
> You received this message because you are subscribed to the Google Groups "scikit-image" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to scikit-image...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.

> <ellipse_errors1.jpg><ellipse_errors2.jpg>

[Arno Dietz]

Hi Johannes,

thank you for your support. I have just recognized I have installed scikit-image 0.10.1, since I use Anaconda. How can I update scikit-image to 0.11? And how to update the changeset you mentioned?

Can I just replace the files in "..\Anaconda\Lib\site-packages\skimage" ?

Sorry I'm a beginner in programming.

Best regards,

Arno

[Arno Dietz]

Ok I just downloaded the latest version from "https://github.com/scikit-image/scikit-image/zipball/master" and run "pip install .".

Then I changed the files "fit.py", "test_fit.py" and "_geometric.py" from your github link.

Is this correct? It doesn't seem to solve my probleme since I still have some outliers (see Image).

Regards,

Arno

[Johannes Schoenberger]

For how many iterations are you running RANSAC?

> --
> You received this message because you are subscribed to the Google Groups "scikit-image" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to scikit-image...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.

> <ransac_ellipse_outlier.png>

[Johannes Schoenberger]

Another question: Is it still random images for which you see the outliers?

[Arno Dietz]

Do you mean the max_trials parameter? At the moment I use these: "model, inliers = measure.ransac(coords, measure.EllipseModel, min_samples=10, residual_threshold=1, max_trials=100)"

I varied these parameters (min_samples=5 to 40, residual_threshold=0.005 to 10, max_trials=10 to 400) but with no success.

The images with outliers remain the same with equal parameters but with different parameters the outliers appear on different images.

Sometimes there also appear a warning message but in this case it is actually random, when it occurs:

C:\Anaconda\lib\site-packages\scipy\optimize\minpack.py:419: RuntimeWarning: Number of calls to function has reached maxfev = 2600.

warnings.warn(errors[info][0], RuntimeWarning)

Another interesting fact, when I use a starburst algorithm (like this) to detect my points for ellipse fitting instead of the canny edge detector, it seems to work fine mostly without outliers. I think the only difference is, that my starburst algorithm generates much less points (about 300) then canny.

Regards,

Arno

[Johannes Schoenberger]

No, that’s not good. You need 5 points to estimate an ellipse model, and you should stick to the minimum parameters with RANSAC. Otherwise, you have to sample exponentially more to converge to a confident correct solution.

Try something like: min_samples=5, max_trials>200 (depending on the outlier ratio of your edge points this may have to increase significantly), residual_threshold>2 (depending on the spread of your edge points, excluding the outlier points)

Hope this helps, otherwise the only thing that helps would be to share your images and a code snippet.

Best, Johannes

[Arno Dietz]

Okay. But I also tried your parameters without success.

It was hard work but I created a minimal example from my code (see attachment). It takes quite a long time to run but I would be really thankful if you could take a look.

regards,

Arno

[Johannes Schoenberger]

I tried to run this, but I get:

Traceback (most recent call last):
File "ellipse_fit.py", line 41, in <module>
true_coords = pickle.load(file)
ImportError: No module named multiarray

> --
> You received this message because you are subscribed to the Google Groups "scikit-image" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to scikit-image...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.

> <ransac_ellipse_fit.zip>

[Arno Dietz]

Hm I don't know. Do you have the file "true_coords.pickle" in the directory? So I think the simplest way is to post the true coordinates here so you can just copy and paste instead of loading it.

true_coords = np.float32([[116.16552734, 56.91558838],

[119.50671387, 50.36520386],

[120.07568359, 47.97659302],

[118.15393066, 51.35003662],

[113.87670898, 58.54443359],

[115.45068359, 67.83599854],

[121.19805908, 61.79907227],

[122.86755371, 58.47949219],

[122.07769775, 59.83483887],

[117.28759766, 65.25402832],

[118.67297363, 74.89511108],

[123.27319336, 70.87173462],

[124.70935059, 69.62966919],

[122.70861816, 70.76901245],

[116.82958984, 76.34967041],

[118.11944580, 85.86563110],

[124.74987793, 82.02990723],

[127.60803223, 80.19348145],

[125.04113770, 81.24456787],

[120.22363281, 83.61611938],

[122.88574219, 93.01083374],

[128.35363770, 91.51263428],

[129.56744385, 89.71978760],

[126.35644531, 92.14715576],

[120.37841797, 93.98809814]])

[Johannes Schoenberger]

I just looked at it, and it seems like this is caused by canny - you probably want to focus on optimizing that part. (0.4px error is also not that bad)

[Stéfan van der Walt]

It may be a good idea to upsample your image before doing canny,
because edges lie in between pixels, and can only be accurately marked
with enough resolution.

[Johannes Schoenberger]

@Stefan, good idea! I am curious to know whether this solves your problem.

[Arno Dietz]

Hi,

ok it seams reasonable that its caused by canny because with other edge detection method (starburst) the ellipse fit works fine.

Certainly 0.4 px isn't too bad. But my aim is a very high accuracy and the outliers are clearly systematic errors so they should be avoidable.

Upsampling sounds like a good Idea. I tried it like this:

...

img_upsampled = cv2.resize(img, (0, 0), fx=(8.0), fy=(8.0), interpolation = cv2.INTER_CUBIC)

ret, thresh = cv2.threshold(img_upsampled, 20, 255, cv2.THRESH_BINARY_INV)

img = canny(thresh, sigma=3).astype(np.uint8)

img[img > 0] = 255

coords = np.column_stack(np.nonzero(img))

model, inliers = measure.ransac(coords, measure.EllipseModel, min_samples=5, residual_threshold=1, max_trials=200)

cx = model.params[1] / 8.0

cy = model.params[0] / 8.0

But there are still a lot of outliers. The upsampled canny image doesn't look too good (see image).

I also tried without thresholding and with different interpolation methods but without success.

Regards,

Arno

[Stéfan van der Walt]

Hi Arno

On Wed, Mar 11, 2015 at 3:18 AM, Arno Dietz <arnod...@googlemail.com> wrote:
> ok it seams reasonable that its caused by canny because with other edge
> detection method (starburst) the ellipse fit works fine.
> Certainly 0.4 px isn't too bad. But my aim is a very high accuracy and the
> outliers are clearly systematic errors so they should be avoidable.

Do you suspect that there is something wrong with our implementation
of Canny? Or can it be improved? If so, it would be well worth
investigating further!

Stéfan

[Arno Dietz]

Hi Stéfan,

I don't know if I did something wrong. But I think there are not that much possibilities to do something wrong with canny.

I also just realised.. when I use cv2.fitEllipse() with the same canny input, the ellipses are detected very accurate with no outliers. So maybe canny is not the problem?

Regards,

Arno

[xu cheng]

Hi Arno,

Using the image you provided here, I fit the black pupil center using a ellipse estimation algorithm.

The result is 295.3148 along the horizontal direction from left to right 

106.7683 along the vertical direction from the top to down. Since I don't know the exact pupil center for this image, I‘m not sure the result is good or not.

Best wishes!

Xu Cheng

在 2015年3月5日星期四 UTC+8下午7:09:34，Arno Dietz写道：