Abstract:
Finite automata are used for the encoding and compression of images. For
black-and-white images, for instance, using the quad-tree representation, the
black points correspond to ω-words defining the corresponding paths in the
tree that lead to them. If the ω-language consisting of the set of all these
words is accepted by a deterministic finite automaton then the image is said
to be encodable as a finite automaton. For grey-level images and colour images
similar representations by automata are in use.
In this paper we address the question of which images can be encoded as
finite automata with full infinite precision. In applications, of course, the image
would be given and rendered at some finite resolution – this amounts to
considering a set of finite prefixes of the ω-language – and the features in the
image would be approximations of the features in the infinite precision rendering.
We focus on the case of black-and-white images – geometrical figures, to
be precise – but treat this case in a d-dimensional setting, where d is any
positive integer. We show that among all polygons and convex polyhedra in
d-dimensional space exactly those with rational corner points are encodable
as finite automata.
In the course of proving this we show that the set of images encodable as
finite automata is closed under rational affine transformations.
Several properties of images encodable as finite automata are consequences
of this result. Finally we show that many simple geometric figures such as
circles and parabolas are not encodable as finite automata.