Rational and affine expressions for image description. (English) Zbl 0784.68058

Culik, Karel II; Dube, Simant

Discrete Appl. Math. 41, No. 2, 85-120 (1993).

The authors present methods based on automata techniques to generate and infer ‘images’. Languages and relations over an arbitrary alphabet are treated as images, strings being considered as rational coordinates. The generation of an images is done from a set of rational or affine expression.
The most important parts of the article is generation, including comparison of various methods. For inference the authors sketch a quad- tree approach and announcee (added in proof) an automated algorithm for data compression based on slight extension of these techniques and wavelets.

Reviewer: J.T.Lapresté (Aubière)

MSC:

68Q45	Formal languages and automata
68Q42	Grammars and rewriting systems
68Q10	Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)

Keywords:

image description; rational expression; languages and relations; automata; affine expression; quad-tree; data compression

References:

[1]	Barnsley, M. F., Fractals Everywhere (1988), Academic Press: Academic Press New York · Zbl 0691.58001
[2]	Barnsley, M. F.; Devaney, R. L.; Mandelbrot, B. B.; Peitgen, H.-O.; Saupe, De; Voss, R. F., Science of Fractal Images (1988), Springer: Springer Berlin
[3]	Barnsley, M. F.; Jacquin, A.; Reuter, L.; Sloan, A. D., Harnessing chaos for image synthesis, Computer Graphics, SIGGRAPH 1988 Conference Proceedings (1988)
[4]	Berstel, J.; Morcrette, M., Compact representation of patterns by finite automata, Proceedings Pixim ’89, 387-402 (1989), Paris
[5]	Berstel, J.; Nait Abdallah, A., Quadtrees generated by finite automata, AFCET 61/62, 167-175 (1989)
[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., Affine automata and related techniques for generation of complex images, (Tech. Rept. TR90009, 452 (1990), Department of Computer Science, University of S. Carolina), 224-231, Preliminary version in: Proceedings of MFCS 1990, Lecture Notes in Computer Science Springer, Berlin
[9]	Culik, K.; Yu, S., Cellular automata, ωω-regular sets, and sofic systems, Discrete Appl. Math., 32, 85-101 (1991) · Zbl 0743.68085
[10]	Even, S., Rational numbers and regular events, IEEE Trans. Electron. Comput., 13, 740-741 (1964) · Zbl 0178.33101
[11]	Gleick, J., Chaos—Making a New Science (1988), Penguin Books: Penguin Books Harmondsworth · Zbl 0706.58002
[12]	Hartmanis, J.; Stearns, R. E., Sets of numbers defined by finite automata, Amer. Math. Monthly, 74, 539-542 (1967) · Zbl 0149.01002
[13]	Hunter, G. M.; Steiglitz, K., Operations on images using quadtrees, IEEE Trans. Pattern Anal. Machine Intell., 1, 145-153 (1979)
[14]	Mandelbrot, B., The Fractal Geometry of Nature (1982), Freeman: Freeman San Francisco, CA · Zbl 0504.28001
[15]	Mazoyer, J., An overview of the firing squad synchronization problem, (Choffrut, C., Automata Networks, 316 (1988), Springer: Springer Berlin), 82-94, Lecture Notes in Computer Science · Zbl 0656.68054
[16]	Shallit, J.; Stolfi, J., Two methods for generating fractals, Comput. Graphics, 13, 185-191 (1989)
[17]	Staiger, L., Quadtrees and the Hausdorff dimension of pictures, Workshop on Geometrical Problems of Image Processing, 173-178 (1989), Georgenthal · Zbl 0679.68169
[18]	Tzeng, W. G., The equivalence and learning of probabilistic automata, FOCS Proceedings, 268-273 (1989)