Chain code compression using string transformation techniques

• String transformation techniques for lossless chain code compression are examined.
• Burrows–Wheeler transform and Move-to-front transform are applied.
• We examine the effects of using simplified run-length encoding.
• The proposed method outperforms state-of-the-art chain code compression methods.

This paper considers the suitability of string transformation techniques for lossless chain codes' compression. The more popular chain codes are compressed including the Freeman chain code in four and eight directions, the vertex chain code, the three orthogonal chain code, and the normalised directional chain code. A testing environment consisting of the constant 0-symbol Run-Length Encoding (RLE0L), Move-To-Front Transformation (MTFT), and Burrows–Wheeler Transform (BWT) is proposed in order to develop a more suitable configuration of these techniques for each type of the considered chain code. Finally, a simple yet efficient entropy coding is proposed consisting of MTFT, followed by the chain code symbols' binarisation and the run-length encoding. PAQ8L compressor is also an option that can be considered in the final compression stage. Comparisons were done between the state-of-the-art including the Universal Chain Code Compression algorithm, Move-To-Front based algorithm, and an algorithm, based on the Markov model. Interesting conclusions were obtained from the experiments: the sequential uses of MTFT, RLE0L, and BWT are reasonable only in the cases of shorter chain codes' alphabets as with the vertex chain code and the three orthogonal chain code. For the remaining chain codes, BWT alone provided the best results. The experiments confirm that the proposed approach is comparable against other lossless chain code compression methods, while in total achieving higher compression rates.