Encoding images as words and languages. (English) Zbl 0777.68056

Culik, Karel II; Dube, Simant

Int. J. Algebra Comput. 3, No. 2, 211-236 (1993).

The authors present some recently developed methods to describe, generate and encode images in a mathematical formalism which uses terminology of finite or infinite words and of formal languages. It is shown how a wide variety of images, in particular, those with fractal (self-similar) geometries can be specified as regular languages over a code alphabet in which symbols denote affine transformations and words are interpreted as compositions of these transformations. Since affine transformations form a monoid under composition, a code language can be manipulated to derive equivalent but shorter descriptions of the same image. This technique is, in particular, useful for the method of recursive subdivisions introduced in this paper.

Reviewer: K.Culik II

MSC:

68Q45	Formal languages and automata
68U10	Computing methodologies for image processing
68U05	Computer graphics; computational geometry (digital and algorithmic aspects)

Keywords:

fractals; image-generation; \(\omega\)-words; finite automata