Digital map compression and display method

• US 6,177,943 B1
• Filed: 02/27/1998
• Issued: 01/23/2001
• Est. Priority Date: 11/08/1996
• Status: Expired due to Term

• Current Assignee: Hanger Solutions, LLC (IP Investments Group LLC)
• Original Assignee: Jed Margolin
• Inventors: Margolin, Jed
• Primary Examiner(s): Vo, Cliff N.
• Application Number:
  US09/031,998
• Time in Patent Office: 1,061 Days
• Field of Search: 345/418, 345/419, 345/420, 345/423, 345/424
• US Class Current: 345/419
• CPC Class Codes: H04N 19/137 Motion inside a coding unit, e.g. average field, frame or block difference
• CPC Class Codes: H04N 19/154 Measured or subjectively estimated visual quality after decoding, e.g. measurement of distortion use of rate-distortion criteria H04N19/147
• CPC Class Codes: H04N 19/172 the region being a picture, frame or field
• CPC Class Codes: H04N 19/196 being specially adapted for the computation of encoding parameters, e.g. by averaging previously computed encoding parameters processing of motion vectors H04N19/513
• CPC Class Codes: H04N 19/27 involving both synthetic and natural picture components, e.g. synthetic natural hybrid coding [SNHC]
• CPC Class Codes: H04N 19/39 involving multiple description coding [MDC], i.e. with separate layers being structured as independently decodable descriptions of input picture data
• CPC Class Codes: H04N 19/60 using transform coding

Abstract

A digital elevation database is compressed to create a compressed digital map database which is used by a digital computer system for displaying three-dimensional terrain data in the form of polygons. The compressed digital map database is produced from a database of elevation points by selecting every mth row and every nth column, thereby resulting in a reduction of database storage requirements. During program run-time the intersection of rows and columns forms cells with four corners. The elevation value of a center elevation point for each cell is formed by various methods, thereby creating a cell made up of four three-dimensional triangles. One method for creating the elevation of the center elevation point uses the elevations of the four corners of the cell. Another method uses extrapolated elevation values from the cell'"'"'s extended diagonals. The three-dimensional triangles formed from the center elevation point are then transformed and projected using standard computer graphics methods on a digital computer to produce a three-dimensional projected display.

Claims

1. A method for compressing a digital elevation database to produce a compressed digital map database for displaying three-dimensional polygons comprising the computer implemented steps of:

a) providing a digital elevation database, said digital elevation database comprising elevation points arranged in an array of rows and columns;

b) producing a compressed digital map database by taking every mth row and every nth column of said digital elevation database, wherein m and n are greater than 1;

c) during program run-time performing the steps of;

(i) determining a center elevation point in the center of each cell of said compressed digital map database, whereby each said cell comprises four corner elevation points formed by the intersections of rows and columns of said compressed digital map database, and whereby said center elevation point is calculated by the steps of;

(a) calculating the elevations of the extrapolated extended cell diagonals;

(i) ZC1=Z(x,y+1)+(Z(x,y+1)−

Z(x−

1,y+2)) * 0.5;

(ii) ZC2=Z(x+1,y+1)+(Z(x+1,y+1)−

Z(x+1,y+2)) * 0.5;

(iii) ZC3=Z(x+1,y)+(Z(x+1,y)−

Z(x+2,y−

1)) * 0.5;

(iv) ZC4=Z(x,y)+(Z(x,y)−

Z(x−

1,y−

1)) * 0.5;

(b) taking the average value of ZC1, ZC2, ZC3, and ZC4;

(ii) using said center elevation point to produce four three-dimensional triangles, each three-dimensional triangle formed from said center elevation point and two adjacent corner elevation points forming a side of said cell;

(iii) transforming and projecting a plurality of cells composed of said four three-dimensional triangles for display on a video display.

2. The method of claim 1 wherein at least one of said three-dimensional triangles is displayed such that at least one edge of said at least one of said three-dimensional triangles has a different appearance than a central portion of said at least one of said three-dimensional triangles.

3. The method of claim 1 wherein said compressed digital map database comprises a plurality of geographic blocks, each geographic block representing a geographic area, wherein a first geographic block may have a different resolution from a second geographic block.

4. The method of claim 1 wherein said center elevation point is determined by taking the lowest elevation of said four corner elevation points of said cell.

5. The method of claim 1 wherein said center elevatoin point is determined by performing the steps of:

a) calculating the elevations of the extrapolaed extended point is determined by performing the steps of;

(i) ZC1=Z(x,y+1)+(Z(x,y+1)−

Z(x−

1,y+2))*0.5;

(ii) ZC2=Z(x+1,y+1) +(Z(x+1,y+1)−

Z(x+1,y+2))*0.5;

(iii) ZC3=Z(x+1,y)+(Z(x+1,y)−

Z(x+2,y−

1))*0.5;

(iv) ZC4=Z(x,y)+(Z(x,y)−

Z(x−

1,y−

1))*0.5;

b) taking the average value of ZC1, ZC2, ZC3, and ZC4.

6. The method of claim 1 wherein said center elevation point is determined by performing the steps of:

a) calculating the elevations of the extrapolated extended cell diagonals;

(i) ZC1=Z(x,y+1)+(Z(x,y+1)−

Z(x−

1,y+2))*0.5;

(ii) ZC2=Z(x+1,y+1) +(Z(x+1,y+1)−

Z(x+1,y+2))*0.5;

(iii) ZC3=Z(x+1,y)+(Z(x+1,y)−

Z(x+2,y−

1))*0.5;

(iv) ZC4=Z(x,y)+(Z(x,y)−

Z(x−

1,y−

1))*0.5;

b) taking the highest value of ZC1, ZC2, ZC3, and ZC4.

7. The method of claim 1 wherein said center elevation point is determined by performing the steps of:

a) calculating the elevations of the extrapolated extended cell diagonals;

(i) ZC1=Z(x,y+1)+(Z(x,y+1)−

Z(x−

1,y+2))*0.5;

(ii) ZC2=Z(x+1,y+1) +(Z(x+1,y+1)−

Z(x+1,y+2))*0.5;

(iii) ZC3=Z(x+1,y)+(Z(x+1,y)−

Z(x+2,y−

1))*0.5;

(iv) ZC4=Z(x,y)+(Z(x,y)−

Z(x−

1,y−

1))*0.5;

taking the lowest value of ZC1, ZC2, ZC3, and ZC4.

8. The method of claim 1 wherein said center elevation point is determined by performing the steps of:

a) calculating the elevations of the extrapolated extended cell diagonals;

(i) ZC1=Z(x,y+1)+(Z(x,y+1)−

Z(x−

1,y+2))*0.5;

(ii) ZC2=Z(x+1,y+1) +(Z(x+1,y+1)−

Z(x+1,y+2))*0.5;

(iii) ZC3=Z(x+1,y)+(Z(x+1,y)−

Z(x+2,y−

1))*0.5;

(iv) ZC4=Z(x,y)+(Z(x,y)−

Z(x−

1,y−

1))*0.5;

taking one of the values of ZC1, ZC2, ZC3, and ZC4.

9. The method of claim 1 wherein at least one of said three-dimensional triangles is displayed such that at least one edge of said at least one of said three-dimensional triangles has a different appearance than a central portion of said at least one of said three-dimensional triangles.

10. The method of claim 1 wherein said compressed digital map database comprises a plurality of geographic blocks, each geographic block representing a geographic area, wherein a first geographic block may have a different resolution from a second geographic block.

11. A method for comprising a digital elevatoin database to produce a compressed digital map database for displaying three-dimensional polygons comprising the computer implemented steps of:

a) providing a digital elevation database, said digital elevation database comprising elevation points arranged in an array of rows and columns;

b) producing a compressed digital map database by taking every mth row and every nth column of said digital elevation database, wherein m and n are greater than 1;

during program run-time performing the steps of;

(i) determining a center elevatoin point in the center of each of cell of said compressed digital map database, whereby each said cell comprises four corner elevation points formed by the intersections of rows and columns of said compressed digital map database, and whereby the elevation of said center elevation point is calculated by taking the average elevation of said four corner elevation points of said cell;

(ii) using said center elevation point to produce four three-dimensional triangles, each three-dimensional triangle formed from said center elevation point and two adjacent corner elevation points forming a side of said cell;

(iii) transforming and projecting a plurality of cells composed of said four three-dimensional triangles for display on a video display.

12. The method of claim 11, wherein at least one of said three-dimensional triangles is displayed such that at least one edge of said at least one of said three-dimensional triangles has a different appearance than a central portion of said at least one of said three-dimensional triangles.

13. The method of claim 11 wherein said compressed digital map database comprises a plurality of geographic blocks, each geographic block representing a geographic area, wherein a first geographic block may have a different resolution from a second geographich block.

14. A method for compressing a digital elevation database to produce a compressed digital map databse for displaying three-dimensional polygons comprising the computer implemented steps of:

a) providing a digital elevation database, said digital elevation database comprising elevation points arranged in an array of rows and columns;

b) producing a compressed digital map database by taking every mth row and every nth column of said digital elevation database, wherein m and n are greater than 1;

c) during program run-time performing the steps of;

(i) determing a center elevation point in the center of each cell of said compressed digital map database, whereby each said cell comprises four corner elevation points formed by the intersections of rows and columns of said compressed digital map database, and whereby said center elevation point is calculated by the steps of;

(a) calculating the elveations of the extrapolated extends cell diagnols;

(i) ZC1=Z(x,y+1)+(Z(x,y+1)−

Z(x−

1,y+2))*0.5;

(ii) ZC2=Z(x+1,y+1) +(Z(x+1,y+1)−

Z(x+1,y+2))*0.5;

(iii) ZC3=Z(x+1,y)+(Z(x+1,y)−

Z(x+2,y−

1))*0.5;

(iv) ZC4=Z(x,y)+(Z(x,y)−

Z(x−

1,y−

1))*0.5;

(b) taking the average value of ZC1, ZC2, ZC3, and ZC4;

(ii) using said center elevatoin point to produce four three-dimensional triangles, each three-dimensional triangle formed from said center elevation point and two adjacent corner elevation points forming a side of said cell;

(iii) transforming and projecting a plurality of cells composed of said four three-dimensional triangles for displaying on a video display.

15. The method of claim 14 wherein at least one of said three-dimensional triangles is displayed such that at least one edge of said at least one of said three-dimensional triangles has a different appearance than a central portion of said at least one of said three-dimensional triangles.

16. The method of claim 14 wherein said compressed digital map database comprises a plurality of geographic blocks, each geographic block representing a geographic area, wherein a first geographic block may have a different resolution from a second geographic block.