Subject: [Geopriv] LCI and Uncertainty Representation

From: "Thomson, Martin" <[email-masked]>
Date: Mon, 27 Mar 2006 22:58:15 -0600

(My apologies for the long mail - it was important to get this right.)
 
This is something that I discovered when working with LCI and PIDF-LO profile.  Uncertainty is an important piece of information, particularly for mobile and wireless networks.  I believe that there is a problem with the way that LCI encodes uncertainty that makes LCI unsuitable for the representation of uncertainty.
 
The way that LCI represents uncertainty is through a "resolution" parameter that indicates how many binary digits of each axis is significant or accurate.  This is explained in detail in RFC 3825 with a series of examples, but in short this describes a rough rectangular prism that is aligned along the north-south/east-west/up-down axes.
 
Conversion from LCI Form
 
RFC 3825 and PIDF-LO profile have mainly concentrated on converting the LCI form into a usable form.  From the example in RFC 3825, 38.89868° is encoded into a 34bit twos-complement number:
    000100110.1110011000001111111001000
The resolution value for this axis indicates how many of this bits are actually significant.  So a resulution of 18 indicates that the last 16 bits could be either 1 or zero:
    000100110.111001100xxxxxxxxxxxxxxxx
If you want to determine the uncertainty for this, you assume a range from the minimum possible value (all zeros for the last 16 bits) to the maximum (all ones):
   000100110.1110011000000000000000000 to
   000100110.1110011001111111111111111
This gives us the range given in the example: 38.8984375° to 38.9003906° (rounded to 7 decimal places).
 
Conversion Into LCI Form
 
I was interested in the conversion from an uncertainty value back into the LCI form.
The first thing that you need to do when converting to LCI form is to convert your original shape into a rectangular prism.  This is quite easy; all you need to do is determine the minimum and maximum values for each of the axes: latitude, longitude and altitude.
 
This slightly increases the area that you are covering, but the overall effect is minimal; for a circular area, it increases by a ratio of 4:pi; a square building will at most double the size of the area.  It's important to note that you can't cut corners off because you don't know the probability that the target is in the corner that you cut.
 
I took a random sample from some mobile testing that we have done: 32.98004° to 32.98054397° is a approximately 56 metres distance.
 
You then take each value and convert to a 34-bit twos-complement number:
    000100000.1111101011100011111001110 to
    000100000.1111101100000100111011100
    ^^^^^^^^^^^^^^^^^
Now to ensure that the encoded value represents the full range from the lowest to highest value, you take the common stem.  I've marked this above.  For this example, we have 16 common bits between low and high.
Just to check, I convert the value back by making the last 18 bits either 0 or 1 as I described earlier.  This leads to a range from 32.9765625° to 32.9843745°, which is approximately 870 metres.
That was a surprising increase in the uncertainty, 56 to 870 is a fairly large increase.  That would be unacceptable to most people.
 
The Problem
 
The LCI encoding breaks when the uncertainty that you are trying to represent causes a change in a relatively significant binary digit.  This means that uncertainty can be expanded, sometimes by an surprising amount, depending on which binary digit changes.  In many cases the change will be in lower-order digits, which will result in a relatively small increase in uncertainty, but certain places can cause this to fail spectacularly.
 
The weakness of this encoding is most clearly demonstrated at whole numbers of degrees, particularly powers of two.  Take the range from 31.9999985° to 32.00000274°, which is a mere 0.5 metre range about 32 degrees.  This results in the following binary values:
    000011111.1111111111111111111001110 to
    000100000.0000000000000000001011100
    ^^^
You'll note that there are only three bits that are common to both.  This results in an encoding that represents a range from 0 to 64 degrees, or a 3,500 kilometre distance!  If this encoding was converted to a PIDF-LO following the guidelines in RFC 3825, this information would be effectively useless.
 
This problem is exacerbated at the three zero points - the Greenwich Meridian, Equator and at the surface of the geoid (altitude).  In these cases, if the input uncertainty spans the zero point, the resultion value ends up as zero; that is, it indicates that there is no useful information for that parameter.
 
It's important to note that the original uncertainty has very little bearing on this problem - a small value can be increased to any value.  More precise location determination technologies only reduce the probability of large problems occuring, although the nature of the encoding is such that any uncertainty can be greatly increased.
 
Conclusion
 
Uncertainty is a reality of location and important for a number of applications.  LCI is unsuited to representing uncertainty.  Its limited form means that adapting existing uncertainty information results in a small error, but this is insignificant when compared to the error that can be introduced by the way that the resolution parameter is interpreted.

------------------------------------------------------------------------------------------------
This message is for the designated recipient only and may
contain privileged, proprietary, or otherwise private information.  
If you have received it in error, please notify the sender
immediately and delete the original.  Any unauthorized use of
this email is prohibited.
------------------------------------------------------------------------------------------------
[mf2]

_______________________________________________
Geopriv mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/geopriv

---

From: John Schnizlein <[email-masked]>
Date: Tue, 28 Mar 2006 07:32:43 -0500

Yes, the truncation calculation of the resolution shown in RFC 3825 is 
an error.  As you indicate, truncation of the value leads to large 
errors where resolution is better than the difference of the value from 
the nearest power of 2.

The correct method to find the upper and lower bounds (respectively) 
from resolution is to add and subtract
  (2 ^ (34 - resolution) - 1) * 2 ^ -25 from the value at the center of 
the region.

It is not the encoding of location with binary-precision that is wrong, 
but the application of truncation.  This should be fixed.

John

On Mar 27, 2006, at 11:58 PM, Thomson, Martin wrote:
>
> The weakness of this encoding is most clearly demonstrated at whole 
> numbers of degrees, particularly powers of two.  Take the range from 
> 31.9999985° to 32.00000274°, which is a mere 0.5 metre range about 32 
> degrees.  This results in the following binary values:
> You'll note that there are only three bits that are common to both.  
> This results in an encoding that represents a range from 0 to 64 
> degrees, or a 3,500 kilometre distance!  If this encoding was 
> converted to a PIDF-LO following the guidelines in RFC 3825, this 
> information would be effectively useless.