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

• US 20030142523A1
• Filed: 01/25/2002
• Published: 07/31/2003
• Est. Priority Date: 01/25/2002
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Biacs, Zoltan
• Granted Patent: US 6,985,903 B2
• Time in Patent Office: Days
• US Class Current: 365/1
• 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 method to retrieve elevation data, the method comprising:

locating a first compressed portion of a Digital Elevation Model (DEM) using a first index, the Digital Elevation Model comprising a plurality of compressed portions which includes the first compressed portion, the first index pointing to a storage location where the first compressed portion is stored; and

decompressing the first compressed portion to retrieve first elevation data for at least one sample point in the Digital Elevation Model.

2. A method as in claim 1 wherein the plurality of compressed portions are stored in one of:

a) a Memory Mapped File (MMF);

b) Random Access Memory (RAM); and

c) a file in a file system on a digital processing system.

3. A method as in claim 2 wherein the plurality of compressed portions are portions of compressed profiles in a first tile of the Digital Elevation Model.

4. A method as in claim 3 further comprising:

identifying the first tile, the first tile containing a first location and being one of a plurality of tiles in an area of the Digital Elevation Model; and

identifying a first profile that is in the vicinity of the first location, the first compressed portion being a portion of the first profile.

5. A method as in claim 4 further comprising:

identifying the area, the area containing the first location and being one of a plurality of areas of the Digital Elevation Model.

6. A method as in claim 1 wherein said decompressing the first compressed portion comprises:

run length decoding the first compressed portion to generate scaled elevation data;

inverse scaling the scaled elevation data to generate normalized elevation data; and

adding a reference elevation to the normalized elevation data to generate the first elevation data.

7. A method as in claim 1 further comprising:

identifying a plurality of sample points in the vicinity of a first location;

retrieving elevations of the plurality of sample points from the Digital Elevation Model; and

computing an elevation of the first location from an interpolation using the elevations of the plurality of sample points.

8. A method as in claim 7 further comprising:

performing a coordinate transformation to express a horizontal position of the first location in a coordinate system used by the Digital Elevation Model.

9. A method as in claim 7 further comprising:

providing the elevation of the first location to a Position Determination Entity to perform altitude aiding in a positioning system.

10. A method as in claim 9 wherein said computing the elevation of the first location comprises:

performing a coordinate transformation such that the elevation of first location is expressed in a coordinate system used by the Position Determination Entity.

11. 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.

12. A method as in claim 11 further comprising:

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

13. A method as in claim 11 further comprising:

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

14. A method as in claim 11 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.

15. A method as in claim 14 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.

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

17. A method as in claim 11 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.

18. A method as in claim 17 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.

19. 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 retrieve elevation data, the method comprising:

locating a first compressed portion of a Digital Elevation Model (DEM) using a first index, the Digital Elevation Model comprising a plurality of compressed portions which includes the first compressed portion, the first index pointing to a storage location where the first compressed portion is stored; and

decompressing the first compressed portion to retrieve first elevation data for at least one sample point in the Digital Elevation Model.

20. A media as in claim 19 wherein the plurality of compressed portions are stored in one of:

a) a Memory Mapped File (MMF);

b) Random Access Memory (RAM); and

c) a file in a file system on a digital processing system.

21. A media as in claim 20 wherein the plurality of compressed portions are portions of compressed profiles in a first tile of the Digital Elevation Model.

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

identifying the first tile, the first tile containing a first location and being one of a plurality of tiles in an area of the Digital Elevation Model; and

identifying a first profile that is in the vicinity of the first location, the first compressed portion being a portion of the first profile.

23. A media as in claim 22 wherein the method further comprises:

identifying the area, the area containing the first location and being one of a plurality of areas of the Digital Elevation Model.

24. A media as in claim 19 wherein said decompressing the first compressed portion comprises:

run length decoding the first compressed portion to generate scaled elevation data;

inverse scaling the scaled elevation data to generate normalized elevation data; and

adding a reference elevation to the normalized elevation data to generate the first elevation data.

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

identifying a plurality of sample points in the vicinity of a first location;

retrieving elevations of the plurality of sample points from the Digital Elevation Model; and

computing an elevation of the first location from an interpolation using the elevations of the plurality of sample points.

26. A media as in claim 25 wherein the method further comprises:

performing a coordinate transformation to express a horizontal position of the first location in a coordinate system used by the Digital Elevation Model.

27. A media as in claim 25 wherein the method further comprises:

providing the elevation of the first location to a Position Determination Entity to perform altitude aiding in a positioning system.

28. A media as in claim 27 wherein said computing the elevation of the first location comprises:

performing a coordinate transformation such that the elevation of first location is expressed in a coordinate system used by the Position Determination Entity.

29. 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.

30. A media as in claim 29 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.

31. A media as in claim 29 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.

32. A media as in claim 29 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.

33. A media as in claim 32 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.

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

35. A media as in claim 29 wherein the method further comprises:

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.

36. A media as in claim 35 wherein the method further comprises:

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.

37. A digital processing system to retrieve elevation data, the digital processing system comprising:

means for locating a first compressed portion of a Digital Elevation Model (DEM) using a first index, the Digital Elevation Model comprising a plurality of compressed portions which includes the first compressed portion, the first index pointing to a storage location where the first compressed portion is stored; and

means for decompressing the first compressed portion to retrieve first elevation data for at least one sample point in the Digital Elevation Model.

38. A digital processing system as in claim 37 wherein the plurality of compressed portions are stored in one of:

a) a Memory Mapped File (MMF);

b) Random Access Memory (RAM); and

c) a file in a file system on the digital processing system.

39. A digital processing system as in claim 38 wherein the plurality of compressed portions are portions of compressed profiles in a first tile of the Digital Elevation Model.

40. A digital processing system as in claim 39 further comprising:

means for identifying the first tile, the first tile containing a first location and being one of a plurality of tiles in an area of the Digital Elevation Model; and

means for identifying a first profile that is in the vicinity of the first location, the first compressed portion being a portion of the first profile.

41. A digital processing system as in claim 40 further comprising:

means for identifying the area, the area containing the first location and being one of a plurality of areas of the Digital Elevation Model.

42. A digital processing system as in claim 37 wherein said means for decompressing the first compressed portion comprises:

means for run length decoding the first compressed portion to generate scaled elevation data;

means for inverse scaling the scaled elevation data to generate normalized elevation data; and

means for adding a reference elevation to the normalized elevation data to generate the first elevation data.

43. A digital processing system as in claim 37 further comprising:

means for identifying a plurality of sample points in the vicinity of a first location;

means for retrieving elevations of the plurality of sample points from the Digital Elevation Model; and

means for computing an elevation of the first location from an interpolation using the elevations of the plurality of sample points.

44. A digital processing system as in claim 43 further comprising:

means for performing a coordinate transformation to express a horizontal position of the first location in a coordinate system used by the Digital Elevation Model.

45. A digital processing system as in claim 43 further comprising:

means for providing the elevation of the first location to a Position Determination Entity to perform altitude aiding in a positioning system.

46. A digital processing system as in claim 45 wherein said means for computing the elevation of the first location comprises:

means for performing a coordinate transformation such that the elevation of first location is expressed in a coordinate system used by the Position Determination Entity.

47. 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.

48. A digital processing system as in claim 47 further comprising:

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

49. A digital processing system as in claim 47 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.

50. A digital processing system as in claim 47 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.

51. A digital processing system as in claim 50 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.

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

53. A digital processing system as in claim 47 further comprising:

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

means for 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.

54. A digital processing system as in claim 53 further comprising:

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

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

55. 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) to generate first compressed elevation data;

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.

56. A media as in claim 55 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.

57. A media as in claim 55 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.

58. A media as in claim 55 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.

59. A media as in claim 58 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.