How many people visit the OSGeo planet?

On a regular day in February 2009, about 120 different IPs visited the OSGeo planet front page (http://planet.osgeo.org), about 25% of them from the US:

Google’s WebP vs JPEG: a more comprehensive test

My previous post was a bit unfortunate. The only relevant conclusion of it is that WebP does provide better compression ratios than JPEG for the same level of lossiness. Here is a new comparison method:

• Take the original image and compress it to WebP and JPEG using all possible quality levels. In both cases, the compression program accepts values between 1 and 100, so you get 200 compressed images.
• Find out the PSNR value (lossiness) for each compressed image.
• For a given requested PSNR value, we’ll estimate the image size by interpolating the closest available values (lower and higher)

According to this article, sensible PSNR values are between 20 (low-quality images, allowed for example when very limited bandwidth is available) and 50 (extremely high-quality images, often not necessary). I have used these four lossless images for the test (2048 x 2048 pixels each):

And these are the resulting line-point charts. If there is no data for a given PSNR value, it’s because it was not possible to create an image with that level of lossiness (all values were tested for the quality parameter of both compressors):

Relevant results can be seen in this table (click to see in PDF format):

Comments

• We can see that the WebP format is able to improve JPEG’s performance by about 40% in certain cases. Apparently they have targeted PSNR values in the range [25-30]. If you need a very low level of lossiness (PSNR above 35, for example) you may find that WebP is not better, or even is unable to provide such images.
• I had always suspected that it was mathematically impossible to significantly improve the JPEG compression ratios, but I am impressed by the performance of WebP, at least in the [25-30] range for PSNR (the vast majority of commercial images and video frames probably fall inside that range, by the way.)
• It will be interesting to see if Google adopts (or at least supports) this format in their web browsers, mapping apps, etc. Even if we assume that WebP is, let’s say, 30% better than JPEG globally, will it pay off in a context where capabilities, requirements, volumes etc. often evolve with a geometrical or exponential rather than linear pattern?

Google’s WebP format compresses 6% better than JPEG

This is an attempt to quantify the compression performance of Google’s WebP image format compared to that of JPEG. The method is as follows:

1. Take a large lossless image like this one and cut it up in a not too small number of large tiles. In my test, I have cropped the image a bit to get a 5,000 x 5,000 pixel image, then split it in 25 tiles of 1,000 x 1,000 pixels.
2. Compress all the tiles to the JPEG format and measure the lossiness of each one (I have used the PSNR value)
3. For each tile, compress the original using WebP with different values for the quality parameter, until for each tile you get a WebP image whose PSNR value is just as good as that of the JPEG image obtained in the previous step. What we are doing is getting images with very similar level of lossiness. PSNR values will never be the same. I have given the JPEG tiles a small advantage by requiring a better PSNR value from the WebP tiles.
4. Compute the size ratio for each pair of tiles as [size of the WebP file] / [size of the JPEG file]
5. Take the resulting ratios and compute their average and standard deviation. We can say that WebP is significantly better than JPEG iff the average plus twice the standard deviation is lower than 1, because we’ll be able to say that in 95% of the cases, the WebP image will be smaller than the equivalent (in terms of lossiness) JPEG image. If the average plus twice the standard deviation is bigger than 1, then we’ll have to say that these formats have similar compression performance. This would be a case where compression performances are not significantly different:
   

Results

These are the results of my test (click to enlarge):

As we can see, the average plus twice the standard deviation is below 1:

Conclusions

• According to this test, the WebP format is about 6% better than JPEG. We can say that in 95% of the cases, the resulting image will be at least 6% smaller than the equivalent JPEG image.
• Of course this test has important flaws: we have only tested one type of image (aerial orthophoto), the number of tiles is not very high (25), the lossiness of the compared images was not exactly the same, etc, but I think the result is a good indication of how these two formats compare.
• We can see that the size ratios do follow the Normal distribution pattern, so using the average plus twice the standard deviation value was not a bad idea.
• My opinion is that this is a rather poor result for the WebP format, and it will not replace JPEG as the de facto standard for image delivery on the Web.

Just a test on this funny Fedora netbook

The OLPC XO Fedora laptop has fallen into my hands by chance for a few days and I have obviously tested Unofficial gvSIG Mobile for Openmoko on it. The latest swt.jar for Linux x86 devices looks really nice on it. Background is a tiled (client side) Japanese ArcIMS service:

The Open Mobile IS synchro engine doing its job:

And the WMS client confirming the remote update of the PostGIS table (server is at home, these pics were shot at the office):

On-the-fly reprojection of tiles using your favorite conventional WMS servers

If we accept Spherical Mercator tiles and the ZXY storage scheme as standard and still wish to use all the nice WMS servers we know, we can easily set up a middle tile server like this:

For example, this request gets a OSM-like tile from a conventional Bavarian WMS server:

http://lucasdom.homelinux.org:8077/services/smtile?baseurl=http://www.geodaten.bayern.de/ogc/getogc.cgi%3fREQUEST=GetMap%26SERVICE=WMS%26VERSION=1.1.1%26LAYERS=UK500,TK50&x=8711&y=5643&z=14

The advantage of this over cascading WMS is that the middle server does not need to know the targeted server URL in advance, and the client (possibly a handheld) only has to provide the URL and the tile indices (x, y, z). In this example, I’m assuming that the targeted WMS server supports EPSG:4326, which is true in almost all cases.

A middle server of this type is currently up and running in my home computer. The images you see here are static ones. The URL to get them from the middle server is provided in the code boxes:

http://lucasdom.homelinux.org:8077/services/smtile?baseurl=http://shagrat.icc.es:80/lizardtech/iserv/ows%3fREQUEST=GetMap%26SERVICE=WMS%26VERSION=1.1.1%26LAYERS=mtc250m,mtc50m,mtc25m,mtc10m,mtc5m&x=132657&y=97914&z=18

	Medieval quarter in Barcelona (Spain). Source: Institut Cartogràfic de Catalunya.
	Corresponding OSM tile with the same indices: x = 132657 y = 97914 z = 18

http://lucasdom.homelinux.org:8077/services/smtile?baseurl=http://www.geosignal.org/cgi-bin/wmsmap%3fREQUEST=GetMap%26SERVICE=WMS%26VERSION=1.1.1%26LAYERS=RASTER4000k,RASTER1000k,RASTER500k,RASTER250k,RASTER100k,RASTER50k,RASTER25k,RASTER5k&x=1027&y=717&z=11

	A French town called Tours. Source: Geosignal.
	Corresponding OSM tile with the same indices: x = 1027 y = 717 z = 11

http://lucasdom.homelinux.org:8077/services/smtile?baseurl=http://www.geodaten.bayern.de/ogc/getogc.cgi%3fREQUEST=GetMap%26SERVICE=WMS%26VERSION=1.1.1%26LAYERS=UK500,TK50&x=8711&y=5643&z=14

	A German town called Ingolstadt. Source: Bayerische Vermessungsverwaltung.
	Corresponding OSM tile with the same indices: x = 8711 y = 5643 z = 14

Ready-to-print maps of Britain from Ordnance Survey (PDF, A0 paper)

Yes, Albion in all its 1:250,000 glory, brought to you by the British taxpayer ;)

I downloaded the images from here (1:250,000 Scale Colour Raster), then embedded them in a large LaTeX document using pdfLaTeX. Right-click on the images and choose Save target as…, if you don’t want your web browser to open it. The download might take a while to start. Let me know if you have issues.

London-Birmingham area (PDF, 35 MB, A0 paper, 841 x 1189 mm)

Central Scotland (PDF, 19 MB, A0 paper, 841 x 1189 mm)

Great Britain (PDF, 94 MB, should be printed on a huge format -at least 2 x 2.82 m- or else placenames won’t be readable)

Water utility management using Open Mobile IS & gvSIG Mobile

A nice example of how data synchronization and GIS software integrate on a mobile platform: Manuel Gomez (from Ubikis, Lyon, France) has published a proof of concept application for Windows Mobile where he integrates gvSIG Mobile and the Open Mobile IS framework. From the main control panel, you can switch between the map and the incident administration module, which allows instant synchronization with the organization’s information system. The map is in EPSG:27561 (NTF Paris – Lambert Nord France) which would also allow easy GPS integration because that SRS is available in gvSIG Mobile.

More details in the Tellus project blog.

JPG compresses better and uncompresses faster than ECW

The following comparison method has been applied to three lossless raster maps (urban orthophoto, rural orthophoto and a 8-bpp map):

1. Compress the original image to JPG.
2. Compress the original image to ECW using different compression levels until the resulting ECW file is slightly larger than the JPG file obtained in the previous step (this gives the ECW file a slight advantage).
3. Uncompress both files to a format that imagemagick can read.
4. Compare the uncompressed versions with the original image to quantify their lossiness.

A screenshot illustrating this process can be seen here. I have used GDAL and imagemagick for this. Lossiness is quantified by computing the PSNR value (the higher the better: very lossy images have a low PSNR). The result of this is that JPG files are smaller but less lossy than ECW files:

	Image size (pixels)	JPG size (Mbytes)	ECW size (Mbytes)	JPG PSNR	ECW PSNR	JPG wins?
	5355 x 5349	5.36	5.67	37.7	35.5	YES
	5351 x 5154	6.53	6.93	35.1	34.2	YES
	4096 x 4096	5.08	5.45	27.6	27.4	YES

Faster

The fact that JPG uncompresses faster than ECW can clearly be seen with just one test. The uncompress time can be estimated with the time Linux command applied to gdal_translate:

From JPG to BMP: 18.4 seconds (16.1 seconds if we discount copy time)
From ECW to BMP: 27.1 seconds (24.8 seconds if we discount copy time)
Copy BMP to BMP: 2.3 seconds (estimated time needed to copy result to disk)

So what is good about ECW?

The ECW format allows fast access to application-defined zones of the raster with very low memory consumption. The typical scenario is that the application’s viewport needs to paint about one million pixels on the screen, while the original raster is a huge image with hundreds of millions or even billions of pixels. The JPG format needs to be fully expanded, so usually most of the resulting pixels will not be used.

How can we avoid uncompressing unneeded pixels?

We must use JPG images in a way that does not force us to uncompress pixels that are not going to be painted. One way to achieve this is by cutting up the original image in pieces that are small enough so that -after quickly selecting the needed ones- we can cover the application’s viewport without uncompressing a number of pixels that is significantly larger than the viewport size. In other words: use JPG tiles.

Madrid 1656

The year 1656 saw the creation in Madrid of -at least- two graphic masterpieces: while Velázquez was doing that, the Portuguese cartographer Pedro Teixeira was doing this (click to enlarge):

A superb map of Madrid in the times of the late Spanish Habsburgs.

You can download it as a georeferenced (EPSG:25830) ECW file and also get the Spherical Mercator TMS-style tiles from here. With these, you will be able to do some nice tile replacements – not only with gvSIG Mobile for Linux, but also with any other software that uses the z/x/y scheme to store tiles:

First available level: z = 10; x = 501; y = 386

Last available level: z = 18; x = 128376; y = 98847

Large shapefiles on small screens using a drawable spatial index

Sometimes a large vector layer needs to be rendered on a relatively small area on the screen. This happens especially with mobile devices, where screen size ranges between 240 x 320 and 480 x 850 pixels. If the vector layer affects a small number of pixels, it makes no sense to go through all the shapes and dedicate some (possibly optimized) computation and graphic instructions to each one. We should prepare an alternative for these cases, which will be used when the scale denominator surpasses a certain value.

Using the quadtree approach, we can create before-hand a drawable spatial index that will quickly tell us which pixels must be painted, and hopefully which color should be used. A non-optimized, initial attempt to do this is explained here.

How it will work

We’ll use a shapefile of polygons to illustrate this. Starting from a square that contains the shapefile’s bounding box, we will recursively analyze the relationship of each sub-square with the shapes contained in the shapefile. For example, if we create 9 levels in the spatial index, we’ll end up with a matrix of 512×512 pixels (2^9 = 512), which we will be able to draw very quickly as long as the shapefile does not need more pixels than that. The quadtree algorithm automatically dedicates more computation to borders, while large homogeneous areas (inside one shape or outside all shapes) are discarded quickly. Click to enlarge:

At the lowest level of the spatial index, we’ll have lists of integers telling us which features are intersected by each sub-square.

Creating the spatial index

We’ll have a matrix of integer values with 4 columns and as many rows as we need. Each row will represent a square in our quadtree scheme. Row 0 will be the minimum square than contains the layer’s bounding box:

Row 0: { 0, 3, 4, 0 }
Row 1: { 5, 6, 0, 0 }
...
Row n: { -23, 233, 1, 7000654 }

Each of the four columns will hold information about each of the four sub-squares:

0	1
3	2

The meaning of the integer values v will be:

• If (v < 0): This value indicates that the feature with index -(v+1) in the shapefile completely contains this sub-square. Therefore, this sub-square must be painted with the fill color that corresponds to feature with index -(v+1).
• If (v = 0): This value indicates that this sub-square in completely outside any feature in the shapefile. Therefore, this sub-square must not be painted.
• If (v > 0 and v < 1,000,000): This value indicates this sub-square intersects with at least one feature but is not contained by any feature, and its four sub-squares are described in the row with index (v-1). Therefore, in case we have to paint this sub-square, we’ll use the layer’s border color. This will happen with views where the scale denominator is very large, and the spatial index itself is enough to draw the layer because the width of each screen pixel in map units is larger than the width in map units of the deepest sub-squares in the spatial index quadtree scheme.
• If (v >= 1,000,000): This value will only be found in the lowest level of the quadtree scheme, and indicates that this sub-square is not contained by any feature in the shapefile, but intersects a number of features, and the indices of those intersected features are listed in the array, starting in position (v mod 1,000,000) and the number of features intersected is (v div 1,000,000).

Using the spatial index

Given the current viewport’s bounding box, we’ll start by comparing it with the well-known bounding box of each of the four sub-squares of the square that is being processed:

• If the value is 0, the sub-square is ignored.
• If the value is negative (sub-square is contained by a feature), we’ll find out the fill color that corresponds to that feature and paint it. This may result in a single pixel or a square on the map (see image).
• If the value is positive, there are three cases:
  • If we need to go deeper because the screen pixel width is smaller than the sub-square’s width, then we’ll recursively visit the row indicated by that value.
  • If we need to go deeper but the spatial index does not have more levels, we’ll find a number bigger than 1,000,000, and we’ll have to access the SHP file to get those features, and paint them in the traditional way.
  • If the sub-square’s width is by now smaller than the screen pixel width and the value is indicating a row where the sub-square is described, then we are in the case where the spatial index is enough to paint the layer, and we’ll use the border color to paint this sub-square (which will result in a single pixel). In this case, we cannot use a different color for the border of each feature.

Conclusion

By indicating in a quadtree scheme the index of the feature that contains a certain sub-square or the place where that sub-square is expanded, we can draw the layer very quickly when all the shapes need to be painted in a small portion of the screen. At the bottom of our quadtree spatial index, we can list the indices of the features intersected by each leaf sub-square.

You can see here a video showing how a shapefile (black) and it’s quadtree spatial index (red) are drawn. All the shapes are contained by the viewport, so a traditional spatial index telling which features intersect the viewport would not help: