Gray-scale Image Compression Based On Fractal Theory And Evolutionary Algorithm

With the developing of multimedia technology and computer communication, digital image which have enormous data quantity restricts image communication. Effective encoding technologies to obliterate redundance and retain the image quality are the focus of research. The possibility of compression is because of high self-similarity and self-transformability redundancy of images. In this dissertation, from theoretical and practice viewpoint, we present a novel approach to compress gray-scale images by using Fractals Theory and Evolutionary Algorithms. The kernel theory based on in this paper is called Iterated Function System(IFS). The main idea is to find an IFS which consists of a set of contractive affine transformations mainly based on fixed-point theorem and collage theorem, when they are applied on the original image, the union of the transformed images will cover up the original image. Decoding process starts from any images which can recur the original image by applying IFS. Therefore, coding file only stores IFS code, which can achieve high compression ratio.The purpose of fractal image compression is to gain a good IFS whose attractor is similar to original image. So this search problem can be viewed as a combination and optimization process with complicated constraints and a large searching space. Because traditional algorithm hardly handle with this problem, we adopt evolutionary algorithm to solve this problem which has the property of artificial intelligence technology. Evolutionary algorithm starts from initial population. The individuals of each population embed some new information while the searching can be directed to the promising area. The evolutive principle and the survival mechanism are applied in the algorithm. As a result, the best result can be fast achieved with high probability.The dissertation starts by explaining the basic notions of Iterative Function System and Evolutionary Algorithms. Then we go to details of the ideas of compression algorithms based on IFS theory, such as range block search, fixed threshold, adaptive threshold, linear classification, and so on. Lastly, an evolutionary algorithm is proposed for obtainment of matching domain blocks of fractal partition in image compression. It makes use of the partition iterated function system and fractal image compression. Chromosome representation, initialization of population, design of special genetic operators are introducedexplicitly. The algorithm is robust and optimal. Both theoretical analyses and experiments show that higher compression ratio and image quality can be achieved.