[Tfug] Smoothing curves

[Rich]

On Dec 1, 2008, at 7:32 am, Bexley Hall wrote:

> Ideally, such a filter would be configurable -- to
> allow its effect to be tailored to the environment
> (i.e., user + input device) without impacting the
> recognizer itself.


> In canvasing the literature, it seems that many
> recognizers use such a feature.  But, their design
> seems to be somewhat ad hoc/arbitrary -- there
> is no *reasoned* explanation for why a particular
> implementation is chosen over some other (better?)
> implmentation.  Indeed, even the coefficients used
> in these filters seem somewhat arbitrary!  It's as
> if the implementers just "tried something" and
> didn't even prove to themselves that their particular
> approach had merit -- let alone being ideal!  :<

So you're saying there's no research to back up these proprietary  
solutions. To state the obvious, maybe you should look for research  
papers on the subject.

This is a trivial motion capture problem. There should be something  
in Siggraph or the ACM Transactions on Graphics.

Another area to research would be digital image stabilizing. Drop the  
inputs -- the feature recognition part -- and plunder the raw  
smoothing algorithm.

> Some, for example, simply "average" each point's
> coordinates with its immediate neighbors.  I.e.,
>   X = (Xi-1 + Xi + Xi+1) / 3
>   Y = (Yi-1 + Yi + Yi+1) / 3
That seems reasonable for testing. I'd have this as a control in my  
research.

> Others claim to be trying to fit a Gaussian to each
> by adjusting the weights of neighbors accordingly:
>   X = (Xi-1)/5 + 3*(Xi)/5 + (Xi+1)/5
>   X = (Yi-1)/5 + 3*(Yi)/5 + (Yi+1)/5
> This latter approach, of course, ignores pesky little
> details like the role of "sigma", etc.
Evidently they've seen the other implementation and decided to  
"improve" on it, without knowing why.

> Almost universally, each approaches applies the
> filter in the time domain instead of in space.
Hm.

> I.e.,
> Pi-1 and P are separated by a fixed amount of *time*
> as are Pi and Pi+1, etc.  I haven't been able to
> convince myself that this is correct or incorrect.
> <frown>  But, neither have the implementers!
You're talking about real-time data. Temporal smoothing is the  
simplest implementation. But for truly accurate data, you'd do  
spatial smoothing.

> An alternative (more rational?) approach is to apply
> the filter in *space* -- so that points *farther*
> away have considerably less influence on the given
> point regardless of their proximity in time.  E.g.,
> if Pi+1 is "quite far" from Pi, then it's weight on
> the average should NOT be the same as that of Pi-1
> (which may have been physically *closer*) despite
> the fact that each is separated in *time* from Pi
> by the exact same interval.
>
I'd go for something between the two. With lots of input data, it  
would be purely spatial, but as input slowed down, I'd start aborting  
the data logger for each spatial group.

For the spatial algorithm, I'd look at fitting a bezier curve to  
averaged control points. Maybe a cubic curve. But we're talking about  
lots of calculation to find control points that lie off the actual path.

> Lastly, does treating each coordinate independantly
> of the other really make sense?  Or, should any
> filter model the location (in 2-space) of those
> other points in their impact on the point in question?
To fit mathematical curves to the data, you should consider all  
dimensions at once. You're looking for vectors, and they're two  
dimensional.

> Having independant controls for each axis is a big
> win for many devices.  For example, the horizontal
> characteristics of pen-on-tablet motions are very
> different from the vertical ones.  And, their
> effects *swap* when applied to things like mice...
>
> But, it seems (intuitively) like this process should
> be modeled as a "flexible stylus" moving through a
> "viscous fluid".  I.e., the stylus' stiffness and
> liquid's viscosity are the parameters being tweeked
> to affect the path that the *tip* of the stylus
> actually takes.  [But, I have *no* experience with
> the behaviour of fluids so I can't draw on anything
> besides intuition to clarify that to myself  :< ]

That seems to be an excessive solution -- modelling something  
computationally *very* expensive to achieve a desired result which  
would really be a simple mathematical curve.

*Every* solution you come up with could be represented by a  
mathematical function -- you just have to find the right one.

Have fun!

Rich.


> <shrug>
>
> I'll keep poking around to see if I can find anything
> in other application domains that might have parallels
> with this.  (sigh)  Nothing's ever easy!  :>
>
> While I don't expect a "solution" here, I would
> appreciate any suggestions as to other directions
> that I could explore.
>
> Thanks!
> --don
>
>
>
>
> _______________________________________________
> Tucson Free Unix Group - tfug at tfug.org
> Subscription Options:
> http://www.tfug.org/mailman/listinfo/tfug_tfug.org