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

Authors

  • David Podgorelec University of Maribor, Faculty of Electrical Engineering and Computer Science
  • Andrej Nerat University of Maribor, Faculty of Electrical Engineering and Computer Science
  • Borut Žalik University of Maribor, Faculty of Electrical Engineering and Computer Science

DOI:

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

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.

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

Downloads

Published

2021-06-15

How to Cite

Podgorelec, D., Nerat, A., & Žalik, B. (2021). Statistics-Based Chain Code Compression with Decreased Sensitivity to Shape Artefacts. Informatica, 45(2). https://doi.org/10.31449/inf.v45i2.3110

Issue

Vol. 45 No. 2 (2021)

Section

MATCOS-19

License

I assign to Informatica, An International Journal of Computing and Informatics ("Journal") the copyright in the manuscript identified above and any additional material (figures, tables, illustrations, software or other information intended for publication) submitted as part of or as a supplement to the manuscript ("Paper") in all forms and media throughout the world, in all languages, for the full term of copyright, effective when and if the article is accepted for publication. This transfer includes the right to reproduce and/or to distribute the Paper to other journals or digital libraries in electronic and online forms and systems.

I understand that I retain the rights to use the pre-prints, off-prints, accepted manuscript and published journal Paper for personal use, scholarly purposes and internal institutional use.

In certain cases, I can ask for retaining the publishing rights of the Paper. The Journal can permit or deny the request for publishing rights, to which I fully agree.

I declare that the submitted Paper is original, has been written by the stated authors and has not been published elsewhere nor is currently being considered for publication by any other journal and will not be submitted for such review while under review by this Journal.  The Paper contains no material that violates proprietary rights of any other person or entity. I have obtained written permission from copyright owners for any excerpts from copyrighted works that are included and have credited the sources in my article. I have informed the co-author(s) of the terms of this publishing agreement.


Copyright ©  Slovenian Society Informatika