4

I was not sure where to put this question, so I put it here. Feel free to move it to another stack exchange site moderators.

Lets say I have a 10 gigs of pictures (or for that matter any type of data, please don't answer the question specifically relating to pictures). Let's pretend that I have the fastest computer in the world and all the time to use it on my hands.

What lossless compression algorithm should I use to compress these files as much as theoretically possible?

Also, if there is currently a program that will do this, please provide a link.

SamB
  • 143
  • 5
  • Well, is mostly belongs on TCS, but will be instantly closed there as not-research-level... It is answered, so I think it may stay. –  Jul 10 '11 at 15:57
  • 4
    Why has no one mentioned theoretical properties of information theory and entropy yet? That seems to be pretty apparently what the OP is asking about given the statement "*Let's pretend that I have the fastest computer in the world and all the time to use it on my hands.*" – cardinal Jul 11 '11 at 02:21
  • @cardinal would you care to explain? It sounds very interesting. – SamB Jul 11 '11 at 02:34

4 Answers4

6

The answer depends on the content of your images. As there is no free lunch in lossless compression you cannot create a lossless compression algorithm which generally performs good on all input images. I.e. if you tune your compression algorithm so that it performs good on certain kind of images then there are always images where it must perform badly, meaning that it increases the filesize compared to the uncompressed representation. So you should have an idea of the image content that you are going to process.

The next question would be if you can afford lossy compression or if you require lossless compression.

In case of typical digital photos JPEG 2000 is a good candidate, as it supports both, lossy and lossless compression and is tuned for photo content. For lossy compression there is also the very real possibility of advances in encoder technology, e.g. the recent alternative JPEG encoder Guetzli by Google, which makes better use of specifics in human visual perception to allocate more bits to features that make a difference in perception.

For images with big areas of the same color and sharp edges, as diagrams and graphs or stylized maps, PNG is a good match. PNG is a lossless file format, supports transparency and achieves good compression for b/w images.

Also wikipedia has a comparison of image file formats.

In the spirit of Kolmogorov complexity there might be images that can be compressed much further by finding an algorithm which generates the image but usually this applies only in special cases like fractals or simple raytraced CG images, not for typical digital photos.

Arbitrary (non-image) data

For general data Arithmetic coding is a good choice, as it can achieve nearly optimal compression (with respect to the occurance proportion of symbols in the data), when the alphabet for data representation suits the data. (E.g. a spectral representation of small chunks of typical music recordings is usually better suited for compression than a time series representation).

Thies Heidecke
  • 546
  • 3
  • 10
  • 1
    And in particular, images use compression different from audio files, which is different from documents. The best compression comes from having the best knowledge of your set of files. – Erik P. Jul 10 '11 at 17:58
  • 1
    Although I appreciate your answer, if you read my post, I said "**please don't answer the question specifically relating to pictures**". Also, of my own fault, I didn't not make it clear that I am looking for lossless compression. – SamB Jul 11 '11 at 00:27
  • @Thies, Re "*not for typical digital photos*", **since when was this ever proven**? – Pacerier Apr 29 '17 at 08:47
  • @Pacerier I wanted to point out that there might be procedurally generated images, that in theory can be compressed a lot by just transmitting the program that generated the image. But this will almost never work for measured images like photos. Even for images that are known to be generated by a program (e.g. rendered), this is a hard inverse problem. For measured photos it's statistically highly unlikely to come up with a short program that generates the image. I wanted to make aware of the concept and possibility of Kolmogorov complexity and it's theoretical implications for compression. – Thies Heidecke May 02 '17 at 11:56
6

There's no optimal algorithm, but universal algorithmic induction comes close to optimality, in the sense that the difference in compressed file size between it and any other compression algorithm is bounded by a value that depends on the algorithm but not the data.

It's not computable, so that's a disadvantage.

The method is as follows: choose a programming language (really, a universal turing machine), and look at every possible program in order of length. Skip the programs that don't halt (this is why it's not computable). Choose the first program whose output is equal to your uncompressed file. Use it as a self-expanding archive.

Peter de Blanc
  • 61
  • 1
  • 2
  • interestingly if you put a limit on the decompression time this take care of the halting problem :) – skyde Jan 13 '21 at 23:23
1

I you dont care about the time it take to compress it`s really hard to do better then DLI for image compression https://sites.google.com/site/dlimagecomp/

skyde
  • 435
  • 6
  • 10
0

The more you know about what you want to compress, the more assumptions you can make and, consequently, the better you can compress. Also you have to decide between lossy and lossless. That is the most important part.

Emre
  • 2,564
  • 15
  • 22