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

David Podgorelec, Andrej Nerat, Borut Žalik

Abstract


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:

PDF

References


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.

https://doi.org/10.1007/11499145_33

Bribiesca E. (1999). A new chain code. Pattern Recognition, Elsevier Sci., vol. 32, iss. 2, pp. 235-251. https://doi.org/10.1016/s0031-3203(98)00132-0

Freeman H. (1961). On the encoding of arbitrary geometric configurations. IRE Transactions on Electronic Computers, IEEE, vol. EC10, iss. 2, pp. 260-268. https://doi.org/10.1109/tec.1961.5219197

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

https://doi.org/10.1145/356625.356627

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.

https://doi.org/10.1016/j.patcog.2004.08.017

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.

https://doi.org/10.1016/j.image.2012.07.008

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.

https://doi.org/10.1016/j.patcog.2007.03.001

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.

https://doi.org/10.1016/s0923-5965(99)00041-7

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.

https://doi.org/10.1016/j.patcog.2006.10.013

Ž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. https://doi.org/10.1016/j.image.2013.09.002

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

https://doi.org/10.1016/j.ins.2018.01.045




DOI: https://doi.org/10.31449/inf.v45i2.3110

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