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.
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|