The PCIF algorithm: compression phase

At the beginning of this phase for each layer a compression method is chosen. This allows the application of different compression tecniques for different types of data, as the compression through polyominoes is more effective on layers with few ones while the compression with RLE and Huffman codes has better results with layers with higher enthropy. In table, the different sizes of the various compressed components of the Lenna image.

We consider we can dispose of the percentage d of zeros in a layer, as the algorithm counts the number of zero values during the previous decomposition phase. We also consider the index of the layer b, as 0 for layers relative to the least sigificative bit up to 7 for the most significative. This is because we expect that, having equal density of zeros, layers that refer to higher bits have more grouped one values, and this lowers the enthropy of the matrix. The function that determines the compression method is the following:

  • If d + b > 90 then compress the layer using polyominoes.
  • If 52 < d + b <= 90 then compress the layer with RLE and Huffman coding.
  • If d + b <= 52 then store the layer 'as is'.

Note that thanks to the remapping phase we expect that b is always >= 50. In the third rule of the above, we save time in compression and decompression at the cost of only a few bits of the final file size, as we expect that very chaotical layers that fall in this category are very weakly compressible.

The values above have been chosen empirically thanks to various sperimentations, always keeping in mind the efficiency goal. The limit 90 in the first and second rule gives quite similar results if lowered up to 85, but in this cases the RLE and Huffman compression method has been chosen as it allows a faster elaboration.

Further information about the two different compression tecniques can be found at the compression through polyominoes section and in the compression through RLE and Huffman codes section.

In the following table, we can see the different sizes of the various compressed components of the Lenna image. For every layer the used compression method and its compressed size are shown. The intestation of the image contains mainly the information about the filters applied to the image in the different zones, and also includes the remapping array and various image information.

Layer Bit Color Zero percentage Compressed with Size
PCF Intestation - - - - 3.4 KB
0 7 Blue 99.9 % Polyominoes 124 bytes
1 7 Green 99.9 % Polyominoes 45 bytes
2 7 Red 99.9 % Polyominoes 18 bytes
3 6 Blue 99 % Polyominoes 1.7 KB
4 6 Green 99.8 % Polyominoes 641 bytes
5 6 Red 99.9 % Polyominoes 349 bytes
6 5 Blue 96 % Polyominoes 7.3 KB
7 5 Green 98 % Polyominoes 3.7 KB
8 5 Red 99 % Polyominoes 2.4 KB
9 4 Blue 82 % RLE and Huffman 21.8 KB
10 4 Green 90 % Polyominoes 15.4 KB
11 4 Red 93 % Polyominoes 10.5 KB
12 3 Blue 65 % RLE and Huffman 30.1 KB
13 3 Green 71 % RLE and Huffman 27.7 KB
14 3 Red 80 % RLE and Huffman 22.6 KB
15 2 Blue 58 % RLE and Huffman 31.6 KB
16 2 Green 60 % RLE and Huffman 31.2 KB
17 2 Red 65 % RLE and Huffman 30.0 KB
18 1 Blue 54 % RLE and Huffman 31.96 KB
19 1 Green 55 % RLE and Huffman 31.88 KB
20 1 Red 57 % RLE and Huffman 31.68 KB
21 0 Blue 54 % RLE and Huffman 31.88 KB
22 0 Green 54 % RLE and Huffman 31.99 KB
23 0 Red 55 % RLE and Huffman 31.95 KB
Total filesize - - - - 432 KB
The evolution of the PCIF algorithm is now available ! It has a greater compression ratio, it is much faster and the implementation is available in both Java bytecode and native executables. Take a look at the new BCIF algorithm.