Fractal image compression

Fractal image compression is an exciting application of fractal theory, particularly in image compression

Description

With this application, you can:

  • Compress images with this fractal method
  • Decompress previously compressed images into a different format

Make use of the platform's libraries, which include the following features:

  • Multi-language
  • Configurable multi-resolution zoom
  • Dark mode option
  • New version notification


Pros:

  • When properly programmed, it functions independently of the image resolution
  • It is a distinctive compression method
  • Allows you to learn as you go


Cons:

  • The compression process is extremely slow
  • You don't achieve very high compression ratios (at least with the parameters I used)

Code description

It's an implementation of this fractal image compression algorithm published in IEEE during my college days

The application utilizes the Delaunay incremental triangulation library, which is also used in the Morphing application


High-level algorithm:

  • Compression:
    • Fractal compression focuses on storing relationships between image regions rather than the actual pixel values, specifically between triangles in this case.
    • The image is divided into a triangular grid consisting of multiple triangles, forming a triangulated domain.
    • The image is subdivided into a new set of triangulations featuring larger triangles designated for the codebook.
    • The triangulations are dynamic, and the split and merge algorithm is applied based on the variance of the triangle pixels.
    • Once the triangulation for the codebook is determined, the most representative 2^n triangles are selected to form the codebook. The value of n significantly impacts the compression time while having a minor effect on the compression ratio and the quality achieved.
    • For each domain triangle, the optimal mapping with a triangle from the codebook is sought using a minimum mean square error (MSE) criterion
    • The optimal mapping between triangles is found by making combinations of::
      • Permutations of the vertices (6 possibilities)
      • Determining an offset for the mean
      • Finding a scale factor between 0 and 1, which is applied to the deviation from the mean. This scale factor should remain between 0 and 1 to prevent divergence during the iterative decompression process
      Additionally, these parameters should be quantized using a limited number of bits to ensure that both the compression time and ratio are reasonable and in line with the desired quality.
  • The stored information in the compressed file for each channel:
    • The information to reproduce the two triangulations:
      • Triangles that split in each iteration
      • Vertices that were removed as a result of the merge (after completing the split iterations)
    • The selection of the 2^n triangles of the codebook
    • The optimal mapping of each domain triangle:
      • Which codebook triangle it uses to map (n bits)
      • The optimal vertex permutation (6 combinations, 3 bits)
      • Offset (the authors indicate that the offset is effectively represented with 6 bits)
      • Scale (the authors indicate that the scale is effectively represented with 6 bits)
  • Decompression (for each channel):
    • The triangles of the two triangulations are obtained.
    • The codebook triangles are obtained.
    • This process is repeated until convergence is achieved:
      • The mapping of all domain triangles to their optimal correspondences with the codebook triangles


After earning a Master's degree in Artificial Intelligence, I envision innovating how to derive the most significant triangles for the codebook by applying K-medoids.

I am unsure if the innovation will improve or hinder the algorithm, but it saves me from needing to program it myself, which initially seemed complicated.


Image processing is divided into channels, typically RGB.

It utilizes multiprocessing, with one thread dedicated to each channel.


With version v1.1, a reader compatible with the ImageIO standard has been added.

Therefore, you can open a compressed image (.dfc) with the application simply by doing:

BufferedImage image = ImageIO.read("image.dfc");

Windows

All

Fractal image compression v1.0 (2022-2024)

Watch vídeo
Download

Fractal image compression v1.1 (2026)

Download

Versions

image

The application implements a fractal image compression algorithm described in an IEEE paper from my university days. It is based on Delaunay triangulation and block coding.

I collaborated with a university classmate to develop the initial version of this algorithm during an internship for the last course of Teleco Television (plan 64 of Barcelona).

The internet was still in its early stages, and any progress relied almost entirely on individual efforts and physical documents.

I remember that we developed a fairly good Delaunay triangulation and successfully implemented the split and merge approach. This involved calculating the most representative triangles and finding the optimal mappings during the coding process. However, despite three months of intensive development, we never completed the application.

Now, 25 years later, I present to you this new implementation of the algorithm, fully developed and completed in a record time of two weeks.

Obviously, something will be improved 25 years later. Additionally, this time with added function support to handle triangles, which I had already programmed for the Morphing effect application.

This time using a Delaunay triangulation library programmed by professionals.

It's evident that when you don't have to make the bricks yourself, the faster you can build the walls ...


Demonstration video

image

The new feature in version v1.1 is the addition of a fractal-compressed image reader within the application that is compatible with ImageIO.

Therefore, you can read a compressed image (.dfc) with the application as follows:


BufferedImage image = ImageIO.read("image.dfc");


Comparing the image in .jpg format and in the application's .dfc format, you can see that the quality is somewhat worse than in .jpg and that it takes up a slightly larger file (as expected).

But the result isn't bad at all.

However, given the long processing time required for compression, this type of compression and its implementation in the application are only of academic interest.


04/05/2026 - 04/12/2026. After having recovered the evolution of this application, I propose to do tests with real images, and I try it with one of "4000 x 3000" pixels.

I encounter many problems:

  • The process takes forever in the split iterations (due to the extensive triangulations of up to 400,000 triangles, and that the split condition check was repeated for all triangles in each iteration)
  • The memory runs out after reaching the limit of 23 GB that I had on my system. Because:
    • The result of the split and merge iterations were stored in a boolean list (around 16 iterations x 2 types of triangulation x 3 channels x 400,000 elements!!!!). That makes a total of around 40,000,000 elements, which is still acceptable)
    • In addition, the selection of the book of most representative triangles (set to 256) was carried out with a K-medoids (over 400,000 elements) (I think the memory used by that algorithm is O(n^2). Now it's getting out of hand...)
    • And, for more INRI, those calculations were performed in parallel for the three channels (rgb) !!
  • Once those problems are solved, I manage to compress the (4000 x 3000) image, but I see that it takes between 6 and 8 hours to complete the work.

And I propose to solve them:

  • For the eternalization of splits. Solution:
    • I increase the minimum size of the triangles to split, in a stepwise manner proportional to the number of pixels in the image. Resulting in a reduction in the number of triangles in the triangulations. In the used image of (4000 x 3000) the number of triangles is divided by more than 4 (we went from about 400,000 triangles to about 100,000 triangles).
    • In addition, I create a Set with the triangles that do not meet the split criterion (relative to the variance of the values ​​of their pixels), so as not to repeat them in each iteration. Now fly!!
  • The system is running out of memory. Solution:
    • Result of splits and merges saved in boolean lists. Solution:
      • As as the split iterations progress, the number of triangles that split is radically smaller, the memory used is saved by storing the indices of the triangles that split in a Set.
    • Memory of K-medoids (presumably O(n^2)). Solution:
      • As we have divided the number of triangles by 4 ..., the memory needed for that algorithm, this reduction of triangles involves dividing the memory used by a factor of around 16.
      • Three K-medoids in parallel (one for each channel). Solution:
        • We sequence the calculations of the triangulations and the selection of the most representative triangles for the code-book (with K-medoids).
      • We have divided the memory needed for K-medoids of 48!!
  • The processing time with "real" images takes forever (the compression of the example image takes between 6 and 8 hours) with 3 threads, one for each channel. Solution:
    • Make the number of threads configurable. (By configuring it to 23 threads (my system has 24 cores), the processing time is reduced to three and a half hours).
  • Effects of the solution:
    • The effect of dividing the number of triangles by 4 obviously results in a notable loss of the quality of the compressed image. But with so much resolution, it's not that important.
    • When dividing the number of triangles by 4, it also causes the size of the compressed file to be divided, supposedly also of the order of 4.

I also aim to try to minimize the size of the compressed file, reorganizing the information to be stored.

The idea is to indicate above all in the coding of the index lists of the triangles that split in each of the iterations, whose original trivial coding was to use one bit per triangle, indicating if it split or not.

I devise an algorithm to try to minimize the size needed to store each of those index sets.

I think it is not wasted ... if you are curious on this website I tell the key points on which I have relied.

Although perhaps it would have been more worthwhile to look for a general lossless compressor like zip or 7z and apply it to the globality of the compressed file... Maybe for the next time.


In the last version of the delivery, a command interface application is included, which translates an archive created with less optimized versions of the coder, to the latest version of the coder, which presumably takes up less space.

Using this small new application on a pair of files with the original encoding (one of 143x143 and another of 4000x3000), it is that the size of the compressed file is reduced by around 4% in them.

Videos

...
Fractal image compression v1.0 (2022-2024)

Downloads

...
Fractal image compressionv1.0 © (2022-2024)
...
Fractal image compression v1.1 © (2026)

Email: frojasg1@hotmail.com