A novel lossless image compression algorithm using multiset permutation encoding

In this paper, a new lossless image compression algorithm is proposed. The algorithm is based on the fact that the number of possible permutations for a binary multiset with a fixed number of elements gets smaller when the number of ‘1’ bits in the multiset approaches zero. Therefore, a particular permutation of the multiset can be encoded using few bits if the number of ‘1’ bits in the multiset is small. To enhance the compression performance of the encoding, pixel color transformation is performed as a preprocessing step to eliminate inter-pixel redundancies as well as assign each pixel value a new value that has a number of bits of ‘1’ as few as possible (depending on the frequency of the pixel value in the image). Additional compression techniques such as a variable length encoding and a run length encoding are also incorporated to enhance compression performance of the encoding process. Based on experiments, the performance of the proposed algorithm is comparable to many popular lossless image compression algorithms.