Movimiento browniano fraccional

Introduccion

fBM significa movimiento fraccional browniano (movimiento fraccional browniano). Pero antes de comenzar a hablar sobre la naturaleza, los fractales y los relieves procesales, profundicemos en la teoría por un momento.

El movimiento browniano (BM), simplemente, sin "fragmentación" es un movimiento en el que la posición de un objeto cambia con incrementos aleatorios a lo largo del tiempo (imagine la position+=white_noise(); secuencia position+=white_noise(); ). Desde un punto de vista formal, BM es una integral del ruido blanco. Estos movimientos definen caminos que son aleatorios pero (estadísticamente) autosimilares, es decir Una imagen aproximada del camino se asemeja a todo el camino. El movimiento browniano fraccional es un proceso similar en el que los incrementos no son completamente independientes entre sí, y hay algún tipo de memoria en este proceso. Si la memoria tiene una correlación positiva, los cambios en una dirección dada tenderán a cambios futuros en la misma dirección, y la ruta será más suave que con BM normal. Si la memoria tiene una correlación negativa, un cambio en la dirección positiva con una alta probabilidad será seguido por un cambio en la negativa, y la ruta será mucho más aleatoria. El parámetro que controla el comportamiento de la memoria o la integración y, por lo tanto, la auto-similitud, su dimensión fractal y espectro de potencia, se llama exponente de Hurst y generalmente se reduce a H. Desde un punto de vista matemático, H nos permite integrar el ruido blanco solo parcialmente (digamos, solo 1/3 de integración , de ahí la "fragmentación" en el nombre) para crear fBM para cualquier característica y apariencia de memoria deseada. H toma valores en el rango de 0 a 1, que describen, respectivamente, un fBM grueso y liso, y el BM habitual se obtiene en H = 1/2.


Aquí la función fBM () se usa para generar topografía, nubes, distribución de árboles, sus variaciones de color y detalles de copa. "Rainforest", 2016: https://www.shadertoy.com/view/4ttSWf

Todo esto es muy teórico, y en gráficos de computadora, fBM se genera de una manera completamente diferente, pero quería explicar la teoría, porque es importante recordarlo incluso cuando crea los gráficos. Veamos cómo se hace esto en la práctica:

Como sabemos, las estructuras auto-similares, que son aleatorias al mismo tiempo, son muy útiles para modelar procedimientos de todo tipo de fenómenos naturales, desde nubes hasta montañas y texturas de corteza de árbol . Es intuitivamente claro que las figuras en la naturaleza se pueden descomponer en varias figuras grandes que describen la forma en su conjunto, un mayor número de figuras de tamaño mediano que distorsionan el contorno principal o la superficie de la figura original, y un número aún mayor de figuras pequeñas que agregan detalles al contorno y la forma de las dos anteriores. Tal forma incremental de agregar detalles a un objeto, brindándonos una manera simple de limitar los límites de los rangos de frecuencia para cambiar LOD (Nivel de detalle, niveles de detalle) y formas de filtrado / suavizado, hace que sea fácil escribir código y crear resultados visualmente hermosos. Por lo tanto, es ampliamente utilizado en películas y juegos. Sin embargo, no creo que fBM sea bien entendido por todo el mecanismo. En este artículo, describiré cómo funciona y cómo se utilizan sus diversas características espectrales y visuales para varios valores de su parámetro principal H, y complementaré todo esto con experimentos y mediciones.

Idea básica

Por lo general (hay muchas formas), los fBM se construyen llamando a la aleatoriedad determinista y suavizada utilizando la función de ruido seleccionada por el desarrollador ( valor , gradiente , celular , Voronoi , trigonométrico, simple , ..., etc., la opción elegida no es muy importante aquí), seguido por la construcción de la auto-similitud. Los fBM se implementan comenzando con la señal de ruido base, agregando gradualmente llamadas de ruido detalladas cada vez más pequeñas. Algo como esto:

 float fbm( in vecN x, in float H ) { float t = 0.0; for( int i=0; i<numOctaves; i++ ) { float f = pow( 2.0, float(i) ); float a = pow( f, -H ); t += a*noise(f*x); } return t; } 

Esto es fBM en su forma más pura. Cada ruido de señal (u "onda") (), para el que tenemos "numOctaves", se combina de forma aditiva con una suma intermedia, pero se comprime horizontalmente por la mitad, lo que esencialmente reduce a la mitad su longitud de onda, y su amplitud disminuye exponencialmente Tal acumulación de ondas con una disminución coordinada en la longitud de onda y amplitud crea la auto-similitud que observamos en la naturaleza. En última instancia, en cualquier espacio dado hay espacio para solo unos pocos cambios grandes, pero hay mucho espacio para cambios cada vez más pequeños. Suena bastante razonable. De hecho, tales manifestaciones de la ley del poder se encuentran en todas partes en la naturaleza.

Lo primero que puede notar es que el código que se muestra arriba no es muy similar a la mayoría de las implementaciones de fBM que puede ver en Shadertoy y otros ejemplos de código. El siguiente código es similar al que se muestra arriba, pero mucho más popular, ya que prescinde de las costosas funciones de pow ():

 float fbm( in vecN x, in float H ) { float G = exp2(-H); float f = 1.0; float a = 1.0; float t = 0.0; for( int i=0; i<numOctaves; i++ ) { t += a*noise(f*x); f *= 2.0; a *= G; } return t; } 

Entonces, comencemos hablando de numOctaves. Dado que la longitud de onda de cada ruido es dos veces menor que la anterior (y la frecuencia es dos veces mayor), la designación de lo que debería llamarse "frecuencias numéricas" se reemplaza por "numOctavas" como referencia a un concepto musical: dividir una octava entre dos notas corresponde duplicando la frecuencia de la nota base. Además, se puede crear fBM incrementando la frecuencia de cada ruido en una cantidad diferente de las dos. En este caso, el término "octava" ya no será técnicamente correcto, pero todavía se usa. En algunos casos, incluso puede ser necesario crear ondas / ruido con frecuencias que aumentan con un coeficiente lineal constante, y no geométricamente, por ejemplo, FFT (transformación rápida de Fourier; en realidad se puede usar para generar fBMs periódicas (), útil para crear texturas océano) Pero, como veremos más adelante, la mayoría de las funciones básicas del ruido () pueden aumentar las frecuencias en magnitudes que son múltiplos de dos, es decir, necesitamos muy pocas iteraciones, y fBM seguirá siendo hermoso. De hecho, sintetizar fBM una octava a la vez nos permite ser muy efectivos; por ejemplo, en solo 24 octavas / iteración, puede crear fBM que cubre todo el planeta Tierra con detalles de 2 metros. Si haces esto usando frecuencias linealmente crecientes, entonces tomará varias órdenes de magnitud más iteraciones.

La última nota sobre la secuencia de frecuencias: si nos movemos de f _i = 2 ⁱ a f _i = 2⋅f _i-1 , esto nos dará cierta flexibilidad con respecto a duplicar las frecuencias (o reducir a la mitad las longitudes de onda): podemos ampliar fácilmente el ciclo y cambie cada octava, por ejemplo, reemplazando 2.0 por 2.01, 1.99 y otros valores similares para que los ceros y picos acumulados de diferentes ondas de ruido no se superpongan exactamente, lo que a veces crea patrones poco realistas. En el caso de 2D-fBM, también puede girar ligeramente el área de definición.

Entonces, en la nueva implementación de software de fBM (), no solo reemplazamos la generación de frecuencia de una formulación de ley de potencia con un proceso iterativo, sino que también cambiamos la amplitud exponencial (ley de potencia) por series geométricas controladas por el indicador de "ganancia" G. Es necesario realizar una transformación desde H a G, calculando G = 2 ^-H , que puede deducirse fácilmente de la primera versión del código. Sin embargo, con mayor frecuencia los programadores gráficos ignoran el exponente de Hurst H, o ni siquiera lo saben, y trabajan directamente con los valores de G. Dado que sabemos que H varía en el rango de 0 a 1, entonces G varía de 1 a 0.5. De hecho, la mayoría de los programadores establecen un valor constante de G = 0.5 en sus implementaciones de fBM. Este código no será tan flexible como usar la variable G, pero hay buenas razones para ello, y pronto lo descubriremos.

Auto-similitud

Como se mencionó anteriormente, el parámetro H determina la autosimilitud de la curva. Por supuesto, esto es auto-similitud estadística. Es decir, en el caso del fBM unidimensional (), si acercamos la cámara horizontalmente al gráfico por U, entonces, ¿cuánto necesitamos acercarnos al gráfico verticalmente por V para obtener una curva que se vea igual? Bueno, como a = f ^-H , entonces a⋅V = (f⋅U) ^-H = f ^-H ⋅U ^-H = a⋅U ^-H , es decir, V = U ^-H . Entonces, si acercamos la cámara a fBM con un indicador horizontal de 2, entonces verticalmente necesitamos cambiar la escala a 2 ^-H . Pero 2 ^-H es G! Y esto no es una coincidencia: cuando se usa G para escalar amplitudes de ruido, nosotros, por definición, construimos autosimilitud fBM con un factor de escala G = 2 ^-H .


El movimiento browniano (H = 1/2) y el zoom anisotrópico se muestran a la izquierda. A la derecha está fBM (H = 1) y zoom isotrópico.

Código: https://www.shadertoy.com/view/WsV3zz

¿Qué pasa con las montañas procesales? El movimiento browniano estándar tiene un valor de H = 1/2, lo que nos da G = 0.707107 ... A estos valores, se genera una curva que, cuando se amplía, se ve exactamente igual si se escala anisotrópicamente a lo largo de X e Y (si es una curva unidimensional). Y de hecho: para cada factor de zoom horizontal U, necesitamos escalar la curva verticalmente por V = sqrt (U), lo cual no es muy natural. Sin embargo, los gráficos de las bolsas de valores a menudo se acercan a H = 1/2, porque en teoría, cada incremento o disminución del valor de las acciones no depende de cambios anteriores (no olvide que BM es un proceso sin memoria). Por supuesto, en la práctica, ciertas dependencias están presentes, y estas curvas están más cerca de H = 0.6.

Pero el proceso natural contiene más "memoria" en sí mismo, y la autosimilitud en él es mucho más isotrópico. Por ejemplo, una montaña más alta es más ancha en su base en la misma cantidad, es decir las montañas generalmente no se estiran y no se vuelven más delgadas. Por lo tanto, esto nos hace comprender que para las montañas G debería ser 1/2, el mismo zoom horizontal y vertical. Esto corresponde a H = 1, es decir, los perfiles de montaña deberían ser más suaves que la curva de la bolsa de valores. De hecho, lo es, y un poco más tarde mediremos perfiles reales para confirmar esto. Pero por experiencia sabemos que G = 0.5 crea hermosos relieves fractales y nubes, por lo que G = 0.5 es el valor G más popular para todas las implementaciones de fbm.

Pero ahora tenemos una comprensión más profunda de H, G y fBM en general. Sabemos que si el valor de G está más cerca de 1, entonces fBM será aún más loco que el BM puro. Y de hecho: para G = 1, que corresponde a H = 0, obtenemos el fBM más ruidoso de todos.

Todas estas funciones fBM parametrizadas se denominan, por ejemplo, "ruido rosa" en H = 0, G = 1 o "ruido marrón" en H = 1/2, G = sqrt (2), que se heredan del campo de procesamiento de señal digital (Digital Procesamiento de señal) y son bien conocidos por las personas con problemas de sueño. Profundicemos en el DSP y calculemos las características espectrales para obtener una comprensión más profunda de fBM.

Perspectiva de procesamiento de señal

Si piensa en el análisis de Fourier o la síntesis de sonido aditiva, la implementación de fBM () que se muestra arriba es similar a la Transformada inversa de Fourier, que es discreta como la transformada discreta de Fourier (DFT), pero muy escasa y utiliza una base diferente función (esencialmente muy diferente de IFT, pero déjame explicarte). De hecho, podemos generar fBM (), gráficos de computadora e incluso superficies oceánicas usando IFFT, pero esto se está convirtiendo rápidamente en un proyecto muy costoso. La razón es que IFFT no combina aditivamente ondas de ruido, sino sinusoides, pero los sinusoides no llenan muy eficientemente el espectro de potencia de energía, porque cada sinusoide afecta una frecuencia. Sin embargo, las funciones de ruido tienen espectros amplios que cubren largos intervalos de frecuencia con una sola onda. Tanto el ruido de gradiente como el ruido de valor tienen gráficos tan ricos y densos de densidad espectral. Echa un vistazo a los gráficos:


Onda sinusoidal


Ruido de valor


Ruido de gradiente
Tenga en cuenta que en el espectro de ruido de valor y ruido de gradiente, la mayor parte de la energía se concentra en las frecuencias más bajas, pero es más amplia, una opción ideal para llenar rápidamente todo el espectro con varias copias offset y escaladas. Otro problema de la onda sinusoidal fBM es este. que, por supuesto, genera pattenes repetidos, que a menudo son indeseables, aunque pueden ser útiles para generar texturas sin costuras. La ventaja de fBM () basado en sin () es que es superproductivo, porque las funciones trigonométricas se realizan en hierro mucho más rápido que el ruido de construcción usando polinomios y hash / lut, por lo que a veces vale la pena usar fBM basado en ondas sinusoidales de consideraciones de rendimiento, incluso si se crean paisajes pobres.

Ahora echemos un vistazo a las gráficas de la densidad de espectros para fBM con diferentes valores de H. Preste especial atención a las marcas en el eje vertical, porque las tres gráficas están normalizadas y no describen las mismas pendientes, aunque a primera vista se ven casi iguales. Si denotamos la pendiente negativa de estos gráficos espectrales como "B", entonces dado que estos gráficos tienen una escala logarítmica, el espectro seguirá una ley de potencia de la forma f- ^B . En esta prueba, utilizo 10 octavas de ruido de gradiente normal para construir el fBM que se muestra a continuación.


G = 1.0 (H = 0)


G = 0.707 (H = 1/2)


G = 0.5 (H = 1)

Como vemos, la energía fBM con H = 0 (G = 1) se atenúa a 3 dB por octava, o, de hecho, tiene un valor hacia atrás de la frecuencia. Esta es una ley de potencia f ^-1 (B = 1), que se llama "ruido rosa" y suena como lluvia.

fBM () con H = 1/2 (G = 0.707) genera un espectro que se atenúa más rápido, a 6 dB por octava, es decir, tiene menos frecuencias altas. En realidad, suena más profundo, como si estuviera escuchando lluvia, pero esta vez desde su habitación con las ventanas cerradas. La atenuación de 6 dB / octava significa que la energía es proporcional a f ^-2 (B = 2), y esto es realmente una característica del movimiento browniano en el DSP.

Finalmente, nuestro fBM favorito de gráficos de computadora con H = 1 (G = 0.5) genera un gráfico de densidad espectral con una disminución de 9 dB / octava, es decir, la energía es inversamente proporcional al cubo de frecuencia (f ^-3 , B = 3). Esta es una señal con una frecuencia constantemente baja, que corresponde a un proceso con memoria de correlación positiva, del que hablamos al principio. Este tipo de señal no tiene su propio nombre, por lo que tengo la tentación de llamarlo "ruido amarillo" (simplemente porque este nombre ya no se usa para nada). Como sabemos, es isotrópico, lo que significa que modela muchas formas naturales que se repiten.

De hecho, confirmaré mis palabras sobre la similitud con la naturaleza haciendo las mediciones que se dan en la siguiente sección del artículo.

Titulo	H	G = 2 -H	B = 2H + 1	dB / oct	Sonido
Azul	-	-	+1	+3	Rociar agua. Enlace
Blanco	-	-	0 0	0 0	Viento en las hojas. Enlace
Rosa	0 0	1	-1	-3	La lluvia Enlace
Marrón	1/2	sqrt (2)	-2	-6	Rain escuchó desde su casa. Enlace
Amarillo	1	1/2	-3	-9	Motor detrás de la puerta

Medidas

Primero debo advertirte que será un experimento muy poco científico, pero aún quiero compartirlo. Tomé fotografías de cadenas montañosas paralelas al plano de la imagen para evitar la distorsión de la perspectiva. Luego dividí las imágenes en blanco y negro, y luego convertí la superficie de contacto del cielo y las montañas en una señal 1D. Luego lo interpreté como un archivo de sonido WAV y calculé su gráfico de frecuencia, como es el caso de las señales sintéticas fBM () que analicé anteriormente. Seleccioné imágenes con una resolución suficientemente alta para que el algoritmo FFT tuviera datos significativos para el trabajo.


Fuente: Reportero griego


Fuente: Wikipedia







Parece que los resultados realmente indican que los perfiles de montaña siguen una distribución de frecuencia de -9 dB / octava, que corresponde a B = -3 o H = 1 o G = 0.5 o, en otras palabras, al ruido amarillo.

Por supuesto, el experimento no fue riguroso, pero confirma nuestra comprensión intuitiva y lo que ya sabemos por experiencia y trabajo con gráficos por computadora. ¡Pero espero que ahora hayamos comenzado a entender esto mejor!