Statistics-Based Chain Code Compression with Decreased Sensitivity to Shape Artefacts

David Podgorelec, Andrej Nerat, Borut Žalik


Chain codes compactly represent raster curves, but there is still a lot of room for improvement by means of data compression. Several statistics-based chain code compression techniques assign shorter extra codes to frequent pairs of consecutive symbols. Here we systematically extend this concept to patterns of up to six symbols. A curve may be represented by any of the exponentially many overlapped chains of codes, and the dynamic programming approach is proposed to determine the optimal chain. We also propose utilization of multiple averaged hard coded pseudo-statistical models, since the exact statistical models of individual curves are often huge, and they can also significantly differ from each other. A competitive compression efficiency is assured in this manner and, as a pleasant side effect, this efficiency is less affected by the curve’s shape, rasterization algorithm, noise, and image resolution, than in other contemporary methods, which surprisingly do not pay any attention to this problem at all.

Full Text:



Akimov A.; Kolesnikov A.; Fränti P. (2007). Lossless compression of map contours by context tree modeling of chain codes, Pattern Recognition, Elsevier Science, vol. 40, iss. 3, pp. 944-952.

Bribiesca E. (1999). A new chain code. Pattern Recognition, Elsevier Sci., vol. 32, iss. 2, pp. 235-251.

Freeman H. (1961). On the encoding of arbitrary geometric configurations. IRE Transactions on Electronic Computers, IEEE, vol. EC10, iss. 2, pp. 260-268.

Freeman H. (1974). Computer processing of line drawing images. ACM Computing Surveys, ACM, vol. 6, iss. 1, pp. 57-97.

Jones N. C.; Pevzner P. A. (2004). An Introduction to Bioinformatics Algorithms. The MIT Press.

Liu Y. K.; Žalik B. (2005). An efficient chain code with Huffman coding. Pattern Recognition, Elsevier Science, vol. 38, iss. 4, pp. 553-557.

Liu Y. K.; Žalik B.; Wang P.-J.; Podgorelec D. (2012). Directional difference chain codes with quasi-lossless compression and run-length encoding. Signal Processing: Image Commun., Elsevier Science, vol. 27, iss. 9, pp. 973-984.

Liu Y. K.; Wei W.; Wang P.-J.; Žalik B. (2007). Compressed vertex chain codes. Pattern Recogn., Elsevier Science, vol. 40, iss. 11, pp. 2908-2913.

Nunes P.; Marqués F.; Pereira F.; Gasull A. (2000). A contour based approach to binary shape coding using multiple grid chain code. Signal Processing: Image Communication, Elsevier Science, vol. 15, iss. 7-8, pp. 585-599.

Sánchez-Cruz H.; Bribiesca E.; Rodríguez-Dagnino R. M. (2007). Efficiency of chain codes to represent binary objects. Pattern Recognition, Elsevier Science, vol. 40, iss. 6, pp. 1660-1674.

Žalik B.; Lukač N. (2014). Chain code lossless compression using Move-To-Front transform and adaptive Run-Length Encoding. Signal Processing: Image Commun., Elsevier Science, vol. 29, iss.1, pp. 96-106.

Žalik B.; Mongus D.; Lukač N.; Rizman Žalik K. (2018). Efficient chain code compression with interpolative coding. Information Sciences, Elsevier Science, vol. 439-440, pp. 39-49.


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.