FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups 
 ProfileProfile   PreferencesPreferences   Log in to check your private messagesLog in to check your private messages   Log inLog in 
Forum index » Science and Technology » Engineering » Control
Glitch/inconsistency detection in navigation data
Post new topic   Reply to topic Page 2 of 3 [34 Posts] View previous topic :: View next topic
Goto page:  Previous  1, 2, 3 Next
Author Message
Ulrich Bangert
science forum beginner


Joined: 27 Jun 2006
Posts: 4

PostPosted: Tue Jun 27, 2006 1:54 am    Post subject: Re: Glitch/inconsistency detection in navigation data Reply with quote

Rune,

this problem is the classical application for so called "robust statistical
methods".

1) Decide for a window length of n data points. This window will be used to
scan through your data for outlier and glitch detection.

2) Get the first n points of data (in case of your three dimensional
problem, cover each dimension on its own)

3) Compute the MEDIAN of the data (= the 50% PERCENTILE) If in doubt how to
compute the MEDIAN, check MATLAB help. The MEDIAN is a very good
approximation to the mean value of your data. However, the MEDIAN is
completely insensitive to outliers and glitches as long as the number of
ourliers within your window is smaller then n/2. Note that you now have a
outlier insensitive measure for the mean of your data. The MEDIAN is to
robust counterpiece to the MEAN.

4) For all data within your window compute the absolute value of the
difference between the data and the median and put the results of this
operation into a buffer array.

5) Multiply all values in your buffer with a scaling constant 1/0.654.

6) Compute the MEDIAN of the the data in your buffer. The MEDIAN of the
buffer values is the so called "MAD" (Median absolute deviation) of the
original values within your window. The MAD is the outlier insensitive
robust counterpiece to the normal standard deviation which is highly
sensitive to outliers. The scaling factor of 1/0.645 makes the MAD directly
comparable to the standard deviation for normal distributed values.

7) A rule of thumb in classical statistics is: If data is more far away from
the mean than 5 time the standard deviation, it is most probably a outlier.
Now that you have robust values available apply this rule to the robust
values: If data is more than 5 time away from the MEDIAN than the MAD then
it is most probably a outlier.

8) If a outlier is detected be sure to remove it from all diemensions.

9) Shift your window by one and go to step 3

10) Repeat for all data

Sounds as if a lot computing power is necessary for the algorithm and yes,
indeed it is. Note that computing the MEDIAN involves ordering the data
within your window in an ascending order and you need to compute a MEDIAN
twice per window shift. Use a fast sorting algorithm!

I use the above method as my standard outlier detection routine whereever i
expect to be confronted with outliers and it works very well. Note that the
length of the window is a compromise between processing time and having
enough values in the window to make significant statistics with. Note also,
that this algorithm detects outliers fairly well but is not well suited if
your your data contains inconsitencies like sudden steps (offsets that
stay).

Regards

Ulrich

"Rune Allnor" <allnor@tele.ntnu.no> schrieb im Newsbeitrag
news:1151317297.168309.116350@m73g2000cwd.googlegroups.com...
Quote:
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
Back to top
Rune Allnor
science forum beginner


Joined: 03 May 2005
Posts: 18

PostPosted: Tue Jun 27, 2006 3:41 am    Post subject: Re: Glitch/inconsistency detection in navigation data Reply with quote

Tim Wescott wrote:
Quote:
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...

Rune

Hey Rune:

One thing you could do would be to compare the data with the Kalman
filter output, and ignore it whenever there's too much difference. This
causes problems if your system truly moves outside of your 'known good'
band.

Another thing that works is to discount the data when it's glitchy, but
not completely. You could either have two state evolution rules, one
for when the data is 'bad' and another for when it's 'good'. This would
result in the filter being influenced by genuinely bad data, but it
would also result in the filter being able to find it's way home if it
were way off track.

My understanding of Kalman filters is somewhat casual*, but I do know
that the classic construction assumes linear systems excited by Gaussian
noise, and quadratic cost functions. If your underlying systems aren't
linear, if your noise isn't Gaussian or if your cost functions aren't
quadratic then the optimal solution isn't linear anymore, so a plain ol'
Kalman filter is ruled out -- search around on the term 'extended
Kalman' for insight in that case.

Right... things get messy when all the nice idealizations and
assumptions turn out to be a bit too ideal... been there.

Quote:
* I've got to get a good book on this.

Let me know if you find one. All I have in my library (which I don't
have access to for another couple of weeks) is an early 90s
edition of Brown and Kwang(?).

Rune
Back to top
Steve Underwood
science forum beginner


Joined: 26 May 2005
Posts: 7

PostPosted: Tue Jun 27, 2006 4:30 am    Post subject: Re: Glitch/inconsistency detection in navigation data Reply with quote

Rune Allnor wrote:
Quote:
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

You didn't say what kind of navigational system this is. I think that

might affect the nature of what you see quite a bit.

I'm no nav system expert. I've simply had cause to use the output of nav
systems for various purposes. Understanding the qualities of the nav
data has been a somewhat low priority compared to my other tasks. That
said.....

My experience with taking data from inertial navigation systems is that
at first sight they look real glitchy. However, if you apply almost any
simple LPF - say, a single pole LPF - with a suitable cut off frequency
the data quietens down wonderfully. What appear at first sight to be
glitches actually appear to be unbiased noise that simply has a very
spiky quality.

Steve
Back to top
Rune Allnor
science forum beginner


Joined: 03 May 2005
Posts: 18

PostPosted: Tue Jun 27, 2006 5:05 am    Post subject: Re: Glitch/inconsistency detection in navigation data Reply with quote

JF Mezei wrote:
Quote:
Eliminating "stray" waypoints requires knowledge of the situation.

If you are travelling by foot and taking trackpoints every minute, then
a point that is more than 250 metres off the general direction of travel
is an exception. ( running at 15km/h for one minute) If it is an olympic
runner, hen you need to increase that value.

If travelling on a bicycle, you need to know the condition. If on a main
road, a trackpoint doesn't need to be that far off before it is an
exception. But if travelling up a switchback on a mountain pass road in
the alps, then a lot of your points will be "off course" but still very
valid to map your track.

If travelling by car on the same road, your trackpoints may not be taken
at sufficiently close intervals to log some of the switchbacks and log
just a mostly straight road up the mountain with minor ddviations
between each point.

If you have 3 points, A B and C, B can be considred an exception if the
discance between B and the axis A-C is greater than some amount. (the
aviation formulary has those equations to calculate distance between a
point and an axis).

Now, if you have 4 points, A B C and D with B and C being odd, the above
logic won't work because B will be within the limits of the A-C axis.

I think this approach might be useful. Do you have any references
(books, articles) to how these things are done in aviation?

Rune
Back to top
JF Mezei
science forum beginner


Joined: 26 Jun 2006
Posts: 6

PostPosted: Tue Jun 27, 2006 6:22 am    Post subject: Re: Glitch/inconsistency detection in navigation data Reply with quote

Rune Allnor wrote:
Quote:
If you have 3 points, A B and C, B can be considred an exception if the
discance between B and the axis A-C is greater than some amount.


I think this approach might be useful. Do you have any references
(books, articles) to how these things are done in aviation?

No. The ideas were given to me here (sci.geo.satellite-nav) years ago
while I was post processing some tracks data I had accumulated during a
bike trip through australia. I built logic to simplify the number of
points (remove those that do not define a change in direction, and
remove those that are "stray".).


Another thing to consider: if you are a large cargo ship overating in
the st-lawrence seaway, a stray point may be really easy to spot because
a ship simply cannot move on a dime. But if you are a canoe on a rapidly
flowing river, you may catch an eddy currnt that quickly pushes you off
course.

But for an aircraft, you need to really define the requirements and
handling os any glitch. Are you allowed to filter data out which will
not get logged onto the flight recorder ? The advantage of aviation is
that you can coorolate GPS with the primary instruments. (UINS and
barometric altimetre). So if you see a glitch on the GPS but no glitch
on the other systems, then the GOPS probably experienced a glitch. But
if it is visible on all 3 systems, then it is probably turbulence etc etc.
Back to top
JF Mezei
science forum beginner


Joined: 26 Jun 2006
Posts: 6

PostPosted: Tue Jun 27, 2006 7:21 am    Post subject: Re: Glitch/inconsistency detection in navigation data Reply with quote

Ulrich Bangert wrote:
Quote:
this problem is the classical application for so called "robust statistical
methods".

How would your method handle a situation where one is riding a bike at
30km on a very flat road for 6 hours in a steady speed, and for one
minute, you have this kamakaze downhill where you reach 80km/ h and then
ride up a hill at 10kmh for 7 minutes. Would it "filter out" those
readings of going down and then up the hill ?
Back to top
JF Mezei
science forum beginner


Joined: 26 Jun 2006
Posts: 6

PostPosted: Tue Jun 27, 2006 7:29 am    Post subject: Re: Glitch/inconsistency detection in navigation data Reply with quote

Another aspect to consider:

When I processed my australian track logs, those points, taken at 1
minute intervals, that were very near to each other were in fact VERY
significant because this indicated a place where I stopped ( in some
cases, I want those to stand out to show places where whater was available).

So from a simplification of the trackpoints to draw a route, those
points can be removed, but you want to mark those points as significant
stops and possibly create a waypoint for them.

So one must really be familiar with the activity and how the data was
collected before selecting some logic to simplify a series of points.

Another aspect: many GPS have an "auto" feature to write track points
into the log. Generallly, track points are written when there is a
change in speed/direction and possibly at some regular intervals. But if
you do not know the exact logic used by the unit to decide if a
trackpoint is to be written or not, you cannot really decide how to
remove trackpoints statistically.
Back to top
Rune Allnor
science forum beginner


Joined: 03 May 2005
Posts: 18

PostPosted: Tue Jun 27, 2006 7:37 am    Post subject: Re: Glitch/inconsistency detection in navigation data Reply with quote

Ulrich Bangert wrote: lots of interesting stuff.

Thanks. Sounds like something to look into. Processing speed is
(as of yet) insignificant if it can release man-hours for other duties.
Where I am right now, man-hours are expensive. If a computer
needs 12 hours for this sort of job, then so be it, if it can be done
in the human operator's time off watch.

Rune
Back to top
Steve Underwood
science forum beginner


Joined: 26 May 2005
Posts: 7

PostPosted: Tue Jun 27, 2006 8:25 am    Post subject: Re: Glitch/inconsistency detection in navigation data Reply with quote

JF Mezei wrote:
Quote:
Another aspect to consider:

When I processed my australian track logs, those points, taken at 1
minute intervals, that were very near to each other were in fact VERY
significant because this indicated a place where I stopped ( in some
cases, I want those to stand out to show places where whater was available).

So from a simplification of the trackpoints to draw a route, those
points can be removed, but you want to mark those points as significant
stops and possibly create a waypoint for them.

So one must really be familiar with the activity and how the data was
collected before selecting some logic to simplify a series of points.

Another aspect: many GPS have an "auto" feature to write track points
into the log. Generallly, track points are written when there is a
change in speed/direction and possibly at some regular intervals. But if
you do not know the exact logic used by the unit to decide if a
trackpoint is to be written or not, you cannot really decide how to
remove trackpoints statistically.

Related fun things happen in radar tracking. There you usually have
reasonable x and y estimates (based on the r and theta you measure), and
a weak z measurement (based on a very limit accuracy angular
measurement). You can track a target and predict based on what is a
reasonable side to side turn rate. However, a fighter can roll over then
do a hard downward half loop and go back in the direction it came. Your
nicely filtered track basically stops abruptly and goes backwards, and
your weak height information doesn't always help that much in tracking
in 3D. Airliners are easy to track, but the interesting targets are a
real pain.

This kind of filtering is like the tale I heard of the world's most
accurate weather forecasts. I was told a DJ in the Caribbean spent years
saying the weather would be whatever it was yesterday. Because the
weather there has long period of similar conditions punctuated by abrupt
changes, his accuracy was very high, but his usefulness was zero. :-)

Regards,
Steve
Back to top
Ulrich Bangert
science forum beginner


Joined: 27 Jun 2006
Posts: 4

PostPosted: Wed Jun 28, 2006 6:01 am    Post subject: Re: Glitch/inconsistency detection in navigation data Reply with quote

To Rune:

On a typical pc with a window width of 100 I process 600000 data points in
1-2 minutes, so it is not THAT slow that my first mail may have indicated. I
use this algorithm for example in a freeware software named "Plotter". You
can download "Plotter" from my homepage

www.ulrich-bangert.de

If you manage to load your data files with that (chances are..) you can
immediatly test the quality and the speed of the outlier detection.

To JF Mezei:

I you managed to figure out exactly what the algorithm does, you will have
noticed that for detecting outliers everything is significant, that is
INSIDE the window, nothing else. For that reason, if this algorithm is
applied to the scenario you present, the first thing to say is, that it does
not matter at all whether you have been riding for 6, 12, 18 or anything
hours before you meet the hill. The algorithm is completely insensitive to
that!

The window is something like "If you want to detect outliers look only to
values in the neighbourhood and decide what is normal and what is not for
them". Please note also, that your scenario arises the question for a
definition of "oulier". Other people would pehrhaps think that the "hill
scenario" IS indeed a outlier that should be removed while you think it is
very significant. Note, that the algorithm can fit BOTH kind of views by
adopting the window length. If you make the window length greater than 2 X
the "hill length" then the hill will be completely removed from the data. If
you find that the hill is significant then make the window length smaller
than 2X the "hill length", in this case the hill will not be filtered out.
By applying the rule "a event shorter than n/2 may be a outlier" YOU decide
what is an outlier not the algorithm.

I cannot accept your second objection, it is a outlier detection algorithm,
not a biker's rest detection algorithm. But if you want to put forward the
question whether the rest will be detected as an outlier or not, the same
rules apply as above: If the window length is set to value so that the
length of the braking action before stop and the window length "match" then
the stop will be recognized as a "normal" change in data

Regards
Ulrich

"Rune Allnor" <allnor@tele.ntnu.no> schrieb im Newsbeitrag
news:1151393854.224220.97860@p79g2000cwp.googlegroups.com...
Quote:

Ulrich Bangert wrote: lots of interesting stuff.

Thanks. Sounds like something to look into. Processing speed is
(as of yet) insignificant if it can release man-hours for other duties.
Where I am right now, man-hours are expensive. If a computer
needs 12 hours for this sort of job, then so be it, if it can be done
in the human operator's time off watch.

Rune
Back to top
Rune Allnor
science forum beginner


Joined: 03 May 2005
Posts: 18

PostPosted: Wed Jun 28, 2006 6:24 am    Post subject: Re: Glitch/inconsistency detection in navigation data Reply with quote

Ulrich Bangert wrote:
Quote:
To Rune:

On a typical pc with a window width of 100 I process 600000 data points in
1-2 minutes, so it is not THAT slow that my first mail may have indicated. I
use this algorithm for example in a freeware software named "Plotter". You
can download "Plotter" from my homepage

www.ulrich-bangert.de

If you manage to load your data files with that (chances are..) you can
immediatly test the quality and the speed of the outlier detection.

I'll definately have a look into this. Your first post indicated you
have programmed these things in matlab? If so, there is a speed-up
potential here. I usually get a speed-up on the order of 10-50x when
I port from matlab to C or C++.

Rune
Back to top
JF Mezei
science forum beginner


Joined: 26 Jun 2006
Posts: 6

PostPosted: Wed Jun 28, 2006 6:58 am    Post subject: Re: Glitch/inconsistency detection in navigation data Reply with quote

Ulrich Bangert wrote:
Quote:
very significant. Note, that the algorithm can fit BOTH kind of views by
adopting the window length. If you make the window length greater than 2 X
the "hill length" then the hill will be completely removed from the data. If
you find that the hill is significant then make the window length smaller
than 2X the "hill length", in this case the hill will not be filtered out.


Ok. fair enough. But that still leaves the requirement that the user
know about the type of data that he has to process, the types of
irregularities which must be retained, and those that can be removed
because this will be needed to decide on the window size. And one also
need to know how the data was collected.

Say on a long straight road, a car turns off and drives 100m to a water
hole/pump. With periodic trackpoint recording, you could have a couple
of stray points. With "auto" track recording, chances are very good that
the GPS would record a point at the turnoff, one point at the stop for
water, and again a point once the car gets back to main road and turns
back into the normal direction.

Now, both would have a couple of stray points from a purely
"mathematical" point of view. But in the second case, a human could
more clearly see a path away from road and back to the road at the same
intersection to resume course.

So one must really understand the "event" as well as how the data was
recorded for that event before starting to process such data and
eliminate points judged to be "bad".
Back to top
Ulrich Bangert
science forum beginner


Joined: 27 Jun 2006
Posts: 4

PostPosted: Wed Jun 28, 2006 7:52 am    Post subject: Re: Glitch/inconsistency detection in navigation data Reply with quote

Rune,

as a dedicated follower of PASCAL i program in Borland DELPHI which produces
native code that i do not suspect to be significantly slower then C/C++
generated code. But over the years I have found that the Matlab help system
gives me information about mathematical topics at exactly the level that
seems to match me, that's why i pointed to it. If Plotter does not read your
files, then (in case they are ASCII) send me a few lines of it. I am very
interested to make my file read routines as universal as possible, so every
no-go is a object of interest.

Regards
Ulrich


"Rune Allnor" <allnor@tele.ntnu.no> schrieb im Newsbeitrag
news:1151475859.983140.83250@d56g2000cwd.googlegroups.com...
Quote:

Ulrich Bangert wrote:
To Rune:

On a typical pc with a window width of 100 I process 600000 data points
in
1-2 minutes, so it is not THAT slow that my first mail may have
indicated. I
use this algorithm for example in a freeware software named "Plotter".
You
can download "Plotter" from my homepage

www.ulrich-bangert.de

If you manage to load your data files with that (chances are..) you can
immediatly test the quality and the speed of the outlier detection.

I'll definately have a look into this. Your first post indicated you
have programmed these things in matlab? If so, there is a speed-up
potential here. I usually get a speed-up on the order of 10-50x when
I port from matlab to C or C++.

Rune
Back to top
Ulrich Bangert
science forum beginner


Joined: 27 Jun 2006
Posts: 4

PostPosted: Wed Jun 28, 2006 8:07 am    Post subject: Re: Glitch/inconsistency detection in navigation data Reply with quote

Hello JF Mezei,

Quote:
Ok. fair enough. But that still leaves the requirement that the user
know about the type of data that he has to process, the types of
irregularities which must be retained, and those that can be removed
because this will be needed to decide on the window size. And one also
need to know how the data was collected.

Agreed!

Quote:
of stray points. With "auto" track recording, chances are very good that
the GPS would record a point at the turnoff, one point at the stop for
water, and again a point once the car gets back to main road and turns
back into the normal direction.

I am not sure if i interprete the term "auto track recording" in the right
way. Perhaps it is even a "standard" term in navigation that i am not aware
of (I have seen the question for outlier detection purely from a
mathematical point of view). But if it is some kind of "event driven" track
recording you are of course right that the proposed algorithm can not handle
data acquired in this way because some frontend entity has already made the
decision what an event is and what not and has missed to acquire the
"surrounding data" that are necessary for the algorithm.

Regards
Ulrich

"JF Mezei" <jfmezei.spamnot@teksavvy.com> schrieb im Newsbeitrag
news:44A2289A.BF59B898@teksavvy.com...
Quote:
Ulrich Bangert wrote:
very significant. Note, that the algorithm can fit BOTH kind of views by
adopting the window length. If you make the window length greater than 2
X
the "hill length" then the hill will be completely removed from the
data. If
you find that the hill is significant then make the window length
smaller
than 2X the "hill length", in this case the hill will not be filtered
out.


Ok. fair enough. But that still leaves the requirement that the user
know about the type of data that he has to process, the types of
irregularities which must be retained, and those that can be removed
because this will be needed to decide on the window size. And one also
need to know how the data was collected.

Say on a long straight road, a car turns off and drives 100m to a water
hole/pump. With periodic trackpoint recording, you could have a couple
of stray points. With "auto" track recording, chances are very good that
the GPS would record a point at the turnoff, one point at the stop for
water, and again a point once the car gets back to main road and turns
back into the normal direction.

Now, both would have a couple of stray points from a purely
"mathematical" point of view. But in the second case, a human could
more clearly see a path away from road and back to the road at the same
intersection to resume course.

So one must really understand the "event" as well as how the data was
recorded for that event before starting to process such data and
eliminate points judged to be "bad".
Back to top
Jerry Avins
science forum Guru


Joined: 03 May 2005
Posts: 534

PostPosted: Wed Jun 28, 2006 2:58 pm    Post subject: Re: Glitch/inconsistency detection in navigation data Reply with quote

JF Mezei wrote:

...

Quote:
So one must really understand the "event" as well as how the data was
recorded for that event before starting to process such data and
eliminate points judged to be "bad".

One must always understand data in order to analyze and interpret it
meaningfully. Believing otherwise is like believing that someone can
manage a business without understanding its nature.

Jerry
--
Engineering is the art of making what you want from things you can get.
ŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻ
Back to top
Google

Back to top
Display posts from previous:   
Post new topic   Reply to topic Page 2 of 3 [34 Posts] Goto page:  Previous  1, 2, 3 Next
View previous topic :: View next topic
The time now is Thu Aug 24, 2017 8:56 am | All times are GMT
Forum index » Science and Technology » Engineering » Control
Jump to:  

Similar Topics
Topic Author Forum Replies Last Post
No new posts modelling method for categorical data Arby Math 1 Wed Jul 19, 2006 12:09 pm
No new posts Obtaining a morphism of sheaves from homotopy data categorist Research 0 Mon Jul 17, 2006 8:15 pm
No new posts starting question: analysing the interations of historica... richardchaven num-analysis 1 Sun Jul 09, 2006 4:24 pm
No new posts Fit a transfer function to gain and phase data Roza.Mahmoodian@gmail.com Control 7 Fri Jul 07, 2006 5:05 pm
No new posts life data: Heywood, Lawley, Young Rudolf Sponsel Math 0 Thu Jul 06, 2006 10:33 am

Copyright © 2004-2005 DeniX Solutions SRL
Other DeniX Solutions sites: Electronics forum |  Medicine forum |  Unix/Linux blog |  Unix/Linux documentation |  Unix/Linux forums  |  send newsletters
 


Powered by phpBB © 2001, 2005 phpBB Group
[ Time: 0.0667s ][ Queries: 16 (0.0360s) ][ GZIP on - Debug on ]