Editing PNG (section)

=== Compression ===
PNG uses a two-stage compression process:
* pre-compression: filtering (prediction)
* compression: [[DEFLATE]]

PNG uses [[DEFLATE]], a non-patented [[lossless data compression]] [[algorithm]] involving a combination of [[LZ77 and LZ78|LZ77]] and [[Huffman coding]]. [[Permissive software licence|Permissively licensed]] DEFLATE implementations, such as [[zlib]], are widely available.

Compared to formats with [[lossy compression]] such as JPEG, choosing a compression setting higher than average delays processing, but often does not result in a significantly smaller file size.

==== Filtering ====
[[File:Pixel-prediction.svg|thumb|128px|PNG's filter method 0 can use the data in pixels A, B, and C to predict the value for X.]]
[[File:PNG-Gradient.png|thumb|128px|A PNG with 256 colors, which is only 251 bytes large with pre-filter. The same image as a GIF would be more than thirteen times larger.]]

Before DEFLATE is applied, the data is transformed via a prediction method: a single ''filter method'' is used for the entire image, while for each image line, a ''filter type'' is chosen to transform the data to make it more efficiently compressible.{{Sfn|W3C|2003|loc=[https://www.w3.org/TR/PNG/#9Filters 9 Filtering]}} The filter type used for a scanline is prepended to the scanline to enable inline decompression.

There is only one filter method in the current PNG specification (denoted method 0), and thus in practice the only choice is which filter type to apply to each line. For this method, the filter predicts the value of each pixel based on the values of previous neighboring pixels, and subtracts the predicted color of the pixel from the actual value, as in [[DPCM]]. An image line filtered in this way is often more compressible than the raw image line would be, especially if it is similar to the line above, since the differences from prediction will generally be clustered around 0, rather than spread over all possible image values. This is particularly important in relating separate rows, since DEFLATE has no understanding that an image is a 2D entity, and instead just sees the image data as a stream of bytes.

There are five filter types for filter method 0; each type predicts the value of each byte (of the image data before filtering) based on the corresponding byte of the pixel to the left (''A''), the pixel above (''B''), and the pixel above and to the left (''C'') or some combination thereof, and encodes the ''difference'' between the predicted value and the actual value. Filters are applied to byte values, not pixels; pixel values may be one or two bytes, or several values per byte, but never cross byte boundaries. The filter types are:<ref>{{cite web| url = http://libpng.org/pub/png/spec/1.2/PNG-Filters.html| work = PNG Specification| title = Filter Algorithms}}</ref>

{| class="wikitable"
|-
! Type byte !! Filter name !! Predicted value
|-
| 0|| None|| Zero (so that the raw byte value passes through unaltered)
|-
| 1|| Sub|| Byte ''A'' (to the left)
|-
| 2|| Up|| Byte ''B'' (above)
|-
| 3|| Average|| Mean of bytes ''A'' and ''B'', rounded down
|-
| 4|| Paeth|| ''A'', ''B'', or ''C'', whichever is closest to {{nowrap|1=''p'' = ''A'' + ''B'' − ''C''}}
|}
The Paeth filter is based on an algorithm by [[Alan W. Paeth]].<ref>{{cite journal|last1=Paeth|first1=Alan W.|title=Image File Compression Made Easy|journal=Graphics Gems 2|editor-last=Arvo|editor-first=James|publisher=Academic Press, San Diego|date=1991|pages=93–100|doi=10.1016/B978-0-08-050754-5.50029-3|isbn=0-12-064480-0}} {{closed access}}</ref>
Compare to the version of [[DPCM]] used in [[lossless JPEG]], and to the [[discrete wavelet transform]] using 1 × 2, 2 × 1, or (for the Paeth predictor) 2 × 2 windows and [[Haar wavelet]]s.

Compression is further improved by choosing filter types adaptively on a line-by-line basis. This improvement, and a heuristic method of implementing it commonly used by PNG-writing software, were created by [[Lee Daniel Crocker]], who tested the methods on many images during the creation of the format;<ref>{{cite journal| url = http://www.ddj.com/architect/184409587?pgno=4| title = PNG: The Portable Network Graphic Format| journal = [[Dr. Dobb's Journal]]| issue = 232|date=July 1995| volume = 20| pages = 36–44| first = Lee Daniel| last = Crocker| author-link = Lee Daniel Crocker}}</ref> the choice of filter is a component of file size optimization, as discussed below.

If interlacing is used, each stage of the interlacing is filtered separately, meaning that the image can be progressively rendered as each stage is received; however, interlacing generally makes compression less effective.