[Gdal-dev] GeoQuadTree - an open format forstoringgeoreferencedimages

Thu Nov 16 13:57:52 EST 2006

Excellent work Jordi,

I really like it, but I am just curious about one comment that you made:

>> ... 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. ...

I guess that you didn't pick the "Quad Tree" name in vain; And Quad Tree is considered as a spatial indexing technique by some (*Spatial Access Method* Chapter 6 in "Spatial Databases, with Application to GIS" by Rigaux, Scholl and Voisard). I hope you don't have a copyright issue with Hannan Samet :-) Just kidding!

Does your algorithm include the Quad Tree's concept of having four initial quadrants NW, NE, SW and SE to breakdown your images and repeat it recursively until the desired level of details? I guess that the four quadrants are translated into four folders in "GeoQuadTree". That is really clever!

And what happens if in one quadrant of your image there is only NODATA value? You just skip that folder's subfolders creation just like Quad Tree does with tree nodes? 

In this case I can see how important the NODATA is to your technique and why you picked PNG. You are concerned about the format that a web browser can display and that is what you need at that point of the process.

Very very good. I am looking forward to try it out.

Best regards,

---
Ivan Lucena

________________________________________
From: gdal-dev-bounces at lists.maptools.org [mailto:gdal-dev-bounces at lists.maptools.org] On Behalf Of Jordi Gilabert Vall
Sent: Wednesday, November 15, 2006 3:51 AM
To: Ed McNierney
Cc: gdal-dev at lists.maptools.org
Subject: Re: [Gdal-dev] GeoQuadTree - an open format forstoringgeoreferencedimages

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] 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 
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.org

http://lists.maptools.org/mailman/listinfo/gdal-dev