Finding an iterated function systems based representation for complex visual structures using an evolutionary algorithm

• Autorzy: Bielecki A. , Strug B.
• Języki publikacji: EN

Abstrakty

EN

This paper presents an approach to the IFS inverse problem based on evolutionary computations. Having a bitmap image, we look for a set of functions that can reproduce a good approximation of a given image. A method using a variable number of mappings is proposed. A number of different crossover operators is described and tested. The possibility of enriching evolutionary algorithms by a specific type mechanism characteristic for replication of influenza viruses is discussed. The genetic material of the influenza type A virus consists of eight separate segments. In some types of tasks, such a structure of a genome can be more adequate than representation that consists of one sequence only. If influenza virus strains infect the same cell, then their RNA segments can mix freely, producing progeny viruses which represents the reasortment mechanism. Furthermore, mistakes leading to new mutations are common. The structure of problems for which such viral reproduction mechanisms can be effective are analyzed. The paper ends with some experimental results showing the images we were able to generate with the proposed method. The preliminary experimental results suggest that the introduction of the reasortment operator results in achieving satisfactory images in a smaller number of generations.

Słowa kluczowe

EN

hierarchical evolutionary algorithms; image generation; iterated function systems inverse problem; viral replication; reasortment

• Wydawca: Institute of Information Technology of the Warsaw University of Life Sciences – SGGW
• Czasopismo: Machine Graphics and Vision
• Rocznik: 2007
• Tom: Vol. 16, No. 1/2
• Strony: 171--189
• Opis fizyczny: Bibliogr. 29 poz., il., wykr.

Twórcy

autor

Bielecki A.

autor

Strug B.

• Institute of Computer Science, Jagiellonian University, Nawojki 11, 30-072 Cracow, Poland,

Bibliografia

• [1] Fogel L., Owens A. J., Walsh M. J.: Artificial intelligence through simulated evolution. Wiley, New York 1966.
• [2] Hollstein R. B.: Artifictal genetic adaptation in computer control systems. Ph.D. Thesis, Ann Arbor, MI: The University of Michigan, 1971.
• [3] Holland J. H.: Adaptation in natural and artificial systems, Ann Arbor: University of Michigan Press, 1975.
• [4] Hutchinson J. E.: Fractals and self-similarity. Indiana Univ. Math. J., vol. 30, 713-747, 1981.
• [5] Dekking F. M.: Recurrent sets. Adv. Math., vol. 44, 78-104, 1982.
• [6] Mandelbrot B.: The fractal geometry of nature. Freeman, San Francisco, 1982.
• [7] Barnsley M. F., Demko S. G.: Iterated function schemes and the global construction of fractals. Proc. R. Soc. A, vol. 399, 243-275, 1985.
• [8] Peitgen H.O., Richter P. H.: The beauty of fractals. Springer Verlag, Berlin, 1986.
• [9] Barnsley M. F., Sloan A. D.: A better way to compress images. Byte, vol. 13, 215-233, 1988.
• [10] Barnsley M. F.: Fractals everywhere, Academic Press, 1988.
• [11] Goldberg D. E.: Genetic algorithms in search, Optimization and Machine Learning, Reading, MA, Addison-Wesley, 1989.
• [12] DeJong K. A.: Genetic algorithm based learning. Machine Learning An Artificial Intelligence Approach, 611-638, Morgan Kaufmann, San Mateo, CA , 1990.
• [13] Falcone K.: Fractal geometry: Mathematical Foundations and Applications, Wiley, 1990.
• [14] Giles P. A.: Iterated function systems and shape representation. PhD thesis, University of Durham, UK, 1990.
• [15] Peitgen H. O., Saupe D.: The science of fractal images, Springer Verlag, Berlin, 1990.
• [16] Hoskins D. E., Vagners J.: Image compression using Iterated Function Systems and Evolutionary Programming: Image compression without image metrics. In Proceedings of the 26th Asilomar Conference on Signals, Systems and Computers, 1992.
• [17] Kudrewicz J.: Fractals and Chaos. WNT, Warszawa, (in Polish), 1993.
• [18] Vences L., Rudomin I.: Fractal compression of single images and image sequences using genetic algorithms. Manuscript, Institute of Technology, University of Monterrey, available from ftp://ftp.informatik.uni-freiburg.de/papers/fractal/VeRu94.ps.gz., 1994.
• [19] Michalewicz Z.: Genetic Algorithms + Data Structures: Evolution programs. Springer, Berlin, 1996.
• [20] Pierrot H. J., Hinterding R: Using multichromosomes to solve a simple mixed integer problem. In Australian Joint Conference on Artificial Intelligence, Lecture Notes in Artificial Intelligence, vol. 1342, 137-146, 1997.
• [21] Michalewicz Z. Fogel D. B.: How to Solve It: Modern heuristics. Springer, 2000.
• [22] Schaefer R.: Foundations of global genetic optimization, UJ, Krakow, (in Polish), 2002.
• [23] Mayer H. A., Spitzlinger M.: Multi-chromosomal representation and chromosome Shuffling in Evolutionary Algorithm, Congress on Evolutionary Computations, 1145-1149, IEEE, 2003.
• [24] Schaefer R., Kołodziej J.: Genetic search reinforced by the population hierarchy in foundations of genetics algorithms 7, De Jong, K.A., Poli, R. , Rowe, J.E. - eds., pp 383-399, Morgan Kaufmann,2003 .
• [25] Bielecki A., Strug B.: An evolutionary algorithm for solving the inverse problem for iterated function systems for a two dimensional image. Advances in Soft Computing, Springer Verlag, Berlin pp 347-355, 2005.
• [26] Paszynska A.: An extension of Vose’s Markov chain model for genetic algorithms. Proc. of GECCO 2005 ACM, 1553-1554.
• [27] Taubenberger J. K., Reid A. H., Fanning T. G.: Capturing a killer flu virus. Scientific American, vol. 292, 62-71, 2005.
• [28] Bielecki A., Strug B.: A viral replication mechanism in evolutionary algorithms. Proc. of ICAISC 2006, IEEE Computational Intelligence Society, pp 175-180.
• [29] Bielecki A., Strug B.: Evolutionary approach to finding itarated function systems for a two dimensional image, in Computational Imaging and Vision, pp 512-520, Springer Verlag, Berlin, 2006.