Fractal-based techniques and their applications

Abstract

The aim of this research is to develop efficient algorithms for fractal image coding, which can be applied in digital image compression, image magnification and image denoising. Fractal image coding can provide a highly reconstructed image quality with a high compression ratio, is independent of resolution, and has a fast decoding process. The problem with fractal coding is its high computational complexity in the encoding process. Most of the encoding time is spent on finding the best-matched domain block from a large domain pool to represent an input range block with respect to contrast and intensity offset, as well as the isometric transformations. The objectives of this research are to investigate and develop efficient techniques for fractal image coding, fractal-based image magnification and denoising. In this thesis, four efficient fractal image coding algorithms have been proposed. The first algorithm is based on new feature vectors and the property of zero contrast. The proposed feature vectors can provide a better representation of image blocks, and thus result in a more efficient search of the domain block using the k-d tree scheme. The second algorithm is an efficient windowing scheme for fractal image coding based on the local variances method. In this method, windows covering those domain blocks whose variances are higher than that of the range block are considered according to a mathematical model. The exhaustive search algorithm can obtain the optimal result by searching all the blocks within the domain pool, but this process requires a high computational cost, which limits its practical application. A single kick-out condition is proposed which can avoid a large number of range-domain block matches when finding the best-matched domain block. An efficient method for zero contrast prediction is also proposed, which can determine whether the contrast factor for a domain block is zero or not, and compute the corresponding difference between the range block and the transformed domain block efficiently and exactly. The fourth method is another fast full search fractal image-coding algorithm, which uses the angle between an input range block and a reference domain block to determine a tighter decision boundary for eliminating the searching space in the domain pool. The encoding time can be further decreased when more reference domain vectors are used. These efficient algorithms have been further investigated to extend their applicability to image magnification and denoising. In this thesis, an efficient image-magnification algorithm based on the Iterated Function System (IFS) is proposed. This IFS-based image-magnification method employs the self-similarity property instead of the conventional interpolation approach. This self-similarity makes it possible to generate images of higher resolution. To further improve the quality of the high-resolution images, the error image or residual errors are considered. In addition, our algorithm can combine with other magnification algorithms. We have also derived a new fractal-based image denoising method, which employs the decoupling property of the fractal code instead of the conventional fractal coding using the contrast scaling and offset parameters. In order to improve the visual quality of a denoised image, a range-block partitioning scheme is used to generate a set of overlapping sub-images. These sub-images are then averaged to produce an optimal denoised image.