Internet DRAFT - draft-hoene-geopriv-bli
draft-hoene-geopriv-bli
GEOPRIV C. Hoene
Internet Draft A. Krebs
Intended status: Informational C. Behle
M. Schmidt
Expires: April 2011 Universitaet Tuebingen
October 14, 2010
Bayesian Location Identifier
draft-hoene-geopriv-bli-00.txt
Status of this Memo
This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet-
Drafts.
Internet-Drafts are draft documents valid for a maximum of six
months and may be updated, replaced, or obsoleted by other documents
at any time. It is inappropriate to use Internet-Drafts as
reference material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html
This Internet-Draft will expire on April 14, 2011.
Copyright Notice
Copyright (c) 2010 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with
respect to this document.
Hoene et al. Expires April 14, 2011 [Page 1]
Internet-Draft Bayesian Location Identifier October 2010
Abstract
Location Generators cannot always provide exact measures of
particular locations. Instead, they estimate the location of
objects. More precisely, they use filters to aggregate noisy sensor
data and to calculate probability density distributions of estimated
positions. In location tracking applications, typically Kalman-type,
Gaussian-Sum, and Particle Filters are used.
We believe that it is reasonable to use the outputs of those filters
to describe a location estimate and its uncertainty, because they
are the natural result of location tracking algorithms. In addition,
the results of those filters can be feed into sensor fusion and
decision making engines easily.
Geometric representations such as polygons or ellipses might be
demanded by an application. The output of filters can be converted
to those application demanded shapes. However, these conversions
come at the loss of precision and are not well understood
scientifically. Thus, we think that transmitting filter results is a
solution that is easier to implement.
In this draft, we present a transmission format for PIDF-LO, which
is based on the output of Kalman-type, Gaussian-Sum, and Particle
Filters.
Table of Contents
1. Introduction...................................................3
2. Overview on Filters............................................3
2.1. Kalman Filters............................................4
2.2. Particle Filter...........................................4
2.3. Gaussian Sum Particle Filters.............................5
3. Coordinate System and Datum....................................5
4. Examples.......................................................5
4.1. Kalman Filter Results.....................................5
4.2. Particle Filter Results...................................6
4.3. Gaussian Sum Filter.......................................7
4.4. Well-know Reference Frame.................................7
4.5. Relative Datum............................................8
5. Security Considerations........................................9
6. IANA Considerations............................................9
7. Conclusions....................................................9
8. References.....................................................9
8.1. Informative References....................................9
Hoene Expires April 14, 2011 [Page 2]
Internet-Draft Bayesian Location Identifier October 2010
1. Introduction
The location of an object cannot be measured precisely always.
Especially, in an indoor environment numerous sources of measurement
errors lead to measurement results, which are uncertain in a high
degree. To represent this uncertainty, a previous draft [1] defines
how uncertainty and its associated datum and confidence is expressed
and interpreted. To simplify the representation, the draft limits
the description of uncertainty to a number of well defined shapes,
e.g. one point, a centroid, an arc-band centroid, or polygons.
However, state of the art multimodal location tracking algorithms do
not provide any location results of the above mentioned shapes.
Instead, they typically applied some sort of Kalman or Particle
Filters, which assume a Gaussian or an arbitrary error distribution.
Thus, in this draft we propose to transmit as location information
the results of Gaussian distributions or Particle Filters to present
uncertainty.
This has the following advantages:
1. Any kind of uncertainly can be transmitted. More precisely, any
form of probability distribution, which represents uncertainty,
can be represented.
2. A conversion from particles to shapes is not required, which
maintains precision and eases implementations.
3. Kalman and Particle filters are well understood statistical tools
based on research of control theory, signal processing, Monte-
Carlo simulations and Bayesian statistics. Numerous location
tracking algorithms have been developed that work with those
filters. Thus, the transmission format defined in this draft is
based on a profound scientific basis.
2. Overview on Filters
Location tracking is based on physical measurements, which estimate
time of flight, signal strength, angle of arrives, motions, objects
in images, and many other forms of sensor input. All these sensor
measurements are subjected to measurement noise. Because of that,
filters are used to estimate the real value of the measurement
despite the fact of measurement results that are subjected to noise.
Many filter types have been developed. However, in location tracking
typically only a few are applied. These include different types of
Kalman-Filters, filters that work with one or multiple Gaussian
Hoene Expires April 14, 2011 [Page 3]
Internet-Draft Bayesian Location Identifier October 2010
Normal distributions, and Particle Filters. These filters are
briefly described in the following.
2.1. Kalman Filters
A Kalman Filter uses a system model to estimate the probability of
changes. This data is combined with a model of measurement data and
control input, if any, to estimate the true value of the parameters
under study. It only allows linear relations between filter
variables and assumes Gaussian noise distributions. Despite that, it
is very robust in many applications.
The result of a Kalman filter is a posteriori state vector (for
example a location) and a posteriori estimated covariance. The state
is given by a vector $\hat{x}_{k|k}$ and the covariance by
$P_{k|k}$. Both estimates are given for the time index $k$ [2]. If
the vector has a dimension of $d$ (for example 3 for xyz), then the
covariance matrix has a size of d*d.
We suggest that, as PIDF-LO object, all these three variables shall
be transmitted to indicate a position estimate, its distribution,
and the time of measurement.
Also, this format should work well for non-linear filters such as
the Extended or Unscented Kalman Filter.
2.2. Particle Filter
Particle Filter, also called sequential Monte Carlo methods (SMC),
have the advantage that arbitrary distributions can be approximated
[3]. As such, they approximate Bayesian models, which consist of
probability distribution functions, which define the degree of
"believe" to which a particular value is true.
Particle filters approximate probability distribution function with
a number of particles. More particles are placed at positions that
are more likely. Each particle has Dirac shape.
The a posteriori state of a particle filter is approximated by $M$
particles called $x^{(M)}_i$, which are weighted with $w^{(m)}_i$.
The PIDF-LO transmission object should contain the particles, their
weights and again the time index k.
Hoene Expires April 14, 2011 [Page 4]
Internet-Draft Bayesian Location Identifier October 2010
2.3. Gaussian Sum Particle Filters
Here we assume that the probability distributions are described by
the sum of normal distributions [4]. As such, it can be seen as the
combination of two previously mentioned filtering approaches.
The a posteriori state of a Gaussian Sum Filter is approximated by
$M$ Gaussian distributions called $$\hat{x}^{(M)}_k$, which are
weighted with $w^{(m)}_k$ and have distributions described by
covariance matrices $P^{(M)}_{k|k}$.
Again, all those parameters shall be transmitted.
3. Coordinate System and Datum
Any location is relative to a frame of reference. The frame of
reference defines the position, orientation and other properties of
a coordinate system, in which an object is located. A number of
geodetic reference frames have been defined such as WGS84, ETRS89,
or ITRF2005. Typically, they define the reference point and the
orientation of the coordinate system.
In robotics, reference frames are used, too. They are referencing to
a zero point, have an orientation, and may be scaled, mirrored,
rotated. For example, a so called transformation matrix can be
applied to the location vector to transform coordinate systems.
Commonly in navigation, besides Carthesian also Polar coordinate
systems are used. In addition, a polar coordinate system has the
benefit that - for example - circular bands can be described easily
if the rotating angles have a high uncertainty or are not defined.
In summary, to describe the location of an object, the reference
frame has to be named or defined, and the type of coordinate system
must be given.
4. Examples
This section shows examples on how to transmit the location ID
described above.
4.1. Kalman Filter Results
Assuming, a Kalman filter estimates a position and assigns an
uncertainty to this estimate. Then
Hoene Expires April 14, 2011 [Page 5]
Internet-Draft Bayesian Location Identifier October 2010
<gp:geopriv>
<gp:location-info>
<gs:Kalman srsName="urn:ogc:def:crs:EPSG::?????>
<gml:pos>-34.407242 150.882518 34</gml:pos>
<gml:covariance>
1 0 0
0 4 0
0 0 16
</gml:covariance>
<gms:timestamp>
102000
</gms:timestamp>
</gs:Kalman>
</gp:location-info>
</gp:geopriv>
defines a point at [-34.407242, 150.882518, 34] that has a Gaussian
distribution with the standard deviation of 1, 4 and 16 for the X,
Y, and Z-axes.
In addition, it states that the location has been estimated at a
time stamp defined by the time index 102000.
4.2. Particle Filter Results
Next, we assume that a Particle Filter has calculated three
particles. Then
<gp:geopriv>
<gp:location-info>
<gs:Particle srsName="urn:ogc:def:crs:EPSG::?????>
<gml:particleList>
-34.407242 150.882518 34 0.5
-34.500000 150.000000 34 0.25
-34.400000 151.000000 34 0.25
</gml:particleList>
</gs:Particle>
</gp:location-info>
</gp:geopriv>
defines a point at [-34.407242, 150.882518, 34] with a weight of
0.5, a point [-34.5,150,34] with a weight of 0.25, and a point at [-
34.4,151,34] with a weight of 0.25.
Hoene Expires April 14, 2011 [Page 6]
Internet-Draft Bayesian Location Identifier October 2010
4.3. Gaussian Sum Filter
Next, we have a Gaussian Sum Filter with two Gaussian distributions.
Then
<gp:geopriv>
<gp:location-info>
<gs:Particle srsName="urn:ogc:def:crs:EPSG::?????>
<gml:particleList>
-34.407242 150.882518 34 0.25
-34.500000 150.000000 34 0.25
</gml:particleList>
<gml:covarianceList>
1 0 0
0 4 0
0 0 16
1 0.5 0.5
0.5 1 0.5
0.5 0.5 1
</gml:covariance>
<gml:particleList>
</gs:Particle>
</gp:location-info>
</gp:geopriv>
defines a multi-vector Gaussian distribution with the center at [-
34.407242, 150.882518, 34], a weight of 0.25, and standard
deviations of 1, 4 and 16. In addition, a second distribution is at
[-34.5, 150, 34] with a weight of 0.25 and a covariance matrix of
[[1 0.5 0.5] [0.5 1 0.5] [0.5 0.5 1]].
In addition, because the sum of weights is lower than 1, we assume
that the position estimate has only a belief of correctness
(according to Bayesian network theory) of 0.5.
4.4. Well-know Reference Frame
Now, we extend the example given in Section 4.1. to well define a
reference frame that is based on the UTM coordinate system.
<gp:geopriv>
<gp:location-info name="Reference Point ID=0123456789">
<gs:ReferenceFrame>
UTM zone=32U
EVRS2000
</gs:ReferenceFrame>
<gs:Kalman srsName="urn:ogc:def:crs:EPSG::?????>
Hoene Expires April 14, 2011 [Page 7]
Internet-Draft Bayesian Location Identifier October 2010
<gml:x>-34.407242</gml:x>
<gml:y>150.882518</gml:y>
<gml:z>34</gml:z>
<gml:covariance>
1 0 0
0 4 0
0 0 16
</gml:covariance>
<gms:timestamp>
102000
</gms:timestamp>
</gs:Kalman>
</gp:location-info>
</gp:geopriv>
Here, the reference frame for the X and Y axes is given by an UTM
map in the zone 32U (western part of Germany) and the height (Z
axis) is given by the European Vertical Reference System (EVRS)
based on the Normaal Amsterdams Peil (NAP).
In addition, we name this location "Reference Point ID=0123456789".
4.5. Relative Datum
Next, we assume that a reference frame is defined. This example is
based on the particle filter given in Section 4.2.
<gp:geopriv>
<gp:location-info name="Reference Point ID=0123456789">
<gs:ReferenceFrameDefinition>
"Reference Point ID=0123456789"
1 0 0 0
0 0 -1 0
0 1 0 0
0 0 0 1
carthesian
</gs:ReferenceFrameDefinition>
<gs:Particle srsName="urn:ogc:def:crs:EPSG::?????>
<gml:particleList>
-34.407242 150.882518 34 0.5
-34.500000 150.000000 34 0.25
-34.400000 151.000000 34 0.25
</gml:particleList>
</gs:Particle>
</gp:location-info>
</gp:geopriv>
Hoene Expires April 14, 2011 [Page 8]
Internet-Draft Bayesian Location Identifier October 2010
The new coordinates are based on the reference point given in the
previous section but it is rotated by 90 degree about their common
normal, from old Z axis to new Z axis.
5. Security Considerations
Security issues have not yet been identified.
6. IANA Considerations
Well-known reference systems must be named or numbered. Thus might
require a registration at IANA.
7. Conclusions
This initial draft presented a transmission format for uncertain,
relative and transformed location estimates.
It is aim as a basis of discussion, because we believe that
uncertainty shall be directly presented by the results of algorithms
that determine uncertainty.
Questions that need to be address are:
o Are the most common filter types covered?
o Is the transmission format efficient? Especially, if many
particle needs to be transmitted an XML description might cause
too much overhead. Instead, a generic XML compression such as
Binary XML can be used or an application-specific compression
algorithm can be defined.
o Does the representation of relative and transformation reference
systems fit into the GEOPRIV framework?
o Shall the time be given as an index or as a fourth dimension?
Any comments to enhance this draft are highly welcomed.
8. References
8.1. Informative References
[1] M. Thomson, J. Winterbottom, "Representation of Uncertainty
and Confidence in PIDF-LO", draft-thomson-geopriv-uncertainty-
05, work in progress, June 1, 2010.
Hoene Expires April 14, 2011 [Page 9]
Internet-Draft Bayesian Location Identifier October 2010
[2] Wikipedia contributors, "Kalman filter", Publisher: Wikipedia,
The Free Encyclopedia, Date of last revision: 7 October 2010
15:52 UTC,
http://en.wikipedia.org/w/index.php?title=Kalman_filter&oldid=
389338611
[3] Wikipedia contributors, "Particle filter", Publisher:
Wikipedia, The Free Encyclopedia, Date of last revision: 24
September 2010 22:18 UTC,
http://en.wikipedia.org/w/index.php?title=Particle_filter&oldi
d=386830379
[4] J.H. Kotecha, P.M. Djuric, "Gaussian sum particle filtering",
IEEE Transactions on Signal Processing, Volume: 51, Issue:10,
pages 2602 - 2612, Oct. 2003.
Hoene Expires April 14, 2011 [Page 10]
Internet-Draft Bayesian Location Identifier October 2010
Authors' Addresses
Christian Hoene
Universitaet Tuebingen
WSI-ICS
Sand 13
72076 Tuebingen
Germany
Phone: +49 7071 2970532
Email: hoene@uni-tuebingen.de
Andreas Krebs
Universitaet Tuebingen
WSI
Sand 13
72076 Tuebingen
Germany
Phone: +49 7071 2977476
Email: krebs@informatik.uni-tuebingen.de
Christoph Behle
Universitaet Tuebingen
WSI
Sand 13
72076 Tuebingen
Germany
Phone: +49 7071 2977565
Email: behlec@informatik.uni-tuebingen.de
Mark Schmidt
Universitaet Tuebingen
WSI-ICS
Sand 13
72076 Tuebingen
Germany
Phone: +49 7071 2970510
Email: mark.schmidt@wsii.uni-tuebingen.de
Hoene Expires April 14, 2011 [Page 11]
