Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

image/png: Encode is not as efficient as zlib-based encoders #16196

Closed
olt opened this issue Jun 27, 2016 · 9 comments
Closed

image/png: Encode is not as efficient as zlib-based encoders #16196

olt opened this issue Jun 27, 2016 · 9 comments
Labels
FrozenDueToAge
Milestone
Go1.8

Comments

@olt
Copy link
Contributor

olt commented Jun 27, 2016

Paletted PNGs like this map tile (http://a.tile.openstreetmap.org/13/4404/2688.png) will increase by 20-30% in size when encoded with image/png.Encode.
See https://gist.github.com/olt/022a206444f20c147c4bc9a54fd1a433 for example re-encoder.

The size does not change much when I re-encode the image with Image Magick (convert) or Python Image Library (PIL/Pillow):

% curl': curl "http://a.tile.openstreetmap.org/13/4404/2688.png" -o orig.png
% convert orig.png image-magick.png
% python -c 'from PIL import Image; Image.open("orig.png").save("pil.png")'
% go run convert.go
% ls -l *.png
-rw-r--r--  1 olt  staff  44099 Jun 27 15:25 go.png
-rw-r--r--  1 olt  staff  34583 Jun 27 15:21 image-magick.png
-rw-r--r--  1 olt  staff  34491 Jun 27 15:21 orig.png
-rw-r--r--  1 olt  staff  34521 Jun 27 15:22 pil.png

Changing the compression level in Go does not make any huge difference.

zlib allows to set different compress strategies. One of the strategies is Z_FILTERED, which is optimized for filtered data as found in PNGs.

From http://www.zlib.net/manual.html:

The strategy parameter is used to tune the compression algorithm. Use the value ... Z_FILTERED for data produced by a filter (or predictor),...
The effect of Z_FILTERED is to force more Huffman coding and less string matching; it is somewhat intermediate between Z_DEFAULT_STRATEGY and Z_HUFFMAN_ONLY.

PIL allows to select the strategy and it gives file sizes in the range of 34521 to 45117:

% python -c 'from PIL import Image; Image.open("orig.png").save("pil.png", compress_type=Image.HUFFMAN_ONLY)'

Implementing a Z_FILTERED-like strategy should give much smaller files and it should have more impact than #15622.
@olt
Copy link
Contributor Author

olt commented Jun 27, 2016

Oh, file sizes are within 1-2% between 1.4 and 1.7beta2.

@josharian
Copy link
Contributor

@nigeltao @dsnet @klauspost

@klauspost
Copy link
Contributor

FWIW, Fileoptimzer can squeeze out an additional 5% with its lossless recompression tools.

I haven't dug into PNG, but this seems more like there are some compression methods missing rather than an entropy encoding (deflate) problem. I looked through the filter chooser function, and couldn't spot anything immediately wrong, but it does seem that there is something sub-optimal in there.

@nigeltao
Copy link
Contributor

It's been a while since I looked at it, but IIRC the Go PNG filter chooser has the same algorithm as libpng.

That's just about PNG filtering as in https://www.w3.org/TR/PNG/#9Filters and not anything to do with zlib.

@nigeltao nigeltao self-assigned this Jun 29, 2016
@olt
Copy link
Contributor Author

olt commented Jun 30, 2016

I found the issue. I dug into the PIL code and found out that it they do not apply filters for paletted images. image/png chooses the filter with the smallest sum, but apparently the unfiltered results can be compressed much better (at least for paletted images).

Changing a single line from
if level != zlib.NoCompression {
to
if level != zlib.NoCompression && cb != cbP8 {
reduced my test image from 43366 to 35177 bytes.

This is in line with the results from PIL and Image Magick.

@olt
Copy link
Contributor Author

olt commented Jun 30, 2016

I found the following comment in the PNG book

[...] the PNG development group has come up with a few rules of thumb (or heuristics) for choosing filters wisely. The first rule is that filters are rarely useful on palette images, so don't even bother with them.

@bradfitz bradfitz added this to the Go1.8 milestone Jun 30, 2016
@bradfitz
Copy link
Contributor

@olt, nice find.

@olt
Copy link
Contributor Author

olt commented Sep 27, 2016

I did tests with more files. Compression is better for almost all files, except for a few tiny files:

file                                                                         old           new           speedup
./testdata/blue-purple-pink-large.lossless.webp.png                          64136         49311         0.77x
./testdata/blue-purple-pink-large.no-filter.lossy.webp.png                   58609         46484         0.79x
./testdata/blue-purple-pink-large.no-filter.lossy.webp.ycbcr.png.png         126092        121210        0.96x
./testdata/blue-purple-pink-large.normal-filter.lossy.webp.png               60013         46523         0.78x
./testdata/blue-purple-pink-large.normal-filter.lossy.webp.ycbcr.png.png     149197        144709        0.97x
./testdata/blue-purple-pink-large.png.png                                    64136         49311         0.77x
./testdata/blue-purple-pink-large.simple-filter.lossy.webp.png               58251         45929         0.79x
./testdata/blue-purple-pink-large.simple-filter.lossy.webp.ycbcr.png.png     135952        135233        0.99x
./testdata/blue-purple-pink.lossless.webp.png                                5916          4918          0.83x
./testdata/blue-purple-pink.lossy.webp.png                                   5377          4747          0.88x
./testdata/blue-purple-pink.lossy.webp.ycbcr.png.png                         12390         12424         1.00x
./testdata/blue-purple-pink.lzwcompressed.tiff.png                           5916          4918          0.83x
./testdata/blue-purple-pink.png.png                                          5916          4918          0.83x
./testdata/bw-deflate.tiff.png                                               539           449           0.83x
./testdata/bw-packbits.tiff.png                                              539           449           0.83x
./testdata/bw-uncompressed.tiff.png                                          539           449           0.83x
./testdata/go-turns-two-14x18.png.png                                        853           1108          1.30x
./testdata/go-turns-two-280x360.jpeg.png                                     43623         34008         0.78x
./testdata/go-turns-two-down-ab.png.png                                      5847          5015          0.86x
./testdata/go-turns-two-down-bl.png.png                                      4824          4099          0.85x
./testdata/go-turns-two-down-cr.png.png                                      5016          4288          0.85x
./testdata/go-turns-two-down-nn.png.png                                      6075          5180          0.85x
./testdata/go-turns-two-rotate-ab.png.png                                    2481          2130          0.86x
./testdata/go-turns-two-rotate-bl.png.png                                    2481          2130          0.86x
./testdata/go-turns-two-rotate-cr.png.png                                    2565          2276          0.89x
./testdata/go-turns-two-rotate-nn.png.png                                    2593          2872          1.11x
./testdata/go-turns-two-up-ab.png.png                                        2916          2742          0.94x
./testdata/go-turns-two-up-bl.png.png                                        2914          2744          0.94x
./testdata/go-turns-two-up-cr.png.png                                        3165          3003          0.95x
./testdata/go-turns-two-up-nn.png.png                                        945           1320          1.40x
./testdata/gopher-doc.1bpp.lossless.webp.png                                 749           579           0.77x
./testdata/gopher-doc.1bpp.png.png                                           749           579           0.77x
./testdata/gopher-doc.2bpp.lossless.webp.png                                 1158          935           0.81x
./testdata/gopher-doc.2bpp.png.png                                           1158          935           0.81x
./testdata/gopher-doc.4bpp.lossless.webp.png                                 1989          1608          0.81x
./testdata/gopher-doc.4bpp.png.png                                           1989          1608          0.81x
./testdata/gopher-doc.8bpp.lossless.webp.png                                 4700          4358          0.93x
./testdata/gopher-doc.8bpp.png.png                                           4700          4358          0.93x
./testdata/no_compress.tiff.png                                              507           526           1.04x
./testdata/no_rps.tiff.png                                                   507           526           1.04x
./testdata/testpattern.png.png                                               1016          2317          2.28x
./testdata/tux-rotate-ab.png.png                                             1485          1222          0.82x
./testdata/tux-rotate-bl.png.png                                             1779          1531          0.86x
./testdata/tux-rotate-cr.png.png                                             1766          1542          0.87x
./testdata/tux-rotate-nn.png.png                                             1391          1149          0.83x
./testdata/tux.lossless.webp.png                                             14718         11294         0.77x
./testdata/tux.png.png                                                       14718         11294         0.77x
./testdata/video-001-16bit.tiff.png                                          6418          5567          0.87x
./testdata/video-001-gray-16bit.tiff.png                                     14443         14073         0.97x
./testdata/video-001-gray.tiff.png                                           14443         14073         0.97x
./testdata/video-001-paletted.tiff.png                                       11255         10991         0.98x
./testdata/video-001-strip-64.tiff.png                                       6418          5567          0.87x
./testdata/video-001-tile-64x64.tiff.png                                     6418          5567          0.87x
./testdata/video-001-uncompressed.tiff.png                                   6418          5567          0.87x
./testdata/video-001.bmp.png                                                 6418          5567          0.87x
./testdata/video-001.lossy.webp.png                                          5818          5067          0.87x
./testdata/video-001.lossy.webp.ycbcr.png.png                                13749         13469         0.98x
./testdata/video-001.png.png                                                 6418          5567          0.87x
./testdata/video-001.tiff.png                                                6418          5567          0.87x
./testdata/yellow_rose-small.bmp.png                                         470           507           1.08x
./testdata/yellow_rose-small.png.png                                         470           507           1.08x
./testdata/yellow_rose.lossless.webp.png                                     22773         17192         0.75x
./testdata/yellow_rose.lossy-with-alpha.webp.nycbcra.png.png                 82347         70882         0.86x
./testdata/yellow_rose.lossy-with-alpha.webp.png                             17506         13827         0.79x
./testdata/yellow_rose.lossy.webp.png                                        21416         16516         0.77x
./testdata/yellow_rose.lossy.webp.ycbcr.png.png                              71849         62866         0.87x
./testdata/yellow_rose.png.png                                               22773         17192         0.75x

Code/test files can be found here: https://github.com/olt/compressbench

I created (my first) patch https://go-review.googlesource.com/#/c/29872/

@gopherbot
Copy link

CL https://golang.org/cl/29872 mentions this issue.

@golang golang locked and limited conversation to collaborators Sep 27, 2017
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Assignees
No one assigned
Labels
FrozenDueToAge
Projects
None yet
Milestone
Go1.8
Development

No branches or pull requests
6 participants
@bradfitz @josharian @olt @klauspost @nigeltao @gopherbot