Research And Implementation Of Fractal Binary Image Compression Based On Genetic Algorithm

Generally speaking, Image compression or Data Compression is a problem of optimization. And under the condition of satisfying a certain limit, the target of compression is to acquire the simplest description of the image or data. Now Fractal image compression has been a popular technique for very high compression ratios. In this paper, Fractal image compression algorithm is based on the fractal theory of self-similar and self-affine transformation and the kernel theory of Iterated Function System. The main idea is to find one more effective IFS which consists of contraction affine transformations. Moreover, Using the IFS can reconstruct any scale of image which is very similar to the original image.However, finding the IFS belongs to NP-hard problem. Under complicated constraints, it is hardly to obtain its best result in such huge researching space by traditional search methods. Therefore, in this paper, importing Genetic algorithm (GA) which has been applied successfully to deal with this problem, we present a better approach to compress a binary image by using Iterated Function System and Genetic Algorithm. Genetic Algorithm simulates natural evolutionary processes, though retaining a population of candidate solution sets to search multi-direction. The evolution and reproduction of population is comply with selecting the superior and eliminate the inferior, therefore, searching can be directed to the potential most result in the extensible search space.The paper starts by introducing the basic theory of Iterated Function System and Genetic Algorithm. Then the theory of the fractal image compression and the implementation method are elaborated based on the idea of Genetic Algorithm and IFS, including fractal image mathematic model, chromosome encoding, evaluation of chromosome, selection strategy, designed of genetic operations, decoding reconstruction of image. The variable-length chromosome encoding and the extensible search space were proposed in this paper. The algorithm performance and efficiency have been improved greatly by introducing multi-object fitness functions, manifold crossover operators and mutation operators. The experiment results showthat our algorithm has tremendous ability in searching best solutions, and can find out one of the most approximate result of IFS whose decoding image is quite similar with original one and also has high image quality.Genetic Algorithm itself has the immanent parallel mechanism, so it has the possibility of parallel compute on a large scale. This paper implemented a simple distributed GA based on distributed environment, according to the existent framework. And then, the paper explained its idea to design a parallel Genetic Algorithm about based on the distributed system. The realization of this blueprint will be the next focal point.Finally, this paper summarizes for this whole thesis. And then the further research is discussed.