0

PNG, and the deflate compression it uses, is usually pretty good at exploting redundancy. For example, this 18.1kB image only grows to 19.1kB when duplicated and concatenated:

--->

By Contrast, it almost doubles in size to 35.7kB when the copy is mirrored before concatenation

--->

I can't see why this is the case. From my understanding, the first stage of PNG compression, the filtering, shouldn't be able to make use of that redundancy in either of those cases. The second stage on the other hand, the deflate compression, shouldn't have a problem since most if not all of the duplicated parts should fit within it's 32 KiB sliding window size. (for reference the encoder I used was Google's zopflipng)

Why then can't PNG take advantage of the redundancy of that mirrored part?

3
  • What program are you using to make these comparisons? Mar 1, 2019 at 18:06
  • The concatenation was done in GIMP Mar 1, 2019 at 19:14
  • 2
    Sorry, but only few of us have the math competency and knowledge you expect. Most of us can only make rephrasings of what you obviously have noticed: The reduction algorithm can see exact repeatings but not anything which need a math transform before there's same pattern twice. You should ask elsewhere for exact explanations in math terms.
    – user287001
    Mar 2, 2019 at 7:39

1 Answer 1

1

To provide some closure, I have now learned that there's nothing magic about compression.

PNG does the following simple yet effective steps to achieve compression:

  1. Pixel filtering, based on prediction from neighbouring pixels.
  2. Lempel-Ziv style elimination of repeating patterns.
  3. Huffman coding of the resulting data.

In the first concatenated example, the filtering step will produce roughly the same result for for both halves of the picture, since the pixel values are the same.

But since the prediction algorithm uses the left, top and top-left values for prediction, it's not symmetric, and the filtering will produce a very different results for the two halves in the second mirrored concatenated example.

So when Lempel-Ziv is applied, it will see lots of repeated patterns in the first case, and few in the second.

As such, compression efficiency diverges at step 2).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.