Deleting Blank Tiles. In a Dangerous Way.

Creating raster tilesets almost invariably leads to the creation of some blank tiles – covering those areas of space where no features were present in the underlying dataset. Depending on the image format you use for your tiles, and the method you used to create them, those “blank” tiles may be pure white, or some other solid colour, or they may have an alpha channel set to be fully transparent.

Here’s an example of a directory of tiles I just created. In this particular z/x directory, more than half the tiles are blank. Windows explorer shows them as black but that’s because it doesn’t process the alpha channel correctly. They are actually all 256px x 256px PNG images, filled with ARGB (0, 0, 0, 0):

What to do with these tiles? Well, there’s two schools of thought:

• The first is that they should be retained. They are, after all, valid image files that can be retrieved and overlaid on the map. Although they aren’t visually perceptible, the very presence of the file demonstrates that the dataset was tested at this location, and confirms that no features exist there. This provides important metadata about the dataset in itself, and confirms the tile generation process was complete. The blank images themselves are generally small, and so storage is not generally an issue.
• The opposing school of thought is that they should be deleted. It makes no sense to keep multiple copies of exactly the same, blank tile. If a request is received for a tile that is not present in the dataset, the assumption can be made that it contains no data, and a single, generic blank tile can be returned in all such instances – there is no benefit of returning the specific blank tile associated with that tile request. This not only reduces disk space on the tile server itself, but the client needs only cache a single blank tile that can be re-used in all cases where no data is present.

I can see arguments in favour of both sides. But, for my current project, disk and cache space is at a premium, so I decided I wanted to delete any blank tiles from my dataset. To determine which files were blank, I initially thought of testing the filesize of the image. However, even though I knew that every tile was of a fixed dimension (256px x 256px), an empty tile can still vary in filesize according to the compression algorithm used. Then I thought I could loop through each pixel in the image and use GetPixel() to retrieve the data to see whether the entire image was the same colour, but it turns out that GetPixel() is slooooowwwww….

The best solution I’ve found is to use an unsafe method, BitMap.LockBits to provide direct access to the pixel byte data of the image, and then read and compare the byte values directly. In my case, my image tiles are 32bit PNG files, which use 4 bytes per pixel (BGRA), and my “blank” tiles are completely transparent (Alpha channel = 0). Therefore, in my case I used the following function, which returns true if all the pixels in the image are completely transparent, or false otherwise:

public static Boolean IsEmpty(string imageFileName)
{
  using (Bitmap b = ReadFileAsImage(imageFileName))
  {
    System.Drawing.Imaging.BitmapData bmData = b.LockBits(new Rectangle(0, 0, b.Width, b.Height), System.Drawing.Imaging.ImageLockMode.ReadOnly, b.PixelFormat);
    unsafe
    {
      int PixelSize = 4; // Assume 4Bytes per pixel ARGB
      for (int y = 0; y < b.Height; y++)
      {
        byte* p = (byte*)bmData.Scan0 + (y * bmData.Stride);
        for (int x = 0; x < b.Width; x++)
        {
          byte blue = p[x * PixelSize]; // Blue value. Just in case needed later
          byte green = p[x * PixelSize + 1]; // Green. Ditto
          byte red = p[x * PixelSize + 2]; // Red. Ditto
          byte alpha = p[x * PixelSize + 3];
          if (alpha > 0) return false;
        }
      }
    }
    b.UnlockBits(bmData);
  }

  return true;
}

It needs to be compiled with the /unsafe option (well, it did say in the title that this post was dangerous!). Then, I just walked through the directory structure of my tile images, passing each file into this function and deleting those where IsEmpty() returned true. And voila! – no more blank tiles.

Geo-referencing and Tile-cutting Raster Imagery

Just as there are many different formats in which vector spatial data may be represented: Well-Known Text (WKT), Well-Known Binary (WKB), Geography Markup Language (GML), and Keyhole Markup Lanuage (KML), to name but a few – so too are there many different formats of raster spatial data.  In fact, almost any image format can be used to encode raster spatial data – since each pixel in an image naturally corresponds to an X,Y location in a raster grid. Any regular BMP, GIF, PNG, JPG, or TIFF image file can therefore be used to store spatial data, so long as the real-world coordinates corresponding to the pixels in each corner of the image are known (and thus the coordinates of each other pixel in the image can be determined). The process of assigning coordinates from a spatial reference system to a raster image is known as geo-referencing.

Some dedicated spatial raster formats, such as GeoTIFF, encode coordinate metadata along with the image data in a single file. However, the raster images used by Open Street Maps, Bing Maps, and Google Maps don’t use GeoTIFFs – they are formed from a series of 256px x 256px tiles saved as regular PNG and JPG images. The metadata describing the geographic extent of each tile is encoded entirely in the filename, which, in Bing Maps, uses the quadkey numbering system as described here.

For example, the following tile shows the Bing Maps road map style tile for quadkey 031311, retrieved from http://ecn.t1.tiles.virtualearth.net/tiles/r031311.png?g=685&mkt=en-us

Knowing nothing but the quadkey number, 031311, and the formulas in the MSDN article linked above, I can calculate that the exact geographic extent of features shown on this tile lie from longitude of –5.625 to 0, and latitude between 52.4827802220782 and 55.7765730186677. Like all Bing Maps tiles, they are projected using the Spherical Mercator projection.

Here’s another tile – this time 120200223:

Once again, I can immediately determine from the quadkey that the extent of this tile has longitude ranging from 0.703125 to 1.40625 and latitude from 52.4827802220782 to 52.9089020477703.

The quadkey system is quite beautiful in its simplicity and efficiency. There are, of course, some limitations with this sort of tiling system – all raster data must be represented using the same projection, and every tile must be regularly-sized, for example, but these limitations are offset by the ease with which it’s possible to place any tile at any zoom level at the correct position on the map with minimum amount of coding.

Preparing Custom Tiles

To get your own raster data into Bing Maps (such as a digitized map or floor plan), you need to prepare a series of individual quadkey tile images following the structure outlined above. Applications such as Safe FME and Microsoft MapCruncher provide the ability to prepare raster images for use as background tile layers in Bing Maps (or Google Maps), or you can write your own script to do so. The process is generally known as “tile-cutting”, and the steps are described below:

1.) First, start out with a source image. Here’s John Snow’s famous map of the Cholera outbreak that occurred in Broad Street in London, 1854:

2.) Georeference the image, by assigning coordinates to corresponding pixel positions in the image. If the image is not already in the correct projection, it might need to be warped to bring features into line with the Mercator projection as used by Bing Maps. The image below shows the interface provided by Mapcruncher for placing reference points in the source image (left hand pane) and Bing Maps (right hand pane):

3.) The geo-referenced, transformed image must then be cut into a series of 256px x 256px tiles at different levels of magnification, numbered according to quadkey. For example, the tile below shows a single tile from zoom level 16 of the above image (quadkey 0313131311122330):

4.) Finally, create a tilelayer that references the set of quadkey tile images. Assuming that the tiles are all saved in the same directory, this is as simple as adding the following lines of javascript. the Bing Maps v7 control will expand the {quadkey} placeholder to the appropriate quadkey filename for each tile request:

// Define the tile source
var tileSource = new Microsoft.Maps.TileSource({
  uriConstructor: 'http://example.com/pathtoyourtiles/{quadkey}.png'
});

// Construct a tile layer based on the tile source
var tilelayer = new Microsoft.Maps.TileLayer({
  mercator: tileSource,
  opacity: 1.0,
  visible: true,
  zIndex: 1
});

// Place the layer onto the map
map.entities.push(tilelayer);

The result

Once the tilelayer is added to the map, whenever a part of that tilelayer comes into view Bing Maps will automatically request and stitch together the appropriate tile images and overlay them at the appropriate position on the map.

The screenshot below shows the result of overlaying Jon Snow’s Cholera map onto a modern day map of London using Bing Maps’ default road map style using the steps described above. Notice how well the roads that cross the edges of the tile layer line up – John Snow was not only the father of epidemiology, but also a highly talented cartographer: