Abstract
String covers are a powerful tool for analyzing the quasi-periodicity of 1-dimensional data and find applications in automata theory, computational biology, coding and the analysis of transactional data. A cover of a string T is a string C for which every letter of T lies within some occurrence of C. String covers have been generalized in many ways, leading to k-covers, λ -covers, approximate covers and were studied in different contexts such as indeterminate strings. In this paper we generalize string covers to the context of 2-dimensional data, such as images. We show how they can be used for the extraction of textures from images and identification of primitive cells in lattice data. This has interesting applications in image compression, procedural terrain generation and crystallography.
| Original language | English |
|---|---|
| Title of host publication | Theory and Applications of Models of Computation - 15th Annual Conference, TAMC 2019, Proceedings |
| Editors | T. V. Gopal, Junzo Watada |
| Publisher | Springer Verlag |
| Pages | 536-549 |
| Number of pages | 14 |
| ISBN (Print) | 9783030148119 |
| DOIs | |
| Publication status | Published - Jan 1 2019 |
| Event | 15th Annual Conference on Theory and Applications of Models of Computation, TAMC 2019 - Kitakyushu, Japan Duration: Apr 13 2019 → Apr 16 2019 |
Publication series
| Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Volume | 11436 LNCS |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |
Conference
| Conference | 15th Annual Conference on Theory and Applications of Models of Computation, TAMC 2019 |
|---|---|
| Country | Japan |
| City | Kitakyushu |
| Period | 4/13/19 → 4/16/19 |
Fingerprint
ASJC Scopus subject areas
- Theoretical Computer Science
- Computer Science(all)
Cite this
An output-sensitive algorithm for the minimization of 2-dimensional string covers. / Popa, Alexandru; Tanasescu, Andrei.
Theory and Applications of Models of Computation - 15th Annual Conference, TAMC 2019, Proceedings. ed. / T. V. Gopal; Junzo Watada. Springer Verlag, 2019. p. 536-549 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11436 LNCS).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution
}
TY - GEN
T1 - An output-sensitive algorithm for the minimization of 2-dimensional string covers
AU - Popa, Alexandru
AU - Tanasescu, Andrei
PY - 2019/1/1
Y1 - 2019/1/1
N2 - String covers are a powerful tool for analyzing the quasi-periodicity of 1-dimensional data and find applications in automata theory, computational biology, coding and the analysis of transactional data. A cover of a string T is a string C for which every letter of T lies within some occurrence of C. String covers have been generalized in many ways, leading to k-covers, λ -covers, approximate covers and were studied in different contexts such as indeterminate strings. In this paper we generalize string covers to the context of 2-dimensional data, such as images. We show how they can be used for the extraction of textures from images and identification of primitive cells in lattice data. This has interesting applications in image compression, procedural terrain generation and crystallography.
AB - String covers are a powerful tool for analyzing the quasi-periodicity of 1-dimensional data and find applications in automata theory, computational biology, coding and the analysis of transactional data. A cover of a string T is a string C for which every letter of T lies within some occurrence of C. String covers have been generalized in many ways, leading to k-covers, λ -covers, approximate covers and were studied in different contexts such as indeterminate strings. In this paper we generalize string covers to the context of 2-dimensional data, such as images. We show how they can be used for the extraction of textures from images and identification of primitive cells in lattice data. This has interesting applications in image compression, procedural terrain generation and crystallography.
UR - http://www.scopus.com/inward/record.url?scp=85064874787&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85064874787&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-14812-6_33
DO - 10.1007/978-3-030-14812-6_33
M3 - Conference contribution
AN - SCOPUS:85064874787
SN - 9783030148119
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 536
EP - 549
BT - Theory and Applications of Models of Computation - 15th Annual Conference, TAMC 2019, Proceedings
A2 - Gopal, T. V.
A2 - Watada, Junzo
PB - Springer Verlag
ER -