This award will permit the continued study of the use of random iterated function systems (IFS) to generate and encode digital images. In IFS generation an ergodic Markov chain is simulated in R2 or R3 through products of random affine transformations, and its trajectory is plotted to create an image. The IFS encoding problem involves the construction of such a Markov chain so as to generate a given target image. By exploiting the linearity of the transformations involved with these chains, one can encode any digital image, and for a broad class of images this affords substantial data compression. It is planned to analyze and test various encoding schemes, and to develop algorithms to implement them on vector and parallel machines. It is potentially of great value to deal with large-scale image and encoding problems, particularly involving real time applications of image transmission and communication, image construction and processing and image restoration. Potential applications include 3-D mechanical imaging, visual (e.g., flight) simulators, voice and pattern recognition, optical character and object scanners, image understanding, fingerprint and passport encoding, animation encoding, high resolution graphics and high definition TV.
