Geekly Articles each Day
📜 ⬆️ ⬇️

Image palette clustering and PNG compression

annotation


In this article, the reader is offered the experience of developing an image compression algorithm stored in PNG format. Compression is accomplished by quantizing the palette using the K – intragroup average classifier. The source code of the algorithm written in the Java language is given. Indicates problems and further ways to improve the algorithm.

Introduction


The PNG format (pronounced "ping") is intended for storing and transferring bitmaps. The format provides a phased display of image data, storing information about the gamma index, the transparency of each pixel, as well as textual information. The format uses an efficient lossless compression method [1].
A file (or data stream) in PNG format consists of an identification signature and at least three pieces of data. The PNG defines four standard chunks, called critical chunks, which must be supported by all read and write programs [1]:
  1. A portion of the header (IHDR).
  2. Palette Portion (PLTE) - stores color table data associated with image data. This portion is present in the file only when the image data uses a color palette (color indexation).
  3. A portion of image data (IDAT).
  4. The final portion (IEND).

More information about the description and features of the PNG format is given in [2]. It also describes the compression algorithms used by the format and indicates the application.
The main idea of ​​reducing the size of images stored in PNG format is to reduce the number of different colors represented in the image. In this case, the loss of the initial number of colors may be completely invisible to the human eye. According to the author, one of the most qualitative programs for today (02.2011) is the Color Quantizer (CQ) [3]. The main features of this program include:

As a test pattern for further research, we select an image from [4], presented in Figure 1 below. Note that Figure 1 does not contain the alpha channel and the chess background is only an imitation. The original image contains 43,500 unique colors. Using the CQ program, table 1 was compiled containing data on the number of colors left on the image and the size of the output file. When compressed in CQ, an error level of 25% was set.
Table 1 - Indicators of image compression using the CQ program
Number of colors, countSize, bytes on disk
43,500 (original)184 320
4096147 456
1024106,496
25653,248

As can be seen from the data in Table 1, reducing the number of colors to 256, the size of the resulting file is 53,248 bytes, which is almost 3.5 times smaller than the original file.

Test image
Figure 1 - Test image format PNG for research, resolution - 800x600

Compressed image using QE, 256 colors
Figure 2 - Compressed to 256 color image using the program Color Quantizer
')
Compressed image using the developed algorithm, 256 colors
Figure 3 - Compressed to 256 color image using the developed algorithm

Naturally, such a serious loss of color can not pass without a trace for the image, but in this case it is insignificant in the author’s opinion. Figure 2 shows a compressed image with up to 256 colors. Thus, you can significantly reduce the amount of PNG images by simply reducing the number of colors, which is especially important when using images on the web. However, it is not so easy to do this, the CQ program has a significant drawback - an extremely slow speed of work, which makes it difficult to use it in real time, for example, when transmitting data of geographic information systems. It turns out that the time it takes to compress an image is several times longer than the time required to transfer the original - uncompressed image.
In the next chapter, a very simple and fairly fast algorithm will be described, which allows in real time to reduce the number of colors in an image by quantizing (clustering) a palette (here we are not talking about PLTE portions) of an image.

Image Clustering Algorithm


An image palette is a variety of colors used in an image. If the image is stored in RGB format, then each point of this set has three coordinates - Red, Green, Blue; and if in the ARGB format, another, very important component is added - the alpha channel or transparency.
The palette can be represented by a set of points in three-dimensional for RGB or four-dimensional for ARGB spaces. Due to the presence of smooth transitions and halftone colors in the image, the dots will form “clouds” - the so-called clusters, where all the points of one cluster have a color close to each other. Therefore, for points that fall into one cluster, you can assign one averaged (one of the options) color, and thereby reduce the dimension of the set - the palette.
However, it is first necessary to determine the measure of proximity between colors. There are many options, all based on the construction of a space of colors which is visually evenly [5]. In this article, the author applies the most simple approach - a weighted Euclidean metric is selected. In this case, the distance between the colors in the ARGB format is determined by the formula
image
where x and y are the colors with the components {x A , x R , x G , x B }, {y A , y R , y G , y B } and α, β, γ, ε are parameters that may provide visual uniformity which are selected experimentally.
A number of data clustering algorithms have been developed [6], one of the simplest algorithms is K – intragroup averages, which is used if the number of clusters into which many objects are divided (in our case, many colors) is known. The algorithm can be represented by the following steps:

The author used the following stopping criterion for an iterative clustering algorithm: iterations stop if the number of objects that changed their cluster at the current step is equal to the number of the same objects at the previous step.
The implementation of this algorithm does not cause significant difficulties. The file attached to the article shows the source code of the algorithm. To work with the PNG image, the PNGEncoder module [7] is used.
Link to download archive with source text

An example of calling the function of reducing the number of colors


String imageFileName = "D:/Projects/PNG/big.png" ; String outImageFileName = "D:/Projects/PNG/bigout" ; int ColorCounts = 255; // PNG PngImage image = new PngImage(); BufferedImage bufImage = image.read( new File (imageFileName)); // CPNGCompression.Compression(bufImage, true , ColorCounts); // encoder.setColorType(encoder.COLOR_INDEXED_ALPHA); // encoder.setCompression(encoder.BEST_COMPRESSION); // PNG // ( PLTE) - 255 encoder.setIndexedColorMode(encoder.INDEXED_COLORS_AUTO); // FileOutputStream outfile = new FileOutputStream(outImageFileName + ".png" ); encoder.encode(bufImage, outfile); outfile.flush(); outfile.close(); * This source code was highlighted with Source Code Highlighter .
  1. String imageFileName = "D:/Projects/PNG/big.png" ; String outImageFileName = "D:/Projects/PNG/bigout" ; int ColorCounts = 255; // PNG PngImage image = new PngImage(); BufferedImage bufImage = image.read( new File (imageFileName)); // CPNGCompression.Compression(bufImage, true , ColorCounts); // encoder.setColorType(encoder.COLOR_INDEXED_ALPHA); // encoder.setCompression(encoder.BEST_COMPRESSION); // PNG // ( PLTE) - 255 encoder.setIndexedColorMode(encoder.INDEXED_COLORS_AUTO); // FileOutputStream outfile = new FileOutputStream(outImageFileName + ".png" ); encoder.encode(bufImage, outfile); outfile.flush(); outfile.close(); * This source code was highlighted with Source Code Highlighter .
  2. String imageFileName = "D:/Projects/PNG/big.png" ; String outImageFileName = "D:/Projects/PNG/bigout" ; int ColorCounts = 255; // PNG PngImage image = new PngImage(); BufferedImage bufImage = image.read( new File (imageFileName)); // CPNGCompression.Compression(bufImage, true , ColorCounts); // encoder.setColorType(encoder.COLOR_INDEXED_ALPHA); // encoder.setCompression(encoder.BEST_COMPRESSION); // PNG // ( PLTE) - 255 encoder.setIndexedColorMode(encoder.INDEXED_COLORS_AUTO); // FileOutputStream outfile = new FileOutputStream(outImageFileName + ".png" ); encoder.encode(bufImage, outfile); outfile.flush(); outfile.close(); * This source code was highlighted with Source Code Highlighter .
  3. String imageFileName = "D:/Projects/PNG/big.png" ; String outImageFileName = "D:/Projects/PNG/bigout" ; int ColorCounts = 255; // PNG PngImage image = new PngImage(); BufferedImage bufImage = image.read( new File (imageFileName)); // CPNGCompression.Compression(bufImage, true , ColorCounts); // encoder.setColorType(encoder.COLOR_INDEXED_ALPHA); // encoder.setCompression(encoder.BEST_COMPRESSION); // PNG // ( PLTE) - 255 encoder.setIndexedColorMode(encoder.INDEXED_COLORS_AUTO); // FileOutputStream outfile = new FileOutputStream(outImageFileName + ".png" ); encoder.encode(bufImage, outfile); outfile.flush(); outfile.close(); * This source code was highlighted with Source Code Highlighter .
  4. String imageFileName = "D:/Projects/PNG/big.png" ; String outImageFileName = "D:/Projects/PNG/bigout" ; int ColorCounts = 255; // PNG PngImage image = new PngImage(); BufferedImage bufImage = image.read( new File (imageFileName)); // CPNGCompression.Compression(bufImage, true , ColorCounts); // encoder.setColorType(encoder.COLOR_INDEXED_ALPHA); // encoder.setCompression(encoder.BEST_COMPRESSION); // PNG // ( PLTE) - 255 encoder.setIndexedColorMode(encoder.INDEXED_COLORS_AUTO); // FileOutputStream outfile = new FileOutputStream(outImageFileName + ".png" ); encoder.encode(bufImage, outfile); outfile.flush(); outfile.close(); * This source code was highlighted with Source Code Highlighter .
  5. String imageFileName = "D:/Projects/PNG/big.png" ; String outImageFileName = "D:/Projects/PNG/bigout" ; int ColorCounts = 255; // PNG PngImage image = new PngImage(); BufferedImage bufImage = image.read( new File (imageFileName)); // CPNGCompression.Compression(bufImage, true , ColorCounts); // encoder.setColorType(encoder.COLOR_INDEXED_ALPHA); // encoder.setCompression(encoder.BEST_COMPRESSION); // PNG // ( PLTE) - 255 encoder.setIndexedColorMode(encoder.INDEXED_COLORS_AUTO); // FileOutputStream outfile = new FileOutputStream(outImageFileName + ".png" ); encoder.encode(bufImage, outfile); outfile.flush(); outfile.close(); * This source code was highlighted with Source Code Highlighter .
  6. String imageFileName = "D:/Projects/PNG/big.png" ; String outImageFileName = "D:/Projects/PNG/bigout" ; int ColorCounts = 255; // PNG PngImage image = new PngImage(); BufferedImage bufImage = image.read( new File (imageFileName)); // CPNGCompression.Compression(bufImage, true , ColorCounts); // encoder.setColorType(encoder.COLOR_INDEXED_ALPHA); // encoder.setCompression(encoder.BEST_COMPRESSION); // PNG // ( PLTE) - 255 encoder.setIndexedColorMode(encoder.INDEXED_COLORS_AUTO); // FileOutputStream outfile = new FileOutputStream(outImageFileName + ".png" ); encoder.encode(bufImage, outfile); outfile.flush(); outfile.close(); * This source code was highlighted with Source Code Highlighter .
  7. String imageFileName = "D:/Projects/PNG/big.png" ; String outImageFileName = "D:/Projects/PNG/bigout" ; int ColorCounts = 255; // PNG PngImage image = new PngImage(); BufferedImage bufImage = image.read( new File (imageFileName)); // CPNGCompression.Compression(bufImage, true , ColorCounts); // encoder.setColorType(encoder.COLOR_INDEXED_ALPHA); // encoder.setCompression(encoder.BEST_COMPRESSION); // PNG // ( PLTE) - 255 encoder.setIndexedColorMode(encoder.INDEXED_COLORS_AUTO); // FileOutputStream outfile = new FileOutputStream(outImageFileName + ".png" ); encoder.encode(bufImage, outfile); outfile.flush(); outfile.close(); * This source code was highlighted with Source Code Highlighter .
  8. String imageFileName = "D:/Projects/PNG/big.png" ; String outImageFileName = "D:/Projects/PNG/bigout" ; int ColorCounts = 255; // PNG PngImage image = new PngImage(); BufferedImage bufImage = image.read( new File (imageFileName)); // CPNGCompression.Compression(bufImage, true , ColorCounts); // encoder.setColorType(encoder.COLOR_INDEXED_ALPHA); // encoder.setCompression(encoder.BEST_COMPRESSION); // PNG // ( PLTE) - 255 encoder.setIndexedColorMode(encoder.INDEXED_COLORS_AUTO); // FileOutputStream outfile = new FileOutputStream(outImageFileName + ".png" ); encoder.encode(bufImage, outfile); outfile.flush(); outfile.close(); * This source code was highlighted with Source Code Highlighter .
  9. String imageFileName = "D:/Projects/PNG/big.png" ; String outImageFileName = "D:/Projects/PNG/bigout" ; int ColorCounts = 255; // PNG PngImage image = new PngImage(); BufferedImage bufImage = image.read( new File (imageFileName)); // CPNGCompression.Compression(bufImage, true , ColorCounts); // encoder.setColorType(encoder.COLOR_INDEXED_ALPHA); // encoder.setCompression(encoder.BEST_COMPRESSION); // PNG // ( PLTE) - 255 encoder.setIndexedColorMode(encoder.INDEXED_COLORS_AUTO); // FileOutputStream outfile = new FileOutputStream(outImageFileName + ".png" ); encoder.encode(bufImage, outfile); outfile.flush(); outfile.close(); * This source code was highlighted with Source Code Highlighter .
  10. String imageFileName = "D:/Projects/PNG/big.png" ; String outImageFileName = "D:/Projects/PNG/bigout" ; int ColorCounts = 255; // PNG PngImage image = new PngImage(); BufferedImage bufImage = image.read( new File (imageFileName)); // CPNGCompression.Compression(bufImage, true , ColorCounts); // encoder.setColorType(encoder.COLOR_INDEXED_ALPHA); // encoder.setCompression(encoder.BEST_COMPRESSION); // PNG // ( PLTE) - 255 encoder.setIndexedColorMode(encoder.INDEXED_COLORS_AUTO); // FileOutputStream outfile = new FileOutputStream(outImageFileName + ".png" ); encoder.encode(bufImage, outfile); outfile.flush(); outfile.close(); * This source code was highlighted with Source Code Highlighter .
  11. String imageFileName = "D:/Projects/PNG/big.png" ; String outImageFileName = "D:/Projects/PNG/bigout" ; int ColorCounts = 255; // PNG PngImage image = new PngImage(); BufferedImage bufImage = image.read( new File (imageFileName)); // CPNGCompression.Compression(bufImage, true , ColorCounts); // encoder.setColorType(encoder.COLOR_INDEXED_ALPHA); // encoder.setCompression(encoder.BEST_COMPRESSION); // PNG // ( PLTE) - 255 encoder.setIndexedColorMode(encoder.INDEXED_COLORS_AUTO); // FileOutputStream outfile = new FileOutputStream(outImageFileName + ".png" ); encoder.encode(bufImage, outfile); outfile.flush(); outfile.close(); * This source code was highlighted with Source Code Highlighter .
  12. String imageFileName = "D:/Projects/PNG/big.png" ; String outImageFileName = "D:/Projects/PNG/bigout" ; int ColorCounts = 255; // PNG PngImage image = new PngImage(); BufferedImage bufImage = image.read( new File (imageFileName)); // CPNGCompression.Compression(bufImage, true , ColorCounts); // encoder.setColorType(encoder.COLOR_INDEXED_ALPHA); // encoder.setCompression(encoder.BEST_COMPRESSION); // PNG // ( PLTE) - 255 encoder.setIndexedColorMode(encoder.INDEXED_COLORS_AUTO); // FileOutputStream outfile = new FileOutputStream(outImageFileName + ".png" ); encoder.encode(bufImage, outfile); outfile.flush(); outfile.close(); * This source code was highlighted with Source Code Highlighter .
  13. String imageFileName = "D:/Projects/PNG/big.png" ; String outImageFileName = "D:/Projects/PNG/bigout" ; int ColorCounts = 255; // PNG PngImage image = new PngImage(); BufferedImage bufImage = image.read( new File (imageFileName)); // CPNGCompression.Compression(bufImage, true , ColorCounts); // encoder.setColorType(encoder.COLOR_INDEXED_ALPHA); // encoder.setCompression(encoder.BEST_COMPRESSION); // PNG // ( PLTE) - 255 encoder.setIndexedColorMode(encoder.INDEXED_COLORS_AUTO); // FileOutputStream outfile = new FileOutputStream(outImageFileName + ".png" ); encoder.encode(bufImage, outfile); outfile.flush(); outfile.close(); * This source code was highlighted with Source Code Highlighter .
  14. String imageFileName = "D:/Projects/PNG/big.png" ; String outImageFileName = "D:/Projects/PNG/bigout" ; int ColorCounts = 255; // PNG PngImage image = new PngImage(); BufferedImage bufImage = image.read( new File (imageFileName)); // CPNGCompression.Compression(bufImage, true , ColorCounts); // encoder.setColorType(encoder.COLOR_INDEXED_ALPHA); // encoder.setCompression(encoder.BEST_COMPRESSION); // PNG // ( PLTE) - 255 encoder.setIndexedColorMode(encoder.INDEXED_COLORS_AUTO); // FileOutputStream outfile = new FileOutputStream(outImageFileName + ".png" ); encoder.encode(bufImage, outfile); outfile.flush(); outfile.close(); * This source code was highlighted with Source Code Highlighter .
  15. String imageFileName = "D:/Projects/PNG/big.png" ; String outImageFileName = "D:/Projects/PNG/bigout" ; int ColorCounts = 255; // PNG PngImage image = new PngImage(); BufferedImage bufImage = image.read( new File (imageFileName)); // CPNGCompression.Compression(bufImage, true , ColorCounts); // encoder.setColorType(encoder.COLOR_INDEXED_ALPHA); // encoder.setCompression(encoder.BEST_COMPRESSION); // PNG // ( PLTE) - 255 encoder.setIndexedColorMode(encoder.INDEXED_COLORS_AUTO); // FileOutputStream outfile = new FileOutputStream(outImageFileName + ".png" ); encoder.encode(bufImage, outfile); outfile.flush(); outfile.close(); * This source code was highlighted with Source Code Highlighter .
  16. String imageFileName = "D:/Projects/PNG/big.png" ; String outImageFileName = "D:/Projects/PNG/bigout" ; int ColorCounts = 255; // PNG PngImage image = new PngImage(); BufferedImage bufImage = image.read( new File (imageFileName)); // CPNGCompression.Compression(bufImage, true , ColorCounts); // encoder.setColorType(encoder.COLOR_INDEXED_ALPHA); // encoder.setCompression(encoder.BEST_COMPRESSION); // PNG // ( PLTE) - 255 encoder.setIndexedColorMode(encoder.INDEXED_COLORS_AUTO); // FileOutputStream outfile = new FileOutputStream(outImageFileName + ".png" ); encoder.encode(bufImage, outfile); outfile.flush(); outfile.close(); * This source code was highlighted with Source Code Highlighter .
  17. String imageFileName = "D:/Projects/PNG/big.png" ; String outImageFileName = "D:/Projects/PNG/bigout" ; int ColorCounts = 255; // PNG PngImage image = new PngImage(); BufferedImage bufImage = image.read( new File (imageFileName)); // CPNGCompression.Compression(bufImage, true , ColorCounts); // encoder.setColorType(encoder.COLOR_INDEXED_ALPHA); // encoder.setCompression(encoder.BEST_COMPRESSION); // PNG // ( PLTE) - 255 encoder.setIndexedColorMode(encoder.INDEXED_COLORS_AUTO); // FileOutputStream outfile = new FileOutputStream(outImageFileName + ".png" ); encoder.encode(bufImage, outfile); outfile.flush(); outfile.close(); * This source code was highlighted with Source Code Highlighter .
  18. String imageFileName = "D:/Projects/PNG/big.png" ; String outImageFileName = "D:/Projects/PNG/bigout" ; int ColorCounts = 255; // PNG PngImage image = new PngImage(); BufferedImage bufImage = image.read( new File (imageFileName)); // CPNGCompression.Compression(bufImage, true , ColorCounts); // encoder.setColorType(encoder.COLOR_INDEXED_ALPHA); // encoder.setCompression(encoder.BEST_COMPRESSION); // PNG // ( PLTE) - 255 encoder.setIndexedColorMode(encoder.INDEXED_COLORS_AUTO); // FileOutputStream outfile = new FileOutputStream(outImageFileName + ".png" ); encoder.encode(bufImage, outfile); outfile.flush(); outfile.close(); * This source code was highlighted with Source Code Highlighter .
String imageFileName = "D:/Projects/PNG/big.png" ; String outImageFileName = "D:/Projects/PNG/bigout" ; int ColorCounts = 255; // PNG PngImage image = new PngImage(); BufferedImage bufImage = image.read( new File (imageFileName)); // CPNGCompression.Compression(bufImage, true , ColorCounts); // encoder.setColorType(encoder.COLOR_INDEXED_ALPHA); // encoder.setCompression(encoder.BEST_COMPRESSION); // PNG // ( PLTE) - 255 encoder.setIndexedColorMode(encoder.INDEXED_COLORS_AUTO); // FileOutputStream outfile = new FileOutputStream(outImageFileName + ".png" ); encoder.encode(bufImage, outfile); outfile.flush(); outfile.close(); * This source code was highlighted with Source Code Highlighter .
String imageFileName = "D:/Projects/PNG/big.png" ; String outImageFileName = "D:/Projects/PNG/bigout" ; int ColorCounts = 255; // PNG PngImage image = new PngImage(); BufferedImage bufImage = image.read( new File (imageFileName)); // CPNGCompression.Compression(bufImage, true , ColorCounts); // encoder.setColorType(encoder.COLOR_INDEXED_ALPHA); // encoder.setCompression(encoder.BEST_COMPRESSION); // PNG // ( PLTE) - 255 encoder.setIndexedColorMode(encoder.INDEXED_COLORS_AUTO); // FileOutputStream outfile = new FileOutputStream(outImageFileName + ".png" ); encoder.encode(bufImage, outfile); outfile.flush(); outfile.close(); * This source code was highlighted with Source Code Highlighter .

Function signature
public static void Compression ( BufferedImage aImage, // boolean aUseFixedColorList, // int aColorCount // ) * This source code was highlighted with Source Code Highlighter .
  1. public static void Compression ( BufferedImage aImage, // boolean aUseFixedColorList, // int aColorCount // ) * This source code was highlighted with Source Code Highlighter .
  2. public static void Compression ( BufferedImage aImage, // boolean aUseFixedColorList, // int aColorCount // ) * This source code was highlighted with Source Code Highlighter .
  3. public static void Compression ( BufferedImage aImage, // boolean aUseFixedColorList, // int aColorCount // ) * This source code was highlighted with Source Code Highlighter .
  4. public static void Compression ( BufferedImage aImage, // boolean aUseFixedColorList, // int aColorCount // ) * This source code was highlighted with Source Code Highlighter .
  5. public static void Compression ( BufferedImage aImage, // boolean aUseFixedColorList, // int aColorCount // ) * This source code was highlighted with Source Code Highlighter .
  6. public static void Compression ( BufferedImage aImage, // boolean aUseFixedColorList, // int aColorCount // ) * This source code was highlighted with Source Code Highlighter .
public static void Compression ( BufferedImage aImage, // boolean aUseFixedColorList, // int aColorCount // ) * This source code was highlighted with Source Code Highlighter .
public static void Compression ( BufferedImage aImage, // boolean aUseFixedColorList, // int aColorCount // ) * This source code was highlighted with Source Code Highlighter .

The Compression function is static for the CPNGCompression class. If the aUseFixedColorList parameter is set to true, then some colors in the image become “untouchable” —the list of such colors is configured in the static array of the CPNGCompression class. Untouchable colors are introduced so that, for example, there is no mixing (when calculating the center of the cluster) of white and black with the formation of gray.
It is logical to assume that the visual quality of the classification strongly depends on the coefficients in formula (1), which can be defined for a limited class of images, for example, the following values ​​are selected for special cartographic data: α = 100, β = 30, γ = 59, ε = 11
Figure 3 shows the result of compressing up to 256 colors of the original image using the developed algorithm. The total opening, compression and storage times were 4,700 ms . The size of the output file is 53,248 bytes , as well as for the CQ program (Table 1). As we can see, figure 3 compared to figure 2, has a changed background color - visually it became closer to yellow than to gray . This defect is easily eliminated if you specify white and gray as the “untouchables”, which constitute the background.

Conclusion


The article describes one of the simplest clustering algorithms used in the task of reducing the number of colors in an image. The algorithm is compared with the known solution - the CQ program. Further improvements to the algorithm may be associated with


Additions to the article - based on comments


The main article does not provide an image compressed by this algorithm using “untouchable colors”. Set up untouchable colors as follows:
// CPNGCompression.m_fixedColors = new int [2]; CPNGCompression.m_fixedColors[0] = 0xFF969696; CPNGCompression.m_fixedColors[1] = 0xFFFFFFFF; // CPNGCompression.Compression(bufImage, true , 256); * This source code was highlighted with Source Code Highlighter .
  1. // CPNGCompression.m_fixedColors = new int [2]; CPNGCompression.m_fixedColors[0] = 0xFF969696; CPNGCompression.m_fixedColors[1] = 0xFFFFFFFF; // CPNGCompression.Compression(bufImage, true , 256); * This source code was highlighted with Source Code Highlighter .
  2. // CPNGCompression.m_fixedColors = new int [2]; CPNGCompression.m_fixedColors[0] = 0xFF969696; CPNGCompression.m_fixedColors[1] = 0xFFFFFFFF; // CPNGCompression.Compression(bufImage, true , 256); * This source code was highlighted with Source Code Highlighter .
  3. // CPNGCompression.m_fixedColors = new int [2]; CPNGCompression.m_fixedColors[0] = 0xFF969696; CPNGCompression.m_fixedColors[1] = 0xFFFFFFFF; // CPNGCompression.Compression(bufImage, true , 256); * This source code was highlighted with Source Code Highlighter .
  4. // CPNGCompression.m_fixedColors = new int [2]; CPNGCompression.m_fixedColors[0] = 0xFF969696; CPNGCompression.m_fixedColors[1] = 0xFFFFFFFF; // CPNGCompression.Compression(bufImage, true , 256); * This source code was highlighted with Source Code Highlighter .
  5. // CPNGCompression.m_fixedColors = new int [2]; CPNGCompression.m_fixedColors[0] = 0xFF969696; CPNGCompression.m_fixedColors[1] = 0xFFFFFFFF; // CPNGCompression.Compression(bufImage, true , 256); * This source code was highlighted with Source Code Highlighter .
  6. // CPNGCompression.m_fixedColors = new int [2]; CPNGCompression.m_fixedColors[0] = 0xFF969696; CPNGCompression.m_fixedColors[1] = 0xFFFFFFFF; // CPNGCompression.Compression(bufImage, true , 256); * This source code was highlighted with Source Code Highlighter .
// CPNGCompression.m_fixedColors = new int [2]; CPNGCompression.m_fixedColors[0] = 0xFF969696; CPNGCompression.m_fixedColors[1] = 0xFFFFFFFF; // CPNGCompression.Compression(bufImage, true , 256); * This source code was highlighted with Source Code Highlighter .
// CPNGCompression.m_fixedColors = new int [2]; CPNGCompression.m_fixedColors[0] = 0xFF969696; CPNGCompression.m_fixedColors[1] = 0xFFFFFFFF; // CPNGCompression.Compression(bufImage, true , 256); * This source code was highlighted with Source Code Highlighter .

Then the compression result of the algorithm considered here is the image:
image
Figure 4 - Compressed image using two untouchable colors

The size of this picture is also 53,243 bytes on the disk.

I do not know how to make a comparison of the running time of the CQ program with the required accuracy.
Using the system clock, with an accuracy of + -2 seconds, CQ compresses up to 256 colors in 34 seconds , which is an order of magnitude worse than the result of the proposed algorithm.

Sources used


  1. D. Murray, W. Van Riper. Encyclopedia of graphic file formats.
  2. Greg Roelofs, Ivan Zenkov, Dimok Busheff. PNG: A simple introduction to the features of the format / Link
  3. Color Quantizer: A program that allows you to easily optimize images for the web / Link
  4. Wikipedia, test image, GNU Free Documentation License / Link
  5. A.I. Kulikov, T.E. Ovchinnikov. Space CIE Luv, Algorithmic Foundations of Modern Computer Graphics / Reference
  6. Overview of data clustering algorithms / Link
  7. Package PNGEncoder for working with images in PNG, Java / Link

Source: https://habr.com/ru/post/113393/

More articles:


All Articles