Feb 10 2014

Compressing VN CGs

Category: Anime,cgCompress,Programs,SoftwareSpiller @ 06:48

I have a lot of images on my computer, random fanart from the web, screenshots of movies I have seen, etc. I recently saw that one of my image folders was 80 GB big, so it is no wonder I care much about image compression.

I was looking through a visual novel CG collection when I thought: shouldn’t this be able to compress well? After all, VN CGs tend to have a lot of similar images with minor modifications like different facial expressions. So I did a quick test, how well does it compress using different lossless compression algorithms:

Chart showing compression ratios

As expected, PNG is quite a bit better than simply zipping BMP images, and WebP fares even better. However what is this, compressing BMP images with 7z literally kills the competition!

The giant gap from ZIP to 7z does not come from the fact that LZMA is superior to Deflate, but because ZIP only allows files to be compressed individually while 7z can treat all files as one big blob of data. This is also why a general purpose compression algorithm can beat the ones optimized for images, as PNG and WebP also compresses images individually.

Note to the comparison: Usually CG collections have an average of 2-3 versions of each image, here we checked on an extreme case with 13 versions. This obviously exaggerates the results, but the trend still stands.

Doing it better

BMP is the superior solution? There is no way I can accept that, we need to do something about that!

If you have ever worked with GIF animations you properly know that you can reduce the size if you only change the differences between each frame. That is exactly what we want to do, but to use PNG and WebP to compress that difference. The problem is that we need to store the differences and information on how those should interact to recreate all the images, and there isn’t a good file format to do that.

How to get from one CG to another using the difference

So I have created a format based on OpenRaster, which is a layered image format to compete with PSD (Photoshop) and XCF (GIMP). I wanted to use it without modifications, but having multiple images in one file, while planned, appears to be far into the future. (I want it now!) It is basically a ZIP file which contains ordinary image files and a XML document describing layers, blend modes, etc.

Next part is automatically creating such a file from a series of images. For this I have written cgCompress (Github page) and while there is still a lot of work to be done, it has proven that we can do it better. Fundamentally this is done by creating all the differences and then with an greedy algorithm, select the ones which will add the least to the total file size. This continues frame by frame until we have recreated all the original images. I have also worked with a optimal solver, but I have not been able to get it to work with more that 3-5 images (because of time complexity).

Using the greedy algorithm I managed to reduce the file size 25.6% compared 7z compressing BMP images: (Lossless WebP used internally)

Comparision of compressed BMP and cgCompress

This is a compression rate of a whooping 88.7%! Of course, this is only because we are dealing with 13 very similar images. 67.2% of the file size is the start image and without a better image compression algorithm, we can do very little to improve that. That means the 12 remaining images use each 2.7% each (1/13 is 7.7%), not much to work with but I believe I can still make improvements.

This is just one case though, while uncommon, some images still need further optimization to get near-perfect results. I have tried compressing an entire CG collection of 154 images and my results where as following:

Chart showing compression ratios for an entire CG collection

Compared to 7z compressed BMP, there was an improvement of 24.0% and compared to WebP it is 61.1%. On average, the set contained 3.92 variations per image; cgCompress manages to do 2.57 as many images compared to ordinary WebP. The difference between those two numbers is the overhead cgCompress requires to recreate all 3.92 variations per image and it depends on how different the variations are. While I don’t know how low it can get, I do believe there is room for improvement here.

I included lossy WebP here as well (done at quality 95) to give a sense of difference between lossless and lossy compression. cgCompress definitively closes the gap, but if you don’t care about your images lossy WebP is still the way to go. (It should be possible to use lossy compression together with the ideas used in cgCompress though.)

Conclusion

cgCompress can significantly reduce the space needed to store visual novel CG collections. While only a moderate improvement of ~25% over 7z compressed BMP, compressed archives only works well for archiving or transferring over networks. cgCompress, as based on OpenRaster, has proper thumbnailing, viewer support and potentially meta-data. With PNG and WebP being the direct contenders, cgCompress provides a big leap in compression ratio.

On a personal note, going from concept to something I can use in 8 days is quite an achievement for me. While the cgCompress code isn’t too great, I’m still quite happy on how this turned out.

Tags: , , ,


Nov 20 2011

Saving images in the correct format

Category: Software,WebdevelopmentSpiller @ 00:32

I quite often see images stored in wrong formats, see for example this website: http://www.retrofit-anime.com/index.html.

Notice the gradient, it contains ugly lines moving from top to bottom. (More visible on a dark background.) It was properly saved as a 1px high image and then stretched downwards (in order to make the file smaller), however it was saved as JPEG. There are two issues here. First of all, the compression artifacts becomes quite clear as they are repeated, however gradients like this also compresses better in a lossless format like PNG, so it is actually larger than it could have been, with worse quality.

So here is a introduction to image formats which will hopefully give you an idea of when to use one format instead of another.

Compression

File formats uses one of 3 types of compression:

  • No compression: The file is simply raw data and can be read and modified directly. The files usually ends up being rather large though.
  • Lossless compression: The format saves the data in a way that makes the data fill less on the disc, however it still contains all the data. (Like a .zip archive.)
  • Lossy compression: Saves the data, but trows away some of it in a way that the user (hopefully) wouldn’t notice.

Each type has its pros and cons. (Examples are all non-image formats.)

Not compressing at all makes it very fast to display the image when you can access the data just as fast. This is usually the case with an HDD as its reading speed is up to 100 MiB/s (and with SSD reaching speeds of 300MiB/s), however not on the web as the speed is rather slow, often something like 0.5MiB/s (which is 4Mb/s). However its simplicity is its main strength and most file formats (.txt, .exe, .doc, .html, .css, .tar and so on) are therefore uncompressed.

Lossless compression reduces file size greatly in most cases and is therefore used when file size is of importance. The downside is that it becomes slower to open and save, as it has to decompress and compress the file each time. It is also a lot harder to implement. Examples are .docx, .zip and .flac.

Lossy compression reaches file sizes which are normally much smaller than possible with lossless compression, however in the process some data is lost and is impossible to recover. While this might sound terrible, the low file size sometimes is worth the trade-off. Lossy compression usually try to trow away the data humans wouldn’t notice (so much) to avoid losing ‘important’ data. Formats which use this kind of compression is normally media formats (like sound, images and movies) as this kind of data usually is rather large. Examples are .mp3 and .h264.

Image format types

There are two different kind of ways to store an image, Raster and Vector. Raster describes a 2D grid of pixels, just like how your monitor displays it. All popular formats are Raster, that is JPEG, PNG and so on. Vector describes how drawing functions should draw on this 2D grid in order to create an image, for example: ‘draw a line from (30,40) to (100,50) and then draw a circle in (50,50) with radius 10’. Examples on vector formats are SVG and Lego Mindstorms RIC.

Since Vector images are something you create from the bottom up, focus in this post will be on the Raster formats.

Colors in images

The more colors you have to represent in an image, the larger the file becomes. So there are several ways of storing colors and switching from one to another greatly affects size. There are three important modes: indexed, grayscale and truecolor.

Truecolor

This is the normal model which contains all the colors you can display on your monitor. This is normally stored as RGB, i.e. three colors.

Grayscale

Grayscale contains only shades of gray and is stored with a single color. This makes it much smaller than Truecolor, however only in grayscale.

Indexed

Indexed is a bit different. Instead of storing a color for each pixel, it stores an index. This index then refers to a color table which contains a list of truecolors. This means it can only store a few colors (usually up to 256), but you can usually get good results anyway with dithering. Some images, like screenshots might only contain a certain subset of colors which can be indexed, reducing the size greatly sometimes without any loss.

Notice however that this index also takes up a bit of space and if your image contains less than 256 pixels, you might be better of staying in Truecolor.

Alpha

This is a special color, which can be used in addition to Truecolor, Grayscale or Indexed. Alpha specifies the transparency of an pixel which can be quite useful when combining several images together.

However in most situations it is not needed, so make sure you don’t save the alpha values in those cases.

Size of colors

In truecolor and grayscale you store levels of certain colors, like Red, Green and Blue for RGB. However the amount of different shades of the color affect file size too.

A color is usually stored as 8-bit which equals to 1 byte, meaning that it can contain 2^8 = 256 shades of that color. Grayscale uses one color, which means one byte per pixel, while Truecolor uses 3 colors, so it uses 3 bytes per color. If there is an alpha color for each pixel, it would use 1 byte more, to a total of 4 bytes per pixel.

Indexed images with a color table of 256 colors would need to store 8 bits per pixel, as 2^8 = 256. However if your color table is 250 you do still need to store 8 bits, since 7 bits only gives 2^7 = 128. So there is not as much advantage going saving a few colors, unless it will reduce the amount of bits needed per pixel. (The color table will of course be smaller though.)

As said, a color is usually sized to 8-bit, however some images might store more than that per color. 16-bit per color is often used with photography as the more levels increases accuracy when editing the images. However this also means that it uses up twice as much space per pixel, 48-bits, and you can’t display this on monitors either as most are 24-bits (or 18-bits for cheap screens). If you don’t need this, converting to 8-bit can significantly reduce file size.

Overview of image formats

Here is a table over the most common image formats (and I added Lego RIC just for fun).

The most important are PNG (lossless) and JPEG (lossy) as most of the others either compresses badly or is relatively unsupported.

The uncompressed formats like .png and .bmp should be avoided unless you have a good reason to use it, PNG provides just as good result at smaller file size.

TIFF is a bit of a joker, it has many features, however only some are implemented in certain applications. Only use it if you know what you are doing.

JPEG2000, JPEG XR and WebP are some of the popular formats for the future, however both are poorly supported at the moment.

GIF still rule animated images, however there are three alternatives out there, APNG, MNG and WebP.

Guidelines:

Saving while working with images (working copy)

Always use the applications native format if you intend to continue working with the image. This is the only way to ensure that as most data as possible is saved. Most formats doesn’t support layers or any other advanced feature your image editor supports, so all this information will get lost.

If you must save it in a genetic image format, use a lossless one like PNG. (TIFF might save more depending on the implementation, experiment!) If  you save it in a lossy format like JPEG, you will degrade image quality each time you save (and then open it again), as it each time trows a different set of information out.

Lossless versus lossy

In general I tend to use lossless whenever file size is not of great concern. HDDs have reached sizes of 3TB, the only thing not worth saving in lossless today is movies.

But lossless does compress better than lossy in some cases. JPEG works great for  photographs and can easily half the file size compared to PNG. However if the images are more simple graphics, like vector graphics or screenshots of your desktop, PNG suddenly compresses much better. Secondly, the JPEG compression artifacts ruins text readability, so PNG is a much better choice here.

To give you an example, here are two separate screenshots of my two monitors.

Example of good PNG compression

The left monitor, the PNG is 448KB and the JPEG became 777KB at acceptable quality. Try to convert the PNG I supplied and see the difference in quality for yourself.

Example of poor PNG compression

On the right monitor a large amount of my wallpaper was visible. Now the PNG suddenly became 1.95 MB while the JPEG was 801KB. (I have only supplied the JPEG here.)

So as you can see, compression depends a lot on the image. For photos use JPEG. For screenshots, your pie-charts and other similar images, use PNG. For images somewhere in between those, try saving in both PNG and JPEG and compare the sizes and quality.

Don’t convert a lossy image

I have seen it a couple times now, a JPEG image converted to PNG for absolutely no reason. The image will not magically get better by converting it to a lossless format! And even in cases where a lossless normally would compress better, it will not because the JPEG compression added artifacts which the lossless compression conserves. The first test image above became 1.5MB instead of 448KB when converting it to JPEG and back.

Trying to convert a lossy to another lossy format will only mean that you loose even more information in the image, so this is not desirable either.

So it is best to keep the lossy file as it is if you are not going to edit on it.

GIF versus PNG

If you try to save an image in both GIF and PNG, PNG might end up being quite a bit larger. However that is because GIF only supports indexed mode and that it is therefore automatically saved like this, while the PNG is saved in truecolor.

If you save PNG is indexed mode, PNG will in almost every case be smaller than GIF. So there is no reason to use GIF, as PNG compresses better and have more features (except animation).

If you are a web-developer, PNG with alpha works in IE7 and up, while PNG in indexed mode should work in IE6 AFAIK. So you should be able to replace GIFs with PNGs here too.

Index colors when possible

Indexing the colors can reduce the size quite a bit. With diagrams and the like you might not use the 256 colors up at all, so you can sometimes do this conversion without loss or with minimal changes. (In those cases you can dither the image to get prettier results, but it will hurt compression ratio. I would recommend to avoid it…)

The file comparison table a few sections above is an indexed PNG, and no colors were reduced as it only contained 140 different colors from the start. The size in truecolor is 22.5 KB, and when indexed it is 9.79 KB. (In JPEG it became ~125 KB…)

Don’t save transparent pixels

If you have some parts of the image fully transparent, the pixels color will still be saved even though it will not be displayed. This way, when you change the alpha, the original color will remain.

However if you do not need to do this anymore, you can change all completely transparent pixels to the same color. While it will not change the image’s appearance, it will reduce the file size. (Your image editor might have an option to do this for you.)

Animation

GIF is still the main format for animations around, and while it only works for indexed images, there are no real alternatives out there which have good application support.

There are currently three formats other than GIF which supports animation, APNG, MNG and WebP.

APNG is a modification of PNG which adds animation, however the issue with this format is that it uses same mime-type as PNG and thus can’t be differentiated. PNG directly disallows multiple images, so they are two different formats. However it is implemented in Firefox (the creators) and Opera.

MNG is also based on PNG, however it is a separate format. It is quite advanced and offer many possibilities than APNG does not, however its complexity is what has caused it to have nearly nonexistent support. (GIMP support, however animation support in GIMP isn’t that great anyway…)

WebP have recently announced animation support (which works similarly as GIF), and as it supports both lossless, lossy and alpha, it sounds promising. While WebP is implemented in Google Chrome (the creators) and Opera, I do not know whether animation have been added yet.

The future

Both JPEG and PNG is fairly old, PNG is from 1996 and JPEG 1992. Compared to how audio and video formats have evolved the past 10 years, images formats are still stuck in the past. I suspect that you could just replace the default compression algorithm in PNG with something like LZMA and get a 10-20% improvement…

JPEG2000 by the JPEG group was a new format which intended to replace the JPEG format. However support have not been very widespread even though the format was publicized 10 years ago. It is getting better by now though.

There are other similar formats, like JPEG XR by Microsoft, however it does not have good support either. WebP is the newest of the bunch which was publicized 1 year ago, however support is increasing and since it is based on WebM, good browser support is likely and it is already natively implemented in Chrome and Opera (and should be working in any WebM compatible browser via a JavaScript shim).

Which format that is going to get widespread is hard to tell. WebP seems to have a better chance on the Web, however I suspect that it doesn’t have as many advanced features as JPEG2000 and JPEG XR which especially photographers wants.

My guess however is that the Web is the most crucial factor, as this is where lossy compression is most important. I still however have my doubts with WebP in professional photography.

Tags: , , , , , , ,