Glitch/inconsistency detection in navigation data

Hi folks.

Assume you are given som 20,000 - 100,000 points of raw (x,y,z)
navigation data as previously logged on some platform, and are asked
to clean up the data.

My first, naive idea is to use some Kalman filter. So far so good.

However, the data might contain glitches (jumps) or other
inconsistencies
that need to be sorted out before feeding them to the Kalman filter.

How would you go about detecting glitches and maybe even do a
first-pass correction of such data? A manual check of 100,000 data
points doesn't seem as a very tempting prospect...

Rune

"Rune Allnor" <allnor@tele.ntnu.no> kirjoitti 
viestiss&#4294967295;:1151317297.168309.116350@m73g2000cwd.googlegroups.com...
> Hi folks.
>
> Assume you are given som 20,000 - 100,000 points of raw (x,y,z)
> navigation data as previously logged on some platform, and are asked
> to clean up the data.
>
> My first, naive idea is to use some Kalman filter. So far so good.
>
> However, the data might contain glitches (jumps) or other
> inconsistencies
> that need to be sorted out before feeding them to the Kalman filter.
>
> How would you go about detecting glitches and maybe even do a
> first-pass correction of such data? A manual check of 100,000 data
> points doesn't seem as a very tempting prospect...
>
> Rune

I don't know about the systems to exclude irregularities, I doubt if there 
are any without some presumptions, e.g. maximum distance between two 
consecutive points etc. I will stay tuned to here about such methods.

However, if you after getting rid of the exceptions (errors in data) want to 
reduce the number of points in your navigation data, you could apply my 
freeware GeoConv. With GeoConv you can reduce the number of points in your 
navigation data still maintaining the shape of the track as close to the 
original track as possible.

GeoConv: http://www.kolumbus.fi/eino.uikkanen/geoconvgb/index.htm

Eino Uikkanen
http://www.kolumbus.fi/eino.uikkanen/gb/index.htm 

Rune Allnor wrote:
> Hi folks.
>
> Assume you are given som 20,000 - 100,000 points of raw (x,y,z)
> navigation data as previously logged on some platform, and are asked
> to clean up the data.
>
> My first, naive idea is to use some Kalman filter. So far so good.
>
> However, the data might contain glitches (jumps) or other
> inconsistencies
> that need to be sorted out before feeding them to the Kalman filter.
>
> How would you go about detecting glitches and maybe even do a
> first-pass correction of such data? A manual check of 100,000 data
> points doesn't seem as a very tempting prospect...

What do you look for in a manual check?

Andor wrote:
> Rune Allnor wrote:
> > Hi folks.
> >
> > Assume you are given som 20,000 - 100,000 points of raw (x,y,z)
> > navigation data as previously logged on some platform, and are asked
> > to clean up the data.
> >
> > My first, naive idea is to use some Kalman filter. So far so good.
> >
> > However, the data might contain glitches (jumps) or other
> > inconsistencies
> > that need to be sorted out before feeding them to the Kalman filter.
> >
> > How would you go about detecting glitches and maybe even do a
> > first-pass correction of such data? A manual check of 100,000 data
> > points doesn't seem as a very tempting prospect...
>
> What do you look for in a manual check?

Anything that can be said to be a "glitch" or an "irregular feature".
Some of the tracks seem to "jump" sideways on the order of 2Dx
to 3Dx, where Dx is the along-track distance between measurements.
Then they get back "on-track" within a variable number of samples,
say 5 to 20 samples.

I have a couple of ideas about how to *detect* these things, for
manual correction. But then, if there already exists a wheel, why
re-invent it...

Rune

Eino Uikkanen wrote:
> "Rune Allnor" <allnor@tele.ntnu.no> kirjoitti
> viestiss=E4:1151317297.168309.116350@m73g2000cwd.googlegroups.com...
> > Hi folks.
> >
> > Assume you are given som 20,000 - 100,000 points of raw (x,y,z)
> > navigation data as previously logged on some platform, and are asked
> > to clean up the data.
> >
> > My first, naive idea is to use some Kalman filter. So far so good.
> >
> > However, the data might contain glitches (jumps) or other
> > inconsistencies
> > that need to be sorted out before feeding them to the Kalman filter.
> >
> > How would you go about detecting glitches and maybe even do a
> > first-pass correction of such data? A manual check of 100,000 data
> > points doesn't seem as a very tempting prospect...
> >
> > Rune
>
> I don't know about the systems to exclude irregularities, I doubt if there
> are any without some presumptions, e.g. maximum distance between two
> consecutive points etc. I will stay tuned to here about such methods.
>
> However, if you after getting rid of the exceptions (errors in data) want=
 to
> reduce the number of points in your navigation data, you could apply my
> freeware GeoConv. With GeoConv you can reduce the number of points in your
> navigation data still maintaining the shape of the track as close to the
> original track as possible.
>
> GeoConv: http://www.kolumbus.fi/eino.uikkanen/geoconvgb/index.htm
>
> Eino Uikkanen
> http://www.kolumbus.fi/eino.uikkanen/gb/index.htm

Thanks. I'll have a look at it.

Rune

Rune Allnor wrote:
> Andor wrote:
> > Rune Allnor wrote:
> > > Hi folks.
> > >
> > > Assume you are given som 20,000 - 100,000 points of raw (x,y,z)
> > > navigation data as previously logged on some platform, and are asked
> > > to clean up the data.
> > >
> > > My first, naive idea is to use some Kalman filter. So far so good.
> > >
> > > However, the data might contain glitches (jumps) or other
> > > inconsistencies
> > > that need to be sorted out before feeding them to the Kalman filter.
> > >
> > > How would you go about detecting glitches and maybe even do a
> > > first-pass correction of such data? A manual check of 100,000 data
> > > points doesn't seem as a very tempting prospect...
> >
> > What do you look for in a manual check?
>
> Anything that can be said to be a "glitch" or an "irregular feature".
> Some of the tracks seem to "jump" sideways on the order of 2Dx
> to 3Dx, where Dx is the along-track distance between measurements.
> Then they get back "on-track" within a variable number of samples,
> say 5 to 20 samples.

Sounds like you are witnessing innovation outliers in a small order AR
process (since the signal take some time to get back on track after an
outlier). You can try an m-estimate (robust) linear predictor, and
threshold the prediction error for outlier detection. Are the outliers
correlated in the three dimensions eg. you have one in x-axis, then you
have one in y-axis?.

Alternatively, if you have to smooth the data afterwards in any case,
you might be interested in the procedure described here:

G Doblinger: "Adaptive Kalman Smoothing of AR Signals distrubed by
impulses and colored noise", Proc. 1998 IEEE Symp. on Advances in Dig.
Filt. and Sig. Proc., June 5-6, 1998.

The paper is available on the net.

> I have a couple of ideas about how to *detect* these things, for
> manual correction. But then, if there already exists a wheel, why
> re-invent it...

AR modeling can also be useful for automatic correction
(interpolation).

Regards,
Andor

> However, the data might contain glitches (jumps) or other
> inconsistencies
> that need to be sorted out before feeding them to the Kalman filter.

It depends on what you call a glitch.

If you are talking about several non-plausible points, try to check 
agains physical constraints like maximum velocity (1st derivative) or 
maximum acceleration/deceleration (2nd derivative). However, in any case 
you need the time. So either delta-t between two points must be always 
the same or you need tuples of {x,y,z,t}.


Marcel

(f'up)

Andor wrote:
> Rune Allnor wrote:
> > Andor wrote:
> > > Rune Allnor wrote:
> > > > Hi folks.
> > > >
> > > > Assume you are given som 20,000 - 100,000 points of raw (x,y,z)
> > > > navigation data as previously logged on some platform, and are asked
> > > > to clean up the data.
> > > >
> > > > My first, naive idea is to use some Kalman filter. So far so good.
> > > >
> > > > However, the data might contain glitches (jumps) or other
> > > > inconsistencies
> > > > that need to be sorted out before feeding them to the Kalman filter.
> > > >
> > > > How would you go about detecting glitches and maybe even do a
> > > > first-pass correction of such data? A manual check of 100,000 data
> > > > points doesn't seem as a very tempting prospect...
> > >
> > > What do you look for in a manual check?
> >
> > Anything that can be said to be a "glitch" or an "irregular feature".
> > Some of the tracks seem to "jump" sideways on the order of 2Dx
> > to 3Dx, where Dx is the along-track distance between measurements.
> > Then they get back "on-track" within a variable number of samples,
> > say 5 to 20 samples.
>
> Sounds like you are witnessing innovation outliers in a small order AR
> process (since the signal take some time to get back on track after an
> outlier). You can try an m-estimate (robust) linear predictor, and
> threshold the prediction error for outlier detection.

We'll see. My idea is a bit more simplistic/naive, to sheck deviations
in forward direction between time steps. Yours is probably more
computationally efficient.

> Are the outliers
> correlated in the three dimensions eg. you have one in x-axis, then you
> have one in y-axis?.

I don't know. I haven't had a very close look at the data yet.

> Alternatively, if you have to smooth the data afterwards in any case,
> you might be interested in the procedure described here:
>
> G Doblinger: "Adaptive Kalman Smoothing of AR Signals distrubed by
> impulses and colored noise", Proc. 1998 IEEE Symp. on Advances in Dig.
> Filt. and Sig. Proc., June 5-6, 1998.
>
> The paper is available on the net.

Thanks! I guess there are one or two journal papers based on this
one, if the idea turned out to be good.

> > I have a couple of ideas about how to *detect* these things, for
> > manual correction. But then, if there already exists a wheel, why
> > re-invent it...
>
> AR modeling can also be useful for automatic correction
> (interpolation).

I was thinking along the lines of Wiener filters for data smoothing,
but I guess we are in the same ball park.

Rune

Rune Allnor wrote:
> Andor wrote:
> > Rune Allnor wrote:
> > > Andor wrote:
> > > > Rune Allnor wrote:
> > > > > Hi folks.
> > > > >
> > > > > Assume you are given som 20,000 - 100,000 points of raw (x,y,z)
> > > > > navigation data as previously logged on some platform, and are asked
> > > > > to clean up the data.
> > > > >
> > > > > My first, naive idea is to use some Kalman filter. So far so good.
> > > > >
> > > > > However, the data might contain glitches (jumps) or other
> > > > > inconsistencies
> > > > > that need to be sorted out before feeding them to the Kalman filter.
> > > > >
> > > > > How would you go about detecting glitches and maybe even do a
> > > > > first-pass correction of such data? A manual check of 100,000 data
> > > > > points doesn't seem as a very tempting prospect...
> > > >
> > > > What do you look for in a manual check?
> > >
> > > Anything that can be said to be a "glitch" or an "irregular feature".
> > > Some of the tracks seem to "jump" sideways on the order of 2Dx
> > > to 3Dx, where Dx is the along-track distance between measurements.
> > > Then they get back "on-track" within a variable number of samples,
> > > say 5 to 20 samples.
> >
> > Sounds like you are witnessing innovation outliers in a small order AR
> > process (since the signal take some time to get back on track after an
> > outlier). You can try an m-estimate (robust) linear predictor, and
> > threshold the prediction error for outlier detection.
>
> We'll see. My idea is a bit more simplistic/naive, to sheck deviations
> in forward direction between time steps.

The ideas are the same - differencing is the simplest form of linear
prediction (where you predict the future value to be equal to the
current value). The first difference filter can be interpreted as the
prediction error filter. In general, predictors can be made data
adaptive. However, differencing is a good first guess for a linear
predictor. As Marcel writes, you can even threshold the prediction
error based on physical criteria.

> Yours is probably more
> computationally efficient.

No, mine is more costly - you have to compute the data adaptive
predictor (usually a new one every couple of samples).

>
> > Are the outliers
> > correlated in the three dimensions eg. you have one in x-axis, then you
> > have one in y-axis?.
>
> I don't know. I haven't had a very close look at the data yet.

Would be interesting to know.

>
> > Alternatively, if you have to smooth the data afterwards in any case,
> > you might be interested in the procedure described here:
> >
> > G Doblinger: "Adaptive Kalman Smoothing of AR Signals distrubed by
> > impulses and colored noise", Proc. 1998 IEEE Symp. on Advances in Dig.
> > Filt. and Sig. Proc., June 5-6, 1998.
> >
> > The paper is available on the net.
>
> Thanks! I guess there are one or two journal papers based on this
> one, if the idea turned out to be good.
>
> > > I have a couple of ideas about how to *detect* these things, for
> > > manual correction. But then, if there already exists a wheel, why
> > > re-invent it...
> >
> > AR modeling can also be useful for automatic correction
> > (interpolation).
>
> I was thinking along the lines of Wiener filters for data smoothing,
> but I guess we are in the same ball park.

Yup. Have fun in your Waterworld :-)!

Regards,
Andor

Rune Allnor wrote:
> Andor wrote:

>> What do you look for in a manual check?
> 
> Anything that can be said to be a "glitch" or an "irregular
> feature". Some of the tracks seem to "jump" sideways on the
> order of 2Dx to 3Dx, where Dx is the along-track distance
> between measurements. Then they get back "on-track" within a
> variable number of samples, say 5 to 20 samples.
> 
> I have a couple of ideas about how to *detect* these things, for
> manual correction. But then, if there already exists a wheel,
> why re-invent it...

This may not be of immediate help to you but there's a book titled 
"Detection of Abrupt Changes" online at 
http://www.irisa.fr/sisthem/kniga/ .

Regarding correction, your problem sounds similar to that of click 
removal in audio which has been treated here before, I think, and is 
commonly attacked with LPC extrapolation.


Martin

-- 
Quidquid latine scriptum sit, altum viditur.