Re: [CAD_CAM_EDM_DRO] digitized point smoothing algorithm

> I realize this is a big general question, but I have seen bigger
> ones on this forum, and I thought I would ask and see what happens.
> It seems like Chris Stratton, the instrument maker might be able to
> help, if I am able to follow his explanation with my limited mental
> faculties.

Oh no, what have I gotten myself into?

Curve fitting is tricky, and I'm not very good at it.

But basically, it can work like this:

1) Guess a general form of an equation that might fit your data. It
used to be important to do this 'right' however with todays' computers
we can take advantage of the fact that higher math shows that anything
can be approximated (often inefficiently) as a polynomial, like

y = Ax^4 + Bx^3 + Cx^2 + Dx^1 +E

This is a 4th-degree polynomial as the highest power of X is the 4th,
and many shapes may require higher degree ones, but the basic idea is
the same. What the computer does for us is find values of the
coefficients A, B, C, D, E, etc

2) Define a test that will tell us how well the curve with certain
proposed values of the coefficients A, B, C, etc fits the actual data.
For example, you might at each point calculate the square of the
difference between the measued value and the one given by the trial
equation. The sum of all these squared differences will give you an
idea of how well your curve fits.

3) Now you try a bunch of possibilities for the coefficients and see
which gives you the lowest error. There are no doubt tricks for doing
this wisely, but you can also try to do it by brute force with a
nested approach like this:

For A = -limit to +limit
For B = -limit to +limit
For C = -limit to +limit
For D = -limit to +limit
test fit
save values if it is lowest error yet seen
next D
next C
next B
next A

Beware this kind of search can get very big for a polynomial of large
degree!

------------

Microsoft Excell has, either natively or with certain add-ons, a
tool for minimizing the value of a cell by changing values of other
cells. You can set up a spreadsheet with your measured data,
calculated approximation (use some other cells to store the
coefficients), squared error, and finally its sum. Tell the optimizer
to minimize the value of the error sum cell by varying the values of
the coefficient cells.. Graph the results and see how you like them.

I've sometimes multiplied the error in each cell by a scale factor,
and manually adjusted those factors to make certain points (like the
end points of the curve) more important so they come out exactly,
while others are less exact.

Some packages including matlab, the free gnuplot, etc have built in
curve fitting. (finding the more recent versions of gnuplot can be
tricky - I can't remember if I finally used it under windows or
linux).

Smoothing data is a different but related issue... You could do
things like replace each point with the average of itself, the
previous, and next points. Depending on what your data is doing,
there are kind of weighted averages you might employ such as the
geometric mean (square the values, sum, divide by 3, and square root).

You can also simply edit out or adjust bad data by hand if your points
are limited in number.

One risk in polynomial approximations is that they can oscillate a bit
rather than give smooth curves. So far I've been lucky, but I'm
generally fitting fairly simple shapes (diameter vs length for tapered
and ultimately flared french horn parts).

You can test for oscillation by repeatedly taking the derivative and
looking for zero crossings in it. Taking the derivative of a
polynomial is simple: write each term as A x^n and replace it with nA
x^(n-1). You'll end up with one fewer term than you started with, as
n is zero for the constant term.

I'm sure others will have things to say, and hope I'll learn something
from their comments.

Chris

--
Christopher C. Stratton, stratton@...
Instrument Maker, Horn Player & Engineer
22 Adrian Street, Somerville, MA 02143
http://www.mdc.net/~stratton
NEW PHONE NUMBER: (617) 628-1062 home, 253-2606 MIT