Hi! First I would like to say that I did not exactly understand the second paragraph of your question. It would be nice to explain by an example. Nevertheless here is my 2 cents: Fitting ellipse using Hough transform (HT) can be tedious but there are many methods in literature (even recent ones) that find clever parametrization of the ellipse; something like using the value of the eccentricity for the parametric form of ellipse, which reduces the dimensions of the bin in HT. Further, if you have some more fixed constraints like the length of the major or minor axis, or the total area then more efficient parametrization could be achieved and the HT would be very fast. Let me know the exact question more clearly and I will be glad to help you with the mathematics if I find some time :) Have a good day! Aamir

Can we assume that the single object is convex or not?

A quick answer that came to my mind is that you can start from an initial ellipse estimate and then refine it by enlarging it. I suppose that you have tried it, but it is slow. So I propose a bisection-like optimization method where the best fitting ellipse is found by taking two extreme ellipses, a small and a long one, and then test if the ellipse being the average of these two extremes is what you want. If not, continue iteratively by setting the average ellipse and one of the extremes (depending on the constraints you want to satisfy) as the new extremes and repeat the averaging.

Hope that helps.

I am not sure if I understood your question correctly. But binary image is considered as a point set of foreground pixel locations, just by using PCA or SVD you can compute major and Minor axis....This may interest you further javascript:http://www.mathworks.com/matlabcentral/filejavascript:exchange/15125-fitellipse-m/content/demo/html/ellipsedemo.html

Is the object convex?

What do you consider as slow? "Takes an hour", "Takes more than a couple of seconds", "Takes more than 10 ms" ?

If you have binary data, the quickest way is just to estimate the spatial distribution with the covariance matrix. The eigen values will give you the axes directions and amplitude.

This will give you a first rough estimation of the ellipse, which should be tuned a bit to contain all the pixels.

Anyway, this is a rough sketch since we don't really know how your data look like (noisy, not noisy, badly scattered data etc.)

edit: Ah well, I didn't seen the post from Gopal, but is basically the same idea.

If you want a fast ellipse detector, you should try one of these:

L. Libuda, I. Grothues, K.-F. Kraiss, Ellipse detection in digital image

data using geometric features, in: J. Braz, A. Ranchordas, H. Arajo,

J. Jorge (Eds.), Advances in Computer Graphics and Computer Vision,

volume 4 of Communications in Computer and Information Science,

Springer Berlin Heidelberg, 2007, pp. 229-239.

M. Fornaciari, A. Prati, Very Fast Ellipse Detection for Embedded Vision Applications, ICDSC - ACM/IEEE 6th International Conference on Distributed Smart Cameras, Hong Kong, 2012

The code of the first is available on-line (see the paper for the link).

The second is part of my research. I don't know if the paper is already available on-line, since it will be presented today in Hong Kong. The code will be available on-line soon. If you need further information please contact me.

Otherwise, if you are only interested in a least-square fitting method, please consider one of these:

A. Fitzgibbon, M. Pilu, R. Fisher, Direct least square tting of ellipses,

Pattern Analysis and Machine Intelligence, IEEE Transactions on 21

(1999) 476 - 480.

Z.L. Szpak, W. Chojnacki, A. van den Hengel, Guaranteed Ellipse Fitting with the Sampson Distance, ECCV European Conference on Computer Vision, Firenze (I), 2012.

Both implementation are available online.

I hope this will help you.

Try starting from "ELLIPSES INSCRIBED IN PARALLELOGRAMS" , A. Horowitz, AJMAA, Volume 9, Issue 1, Article 6, pp. 1-12, 2012.

You are not reinventing the wheel !!

I think the key idea here is that an ellipse can be enlarged in any way you want just by enlarging it in two orthogonal directions. So I would first try to construct the largest circle that fits within your shape, find the direction that constrains my circle and then enlarge your circle followinf the orthogonal direction with respect to the constrained one. there you go your ellipse.

The problem, as stated, is ill-defined. What do you mean _exactly_ by "largest ellipse"? Largest...

...major axis?

...minor axis?

...sum of axes?

...area?

...perimeter?

...?

The appropriate algorithm will probably be different depending on your metric of choice for the 'size' of the ellipse.

Manuel is right. Give some additional information (and an example image, maybe) and we'll be able to help much more.

Can the ellipse go beyond the border of the image?

highly recommended 'A. Fitzgibbon, M. Pilu, R. Fisher, Direct least square tting of ellipses, Pattern Analysis and Machine Intelligence, IEEE Transactions on 21

(1999) 476 - 480.'. Easy to integrate constraints as the solution is in closed-form. With RANSAC can also be robust to noises.

The Pilu algorithm is good, but it fits an ellipse to a collection of points on the ellipse, which is not what the questioner wants. But here is one approach that might work: first find the boundary points of the original region, and fit an ellipse to them. Some of the boundary points will be inside the fit, so fit another ellipse to just these points. Repeat as needed. This is not going to work as described (imagine an elliptical region with a single bit taken out of it), but maybe a variant could be found that would work, such as including some of the original boundary points with diminished weights. This approach is going to have trouble with pathological cases such as an "X" shaped region, where there are two local maxima...

Here is another approach that would definitely work (but is likely to be slow): do something like a Hough transform. For each boundary point, there is a family of ellipses which are "inside" of it. So you construct a quantized representation of the parameter space, and for each boundary point add "votes" to each bin that satisfies the constraint. Then all the bins that have exactly N votes (N being the number of boundary points used) represent your candidate solutions, and as has already been observed you have to introduce a metric defining what is meant by "largest" in order to choose among them. This would go a lot faster if you could come up with a way to down-select among the boundary points, but that might be difficult given the possibility of local maxima as described above.

In our paper @IROS2011 we used 1D and 2D moments to fit approximate elliptic boundaries to a set of 2D points (Section IV, Steps 4-9).

The idea comes from L. Rocha, L. Velho, and P. C. P. Carvalho, “Image moments-based structuring and tracking of objects,” in Brazilian Symposium on Computer Graphics and Image Processing, 2002.

It seems to work fine and it is also fast.

one of the best solutitions is "Computation of Minimum-Volume Covering Ellipsoids" vy prof sun

Honestly, everyone is giving his own solution with a lot of overlapping ones. instead of getting thing even more messy, the better for you Tim is to give us more detail on your data or even better, post one of the picture you want to process.