Characterizing height above terrain confidence

1. A method comprising:

determining, at a mobile device or a server, an estimated 2D position of the mobile device;

identifying, at the mobile device or the server, an offset value representing an offset that models confidence of terrain uncertainty in excess of uncertainty in terrain database accuracy of a terrain database and an uncertainty in terrain flatness over a locus of possible 2D positions using the estimated 2D position;

identifying, at the mobile device or the server, a first scaling factor for weighting a term derived from the uncertainty in terrain database accuracy;

identifying, at the mobile device or the server, a second scaling factor for weighting a term derived from the uncertainty in terrain flatness over the locus of possible 2D positions;

determining, at the mobile device or the server, a first product of the first scaling factor and a square of the uncertainty in terrain database accuracy;

determining, at the mobile device or the server, a second product of the second scaling factor and a square of the uncertainty in terrain flatness over the locus of possible 2D positions;

determining, at the mobile device or the server, a first sum of the first product and the second product;

determining, at the mobile device or the server, a square root of the first sum;

determining, at the mobile device or the server, a second sum of the offset value and the square root; and

determining, at the mobile device or the server, an uncertainty in terrain height above a reference altitude over the locus of possible 2D positions using the second sum.

2. A method comprising:

determining, at a mobile device or a server, an estimated 2D position of the mobile device;

determining, at the mobile device or the server, an uncertainty in terrain database accuracy of a terrain database using the estimated 2D position;

determining, at the mobile device or the server, an uncertainty in terrain measurement over a locus of possible 2D positions using the estimated 2D position; and

determining, at the mobile device or the server, an uncertainty in terrain height above a reference altitude using the uncertainty in terrain database accuracy and the uncertainty in terrain measurement over the locus of possible 2D positions.

3. The method of claim 2 , wherein determining the uncertainty in terrain database accuracy comprises:

determining a grid resolution of the terrain database;

selecting a terrain tile;

creating a fine mesh grid over the terrain tile having a greater grid resolution than the grid resolution of the terrain database, the fine mesh grid having a plurality of fine mesh grid polygons;

determining a correlation between i) a distance from a center or a centroid of each fine mesh grid polygon to a nearest centroid or a middle of the terrain tile and ii) a determined altitude error; and

determining the uncertainty in terrain database accuracy using the determined correlation.

4. The method of claim 3 , wherein determining the correlation between the distance from the center or centroid of each fine mesh grid polygon to the nearest centroid or the middle of the terrain tile and the determined altitude error comprises:

for each fine mesh grid polygon of the plurality of fine mesh grid polygons:

determining the distance from the center or the centroid of the fine mesh grid polygon to the nearest centroid or the middle of the terrain tile;

determining a tile altitude value of the nearest centroid or the middle of the terrain tile;

interpolating altitude values across the selected terrain tile and neighboring terrain tiles;

determining a fine mesh altitude for the fine mesh grid polygon using the interpolated altitude values; and

determining an absolute difference between the fine mesh altitude for the fine mesh grid polygon and the tile altitude value of the selected terrain tile; and

correlating i) each of the determined distances from the center or the centroid of the fine mesh grid polygon to the nearest centroid or the middle of the terrain tile to ii) the determined absolute differences between the fine mesh altitude for the fine mesh grid polygon and the tile altitude value of the selected terrain tile.

5. The method of claim 4 , wherein determining the uncertainty in terrain database accuracy using the determined correlation comprises:

determining a typical distance from the mobile device to the nearest tile centroid or the middle of the terrain tile;

determining, using the correlation and based on the determined typical distance, a typical grid error value for the terrain database; and

determining the uncertainty in terrain database accuracy using the typical grid error value.

6. The method of claim 2 , wherein determining the uncertainty in terrain database accuracy comprises:

for each location in the terrain database:

within a threshold of the location, retrieving corresponding terrain data;

within a threshold of the location, retrieving corresponding surface data;

identifying suspect grid point pairs within the surface data; and

upon determining, using the identified grid point pairs, that the location is suspect, storing an indication in the terrain database that the location is suspect; and

determining the uncertainty in terrain database accuracy using the stored indication.

7. The method of claim 6 , wherein identifying the suspect grid point pairs within the surface data comprises:

determining a plurality of possible combinations of neighboring grid points;

for each of the neighboring grid points, determining a difference in altitude between the neighboring grid points; and

upon determining that a magnitude of the difference in altitude exceeds a threshold value, storing an indication in the terrain database that the neighboring grid points are suspect.

8. The method of claim 2 , wherein determining the uncertainty in terrain database accuracy comprises:

identifying a building footprint database having similar terrain coverage as the terrain database;

for each building footprint polygon in the building footprint database, determining if a corresponding portion of the terrain of the terrain database is suspect;

upon determining that the corresponding portion of the terrain of the terrain database is suspect, storing an indication in the terrain database that the corresponding portion of the terrain is suspect; and

determining the uncertainty in terrain database accuracy using the stored indication.

9. The method of claim 8 , wherein determining if the corresponding portion of the terrain of the terrain database is suspect comprises:

retrieving corresponding altitude values from terrain tiles within a threshold distance of the building footprint polygon;

removing the terrain tiles that fall within the building footprint polygon;

interpolating altitude values over the building footprint polygon;

creating a fine mesh of small grid polygons within the building footprint polygon;

for each of the small grid polygons:

determining a terrain altitude value using the interpolated altitude values;

determining a corresponding terrain altitude from the building footprint database; and

determining a difference between the determined terrain altitude value and the corresponding terrain altitude;

determining a quality metric using the differences; and

upon determining that the quality metric surpasses a threshold value, storing an indication in the terrain database that one or more of the terrain tiles within a threshold distance of the building footprint polygon are suspect.

10. The method of claim 2 , wherein determining the uncertainty in terrain database accuracy comprises:

identifying a plurality of Global Positioning System (GPS) benchmarks corresponding to at least a portion of terrain of the terrain database;

for each GPS benchmark of the plurality of GPS benchmarks:

retrieving an altitude value corresponding to that GPS benchmark;

retrieving a terrain altitude value from the terrain database corresponding to that GPS benchmark; and

determining a height difference between the altitude value of that GPS benchmark and the terrain altitude value;

determining a distribution of the height differences;

determining a deviation from a central tendency of the distribution; and

determining the uncertainty in terrain database accuracy using the determined deviation from the central tendency of the distribution.

11. The method of claim 2 , wherein determining the uncertainty in terrain database accuracy comprises:

identifying a plurality of ground control points corresponding to at least a portion of terrain of the terrain database;

for each ground control point of the plurality of ground control points:

retrieving an altitude value corresponding to that ground control point;

retrieving a terrain altitude value from the terrain database corresponding to that ground control point; and

determining a height difference between the altitude value corresponding to that ground control point and the terrain altitude value;

determining a distribution of the height differences;

determining a deviation from a central tendency of the distribution; and

determining the uncertainty in terrain database accuracy using the determined deviation from the central tendency of the distribution.

12. The method of claim 2 , further comprising determining the uncertainty in terrain flatness over the locus of possible 2D positions using the estimated 2D position which comprises:

determining a first terrain altitude value corresponding to the estimated 2D position;

determining a plurality of second terrain values falling within a confidence polygon or circle;

determining a plurality of height differences between the first terrain altitude value and each second terrain value of the plurality of second terrain values;

determining a distribution of the height differences;

determining a deviation from a central tendency of the distribution; and

determining the uncertainty in terrain database accuracy using the determined deviation from the central tendency of the distribution.