Method and system for wavelet-based representation and use of cartographic data

• US 7,987,186 B1
• Filed: 11/06/2000
• Issued: 07/26/2011
• Est. Priority Date: 11/06/2000
• Status: Active Grant

• Current Assignee: HERE Global B.V. (HERE Holding Corporation)
• Original Assignee: Navteq North America LLC (HERE Holding Corporation)
• Inventors: Joshi, Rajashri
• Primary Examiner(s): Trujillo; James
• Assistant Examiner(s): Casanova; Jorge A
• Application Number:
  US09/706,926
• Time in Patent Office: 3,914 Days
• Field of Search: 707/100, 707 1- 5, 707/102, 707/104.1, 707200-201, 707/736, 707/919, 707/920, 701200-211, 345/428, 340/995, 340/990, 382/173, 382/305, 382/713, 342/450
• US Class Current: 707/736
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: Y10S 707/919 Geographic

Abstract

Cartographic data is represented using wavelet coefficients. Specifically, a cartographic shape point database consisting of shape points and nodes stored on a per geographic feature basis is converted to a cartographic wavelet database consisting of wavelet and scaling coefficients also stored on a per geographic feature basis. The shape of each geographic feature can be reconstructed from the stored wavelet and scaling coefficients for that geographic feature. The wavelet transform organizes the information in a function according to scale, a concept which is related to resolution. The wavelet-based representation facilitates operations such as line simplification (generalization) and zooming. Multi-resolution error metrics are defined using the wavelet representation for assessing the accuracy of sampled cartographic databases with respect to a ground truth database.

Claims

1. A method for representing cartographic data in a computer-based system, comprising:

providing a cartographic database containing a sequence of latitude and longitude data points indicating locations along a geographic feature, wherein the sequence of latitude and longitude data points provide a data point representation of the geographic feature;

using the latitude and longitude data points to generate a parameterized function representing the geographic feature;

computing a plurality of wavelet coefficients from said parameterized function representing the geographic feature, wherein said wavelet coefficients obtained with a wavelet, wherein said wavelet being one of a family of functions having a form

2. The method of claim 1, wherein the data points include altitude.

3. The method of claim 1, wherein the geographic feature is the boundary of a feature selected from the group consisting of a road, waterway, building, park, lake, railroad track, and airport.

4. The method of claim 1, wherein the step of computing the wavelet coefficients includes:

computing the wavelet coefficients by performing a least-squares fit.

5. The method of claim 1, wherein the wavelet coefficients are computed using a semi-discrete orthonormal wavelet transform.

6. A method of displaying on a computer output device a representation of a geographic feature, comprising:

identifying a display scale for displaying the representation of the geographic feature, wherein the display scale is one of several display scale levels useable for a zooming operation of a map display;

retrieving from a computer-usable database a plurality of wavelet coefficients associated with the geographic feature at the identified display scale, wherein a wavelet being one of a family of functions having a form

7. The method of claim 6, further comprising:

performing the zooming operation to display another representation of said geographic feature at a different scale level by retrieving the wavelet coefficients associated with the geographic feature at the different display scale.

8. The method of claim 6, wherein the geographic feature is selected from the group consisting of a road, waterway, building, park, lake, railroad track, and airport.