[Gdal-dev] GeoQuadTree - an open format forstoringgeoreferencedimages

[Jordi Gilabert Vall]

Thank you Ivan,

You are right, a quadtree can be considered and IS a spatial indexing
technique, I wish I could expressed myself better. I meant that the spatial
indexing can be inherent to the structure of the folders.

If in one quadrant there is only NODATA, its folder simply doesn't exist. As
an example, if I want to access the quadrant NW/NE/SE/NE/SE/NW, then i look
up the tile /1/2/3/2/3/1/gqt.png on the filesystem, but it doesn't exist,
then I know that there is only NODATA pixels in that quadrant. When you
import an image into an existing GeoQuadTree, only the tiles affected by
pixels with data should be rewritten, fusioning the existing ones on the
filesystem with the new pixels. If the tile doesn't exist, you simply create
all the list of parent folders and the tile image. If the tile exists, you
read it to memory, overwrite its pixels with the pixels of the image you are
importing, and write the new tile to the same location.

Some people would like to have the freedom to choose other image formats for
tiles, like JPEG, TIFF or JPEG2000. I'm working on this. For instance, if
you choose JPG format for tiles, the non-data pixels must be translated to a
fixed color, say black, or white, or whatever, but the importing process is
the same.

Regards,

Jordi

On 11/16/06, Ivan Lucena <ILucena at clarku.edu> wrote:
>
> 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 relateddiscussion/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
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/gdal-dev/attachments/20061116/e2c59078/attachment.html