Back to search

University of Glasgow

Jigsaws and Faster Fractal Pictures

Abstract

dc:description.abstract

Today it is possible to express a wide range of images as attractors of Iterated Function Systems in the plane. An Iterated Function System, or IFS for short, is a finite collection of contractive affine transformations w1, w2,...,wN, while the attractor A is the limit under repeated application of the associated collage map W(E) = UiWi(E) for any compact set E - that is, Wn(E) → A [2, 12, 25, 26]. Since only 6N real numbers, known as the IFS code, are required to store the image, IFS's are now being widely used as a method of image compression [3, 4, 9] - leading to the need for algorithms which produce the attractor A quickly on a computer screen. In this thesis, we study one such algorithm - the Graphical Algorithm, or GA [5] -whose main characteristic is that maps are applied to points only after their coordinates have been rounded to integers. By introducing the concept of jigsaws of maps - where the jigsaw piece of an integer point (u, v) is the set of all integer points (x, y) such that w(x, y) rounds to (u, v) - and studying the properties of such sets, we reduce the time taken to produce an approximation to the attractor by up to a factor of N, making the GA as accurate as the Adaptive Cut Method (ACM) [11, 25, 26], and a frequently faster option than the popular Random Iteration Algorithm (RIA) [1, 2].

Degree

thesis:*
Level dc:type.qualificationlevel
PhD
Grantor dc:publisher.institution
University of Glasgow
Year dc:date.issued
1997

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Menzies, Lindsey

Rights

Language dc:language
en

Chain of custody

source
Harvested from
University of Glasgow
Base URL
theses.gla.ac.uk/cgi/oai2
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Menzies, Lindsey. Jigsaws and Faster Fractal Pictures. PhD thesis, University of Glasgow, 1997.