search

golang / go

The Go programming language
https://go.dev
BSD 3-Clause "New" or "Revised" License
123.01k stars 17.54k forks source link

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

Closed olt closed 7 years ago

olt commented 8 years ago

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 commented 8 years ago

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

josharian commented 8 years ago

@nigeltao @dsnet @klauspost

klauspost commented 8 years ago

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 commented 8 years ago

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.

olt commented 8 years ago

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 commented 8 years ago

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 commented 8 years ago

@olt, nice find.

olt commented 7 years ago

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 commented 7 years ago

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