I want to devise a rather basic indicator (I will call it LICAP) of how good is on average a lossy image compression algorithm at compressing an image over the various degrees of compression.
LICAP Calculation
The LICAP calculation described here is still at a draft stage, so it is subject to change and any feedback is welcome.
Core Idea
Here is a typical diagram which shows the relative performance of two compression methods through their rate-distortion curves:
(source: JPEG vs. JPEG2000: An Objective Comparison of Image Encoding Quality)
Two parameters (the PSNR and the Compression Ratio in this case) are used to measure the loss of information in the image versus the degree of compression achieved.
Each sample in the diagram is produced by setting up the compression algorithm to compress the image at a specified quality.
For instance the quality parameter could be an integer ranging from 1 to 100. With quality 1 the algorithm would compress the image as much as possible, albeit at a high loss of information. With quality 100 the algorithm would compress the image with minimum or no loss of information, achieving only a small compression.
The core idea with the LICAP is to collapse the data from all samples into a single number; visually speaking the idea is to calculate the average height of the rate-distortion curves, so that for instance it may be possible to get an overall initial indication of which of two compression algorithms may be better by simply comparing two numbers.
Nominal vs Storage Size
A typical image can be logically represented as an array of pixels having a certain number of rows (height) and columns (width) and each pixel can be typically coded using 3 bytes (one for each of the Red, Green and Blue color components), therefore the Nominal Size of the image in bytes will be: width * height * 3.
An image compression algorithm will typically allow an image to be stored in a file whose size is smaller than the image nominal size. I will refer to this compressed image size as the Storage Size.
Average PSNR Calculation
The Peak Signal-to-Noise Ratio (PSNR) is a rather simple and common way of measuring the loss of information. The higher the value, the lower the information loss. The problem is that when the information loss is zero, i.e. when the source image and the compressed image are identical (this may be the case with max quality), the PSNR is infinite.
To avoid this problem, when measuring the information loss of each sample, only the first stage of the PSNR calculation is performed, i.e. only the Total Squared Error (where Total Squared Error = Mean Squared Error * Nominal Size) is calculated.
The Total Squared Error can then be averaged over all samples and then divided by the nominal size of the image to get the averaged Mean Squared Error.
The LICAP can then be calculated as the PSNR corresponding to the averaged Mean Squared Error.
Here below I am still going to use the term PSNR instead of Total Squared Error when referring to the distortion of individual samples, they are both measures of the same feature anyway and the reasoning is the same.
Continuous Range
Different compression algorithms will produce samples at sizes that do not match each other.
For instance the rate-distortion diagram shows a JPEG2000 sample at compression ratio 80 whereas the closest JPEG sample is at a different compression ratio 84.
To provide a consistent LICAP calculation, instead of averaging the available PSNR samples, it is necessary to average over a continuous range of storage sizes.
For those storage sizes that are not covered by the compressed image samples, it will be necessary to construct the relative PSNR values.
For instance the JPEG2000 curve shows one sample at about (20, 36) and the next sample is at about (30, 33), and the PSNR values in the range 21 to 29 are defined through a linear interpolation between these to samples.
When calculating the LICAP however no interpolation is performed, instead the sample which reflects the higher compression (hence the higher loss) is used.
The reasoning behind this is that if we wanted to reduce an image down to a size no greater than a certain threshold, we would have to go for the higher compression.
Range Extension
Different compression algorithms will generally have a different storage size for their lowest quality sample and likewise a different storage size for their highest quality sample.
For instance in the rate-distortion diagram the maximum JPEG2000 compression ratio is 100 and the maximum JPEG compression ration is 84.
To provide a consistent LICAP calculation, the range over which the LICAP is calculated needs to be extended beyond the storage size range of any particular compression algorithm.
The LICAP range therefore will go from 1 byte to the nominal size of the image to be compressed.
Image Scaling
To construct some sensible PSNR values relative to sizes that are beyond the compression algorithm range, the following method is used:
- The image is scaled, i.e. its width and height are increased or decreased by a certain factor
- The scaled image is compressed
- The size of the compressed image is taken to be the Storage Size
- The compressed image is rescaled back to the original width and height
- The PSNR value is calculated by comparing the rescaled image against the original image
The scales used to increase the image width and height are:
- 2:1
- 4:1
- 8:1
The scales used to decrease the image width and height are:
- 1:2
- 1:4
- 1:8
- 1:16
- etc..
Until the image cannot be scaled down any further because its width or height would become zero.
Even a single pixel image however may not get compressed down to a storage size of 1 byte, so for sizes that are smaller than the smallest rescaled and compressed sample, the information loss is calculated as the average information loss that would be expected from a completely random image.
Sub-Optimal Samples
As samples are produces at various scales and various qualities, it may happen that a sample has the same storage size of another sample but a higher distortion.
It may also happen that a sample is produced with a higher storage size and a higher distortion than another sample.
All sub-optimal samples are simply discarded and do not contribute to the LICAP value.
Benchmarks
Image Compression Algorithms
- JPEG image compression library (release 7 of 27-Jun-2009) from the Independent JPEG Group (IJG).
Test Images
The USC-SIPI Image Database includes the Lena image, which is probably the most widely used test image for all sorts of image processing algorithms (see The Lenna Story for some background).
For my test I am going to use all 16 colour images in the Miscellaneous section of the USC-SIPI Image Database.
Results
Provisional, subject to possible improvements in the LICAP calculation and possible bug fixes in my implementation.
Test Image | LICAP (dB) | ||||||||
---|---|---|---|---|---|---|---|---|---|
Preview | Details | IJG v.7 |
TBD v.# |
TBD v.# |
TBD v.# |
TBD v.# |
TBD v.# |
TBD v.# |
TBD v.# |
Girl 4.1.01 256x256 24 Bit |
31.08 | - | - | - | - | - | - | - | |
Couple 4.1.02 256x256 24 Bit |
30.51 | - | - | - | - | - | - | - | |
Girl 4.1.03 256x256 24 Bit |
34.27 | - | - | - | - | - | - | - | |
Girl 4.1.04 256x256 24 Bit |
32.34 | - | - | - | - | - | - | - | |
House 4.1.05 256x256 24 Bit |
32.18 | - | - | - | - | - | - | - | |
Tree 4.1.06 256x256 24 Bit |
30.10 | - | - | - | - | - | - | - | |
Jelly Beans 4.1.07 256x256 24 Bit |
32.85 | - | - | - | - | - | - | - | |
Jelly Beans 4.1.08 256x256 24 Bit |
32.40 | - | - | - | - | - | - | - | |
Splash 4.2.01 512x512 24 Bit |
36.03 | - | - | - | - | - | - | - | |
Tiffany 4.2.02 512x512 24 Bit |
34.56 | - | - | - | - | - | - | - | |
Mandrill 4.2.03 512x512 24 Bit |
29.23 | - | - | - | - | - | - | - | |
Lena 4.2.04 512x512 24 Bit |
35.56 | - | - | - | - | - | - | - | |
Airplane F-16 4.2.05 512x512 24 Bit |
35.54 | - | - | - | - | - | - | - | |
Sailboat on Lake 4.2.06 512x512 24 Bit |
31.99 | - | - | - | - | - | - | - | |
Peppers 4.2.07 512x512 24 Bit |
33.74 | - | - | - | - | - | - | - | |
House house 512x512 24 Bit |
33.95 | - | - | - | - | - | - | - |
Here are the lossy image compression algorithms ranked according to the LICAP averaged over the image set:
Algorithm | Version | LICAP (dB) |
---|---|---|
IJG JPEG Library | 7 | 32.90 |
TBD | - | - |
TBD | - | - |
TBD | - | - |
TBD | - | - |
TBD | - | - |
TBD | - | - |
TBD | - | - |
LICAP C++ Source Code
To be published.