Lossless Image Compression Through Super-Resolution
github.com
github.com
To be clear -- it stores a low-res version in the output file, uses neural networks to predict the full-res version, then encodes the difference between the predicted full-res version and the actual full-res version, and stores that difference as well. (Technically, multiple iterations of this.)
I've been wondering when image and video compression would start utilizing standard neural network "dictionaries" to achieve greater compression, at the (small) cost of requiring a local NN file that encodes all the standard image "elements".
This seems like a great step in that direction.
How is this lossless? The entropy coder is what makes this technique lossless. The neural network predicts a probability distribution over pixels, and the entropy coder can find a near optimal mapping of pixel values to bits based on those probabilities (near optimal according to Shannon’s entropy).
On practicality of the method, I don’t expect SReC to replace PNGs anytime soon. The current implementation is not efficient for client-side single-image decoding because of the cost of loading a neural network into memory. However, for decoding many high-quality images, this is efficient because the memory cost is amortized. Additionally, the model size can be reduced with a more efficient architecture and pruning/quantization. Finally, as neural networks become more popular in image-related applications, I think the hardware and software support to run neural nets client-side efficiently will get better. This project in its current form is just a proof of concept that we can get state-of-the-art compression rates using neural network. The previous practical neural network-based approach (L3C) was not able to beat FLIF on Open Images.
For a detailed explanation of how SReC works and results, please refer to our paper: https://arxiv.org/abs/2004.02872.
Btw, SReC is pronounced “Shrek”, because both ogres and neural nets have layers ;).
Isn't the quality of the prediction heavily influenced by how common the encoded content is?
- Using the previously decoded data, try to predict what's next, and the probability or being right
- Using an entropy coder, encode the difference between what is predicted and the actual data. The predicted probability will be used to define how many bits to assign to each possible value. The higher the probability, the less bits will be used for a "right" answer and the more bits will be used for a "wrong" answer.
Decoding works by "replaying" what the encoder did.
The most interesting part is the prediction. So much that some people think of compression as a better test for AIs that the Turing test. You are basically asking the computer to solve one of these sequence-based IQ tests.
And of course neural networks are one of the first thing we tend to think of when we want to implement an AI, and unsurprising it is not an uncommon approach for compression. For instance, the latest PAQ compressors use neural networks.
Of course, all that is a general idea. How to do it in practice is where the real challenge is. Here, the clever part is to "grow" the image from low to high resolution. Which kinds of reminds me of wavelet compression.
Minor nitpick: In the idealized model there is no single prediction that you can take the difference with. There is just a probability distribution and you encode the actual data using this distribution.
Taking the difference between the most likely prediction and the actual data is just a very common implementation strategy.
"A single prediction that you can take the difference with" makes some assumptions about the shape of your distribution, at least under any reasonable model of "code the difference" where, e.g., probability decreases as the difference gets larger. These are often very good assumptions, to be fair.
The trained neural network weights tend to be very large, and hard to compress, and the hutter prize requires the size of them to be counted too.
To win the hutter prize, you'd probably need some kind of training-during-inference system.
I bet this scales way better than any other method on large datasets
Reminds me of doing something similar, albeit a thousand times dumber in ~2004 when I had to find a way to "compress" interior automotive audio data, indicator sounds, things like that. At some point instead of using traditional copression, I synthesized a wave function and and only stored its parameters and the delta from the actual wave which achieved great compression ratios. It was expensive to compress but virtually free to decompress. And as a side effect my student mind was forever blown by the beauty of it.
And speaking of storing the networks: I don't know that you would ever want to pay the memory hit that it would take to store the entire network in memory just to decompress images or video, nor the performance hit the decompression takes. The trade-off here is trading reduced drive space for massively increased RAM and CPU/GPU time. I don't know any case where you'd want to make that trade-off, at least not at this magnitude.
Again though: it's an awesome idea. I just don't know that's ever going to be anything other than a cool ML curiosity.
Isn’t this just a special version of a problem any type of compression will always have? There’s all kinds of ways you can imagine improving on a format like JPEG, but the reason it’s useful is because it’s locked down and widely supported.
A neural network that models upscaling is, on the other hand, not only inconveniently big, but also completely explicit (inviting all sorts of tweaking and replacement) and adapted to a specific data set (further demanding specialized replacements for performance reasons).
Among the applications that are able to store and process the neural network, which is no small feat, I don't think many would be able to amortize the cost of a tailored neural network over a large, fixed set of very homogeneous images.
The imagenet64 model is over 21 MB: saving 21 MB over PNG size, at 4.29 vs 5.74 bpp (table 2a in the article), requires a set of more than 83 MB of perfectly imagenet64-like PNG images, which is a lot. Compressing with a custom upscaling model the image datasets used for neural network experiments, which are large and stable, is the most likely good application (with the side benefit of producing useful and interesting downscaled images for free in addition to compressing the originals).
And as for performance/resources -- great point. But what about video, where the space/bandwidth improvements become drastically more important?
Since h.264 and h.265 already has dedicated hardware, would it be reasonable to assume that a chip dedicated to this would handle it just fine?
And that if you've already got hardware for video, then of course you'd just re-use it for still images?
I guess you could have versioning of your file format, and some sort of organization that standardized it.
All in all, a very interesting idea.
now this might be prohibitive for images over the web, but it'd be interesting whether it might be applicable for images with huge resolutions for printing, where single images are are hundreds of megabytes
There could be a release of a new model every 6 months or something (although even that is probably too often, the incremental improvement due to statistical changes in the distribution of images being compressed isn't likely to change much over time), and you just keep a copy of all the old models (or lazily download them like msft foundation c++ library versions when you install an application).
The models themselves aren't very large.
One scenario I can picture is the Netflix app on your TV. Firstly, they create a neural network trained on the video data in their library and ship it to all their clients while they are idle. They could then stream very high-quality video at lower bandwidth than they currently use and, assuming decoding can be done quickly enough, provide a great experience for their users. Any updates to the neural network could be rolled out gradually and in the background.
The dictionary had to be updated from time to time to keep a good compression rate as the Google website changed over time. There was a whole protocol to handle verifying what dictionary the client had and such.
The big memory load wouldn't neccesarily be a problem for the likes of Youtube and Netflix - they could just have dedicated machines which do nothing else but decoding. The performance penalty could be a killer though.
The "dictionary" approach was roughly what vector quantization was all about. The idea of turning lossy encoders into lossless by also encoding the error is a old one too, but somewhat derailed by focus on embedable codecs with an ideal of each additional bit read will improve your estimate.
I think the potentially novelty here is really in the unfortunately-named-but-too-late-now super-resolution aspects. You could do the same sort of thing ages ago with say IFS projection, or wavelet (and related) trees, or VQ dictionaries with a resolution bump, but they were limited by the training a bit (although this approach might have some overtraining issues that make it worse for particular applications.
Browse thumbnails, open original. Without any processes to generate / keep in sync these files.
Raw images typically contain an embedded, full-sized JPEG version of the image as well.
All of these are easily extracted with `exiftool -b -NameOfBinaryTag $file > thumb.jpg`.
I've found while making PhotoStructure that the quality of these embedded images are surprisingly inconsistent, though. Some makes and models do odd things, like handle rotation inconsistently, add black bars to the image (presumably to fit the camera display whose aspect ratio is different from the sensor), render the thumb with a color or gamma shift, or apply low quality reduction algorithms (apparent due to nearest-neighbor jaggies).
I ended up having to add a setting that lets users ignore these previews or thumbnails (to choose between "fast" and "high quality").
The guy was using neural networks for compression long time ago before it was a thing again.
EDIT: Oh, somebody mentioned it already (but it's really good, free & totally worth reading)
For example, StyleGAN takes months of compute-time on a cluster of high-end GPUs to train to get the photorealistic face model we've all seen. But generating new faces from the trained model only takes mere seconds on a low-end GPU or even a CPU.
The decode process takes the last image from the process above, and iteratively applies the upscalers until the original image has been reproduced.
Link to the code in question: https://github.com/caoscott/SReC/blob/master/src/l3c/bitcodi...
To decompress then, reverse the CNN on the low information bitstream with the tensor.
You now have a high information bitstream which is almost like your original.
Then use the entropy series of bits to fix the difference. You're back to the original.
Losslessly.
So I wonder if this, or a similar process can be done on non-image data...
But that's not all...
If it works with non-image data, it would also say that mathematically, low information (lower) numbers could be converted into high information (higher) numbers with a tensor and entropy values...
We could view the CNN + tensor as mathematical function, and we can view the entropy as a difference...
In other words:
Someone who is a mathematician might be able to derive some identities, some new understandings in number theory from this...
If by non-image data you mean something like audio, then yes it could probably work.
They did not have any idea and they were dicks about it as usual.
A few years ago, I worked for #bigcorp on a product which, among other things, optimized and productized a super resolution model and made it available to customers.
For anyone looking for it - it should be available in several open source libraries (and closed source #bigcorp packages) as an already trained model which is ready to deploy
The only parts that are slow in comparison are the bits written in Python and those are just the frontend application.
There's not much room for performance improvement.
For example, YACC is highly optimized, but the parsers in GCC and LLVM are an order of magnitude faster because they are custom recursive-descent parsers optimized for the specific languages that those compilers actually support. GCC switched from YACC/Bison, which are each highly optimized, in version 4.0, and parsing was sped up dramatically.
Additionally, a lot of the glue code in any pytorch project is python, which is astonishingly slow compared to C++.
So I reiterate, a 10x speedup would be mundane when moving from a generic solution like pytorch and coding something specific for using this technique for image compression.
Finally, Pytorch is optimized primarily for model training in an Nvidia GPU. Applying models doesn't need a GPU for good performance, and in fact probably isn't a net win due to the need to allocate and copy data, and the fact that consumer computers often have slow integrated GPU's that can't run nvidia gpu code, and the compatible system (OpenCL, which basically isn't used in ML in a serious way yet) is supported on many systems on the CPU only since integrated GPU's are still slower than the CPU even with OpenCL.
Unless it is with battery powered devices. However I would say that with general web browsing without ad-blocking it wouldn't count much either it terms of bandwidth or processing milliwatts.
https://en.wikipedia.org/wiki/Jan_Sloot
Gave me a comical thought if such things can be permitted.
You split into rgb and b/w, turn the pictures into blurred vector graphics. Generate and use an incredibly large spectrum of compression formulas made up of separable approaches that each are sorted in such a way that one can dial into the most movie-like result.
3d models for the top million famous actors and 10 seconds of speech then deepfake to infinite resolution.
Speech to text with plot analysis since most movies are pretty much the same.
Sure, it wont be lossless but replacing a few unknown actors with famous ones and having a few accidental happy endings seems entirely reasonable.
(this is by Fabrice Bellard, one wonder how he can achieve so much)
I remember talking with the team and they had production apps using it and reducing bandwidth by 30%, while only adding a few hundred kb to the app binary.
e: actually a better metric would be how much does it compress compared to doing the resolution increase with just lanczos in place of the neural net and keeping the Delta part intact
Out of focus parts of an image should be pretty darned easy to compress using what is effectively a thumbnail.
That said, the idea of having an image format where 'preview' code barely has to do any work at all is pretty damned cool.
That's why most compression algorithms use fixed point mathematics.
There are ways to quantizise neutral networks to make them use integer coefficients, but that tends to lose quite a lot of performance.
Still, this is a very promising lead to explore. Thank you for sharing :)
The compression scheme here is similar. Transmit a low res version of an image, use a neural network to guess what a 2x size image would look like, then send just the delta to fix where the prediction was wrong. Then do it again until the final resolution image is reached.
If the neural network is terrible, you'd still get a lossless image recovery, but the amount of data sent in deltas would be greater than just sending the image uncompressed.
It can then take all the "best fit" block from the previous frame and use it to generate a prediction of the next frame. It then computes the difference between the prediction and the actual frame, and stores this difference along with the set of motion vectors used to generate the prediction image.
If nothing much has changed, just camera moving a bit about, the difference between the prediction and the actual frame data is very small and can be easily compressed. Also, the range of the motion vectors is typically limited to +/-16 pixels, and you only need one per block, so they take up very little space.
"For lossless super-resolution, we predict the probability of a high-resolution image, conditioned on the low-resolution input"
Most applications are memory movement constrained rather than compute constrained.
If its something you don't necessarily require all the time its still probably cheaper to just store it instead of run it through a ANN. You just need to look at the prices of a GPU server compared with storage costs on AWS and the estimated run time to see there is still a large difference.
I mean I could be wrong (and I'd love to be since I looked at a lot of SR stuff before) but that's sort of the conclusion I reached before and I don't really see anything has significantly changed since
You're compressing only once. Decompression is usually way less expensive and that happens on the client, so without additional cost to netflix/youtube.
Of course this does not mean youtube must use it on all the videos including the ones with 10 views.
In terms of quality vs bit rate, ML-based methods are superior.
In terms of computation and memory requirements, they're orders of magnitude worse. It's a trade-off; TINSTAAFL.
Agreed, although this bit is unclear - the compressed representations of the ML-based methods take up much less space in memory than traditional methods, but yes - the decompression pipeline is memory-intensive due to intermediary feature maps.
Is a soft-link a lossless compression?
It's like the old joke about a pub where they optimise by numbering all the jokes, .. just the joke number isn't enough, it can be used to losslessly recover the joke, but it's using the community storage to hold the data.
Another way of looking at it is that you could have a 3D model of a person, as used for CG in movies, and then have an error map + config data to return an image of the person that is exactly the same as a mask of a photo that was taken. The error map + config data wouldn't really be a "lossless compression". Much of the data would lie in the 3D model. Do you agree that this would not be "lossless compression"? So, there's a dividing line somewhere?!
1) that the aggregate savings from compressing the images needs to outweigh the initial cost of distributing the decompressor.
2) to be lossless, decompression must be deterministic an unambiguous, so you can't compress _everything_ down to zero bits; you can compress only _one_ thing down to zero bits, because otherwise you wouldn't be able to unambiguously determine which thing is represented by your zero bits.
There was also a classic thread that surfaced recently on HN about a compression challenge whereby someone tried to disengenuously attempt to compress a file of random data (uncompressable by definition) by splitting it on a character then deleting that character from each file. Was a simple algorithm, that appeared to require fewer bits to encode. The problem is, all this person did was shift the bits to the filesystem’s metadata, which is not obvious from the command line. The final encoding ended up taking more bits once you take said metadata into account.
If I'm allowed to bring along an unlimited amount of background data, then I can compress everything down to zero bits.
In contrast, an algorithm like LZ78 can expressed in a 5 line python script and perform decently on a wide variety of data types.
If by "background data" you mean the decompressor, this is patently false. No matter how much information is contained in the decompressor (The Algorithm + stable weights that don't change), you can only compress one thing down to any given new representation ( low resolution image + differential from rescale using stable weights ).
If by "background data" you mean new data that the decompressor doesn't already have, then you're ignoring the definition of compression. Your compressed data is all bits sent on the fly that aren't already possessed by the side doing the decompression regardless of obtuse naming scheme.
> I'm arguing it's the same as this image compression technique.
That's wrong, because this scheme doesn't claim to send a custom image generator instead of each image, which is what you're proposing.
Further, if you're not familiar with the pigeonhole principle, it might be worth a read on Wikipedia.
Ideally they would have trained the network on a non-overlapping collection of images from their testing but if they did that I don't see it mentioned in the paper.
The model is only 15.72 MiB (after compression with xz), so it would amortize pretty quickly... even if it was trained on the input it looks like it still may be pretty competitive at a fairly modest collection size.
[Aside: I've heard they know nothing of qi in Qatar, ;oP]