Jigsaws and Faster Fractal Pictures

[摘要] 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].

[发布机构] University:University of Glasgow

[关键词] Mathematics