This dissertation presents a study on fractal image coding. The fractal image coding exploits the redundancies, using the self-similarity in images themselves. In other words, the compression is accomplished as a transformation to generate the attractor close to an original Image, instead of the original image, is transmitted to receiver. Since jacquin first proposed the automated fractal coding in 1989, many researchers have improved its performance. It is exptected that this dissertation makes a contribution to improvement of encoding and decoding performance. This dissertation is composed of 3 parts.
First, we introduce a method to improve the encoding performance using the reference images which is determined by some criteria described in the chapter 3. As the image quality in the fractal coding is determined by the distance between an original image and the attractor generated by a transformation, it is important to obtain the transformation generating the attractor close to the original image as long as possible. Therefore we can define the optimal transformation as a transformation to minimize the distance. However, we have a difficulty in finding the optimal transformation due to too heavy computation, which causes that it is impossible to obtain the transformation. Thus, the conventional fractal coding schemes just limit the upper bound of the distance between an original image and an attractor, minimizing the distance between the original image and its collage image instead of the attractor. Thus the schemes take a disadvantage that the bound is not tight. Moreover, the schemes give unique transformation in encoding. Compared with the schemes, the proposed scheme gives various transformations which are obtained using the reference images satisfying some criteria. Finally, we choose one of them that generates the attractor closest to the original image. The performance of the proposed scheme is analyzed showing the upper bound of the distance between an original image and an attractor obtained by the proposed scheme, and then experimentally evaluated. In a simple case that the optimal transformation is practically available, the proposed scheme is evaluated as to how close to the optimal scheme. Besides, the proposed scheme is evaluated in general cases that the optimal transformation is unavailable.
Second, an object-based fractal coding is discussed. Considering that objects have arbitrary shapes, the conventional schemes can be applied to an object coding as they are. That is, an object is partitioned to non-overlapped blocks, and then each block is coded by the conventional schemes. The partitioned blocks are classified into boundary blocks and internal blocks by the shapes and the positions of the blocks. Thus the proposed object-based coding scheme is composed of the coding of the internal blocks and the boundary blocks. As the internal blocks can be coded by the conventional schemes without modification, we focus on the coding of the boundary blocks, considering the characteristics of the boundary blocks distinct from the internal blocks. Thus we propose the coding schemes for the boundary blocks and analyze their performance.
Finally, the minimal iteration decoding algorithm (mida) for fast decoding is described. Decoding requires many iterations as the fractal coding is based on ifs (iterative function system), while encoding is done once although encoding requires much computation. Thus it is important to reduce the number of iterations in real-time applications. The mida is an algorithm to minimize the number of iterations when the transformation parameters for an image are given. We analytically show that the mida has the minimal number of iterations and experimentally verify the analytic results. Resultantly, the mida reduces the number of iterations by about 2 times.
