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

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


68Q45 Formal languages and automata
68U10 Computing methodologies for image processing
Full Text: DOI


[1] Barnsley, M.F., Fractals everywhere, (1988), 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 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.
[5] J. Berstel and M. Morcrette, Compact representation of patterns by finite automata, in:Proc. Pixim ’89, Paris, pp. 387-402.
[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)
[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., to appear. · Zbl 0784.68058
[10] K. Culik and S. Yu, Cellular automata, ωω-regular sets, and sofic systems,Discrete Appl. Math., to appear. · 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, (), 158-171
[13] Gleick, J., Chaos—making a new science, (1988), Penguin Baltimore, MD · Zbl 0706.58002
[14] Liu, Y., Recurrent IFS, ω-orbit finite automata, and regular set plotter, ()
[15] Mandelbrot, B., The fractal geometry of nature, (1982), 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, (), 534-548
[18] K. Culik II and S. Dube, Balancing order and chaos in image generation,Computer and Graphics, to appear. · Zbl 0769.68120
[19] Culik, K.; Dube, S., Balancing order and chaos in image generation, (), 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. 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.