Saturday, September 26, 2009

The illusive ellipse

Well, it took me a while, but I finally got my ellipse fitting code working. And I couldn't have done it without Google. I've no idea anymore how research could have been done before the advent of the Internet and more importantly search engines. You'll see what I mean as I explain the picture. The pic contains two ellipses. The first, the one in white is the reference, or known, ellipse. In other words, I specified its quadratic equation and am just drawing it. Then, I also randomly pick points on the ellipse and use those to sample the original ellipse and then to fit a new ellipse to these points. The fit ellipse is shown in green. The sampled points show up in yellow. The reason the points are not on the ellipse is because they get shifted and scaled by the algorithm used to fit an equation to the points. The ellipse fitting code is due to Fitzgibbon, Pilu, and Fisher and a few other authors, particularly Halír and Flusser, and this superb WSCG '98 paper. I had most of the math coded up but what held me up was calculation of the generalized eigensystem. I had code to calculate eigenvectors before, but that was for symmetric matrices. In the current situation, the key matrix for which I needed its eigenvectors was not symmetrical. It took me about a week's worth of looking at everything but that one line of code to finally come around to thinking that it had to be this one routine that I've been using for years that could be messing up. Eventually, I came across the Template Numerical Toolkit that has freely available C++ code to calculate the eigenvectors that I needed. Once I plugged this in, everything worked. And as an added bonus, I came across this paper on A Fast Bresenham Type Algorithm for Drawing Ellipses that uses integer math to draw ellipses. I've known (and had written code for) Bresenham circles and lines, but I'd never written up the ellipse drawing code. It was really rewarding to get everything running finally, and I think the Internet made getting this done relatively quickly. I mean, how did people do this before? Via hand-written letters? Faxes?