Variance-Based Color Quantization

Converting an image into a smaller file and remodeling its color space with fewer representative colors are not the same operation. In the first case, the encoder's ability to compress the bitstream is central. In the second, the problem is how millions of possible colors can be reduced to a limited palette with controlled loss. The library I examined combines these two problems in one pipeline. It first performs statistical quantization in RGBA color space, then re-encodes the resulting indexed image and tests whether the file size has decreased.

I developed this library before generative AI-assisted coding tools became widespread, after studying established approaches to image quantization and palette optimization. Its theoretical background follows the same technical line as the chapter titled "Image and Audio Processing," which I wrote for the book Artificial Intelligence from Theory to Practice, published by Nobel Academic Publishing. In that chapter, I built a structure extending from the numerical representation of images and feature vectors to enhancement, segmentation, and AI-based image analysis. This library is a low-level and measurable example of the transition from theory to practice discussed there.

There is no neural network at the core of the code. The operation is nevertheless meaningful from the perspective of artificial intelligence and pattern recognition. Each pixel is treated as a four-dimensional feature vector, the observed color distribution is divided into clusters, and each cluster is represented by a central color. This is a classical statistical-learning and vector-quantization approach. Because the algorithm is explainable, each decision can be traced through moments, variance, and distance.

The color-quantization problem

A 32-bit RGBA image carries four 8-bit components per pixel:

• Alpha
• Red
• Green
• Blue

The theoretical color space permits approximately 4.29 billion different RGBA combinations. In an indexed image, however, a pixel carries the number of a palette entry rather than a direct color value. PNG supports 1-, 2-, 4-, and 8-bit indices for indexed images. An image can therefore be represented by at most 2, 4, 16, or 256 palette colors. The implementation under examination uses 1-, 4-, and 8-bit output formats.

A quantization function can generally be represented as:

[ Q: \mathbb{R}^{4} \rightarrow {c_0,c_1,\ldots,c_{K-1}} ]

Each pixel is mapped to the most suitable representative color in RGBA space. The objective is to balance the palette size K against reconstruction error.

A simple approach can reduce the number of colors by discarding the lower bits of each channel. This method is fast, but it ignores the actual color distribution of the image. Median cut divides boxes in color space according to population or axis length. K-means assigns pixels to centers and updates the centers iteratively. The main structure of the examined code, however, closely matches Xiaolin Wu's color-quantization approach based on variance reduction.

Wu's method treats an RGB image as a three-dimensional density distribution. It divides color space into axis-aligned boxes and selects cuts that reduce within-cluster variance. Its main advantage is that it precomputes statistics for color regions and can therefore evaluate possible cuts efficiently.

The implementation I developed does not leave this idea in three-dimensional RGB space. It includes the alpha channel as an independent dimension. Boxes are thus defined on four axes:

[ C=[A_0,A_1]\times[R_0,R_1]\times[G_0,G_1]\times[B_0,B_1] ]

This extension can prevent semitransparent pixels from being placed in the same cluster based only on their RGB components. In return, it substantially increases the memory cost of the moment space.

Five-bit histogram and color moments

Constructing a four-dimensional histogram directly over the full RGBA space is impractical. Because each channel has 256 possible values, the number of cells would be:

[ 256^4 ]

The source code shifts each channel three bits to the right, reducing it from 8 bits to 5 bits. Each axis is thereby divided into 32 effective bins. With an additional zero layer that simplifies boundary calculations, each dimension has length 33:

[ B=33 ]

The total number of four-dimensional cells is reduced to:

[ 33^4=1,185,921 ]

This is still a large number, but it is fixed and manageable on current desktop systems.

Each histogram cell stores more than a pixel count. The following sufficient statistics are accumulated:

[ w=\sum 1 ]

[ s_A=\sum A,\quad s_R=\sum R,\quad s_G=\sum G,\quad s_B=\sum B ]

[ q=\sum(A^2+R^2+G^2+B^2) ]

Here, w is the pixel weight in the cell, the s values are channel sums, and q is the second moment.

The mean color of a specified color box is:

[ \mu_C= \left( \frac{s_A}{w}, \frac{s_R}{w}, \frac{s_G}{w}, \frac{s_B}{w} \right) ]

The total squared error, or variance measure, of the same box corresponds to the following relation in the source code:

[ V(C)=q-\frac{s_A^2+s_R^2+s_G^2+s_B^2}{w} ]

This expression is the sum of squared distances between the pixels in the box and their mean color. A box with high variance produces more error when represented by a single palette color. Selecting high-variance boxes for subsequent splitting is therefore meaningful.

An additional threshold is applied for partial transparency. Pixels with very low alpha are excluded from the histogram, and a separate index is reserved for transparent color. The additional correction used for intermediate alpha values is a compression heuristic. Its modulo-based mapping is not monotonic, however. Two close alpha values can fall into distant histogram cells around transition points. In a production version, alpha quantization with a monotonic transfer function would provide more stable results.

Four-dimensional integral histogram

The algorithmic strength of the method lies in calculating four-dimensional cumulative moments after the histogram has been constructed. It can be viewed as an application of the integral-image approach from image processing to color space.

Each cell stores the sum of all alpha, red, green, and blue cells preceding it. After this precomputation, the moments of any four-dimensional rectangular region can be obtained without traversing every cell inside that region.

The volume of a four-dimensional box is calculated with 16 corner values using the inclusion-exclusion principle. When the number of dimensions is D, the number of required corners is:

[ 2^D ]

Sixteen fixed accesses are therefore sufficient in four dimensions.

This choice moves the expensive calculation into the one-time moment-construction stage. For hundreds of subsequent cut candidates, box weight, channel sums, and the second moment can be obtained in constant time.

When N denotes the number of pixels, histogram construction costs:

[ \Theta(N) ]

The cumulative moment table costs:

[ \Theta(B^4) ]

Because B=33 is fixed, this cost is independent of image resolution. Pixel traversal dominates for large images. For very small images, preparing the fixed moment table can be relatively expensive.

The raw moment structure is approximately 40 bytes. The moment data alone in the four-dimensional table occupies approximately 45.2 MiB according to:

[ 1,185,921\times40 ]

This excludes the bitmap, stream, and row buffers. Compared with a three-dimensional Wu histogram, adding the alpha dimension increases the number of cells by a factor of 33. This is a deliberate memory tradeoff made before quality is evaluated.

Variance-guided box splitting

Initially, a single box covers the entire color space. At each step, one of the boxes is divided into two. All four axes are evaluated separately as possible cut dimensions.

Assume a cut divides a box into C_1 and C_2. The code attempts to maximize:

[ J= \frac{|s_1|^2}{w_1} + \frac{|s_2|^2}{w_2} ]

Because the total second moment is fixed, maximizing this expression is equivalent to minimizing the combined within-cluster variance of the two subboxes:

[ V(C_1)+V(C_2) ]

The best cuts found along the alpha, red, green, and blue axes are compared. The axis and position that provide the greatest gain are selected. After the split, the variances of the two new boxes are recalculated.

At the next step, the box with the highest variance among the existing boxes is split rather than an arbitrary box. This greedy strategy concentrates palette colors according to the image's color distribution. Flat-color regions are represented by fewer boxes, while gradients or textured regions receive more boxes.

The process continues until the requested palette size is reached or no box can be divided further. Because the implementation reserves an entry for transparent pixels, the number of visible colors is kept below the practical limit of 256.

The mean RGBA values of the boxes form the initial palette centers. This completes the statistical stage of the Wu quantizer.

Nearest-color search

After the palette has been created, each image pixel must be converted into a palette index. The source code uses squared Euclidean distance in RGBA space:

[ d(p,c)= (A_p-A_c)^2+ (R_p-R_c)^2+ (G_p-G_c)^2+ (B_p-B_c)^2 ]

The center with the smallest distance becomes the pixel's palette color.

Comparing every pixel against every palette color has worst-case cost:

[ \Theta(NK) ]

When K approaches 255, this stage can become more expensive than histogram calculation.

To reduce this cost, I developed a data-dependent masking and bucket structure in the library. Bit masks for alpha, red, green, and blue are created according to the distribution of unique values in the palette channels. Palette colors carrying the same masked key are placed in one bucket. An incoming pixel is first searched in its own bucket. If no bucket exists, the entire palette is scanned and the result is cached for the same key.

This method is not a classical spatial index. It is a lightweight approximate-search layer that divides color space into coarse cells according to the data distribution. With a small palette, it can have lower fixed cost than a tree-based structure.

Searching only the colors in a populated bucket does not guarantee the global nearest neighbor, however. The nearest palette color may lie in an adjacent masked region. There is therefore a tradeoff between speed and exact nearest-color accuracy.

After assignment with the initial box centers, the code recalculates the channel means of the actual pixels assigned to each palette entry. This can be viewed as one centroid-update step. Assignment and center update are not repeated until convergence as in a complete k-means algorithm. Even so, this correction after the Wu centers moves the palette toward the actual assignment clusters.

Studies of k-means-based color quantization likewise show that good initial centers and efficient nearest-neighbor search determine both quality and execution time. The examined structure uses a similar center-correction idea without implementing full k-means.

Bit-level packing of indices

After the color count is determined, the target pixel format is selected:

• 1-bit output for one color region
• 4-bit output for 2 to 16 colors
• 8-bit output for more colors

In the one-bit format, eight pixels are packed into one byte. In the four-bit format, two pixels are written into the upper and lower halves of one byte. In the eight-bit format, each pixel carries a one-byte palette index.

High-level calls such as SetPixel are not used in this section. Rows are locked directly and packed indices are copied into bitmap memory. This removes the cost of a managed method call for each pixel.

The PNG standard states that pixel values in indexed color are palette indices, that palette length cannot exceed the limit permitted by bit depth, and that alpha information can be associated with palette entries. Alpha values in PNG are not premultiplied.

The transparency approach in the source code directs low-alpha values to a separate palette entry and later marks a specified color as transparent. This is a practical solution that can work for icon-like images. It is more fragile than managing a real alpha palette, however. It must also be verified that visible pixels with the same RGB value as the transparency key are not affected inadvertently.

Iterative optimization by file size

The library does not accept the first quantized output as the final result. It opens the encoded image again, requantizes it, and compares the new file size with the previous result. Processing stops if the new result is larger. If it is smaller or equal, the new output is retained.

This is a greedy size optimization that accepts results satisfying:

[ L_{i+1}\leq L_i ]

A fixed number of iterations is used as an upper bound.

This design is notable because it includes the real file encoder in the optimization loop. It does not consider only raw pixel count or palette size. Palette order, color repetition, filtering, and the compressed bitstream are all reflected in final file size.

The objective function is only byte length, however. Visual error is not measured. Each requantization uses the previous quantized result rather than the original image, so loss can accumulate. The file can become smaller while banding, damaged edge colors, or halos in semitransparent regions increase.

A stronger optimization would evaluate both of the following conditions:

[ \min L ]

[ D(I,\hat I)\leq D_{\max} ]

Here, L is file size and D is distortion between the original and resulting image. PSNR or structural-similarity measures can be used. For palette quantization, however, a color-difference and alpha-compositing measure more consistent with human perception would be more meaningful.

Algorithmic complexity

For one quantization pass, let:

• N be the number of pixels
• B be the histogram-axis length, here 33
• K be the number of palette colors
• I be the number of outer optimization iterations

Histogram construction:

[ \Theta(N) ]

Cumulative moment calculation:

[ \Theta(B^4) ]

Searching cuts across four axes for each box:

[ O(KB) ]

Selecting the highest-variance box by a linear scan after each split:

[ O(K^2) ]

Pixel-to-palette mapping, although lower on average depending on masking success, has worst-case cost:

[ O(NK) ]

The overall upper bound can therefore be expressed approximately as:

[ O\left( I\left[ N+B^4+KB+K^2+NK \right] \right) ]

In real images, bucket-based search can substantially reduce the NK term. The four-dimensional moment table uses approximately 45 MiB of fixed space independent of image size. Bitmap and stream copies add an O(N) component to total memory consumption.

The algorithm can provide a strong quality-to-size balance for small icons and web images. For very large images, repeated decoding, bitmap copies, and the four-dimensional moment table must be considered.

Limitations found in the source review

The general algorithmic structure of the code is consistent. The examined version nevertheless contains several boundary conditions that should be corrected before production use.

During construction of the palette-search mask, the highest alpha-channel value appears to be used instead of the highest blue-channel value. This can position the blue-channel mask incorrectly. When channel distributions differ, bucket quality may be reduced.

When the color count is exactly 16, the extra entry reserved for transparency can conflict with the 16-entry capacity of a four-bit palette. Palette capacity, visible color count, and the reserved transparent entry should be managed as separate variables.

The general exception-catching behavior in transparency detection converts a pixel-reading error into a "no transparency" result. This avoids interrupting processing but can hide the real error. Recording the error type or propagating it to the caller would be more reliable.

Overlaying the byte channels of a pixel structure with a 32-bit integer in the same memory is fast. Channel order, however, depends on processor byte order and the graphics infrastructure in use. The layout is predictable in the Windows and GDI+ environment for which the code was developed. Byte order must be tested explicitly when moving to another platform.

The library was historically developed on System.Drawing and GDI+. In current .NET versions, System.Drawing.Common is considered Windows-specific. In a new cross-platform version, the pixel-processing core should remain platform-independent, with only the decoder and encoder layers replaced.

Meaning for artificial intelligence and image processing

It would be incomplete to regard this library only as a PNG size-reduction tool. From the perspective of artificial intelligence and image processing, the pipeline combines four fundamental concepts:

1. Constructing a feature space
2. Extracting sufficient statistics
3. Variance-based clustering
4. Prototype representation and nearest-sample mapping

Each pixel is a four-component vector. The histogram is the empirical distribution of the image. Boxes represent clusters, and palette colors represent prototypes. The quantized image is a reconstruction of the original data with a limited number of prototypes.

This approach is consistent with the central idea I discussed in the "Image and Audio Processing" chapter of Artificial Intelligence from Theory to Practice. The connection between image processing and artificial intelligence is not established only through deep neural networks. Representing data in an appropriate feature space, modeling its distribution, and reducing representation cost are also foundations of the same discipline. The chapter's treatment of image acquisition, feature vectors, enhancement, and AI-based analysis provides the theoretical framework for this relationship.

The distinctive engineering aspects of my implementation are that it extends a known variance-quantization approach with an alpha dimension rather than copying it directly, adds a data-dependent pre-index to palette search, recalculates centers after assignment, and uses the size of the actually encoded file as an iterative stopping criterion.

The code also clearly demonstrates the fundamental tradeoffs common in classical algorithms. Memory is allocated for faster regional statistics. Approximate search is accepted for faster color mapping. Requantization is performed for a smaller file. A fourth dimension is added to color space to support transparency.

A good image-optimization algorithm does more than reduce file size. It can explain which information it preserves, which information it loses, and at what cost it reduces that loss. This is the main technical value of the library. Instead of leaving palette generation to opaque encoder behavior, it constructs moments, variance, box splitting, and center assignment as an explicit algorithm.

References

Köker, M. A. "Image and Audio Processing." Artificial Intelligence from Theory to Practice. Nobel Academic Publishing, 2022. ISBN 978-625-427-802-0.

Wu, X. "Efficient Statistical Computations for Optimal Color Quantization." Graphics Gems II, pp. 126-133, 1991. DOI: 10.1016/B978-0-08-050754-5.50035-9.

Celebi, M. E. "Improving the Performance of K-Means for Color Quantization." 2011.

World Wide Web Consortium. Portable Network Graphics Specification, Third Edition. 2025.