PNGPart is an image partitioning algorithm. Combined with oxipng it can compress PNGs down to 68% of their original (oxipng optimized) size with almost no visible quality loss.

This repo is a Rust implementation of the algorithm and a basic CLI tool that also incorporates oxipng for optimal PNG encoding.

NOTE: this is just a toy image compression scheme. It can commpresse images but other lossy compression method are better (JPEG, WebP, pngquant, ...)

High tolerance (74Kb)	Medium tolerance (279Kb)	Low tolerance (420Kb)

_{Original image: 540Kb}

The algorithm iteratively divides the image into axis-aligned regions. Each region is colored with its average color. In every iteration, the region with the most variance in color is divided in the middle of the axis that minimises both subsections' variance.

The algorithm can be stopped at any time, and more iteration equals better quality but reduces compression rate. Instead of using a fixed iteration count, the tolerance is used instead as the stopping criteria. This means that the algorithm will stop when the maximum variance falls below a certain threshold.

Original (500Kb)	Compressed (424Kb)

• Command line tool for compressing PNG
• Preserves alpha channel
• Further reduce file size with oxipng

Other non-compression capabilities of this algorithm, currently only for demonstration and not implementated in this repository.

• Image detail heatmap (based on how many time a pixel is divided)

Image	Heatmap (brighter = more detailed)

• Image stylization (by rendering other shapes instead of AABB)

Original	Stylized with ellipses

• Add way to control quality from the command line arguments
• Make a web interface
• SVG output with shape other than AABB
• Bulk processing multiple images
• Experiments with other region rendering methods
• Experiments with other splitting methods

PNGPart can be built from source using Rust.

git clone https://github.com/ziap/pngpart
cd pngpart

cargo build --release

# Usage
target/release/pngpart <input file> <output file>

A benchmark is performed on the validation set of the DIV2K dataset.

The algorithm is compared with another lossy PNG compressor, namely pngquant. For a fairer comparison, oxipng is run on the output of both algorithms and also on the original image. Both algorithms are run on their default settings.

This shows that while PNGPart has a worse compression ratio, the image quality is slightly better based on many common image comparison metrics. Note that these metrics don't really reflect the perceptual image quality, and the output of pngquant is also almost indistinguishable from the original image.

Further experiments:

• Test on graphical images (digital illustration, textures, cartoon, SVG converted to PNG, ...)
• Test with same SSIM or same file size
• Graph BPP (bit per pixel) vs quality

This project is licensed under the MIT Licence.