Using Huffman coding to compress images taken by the iPhone camera

Question

Im thinking to use the Huffman coding to make an app that takes pictures right from the iPhone camera and compress it. Would it be possible for the hardware to handle the complex computation and building the tree ? In other words, is it doable?

Thank you

Planula

iPhones are getting more and more powerful so depending how big images you are looking for and what speed baseline you are setting should be possible. Take a look at this implementation and you can try to profile the speed for yourself: raywenderlich/swift-algorithm-club – Deraign

Answer 1

If you mean the image files (like jpg, png, etc), then you should know that they are already compressed with algorithms specific to images. The resulting files would not huffman compress much, if at all.

If you mean that you are going to take the UIImage raw pixel data and compress it, you could do that. I am sure that the iPhone could handle it.

If this is for a fun project, then go for it. If you want this to be a useful and used app, you will have some challenges

1. It is very unlikely that Huffman will be better than the standard image compression used in JPG, PNG, etc.

2. Apple has already seen a need for better compression and implemented HEIF in iOS 11. WWDC Video about HEIF

3. They did a lot of work in the OS and Photos app to make sure to use HEIF locally, but if you share the photo it turns it into something anyone could use (e.g. JPG)

4. All of the compression they implement uses hardware acceleration. You could do this too, but the code is a lot harder than Huffman.

So, for learning and fun, it's a good project -- it might be easier to do as a Mac app instead, but for something meant to be real, it would be extremely hard to overcome the above issues.

Ardellearden

Thank you @Lou . Your answer is very helpful – Planula

Answer 2

There are 2 parts, encoding and decoding. The encoding process involves constructing a tree or a table based representation of a tree. The decoding process covers reading from huff encoding bytes and undoing a delta. It would likely be difficult to get much speed advantage in the encoding as compared to PNG, but for decoding a very effective speedup can be seen by moving the decoding logic to the GPU with Metal. You can have a look at the full source code of an example that does just that for grayscale images on github Metal Huffman.

Anett

A new rice based codec with a decoder implemented in the GPU can be found at this SO answer: https://mcmap.net/q/494810/-memory-write-performance-gpu-cpu-shared-memory – Anett