The complexity of compressing subsegments of images described by finite automata. (English) Zbl 1010.68075

Summary: We investigate how the compression size of the compressed version of a two-dimensional image changes when we cut off a part of it, e.g. extract a photo of one person from a photo of a group of people, when compression is considered in terms of finite automata. Denote by \(c(T)\) the compression size of a square image \(T\) in terms of deterministic automata, it is the smallest size of a deterministic acyclic automaton \(A\) describing \(T\). The corresponding alphabet of \(A\) has only four letters, corresponding to four quadrants. We consider an independent useful combinatorial interpretation of \(c(T)\) in terms of regular subsquares of \(T\). Denote by \(\varPsi (n)\) the largest compression size \(c(R)\) of a square subsegment \(R\) of the image \(T\) such that \(c(T)=n\). We show that there is a constant \(c>0\) such that: \[ cn^{2.5}\leqslant \varPsi (n)\leqslant n^{2.5} \] For weighted automata we show that the compression size grows only linearly, if \(T\) is described by a weighted automaton with \(n\) states and \(m\) edges then a subimage \(R\) can be described by a similar automaton having \(O(n)\) states and \(O(m)\) edges.
We also show how to construct efficiently (in linear time w.r.t. the total size of the input and the produced output) the compressed representation of subsegments given the compressed representation of the whole image.


68Q45 Formal languages and automata
Full Text: DOI


[1] P. Berman, M. Karpinski, L. Larmore, W. Plandowski, W. Rytter, On the complexity of pattern matching of highly compressed two-dimensional texts, in: Proceedings of the CPM’97, Lecture Notes in Computer Science, Vol. 1264, 1997, pp. 40-51. · Zbl 1059.68098
[2] Culik, K.; Karhumäki, J., Finite automata computing real functions, SIAM J. comput., 23, 4, 789-814, (1994) · Zbl 0820.68061
[3] Culik, K.; Kari, J., Image compression using weighted finite automata, Comput. graph., 17, 305-313, (1993)
[4] Culik, K.; Kari, J., (), 243-258
[5] Derencourt, D.; Karhumäki, J.; Latteux, M.; Terlutte, A., On continuous functions computed by finite automata, RAIRO theor. inform. appl., 28, 387-404, (1994) · Zbl 0883.68095
[6] Eilenberg, S., Automata, Languages and machines, Vol. A, (1974), Academic Press New York
[7] M. Farach, M. Thorup, String matching in Lempel-Ziv compressed strings, in: Proc. Twenty-Seventh Annual ACM Symp. on the Theory of Computing, ACM Press, 1995, pp. 703-712. · Zbl 0978.68520
[8] L. Ga̧sieniec, M. Karpiński, W. Plandowski, W. Rytter, Efficient algorithms for Lempel-Ziv encoding (extended abstract), in: Proceedings of the SWAT’96, Lecture Notes in Computer Science, Vol. 1097, 1996, pp. 392-403.
[9] J. Karhumäki, W. Plandowski, W. Rytter, Pattern-matching problems for two-dimensional images described by finite automata, Nordic J. Comput. 7 (2000) 1-13. · Zbl 0958.68146
[10] J. Karhumäki, W. Plandowski, W. Rytter, The compression of subsegments of images described by finite automata, in: Proceedings of the CPM’99, Lecture Notes in Computer Science, Vol. 1645, pp. 186-195. · Zbl 1063.68687
[11] Kari, J.; Franti, P., Arithmetic coding of weighted finite automata, RAIRO theor. inform. appl., 28, 343-360, (1994) · Zbl 0883.68094
[12] M. Karpinski, W. Rytter, A. Shinohara, Pattern-matching for strings with short description, in: Proceedings of the CPM’95, Lecture Notes in Computer Science, Vol. 937, 1995, pp. 205-214.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.