TileShare: Maps as Computer Images
A cross-platform file format and library for scanned map images
Hrvoje Lukatela and John Russell,
An article published in May 2005 issue of Dr. Dobb's Journal
There are three methods by which geographical knowledge is conveyed in digital
The first (and usually best) method is via a set of "round-Earth"
coordinates of point, line and area abstractions of objects defining their
whereabouts on or near the Earth's ellipsoidal (or at least spherical)
surface. Geographic information in this form can be processed with a computer
to yield acurate quantitative analysis and can subsequently be cast into any
number of flat-panel or paper displays for presentation to human eyes.
A second (and second best) method is via a set of "flat Earth" coordinates
for the same surface object abstractionss, but having already fictitiously
located them on a flat-Earth, using any one of many different planar
projections. Geographic information of this type permits less accurate
quantitative analysis and has obvious limitations at the edges of the
Digital maps based on either of the foregoing methods are referred to
as "vector" maps.
The least desirable method for the conveyance of geographical information
is via digital images from the start. Very little analysis is possible, and
about all that can be reasonably done with them is to use a computer to
present images (or parts of them) for viewing by human eyes, possibly with the
addition of some application-specific content.
Why then would it be worthwhile to consider a file format suited specifically
to "image" maps? Primarily, because digital map images can easily be
obtained by scanning existing paper maps.
While there is an ever-increasing availability of high-quality vector
geography, there are many instances where vector data either isn't available
or can be obtained only at prohibitive cost. However, a paper map often may
be obtained and scanned inexpensively. And even though it is only an image, a
scanned map may contain information not readily available in vector form.
There are other sources of digital map images. Sometimes images photographed
from flying or orbiting platforms may be distributed in raw form without ever
having undergone the typically labor-intensive photogrammetric and
interpretive processes which are used by cartographers to turn aerial
photographs or satellite images into paper maps.
Regardless of image source, the ability to associate each pixel of a map
image with actual ground coordinates will usually exist. Knowledge of this
association enables many practical computer applications such as GPS
navigation. We propose that such applications can benefit greatly from use of
the cross-platform file format and C library components presented here.
So for the remainder of this article, when we talk about computer maps we are
referring to the third type, namely image maps.
A map as a computer image
Maps are a peculiar sub-species of computer image for the following two main
Unlike business graphics or photographs, map images are usually quite large.
After all, they are often derived from large conventional maps. As such,
their pixel count is likely to be quite high, requiring many megabytes of
external storage. Furthermore, an application may require that imagery
from more than one map be stitched together, making the combined image
even much larger.
There are two fundamentally different kinds of computer images. There are
those that are composed of lines, lettering and areas of uniform color having
sharp outlines. Then there are photographs or other material obtained by
imaging devices having continuously changing colors and other acquisition
artifacts. A map as an image can have elements of both types, for instance
a shaded background with line-work and lettering on top of it. Imagery of
the first type is commonly stored as .png, which is lossless, and imagery of
the second type as .jpg, which is lossy. A truly general and comprehensive
map image file format should thus accommodate both types of
To be useful for the storage of map images, a graphical file format should be:
- Capable of handling very high pixel-count collections. Even a single map
sheet of 700 x 800 mm (28x32 inches) scanned at the resolution of 150dpi
becomes a 4200 x 4800 pixel bitmap.
- Randomly accessible. The granularity of compression commonly used in
graphical file formats takes in a complete scan-line - the width of the
entire image. However, since we assume that not the whole file, but only a
small portion of the file will be on screen at any one time, then the "atom"
of compression should be a two-dimensional subset of the file (a tile)
instead of a single-dimensional subset (a scan-line).
- Organized for access efficiency. Compressed tiles that are close to each
other on the ground should be - as much as possible - close to each other in
Memory mappable. Since map image files are unlikely to change in the hands of
the end user, and possibly be accessed directly from read-only media,
applications should be able to access them in a memory-mapped mode.
Computationally tractable. The direct and inverse mapping between each pixel
and its geographic coordinates must be simple to calculate.
- Cross-platform useable. Map image information on disk or CD should
accommodate processing in both big or little endian byte-order architectures,
with a minimum of overhead. Also, the files should be processable
reasonably well on hardware platforms having no floating-point hardware, as
is often the case for hand-held PDA devices or embedded applications.
Tileset File Format and Supporting Computations
We offer developers the two essential ingredients for an effective map image
management and access system: an efficient cross-platform file format
specification and a library of C source code to perform the necessary
geometric and indexing computations. With these two elements (and some
rudimentary application code, as offered here), it should be easy to
jump-start an application project that makes use of scanned maps or other
In addition to these two software components, it is assumed that two other
widely available software components will be used: zlib compression (for
.png-like images) and JPEG library compression (for .jpeg images).
We expect that this technology will be used primarily for maps of
relatively large scale (1:25k-1:250k), maps that cover reasonably large local,
possibly regional, but not continental areas, and that do not extend into very
high latitudes (60+ degrees).
The file format is described here only in general terms: the details are
specified in the tileset.h header file. We will describe in some detail a
basic form of the file: one that has only a single image layer of 24 bits per
pixel (bpp) color, compressed using the lossless zlib compression.
The file is a binary replication of C language structures. It consists of
three main blocks of information:
- A general information header.
- A table of values required to index tile storage and perform tile- or pixel-to-ground direct and inverse mapping.
- The compressed image tiles themselves, organized in a latitude/longitude matrix.
Fig. 1: Tileset File Layout (for rectangular projection,
single lossless image, 24-bpp color).
The header provides basic information about the file: the size of each tile,
the tile rows and columns count, etc.
Next to the file header is a structure that defines how the tiles and pixels
are related to geographic locations. At present, only one such structure -
describing the "rectangular tileset projection" - is provided. Of note is
that all but one longitude in the file are relative to the tileset
mid-longitude value specified therein. This significantly reduces the number
of instances in the code where the cyclic nature of the longitude domain must
be taken into account.
Following the geometry defining structure, there is an array of latitude
values that specify the latitude at each tile boundary, starting at the
South boundary of the outhernmost row of tiles, and progressing North,
ending with the latitude of the North boundary of the northernmost row
Next in the file is an index table providing a file-relative
pointer to each compressed tile and its size.
All of the structures and tables listed above contain only two types of
data: single-byte characters and 4-byte integers. In order to make it possible
to process the file as a read-only file in memory-mapped mode, and to avoid
reading complete header structures and tables into memory and possibly
having to reverse the byte order in the integers, the foregoing is
repeated again in its opposite-endian form. (It makes no difference which
endian version occurs first and which second.) In comparison with the tile
storage itself this overhead is insignificant.
zlib is used to compress and decompress the tiles with 24bpp pixels. As
mentioned in the introduction, the file design provides for "two-layer" maps:
background compressed with lossy jpglib compression, and linework and
lettering in a png-like layer with transparency. Again, the details can be
found in tileset.h
Indexing - Morton Order
As mentioned in the introduction, one of the TileShare design principles
assumes that large tilesets will exist as disk files and that only a small
number of tiles - presumably those that are currently visible on the screen
or in the window - will be brought into the main memory as needed. Depending
on the type of the external storage used, access can be considerably faster
if the tiles that are close to each other geogaphically are close to each
other in the file. Since tiles cover a two-dimensional (latitude/longitude)
domain and the file is essentially a one-dimensional object, this is possible
only to a limited extent. Out of many different arrangements, the Morton
Order - modified so that rectangular arrangements with different x and y tile
counts are accommodated - is used in tilesets. The details can be found in
the extensive commentary of the ts_Morton() function in tileset.c. The
function is provided for use in programs that compose tilesets, and will not,
as a rule, be required by the programs that use tilesets once they have been
Angular Coordinate Encoding and the "Discrete" Mercator Projection
Tilesets use only two data types: 8-bit bytes and 4-byte integers. The angular
measure of latitudes and longitudes are therefore mapped from/to their
canonical forms which are signed real numbers in radian measure into 4-byte
signed integers using two macros in tileset.h: TS_I4OfAng() and TS_AngOfI4().
The ground resolution of geographic coordinates in the integer representation
is in the order of a centimeter: more than sufficient even for tilesets on
the high-end of the anticipated scale range.
All tiles in a tileset are rectangular, having identical pixel dimensions,
and the same longitudinal "width". This means that a tile width measured on
the ground changes continuously not only from one tile row to another, but
also from one east-west line of pixels within the tile to the next. In order
to preserve the similarity of object shapes between the map and the ground,
the design therefore calls for the tile mid-latitude width-to-height aspect
ratio on the ground to be the same as the equivalent aspect ratio on the map
image. The tile width in pixels must be a multiple of eight, while height is
open. The application choice will depend on the scope of the application and
the the anticipated use of the tileset. An example implementation might use
128 pixels in latitude (height) by 256 pixels in longitude (width). Note that
all tiles in any one east-west row have the same north-south extent on the
This arrangement results in a different latitude extent for each row of
tiles; so that each pixel has approximately the same extent on the ground in
both east-west and north-south directions. Indeed, as the tiles are getting
smaller, the geometry of the planar tileset pixel xy system and geographic
coordinates becomes more and more similar to the Mercator projection (which
is itself a rigorous mathematical expression of such an arrangement with
infinitesimally small tiles). It is therefore reasonable to call this mapping
a "discrete" (as opposed to "continuous") Mercator projection. Inside each
tile, the latitudes and longitudes can be assumed to be linearly proportional
to the pixel coordinates: if tiles have a relatively low north-south extent
on the ground (in the order of several kilometers) and relatively low pixel
count in north/south direction (hundreds) the error made by linear
interpolation of latitudes will remain sub-pixel. There is no error as a
result of linear interpolation of longitudes: these are, by definition,
proportional to the x pixel coordinates.
A program that constructs a tileset will require two simple geodetic
computations: finding the length of an arc of meridian between two latitudes
and the length of an arc of the parallel of latitude between two longitudes.
If the scale of the tileset is large and the tiles are small, the simple
spherical form - given below in the form of C language statements - will
meridianArcLength = earthRadius * (latitudeNorth - latitudeSouth);
parallelArcLength = earthRadius * cos(latitude) * (longitudeEast - longitudeWest);
The ellipsoidal version of these computations - together with many other
geodetic computations - can be found in the Hipparchus Library (see
TileShare Source Code: header and function library
Developers wishing to create and/or use tileset files in their application
will find two C language files,
containing the definition of all file structures and the C language source
code for the functions that perform data transformation, geometric
computations and the indexing required to access tiles. The code can be used
as source for a library, or the functions in it may be individually included
in the application source code. Since one of the main advantages of the
TileShare system is its cross-platform capability, the code is intentionally
presented and made available with no dependency on a particular development
environment. Both of these files are provided to application developers free
of charge and free of copyright restriction in the hope that they will enable
the development of robust cross-platform geographical applications.
Attribution of this design to Geodyssey Limited at www.geodyssey.com would be
Sample Viewers (and their source)
To help jump-start the development of applications that use tilesets, we have
prepared programs for three different platforms: the ubiquitous Win32, the
Mac OS X and Windows CE. All three are available in full source form.
Fig. 2: Tileset Viewers in different environments
All three programs open a read-only cross-platform tileset file in
"memory-mapped" mode and use only the most fundamental components of the
graphical API of their respective platforms. This is intentional, as the
purpose of the code is primarily to be reused in the development of more
The viewer for Win32 includes the components required for communication with
a GPS device and provides a "moving map" display of the tileset. Unlike most
GPS navigation applications which "usurp" the COM port and the device
connected through it for their exclusive use, this program consists of two
independent executables: a GPS monitor and a tileset display program. Any
number of programs that follow a simple data exchange protocol can be
executing simultaniously - perhaps multiple viewers displaying different
tilesets for the same locale or providing navigational computations and
numeric data display.
Example Project on the Web
In order to provide end-users with representative scanned map material, and
developers to quickly become operational, we have also provided a suite of
Win32 programs that comprise a "Tileset Builder's Toolkit". The suite is
freely available for download from our web site at
http://www.geodyssey.com/tileshare. Figure 3 presents a snapshot of the
tilest build process using this toolkit.
Fig. 3: The Tileset Build Process
Yes, you CAN make a silk purse out of a sow's ear!