[Gdal-dev] GeoQuadTree - an open format for storinggeoreferencedimages

[Jordi Gilabert Vall]

As far as I know, TILEINDEX is a MapServer related thing. Can a GDAL-linked
application access to it ?

In TILEINDEX, the list of files forming a layer are stored in a shapefile
with polygons representing the footprint of each file, and the name of the
files. In GeoQuadTree there is no need of a spatial index, tile index,
catalog of images, or a database. There is a simple algorithm that
calculates the specific level of the pyramid, and the specific tiles to
access. The algorithm calculates the path in the filesystem needed to
retrieve the tiles. The XML file in the GeoQuadTree doesn't include a
catalogue/index, it only need 6 attributes: the name of the tile file names,
the number of levels in the pyramid of overviews, the size of the pixel in
CRS units, and the size of the tile in pixels. If you import overlapped
images into the same GeoQuadTree image, the common region of one will be
overwritten with the other.

As an example, I loaded NASA's Blue Marble Next Generation at a resolution
of 15-arc-seconds. This is an image of 86400x43200 pixels in size, that is
about 2.5 GB on disk. I chose the size of the tiles as 270x270 pixels. There
were built 52015 tiles. When I said that i wanted to "avoid  the use of tile
indexes or catalogues of images", I meant that in order to manage a so huge
quantity of tiles, you need a database. The database can be very efficient,
but it's sure that it's even more efficient if you don't need one, and of
course much simpler. For instance, you can write a simple web viewer that
can do all this calculations, without a database. You only need a web
server. I wrote a viewer like similar to Google Maps or Windows Live Maps,
and you could view almost instantaneously images of 2000x2000 pixels in
size, or greater. The response time was only affected by the time needed by
the web server to send the tile images to your browser.

I only wanted a lossless compression, so I chose PNG format for tiles, but
many people also wants a lossless compression, so I'm going to support two
types of compression, PNG and maybe JPEG or JPEG2000. I like the PNG format
because with 4-bands PNGs (RGBA), the alpha channel allows me to store
non-data pixels. With JPEG format, I would "sacrifice" a RGB color to
represent non-data values. There is also the need of supporting multi-band
images, this could be accomplished with as many PNGs as bands. These are
small changes, I will try to make it on the next release.

On the other side, I think storage space is not the big problem nowadays. I
prefer more efficient algorithms in terms of CPU usage, than efficient in
terms of storage space. If someone prefer the reduction of storage space,
the wavelet compression approach could be preferred (LizardTech's MrSID, ER
Mapper's...). I want the freedom to choose a simpler, efficient an FREE
approach.

GeoQuadTree handles a pyramid of overviews. When you create a GeoQuadTree
image, you specifiy the number of levels in the pyramid. Every time you
import a image into a GeoQuadTree, the utility builds the pyramid of
overviews (only updates the tiles affected upside in the pyramid).

Thank you for your interest all you comments,

Jordi


On 11/15/06, Ed McNierney <ed at topozone.com> wrote:
>
>  Simon -
>
> TILEINDEX is a MapServer/quasi-GDAL mechanism for handling a large number
> of rasters as a single unit.  The rasters don't need to be the same size,
> and can overlap - I suspect they can even be different file formats,
> although I've never tried, and they can be stored anywhere in the file
> system.
>
> The TILEINDEX scheme uses an ESRI shapefile (with an optional quadtree
> index on it) as a spatial index for the rasters.  One polygon is generated
> for each raster, with that polygon representing the bounding box of that
> file.  The path to the raster file itself is stored as a string attribute of
> the polygon.  Applications use the spatial/geometry features of the polygon
> to determine which input image(s) if any intersect the area of interest for
> drawing.
>
> It's not the same sort of thing, exactly, and there are no tools I'm aware
> of for managing the individual image organization on disk.  But it works
> well for me.  I use TILEINDEX structures to manage about 500,000 individual
> raster files that are about 40 terabytes altogether (haven't counted lately
> <g>).  It could certainly use enhancement, but it might be a good starting
> point for such a project.
>
>     - Ed
>
> Ed McNierney
> President and Chief Mapmaker
> TopoZone.com / Maps a la carte, Inc.
> 73 Princeton Street, Suite 305
> North Chelmsford, MA  01863
> Phone: +1 (978) 251-4242
> Fax: +1 (978) 251-1396
> ed at topozone.com
>
>  ------------------------------
> *From:* Simon Perkins [mailto:sy at perkins.net]
> *Sent:* Tuesday, November 14, 2006 8:52 PM
> *To:* Ed McNierney
> *Cc:* Brent Fraser; Jordi Gilabert Vall; gdal-dev at lists.maptools.org
> *Subject:* Re: [Gdal-dev] GeoQuadTree - an open format for
> storinggeoreferencedimages
>
>
> TIFF has some pretty serious file size limitations so wouldn't be good for
> these kinds of large rasters. I'm not familiar with TILEINDEX, but is this a
> MapServer related thing? Is that applicable to local image storage on the
> desktop?
>
> I think the GeoQuadTree idea is interesting - it doesn't rely on large
> file support on the OS (not that that's a serious problem for any modern
> OSes), and dealing with lots of small files could be more efficient than one
> large file in some cases I would think.
>
> As for PNG vs JPEG, it depends on whether you're happy to accept lossy
> compression or not. For many applications, customers are averse to losing
> any resolution. It might make sense to make the underlying file format in
> GeoQuadTree flexible acording to application. Actually, I'd prefer to see a
> format that can handle multispectral files - PNG and JPEG are both limited
> to 1 or 3 bands, aren't they? Or are multiple bands stored as separate
> grayscale images?
>
> I would guess that with very large rasters, some sort of pyramid scheme
> becomes important in addition to the tiling, so that if you just want to get
> an overview of the whole image, you don't have to read every single file.
> Does GeoQuadTree handle that?
>
> But, Ed is right that storing very large rasters is a not a new problem.
> So, what do people do? I guess that at the high end, outfits like Google
> Earth use a spatial database to organize multiple individual raster files
> and then stich them together. Could somebody outline the solution used by
> the Virtual Terrain project?
>
> Cheers,
>
> Sy
>
>
> Ed McNierney wrote:
>
> Jordi -
>
> You said you wanted to "avoid the use of tile indexes or catalogues of
> images", but isn't that exactly what your XML catalogue/index does?  It
> seems that the GeoQuadTree format is a different form of that same sort of
> structure.  There are several different ways of doing this now, including
> the TILEINDEX mechanism, tiled TIFF files, etc.  I'm sure there are
> limitations to each, but I'm not sure that yet another tiling scheme will
> help.
>
> In particular, PNG is not the best format for all images, and it's
> important to support other encoding mechanisms, especially JPEG.
> Photographic images are huge when stored in PNG format, and JPEG is usually
> a much better choice.  Conversely, scanned line art and synthetic images
> generally compress and store better as PNG images.
>
>     - Ed
>
> Ed McNierney
> President and Chief Mapmaker
> TopoZone.com / Maps a la carte, Inc.
> 73 Princeton Street, Suite 305
> North Chelmsford, MA  01863
> ed at topozone.com
> (978) 251-4242
>
>  ------------------------------
> *From:* gdal-dev-bounces at lists.maptools.org [
> mailto:gdal-dev-bounces at lists.maptools.org<gdal-dev-bounces at lists.maptools.org>]
> *On Behalf Of *Brent Fraser
> *Sent:* Tuesday, November 14, 2006 3:05 PM
> *To:* Jordi Gilabert Vall; gdal-dev at lists.maptools.org
> *Subject:* Re: [Gdal-dev] GeoQuadTree - an open format for
> storinggeoreferencedimages
>
> For those interested tiling,
>
>   There is similar tiling related discussion/work going on at:
>
>         http://lists.eogeo.org/mailman/listinfo/tiling (do they have a web
> page?)
>
>     and
>             http://www.stereofx.org/terrain.html, implemented in
> http://vterrain.org/, particularly VTBuilder (
> http://vterrain.org/Doc/VTBuilder/overview.html)
>
> Brent Fraser
>
> ----- Original Message -----
> *From:* Jordi Gilabert Vall <jordi at geoquadtree.org>
> *To:* gdal-dev at lists.maptools.org
> *Sent:* Tuesday, November 14, 2006 3:25 AM
> *Subject:* [Gdal-dev] GeoQuadTree - an open format for storing
> georeferencedimages
>
> Hi,
>
> Some time ago I needed the retrieval from very large georeferenced raster
> images in a OGC WMS server, and I wanted to avoid the use of tile indexes or
> catalogues of images, neither a database. I started thinking of an open
> format for storing arbitrarily large georeferenced images. I named this
> format "GeoQuadTree", as it would be based on a quadtree of rectangular
> tiles, each in PNG format on the filesystem, in a simple hierarchical
> structure of folders. I wrote a command line utility for creating it,
> importing from PNG/JPEG/TIFF and exporting to PNG/JPEG/TIFF/GDAL. I also
> wrote a GDAL driver for this format. I tested successfully with my own WMS
> server software, and on MapServer compiled with GDAL support. It worked very
> well on Blue Marble Next Generation at a resolution of 15 arc-seconds, i.e.
> 86400x43200 pixels.
>
> You can find more information on the project web site:
>
> http://geoquadtree.org/
>
> I'm testing the release 1.0.0, you can test it on the subversion
> repository if you want (I haven't packaged it yet).
>
> I think it's a useful format, open, very easy to use, and very efficient
> (in terms of response time).
>
> Do you think it could be useful for you ? Would you like to include it on
> GDAL's next release ?
>
> jordi at geoquadtree org
>
> ------------------------------
> _______________________________________________
> Gdal-dev mailing list
> Gdal-dev at lists.maptools.org
> http://lists.maptools.org/mailman/listinfo/gdal-dev
>
> ------------------------------
>
> _______________________________________________
> Gdal-dev mailing list
> Gdal-dev at lists.maptools.orghttp://lists.maptools.org/mailman/listinfo/gdal-dev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/gdal-dev/attachments/20061115/f9711214/attachment.html