LabVIEW

cancel
Showing results for 
Search instead for 
Did you mean: 

Fitting on a Sphere

chilly charly, et al.:

It seems the image of my last post regarding Fitting on a Sphere is not viewable from this discussion forum.  I apologize for this and urge interested poeple to view it from its URL source:

ftp://sjpublicaccess.mybpip.net/least_sqaure_min_sphere1.bmp

Jordan

 

 

 

0 Kudos
Message 11 of 18
(1,854 Views)

As I wrote in your other post, I have underestimated the difficulty. I bumped into the same dead corner, although your equations can be further developped into
Sigma(fi) = Sigma(fi.xi) = Sigma(fi.yi)= Sigma(fi.zi)= 0

If Altenbach doesn't come back with an answer before, I'll try to spend some more time on this during the we.

Chilly Charly    (aka CC)

         E-List Master - Kudos glutton - Press the yellow button on the left...
        
0 Kudos
Message 12 of 18
(1,848 Views)


@chilly charly wrote:
If Altenbach doesn't come back with an answer before, I'll try to spend some more time on this during the we...

Well, let's not overcomplicate things and instead solve the 2D equivalent of fitting a circle in a plane. Almost the same thing, but easier on the ink ;).

A good explanation is given  in  the maple article by Thomas Schramm (Fitting a Circle to a Number of Points, free registration required), but a quick Google search will probably show others.

Expanding it to three (or more) dimensions seems trivial. 🙂

Message Edited by altenbach on 11-04-2005 11:05 AM

0 Kudos
Message 13 of 18
(1,831 Views)
In a nutshell (for the 2D circle case), you set up a set of linear equations, one for each of the n data points (x,y):
 
x(1)^2 + y(1)^2 -2ax(1) -2by(1) -c =0
x(2)^2 + y(2)^2 -2ax(2) -2by(2) -c =0
x(3)^2 + y(3)^2 -2ax(3) -2by(3) -c =0
x(4)^2 + y(4)^2 -2ax(4) -2by(4) -c =0
...
x(n)^2 + y(n)^2 -2ax(n) -2by(n) -c =0
 
 
and solve for a, b, and c: A simple linear system!
 
The midpoint will be at (a, b) and the radius is r=sqrt(c+a^2+b^2).
0 Kudos
Message 14 of 18
(1,823 Views)
I just remembered that I made a simple circle fit demo way back in the last century (using the fitting on a sphere.vi). Here's a LabVIEW 5.1 version.
Still seems to work OK :).
 
 
Enjoy! 😄
 

Message Edited by altenbach on 11-04-2005 12:04 PM

Download All
0 Kudos
Message 15 of 18
(1,821 Views)
Altenbach , et al.:
 
Thank you for Thomas Schramm's reference and your "nutshell" explanation of it.  I think his approach begins to shed light on my original question:
 
Can someone please explain the algorithm used by the "Fitting on a Sphere" VI located in Optimization?
 
Schramm's approach to the circle fitting may be summarized as taking the partial derivative of the-general-equation-of-a-circle with respect to the parameters and setting each of the resulting linear equations equal to zero.  In matrix notation, the resulting system of simultaneous linear equations is:
 
 / sum(2 xi^2) sum(2 xi yi) sum(xi)   \    /   a   \        /  sum(xi^2+yi^2) xi   \
|                                                          |   |         |       |                                 |
|  sum(2 xi yi) sum(2 yi^2) sum(y_i)  |   |    b    |  =  |   sum((xi^2+yi^2) yi  | 
|                                                          |   |         |       |                                 |
\  sum(2 xi)    sum(2 yi)        N          /    \   c  /        \   sum((xi^2+yi^2)    /
 
Where xi, yi, N, a, b, and c are the x-position and y-positions of the data-points, the total # of data-points, and the least-square-minimized circle parameters: x0, y0, and r^2-x0^2-y0^2, respectively.
 
Jordan
0 Kudos
Message 16 of 18
(1,809 Views)
Altenbach , et al.:
 
The matrix equation in my last post regarding Fitting on a Sphere seems to have lost its formatting upon upload and contains minor errors--my apologies.  The corrected equation may be viewed at:
 
 
It is noted that this equation may be directly solved for a, b, and c using LabVIEW's "Solve Linear Equations" VI.
 
Jordan
0 Kudos
Message 17 of 18
(1,798 Views)

Altenbach, et al.:

Thanks to you and others, I satisfactorily understand the "clever change of variables" that makes LabVIEW's "fitting on a sphere" function possible!  I wrote a version of it in MatLab for my research purposes and have included it below.  You may find some of the references interesting.

I greatly appreciate you and others putting-up with and responding to my questions as I wrested with this one.

Regards,

Jordan


function

params = sphere_fit_linear1(x_i,y_i,z_i)

% function params = sphere_fit_linear1(x_i,y_i,z_i)

%

% This approach to fitting a general equation of a sphere to data is based

% on a clever change of variables that reduces the non-linear least-squares

% problem to a linear one!

% My awareness of this possibility was sparked by not understanding how

% LabVIEW's "fitting on a sphere" function was doing this. Understanding

% developed after (1) "stumbling on" Marc Renault's ("Fitting Circles and

% Ellipses to Data Using the Least-Squares Method",

% http://www.math.temple.edu/~renault/ellipses.html) explaination of I. D.

% Coope's published derivation (Circle Fitting by Linear and Nonlinear

% Least Squares, J Optim Theory Appl, 76 (1993) pp. 381-388) and (2) a

% series of interacations on National Instrument's LabVIEW discussion forum

% (http://forums.ni.com/ni/board?board.id=170), particularly with C.

% Altenbach.

% Jordan Alexander 7 Novemember 2005 Luxel Corporation

a_11 = 2*sum(x_i.^2);

a_12 = 2*sum(y_i*x_i');

a_13 = 2*sum(z_i*x_i');

a_14 = sum(x_i);

a_21 = a_12;

a_22 = 2*sum(y_i.^2);

a_23 = 2*sum(z_i*y_i');

a_24 = sum(y_i);

a_31 = a_13;

a_32 = a_23;

a_33 = 2*sum(z_i.^2);

a_34 = sum(z_i);

a_41 = 2*sum(x_i);

a_42 = 2*sum(y_i);

a_43 = 2*sum(z_i);

a_44 = length(x_i);

b_1 = sum((x_i.^2+y_i.^2+z_i.^2)*x_i');

b_2 = sum((x_i.^2+y_i.^2+z_i.^2)*y_i');

b_3 = sum((x_i.^2+y_i.^2+z_i.^2)*z_i');

b_4 = sum(x_i.^2+y_i.^2+z_i.^2);

A = [a_11 a_12 a_13 a_14;a_21 a_22 a_23 a_24;a_31 a_32 a_33 a_34;a_41 a_42 a_43 a_44];

B = [b_1 b_2 b_3 b_4];

params = A\B';

Message 18 of 18
(1,767 Views)