1

I have noisy data (from bluetooth indoor positioning system), which I will filter with Kalman filter, but after that I want to fit a curve into it.

The problem that I have is that the data is positioning data, and the object being tracked is making sharp turns and it has quite fast acceleration and deacceleration. Between the turns the object being located usually is using a straight track.

For example fitting a cubic spline does not give me a good approximation since the curve leaves far away from the sharp (angle) turn.

I am quite familiar with Bezier curves and I know that if I put the one control point behind of the sharp turn, then I can squeeze the curve quite close to it. But not close enough. I do not have enough data points for that.

Does anyone have any tips or tricks that I could use?

Note: I am not looking for interpolation. I am looking for an approximation.

  • Do you want a polynomial approximation, or just some way of producing a curve? – Eddy Jan 05 '18 at 21:04
  • Polynomial approximation would really great, but as for starters a some way of producing a curve is fine. –  Jan 05 '18 at 21:46
  • Have a look at https://math.stackexchange.com/questions/1951624/creating-a-parametric-equation-given-n-points-on-a-curve/1951682#1951682 – Claude Leibovici Jan 06 '18 at 10:18

2 Answers2

1

So long as all you desire is a curve, and not a polynomial interpolation in particular, you could try using a weighted average approach. That is, given a set of points and time values $$ (\mathbf{x}_i, t_i) \quad i\in \{1,2,\ldots,n\} $$ We can construct a function $$ \mathbf{x} (t) = \frac{\sum_{i=1} ^n w\left(\frac{|t-t_i|} {\tau}\right)\mathbf{x}_i} {\sum_{i=1} ^n w\left(\frac{|t-t_i|} {\tau}\right) } $$ where $w:\mathbb{R}_0^+\rightarrow(0,1]$ is a monotonically decreasing function determining the weight of each point at a given time instant, and should satisfy $$ w(0) = 1 \\ \lim_{x\rightarrow \infty} w(x) =0 $$ It is likely that we desire the reconstructed function to have a low acceleration (at least, as low as can be to approximate the points). For this we want to minimise $w''$, as such we set $$ w'(0)=0 \\ w''(1)=0 $$ the second equation due to the arbitrary time scale due the rescaling by $\tau$. We wish to minimise (under our constraints) $$ F(w) = \int_0^\infty (w''(x))^2dx $$ Trying to minimise, we take an $\eta(x)$ satisfying $$ \eta(0) = \eta'(0) = 0 \\ \eta(1)=0 \\ \lim_{x\rightarrow\infty} \eta(x) = 0 $$ and take $$ w(x) =q(x) + \epsilon\eta(x) $$ where $q(x)$ is our solution. Thus $$ \lim_{\epsilon\rightarrow0} \frac{F(q(x) + \epsilon\eta(x)) - F(q(x))} {\epsilon} =\frac{1}{\epsilon}\left[\int_0^\infty (q''(x)+\epsilon\eta' '(x) )^2dx - (q''(x) )^2dx\right] = \int_0^\infty 2 q''(x) \eta''(x)dx = 0 $$ I'm not sure how to get a minimum out of this that matches my conditions, I'll post a question of my own. For now a function like $$ w(x) = \frac{3} {x^2+3} $$ or $$ w(x)=\exp\left({\frac{-x^2} {2}} \right) $$ should work.

Eddy
  • 1,139
  • 7
  • 12
  • Very interesting, I also will try to minimise that functional, but it looks kinda tough one for it. –  Jan 06 '18 at 11:23
  • Just noticed that $w''(1)=\frac{1}{2}$, if we use $\frac{1}{x^2 + 1}$ as $w(x)$. –  Jan 06 '18 at 12:10
  • Fixed that problem :) – Eddy Jan 06 '18 at 12:23
  • Eddy, have you have an luck with that functional? –  Jan 10 '18 at 18:20
  • I don't think there is a solution, at least not a useful one. Whatever the curvature for $x<1$, the functional can be made smaller by reducing the curvature there. Repeatedly lowering the curvature the solution tends towards $w=1$. Perhaps a better restriction, as opposed to $w''(1)=0$ would be $\int_0^\infty x^2 w(x) dx = 1$, but I haven't thought about what effect that might have. – Eddy Jan 10 '18 at 18:29
  • No, I don't think that works either... – Eddy Jan 10 '18 at 19:00
1

You could consider a piecewise interpolation scheme where you detect the turning points of the trajectory by some criterion. Then perform curve fitting of your choice (such as linear or Bezier) with the points between turning points, and extend them up to the intersections.

enter image description here

  • The image that you posted is exactly the situation that I am involved in. Only difference is that I get more noise. –  Jan 06 '18 at 14:17
  • @ardevealca: you should question the relevance of a smooth curve with sharp turns vs a piecewise model with angular points. –  Jan 06 '18 at 14:19
  • Yes, I will have to try out your suggestion of the piecewise model. It should be easy to implement. –  Jan 07 '18 at 08:59