GEOPRIV                                                       M. Thomson
Internet-Draft                                           J. Winterbottom
Updates: 3693 (if approved)                                       Andrew
Intended status: Standards Track                       November 12, 2007
Expires: May 15, 2008


        Representation of Uncertainty and Confidence in PIDF-LO
                draft-thomson-geopriv-uncertainty-00.txt

Status of this Memo

   By submitting this Internet-Draft, each author represents that any
   applicable patent or other IPR claims of which he or she is aware
   have been or will be disclosed, and any of which he or she becomes
   aware will be disclosed, in accordance with Section 6 of 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 May 15, 2008.

Copyright Notice

   Copyright (C) The IETF Trust (2007).













Thomson & Winterbottom    Expires May 15, 2008                  [Page 1]


Internet-Draft          Uncertainty & Confidence           November 2007


Abstract

   The key concepts of uncertainty and confidence as they pertain to
   location information are defined.  A form for the representation of
   confidence in Presence Information Data Format - Location Object
   (PIDF-LO) is described, optionally including the form of the
   uncertainty.  Suggested methods for the manipulation of location
   estimates that include uncertainty information are outlined.


Table of Contents

   1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  4
     1.1.  Conventions and Terminology  . . . . . . . . . . . . . . .  4
   2.  A General Definition of Uncertainty and Confidence . . . . . .  5
     2.1.  Uncertainty as a Probability Distribution  . . . . . . . .  5
     2.2.  Deprecation of the Terms Precision and Resolution  . . . .  7
     2.3.  Accuracy as a Qualitative Concept  . . . . . . . . . . . .  7
   3.  Uncertainty in Location  . . . . . . . . . . . . . . . . . . .  9
     3.1.  Representation of Uncertainty and Confidence in PIDF-LO  .  9
     3.2.  Uncertainty and Confidence for Civic Addresses . . . . . . 11
     3.3.  DHCP Location Configuration Information and Uncertainty  . 11
   4.  Manipulation of Uncertainty  . . . . . . . . . . . . . . . . . 12
     4.1.  Reduction of a Location Estimate to a Point  . . . . . . . 12
       4.1.1.  Centroid Calculation . . . . . . . . . . . . . . . . . 13
     4.2.  Increasing and Decreasing Uncertainty and Confidence . . . 17
       4.2.1.  Rectangular Distributions  . . . . . . . . . . . . . . 18
       4.2.2.  Normal Distributions . . . . . . . . . . . . . . . . . 18
     4.3.  Determining Whether a Location is Within a Given Region  . 19
       4.3.1.  Determining the Area of Overlap for Two Circles  . . . 20
     4.4.  Obfuscation of Location Estimates for Privacy Reasons  . . 21
   5.  Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
     5.1.  Reduction to a Point or Circle . . . . . . . . . . . . . . 23
     5.2.  Increasing and Decreasing Confidence . . . . . . . . . . . 26
     5.3.  Matching Location Estimates to Regions of Interest . . . . 26
     5.4.  Obfuscating Location Estimates . . . . . . . . . . . . . . 26
   6.  Confidence Schema  . . . . . . . . . . . . . . . . . . . . . . 28
   7.  Security Considerations  . . . . . . . . . . . . . . . . . . . 29
   8.  IANA Considerations  . . . . . . . . . . . . . . . . . . . . . 30
     8.1.  URN Sub-Namespace Registration for
           urn:ietf:params:xml:ns:geopriv:conf  . . . . . . . . . . . 30
     8.2.  XML Schema Registration  . . . . . . . . . . . . . . . . . 30
   9.  Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 31
   Appendix A.  Conversion Between Cartesian and Geodetic
                Coordinates . . . . . . . . . . . . . . . . . . . . . 32
   Appendix B.  Calculating the Upward Normal of a Polygon  . . . . . 34
   10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 35
     10.1. Normative References . . . . . . . . . . . . . . . . . . . 35



Thomson & Winterbottom    Expires May 15, 2008                  [Page 2]


Internet-Draft          Uncertainty & Confidence           November 2007


     10.2. Informative References . . . . . . . . . . . . . . . . . . 35
   Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 37
   Intellectual Property and Copyright Statements . . . . . . . . . . 38
















































Thomson & Winterbottom    Expires May 15, 2008                  [Page 3]


Internet-Draft          Uncertainty & Confidence           November 2007


1.  Introduction

   Location information represents an estimation of the position of a
   Target.  Under ideal circumstances, a location estimate precisely
   reflects the actual location of the Target.  In reality, there are
   many factors that introduce errors into the measurements that are
   used to determine location estimates.

   The process by which measurements are combined to generate a location
   estimate is outside of the scope of work within the IETF.  However,
   the results of such a process are carried in IETF data formats and
   protocols.  This document outlines how uncertainty, and its
   associated datum, confidence, are expressed and interpreted.

   The goal of this document is to provide a common nomenclature for
   discussing uncertainty.  An xml format for expressing confidence, a
   datum previously inexpressible in the Presence Information Data
   Format - Location Object (PIDF-LO), is defined.

   This document also provides guidance on how to use location
   information that includes uncertainty.  Methods for expanding or
   reducing uncertainty to obtain a required level of confidence are
   described.  Methods for determining the probability that a Target is
   within a specified region based on their location estimate are
   described.  These methods are simplified by making certain
   assumptions about the location estimate and are designed to be
   applicable to location estimates in a relatively small area.

1.1.  Conventions and Terminology

   This document assumes a basic understanding of the principles of
   mathematics, particularly statistics and geometry.

   Some terminology is borrowed from [RFC3693].

   Mathematical formulae are presented using the following notation: add
   "+", subtract "-", multiply "*", divide "/", power "^" and absolute
   value "|x|".  Precedence is indicated using parentheses.
   Mathematical functions are represented by common abbreviations:
   square root "sqrt", sine "sin", cosine "cos", inverse cosine "acos",
   tangent "tan", inverse tangent "atan", inverse error function
   "erfinv".

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
   document are to be interpreted as described in [RFC2119].





Thomson & Winterbottom    Expires May 15, 2008                  [Page 4]


Internet-Draft          Uncertainty & Confidence           November 2007


2.  A General Definition of Uncertainty and Confidence

   Uncertainty, as a general concept, is a product of the limitations of
   measurement.  In measuring any observable quantity, errors from a
   range of sources affect the result.

   When quantifying the impact of measurement errors, two values are
   used.  The first value expresses the magnitude of the possible error,
   which is the estimated _uncertainty_ value.  Uncertainty is most
   often expressed as a range in the same units as the result.  The
   second value is _confidence_, which estimates the probability that
   the true value lies within the extents defined by the uncertainty.

   In the following example, the result is shown with a range specified
   by a nominal value and an uncertainty value.

      e.g. x = 1.00742 +/- 0.0043 meters at 95% confidence

   In other words, the true value of "x" is 95% likely to be between
   1.00312 and 1.01172 meters.

   Uncertainty and confidence for location estimates can be derived in a
   number of ways.  It is out of the scope of this document to describe
   methods for determining uncertainty.  [ISO.GUM] and [NIST.TN1297]
   provide guidelines for managing and manipulating measurement
   uncertainty.

2.1.  Uncertainty as a Probability Distribution

   It is helpful to think of the uncertainty and confidence as defining
   a probability density function (PDF).  The probability density
   indicates the probability that the true value lies at any one point.
   The shape of the probability distribution depends on the method that
   is used to determine the result.  Two probability density functions
   are considered in this document:

   o  The normal PDF (also referred to as a Gaussian PDF) is used where
      a large number of small random factors contribute to errors.  The
      value used for uncertainty in a normal PDF is related to the
      standard deviation of the distribution.

   o  A rectangular PDF is used where the errors are known to be
      consistent across a limited range.  The value used for uncertainty
      where a rectangular PDF is known is the half-width of the
      distribution; that is, half the width of the distribution.

   Each of these probability density functions can be characterized by
   its center point, or mean, and its width.  For a normal distribution,



Thomson & Winterbottom    Expires May 15, 2008                  [Page 5]


Internet-Draft          Uncertainty & Confidence           November 2007


   uncertainty and confidence together are related to the standard
   deviation (see Section 4.2).  For a rectangular distribution, half of
   the width of the distribution is used.

   Figure 1 shows a normal and rectangular probability density function
   with the mean (m) and standard deviation (s) labelled.  The half-
   width (h) of the rectangular distribution is also indicated.

                                *****             *** Normal PDF
                              **  :  **           --- Rectangular PDF
                            **    :    **
                           **     :     **
                ,---------*---------------*---------.
                |        **       :       **        |
                |       **        :        **       |
                |      * <-- s -->:          *      |
                |     * :         :         : *     |
                |    **           :           **    |
                |   *   :         :         :   *   |
                |  *              :              *  |
                |**     :         :         :     **|
               **                 :                 **
            *** |       :         :         :       | ***
        *****   |                 :<------ h ------>|   *****
    .****-------+.......:.........:.........:.......+-------*****.
                                  m

      Figure 1: Normal and Rectangular Probability Density Functions

   In relation to a PDF, uncertainty represents a certain range of
   values and confidence is the probability that the true value is found
   within that range.  Confidence is defined as the integral of the PDF
   over the range represented by the uncertainty.

      The probability of the actual value falling between two points is
      found by finding the area under the curve between the points (that
      is, the integral of the curve between the points).  For any given
      PDF, the area under the curve for the entire range from negative
      infinity to positive infinity is 1 or (100%).  Therefore, the
      confidence over any interval of uncertainty is always less than
      100%.

   Figure 2 shows how confidence is determined for a normal
   distribution.  The area of the shaded region gives the confidence (c)
   for the interval between "m-u" and "m+u".






Thomson & Winterbottom    Expires May 15, 2008                  [Page 6]


Internet-Draft          Uncertainty & Confidence           November 2007


                                *****
                              **:::::**
                            **:::::::::**
                           **:::::::::::**
                          *:::::::::::::::*
                         **:::::::::::::::**
                        **:::::::::::::::::**
                       *:::::::::::::::::::::*
                      *:::::::::::::::::::::::*
                     **:::::::::::::::::::::::**
                    *:::::::::::: c ::::::::::::*
                   *:::::::::::::::::::::::::::::*
                 **|:::::::::::::::::::::::::::::|**
               **  |:::::::::::::::::::::::::::::|  **
            ***    |:::::::::::::::::::::::::::::|    ***
        *****      |:::::::::::::::::::::::::::::|      *****
    .****..........!:::::::::::::::::::::::::::::!..........*****.
                   |              |              |
                 (m-u)            m            (m+u)

               Figure 2: Confidence as the Integral of a PDF

   It can be seen from these diagrams that, when expressing uncertainty,
   the value for uncertainty is the range of values and confidence is
   the probability that the true value is found within that range.

   In Section 4.2, methods are described for manipulating uncertainty
   and confidence if the shape of the PDF is known.

2.2.  Deprecation of the Terms Precision and Resolution

   The terms _Precision_ and _Resolution_ are defined in RFC 3693
   [RFC3693].  These definitions were intended to provide a common
   nomenclature for discussing uncertainty; however, these particular
   terms have many different uses in other fields and their definitions
   are not sufficient to avoid confusion about their meaning.  These
   terms MUST NOT be used in relation to quantitative concepts when
   discussing uncertainty and confidence in relation to location
   information.

2.3.  Accuracy as a Qualitative Concept

   Uncertainty and confidence are quantitative concepts.  The term
   _Accuracy_ is useful in describing, qualitatively, the general
   concepts of location information.  Accuracy MAY be used as a general
   term when describing location estimates.  Accuracy MUST NOT be used
   in a quantitative context.




Thomson & Winterbottom    Expires May 15, 2008                  [Page 7]


Internet-Draft          Uncertainty & Confidence           November 2007


   For instance, it could be appropriate to say that a location estimate
   with uncertainty "X" is more accurate than a location estimate with
   uncertainty "2X" at the same confidence.  It is not appropriate to
   assign a number to "accuracy", nor is it appropriate to refer to any
   component of uncertainty or confidence as "accuracy".  That is, to
   say that the "accuracy" for the first location estimate is "X" would
   be an erroneous use of this term.












































Thomson & Winterbottom    Expires May 15, 2008                  [Page 8]


Internet-Draft          Uncertainty & Confidence           November 2007


3.  Uncertainty in Location

   A _location estimate_ is the result of location determination.  A
   location estimate is subject to uncertainty like any other
   observation.  However, unlike a simple measure of a one dimensional
   property like length, a location estimate is specified in two or
   three dimensions.

   Uncertainty in a single dimension is expressed as a range; that is, a
   length of uncertainty in one dimension.  Locations in two or three
   dimensional space are expressed as a subset of that space, either an
   area or volume of uncertainty.  In simple terms, areas or volumes can
   be formed by the combination of two or three ranges, or more complex
   shapes could be described.

   This document uses the term _region of uncertainty_ to refer to the
   uncertainty of a location estimate expressed either as an area or
   volume.

3.1.  Representation of Uncertainty and Confidence in PIDF-LO

   A set of shapes that can be used for the expression of uncertainty in
   location estimates are described in [GeoShape].  These shapes are the
   recommended form for the representation of uncertainty in PIDF-LO
   [RFC4119] documents.  However, these shapes do not include an
   indication of confidence.

   A schema defining a confidence element is included in Section 6.
   This element also includes an optional parameter that defines the
   PDF.

   Absence of uncertainty information in a PIDF-LO document does not
   indicate that there is no uncertainty in the location estimate.
   Uncertainty might not have been calculated for the estimate, or it
   may be withheld for privacy purposes.

   The confidence element is included within the "location-info" element
   of the PIDF-LO.  The PIDF-LO document in Figure 3 includes a
   representation of uncertainty as a circular area.  The confidence
   element (on the line marked with a comment) indicates that the
   confidence is 67% and that it follows a normal distribution.










Thomson & Winterbottom    Expires May 15, 2008                  [Page 9]


Internet-Draft          Uncertainty & Confidence           November 2007


     <pidf:presence
         xmlns:pidf="urn:ietf:params:xml:ns:pidf"
         xmlns:dm="urn:ietf:params:xml:ns:pidf:data-model"
         xmlns:gp="urn:ietf:params:xml:ns:pidf:geopriv10"
         xmlns:gs="http://www.opengis.net/pidflo/1.0"
         xmlns:gml="http://www.opengis.net/gml"
         xmlns:con="urn:ietf:params:xml:ns:pidf:geopriv:conf"
         entity="pres:alice@example.com">
       <dm:device id="sg89ab">
         <pidf:status>
           <gp:geopriv>
             <gp:location-info>
               <gs:Circle srsName="urn:ogc:def:crs:EPSG::4326">
                 <gml:pos>42.5463 -73.2512</gml:pos>
                 <gs:radius uom="urn:ogc:def:uom:EPSG::9001">
                   850.24
                 </gs:radius>
               </gs:Circle>
   <!-- c -->  <con:confidence pdf="normal">67</con:confidence>
             </gp:location-info>
             <gp:usage-rules/>
           </gp:geopriv>
         </pidf:status>
         <dm:deviceID>mac:010203040506</dm:deviceID>
       </dm:device>
     </pidf:presence>

         Figure 3: Example PIDF-LO with Confidence and Uncertainty

   Where uncertainty information is provided, but the confidence element
   is not, the confidence is assumed to be 95%
   [I-D.ietf-geopriv-pdif-lo-profile].  If only a point is included,
   confidence is 0% and the confidence element SHOULD be omitted.

   Three probability distribution functions can be described using the
   confidence parameter.  The "pdf" attribute value SHOULD only be
   included if known, but it is acknowledged that each PDF is an
   approximation only - as are all values relating to uncertainty.  The
   PDF is normal if there are a large number of small, independent
   sources of error; and rectangular if all points within the area have
   roughly equal probability of being the actual location of the Target;
   otherwise, the PDF MUST be set to unknown.

   In order to support the functions provided in this document, Location
   Generators MUST ensure that confidence is equal in each dimension
   when generating location information.  See Section 4.2 for more
   details.




Thomson & Winterbottom    Expires May 15, 2008                 [Page 10]


Internet-Draft          Uncertainty & Confidence           November 2007


3.2.  Uncertainty and Confidence for Civic Addresses

   Civic addresses [I-D.ietf-geopriv-revised-civic-lo] inherently
   include uncertainty, based on the area of the most precise element
   that is specified.  Uncertainty is effectively defined by the
   presence or absence of elements -- elements that are not present are
   deemed to be uncertain.  Indicating confidence for a civic address is
   useful, however values of other than the default (95%) are not
   expected and manipulation of a civic address based on confidence is
   difficult.

   It is RECOMMENDED that confidence not be indicated for civic
   addresses and that the default of 95% is always assumed.  The methods
   described in Section 4.2 for manipulating uncertainty do not apply to
   civic location information.  Uncertainty MAY be increased by removing
   elements, but unless additional confidence information is available,
   confidence MUST NOT be increased as a consequence.

3.3.  DHCP Location Configuration Information and Uncertainty

   Location information is often measured in two or three dimensions;
   expressions of uncertainty in one dimension only are rare.  The
   "resolution" parameters in [RFC3825] provide an indication of
   uncertainty in one dimension.

   [RFC3825] defines a means for representing uncertainty, but a value
   for confidence is not specified.  A default value of 95% confidence
   can be assumed for the combination of the uncertainty on each axis.
   That is, the confidence of the resultant rectangular polygon or prism
   is 95%.  The PDF for a DHCP result is unknown.





















Thomson & Winterbottom    Expires May 15, 2008                 [Page 11]


Internet-Draft          Uncertainty & Confidence           November 2007


4.  Manipulation of Uncertainty

   This section deals with manipulation of location information that
   contains uncertainty.

   The following rules generally apply when manipulating location
   information:

   o  Where calculations are performed on coordinate information, these
      should be performed in Cartesian space and the results converted
      back to latitude, longitude and altitude.  A method for converting
      to and from Cartesian coordinates is included in Appendix A.

   o  Normal rounding rules do not apply when rounding uncertainty.
      When rounding, uncertainty is always rounded up and confidence is
      always rounded down (see [NIST.TN1297]).  Note that manipulating
      uncertainty uses non-reversible operations and that each
      manipulation can result in the loss of some information.

4.1.  Reduction of a Location Estimate to a Point

   Manipulating location estimates that include uncertainty information
   requires additional complexity in systems.  In some cases, systems
   only operate on definitive values, that is, a single point.

   This section describes algorithms for reducing location estimates to
   a simple form without uncertainty information.  Having a consistent
   means for reducing location estimates allows for interaction between
   applications that are able to use uncertainty information and those
   that cannot.

      Note: Reduction of a location estimate to a point constitutes a
      reduction in information.  Removing uncertainty information can
      degrade results in some applications.  Also, there is a natural
      tendency to misinterpret a point location as representing a
      location without uncertainty.  This could lead to more serious
      errors.  Therefore, these algorithms should only be applied where
      necessary.

   Several different approaches can be taken when reducing a location
   estimate to a point; each method is equally valid, depending on the
   assumptions that are made.  For any given region of uncertainty,
   selecting an arbitrary point within the area could be considered
   valid; however, given the aforementioned problems with point
   locations, a more rigorous approach is appropriate.

   Given a result with a known distribution, selecting the point within
   the area that has the highest probability is a more rigorous method.



Thomson & Winterbottom    Expires May 15, 2008                 [Page 12]


Internet-Draft          Uncertainty & Confidence           November 2007


   Alternatively, a point could be selected that minimizes the probable
   error.  For a rectangular distribution, the centroid of the area or
   volume minimizes error.  Minimizing the error for a normal
   distribution is more difficult, but assuming that the normal
   distribution is centered in the region, the centroid is also the
   point with highest probability.

   In order to reduce a region of uncertainty to a single point, the
   centroid of the region is found.  A location estimate that is
   represented as a point has a confidence of 0%, so no confidence
   information is retained if this conversion is performed.

4.1.1.  Centroid Calculation

   For regular shapes, such as Circle, Sphere, Ellipse and Ellipsoid,
   this approach equates to the center point of the region.  For regions
   of uncertainty that are expressed as regular (for instance,
   rectangular) Polygons and Prisms the center point is also the most
   appropriate selection.

   For the Arc-Band shape and non-regular Polygons and Prisms, selecting
   the centroid of the area or volume minimizes the overall error.  This
   assumes a rectangular distribution; the difference arising from
   different distributions is considered acceptable.

   Note that the centroid of a Polygon or Arc-Band shape is not
   necessarily within the region of uncertainty.

4.1.1.1.  Arc-Band Centroid

   The centroid of the Arc-Band shape is found along a line that bisects
   the arc.  The centroid can be found at the following distance from
   the starting point of the arc-band (assuming an arc-band with an
   inner radius of "r", outer radius "R", start angle "a", and opening
   angle "o"):

      d = 4 * sin(o/2) * (R*R + R*r + r*r) / (3*o*(R + r))

   This point can be found along the line that bisects the arc; that is,
   the line at an angle of "a + (o/2)".  Negative values are possible if
   the angle of opening is greater than 180 degrees; negative values
   indicate that the centroid is found along the angle
   "a + (o/2) + 180".

4.1.1.2.  Polygon Centroid

   Calculating a centroid for the Polygon and Prism shapes is more
   complex.  Polygons that are specified using geodetic coordinates are



Thomson & Winterbottom    Expires May 15, 2008                 [Page 13]


Internet-Draft          Uncertainty & Confidence           November 2007


   not necessarily coplanar.  For Polygons that are specified without an
   altitude, choose a value for altitude before attempting this process;
   an altitude of 0 is acceptable.

      The method described in this section is simplified by assuming
      that the surface of the earth is locally flat.  This method
      degrades as polygons become larger; see [GeoShape] for
      recommendations on polygon size.

   The polygon is translated to a new coordinate system that has an x-y
   plane roughly parallel to the polygon.  This enables the elimination
   of z-axis values and calculating a centroid can be done using only x
   and y coordinates.  This requires that the upward normal for the
   polygon is known.

   To translate the polygon coordinates, apply the process described in
   Appendix B to find the normal vector "N = [Nx,Ny,Nz]".  From this
   vector, select two vectors that are perpendicular to this vector and
   combine these into a transformation matrix.  If "Nx" and "Ny" are
   non-zero, the vectors in Figure 4 can be used, given
   "p = sqrt(Nx^2 + Ny^2)".  More transformations are provided later in
   this section for cases where "Nx" or "Ny" are zero.

          [   -Ny/p     Nx/p     0  ]         [ -Ny/p  -Nx*Nz/p  Nx ]
      T = [ -Nx*Nz/p  -Ny*Nz/p   p  ]    T' = [  Nx/p  -Ny*Nz/p  Ny ]
          [    Nx        Ny      Nz ]         [   0      p       Nz ]
                 (Transform)                    (Reverse Transform)

               Figure 4: Recommended Transformation Matrices

   To apply a transform to each point in the polygon, form a matrix from
   the ECEF coordinates and use matrix multiplication to determine the
   translated coordinates.

      [   -Ny/p     Nx/p     0  ]   [ x[1]  x[2]  x[3]  ...  x[n] ]
      [ -Nx*Nz/p  -Ny*Nz/p   p  ] * [ y[1]  y[2]  y[3]  ...  y[n] ]
      [    Nx        Ny      Nz ]   [ z[1]  z[2]  z[3]  ...  z[n] ]

          [ x'[1]  x'[2]  x'[3]  ... x'[n] ]
        = [ y'[1]  y'[2]  y'[3]  ... y'[n] ]
          [ z'[1]  z'[2]  z'[3]  ... z'[n] ]

                         Figure 5: Transformation

   Alternatively, direct multiplication can be used to achieve the same
   result:





Thomson & Winterbottom    Expires May 15, 2008                 [Page 14]


Internet-Draft          Uncertainty & Confidence           November 2007


      x'[i] = -Ny * x[i] / p + Nx * y[i] / p

      y'[i] = -Nx * Nz * x[i] / p - Ny * Nz * y[i] / p + p * z[i]

      z'[i] = Nx * x[i] + Ny * y[i] + Nz * z[i]

   The first and second rows of this matrix ("x'" and "y'") contain the
   values that are used to calculate the centroid of the polygon.  To
   find the centroid of this polygon, first find the area using:

      A = sum from i=1..n of (x'[i]*y'[i+1]-x'[i+1]*y'[i]) / 2

   For these formulae, treat each set of coordinates as circular, that
   is "x'[0] == x'[n]" and "x'[n+1] == x'[1]".  Based on the area, the
   centroid along each axis can be determined by:

      Cx' = sum (x'[i]+x'[i+1]) * (x'[i]*y'[i+1]-x'[i+1]*y'[i]) / (6*A)

      Cy' = sum (y'[i]+y'[i+1]) * (x'[i]*y'[i+1]-x'[i+1]*y'[i]) / (6*A)

   The third row contains a distance from a plane parallel to the
   polygon.  If the polygon is coplanar, then the values for "z'" are
   identical; however, the constraints recommended in
   [I-D.ietf-geopriv-pdif-lo-profile] mean that this is rarely the case.
   To determine "Cz'", average these values:

      Cz' = sum z'[i] / n

   Once the centroid is known in the transformed coordinates, these can
   be transformed back to the original coordinate system.  The reverse
   transformation is shown in Figure 6.

      [ -Ny/p  -Nx*Nz/p  Nx ]     [       Cx'        ]   [ Cx ]
      [  Nx/p  -Ny*Nz/p  Ny ]  *  [       Cy'        ] = [ Cy ]
      [   0        p     Nz ]     [ sum of z'[i] / n ]   [ Cz ]

                     Figure 6: Reverse Transformation

   The reverse transformation can be applied directly as follows:

      Cx = -Ny * Cx' / p - Nx * Nz * Cy' / p + Nx * Cz'

      Cy = Nx * Cx' / p - Ny * Nz * Cy' / p + Ny * Cz'

      Cz = p * Cy' + Nz * Cz'

   The ECEF value "[Cx,Cy,Cz]" can then be converted back to geodetic
   coordinates.  Given a polygon that is defined with no altitude or



Thomson & Winterbottom    Expires May 15, 2008                 [Page 15]


Internet-Draft          Uncertainty & Confidence           November 2007


   equal altitudes for each point, the altitude of the result is reset
   after converting back to a geodetic value.

   The centroid of the Prism shape is found by finding the centroid of
   the base polygon and raising the point by half the height of the
   prism.  This can be added to altitude of the final result;
   alternatively, this can be added to "Cz'", which ensures that
   negative height is correctly applied to polygons that are defined in
   a "clockwise" direction.

   The recommended transforms only apply if "Nx" and "Ny" are non-zero.
   If the normal vector is "[0,0,1]" (that is, along the z-axis), then
   no transform is necessary.  Similarly, if the normal vector is
   "[0,1,0]" or "[1,0,0]", avoid the transformation and use the x and z
   coordinates or y and z coordinates (respectively) in the centroid
   calculation phase.  If either "Nx" or "Ny" are zero, the alternative
   transform matrices in Figure 7 can be used.  The reverse transform is
   the transpose of this matrix.

    if Nx == 0:                              | if Ny == 0:
        [ 0  -Nz  Ny ]       [  0   1  0  ]  |       [ -Nz  0  Nx ]
    T = [ 1   0   0  ]  T' = [ -Nz  0  Ny ]  |   T = [  0   1  0  ] = T'
        [ 0   Ny  Nz ]       [  Ny  0  Nz ]  |       [  Nx  0  Nz ]

               Figure 7: Alternative Transformation Matrices

4.1.1.3.  Conversion to Circle or Sphere

   The Circle or Sphere are simple shapes that suit a range of
   applications.  A circle or sphere contains fewer units of data to
   manipulate, which simplifies operations on location estimates.

   The simplest method for converting a location estimate to a Circle or
   Sphere shape is to select a center point and find the longest
   distance to any point in the region of uncertainty to that point.
   This distance can be determined based on the shape type:

   Circle/Sphere:  No conversion necessary.

   Ellipse/Ellipsoid:  The greater of either semi-major axis or altitude
      uncertainty.

   Polygon/Prism:  The distance to the furthest vertex of the polygon
      (for a Prism, only check points on the base).







Thomson & Winterbottom    Expires May 15, 2008                 [Page 16]


Internet-Draft          Uncertainty & Confidence           November 2007


   Arc-Band:  The furthest length from the centroid to the points where
      the inner and outer arc end.  This distance can be calculated by
      finding the larger of the two following formulae:

         X = sqrt( ( d - R*cos(o/2) )^2 + R*sin(o/2)^2 )

         x = sqrt( ( d - r*cos(o/2) )^2 + r*sin(o/2)^2 )

   Once the Circle or Sphere shape is found, the associated confidence
   can be increased if the result is known to follow a normal
   distribution.  However, this is a complicated process and provides
   limited benefit.  In many cases it also violates the constraint that
   confidence in each dimension be the same.  It is RECOMMENDED that
   confidence is unchanged when performing this conversion.

   Two dimensional shapes are converted to a Circle; three dimensional
   shapes are converted to a Sphere.  The PDF for a converted shape
   SHOULD be set to "unknown".

   A Sphere shape can be easily converted to a Circle shape by removing
   the altitude component.  The altitude is unspecified for a Circle and
   therefore has unlimited uncertainty.  Therefore, the confidence for
   the Circle is higher than the Sphere.  If desired, the confidence of
   the circle can be increased using the following approximate formula:

      C[circle] >= C[sphere] ^ (2/3)

   "C[circle]" is the confidence of the circle and "C[sphere]" is the
   confidence of the sphere.  For example, a Sphere with a confidence of
   95% is simplified to a Circle of equal radius with confidence of
   96.6%.

4.2.  Increasing and Decreasing Uncertainty and Confidence

   The combination of uncertainty and confidence provide a great deal of
   information about the nature of the data that is being measured.  If
   both uncertainty, confidence and PDF are known, certain information
   can be extrapolated.  In particular, the uncertainty can be scaled to
   meet a certain confidence or the confidence for a particular region
   of uncertainty can be found.

   In general, confidence decreases as the region of uncertainty
   decreases in size and confidence increases as the region of
   uncertainty increases in size.  However, this depends on the PDF.  If
   the region of uncertainty is increased, confidence might increase as
   result, but only if the PDF is normal.  If the region of uncertainty
   is increased during the process of obfuscation (see Section 4.4),
   then the confidence MUST NOT be increased.  If the region of



Thomson & Winterbottom    Expires May 15, 2008                 [Page 17]


Internet-Draft          Uncertainty & Confidence           November 2007


   uncertainty is reduced in size, then the confidence MUST be decreased
   accordingly.

   If the PDF is not known, uncertainty and confidence cannot be
   modified.  Uncertainty can be increased, but only if confidence is
   not increased.

4.2.1.  Rectangular Distributions

   Uncertainty that follows a rectangular distribution can only be
   decreased in size.  Since the PDF is constant over the region of
   uncertainty, the resulting confidence is determined by the following
   formula:

      Cr = Co * Ur / Uo

   Where "Uo" and "Ur" are the sizes of the original and reduced regions
   of uncertainty (either the area or the volume of the region); "Co"
   and "Cb" are the confidence values associated with each region.

   Information is lost by decreasing the region of uncertainty for a
   rectangular distribution.  Once reduced in size, the uncertainty
   region cannot subsequently be increased in size.

4.2.2.  Normal Distributions

   Uncertainty and confidence can be both increased and decreased for a
   normal distribution.  However, the process is more complicated.

   For a normal distribution, uncertainty and confidence are related to
   the standard deviation of the function.  The following function
   defines the relationship between standard deviation, uncertainty and
   confidence along a single axis:

      S[x] = U[x] / ( sqrt(2) * erfinv(C[x]) )

   Where "S[x]" is the standard deviation, "U[x]" is the uncertainty and
   "C[x]" is the confidence along a single axis. "erfinv" is the inverse
   error function.

   Scaling a normal distribution in two dimensions requires several
   assumptions.  Firstly, it is assumed that the distribution along each
   axis is independent.  Secondly, the confidence for each axis is the
   same.  Therefore, the confidence along each axis can be assumed to
   be:

      C[x] = Co ^ (1/n)




Thomson & Winterbottom    Expires May 15, 2008                 [Page 18]


Internet-Draft          Uncertainty & Confidence           November 2007


   Where "C[x]" is the confidence along a single axis and "Co" is the
   overall confidence and "n" is the number of dimensions in the
   uncertainty.

   Therefore, to find the uncertainty for each axis at a desired
   confidence, "Cd", apply the following formula:

      Ud[x] <= U[x] * (erfinv(Cd ^ (1/n)) / erfinv(Co ^ (1/n)))

   For regular shapes, this formula can be applied as a scaling factor
   in each dimension to reach a required confidence.

4.3.  Determining Whether a Location is Within a Given Region

   A number of applications require that a judgement be made about
   whether a Target is within a given region of interest.  Given a
   location estimate with uncertainty, this judgement can be difficult.
   A location estimate represents a probability distribution, and the
   true location of the Target cannot be definitively known.  Therefore,
   the judgement relies on determining the probability that the Target
   is within the region.

   The probability that the Target is within a particular region is
   found by integrating the PDF over the region.  For a normal
   distribution, there are no analytical methods that can be used to
   determine the integral of the two or three dimensional PDF over an
   arbitrary region.  The complexity of numerical methods is also too
   great to be useful in many applications; for example, finding the
   integral of the PDF in two or three dimensions across the overlap
   between the uncertainty region and the target region.  If the PDF is
   unknown, no determination can be made.  When judging whether a
   location is within a given region, uncertainties using these PDFs MAY
   be assumed to be rectangular.  If this assumption is made, the
   confidence SHOULD be scaled to 95%, if possible.

      Note: The selection of confidence has a significant impact on the
      final result.  Only use a different confidence if an uncertainty
      value for 95% confidence cannot be found.

   Given the assumption of a rectangular distribution, the probability
   that a Target is found within a given region is found by first
   finding the area (or volume) of overlap between the uncertainty
   region and the region of interest.  This is multiplied by the
   confidence of the location estimate to determine the probability.
   Figure 8 shows an example of finding the area of overlap between the
   region of uncertainty and the region of interest.





Thomson & Winterbottom    Expires May 15, 2008                 [Page 19]


Internet-Draft          Uncertainty & Confidence           November 2007


                    _.-""""-._
                  .'          `.    _ Region of
                 /              \  /  Uncertainty
              ..+-"""--..        |
           .-'  | :::::: `-.     |
         ,'     | :: Ao ::: `.   |
        /        \ :::::::::: \ /
       /          `._ :::::: _.X
      |              `-....-'   |
      |                         |
      |                         |
       \                       /
        `.                   .'  \_ Region of
          `._             _.'       Interest
             `--..___..--'

          Figure 8: Area of Overlap Between Two Circular Regions

   Once the area of overlap, "Ao", is known, the probability that the
   Target is within the region of interest, "Pi", is:

      Pi = Co * Ao / Au

   Given that the area of the region of uncertainty is "Au" and the
   confidence is "Co".

   Specific applications SHOULD make recommendations about the
   probability required for conditions.  Without specific
   recommendations, it is RECOMMENDED that the probability be greater
   than 50% before a decision is made.  If a choice of regions of
   interest is necessary, as is required by [I-D.ietf-ecrit-lost], then
   the region with the highest probability is selected.

4.3.1.  Determining the Area of Overlap for Two Circles

   Determining the area of overlap between two arbitrary shapes is a
   non-trivial process.  Reducing areas to circles (see Section 4.1.1.3)
   enables the application of the following process.

   Given the radius of the first circle "r", the radius of the second
   circle "R" and the distance between their center points "d", the
   following set of formulas provide the area of overlap "Ao".

   o  If the circles don't overlap, that is "d >= r+R", "Ao" is zero.

   o  If one of the two circles is entirely within the other, that is
      "d <= |r-R|", the area of overlap is the area of the smaller
      circle.



Thomson & Winterbottom    Expires May 15, 2008                 [Page 20]


Internet-Draft          Uncertainty & Confidence           November 2007


   o  Otherwise, if the circles partially overlap, that is "d < r+R" and
      "d > |r-R|", find "Ao" using:

         a = (r^2 - R^2 + d^2)/(2*d)

         Ao = r^2*acos(a/r) + R^2*acos((d - a)/R) - d*sqrt(r^2 - a^2)

   A value for "d" can be determined by converting the center points to
   Cartesian coordinates.  However, given the inherent imprecision of
   this method, approximate techniques based on unconverted values MAY
   be used.

4.4.  Obfuscation of Location Estimates for Privacy Reasons

   [RFC3693] and [RFC3694] describe operations on location information
   that obscure the real location of a Target to protect privacy.
   Typically, obfuscation methods operate on a single point and don't
   allow for the associated region of uncertainty.  This section
   describes a method that extends single point methods, while the
   confidence is retained by increasing the size of the region of
   uncertainty.

   Single point obfuscation methods rely on moving the point by a
   constrained distance.  The maximum distance is set by preference, but
   the actual distance chosen varies randomly, or, as in
   [I-D.ietf-geopriv-policy], the distance is set by finding the nearest
   multiple of the inverse of the input value.

   To obfuscate a location estimate that contains uncertainty
   information the following procedure can be used:

   1.  Optionally, the shape could be translated to a Circle or Sphere
       shape.  This simplifies later steps, but could be considered
       additional obfuscation.

   2.  Any single point within the region of uncertainty is chosen.
       This could be the centroid, but any point can be selected.

   3.  That point is moved using the chosen method of obfuscation.

   4.  Based on the movement of the point, the entire region of
       uncertainty is moved in the same direction and by the same
       distance.  For most shapes, this only requires the movement of a
       single point to achieve; whereas each point of a Polygon needs to
       be moved in the same direction and by the same distance to ensure
       that the shape is retained.





Thomson & Winterbottom    Expires May 15, 2008                 [Page 21]


Internet-Draft          Uncertainty & Confidence           November 2007


   5.  The region of uncertainty is expanded.  In each dimension, the
       region of uncertainty is expanded by the maximum distance that
       the point could have moved.  This expansion is done in both
       directions for each axis.  The expanded region therefore includes
       the original region of uncertainty.

   6.  The PDF is changed to unknown; the confidence is unchanged.

   This process ensures that no information about the original region of
   uncertainty is revealed but the confidence for the final estimate is
   the same as the original.

   For the method described in [I-D.ietf-geopriv-policy], the maximum
   distance SHOULD be calculated at the equator.  That is, the maximum
   distance is given for two-dimensional and three-dimensional
   coordinates is:

      2dmax = sqrt(2)*(6378137*pi) /(r*180)

      3dmax = sqrt(2 * ((6378137*pi) / (r*180))^2 + (1/r)^2)

   This method is functionally equivalent to civic address obfuscation
   that relies on removing the most specific elements, thereby
   increasing uncertainty.



























Thomson & Winterbottom    Expires May 15, 2008                 [Page 22]


Internet-Draft          Uncertainty & Confidence           November 2007


5.  Examples

   This section presents some examples of how to apply the methods
   described in Section 4.

5.1.  Reduction to a Point or Circle

   Alice receives a location estimate from her LIS that contains a
   ellipsoidal region of uncertainty.  This information is provided at
   19% confidence with a normal PDF.  A PIDF-LO extract for this
   information is shown in Figure 9.

     <gp:geopriv>
       <gp:location-info>
         <gs:Ellipsoid srsName="urn:ogc:def:crs:EPSG::4979">
           <gml:pos>-34.407242 150.882518 34</gml:pos>
           <gs:semiMajorAxis uom="urn:ogc:def:uom:EPSG::9001">
             7.7156
           </gs:semiMajorAxis>
           <gs:semiMinorAxis uom="urn:ogc:def:uom:EPSG::9001">
             3.31
           </gs:semiMinorAxis>
           <gs:verticalAxis uom="urn:ogc:def:uom:EPSG::9001">
             28.7
           </gs:verticalAxis>
           <gs:orientation uom="urn:ogc:def:uom:EPSG::9102">
             43
           </gs:orientation>
         </gs:Ellipsoid>
         <con:confidence pdf="normal">19</con:confidence>
       </gp:location-info>
       <gp:usage-rules/>
     </gp:geopriv>

                                 Figure 9

   This information can be reduced to a point simply by extracting the
   center point, that is [-34.407242, 150.882518, 34].  Confidence is
   not applicable to values without uncertainty, so this information is
   no longer useful.

   If some limited uncertainty were required, the estimate could be
   converted into a circle or sphere.  To convert to a sphere, the
   radius is the largest of the semi-major, semi-minor and vertical
   axes; in this case, 28.7 meters.  The confidence remains at 19%; and
   the PDF becomes unknown.

   However, if only a circle is required, the altitude can be dropped as



Thomson & Winterbottom    Expires May 15, 2008                 [Page 23]


Internet-Draft          Uncertainty & Confidence           November 2007


   can the altitude uncertainty (the vertical axis of the ellipsoid),
   resulting in a circle at [-34.407242, 150.882518] of radius 7.7156
   meters.  The confidence of the circle can be expanded to 33%.

   Bob receives a location estimate with a Polygon shape.  This
   information is shown in Figure 10.  No confidence element is present
   in the PIDF-LO, so Bob can assume 95% confidence with an unknown
   distribution.

     <gml:Polygon srsName="urn:ogc:def:crs:EPSG::4326">
       <gml:exterior>
         <gml:LinearRing>
           <gml:posList>
             -33.856625 151.215906 -33.856299 151.215343
             -33.856326 151.214731 -33.857533 151.214495
             -33.857720 151.214613 -33.857369 151.215375
             -33.856625 151.215906
           </gml:posList>
         </gml:LinearRing>
       </gml:exterior>
     </gml:Polygon>

                                 Figure 10

   To convert this to a polygon, each point is firstly assigned an
   altitude of zero and converted to ECEF coordinates (see Appendix A).
   Then a normal vector for this polygon is found (see Appendix B).  The
   results of each of these stages is shown in Figure 11.  Note that the
   numbers shown are all rounded; no rounding is possible during this
   process since rounding would contribute significant errors.





















Thomson & Winterbottom    Expires May 15, 2008                 [Page 24]


Internet-Draft          Uncertainty & Confidence           November 2007


   Polygon in ECEF coordinate space
      (repeated point omitted and transposed to fit):
            [ -4.6470e+06  2.5530e+06  -3.5333e+06 ]
            [ -4.6470e+06  2.5531e+06  -3.5332e+06 ]
    pecef = [ -4.6470e+06  2.5531e+06  -3.5332e+06 ]
            [ -4.6469e+06  2.5531e+06  -3.5333e+06 ]
            [ -4.6469e+06  2.5531e+06  -3.5334e+06 ]
            [ -4.6469e+06  2.5531e+06  -3.5333e+06 ]

   Normal Vector: n = [ -0.72782  0.39987  -0.55712 ]

   Transformation Matrix:
        [ -0.48152  -0.87643   0.00000 ]
    t = [ -0.48828   0.26827   0.83043 ]
        [ -0.72782   0.39987  -0.55712 ]

   Transformed Coordinates:
             [  8.3206e+01  1.9809e+04  6.3715e+06 ]
             [  3.1107e+01  1.9845e+04  6.3715e+06 ]
    pecef' = [ -2.5528e+01  1.9842e+04  6.3715e+06 ]
             [ -4.7367e+01  1.9708e+04  6.3715e+06 ]
             [ -3.6447e+01  1.9687e+04  6.3715e+06 ]
             [  3.4068e+01  1.9726e+04  6.3715e+06 ]

   Two dimensional polygon area: A = 12600 m^2
   Two-dimensional polygon centroid: C' = [ 8.8184e+00  1.9775e+04 ]

   Average of pecef' z coordinates: 6.3715e+06

   Reverse Transformation Matrix:
         [ -0.48152  -0.48828  -0.72782 ]
    t' = [ -0.87643   0.26827   0.39987 ]
         [  0.00000   0.83043  -0.55712 ]

   Polygon centroid (ECEF): C = [ -4.6470e+06  2.5531e+06  -3.5333e+06 ]
   Polygon centroid (Geo): Cg = [ -33.856926  151.215102  -4.9537e-04 ]

                                 Figure 11

   The point conversion for the polygon uses the final result, "Cg",
   ignoring the altitude since the original shape did not include
   altitude.

   To convert this to a circle, take the maximum distance in ECEF
   coordinates from the center point to each of the points.  This
   results in a radius of 99.1 meters.  Confidence for this shape
   follows the original confidence of 95%.




Thomson & Winterbottom    Expires May 15, 2008                 [Page 25]


Internet-Draft          Uncertainty & Confidence           November 2007


5.2.  Increasing and Decreasing Confidence

   The confidence associated with Alice's location estimate is quite low
   for many applications.  Since the estimate is known to follow a
   normal distribution, the method in Section 4.2.2 can be used.  Each
   axis can be scaled by:

      scale = erfinv(0.95^(1/3)) / erfinv(0.19^(1/3)) = 2.9937

   Ensuring that rounding always increases uncertainty, the location
   estimate at 95% includes a semi-major axis of 23.1, a semi-minor axis
   of 10 and a vertical axis of 86.

   Bob's location estimate covers an area of approximately 12600 square
   meters.  If the estimate follows a rectangular distribution, the
   region of uncertainty can be reduced in size.  To find the confidence
   that he is within the smaller area of the concert hall, given by the
   polygon [-33.856473, 151.215257; -33.856322, 151.214973;
   -33.856424, 151.21471; -33.857248, 151.214753;
   -33.857413, 151.214941; -33.857311, 151.215128].  To use this new
   region of uncertainty, find its area using the same translation
   method described in Section 4.1.1.2, which is 4566.2 square meters.
   The confidence associated with the smaller area is therefore 95% *
   4566.2 / 12600 = 34%.

5.3.  Matching Location Estimates to Regions of Interest

   Suppose than a circular area is defined centered at
   [-33.872754, 151.20683] with a radius of 1950 meters.  To determine
   whether Bob is found within this area, we apply the method in
   Section 4.3.  Using the converted Circle shape for Bob's location,
   the distance between these points is found to be 1915.26 meters.  The
   area of overlap between Bob's location estimate and the region of
   interest is therefore 2209 square meters and the area of Bob's
   location estimate is 30853 square meters.  This gives the probability
   that Bob is less than 1950 meters from the selected point as 67.8%.

   Note that if 1920 meters were chosen for the distance from the
   selected point, the area of overlap is only 16196 square meters and
   the confidence is 49.8%.  Therefore, it is more likely that Bob is
   outside the region of interest, despite the center point of his
   location estimate being within the region.

5.4.  Obfuscating Location Estimates

   Alices's Location Server (LS, see [RFC3693]) provides her location
   estimate to a Location Recipient (LR), but the ruleset (see
   [I-D.ietf-geopriv-policy]) that Alice has provided includes an



Thomson & Winterbottom    Expires May 15, 2008                 [Page 26]


Internet-Draft          Uncertainty & Confidence           November 2007


   geodetic transformation.  The rule states that the location
   information is obscured by "r = 100".

   Too apply this rule, a single point is chosen.  In this case the
   center point, [-34.407242, 150.882518, 34], is used.  The result of
   applying the transformation is the point [-34.41, 150.88, 34].  The
   maximum distance that this transform could shift a three dimensional
   point is 1574.3 meters.  The actual distance moved is 383.7 meters,
   but including this information could reveal too more about the
   Alice's position than she might desire.  Therefore, the transformed
   location estimate (given with a confidence of 95%) is shown in
   Figure 12.

     <gs:Ellipse srsName="urn:ogc:def:crs:EPSG::4979">
       <gml:pos>-34.41 150.88 34</gml:pos>
       <gs:semiMajorAxis uom="urn:ogc:def:uom:EPSG::9001">
         1597.4
       </gs:semiMajorAxis>
       <gs:semiMinorAxis uom="urn:ogc:def:uom:EPSG::9001">
         1584.3
       </gs:semiMinorAxis>
       <gs:verticalAxis uom="urn:ogc:def:uom:EPSG::9001">
         1660.3
       </gs:verticalAxis>
       <gs:orientation uom="urn:ogc:def:uom:EPSG::9102">
         43
       </gs:orientation>
     </gs:Ellipse>

                                 Figure 12





















Thomson & Winterbottom    Expires May 15, 2008                 [Page 27]


Internet-Draft          Uncertainty & Confidence           November 2007


6.  Confidence Schema

<?xml version="1.0"?>
<xs:schema
     xmlns:conf="urn:ietf:params:xml:ns:geopriv:conf"
     xmlns:xs="http://www.w3.org/2001/XMLSchema"
     targetNamespace="urn:ietf:params:xml:ns:geopriv:conf"
     elementFormDefault="qualified"
     attributeFormDefault="unqualified">

  <xs:annotation>
    <xs:appinfo
        source="urn:ietf:params:xml:schema:geopriv:conf">
      PIDF-LO Confidence
    </xs:appinfo>
    <xs:documentation source="http://www.ietf.org/rfc/rfcXXXX.txt">
<!-- [[NOTE TO RFC-EDITOR: Please replace above URL with URL of
                       published RFC and remove this note.]] -->
      This schema defines an element that is used for indicating
      confidence in PIDF-LO documents.
    </xs:documentation>
  </xs:annotation>

  <xs:element name="confidence" type="conf:confidenceType"/>
  <xs:complexType name="confidenceType">
    <xs:simpleContent>
      <xs:extension base="conf:confidenceBase">
        <xs:attribute name="pdf" type="conf:pdfType" default="unknown"/>
      </xs:extension>
    </xs:simpleContent>
  </xs:complexType>
  <xs:simpleType name="confidenceBase">
    <xs:restriction base="xs:decimal">
      <xs:minExclusive value="0.0"/>
      <xs:maxExclusive value="100.0"/>
    </xs:restriction>
  </xs:simpleType>
  <xs:simpleType name="pdfType">
    <xs:restriction base="xs:token">
      <xs:enumeration value="unknown"/>
      <xs:enumeration value="normal"/>
      <xs:enumeration value="rectangular"/>
    </xs:restriction>
  </xs:simpleType>
</xs:schema>






Thomson & Winterbottom    Expires May 15, 2008                 [Page 28]


Internet-Draft          Uncertainty & Confidence           November 2007


7.  Security Considerations

   This document describes a parameter that is added to a PIDF-LO.  This
   additional information MUST be treated with the same privacy
   considerations as location information.  See [RFC4119] for details on
   privacy considerations for location information.

   No specific security considerations arise from the algorithms
   described in this document.










































Thomson & Winterbottom    Expires May 15, 2008                 [Page 29]


Internet-Draft          Uncertainty & Confidence           November 2007


8.  IANA Considerations

8.1.  URN Sub-Namespace Registration for
      urn:ietf:params:xml:ns:geopriv:conf

   This section registers a new XML namespace,
   "urn:ietf:params:xml:ns:geopriv:conf", as per the guidelines in
   [RFC3688].

      URI: urn:ietf:params:xml:ns:geopriv:conf

      Registrant Contact: IETF, GEOPRIV working group,
      (geopriv@ietf.org), Martin Thomson (martin.thomson@andrew.com).

      XML:

         BEGIN
           <?xml version="1.0"?>
           <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
             "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
           <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
             <head>
               <title>PIDF-LO Confidence Attribute</title>
             </head>
             <body>
               <h1>Namespace for PIDF-LO Confidence Attribute</h1>
               <h2>urn:ietf:params:xml:ns:geopriv:conf</h2>
   [[NOTE TO IANA/RFC-EDITOR: Please update RFC URL and replace XXXX
       with the RFC number for this specification.]]
               <p>See <a href="[[RFC URL]]">RFCXXXX</a>.</p>
             </body>
           </html>
         END

8.2.  XML Schema Registration

   This section registers an XML schema as per the guidelines in
   [RFC3688].

   URI:  urn:ietf:params:xml:schema:geopriv:conf

   Registrant Contact:  IETF, GEOPRIV working group, (geopriv@ietf.org),
      Martin Thomson (martin.thomson@andrew.com).

   Schema:  The XML for this schema can be found as the entirety of
      Section 6 of this document.





Thomson & Winterbottom    Expires May 15, 2008                 [Page 30]


Internet-Draft          Uncertainty & Confidence           November 2007


9.  Acknowledgements

   Thanks go to Peter Rhodes for his assistance with some particularly
   curly integrals.















































Thomson & Winterbottom    Expires May 15, 2008                 [Page 31]


Internet-Draft          Uncertainty & Confidence           November 2007


Appendix A.  Conversion Between Cartesian and Geodetic Coordinates

   The process of conversion from geodetic (latitude, longitude and
   altitude) to earth-centered, earth-fixed (ECEF) Cartesian coordinates
   is relatively simple.

   In this section, the following constants and derived values are used
   from the definition of WGS84 [WGS84]:

      {radius of ellipsoid} R = 6378137 meters

      {inverse flattening} 1/f = 298.257223563

      {first eccentricity squared} e^2 = f * (2 - f)

      {second eccentricity squared} e'^2 = e^2 * (1 - e^2)

   To convert geodetic coordinates (latitude, longitude, altitude) to
   ECEF coordinates (X, Y, Z), use the following relationships:

      N = R / sqrt(1 - e^2 * sin(latitude)^2)

      X = (N + altitude) * cos(latitude) * cos(longitude)

      Y = (N + altitude) * cos(latitude) * sin(longitude)

      Z = (N*(1 - e^2) + altitude) * sin(latitude)

   The reverse conversion requires more complex computation and most
   methods introduce some error in latitude and altitude.  A range of
   techniques are described in [Convert].  A variant on the method
   originally proposed by Bowring, which results in an acceptably small
   error, is described by the following:

      p = sqrt(X^2 + Y^2)

      r = sqrt(X^2 + Y^2 + Z^2)

      u = atan((1-f) * Z * (1 + e'^2 * (1-f) * R / r) / p)

      latitude = atan((Z + e'^2 * (1-f) * R * sin(u)^3)
      / (p - e^2 * R * cos(u)^3))

      longitude = atan(Y / X)

      altitude = sqrt((p - R * cos(u))^2 + (Z - (1-f) * R * sin(u))^2)

   If the point is near the poles, that is "p < 1", the value for



Thomson & Winterbottom    Expires May 15, 2008                 [Page 32]


Internet-Draft          Uncertainty & Confidence           November 2007


   altitude that this method produces is unstable.  A simpler method for
   determining the altitude of a point near the poles is:

      altitude = |Z| - R















































Thomson & Winterbottom    Expires May 15, 2008                 [Page 33]


Internet-Draft          Uncertainty & Confidence           November 2007


Appendix B.  Calculating the Upward Normal of a Polygon

   For a polygon that is guaranteed to be convex and coplanar, the
   upward normal can be found by finding the vector cross product of
   adjacent edges.

   For more general cases the Newell method of approximation described
   in [Sunday02] may be applied.  In particular, this method can be used
   if the points are only approximately coplanar, and for non-convex
   polygons.

   This process requires a Cartesian coordinate system.  Therefore,
   convert the geodetic coordinates of the polygon to Cartesian, ECEF
   coordinates (Appendix A).  If no altitude is specified, assume an
   altitude of zero.

   This method can be condensed to the following set of equations:

      Nx = sum from i=1..n of (y[i] * (z[i+1] - z[i-1]))

      Ny = sum from i=1..n of (z[i] * (x[i+1] - x[i-1]))

      Nz = sum from i=1..n of (x[i] * (y[i+1] - y[i-1]))

   For these formulae, the polygon is made of points
   "(x[1], y[1], z[1])" through "(x[n], y[n], x[n])".  Each array is
   treated as circular, that is, "x[0] == x[n]" and "x[n+1] == x[1]".

   To translate this into a unit-vector; divide each component by the
   length of the vector:

      Nx' = Nx / sqrt(Nx^2 + Ny^2 + Nz^2)

      Ny' = Ny / sqrt(Nx^2 + Ny^2 + Nz^2)

      Nz' = Nz / sqrt(Nx^2 + Ny^2 + Nz^2)















Thomson & Winterbottom    Expires May 15, 2008                 [Page 34]


Internet-Draft          Uncertainty & Confidence           November 2007


10.  References

10.1.  Normative References

   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", BCP 14, RFC 2119, March 1997.

   [RFC3693]  Cuellar, J., Morris, J., Mulligan, D., Peterson, J., and
              J. Polk, "Geopriv Requirements", RFC 3693, February 2004.

   [I-D.ietf-geopriv-policy]
              Schulzrinne, H., Tschofenig, H., Morris, J., Cuellar, J.,
              and J. Polk, "Geolocation Policy: A Document Format for
              Expressing Privacy Preferences for  Location Information",
              draft-ietf-geopriv-policy-13 (work in progress),
              October 2007.

   [WGS84]    US National Imagery and Mapping Agency, "Department of
              Defense (DoD) World Geodetic System 1984 (WGS 84), Third
              Edition", NIMA TR8350.2, January 2000.

   [GeoShape]
              Thomson, M. and C. Reed, "GML 3.1.1 PIDF-LO Shape
              Application Schema for use by the Internet Engineering
              Task Force (IETF)", Candidate OpenGIS Implementation
              Specification 06-142r1, Version: 1.0, April 2007.

10.2.  Informative References

   [RFC3694]  Danley, M., Mulligan, D., Morris, J., and J. Peterson,
              "Threat Analysis of the Geopriv Protocol", RFC 3694,
              February 2004.

   [RFC4119]  Peterson, J., "A Presence-based GEOPRIV Location Object
              Format", RFC 4119, December 2005.

   [RFC3825]  Polk, J., Schnizlein, J., and M. Linsner, "Dynamic Host
              Configuration Protocol Option for Coordinate-based
              Location Configuration Information", RFC 3825, July 2004.

   [RFC3688]  Mealling, M., "The IETF XML Registry", BCP 81, RFC 3688,
              January 2004.

   [I-D.ietf-geopriv-revised-civic-lo]
              Thomson, M. and J. Winterbottom, "Revised Civic Location
              Format for PIDF-LO",
              draft-ietf-geopriv-revised-civic-lo-06 (work in progress),
              October 2007.



Thomson & Winterbottom    Expires May 15, 2008                 [Page 35]


Internet-Draft          Uncertainty & Confidence           November 2007


   [I-D.ietf-ecrit-lost]
              Hardie, T., "LoST: A Location-to-Service Translation
              Protocol", draft-ietf-ecrit-lost-06 (work in progress),
              August 2007.

   [I-D.ietf-geopriv-pdif-lo-profile]
              Winterbottom, J., Thomson, M., and H. Tschofenig, "GEOPRIV
              PIDF-LO Usage Clarification, Considerations and
              Recommendations", draft-ietf-geopriv-pdif-lo-profile-10
              (work in progress), October 2007.

   [ISO.GUM]  ISO/IEC, "Guide to the expression of uncertainty in
              measurement (GUM)", Guide 98:1995, 1995.

   [NIST.TN1297]
              Taylor, B. and C. Kuyatt, "Guidelines for Evaluating and
              Expressing the Uncertainty of NIST Measurement Results",
              Technical Note 1297, Sep 1994.

   [Convert]  Burtch, R., "A Comparison of Methods Used in Rectangular
              to Geodetic Coordinate Transformations", April 2006.

   [Sunday02]
              Sunday, D., "Fast polygon area and Newell normal
              computation.", Journal of Graphics Tools JGT, 7(2):9-
              13,2002, 2002, <http://www.acm.org/jgt/papers/Sunday02/>.

























Thomson & Winterbottom    Expires May 15, 2008                 [Page 36]


Internet-Draft          Uncertainty & Confidence           November 2007


Authors' Addresses

   Martin Thomson
   Andrew
   PO Box U40
   Wollongong University Campus, NSW  2500
   AU

   Phone: +61 2 4221 2915
   Email: martin.thomson@andrew.com
   URI:   http://www.andrew.com/


   James Winterbottom
   Andrew
   PO Box U40
   Wollongong University Campus, NSW  2500
   AU

   Phone: +61 2 4221 2938
   Email: james.winterbottom@andrew.com
   URI:   http://www.andrew.com/





























Thomson & Winterbottom    Expires May 15, 2008                 [Page 37]


Internet-Draft          Uncertainty & Confidence           November 2007


Full Copyright Statement

   Copyright (C) The IETF Trust (2007).

   This document is subject to the rights, licenses and restrictions
   contained in BCP 78, and except as set forth therein, the authors
   retain all their rights.

   This document and the information contained herein are provided on an
   "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
   OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND
   THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS
   OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF
   THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
   WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.


Intellectual Property

   The IETF takes no position regarding the validity or scope of any
   Intellectual Property Rights or other rights that might be claimed to
   pertain to the implementation or use of the technology described in
   this document or the extent to which any license under such rights
   might or might not be available; nor does it represent that it has
   made any independent effort to identify any such rights.  Information
   on the procedures with respect to rights in RFC documents can be
   found in BCP 78 and BCP 79.

   Copies of IPR disclosures made to the IETF Secretariat and any
   assurances of licenses to be made available, or the result of an
   attempt made to obtain a general license or permission for the use of
   such proprietary rights by implementers or users of this
   specification can be obtained from the IETF on-line IPR repository at
   http://www.ietf.org/ipr.

   The IETF invites any interested party to bring to its attention any
   copyrights, patents or patent applications, or other proprietary
   rights that may cover technology that may be required to implement
   this standard.  Please address the information to the IETF at
   ietf-ipr@ietf.org.


Acknowledgment

   Funding for the RFC Editor function is provided by the IETF
   Administrative Support Activity (IASA).





Thomson & Winterbottom    Expires May 15, 2008                 [Page 38]