Coding of fractal binary images with contractive set mappings composed of affine transformations

Sammanfattning: There are several efficient algorithms by which one can generate approximations of binaryattractors induced from contractive set mappings which are composed of affine mappings.There are also complex attractors resembling natural-looking images where the attractors areinduced from only a few affine mappings which can be represented with a few bits. Thus it ismore efficient to store and transmit the affine mappings than the image itself. For set mappingsto be useful for image coding, it is also necessary to have an algorithm which can finda set mapping that defines an attractor image which is close to the given image.In the present thesis, we will describe and analyse two algorithms for this problem, usuallycalled an inverse problem. One algorithm is based on a full search through the parameterspace of the affine mappings. The other is based on a gradient search in the parameter spaceof the affine mappings where the gradient is obtained by the Kantorovich metric. Wedescribe some variants of these attractor coding methods and compare them with non-fractalcoding methods for binary images.We have found that the gradient search algorithm can be used to improve a good initialsolution. A disadvantage of this algorithm is that the number of mappings must be given.Thus, it is less suitable for encoding images. The full search algorithm with its variants canbe used to encode binary images. It also has an inverse property regarding the number of affinemappings, which means that if the given image was generated by a set mapping, thenunder some conditions the algorithm can recover the mappings that generated the givenimage.The Kantorovich distance has a high computational complexity and takes considerabletime to compute even for small images. We have implemented two algorithms with somevariants for the computation of the distance and compared them. We found that they can beused to compute the distance between images.The underlying notion behind the attractor-based techniques described here is that usinga larger parameter space for the affine mappings in the spatial domain should give a betterimage coding in a rate distortion sense. We have also made some experiments on grey scaleimages along this line of thought.