Cfrgtkky

I'm implementing a system that uses a least squares algorithm to fit an ellipse to a set of data points. I've successfully managed to obtain approximate locations for the centre of the ellipse but I am having trouble with the major and minor axes. I'm writing this in C++ using OpenCV so I need to be able to express them as some kind of equation so I can calculate them. Right now I am just testing it with very basic circles rather than what I'll actually be using the program for.

Result of my program, where the top image is the data points (3 contours) and the bottom image is my approximated ellipses. The solid circles are the original image, purple dot is the centre of my approximated ellipse and the green, blue and red curves my approximated ellipses for the contours. The ellipses have not been rotated to the approximated angle yet (I will do this later).

So, is there a way from the general conic

$Ax^2 + Bxy + Cy^2 + Dx + Ey + F = 0$

if I know the values of A,B,C,D,E and F and also the centre point $(x_0,y_0)$

That I can calculate the major and minor axes?

From what I understand. From the equation

${(x-x_0)^2 over a^2} + {(y-y_0)^2 over b^2} = 1$

The major axis is 2a and the minor is 2b.

Note: I do not have points on the ellipse that I can substitute in. In my actual application I am unlikely to have such points.

I came across this question and it helped me implement what I have done thus far
Finding the angle of rotation of an ellipse from its general equation and the other way around

The 1st answer I used for the centre. And the 3rd for the axes/dimensions.

For example. The black circle with the blue 'ellipse' around it. I have

$A = 3.876e-013$
$B = 1.8819e-012$
$C = 1$
$D = -2.51108e-009$
$E = -484$
$F = 54663.6$

And I calculate theta from

${1 over 2} tan^{-1}left({B over A- C}right)$

Which gives me $-9.40948e-013$

I am unsure if I am approaching this in the correct way.

Any help appreciated, cheers :).

If you are looking for the length of the minor and major axis you can calculate $ r_{min} $ and $ r_{max} $ (see formulae below).

If you are trying to determine the bounding box, you can calculate the left-most, right-most, top-most and bottom-most points.

As far as the angle of rotation is concerned, I use the algorithm and formulae below.

Properties of an ellipse from equation for conic sections in general quadratic form

Given the equation for conic sections in general quadratic form: $ a x^2 + b x y + c y^2 + d x + e y + f = 0 $.

The equation represents an ellipse if $ b^2 - 4 a c < 0 $ , or similarly, $ 4 a c - b^2 > 0 $

The coefficient normalizing factor is given by:

$ q = 64 {{f (4 a c - b^2) - a e^2 + b d e - c d^2} over {(4ac - b^2)^2}} $

The distance between center and focal point (either of the two) is given by:

$ s = {1 over 4} sqrt { |q| sqrt { b^2 + (a - c)^2 }} $

The semi-major axis length is given by:

$ r_max = {1 over 8} sqrt { 2 |q| {sqrt{b^2 + (a - c)^2} - 2 q (a + c) }} $

The semi-minor axis length is given by:

$ r_min = sqrt {{r_max}^2 - s^2} $

The center of the ellipse is given by:

$ x_Delta = { b e - 2 c d over 4 a c - b^2} $

$ y_Delta = { b d - 2 a e over 4 a c - b^2} $

The top-most point on the ellipse is given by:

$ y_T = y_Delta + {sqrt {(2 b d - 4 a e)^2 + 4(4 a c - b^2)(d^2 - 4 a f)} over {2(4 a c - b^2)}} $

$ x_T = {{-b y_T - d} over {2 a}} $

The bottom-most point on the ellipse is given by:

$ y_B = y_Delta - {sqrt {(2 b d - 4 a e)^2 + 4(4 a c - b^2)(d^2 - 4 a f)} over {2(4 a c - b^2)}} $

$ x_B = {{-b y_B - d} over {2 a}} $

The left-most point on the ellipse is given by:

$ x_L = x_Delta - {sqrt {(2 b e - 4 c d)^2 + 4(4 a c - b^2)(e^2 - 4 c f)} over {2(4 a c - b^2)}} $

$ y_L = {{-b x_L - e} over {2 c}} $

The right-most point on the ellipse is given by:

$ x_R = x_Delta + {sqrt {(2 b e - 4 c d)^2 + 4(4 a c - b^2)(e^2 - 4 c f)} over {2(4 a c - b^2)}} $

$ y_R = {{-b x_R - e} over {2 c}} $

The angle between x-axis and major axis is given by:

if $ (q a - q c = 0) $ and $ (q b = 0) $ then $ theta = 0 $

if $ (q a - q c = 0) $ and $ (q b > 0) $ then $ theta = {1 over 4} pi $

if $ (q a - q c = 0) $ and $ (q b < 0) $ then $ theta = {3 over 4} pi $

if $ (q a - q c > 0) $ and $ (q b >= 0) $ then $ theta = {1 over 2} {atan ({b over {a - c}})} $

if $ (q a - q c > 0) $ and $ (q b < 0) $ then $ theta = {1 over 2} {atan ({b over {a - c}})} + {pi} $

if $ (q a - q c < 0) $ then $ theta = {1 over 2} {atan ({b over {a - c}})} + {1 over 2}{pi} $

For convenience, I'll use the form with double terms,

$$Ax^2+2Bxy+Cy^2+2Dx+2Ey+F=0.$$

First you need to center the ellipse with

$$A(x-x_c)^2+2B(x-x_c)(y-y_c)+C(y-y_c)^2+2D(x-x_c)+2E(y-y_c)+F=0.$$

The center is found by canceling the linear terms, wich gives

$$Ax_c+By_c=D,\Bx_c+Cy_c=E.$$

The equation then reduces to

$$Ax^2+2Bxy+Cy^2=Ax_c^2+2Bx_cy_c+Cy_c^2-F=G.$$

In polar coordinates,

$$(Acos^2(t)+2Bcos(t)sin(t)+Csin^2(t))r^2=G.$$

We want to find the extrema of $r$. They are also the extrema of the trigonometric factor and we determine them by cancelling the derivative.

$$-Acos(t)sin(t)+B(cos^2(t)-sin^2(t))+Csin(t)cos(t)=0$$
which we rewrite, by the double angle formulas

$$(C-A)sin(2t)+2Bcos(2t)=0$$

which gives

$$tan(2t)=frac{2B}{A-C}.$$

The solution is $$t=frac12arctanleft(frac{2B}{A-C}right)+kfracpi2,$$

(giving the directions of the axis, which are orthogonal), and the semi-axis lengths are

$$r=sqrt{frac G{Acos^2(t)+2Bcos(t)sin(t)+Csin^2(t)}}.$$

One can notice that the ellipse parameters are directly related to the Eigenvalues and Eigenvectors of the matrix

$$left(begin{matrix}A&B\B&Cend{matrix}right).$$

After diagonalization of the matrix, the equation of the ellipse becomes

$$lambda x^2+mu y^2=G,$$ which is of the well-known form

$$left(frac x{sqrt{frac Glambda}}right)^2+left(frac y{sqrt{frac Gmu}}right)^2=1.$$