Trigrad

Triangle Gradient Image Compression

What is Trigrad?

Trigrad is a (mostly[1]) novel image compression algorithm that uses a delaunay triangle mesh and barycentric interpolation to compress. This differs heavily from other compression techniques such as JPEG, which typically use wavelet functions as the basis for their compression.

How well does it work?

Not really well enough to try to push onto people. Current results show that Trigrad can only beat something like JPEG with optimal conditions.

How does it look?

One of the best tests of a compression algorithm is how its artifacts look. Here's a comparison of a mostly uncompressed image and one compressed with Trigrad, using just 15,000 samples.

(Left: Uncompressed. Right: Compressed.)

Of course, with a higher number of samples, a better quality output can be produced. The same image with 25,000 samples starts to look a lot more accurate.

How does it work?

This is where Trigrad gets interesting. Throughout development, I've made sure to produce as many visualizations as I can for the purposes of debugging. This will allow me to explain the process of compression and decompression visually.

Sampling

Sampling is done through a frequency table that is calculated directly off of the sobel edge detection results of the input image. The frequency table ensures a higher rate of sampling at areas of high areas of change.

The effect of changing the sample count. From 1 to 80,000.

The above image, and the one that we will be looking at throughout this post, has had 50,000 samples chosen. This nets an average error of roughly 2.07

Further progress

A delaunay mesh is formed from the selected samples. This is achieved using the awesome Triangle.NET port of the equally awesome Triangle library.

By this point, the mesh could be filled using each pixels Barycentric coordinates. However, in order to achieve optimal results, this mesh is going to have to be tweaked.

Error Optimisation

At first, the end results of this algorithm were rough. Large sample counts were required to produce high quality output, with the delaunay triangulation not conforming to the original data. However, with some simple error minimisation techniques, even a small sample count can yield great results.

The concept of Trigrad's error minimisation is simple. Each vertex of the delaunay mesh is moved to a number of possible points within the surrounding triangle. At each point, the triangles are filled and the error recorded. The point that results in the minimal error is chosen and then the next vertex is tested.

One iteration of error minimation in action.

Compression

Once the mesh has been built, it can be saved and zipped up. Our 50,000 sample count mesh can be saved into a file just 600KB in size! This is nice, considering the simplicity of the algorithm.

Other Fill Modes

Whilst the barycentric gradient fill mode is obvious and the most precise, there are a number of other interesting modes that can be explored.

This is after being filled using a solid single colour 'trigrader' algorithm. Polygonal!

This is after being filled using an extended dithering algorithm. Kind of like sponge painting.

Try Trigrad

Trigrad's source is available online on GitHub.

Triart (Experimental)

If you'd just like to experiment with the various parameters available, an experimental UI is available. This UI does not have compression or decompression support, but it does use the algorithm described above, allowing you to produce unique and impressive results.

Download

Further Reading

After posting Trigrad v1 to Hacker News, I was alerted to a number of related papers:

Fast Polygonal Approximation of Terrains and Height Fields A similar technique applied to grayscale heightmaps.
Visual representation by triangulation A similar technique using more comprehensive analysis techniques.

Author

Trigrad was created over a number of holiday weeks. You can check out more work like this on my website.

Prior Work (Trigrad v1)

The original publication and it's accompanying Hacker News discussion.

Notes

[1] See further reading.