1

I have a problem and I haven´t been able to solve it. The problem is in the area of least-square fitting. Someone drew a sort of "conic" figure on a canvas (i.e. a MATLAB plot) so I have a series of points ($x_i$, $y_i$). Now I need for this points to adjust to a perfect "conic" using least-square fitting.

I now how to do this over a line $f(x) = ax + b$, but I don't know what to do with the general conic equation $Ax^2+Bxy+Cy^2+Dx+Ey+F = 0$

Can someone point me into the right direction.

Some remarks I've been working around:

  • that is an equation, not a function, do i need to parametrize it? how to?
  • Don't know what to do with rectangle term ($Bxy$)

Thanks in advance.

PS: If there was something unclear, please say so and I'll try to explain myself.

PS.1: MATLAB code will be appreciated

Edit:

After checking what @ClaudeLeibovici suggested I got working an example on MATLAB where after getting the points I solve the system of equations given in the french paper and It plotted a perfet circle as I needed (using ezplot with the "explicit equation"), but it does not satisfies Hyperbolas or Parabolas, just circles and elipses. And i need to fit any conic.

Sometimes I get what it looks like to be an hyperbola, sometimes not in the right direction and sometimes not even close to the one I "drew".

Anyhow, I will apreciate if someone could explain me where did the "Generalization for conics" from the paper came from? and what does it means in a least-square sense?

I tried reading it, but couldn't understand it very well, cause I do not speak nor understand french, and the translation wasn't good. I need to understand what is going on cause I need to do a presentation about this.

Thanks in advance

PS: I used $F=1$ as suggested.

DarK_FirefoX
  • 137
  • 8
  • Have a look at https://fr.scribd.com/document/14819165/Regressions-coniques-quadriques-circulaire-spherique The book is by JJacquelin, an MSE user; it is in French but very easy to follow. – Claude Leibovici Mar 18 '17 at 15:07
  • Thanks @ClaudeLeibovici I am taking a look at that! Will tell later if it helped. – DarK_FirefoX Mar 18 '17 at 15:11
  • Look at https://fr.mathworks.com/matlabcentral/fileexchange/32108-fitting-a-conic-to-a-given-set-of-points-using-levenberg-marquardt-method?requestedDomain=www.mathworks.com which seems to be much more advanced than my quick and dirty solution. – Claude Leibovici Mar 18 '17 at 15:24
  • I actually solved the issue using the french article @ClaudeLeibovici suggested. I use the "Generalization for conics" they showed. Thanks everyone for your help. PS: Should I accept an answer or what? Cause the answer was in comment! Not sure what to do! – DarK_FirefoX Mar 20 '17 at 13:26
  • Did you try with $A=1$ ? $F=1$ was a terrible typo. – Claude Leibovici Mar 20 '17 at 18:56
  • @ClaudeLeibovici I actually used $F=1$, cause the french paper used it like that and I got the expected results, I actually was doing something wrong when solving the system of equation. – DarK_FirefoX Mar 21 '17 at 12:40

2 Answers2

1

The basic idea is to minimize $$\Phi=\sum_{i=1}^n (Ax_i^2+Bx_iy_i+Cy_i^2+Dx_i+Ey_i+F)^2$$ Take the derivatives with respect to each parameter and set it equal to $0$.

If you are lazy, define $z_i=0$ for all $i$'s and perform a least square fit for $$z=Ax^2+Bxy+Cy^2+Dx+Ey+F$$ Just a multilinear regression then.

Warning : As JeanMarie commented, set $F=1$ or whatever number you want. This fix to $5$ the number of parameters to be adjusted. And $5$ is the minimum number of points which define a general conic not going through the origin.

Claude Leibovici
  • 260,315
  • Bonjour Claude: the drawback with this solution is that you don't take care of the fact that an equation such as $Ax^2+Bxy+Cy^2+Dx+Ey+F = 0$ is "up to a scaling". You should first "de-homogeneize", for example by arbitrarily taking $F=1$ (in this way, the only conics that are not in the scope are those passing through the origin...). – Jean Marie Mar 18 '17 at 16:44
  • @JeanMarie. For sure ! I am just stupid. Thanks for pointing it. Cheers :-( – Claude Leibovici Mar 18 '17 at 16:54
  • I tried this using $z_i = 0$ for all $i$'s as suggested, but end up having a trivial solution for all coefficients $A = B = C = D = E = 0$ Maybe I did something wrong, I'll try to do it all over again :/ – DarK_FirefoX Mar 19 '17 at 15:24
  • @DarK_FirefoX. Sorry for that :$A=1$ not $F$. I apologize. – Claude Leibovici Mar 19 '17 at 16:22
0

I will assume that this drawing is closed, so that you have a set of points that you want to fit an ellipse to and that these points are approximately equally spaced.

First, get the average $x$ and $y$ values as $x_0$ and $y_0$. This shows the center of the ellipse. Subtract $(x_0, y_0)$ from each point.

Next, do an orientation-independent linear least squares fit to the modified data points. Here is a link to my method of doing this:

linear least squares minimizing distance from points to rays - is it possible?

For each angle $\theta$ in the expression $D=D_1+R\cos(2\theta-\phi)$, where $R$ and $\phi$ are specified in my answer, the value of $D$ is the sum of the squares of the errors of the line at angle $\theta$.

By choosing $\theta$ so $\cos(2\theta-\phi) = -1$ (i.e. $\theta = (\phi+\pi)/2$), the sum is minimized, and by choosing $\theta$ so $\cos(2\theta-\phi) = 1$ (i.e. $\theta = (\phi-\pi)/2$), the sum is maximized.

These values, $D_1 \pm R$, give the square of the values of the major and minor axes of the ellipse, scaled by $\sqrt{2}$ (this is my vague recollection - I did this over thirty years ago).

This method is linear and gives you the center, major axis, minor axis, and orientation of the major axis of the ellipse.

You may have to play around with it to scale and select the length of the axes, but it should work.

marty cohen
  • 107,799