A picture is a two-dimensional counterpart of a string and it is represented by a rectangular array of symbols over a finite alphabet Σ. A set X of pictures over Σ is a code if every picture over Σ is tilable in at most one way with pictures in X. Recently, the definition of strong prefix code was introduced as a decidable family of picture codes, and a construction procedure for maximal strong prefix (MSP) codes was proposed. Unfortunately, the notion of completeness cannot be directly transposed from strings to pictures without loosing important properties. We generalize to pictures a special property satisfied by complete set of strings that allow to prove interesting characterization results for MSP codes. Moreover, we show an encoding algorithm for pictures using pictures from a MSP code. The algorithm is based on a new data structure for the representation of MSP codes.
Anselmo, M., Giammarresi, D., Madonia, M. (2018). Encoding pictures with maximal codes of pictures. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp.552-565). Springer Verlag [10.1007/978-3-319-73117-9_39].
Encoding pictures with maximal codes of pictures
Giammarresi, Dora
;
2018-01-01
Abstract
A picture is a two-dimensional counterpart of a string and it is represented by a rectangular array of symbols over a finite alphabet Σ. A set X of pictures over Σ is a code if every picture over Σ is tilable in at most one way with pictures in X. Recently, the definition of strong prefix code was introduced as a decidable family of picture codes, and a construction procedure for maximal strong prefix (MSP) codes was proposed. Unfortunately, the notion of completeness cannot be directly transposed from strings to pictures without loosing important properties. We generalize to pictures a special property satisfied by complete set of strings that allow to prove interesting characterization results for MSP codes. Moreover, we show an encoding algorithm for pictures using pictures from a MSP code. The algorithm is based on a new data structure for the representation of MSP codes.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
