I'm writing some robot vision stuff in Ruby
(http://www.ruby-lang.org/). I have this image
(http://canning.homeip.net/Public/Bounties) and I want, somehow, to
turn it into a list of ellipses.

I have these leads:
- http://www.math.temple.edu/~renault/ellipses.html
 - the relevant maths
- http://www.chrisashworth.org/classes/comp290-089/code/hw2/fit_ellipse.m
 - what looks like a matlab function that might do the job

* Excellent links (better than those I've already included, at my sole
discretion, obviously), but no code will earn three stars;
* Code in Ruby, Python or Perl that provides the best fit ellipse
given a 2D list of points will earn five stars;
* Code in Ruby, Python or Perl that provides the best fit ellipse,
including start and end points of each ellipse, given a 2D list of
points will earn five stars and a $10 bonus;
* Code in Ruby, Python or Perl that provides the best fit ellipse,
including start and end points of each ellipse, given just the images
will earn five stars and a $30 bonus;
* Good unit tests for the code will earn a $10 bonus (on top of other bonuses);
* A link to an open source package that will solve this problem
another way (without me having to do too much work) will earn five
stars (but no bonus).

Any code can use open source libraries or modules, and you get credit
above as if you had written them.

If any of this is unclear, let me know.

... and I'm expecting that the list of ellipses detected in my image
will include several for each discontinuous edge (after my processing,
many of the edges are broken into short segments) - I expect to have
to clean up the list later, removing those that look like duplicates.

---

Clarification of Question by matthewfallshaw-ga on 20 Nov 2005 22:21 PST

I'm still interested in a solution to this problem. OpenCV (see
comments) looks interesting - is anyone willing to have a punt at
using it?

The Matlab code and the other link your posted describe a method to
map MANY points to ONE ellipse. As far as I see your image, you want
to map MANY points to MANY ellipses. Is that correct ?
A standard method to solve this problem is the Hough Transformation.
However, as arbritary ellipses take a 5-parameter-space, the naive
implementation takes a lot of memory (I am talking about GBs). And it
will be very slow (using Ruby or Python does not help either). There
are recent papers about how to improve it, but I haven't found a
publically available implementation.
OpenCV (http://www.intel.com/technology/computing/opencv/index.htm),
the leading open-source Computer Vision library, has code for fitting
points to a single ellipse. At least with Linux it can be used
together with Ruby or Python using SWIG; I have no clue about Windows.

Hmm...

I reckon I can write a (pretty fast) line follower to break the edges
in the processed image into lists of points. This would mean I had a
series of ellipse fitting tasks to perform (I could either create
another small image that just had those points, or provide a list of
2D points).

I'll look into OpenCV, thanks.

One approach which may be useful for you is related to some work I did
in my PhD for fitting an arbitrary collection of lines to an image. I
started off by dividing the screen into relatively small pieces and
assigning a best-fit line to each one, then progressively merging
pieces to form a complete line. The key advantage of this technique
was that we could resolve collections of lines with very many
intersections, by building up the lines on the clearer sections of the
image first (and not requiring those sections to be connected), and
considering the fuzzier boxes only once we'd built up a reasonable
picture of the lines. If this sounds like an interesting approach, I
can go into more detail. I did look at extending it to ellipses, but
didn't really have time to pursue it.

Sure, it sounds interesting.
It sounds interesting even if all you can go into is a discussion of
the algorithm you used (or, is your PhD up on the web?)... but it
sounds even more interesting if you had any of your code.

I've found a few other links I have to look into (from O'Reilly MAKE
magazine, http://www.eyesweb.org/, http://www.puredata.org/,
http://ydegoyon.free.fr/pidip.html), but have been distracted by other
things. Your ideas would be great.

Processing.org - Open source alternative. There is an edge detection
library that should work. (Java).

re: processing.org
Edge detection isn't the problem, it's converting the edge pixel lists
to ellipses. I've had a look at the site, but I don't think it solves
the parts of the problem I'm having trouble with.
Thanks anyway.

re: images
I broke the old link to the images. It's back up here
<http://canning.homeip.net/?q=node/3>.

Hi matthewfallshaw,
Sorry, haven't had a chance to get to GA for a while and hadn't seen
that you'd expressed an interest in my research... I do have Borland
Pascal code lying around for it. The algorithms themselves are not
that complicated, so it might be better just to go through them and
let you code them up in Ruby from scratch, but I don't mind either
way. I can also email you a copy of the thesis in .dvi or .ps format
if you want it. Feel free to contact me at scarletmanuka at
iprimus-com-au (I'm sure you can figure out the appropriate
conversions here).