Computational fractal geometry: New methods for image description, generation and compression.

摘要

The subject of this dissertation is Computational Fractal Geometry. It is an investigation of a number of methods to describe, generate and encode a wide variety of images, possibly with grey or color tones, which might have fractal (self-similar) geometries.;The basic idea behind the first method is to interpret languages and relations over some alphabet as images by treating strings as rational coordinates. In particular, rational relations specified by rational expressions or finite generators are considered. It is shown how texture (grey or color) images can be defined by probabilistic finite generators (PFG).;In the second method, strings over some alphabet are interpreted in an altogether different fashion--symbols represent affine transformations over an n-dimensional Euclidean space, and strings are interpreted as compositions of these transformations. Languages over this code alphabet of affine transformations, in particular regular languages, are interpreted as images. The approach turns out to be a generalization of the Iterated Function Systems (IFS) introduced by M. F. Barnsley. This generalization is called Mutually Recursive Function Systems (MRFS). Probabilistic MRFS (PMRFS) allow one to define texture images. It is shown that (P)FG are a proper subset of (P)MRFS.;The problem of automatic encoding of images is addressed. A conceptually simple algorithm to infer a (P)FG for a given image is presented. This encoding algorithm for (P)FG is generalized to the method of recursive subdivision which allows one to come up with better compression ratios at the cost of using a few more affine transformations. The computer-graphical applications of (P)MRFS are investigated. In particular, control sets which define sequences of many MRFS under finite control are shown to be a convenient tool to model a large class of real-world images.;L-systems constitute another powerful method to generate plants and fractal curves. The relationship between L-systems and MRFS is investigated. It is also shown that Cellular Automata can generate fractal or highly regular time-space patterns.;Finally, a number of interesting problems is suggested for future work. For example, it is indicated how the techniques developed in this dissertation yield a novel and quite general method to analyze the time complexity of Divide-and-Conquer Algorithms, by geometrically capturing the dynamic structure of such algorithms as fractals.