From: Robert Moniot Subject: Re: Best Fit Plane Newsgroups: sci.math.num-analysis Date: Wed, 13 Jan 1999 20:12:39 GMT Keywords: Fitting best planes to data (Deming's vs Pearson's methods) Brian DeShazer writes: > I am trying to come up with a method to find the equation of the best > fit plane through a 3d cloud of points. I got the following from the > dr. math web site: > > > The perpendicular distance from a point (x[i],y[i],z[i]) from a plane > > A*x+B*y+C*z+D = 0 is given by > > [snip] > Does anyone have any suggestions? Did I start down the right path? > Have I missed something? > > Thanks, > Brian D. The best way to formulate this problem, IMHO, is to use the approach described by Deming[1] (when he was still a statistician). It has the advantage that it treats all directions equally and also allows error bars on each dimension to be included, if you have them. IIRC, if all data points' error bars in all directions are equal, it gives the same result as minimizing the sum of squares of perpendicular distances. The basic idea is to re-cast the problem as an "adjustment" in which you seek adjusted data values that fit the constraint (lying on a plane in this case.) Let the given data be (X_i,Y_i,Z_i) and the adjusted data be (x_i,y_i,z_i) for i=1..N. Then seek values for (x_i,y_i,z_i) as well as A,B,C,D that minimize \sum_i^N (x_i-X_i)^2 + (y_i-Y_i)^2 + (z_i-Z_i)^2 subject to the constraints of A x_i + B y_i + C z_i + D = 0 for i=1..N. I worked this out many years ago for (M-1)-dimensional hyperplanes in M-dimensional space, by generalizing the straight-line fit method of Williamson[2]. This solution is based on lagrange multipliers to include the constraints, and solves analytically for the adjusted data, so they are not included in the system that finally needs to be solved. It ends up requiring an iterative solution of an M+1 x M+1 system (for you, 4x4) of linear equations. It is iterative because the "constants" in the equations actually depend weakly on the unknowns, but it converges quite quickly from a starting point of A=B=C=D=0. If you are interested in this method I can send you a tech report about it. [1] W. Edwards Deming, Statistical Adjustment of Data, Wiley (1943). [2] J. H. Williamson, Least-squares Fitting of a Straight Line, Can. J. Phys. 46, 1845-1846 (1968). -- Bob Moniot Fordham University email: moniot@fordham.edu Fordham College at Lincoln Center URL: http://www.dsm.fordham.edu/~moniot/ New York, NY 10023 phone: (212) 636-6311 ============================================================================== Newsgroups: sci.math.num-analysis Subject: Re: Least Squares Planes/Lines Methodology From: Robert Moniot Date: Fri, 15 Jan 1999 19:00:10 GMT islam writes: > Recently there have been a number of threads in this newsgroup offering > explanations > for methodology of fitting of least squares planes/lines to 3D data. I > am curious, as > I thought the "standard" method for these calculations is simply an > "eigenvalue problem", > with the measure of the goodness of fit being the RMS deviations of the > points from the > plane/line i.e. > > | S[(X-Xo)^2] S[(X-Xo)(Y-Yo)] S[(X-Xo)(Z-Zo)] | > | S[(X-Xo)(Y-Yo)] S[(Y-Yo)^2] S[(Y-Yo)(Z-Zo)] | > | S[(X-Xo)(Z-Zo)] S[(Y-Yo)(Z-Zo)] S[(Z-Zo)^2] | > > Where S is symbol of summation over all points & Xo,Yo,Zo is the > weighted Centre. > > The earliest reference I have is > > Pearson, Karl > On lines & planes of closest fit to systems of points in space > Philosophical Magazine pp 559-572 S. 6. Vol. 2 No. 11 Nov 1901 > > My own notes & code imlimentation are at > > http://www.icnet.uk/bmm/people/suhail/plane.html > > Could someone please say, in summary, if there are different > approaches/methods to > this problem. I assume that, if there are different approaches then they > would give > different RMS values. Best method ? > The method I sketched out in this newsgroup a couple of days ago, based on Deming's formulation of constrained least-squares minimization, is equivalent to Pearson's eigenvalue method if the data points are assumed to have equal a priori uncertainties in all dimensions. In its simplest form, the eigenvalue method has the drawback that the plane it finds is not invariant under changes of scale. Whether this is a problem for you depends on the source of your data. If the data have a natural equal scaling, then all is OK. But if your data are empirical measurements, expressed in some units such as meters or kilograms, then the natural scaling may not be obvious, especially if the units are not the same for each coordinate. The formulation I posted omitted scaling. In general, each measurement (X_i,Y_i,Z_i) can be associated with an uncertainty (\sigma_x_i, \sigma_y_i, \sigma_z_i). Then the sum to be minimized is \sum_i=1^n [(x_i-X_i)/\sigma_x_i]^2 + [(y_i-Y_i)/\sigma_y_i]^2 + [(z_i-Z_i)/\sigma_z_i]^2 (where (x_i,y_i,z_i) are the adjusted points that are constrained to lie on the plane). This gives a scale-invariant solution since the \sigma's are scaled along with the data points. If \sigma_x_i = \sigma_y_i = \sigma_z_i for all i, then they can be omitted entirely. If they are not equal in all directions but do not vary from data point to data point (i.e. \sigma_x_i = \sigma_x for all i, and likewise for y and z), then you can still use the eigenvalue method if you scale the data. Simply divide all the X_i by \sigma_x, Y_i by \sigma_y, and Z_i by \sigma_z before proceeding. I needed to use Deming's formulation since I was fitting a plane to isotopic ratio measurements, which each data point has its own uncertainty in each dimension. Such data cannot be treated properly by Pearson's method. -- Bob Moniot Fordham University email: moniot@fordham.edu Fordham College at Lincoln Center URL: http://www.dsm.fordham.edu/~moniot/ New York, NY 10023 phone: (212) 636-6311 ==============================================================================