En matemáticas , los sistemas de funciones iteradas ( IFS ) son un método para construir fractales ; los fractales resultantes son a menudo auto-similares . Los fractales IFS están más relacionados con la teoría de conjuntos que con la geometría fractal. [1] Fueron introducidos en 1981.
Los fractales IFS , como se les llama normalmente, pueden tener cualquier número de dimensiones, pero normalmente se calculan y dibujan en 2D. El fractal se compone de la unión de varias copias de sí mismo, siendo cada copia transformada por una función (de ahí "sistema de funciones"). El ejemplo canónico es el triángulo de Sierpiński . Las funciones son normalmente contractivas , lo que significa que acercan los puntos y hacen que las formas sean más pequeñas. Por lo tanto, la forma de un fractal IFS se compone de varias copias más pequeñas posiblemente superpuestas de sí mismo, cada una de las cuales también está formada por copias de sí mismo, ad infinitum . Esta es la fuente de su naturaleza fractal auto-similar.
Definición
Formalmente, un sistema de funciones iteradas es un conjunto finito de asignaciones de contracciones en un espacio métrico completo . [2] Simbólicamente,
es un sistema de funciones iteradas si cada es una contracción en el espacio métrico completo .
Propiedades
Hutchinson (1981) demostró que, para el espacio métrico , o más en general, para un espacio métrico completo , dicho sistema de funciones tiene un conjunto fijo S único compacto no vacío (cerrado y acotado) . Una forma de construir un conjunto fijo es comenzar con un conjunto inicial no vacío cerrado y acotado S 0 e iterar las acciones de f i , tomando S n +1 como la unión de las imágenes de S n bajo f i ; luego tomando S como el cierre de la unión de los S n . Simbólicamente, el conjunto único fijo (compacto no vacío) tiene la propiedad
El conjunto S es, por tanto, el conjunto fijo del operador Hutchinson. definido para vía
La existencia y unicidad de S es una consecuencia del principio de mapeo de contracciones , al igual que el hecho de que
para cualquier conjunto compacto no vacío en . (Para IFS contractivo, esta convergencia tiene lugar incluso para cualquier conjunto acotado cerrado no vacío). Los elementos aleatorios arbitrariamente cercanos a S pueden obtenerse mediante el "juego del caos", que se describe a continuación.
Recientemente se demostró que los IFS de tipo no contractivo (es decir, compuestos por mapas que no son contracciones con respecto a ninguna métrica topológicamente equivalente en X ) pueden producir atractores. Estos surgen naturalmente en espacios proyectivos, aunque también se puede adaptar la rotación irracional clásica en el círculo. [3]
La colección de funciones genera un monoide bajo composición . Si solo hay dos de tales funciones, el monoide puede visualizarse como un árbol binario , donde, en cada nodo del árbol, uno puede componer con una función u otra ( es decir, tomar la rama izquierda o derecha). En general, si hay k funciones, entonces se puede visualizar el monoide como un árbol k -ary completo , también conocido como árbol de Cayley .
Construcciones
A veces cada función se requiere que sea una transformación lineal , o más generalmente una afín , y por lo tanto representada por una matriz . Sin embargo, los IFS también se pueden construir a partir de funciones no lineales, incluidas las transformaciones proyectivas y las transformaciones de Möbius . La llama fractal es un ejemplo de IFS con funciones no lineales.
El algoritmo más común para calcular fractales IFS se llama " juego del caos ". Consiste en elegir un punto aleatorio en el plano, luego aplicar iterativamente una de las funciones elegidas al azar del sistema de funciones para transformar el punto y obtener el siguiente punto. Un algoritmo alternativo es generar cada secuencia posible de funciones hasta una longitud máxima dada, y luego trazar los resultados de aplicar cada una de estas secuencias de funciones a un punto o forma inicial.
Cada uno de estos algoritmos proporciona una construcción global que genera puntos distribuidos en todo el fractal. Si se dibuja un área pequeña del fractal, muchos de estos puntos quedarán fuera de los límites de la pantalla. Esto hace que hacer zoom en una construcción IFS dibujada de esta manera no sea práctico.
Aunque la teoría de IFS requiere que cada función sea contractiva, en la práctica el software que implementa IFS solo requiere que todo el sistema sea contractivo en promedio. [4]
Sistemas de funciones iteradas particionadas
Los PIFS (sistemas de funciones iteradas particionadas), también llamados sistemas de funciones iteradas locales, [5] brindan una compresión de imagen sorprendentemente buena, incluso para fotografías que no parecen tener los tipos de estructura auto-similar que muestran los fractales IFS simples. [6]
El problema inverso
Existen algoritmos muy rápidos para generar una imagen a partir de un conjunto de parámetros IFS o PIFS. Es más rápido y requiere mucho menos espacio de almacenamiento para almacenar una descripción de cómo se creó, transmitir esa descripción a un dispositivo de destino y regenerar esa imagen de nuevo en el dispositivo de destino, que almacenar y transmitir el color de cada píxel en la imagen. . [5]
El problema inverso es más difícil: dada alguna imagen digital arbitraria original, como una fotografía digital, intente encontrar un conjunto de parámetros IFS que, cuando se evalúen por iteración, produzcan otra imagen visualmente similar a la original. En 1989, Arnaud Jacquin presentó una solución a una forma restringida del problema inverso utilizando solo PIFS; la forma general del problema inverso sigue sin resolverse. [7] [8] [5]
A partir de 1995, todo el software de compresión fractal se basa en el enfoque de Jacquin. [8]
Ejemplos de
El diagrama muestra la construcción de un IFS a partir de dos funciones afines. Las funciones están representadas por su efecto en el cuadrado de dos unidades (la función transforma el cuadrado delineado en el cuadrado sombreado). La combinación de las dos funciones forma el operador Hutchinson . Se muestran tres iteraciones del operador, y luego la imagen final es del punto fijo, el fractal final.
Los primeros ejemplos de fractales que pueden ser generados por un IFS incluyen el conjunto de Cantor , descrito por primera vez en 1884; y curvas de Rham , un tipo de curva auto-similar descrita por Georges de Rham en 1957.
Historia
Los IFS fueron concebidos en su forma actual por John E. Hutchinson en 1981 [9] y popularizados por el libro de Michael Barnsley Fractals Everywhere .
Los IFS proporcionan modelos para ciertas plantas, hojas y helechos, en virtud de la auto-similitud que a menudo ocurre en las estructuras ramificadas en la naturaleza.
- Michael Barnsley y col. [10]
Ver también
- Sistema de base compleja
- Teorema del collage
- Composiciones infinitas de funciones analíticas
- Sistema L
- Compresión fractal
Notas
- ^ Zobrist, George Winston; Chaman Sabharwal (1992). Progreso en gráficos por computadora: Volumen 1 . Libros de intelecto. pag. 135. ISBN 9780893916510. Consultado el 7 de mayo de 2017 .
- ^ Michael Barnsley (1988). Fractales en todas partes , p.82. Prensa académica, Inc. ISBN 9780120790623 .
- ^ M. Barnsley, A. Vince, El juego del caos en un sistema general de funciones iteradas
- ^ Draves, Scott ; Erik Reckase (julio de 2007). "El algoritmo de la llama fractal" (PDF) . Archivado desde el original (pdf) el 9 de mayo de 2008 . Consultado el 17 de julio de 2008 .
- ^ a b c Bruno Lacroix. "Compresión de imagen fractal" . 1998.
- ^ Fischer, Yuval (12 de agosto de 1992). Przemyslaw Prusinkiewicz (ed.). Notas del curso SIGGRAPH'92 - Compresión de imágenes fractal (PDF) . SIGGRAPH . Fractales: del arte popular a la hiperrealidad. ACM SIGGRAPH .
- ^ Dietmar Saupe, Raouf Hamzaoui. "Una revisión de la literatura de compresión de imágenes fractal" .
- ^ a b John Kominek. "Algoritmo para la compresión rápida de imágenes fractal" . doi : 10.1117 / 12.206368 .
- ^ Hutchinson, John E. (1981). "Fractales y auto semejanza" (PDF) . Indiana Univ. Matemáticas. J . 30 (5): 713–747. doi : 10.1512 / iumj.1981.30.30055 .
- ^ Michael Barnsley , et al. , "Fractales y superfractales V-variable" (PDF) . (2,22 MB)
Referencias
- Draves, Scott ; Erik Reckase (julio de 2007). "El algoritmo de la llama fractal" (PDF) . Archivado desde el original (pdf) el 9 de mayo de 2008 . Consultado el 17 de julio de 2008 .
- Falconer, Kenneth (1990). Geometría fractal: fundamentos y aplicaciones matemáticas . John Wiley e hijos. págs. 113-117, 136 . ISBN 0-471-92287-0.
- Barnsley, Michael ; Andrew Vince (2011). "El juego del caos en un sistema general de funciones iteradas". Teoría Ergódica Dynam. Sistemas . 31 (4): 1073–1079. arXiv : 1005.0322 . Código Bibliográfico : 2010arXiv1005.0322B .
- Para una descripción histórica y la generalización:David, Claire (2019). "propiedades fractales de funciones de tipo Weierstrass" . Actas del Centro Internacional de Geometría . 12 (2): 43–61.