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.

Posted in GIS

Community GIS/Map Wiki

   Pursuing the idea of community GIS a bit further. The question is,”would it be possible to adapt a current content management tool to include an OGC component?” Currently, content managers are oriented to text/html. A portal that merges Wiki, weblog, and content editing with a GeoServer OGC service seems theoretically possible and eminently interesting.

    Once GIS features join the larger world of content management it is alluring to think about what that could mean. Currently content managers make communityportals easier to develop and maintain. The open source community adapted commercial portal interest into public community portals. We now commonly see Wikis maintained by, and for, a common interest community. The Weblog phenomena isanother specifically community type of content management, where blog sites intermingle in a larger web of interest oriented toward news and commentary. These are primarily verbal/text communities.

    Social networkportals such as Faces, Flickr, and Craigslist are also recent successful community interest portals. In these portals digital photos begin to see prominence. Older communities based on code sharing and versioning tools CVS, SVN have beenused for a long time both commercially and in the open source world. Podcasting is now being added to the RSS/Atom community of weblogging which adds an audio-visual component to verbal communities.
  
But, how would GIS/maps fit into these types of community portals?
  
There are some interesting developments in the map graphics arena that provide some hints. For example in the blog realm there is geourl or a2b which are community databases of location. These are essentially spatial point sets locating website ip on a global context. A similar idea is found at the GeoServer user map hosted by moximedia. Again a spatial point set of community users.
  
Google added a huge impetus to community GIS with their Google map api and KML. There are numerous mashups which mostly provide spatial point locations. Here is a javascript project that builds a bridge between Google Maps and the OGC WMS services, Brian Flood so that much more complex features can live on top of Google map base. Yahoo maps and Microsoft maps are belatedly following in Google map’s tracks.
  
OGC WFS-T which allows bidirectional spatial feature updates may be a key foundation block to the burgeoning map community networks. GeoServer provides an open source WFS-T that allows a datastore to be published and updated. Features can be complex entities such as polylines, polygons, and symbols. However, the client side is still problematic. Even with Ajax, html makes a poor tool for graphic updates more complex than point data. On the client side either a heavy weight tool like the uDig Eclipse plugin, or a lightweight tool based on SVG/XAML is needed. uDig is still early in development. SVG has been around awhile but acceptance seems to be growing slowly. Microsoft XAML is definitely a future thing, but promises SVG capability augmented with 3D and graphics hardware rendering performance.
  
WFS chaining adds a great deal of flexibility with interchangeable layer sources. Map sources from the Census Bureau, NOAA, JPL, USGS, FEMA etc can be intermingled. If the MS GeoTango rumor sees light there may be a shift from pure Ajax raster stacks to a more powerful OGC types of services in the future of the big map players. In an OpenGIS world services from all sorts of sources can be mingled as desired. As an example: Add a FEMA flood zone to a Google street base, over a USGS DOQQ, and pull currently available real-estate points from realtor.com, with links to automated appraisal sites for a better understanding of a property you are interested in buying.
  
But, what exactly would community GIS look like, based on a WFS foundation? Once there is a basic public map background whether from the Census TIGER, Google, Yahoo, or Microsoft what would a community add?

Commercial Intranet:
  
In the commercial Intranet zone there are numerous possibilities but security issues are a potential barrier. External infrastructure for utilities, electrical power, pipeline, cable, and telephone are obvious candidates. Customer locations are a big part of enterprise CRM. SAP inventory management and work flow are candidates. Tracking for fleet management, equipment and resources, physical networks, facilities management, and people all have spatial components. Security monitoring from remote cameras to dispatch are all possibilities. Collaborative engineering for complex projects whether civil engineering, construction, or architecture are again spatially located and graphically intensive possibilities for community mapping. Expanding GIS to include geometry in general encompasses a wider engineering audience.
  
Public Service (government):
  
This would include DOTs, county appraisers, land ownership and civil records, disaster planning, water and sewer, health and human services, public safety.
  
Public Community:
    Obviously point locations with comment are already popular. Route sharing is also a part of the major web map channels. Cell phone GPS feeds could aggregate large volumes of traffic for flow maps and traffic analysis. Katrina type disaster communities could provide a way for the local individual to feed information to a larger picture in a weblog manner. Craigslist local want ads could add location to real estate, garage sales, rental subleasing etc. Perhaps community GIS would develop around game plays such as geocaching? Perhaps site seeing and travel with routes and commentary online. It is difficult to predict what would be considered useful to public communities.
  
A first step is simply developing a web mapping portal or Map Wiki. Both comment and location are accessible to the user. The basic data layers are available as WFS datastores from selectable public sources. Community members can then add whatever, points, lines, polygons, or symbols they wish along with linked comment. Using a Wiki model maps and comment can be both public and private. Using a login mode users would add features to be published to just a small network of friends by invitation only; or in anonymous mode completely public features could be added. If such a Map Wiki portal was made available the community decides the content.
  
RSS feeds linking layer changes for community alerts are an interesting possibility. Automated alert entries would be very useful in inventory tracking, security, or SCADA networks. An authenticated user could click a point, line, symbol with an associated RSS feed to add to his feed monitor. Alerts are then sent on change. Monitoring networks of sensors with automatic feeds to a community map service add other interesting avenues to explore.
  
This is why a portal that merges Wiki, Weblog, content editing with a GeoServer OGC service seems theoretically possible and eminently interesting.

The Potential of WFS

    Web feature Service, WFS, is the logical extension of theprior Web Map Service, WMS, specification from the Open Geospatial Consortium, OGC. (See GeoServer for an open source OWS server) Apart from the questionable proliferation of acronyms, there is a real reason for this. WMS deals with distribution of raster while WFS pushes out vectors. WMS rasters of course may be and often are the result of underlying stores of vectors, but the client sees only the pixel result. On the other hand WFS pushes out the more fundamental mathematics of geometry in the form of another acronym, GML or Geographic Markup Language. The utility of geometry on the client side may be in question, especially in the html world where vectors reside as second class or less citizens. However, a further acronym, SVG, Scalable Vector Graphics, adds vector rendering to the humble browser, opening a new window for graphic clients.

    WFS combined with a vector rendering specification like the W3C’s SVG or Microsoft’s take on the same problem, XAML, extends the simple raster map into a new thing. In vectors all geometries are accessible, all features are potentially event driven, dynamic, interactive, alive. Geometry is a short hand for complex pixel relationships. Instead of empty singular pixels, geometry defines pixel relations in the real number plane. Linear algebra provides very efficient spatial manipulation for scaling, skewing, rotating, and translating Cartesian end points, while geometry fills in the relation(s) between ends. Rendering geometry on the client pulls intelligence back from the server into the local system.

    Unfortunately WFS on the server is still rare, and vector rendering on the browser is only in versions 1.0. Incentive for WFS publication is somewhat lacking until the client rendering is ubiquitous. It is still conceivable that there is value in pushing out vectors as GML for input to other systems, a mere transport mechanism, but the real end goal is direct rendering with event listeners at the client. The obvious early players in the WFS services are government players like the USGS, Census Bureau, County appraisers, FEMA, … which at present have not publicly exposed vectors in a WFS. There are a number of WMS services available, but WFS is still in its infancy. Commercial interest would grow out of the availability of base infrastructure in the government realm.

    There are some early hints. NOAA has recently opened an experimental electronic navigation chart, ENC, web service as WFS to supplement their previous WMS. There is some talk of a WFS published by the Census Bureau sometime in this coming Feb. The delay is curious given the potential benefit for both the government and the public. The Census is actually a member of the OGC, and Paul Daisy, had done some very interesting work back in 2003. The Census continues work on an experimental service but apparently it will not become available until Feb of 2006 at the earliest.

    WFS is vector, optionally bidirectional, and chainable. Each of these attributes is an important step for GIS web services. Vectors are important to client side interaction, bidirectional WFS-T is important for community based data stores, and the ability to chain together published web services unleashes the commercial potential. The three together are potentially revolutionary for GIS web services.

Posted in OWS