The Polyomino Compressed Image Format

The Polyomino Compressed Image Format (PCIF, formerly PCF) is a new lossless compressed image format developed by Stefano Brocchi. The goal of the development of the PCIF algorithm is to create an efficient image compressing engine using techniques that do not compromise time performances. Even if most image formats actually imply lossy compression, there can be cases where lossless image compression can be recommandable or even mandatory, as explained here.

Actually, the most popular format for lossless image compression is the Portable Network Graphics (PNG) format. Other formats for general-purpose compression such as ZIP, but also higher-performance algorithms based on PPMD or BWT (used for example in the newest winzip versions or in the open-source 7 zip program) usually give worst results as they are not specialyzed for image data. An exception is the RAR algorithm that gives results comparable the ones of PNG. Another format that is rising is the Jpeg2000 standard, offering also a high-performance lossless compression mode. Finally, a new proposal by the Jpeg commitee for lossless image compression is the JPEG-LS standard.

The new Polyomino Compressed Image Format achieves globally the best compression results in respect to all formats mentioned, with results very close to the JPEG-LS format; benchmarks have been done on two popular image sets (the Waterloo color image set and the Kodak image set), on another image set proposed by the author and on a fourth set proposed in A more accurate analysis of results is in the benchmarks section. Shortly, in comparison to the JP2 lossless files, the PCIF compressed images are slightly bigger regarding photographical images but much smaller in computer generated or high edge images. The PNG files are smaller for very 'regular' images with wide uniform color areas, but most of the PNG files result to be from 25% to 40% bigger than PCIF files.

The PCIF algorithm uses a combination of techniques to obtain a good lossless image compression ratio without compromising time performances, as reversible filtering and huffman coding. A new tecnique is also intruduced to group points in convenently codable shapes calles polyominoes. A complete description of the algorithm with an example can be found in the algorithm section.

The PCIF algorithm is addressed to be used for lossless compression of true color images. This is important because often this is not considered in research algorithms. Often algorithms that compress true color images just do a color transform of the three color layers and then compress the three obtained channels indipendently. The PCIF algorithm obtains a major advantage from color correlation because instead of applying one only color tranformation to all the image it searches a good tranform for every single 8x8 pixel zone, seeking a tranform close to optimality on a local basis.

The software realizing the compression and decompression algorithm is available on the download section. Actually the software is free for personal use; anyway before downloading any file you must carefully read and accept the agreement. All the program has been realized in the Java language, allowing a very easy web integration, as demostrated by the PCIF applet.

For any question about the PCIF algorithm, the available program or its benchmarks you can contact the author.

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.