Google Map Pyramid

Google Maps Imagery makes use of a quadtree for storing and accessing its pyramid of imagery tiles. It is interesting to view such an approach as a binary spiral which can be encoded in an xml tag hierarchy with interesting possibilities for Xpath queries.

Quad trees have been known in GIS for some time. Computer graphics have commonly made use of this storage approach for imagery. It is particularly useful for images with large uniform areas mingled with small detailed areas. The efficiency is generally not realized in compression but in speed of processing. Insertions, deletions, and searches are performed on tree-node traversals and are consequently faster than serial traversals. You can think of quad trees as a 2D extension of the binary tree.

In a different vein, the Google imagery stack makes use of a quadtree approach in its tile queries. For example this url, http://kh.google.com/kh?v=3&t=trtsqtqsqqqt, will select a tile at level 12 for west Kuwait City. The letters “q”, “r”, “s”, and “t” being used to code x and y quadrants one level deeper in a pyramid of tiles.

The Google image universe starts at quadrant t, img=t.    

Kuwait falls in the NE quadrant or “r’ google tile. Adding r to the string, img=”tr”

Next SW quadrant = “t” for img=trt

Next SE quadrant = “t” for img=trts

Next NW quadrant = “q” for img=trtsq

Following the same spiral leads to tile set

Which contains the Google imagery tile http://kh.google.com/kh?v=3&t=trtsqtqsqqqt

Substituting a binary scheme for the letter nomenclature provides an approach for calculating neighboring tiles. q=0, r=1, t=2, and s=3

   

Img= trtsqtqsqqqt becomes 212302030002 or 10 01 10 11 00 10 00 11 00 00 00 10

In the binary representation the right bit indicates left/right and the left bit indicates up/down. By splitting the bits into vertical and horizontal we can rewrite the above string as:

Right bit, Horizontal, X: 010100010000

Left bit, Vertical, Y: 101101010001

Using these as integers we can move east by incrementing X or west by decrementing X or north – decrementing y, and south – incrementing y. Once we have moved in the direction desired the binary encoding is reversed back to qrst code to pick up the neighboring tile.

Example:

Moving East from tile “trtsqtqsqqqt” would increment the X =010100010000 +1 resulting in 010100010001 or recombining with the Y 101101010001 = 10 01 10 11 00 10 00 11 00 00 00 11 = 212302030003 = tile “trtsqtqsqqqs”

http://kh.google.com/kh?v=3&t=trtsqtqsqqqt move east to http://kh.google.com/kh?v=3&t=trtsqtqsqqqs

East to

This is a useful approach for storing the pyramid of pretiled imagery on the Google servers, which makes retrieval consistent across the projected world domain. The Google map/imagery world is a Mercator projected plane.

Beyond Google however, it’s interesting to note the hierarchy implicit in this type of quad tree scheme. The real number plane may be similarly considered as a hierarchy or quad tree. In this case a binary series defines each rational number:

x +/- x/2 +/- x/4 +/- x/8 +/- x/16 … x/2**n,� y +/- y/2 +/- y/4 +/- y/8 +/- y/16 … y/2**n

And an infinite series defines the bounds of the irrational numbers.

Translating a decimal place hierarchy 1327.32 into an xml hierarchy results in something like:

<x1>1<x2>3<x3>2<x4>7<x5>.<x6>3<x7>2</x7></x6></x5></x4></x3></x2></x1>

This type of tag hierarchy may spiral to arbitrary precision depth with infinite holes at irrational numbers like pi.

In a quadtree hierarchy the tag hierarchy is binary 0b10100101111

<point>

<x1>1<x2>0<x3>1<x4>0<x5>0<x6>1<x7>0 </x7></x6></x5></x4></x3></x2></x1>

<y1>1<y2>0<y3>1<y4>0<y5>0<y6>1<y7>0 </y7></y6></y5></y4></y3></y2></y1>

</point>

An interesting aspect of Xpath is its ability to slice across the xml tree at an arbitrary depth. In a spatial xml encoding, Xpath could be used to slice out arbitrary precision data at a desired depth. If duplicates are filtered the result is a spatial point set thinned to the Xpath precision, which might be a useful way to generalize arbitrary views on a high resolution spatial set.

Another interesting aspect of a quadtree spatial set might be the use of binary hierarchies to encode minimum bounding boxes of geometric features. In this case the Xpath slice across the xml encoded space would result in a set of intersecting bounding boxes. With very efficient Xpath queries you have in essence a quadtree index based on XML/XPath.

This entry was posted in Uncategorized by admin. Bookmark the permalink.

Comments are closed.