Movimento browniano fracionário

1. Introdução

fBM significa Movimento Browniano Fracionário (movimento Browniano fracionário). Mas antes de começarmos a falar sobre natureza, fractais e relevos processuais, vamos nos aprofundar na teoria por um momento.

Movimento Browniano (BM), simplesmente, sem "fragmentação" é um movimento no qual a posição de um objeto muda ao longo do tempo com incrementos aleatórios (imagine a position+=white_noise(); da sequência position+=white_noise(); ). Do ponto de vista formal, o BM é parte integrante do ruído branco. Esses movimentos definem caminhos que são aleatórios, mas (estatisticamente) auto-similares, ou seja, Uma imagem aproximada do caminho se assemelha a todo o caminho. O movimento browniano fracionário é um processo semelhante no qual os incrementos não são completamente independentes um do outro, e há algum tipo de memória nesse processo. Se a memória tiver uma correlação positiva, as alterações em uma determinada direção tenderão a futuras alterações na mesma direção, e o caminho será mais suave do que o BM comum. Se a memória tiver uma correlação negativa, uma mudança na direção positiva com uma alta probabilidade será seguida por uma mudança na negativa, e o caminho será muito mais aleatório. O parâmetro que controla o comportamento da memória ou da integração e, portanto, a auto-similaridade, sua dimensão fractal e espectro de potência, é chamado de expoente de Hurst e geralmente é reduzido para H. Do ponto de vista matemático, H nos permite integrar o ruído branco apenas parcialmente (digamos, apenas 1/3 da integração , daí a "fragmentação" no nome) para criar o fBM para quaisquer características e aparência de memória desejadas. H assume valores no intervalo de 0 a 1, que descrevem, respectivamente, uma fBM grossa e suave, e o BM usual é obtido em H = 1/2.


Aqui, a função fBM () é usada para gerar topografia, nuvens, distribuição de árvores, suas variações de cores e detalhes das copas. "Rainforest", 2016: https://www.shadertoy.com/view/4ttSWf

Tudo isso é muito teórico, e em computação gráfica, o fBM é gerado de uma maneira completamente diferente, mas eu queria explicar a teoria, porque é importante lembrar dela mesmo quando você cria os gráficos. Vamos ver como isso é feito na prática:

Como sabemos, estruturas auto-semelhantes, que são aleatórias ao mesmo tempo, são muito úteis para modelar procedimentos de todos os tipos de fenômenos naturais, de nuvens a montanhas e texturas de casca de árvore . É intuitivamente claro que as figuras da natureza podem ser decompostas em várias figuras grandes que descrevem a forma como um todo, um número maior de figuras de tamanho médio que distorcem o contorno ou a superfície principal da figura original e um número ainda maior de figuras pequenas que adicionam detalhes ao contorno e à forma das duas anteriores. Essa maneira incremental de adicionar detalhes a um objeto, fornecendo uma maneira simples de limitar os limites das faixas de frequência para alterar o LOD (nível de detalhe, níveis de detalhe) e formas de filtragem / suavização, facilita a gravação de código e a criação de resultados visualmente bonitos. Portanto, é amplamente utilizado em filmes e jogos. No entanto, não acho que o fBM seja bem entendido por todo o mecanismo. Neste artigo, descreverei como ele funciona e como suas várias características espectrais e visuais são usadas para vários valores de seu principal parâmetro H, e complementarei tudo isso com experimentos e medições.

Ideia básica

Geralmente (existem várias maneiras) os fBMs são criados chamando aleatoriedade determinística e de suavização usando a função de ruído selecionada pelo desenvolvedor ( valor , gradiente , celular , Voronoi , trigonométrico, simplex , ..., etc., a opção escolhida não é muito importante aqui), seguido pela construção da auto-similaridade. Os fBMs são implementados começando com o sinal de ruído base, aumentando gradualmente cada vez mais as chamadas de ruído detalhadas. Algo assim:

 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; } 

Este é o fBM na sua forma mais pura. Cada ruído de sinal (ou "onda") (), para o qual temos "numOctaves", é combinado de maneira aditiva com uma soma intermediária, mas é comprimido horizontalmente pela metade, o que reduz pela metade o comprimento de onda e a amplitude diminui. exponencialmente. Tal acúmulo de ondas com uma diminuição coordenada no comprimento de onda e amplitude cria a auto-similaridade que observamos na natureza. Por fim, em qualquer espaço dado, há espaço para apenas algumas grandes mudanças, mas há muito espaço para mudanças cada vez menores. Parece bastante razoável. De fato, tais manifestações da lei do poder são encontradas em toda parte da natureza.

A primeira coisa que você pode notar é que o código mostrado acima não é muito semelhante à maioria das implementações de fBM que você pode ver no Shadertoy e em outros exemplos de código. O código abaixo é semelhante ao mostrado acima, mas muito mais popular, porque dispensa as caras funções 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; } 

Então, vamos começar falando sobre numOctaves. Como o comprimento de onda de cada ruído é duas vezes menor que o anterior (e a frequência é duas vezes maior), a designação do que deve ser chamado de "numFrequencies" é substituída por "numOctaves" como referência a um conceito musical: dividir uma oitava entre duas notas corresponde dobrando a frequência da nota de base. Além disso, o fBM pode ser criado incrementando a frequência de cada ruído em uma quantidade diferente dos dois. Nesse caso, o termo "oitava" não será mais tecnicamente correto, mas ainda será usado. Em alguns casos, pode até ser necessário criar ondas / ruído com frequências que aumentam com um coeficiente linear constante e não geometricamente, por exemplo, FFT (transformada rápida de Fourier; pode realmente ser usado para gerar fBMs periódicos (), úteis na criação de texturas oceano). Mas, como veremos mais adiante, a maioria das funções básicas noise () pode aumentar as frequências em magnitudes que são múltiplos de dois, ou seja, precisamos de muito poucas iterações, e os fBMs ainda serão bonitos. De fato, sintetizar o fBM uma oitava de cada vez nos permite ser muito eficazes - por exemplo, em apenas 24 oitavas / iteração, você pode criar o fBM, cobrindo todo o planeta Terra com um detalhe de 2 metros. Se você fizer isso usando frequências linearmente crescentes, serão necessárias várias ordens de magnitude em mais iterações.

A última nota na sequência de frequências: se passarmos de f _i = 2 ⁱ para f _i = 2⋅f _i-1 , isso nos dará alguma flexibilidade com relação ao dobro das frequências (ou redução pela metade dos comprimentos de onda) - podemos expandir facilmente o ciclo e altere cada oitava, por exemplo, substituindo 2.0 por 2.01, 1.99 e outros valores semelhantes, para que os zeros e picos acumulados de diferentes ondas de ruído não se sobreponham exatamente, o que às vezes cria padrões irreais. No caso de 2D-fBM, você também pode girar levemente a área de definição.

Assim, na nova implementação de software do fBM (), não apenas substituímos a geração de frequência de uma formulação de lei de potência por um processo iterativo, mas também alteramos a amplitude exponencial (lei de potência) por séries geométricas controladas pelo indicador de "ganho" G. É necessário realizar uma transformação de H a G, calculando G = 2- ^H , que pode ser facilmente deduzido da primeira versão do código. No entanto, mais frequentemente programadores gráficos ignoram o expoente Hurst H, ou nem sequer sabem sobre ele, e trabalham diretamente com os valores de G. Como sabemos que H varia no intervalo de 0 a 1, G varia de 1 a 0,5. De fato, a maioria dos programadores define um valor constante de G = 0,5 em suas implementações de fBM. Esse código não será tão flexível quanto o uso da variável G, mas há boas razões para isso, e em breve descobriremos sobre elas.

Auto-similaridade

Como mencionado acima, o parâmetro H determina a auto-similaridade da curva. Obviamente, isso é auto-similaridade estatística. Ou seja, no caso do fBM unidimensional (), se aproximarmos a câmera horizontalmente do gráfico por U, então quanto precisamos nos aproximar do gráfico verticalmente por V para obter uma curva com a mesma aparência? Bem, desde que a = f- ^H , então a = V = (f = U) ^-H = f- ^H = U ^-H = a = U- ^H , ou seja, V = U- ^H . Portanto, se aproximarmos a câmera de fBM de um indicador horizontal de 2, verticalmente, precisamos alterar a escala para 2 ^-H . Mas 2 ^-H é G! E isso não é uma coincidência: ao usar G para dimensionar amplitudes de ruído, por definição, construímos fBM de auto-similaridade com um fator de escala G = 2- ^H .


O movimento browniano (H = 1/2) e o zoom anisotrópico são mostrados à esquerda. À direita está fBM (H = 1) e zoom isotrópico.

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

E quanto a montanhas processuais? O movimento browniano padrão tem um valor de H = 1/2, o que nos dá G = 0,707107 ... A esses valores, é gerada uma curva que, quando ampliada, parece exatamente a mesma se for anisotropicamente escalada ao longo de X e Y (se for uma curva unidimensional). E, de fato: para cada fator de zoom horizontal U, precisamos escalar a curva verticalmente em V = sqrt (U), o que não é muito natural. No entanto, os gráficos do mercado de ações muitas vezes se aproximam de H = 1/2, porque, em teoria, todo incremento ou decréscimo do valor das ações é independente das alterações anteriores (não esqueça que o BM é um processo sem memória). Obviamente, na prática, certas dependências estão presentes e essas curvas estão mais próximas de H = 0,6.

Mas o processo natural contém mais "memória" em si, e a auto-similaridade é muito mais isotrópica. Por exemplo, uma montanha mais alta é mais larga em sua base na mesma quantidade, ou seja, as montanhas geralmente não se esticam e não se tornam mais finas. Portanto, isso nos faz entender que para as montanhas G deve ser 1/2 - o mesmo zoom horizontal e vertical. Isso corresponde a H = 1, ou seja, os perfis das montanhas devem ser mais suaves que a curva da bolsa de valores. De fato, é, e um pouco mais tarde mediremos perfis reais para confirmar isso. Mas, por experiência, sabemos que G = 0,5 cria belos relevos fractais e nuvens; portanto, G = 0,5 é realmente o valor G mais popular para todas as implementações de fbm.

Mas agora temos uma compreensão mais profunda de H, G e fBM em geral. Sabemos que se o valor de G for mais próximo de 1, o fBM será ainda mais louco que o BM puro. E de fato: para G = 1, que corresponde a H = 0, obtemos o fBM mais barulhento de todos.

Todas essas funções paramétricas do fBM têm nomes, por exemplo, “ruído rosa” em H = 0, G = 1 ou “ruído marrom” em H = 1/2, G = sqrt (2), herdados do campo de processamento de sinal digital (Digital Processamento de Sinais) e são bem conhecidos por pessoas com problemas de sono. Vamos nos aprofundar no DSP e calcular as características espectrais para obter uma compreensão mais profunda do fBM.

Perspectiva de processamento de sinal

Se você pensa na análise de Fourier ou na síntese aditiva de sons, a implementação do fBM () mostrada acima é semelhante à Transformada Inversa de Fourier, que é discreta como a transformada discreta de Fourier (DFT), mas muito esparsa e usa uma base diferente função (essencialmente muito diferente da IFT, mas deixe-me explicar). De fato, podemos gerar fBM (), computação gráfica e até superfícies oceânicas usando o IFFT, mas isso está rapidamente se tornando um projeto muito caro. A razão é que o IFFT não combina de maneira aditiva as ondas sonoras, mas os sinusóides, mas os sinusóides não preenchem muito eficientemente o espectro de energia da energia, porque cada sinusóide afeta uma frequência. No entanto, as funções de ruído têm espectros amplos que cobrem longos intervalos de frequência com uma única onda. Tanto o ruído de gradiente quanto o ruído de valor têm gráficos tão ricos e densos de densidade espectral. Veja os gráficos:


Onda senoidal


Ruído de valor


Ruído gradiente
Observe que, no espectro do ruído Value e do gradiente, a maior parte da energia está concentrada nas frequências mais baixas, mas é mais ampla - uma escolha ideal para preencher rapidamente todo o espectro com várias cópias em offset e em escala. Outro problema da onda senoidal fBM é esse. é claro que gera pattenes repetidos, que geralmente são indesejáveis, embora possam ser úteis para gerar texturas sem costura. A vantagem do fBM () baseado no sin () é que ele é superprodutivo, porque as funções trigonométricas são executadas no ferro muito mais rapidamente do que a criação de ruído usando polinômios e hashes / lut, portanto, às vezes, ainda vale a pena usar o fBM baseado em ondas senoidais de considerações de desempenho, mesmo que sejam criadas paisagens ruins.

Agora, vamos dar uma olhada nos gráficos da densidade de espectros para fBM com diferentes valores de H. Preste atenção especial às marcas no eixo vertical, porque todos os três gráficos são normalizados e não descrevem as mesmas inclinações, embora à primeira vista pareçam quase iguais. Se denotarmos a inclinação negativa desses gráficos espectrais como “B”, como esses gráficos têm uma escala logarítmica, o espectro seguirá uma lei de potência da forma f- ^B . Neste teste, utilizo 10 oitavas de ruído de gradiente normal para criar o fBM mostrado abaixo.


G = 1,0 (H = 0)


G = 0,707 (H = 1/2)


G = 0,5 (H = 1)

Como podemos ver, a energia fBM com H = 0 (G = 1) atenua a 3 dB por oitava ou, de fato, retorna em valor à frequência. Esta é uma lei de potência f ^-1 (B = 1), que é chamada de "ruído rosa" e soa como chuva.

O fBM () com H = 1/2 (G = 0,707) gera um espectro que atenua mais rapidamente, a 6 dB por oitava, ou seja, possui menos frequências altas. Na verdade, parece mais profundo, como se você estivesse ouvindo chuva, mas desta vez do seu quarto com as janelas fechadas. A atenuação de 6 dB / oitava significa que a energia é proporcional a f ^-2 (B = 2), e isso é realmente uma característica do movimento browniano no DSP.

Finalmente, nosso fBM favorito de computação gráfica com H = 1 (G = 0,5) gera um gráfico de densidade espectral com um decaimento de 9 dB / oitava, ou seja, a energia é inversamente proporcional ao cubo de frequência (f ^-3 , B = 3). Este é um sinal com frequência constantemente baixa, que corresponde a um processo com memória de correlação positiva, sobre a qual falamos no início. Esse tipo de sinal não tem seu próprio nome, por isso tenho a tentação de chamá-lo de "ruído amarelo" (simplesmente porque esse nome não é mais usado para nada). Como sabemos, é isotrópico, o que significa que modela muitas formas naturais auto-repetitivas.

De fato, vou confirmar minhas palavras sobre a semelhança com a natureza fazendo as medições fornecidas na próxima seção do artigo.

Título	H	G = 2 -H	B = 2H + 1	dB / oct	Som
Azul	-	-	+1	+3	Pulverize água. Link
Branco	-	-	0 0	0 0	Vento nas folhas. Link
Rosa	0 0	1	-1	-3	A chuva Link
Castanho	1/2	sqrt (2)	-2	-6	Chuva ouviu de casa. Link
Amarelo	1	1/2	-3	-9	Motor atrás da porta

Medições

Primeiro, devo adverti-lo de que será um experimento não científico, mas ainda quero compartilhá-lo. Tirei fotografias de cadeias de montanhas paralelas ao plano da imagem para evitar distorções de perspectiva. Dividi as imagens em preto e branco e converti a superfície de contato do céu e das montanhas em um sinal 1D. Depois, interpretei-o como um arquivo de som WAV e calculei seu gráfico de frequência, como é o caso dos sinais sintéticos fBM () que analisei acima. Selecionei imagens com uma resolução suficientemente alta para que o algoritmo FFT tivesse dados significativos para o trabalho.


Fonte: Repórter grego


Fonte: Wikipedia







Parece que os resultados realmente indicam que os perfis das montanhas seguem uma distribuição de frequência de -9 dB / oitava, que corresponde a B = -3 ou H = 1 ou G = 0,5, ou seja, ruído amarelo.

Obviamente, o experimento não foi rigoroso, mas confirma nossa compreensão intuitiva e o que já sabemos por experiência própria e trabalhamos com computação gráfica. Mas espero que agora tenhamos começado a entender isso melhor!