Method and system for storage and fast retrieval of digital terrain model elevations for use in positioning systems

• US 7,664,764 B2
• Filed: 06/01/2005
• Issued: 02/16/2010
• Est. Priority Date: 01/25/2002
• Status: Expired due to Term

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Biacs, Zoltan
• Primary Examiner(s): Pannala; Sathyanarayan
• Application Number:
  US11/143,350
• Publication Number:
  US 20060074958A1
• Time in Patent Office: 1,721 Days
• Field of Search: 707 1- 10, 707100-102, 707200-206
• US Class Current: 702/5
• CPC Class Codes: G01C 21/005 with correlation of navigation data from several sources, e.g. map or contour matching G01C21/30 takes precedence
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 take precedence
• CPC Class Codes: G01S 19/06 employing an initial estimate of the location of the receiver as aiding data or in generating aiding data
• CPC Class Codes: G01S 19/50 whereby the position solution is constrained to lie upon a particular curve or surface, e.g. for locomotives on railway tracks
• CPC Class Codes: G01S 5/02 using radio waves using satellite radio beacon systems for determining position G01S19/00
• CPC Class Codes: G01S 5/0236 Assistance data, e.g. base station almanac
• CPC Class Codes: G01S 5/0268 by deriving positions from different combinations of signals or of estimated positions in a single positioning system
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
• CPC Class Codes: H04W 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management

Abstract

Methods and apparatuses to generate and to access compressed and indexed elevations of Digital Elevation Models. In one aspect of the invention, a method to store elevation data includes: compressing elevation data of a first portion of a Digital Elevation Model (DEM) to generate first compressed elevation data; storing the first compressed elevation data in a storage location pointed to by a first index; and storing the first index. In another aspect of the invention, a method to retrieve elevation data includes: locating a first compressed portion of a Digital Elevation Model (DEM) using a first index; and decompressing the first compressed portion to retrieve first elevation data for at least one sample point in the Digital Elevation Model. The Digital Elevation Model has a plurality of compressed portions which includes the first compressed portion; and the first index points to a storage location where the first compressed portion is stored.

Claims

1. A computer implemented method to store elevation data, the method comprising:

compressing elevation data of a first portion of a Digital Elevation Model (DEM), in part, by normalizing elevation data within the first portion to generate first compressed elevation data, wherein normalizing elevation data includes subtracting a reference elevation from each elevation data value in the first portion;

storing the first compressed elevation data in a storage location of a storage media pointed to by a first index; and

storing the first index in the storage media.

2. A method as in claim 1 further comprising:

storing parameters required for determining whether or not a location is in the first portion of the Digital Elevation Model.

3. A method as in claim 1 further comprising:

storing data specifying a coordinate system used to represent the elevation data of the first portion of the Digital Elevation Model.

4. A method as in claim 1 wherein said compressing the elevation data of the first portion comprises:

subtracting a reference elevation from the elevation data in the first portion from the elevation data of the first portion of the Digital Elevation Model (DEM) to generate normalized elevation data; and

scaling the normalized elevation data to generate scaled elevation data.

5. A method as in claim 4 wherein said compressing the elevation data of the first portion further comprises:

run length encoding the scaled elevation data to generate the first compressed elevation data.

6. A method as in claim 1 wherein the first portion is a profile of the Digital Elevation Model.

7. A method as in claim 1 further comprising:

dividing an area of the Digital Elevation Model into a plurality of tiles; and

storing parameters required for determining whether or not a location is in one of the plurality of tiles;

wherein the first portion is one of a plurality of profiles in one of the plurality of tiles.

8. A method as in claim 7 further comprising:

dividing the Digital Elevation Model into a plurality of areas; and

storing parameters required for determining whether or not a location is in one of the plurality of areas.

9. A machine readable media containing executable computer program instructions which when executed by a digital processing system cause said system to perform a method to store elevation data, the method comprising:

compressing elevation data of a first portion of a Digital Elevation Model (DEM) to generate first compressed elevation data;

storing the first compressed elevation data in a storage location pointed to by a first index; and

storing the first index;

dividing an area of the DEM into a plurality of tiles;

dividing at least a first of the plurality of tiles into a plurality of subtiles;

storing parameters required for determining whether or not a location is in one of the plurality of tiles; and

storing parameters for determining whether or not the location is in one of the plurality of subtiles;

wherein the first portion is one of a plurality of profiles in one of the plurality of tiles.

10. A media as in claim 9 wherein the method further comprises:

storing data specifying a coordinate system used to represent the elevation data of the first portion of the Digital Elevation Model.

11. A media as in claim 9 wherein said compressing the elevation data of the first portion comprises:

subtracting a reference elevation from the elevation data of the first portion of the Digital Elevation Model (DEM) to generate normalized elevation data; and

scaling the normalized elevation data to generate scaled elevation data.

12. A media as in claim 11 wherein said compressing the elevation data of the first portion further comprises:

run length encoding the scaled elevation data to generate the first compressed elevation data.

13. A media as in claim 9 wherein the first portion is a profile of the Digital Elevation Model.

14. A digital processing system to store elevation data, the digital processing system comprising:

means for compressing elevation data of a first portion of a Digital Elevation Model (DEM) to generate first compressed elevation data;

means for storing the first compressed elevation data in a storage location pointed to by a first index; and

means for storing the first index;

means for dividing an area of the Digital Elevation Model into a plurality of tiles;

means for dividing at least a first of the plurality of tiles into a plurality of subtiles;

means for storing parameters required for determining whether or not a location is in one of the plurality of tiles;

means for storing parameters for determining whether or not the location in one of the plurality of subtiles;

a processor; and

storage media configured to store processor executable instructions;

wherein the first portion in one of a plurality of profiles in one of the plurality of tiles.

15. A digital processing system as in claim 14 further comprising:

means for storing data specifying a coordinate system used to represent the elevation data of the first portion of the Digital Elevation Model.

16. A digital processing system as in claim 14 wherein said means for compressing the elevation data of the first portion comprises:

means for subtracting a reference elevation from the elevation data of the first portion of the Digital Elevation Model (DEM) to generate normalized elevation data; and

means for scaling the normalized elevation data to generate scaled elevation data.

17. A digital processing system as in claim 16 wherein said means for compressing the elevation data of the first portion further comprises:

means for run length encoding the scaled elevation data to generate the first compressed elevation data.

18. A digital processing system as in claim 14 wherein the first portion is a profile of the Digital Elevation Model.

19. A machine readable media containing a data stream representing a Digital Elevation Model, the data stream being produced by a method comprising:

compressing elevation data of a first portion of a Digital Elevation Model (DEM), including normalizing the elevation data to generate first compressed elevation data, wherein normalizing elevation data includes subtracting a reference elevation from each elevation data value in the first portion;

storing the first compressed elevation data in a storage location pointed to by a first index as part of the data stream; and

storing the first index as part of the data stream.

20. A media as in claim 19 wherein the method further comprises:

storing parameters required for determining whether or not a location is in the first portion of the Digital Elevation Model as part of the data stream.

21. A media as in claim 19 wherein the method further comprises:

storing data specifying a coordinate system used to represent the elevation data of the first portion of the Digital Elevation Model as part of the data stream.

22. A media as in claim 19 wherein said compressing the elevation data of the first portion comprises:

subtracting a reference elevation from the elevation data of the first portion of the Digital Elevation Model (DEM) to generate normalized elevation data; and

scaling the normalized elevation data to generate scaled elevation data.

23. A media as in claim 22 wherein said compressing the elevation data of the first portion further comprises:

run length encoding the scaled elevation data to generate the first compressed elevation data.

24. A computer implemented method to store elevation data, the method comprising:

dividing a first portion of a Digital Elevation Model (DEM) into a plurality of tiles;

for each of the plurality of tiles, compressing elevation data within the tile according to a first resolution;

dividing at least one of the plurality of tiles into a plurality of subtiles;

for each of the plurality of subtiles, compressing elevation data within the subtile according to a second resolution that has a higher resolution than the first resolution;

storing in a storage media, parameters for determining whether a location is in one of the plurality of tiles; and

storing in the storage media, parameters for determining whether the location is in one of the plurality of subtiles.