×
Culik, Karel II; Dube, Simant

Affine automata and related techniques for generation of complex images. (English) Zbl 0779.68062

Theor. Comput. Sci. 116, No. 2, 373-398 (1993).
The paper introduces two generalizations of Barnsley’s Iterative Function Systems (IFS): Probabilistic Affine Automata and Mutual Recursive Function Systems. In particular, the latter turned out to be a powerful tool for image description and generation. A number of theoretical results about these systems is shown. Recently, Weighted Finite Automata (introduced in [K. Culik II and J. Karhumäki, Automata Computing Real Functions, SIAM J. Comput., to appear]) have proved to be an excellent tool for image compression [K. Culik II and J. Kari, Image Compression Using Weighted Finite Automata, Computer and Graphics vol. 17, 3, 305-313 (1993)] and [K. Culik II and J. Kari, Image-data Compression Using Edge-Optimizing Algorithm for WFA Inference, Journal of Information and Management, to appear]).
Reviewer: Karel II Culik

Cited in 13 Documents

MSC:

68Q45 Formal languages and automata
68U10 Computing methodologies for image processing

Keywords:

image generation; Iterative Function Systems; Probabilistic Affine Automata; Mutual Recursive Function Systems
Cite Review PDF
Full Text: DOI

References:

[1] Barnsley, M. F., Fractals Everywhere (1988), Academic Press: Academic Press New York · Zbl 0691.58001
[2] Barnsley, M. F.; Elton, J. H.; Hardin, D. P., Recurrent iterated function systems, Constr. Approx., 5, 3-31 (1989) · Zbl 0659.60045
[3] Barnsley, M. F.; Devaney, R. L.; Mandelbrot, B. B.; Peitgen, H-O.; De, Saupe; Voss, R. F., Science of Fractal Images (1988), Springer: Springer Berlin
[4] M.F. Barnsley, A. Jacquin, L. Reuter and A.D. Sloan, Harnessing chaos for image synthesis, in:Computer Graphics, Proc. SIGGARPH’ 1988 Conf.; M.F. Barnsley, A. Jacquin, L. Reuter and A.D. Sloan, Harnessing chaos for image synthesis, in:Computer Graphics, Proc. SIGGARPH’ 1988 Conf.
[5] J. Berstel and M. Morcrette, Compact representation of patterns by finite automata, in:Proc. Pixim ’89; J. Berstel and M. Morcrette, Compact representation of patterns by finite automata, in:Proc. Pixim ’89
[6] Boasson, L.; Nivat, M., Adherences of languages, J. Comput. System Sci., 20, 285-309 (1980) · Zbl 0471.68052
[7] Cohen, R.; Gold, A., Theory of ω-languages, Part I and II, J. Comput. System Sci., 15, 169-208 (1977) · Zbl 0363.68113
[8] Culik, K.; Dube, S., L-systems and MRFS (1991), manuscript
[9] K. Culik and S. Dube, Rational and affine expressions for image description, Tech. Report TR90001, Dept. of Computer Science, Univ. of S. Carolina;Discrete Appl. Math.; K. Culik and S. Dube, Rational and affine expressions for image description, Tech. Report TR90001, Dept. of Computer Science, Univ. of S. Carolina;Discrete Appl. Math. · Zbl 0784.68058
[10] K. Culik and S. Yu, Cellular automata, ωω-regular sets, and sofic systems,Discrete Appl. Math.; K. Culik and S. Yu, Cellular automata, ωω-regular sets, and sofic systems,Discrete Appl. Math. · Zbl 0743.68085
[11] Dekking, F. M., Recurrent sets, Adv. in Math., 44, 78-104 (1982) · Zbl 0495.51017
[12] Ellis, D. B.; Branton, M. G., Non-self-similar attractors of hyberbolic IFS, (Alexander, J. C., Dynamical Systems. Dynamical Systems, Lecture Notes in Mathematics, Vol. 1342 (1988), Springer: Springer Berlin), 158-171 · Zbl 0683.58033
[13] Gleick, J., Chaos—Making a New Science (1988), Penguin: Penguin Baltimore, MD · Zbl 0706.58002
[14] Liu, Y., Recurrent IFS, ω-orbit finite automata, and regular set plotter, (M.S. Thesis (1990), Dept. of Comp. Sci., Univ. of S. Carolina)
[15] Mandelbrot, B., The Fractal Geometry of Nature (1982), Freeman: Freeman San Francisco · Zbl 0504.28001
[16] Mauldin, R. D.; Williams, S. C., Hausdorff dimension in graph directed constructions, Trans. Am. Math. Soc., 309, 811-829 (1988) · Zbl 0706.28007
[17] Prusinkiewicz, P., Applications of L-systems to computer imagery, (Ehrig, H., Graph Grammars and their Application to Computer Science. Graph Grammars and their Application to Computer Science, Lecture Notes in Computer Science, Vol. 291 (1987), Springer: Springer Berlin), 534-548
[18] K. Culik II and S. Dube, Balancing order and chaos in image generation,Computer and Graphics; K. Culik II and S. Dube, Balancing order and chaos in image generation,Computer and Graphics · Zbl 0769.68120
[19] Culik, K.; Dube, S., Balancing order and chaos in image generation, (Proc. 18th Internat. Colloq. on Automata, Languages and Programming, Madrid, Spain, July 1991. Proc. 18th Internat. Colloq. on Automata, Languages and Programming, Madrid, Spain, July 1991, Lecture Notes in Computer Science, Vol. 510 (1991), Springer: Springer Berlin), 600-614 · Zbl 0769.68120
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.