Characterizing height above terrain confidence

Patent metadata

Field	Value
Publication number	US-12101689-B2
Application number	US-202217816306-A
Country	US
Kind code	B2
Filing date	Jul 29, 2022
Priority date	Jun 11, 2020
Publication date	Sep 24, 2024
Grant date	Sep 24, 2024

Abstract

A method involves determining, at a mobile device or a service, an uncertainty in height above a reference altitude, an estimated 2D position of the mobile device, and an uncertainty in terrain height above the reference altitude using the estimated 2D position. An uncertainty in height above terrain, of the mobile device, is determined at the mobile device or a server using the uncertainty in height above the reference altitude and the uncertainty in terrain height above the reference altitude.

First claim

The invention claimed is:

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 Positioni

Assignees

• Nextnav Llc

Inventors

• Dormody Michael
• Nagarajan Badrinath
• Han Guiyuan
• Raghupathy Arun

Classifications

• G01C5/00

  Measuring height; Measuring distances transverse to line of sight; Levelling between separated points; Surveyors' levels (G01C3/20, G01C3/30 take precedence) · CPC title

• G01S19/51

  Relative positioning · CPC title

• G01C5/06

  by using barometric means · CPC title

• G01S19/17

  Emergency applications · CPC title

• G01S19/396

  Determining accuracy or reliability of position or pseudorange measurements · CPC title