Like attention, no more lost, your support means a lot to me!
🔥 Hi, I’m Chouchou. GitHub · Android-Notebook has been included in this article. Welcome to grow up with Chouchou Peng. (Contact information at GitHub)
preface
- PNG (Protable Network Graphics) is a very common image format. A deep understanding of the principle of PNG file is helpful to strengthen the understanding of the image codec process and facilitate the optimization work.
- In this article, I will take you to explore the data structure of PNG images & coding principles & optimization methods. Please be sure to like and follow if you can help, it really means a lot to me.
series
- The graphics | ready! Say pictures related to the concept of”
- The graphics | new-confucianism. PNG besides lossless what else do you know?”
- The Android | cliche! Screen adaptation principle & plan summary notes”
- The Android | so-accurately weighed various! Tell me about the whole process of loading picture”
directory
1. An overview of the
1.1 define
PNG (Portable Network Graphics) is a bitmap format with lossless compression. It itself is designed to replace the GIF format, so it bears some similarities to GIF.
1.1 the characteristics of
-
Lossless Compression (Lossless Compression) : LZ77 derived algorithm + Huffman coding, higher Compression rate, smaller volume and no loss of data;
-
Support transparent: support 8-bit transparent channel, while GIF only supports 1-bit transparent channel, JPEG does not support transparent channel;
-
The less complex the image, the higher the compression rate using PNG (see section 3 coding Principles for reasons);
-
Five pixel/color types are supported
- Indexed colour (Indexed- Colour, 8 bits)
- Greyscale (8 bits)
- True color (Truecolour, 24 bits)
- Greyscale with Alpha, 16 bits
- True Color Transparency (Truecolour with Alpha, 32-bit)
Note: the three PNG types mentioned on the Internet are: PNG 8, PNG 24 and PNG 32. After checking the encyclopedia, PNG official website and PNG File Protocol, no supporting evidence can be found, so this paper will not elaborate.
2. PNG data structure
In this section, we discuss the data structure of a PNG image. A PNG file (or data stream) consists of an 8-byte signature and several chunks.
2.1 PNG signature
The 8 bytes in the header of a PNG file are the file signature (or magic number). This value will be used to identify whether the file is a PNG file. The data is fixed at 8950 4E47 0D0A 1A0A. Here is a PNG file I opened arbitrarily:
Tip: Use 010 Editor to view file binary data. When you first open a PNG file, it prompts you to install png.bt, which will help you read the meaning of each piece of data.
2.2 data block
- Data block type
PNG defines two types of data blocks: critical chunks and ancillary chunks.
Key data blocks are required to successfully decode images from PNG data streams, while secondary data blocks are optional, and we will focus on key data blocks. Key data blocks are divided into four types: file header data block, palette data block, image data block and image end data block.
- The internal structure of a data block
Each data block in PNG consists of four parts:
| The name of the | The number of bytes | describe |
|---|---|---|
| Length (length) | 4 | Specifies the length of the data field in the data block |
| Chunk Type Code | 4 | It consists of (A-Z, A-Z) |
| data | length | Data block data |
| Cyclic redundancy Detection (CRC) | 4 | Used for error detection |
- Header chunk IDHR (Header Chunk)
The header data block is the first data block in a PNG file. It contains the basic information of a PNG file and consists of 13 bytes. The data structure is as follows:
| field | The number of bytes | describe |
|---|---|---|
| Image Width | 4 | In pixels |
| Image Height | 4 | In pixels |
| Image Bit depth | 1 | / |
| ColorType | 1 | 5 color types: The index color gray Gray transparent True color (24 bit direct color) True color Transparency (32 bit direct color) |
| Compression method | 1 | LZ77 derivative algorithm |
| Filter method | 1 | / |
| Interlaced scanning method | 1 | 0: non-interlaced scan 1: Adam7 (7 times interlaced scanning method) |
- Palette Chunk
The palette data block contains the color transform data related to indexed color image, which is only related to indexed color image and is placed before the image data block IDAT. True-color PNG data streams can also have palette data blocks, which are intended to be used by non-true-color display programs to quantify the image data and thus display the image.
- Image Data Chunk (IDAT)
Image data block is the actual data stored in an image and can contain multiple sequential image data blocks.
- IEND (Image Trailer Chunk)
End of image data block indicates that the PNG file or data stream has ended and must be placed at the end.
3. PNG coding principle
By referring to Protable Network Graphic (PNG) Specification (Second Edition), it can be learned that the encoding process of PNG files is divided into five stages:
- 1. By Pass Extraction
- Scanline serialization
- 3. Filtering
- 4. Compression
- 5. Chunking
I don’t understand the first two steps, so I’ll go straight to the last three.
3.3 Filtering
The main idea of this step is incremental encoding, that is, a value can be expressed as a difference from the previous value.
Such as: ,3,4,5,6,7,8,3,4,5,6,7,8 [2] [2],3,4,5,6,7,8 [2] can be encoded as [2, 3-2 = 1, 4-3 = 1, 5-4 = 1, 6, 7-6 = 1-5 = 1, 8-7 = 1] [2, 3-2 = 1, 4-3 = 1 = 1, 6, 5-4-5 = 1, 7-6 = 1, 8-7 = 1] [2, 3-2 = 1, 4-3 = 1, 5-4 = 1, 6-5 = 1, 7-6 = 1, 8-7 = 1] = > ,1,1,1,1,1,1,1,1,1,1,1,1 [2] [2],1,1,1,1,1,1 [2]
You can see that the incrementally encoded data becomes a lot of repetitive, low-value data, which is good for compression, for the reasons I mentioned in Section 3.4 (p.
Back to the PNG filtering step, this step is mainly to select the appropriate difference filter and process each pixel in each line respectively, so that the value of the difference coding can be repeated as much as possible and as small as possible. The main points are as follows:
- 1. There are five types of filters
In the following chunking step, the filtering method used in the coding process is recorded in the Filter Method field of IHDR.
- 2, for optimal effect, each line can use a different filter
- 3. Filtering is done by channel rather than pixel
Filtering is done by channel rather than pixel, that is, filtering is done by scanning the red channel of pixels in a row, then the blue channel of pixels in a row, and so on.
- 4. All channels in a row use the same filter
3.4 Compression
The PNG compression process combines LZ77 coding and Huffman coding. The main points are as follows:
- 1, the compression process is lossless compression
- 2, the more single the color, the smaller the color difference, the greater the compression rate
LZ77 coding
A dictionary-based, “sliding window” lossless compression algorithm.
Huffman coding (Huffman coding)
A variable length code used for lossless compression, the main idea is: to evaluate the probability of the occurrence of symbols to choose different length of the code, the high probability of the symbol to use a short code, and the low probability of the symbol to use a long code, which will reduce the average length of the code.
3.5 Chunking
Chunking makes it easy to decompose a compressed data stream into manageable chunks, the structure of which we discussed in Section 2.
4. Reduce the PNG file size
4.1 Reduce the number of colors & differences
In section 3 of the discussion of coding principles, we mentioned the concept of incremental coding, by reducing the number & difference of colors, the difference of data after the filtering step is smaller, which is beneficial to shrink the file during the compression step.
However, reducing the number & difference of colors is equivalent to lossy encoding of an image and should ensure the right balance between efficient compression and image quality.
4.2 Use index color format
If the number of monochrome images does not exceed 256, Indexed-colour format can be used. Each pixel of the original image is represented by an index in the palette. At this point, the number of bytes per pixel is reduced from 3 bytes (without transparent channels) and 4 bytes (with transparent channels) to 1 byte, greatly shrinking the file.
Citing the developer.android.com/topic/perfo… – the Android Developers
4.3 Vector Quantization
If the number of monochromatic images exceeds 256, it is necessary to use vector quantization to reduce the number of colors and regenerate into an indexed color format. Vector quantization is the rounding process of combining areas with similar colors into the same color, which is mainly divided into the following steps:
- 1. Grouping according to the similarity of similar areas;
- 2. Replace all the colors in the group with the colors of a single center point;
- 3, generate index color format.
Citing the developer.android.com/topic/perfo… – the Android Developers
5. PNG lossy compression scheme
In section 3, we mentioned that PNG compression is lossless compression. In order to further improve the compression rate, lossy compression algorithm can be adopted. The following are the existing PNG lossy compression schemes.
In the introduction of the official website, you can clearly understand their principle, mainly using the scheme discussed in section 4.3: using vector quantization to reduce the number of colors, regeneration into an indexed color format.
5.1 TinyPNG
Official address: tinypng.com
How does it work?
. By reducing the number of colors, 24-bit PNG files can be converted to much smaller 8-bit indexed color images. All unnecessary metadata is stripped too. The result better PNG files with 100% support for transparency. Have your cake and eat it too!
Limitations: Only HTTP requests are provided, and the number of requests is limited.
5.2 pngquant
Official address: pngquant.org
Features
High-quality palette generation using a combination of vector quantization algorithms. ……
5.3 zopflipng
5.4 pngcursh
Editting…
The resources
- PNG Entry — Wikipedia
- PNG format — GameRes.com
- Reduce image Download Size — Android Developers
- How PNG Works. By Colt McAnlis
- Optimizing Package Size – Part PNG by Leo The Striving
- Introduction to Mobile Image Compression (iOS & Android) by Nemocdz
- Protable Network Graphic (PNG) Specification (Second Edition) — w3.org
Recommended reading
- Algorithm | list problem summary
- | back algorithm framework to solve problems
- Cryptography | is Base64 encryption algorithm?
- Operating system | interruption & system call is analysed
- Data structure | weibo Top 10 hot search is how calculated? (Binary heap)
- Computer network | graphic DNS & HTTPDNS principle
- Android | so-accurately weighed various! Talk about the whole process of loading images
- Android | food tasteless! App Startup may be easier than you think
- Android | enough is enough! How does Glide arrange the life cycle clearly
