Method for encoding and serving geospatial or other vector data as images

• US 7,254,271 B2
• Filed: 03/17/2005
• Issued: 08/07/2007
• Est. Priority Date: 03/05/2003
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: SeaDragon Software, Inc. (Microsoft Corporation)
• Inventors: Aguera y Arcas, Blaise
• Primary Examiner(s): Wu; Jingge
• Assistant Examiner(s): Bayat; Ali
• Application Number:
  US11/082,556
• Publication Number:
  US 20050270288A1
• Time in Patent Office: 873 Days
• Field of Search: 382/232, 382/253, 382/299, 382/274, 382/302, 382/305, 715/850, 345/428
• US Class Current: 382/232
• CPC Class Codes: G06T 17/05 Geographic models
• CPC Class Codes: G06V 30/422 Technical drawings; Geographical maps
• CPC Class Codes: H04N 19/63 using sub-band based transform, e.g. wavelets

Abstract

A system and method are disclosed which include providing a first layer of an image, the first layer including features of the image having locations within the first layer; and providing a second layer of the image, the second layer including data blocks corresponding to respective ones of the features; each data block being in a location in the second layer substantially corresponding to a location in the first layer of the feature corresponding to each data block, wherein a size and shape of the second layer substantially correspond to a size and shape of said first layer.

Claims

1. A method, comprising:

providing a first layer of an image, said first layer including features of said image having locations within said first layer;

providing a second layer of said image, said second layer including data blocks corresponding to and describing respective ones of said features, each said data block being in a location in said second layer at least substantially corresponding to a location in said first layer of the feature corresponding to each said data block; and

providing a third layer of said image, said third layer including pointers having locations in said third layer, each said pointer corresponding to a respective one of said features and a respective one of said data blocks, the location of each said pointer in said third layer at least substantially corresponding to the location in said first layer of the feature corresponding to each said pointer wherein said providing said second layer of said image comprises;

locating each said data block employing a packing algorithm to achieve a maximum proximity of each said data block to a target location for each said data block in said second layer, said target location in said second layer corresponding to the location in said first layer of the feature corresponding to each said data block.

2. The method of claim 1 wherein said second layer and said third layer each have a size and shape corresponding to a size and a shape of said first layer.

3. The method of claim 1 further comprising:

forming a map image from a combination of said first layer, said second layer, and said third layer.

4. The method of claim 3 further comprising flattening data in said map image.

5. The method of claim 1 wherein each said pointer indicates the location of each said pointer'"'"'s corresponding data block with respect to each said pointer'"'"'s location.

6. The method of claim 5 wherein said indicating comprises identifying an offset in two dimensions.

7. The method of claim 6 wherein each said dimension of said offset is expressed in pixels.

8. The method of claim 6 wherein said indicating comprises identifying an offset as a one-dimensional distance along a Hilbert curve.

9. The method of claim 8 wherein said offset along said one-dimensional curve is expressed in units of pixels.

10. The method of claim 8 wherein said offset along said one-dimensional curve is expressed in units corresponding to integral multiples of pixels.

11. The method of claim 1 wherein said maximum proximity is determined based on a shortest straight-line distance between each said data block'"'"'s location and said target location for each said data block.

12. The method of claim 1 wherein said maximum proximity is determined based on a sum of absolute values of offsets in each of two dimensions between each said data block'"'"'s location and said target location for each said data block.

13. The method of claim 1 wherein said maximum proximity is determined based on a minimum Hilbert curve length between each said data block'"'"'s location and said target location for each said data block.

14. A computer readable storage medium encoded with one or more software programs that are operable to cause a processing unit to execute actions, comprising:

providing a first layer of an image, said first layer including features of said image having locations within said first layer;

providing a second layer of said image, said second layer including data blocks corresponding to and describing respective ones of said features, each said data block being in a location in said second layer at least substantially corresponding to a location in said first layer of the feature corresponding to each said data block; and

providing a third layer of said image, said third layer including pointers having locations in said third layer, each said pointer corresponding to a respective one of said features and a respective one of said data blocks, the location of each said pointer in said third layer at least substantially corresponding to the location in said first layer of the feature corresponding to each said pointer, wherein said providing said second layer of said image comprises;

locating each said data block employing a packing algorithm to achieve a maximum proximity of each said data block to a target location for each said data block in said second layer, said target location in said second layer corresponding to the location in said first layer of the feature corresponding to each said data block.

15. The computer readable storage medium of claim 14 wherein said second layer and said third layer each have a size and shape corresponding to a size and a shape of said first layer.

16. The computer readable storage medium of claim 14 wherein the processing unit executes the further action of:

forming a map image from a combination of said first layer, said second layer, and said third layer.

17. The computer readable storage medium of claim 14 wherein each said pointer indicates the location of each said pointer'"'"'s corresponding data block with respect to each said pointer'"'"'s location.

18. The computer readable storage medium of claim 14 wherein said indicating comprises identifying an offset in two dimensions.

19. The computer readable storage medium of claim 14 wherein said maximum proximity is determined based on a shortest straight-line distance between each said data block'"'"'s location and said target location for each said data block.

20. An apparatus including a computer readable storage medium encoded with one or more software programs, a processing unit operating under the control of said one or more software programs that are operable to cause the processing unit to execute actions, comprising:

providing a first layer of an image, said first layer including features of said image having locations within said first layer;

providing a second layer of said image, said second layer including data blocks corresponding to and describing respective ones of said features, each said data block being in a location in said second layer at least substantially corresponding to a location in said first layer of the feature corresponding to each said data block; and

providing a third layer of said image, said third layer including pointers having locations in said third layer, each said pointer corresponding to a respective one of said features and a respective one of said data blocks, the location of each said pointer in said third layer at least substantially corresponding to the location in said first layer of the feature corresponding to each said pointer, wherein said providing said second layer of said image comprises;

locating each said data block employing a packing algorithm to achieve a maximum proximity of each said data block to a target location for each said data block in said second layer, said target location in said second layer corresponding to the location in said first layer of the feature corresponding to each said data block.

21. The apparatus of claim 20 wherein said second layer and said third layer each have a size and shape corresponding to a size and a shape of said first layer.

22. The apparatus of claim 20 wherein the processing unit executes the further action of:

forming a map image from a combination of said first layer, said second layer, and said third layer.

23. The apparatus of claim 20 wherein each said pointer indicates the location of each said pointer'"'"'s corresponding data block with respect to each said pointer'"'"'s location.

24. The apparatus of claim 23 wherein said indicating comprises identifying an offset in two dimensions.

25. The apparatus of claim 20 wherein said maximum proximity is determined based on a shortest straight-line distance between each said data block'"'"'s location and said target location for each said data block.