I've pared down wavelet image compression to what I believe are the bare essentials, producing a simple implementation with compression ratios similar to JPEG 2000, but several times faster. Using OpenMP multithreading, it's faster yet.

GFWX was developed by Graham Fyffe at the USC Institute for Creative Technologies Graphics Lab, to help manage the large amount of video data produced by the New Dimensions in Testimony project. This required real-time, lossy compression of Bayer patterned raw images and none of the existing formats fit the bill. This work was sponsored by the U.S. Army Research Laboratory (ARL) under contract number W911NF-14-D-0005, and the USC Shoah Foundation.

Features

• Lossy and lossless compression

• Progressive decoding with optional downsampling

• Fast, simple, optionally multithreaded C++11 implementation

• Supports 8-bit or 16-bit data (or anything in between), signed or unsigned

• Stores up to 65536 channels (not limited to RGBA)

• Stores up to 65536 layers or frames

• Bayer mode to improve compression on raw camera sensor data

• Chroma downsampling option, even in Bayer mode

• Programmable lossless color / channel / layer transform (not limited to YUV or whatever)

• Optionally stores an arbitrary metadata block

Performance

Let's compare the compressed file sizes and timings on my machine for several open-source lossless image formats. GFWX includes timings with and without OpenMP (OMP). I've also tested GraLIC and FLIC, but these are closed-source. I'm testing on a cat poster by Alvesgaspar [CC BY-SA 3.0], via Wikimedia Commons, which comprises several cats.

Usage Examples

Let's look at some code. I'm going to use OpenCV to load and save images, but please note you can use whatever libraries you want with GFWX because it has no dependencies. First let's load an image, and save it in GFWX format:

That's a complete code example. How about decoding:

You can also downsample the image by any power of two by changing a few lines:

This produces the following downsampled image in just 0.04 seconds (instead of 1.2 seconds for the whole image):

Now let's truncate the byte buffer to only 5000 bytes, and print the result of decompress, which is the next point of interest:

This produces the following image from the incomplete data stream:

It also outputs "Next point of interest is at byte 10892", so let's try 10892 bytes:

Loading the bytes up to the next point of interest before decompressing again allowed us to get an additional level of detail. It also now tells us that the next point of interest is at byte 38072. We can continue in this way to achieve completely efficient progressive decoding of a byte stream as the bytes become available, without wasting time decoding partial buffers that are no better than the last one we decoded. As an additional efficiency, if you set the last parameter of the decompress function to true, it will return GFWX::ResultOk if you have enough bytes to decode your requested downsampled size, without going through the entire rigamarole of decoding the pixels. Use this if you just want to wait until you have enough bytes.

Now let's look at lossy compression. First let's compress the living daylights out of this image by setting quality to 4 and chroma scaling to 4, and set the filter to GFWX::FilterCubic and the color transform to YUV so it looks nicer. This shrinks the file by a factor of 690. We'll decode it downsampled again for viewing, but trust me, it looks terrible at full size:

Let's look at a more reasonable quality at full size, say quality 64. This shrinks the file by a factor of 78. Here's a crop of the full size result, with the compressed file on the left, and the original on the right:

1995 Technology, Today!

The wavelet image compression pipeline consists of three steps: forward transform, quantization, and encoding (and the accompanying decoding, dequantizing, and inverse transform), described in e.g. Hilton et al. "Compressing Still and Moving Images with Wavelets", Multimedia Systems, 1994. GFWX uses an in-place lifting scheme to compute the wavelet transforms, described by Wim Sweldens in multiple papers in 1994 and 1995, my favorite of which is Sweldens, W. "The Lifting Scheme: A New Philosophy in Biorthogonal Wavelet Constructions", 1995. The two options for lifting in GFWX are equivalent to the 5/3 (linear) and 9/7 (cubic) wavelet filters present in JPEG 2000, but in GFWX either may be used for lossy or lossless coding, and I threw in median-clamping for the 9/7 wavelet to reduce ringing artifacts. Both of these filters are also described in Sweldens' 1995 paper. For encoding the transformed coefficients, GFWX uses limited-length Golomb-Rice codes, described in Rice, R. and Plaunt, J. "Adaptive Variable-Length Coding for Efficient Compression of Spacecraft Television Data", 1971. These codes have the advantage of being computationally simple, and quite accurately model the probability distribution of prediction residuals or wavelet coefficients (to within half a bit). Whenever the probability of zero is very high, a zero-run-length is encoded instead of a Golomb-Rice symbol, because an extra half bit is relatively costly in such a case. JPEG-LS uses Golomb-Rice codes and zero-runs to code prediction residuals, but GFWX uses them to encode wavelet coefficients, and differs in the way that the Golomb parameter is selected, and in the way that zero-run-lengths are detected and encoded. GFWX selects the Golomb parameter based on the first and second moments of the neighborhood around a coefficient, which can be either a simple sliding window (fast) or a set of nearby coefficients sampled from the same frequency band as well as the parent band (slightly slower). The parameter is selected using a simple fixed partitioning of the first and second moment landscape using quadratic boundaries, which were hand-picked to fit statistics gathered from the Kodak true color image suite. A similar scheme is used for switching to zero-run coding, and also for selecting a Golomb parameter to code the zero-run length. Despite the simplicity of this encoding scheme, it often slightly outperforms the EBCOT arithmetic encoder used in JPEG 2000 for lossless encoding.

White Paper

GFWX is described in more detail in ICT Technical Report no. ICT-TR-01-2016.pdf.

License

GFWX is released under the 3-clause BSD license:

Copyright (c) 2015, University of Southern California. All rights reserved. Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.

2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.

3. Neither the name of the organization nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

Binaries

You can download the following zip file containing simple compressor and decompressor executables for 64-bit Windows operating systems. Use at your own risk! Download GFWX_bin_Winx64.zip

Simple Source Code

The source code is a single header file, using only standard C++ libraries so there are no dependencies, and it's less than 1000 lines long. It's so simple, I'm literally just going to paste the code right here. You can also download it here, or from github. There's also a rust implementation and a fuzzer to check for vulnerabilities.