Mouvement brownien fractionnaire

Présentation

fBM signifie Fractional Brownian Motion (mouvement fractionnaire brownien). Mais avant de commencer à parler de la nature, des fractales et des reliefs procéduraux, penchons-nous un instant sur la théorie.

Le mouvement brownien (BM), simplement, sans "fragmentation" est un mouvement dans lequel la position d'un objet change avec le temps avec des incréments aléatoires (imaginez la position+=white_noise(); la séquence position+=white_noise(); ). D'un point de vue formel, BM fait partie intégrante du bruit blanc. Ces mouvements définissent des trajectoires aléatoires mais (statistiquement) auto-similaires, c'est-à-dire Une image approximative du chemin ressemble à l'ensemble du chemin. Le mouvement brownien fractionnaire est un processus similaire dans lequel les incréments ne sont pas complètement indépendants les uns des autres, et il y a une sorte de mémoire dans ce processus. Si la mémoire a une corrélation positive, alors les changements dans une direction donnée auront tendance à des changements futurs dans la même direction, et le chemin sera plus lisse qu'avec le BM ordinaire. Si la mémoire a une corrélation négative, alors un changement dans la direction positive avec une forte probabilité sera suivi d'un changement dans le négatif, et le chemin sera beaucoup plus aléatoire. Le paramètre qui contrôle le comportement de la mémoire ou de l'intégration, et donc l'autosimilarité, sa dimension fractale et son spectre de puissance, est appelé l'exposant de Hurst et est généralement réduit à H. D'un point de vue mathématique, H nous permet d'intégrer le bruit blanc seulement partiellement (disons, seulement 1/3 de l'intégration , d'où la "fragmentation" dans le nom) pour créer fBM pour toutes les caractéristiques de mémoire désirées et l'apparence. H prend des valeurs dans la gamme de 0 à 1, qui décrivent respectivement un fBM grossier et lisse, et le BM habituel est obtenu à H = 1/2.


Ici, la fonction fBM () est utilisée pour générer la topographie, les nuages, la distribution des arbres, leurs variations de couleur et les détails de la couronne. "Rainforest", 2016: https://www.shadertoy.com/view/4ttSWf

Tout cela est très théorique, et en infographie, le fBM est généré d'une manière complètement différente, mais je voulais expliquer la théorie, car il est important de s'en souvenir même lorsque vous créez les graphiques. Voyons comment cela se fait dans la pratique:

Comme nous le savons, les structures auto-similaires, qui sont aléatoires en même temps, sont très utiles pour la modélisation procédurale de toutes sortes de phénomènes naturels, des nuages aux montagnes et aux textures d'écorce d'arbre . Il est intuitivement clair que les figures dans la nature peuvent être décomposées en plusieurs grandes figures qui décrivent la forme dans son ensemble, un plus grand nombre de figures de taille moyenne qui déforment le contour principal ou la surface de la figure originale, et un nombre encore plus grand de petites figures qui ajoutent des détails au contour et à la forme des deux précédentes. Une telle manière incrémentielle d'ajouter des détails à un objet, nous fournissant un moyen simple de limiter les limites des plages de fréquences pour changer le LOD (niveau de détail, niveaux de détail) et filtrer / lisser les formes, facilite l'écriture de code et crée des résultats visuellement beaux. Par conséquent, il est largement utilisé dans les films et les jeux. Cependant, je ne pense pas que la fBM soit bien comprise par l'ensemble du mécanisme. Dans cet article, je décrirai comment il fonctionne et comment ses différentes caractéristiques spectrales et visuelles sont utilisées pour différentes valeurs de son paramètre principal H, et je compléterai tout cela par des expériences et des mesures.

Idée de base

Habituellement (il existe de nombreuses façons) les fBM sont construits en appelant l'aléatoire déterministe et le lissage en utilisant la fonction de bruit sélectionnée par le développeur ( valeur , gradient , cellulaire , Voronoi , trigonométrique, simplex , ..., etc., l'option choisie n'est pas très importante ici), suivie par la construction de l'auto-similitude. Les fBM sont implémentés à partir du signal de bruit de base, en y ajoutant progressivement des appels de bruit détaillés de plus en plus petits. Quelque chose comme ça:

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

C'est fBM dans sa forme la plus pure. Chaque bruit de signal (ou "onde") (), pour lequel nous avons "numOctaves", est additionnellement combiné avec une somme intermédiaire, mais est compressé horizontalement de moitié, ce qui réduit de moitié sa longueur d'onde, et son amplitude diminue exponentiellement. Une telle accumulation d'ondes avec une diminution coordonnée de la longueur d'onde et de l'amplitude crée l'auto-similitude que nous observons dans la nature. En fin de compte, dans un espace donné, il n'y a de place que pour quelques grands changements, mais il y a beaucoup de place pour des changements toujours plus petits. Cela semble tout à fait raisonnable. En fait, de telles manifestations de la loi de puissance se retrouvent partout dans la nature.

La première chose que vous pouvez remarquer est que le code ci-dessus n'est pas tout à fait similaire à la plupart des implémentations fBM que vous pouvez voir dans Shadertoy et d'autres exemples de code. Le code ci-dessous est similaire à celui montré ci-dessus, mais beaucoup plus populaire, car il renonce aux fonctions coûteuses 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; } 

Commençons donc par parler de numOctaves. La longueur d'onde de chaque bruit étant deux fois inférieure à la précédente (et la fréquence deux fois plus élevée), la désignation de ce qu'il convient d'appeler «numFrequencies» est remplacée par «numOctaves» en référence à un concept musical: la division d'une octave entre deux notes correspond doubler la fréquence de la note de fond. De plus, fBM peut être créé en augmentant la fréquence de chaque bruit d'une quantité différente des deux. Dans ce cas, le terme «octave» ne sera plus techniquement correct, mais il est toujours utilisé. Dans certains cas, il peut même être nécessaire de créer des ondes / bruit avec des fréquences qui augmentent avec un coefficient linéaire constant, et non géométriquement, par exemple, FFT (transformée de Fourier rapide; il peut en fait être utilisé pour générer des fBM périodiques (), utiles pour créer des textures océan). Mais, comme nous le verrons plus loin, la plupart des fonctions de base de noise () peuvent augmenter les fréquences par des amplitudes qui sont des multiples de deux, c'est-à-dire que nous avons besoin de très peu d'itérations, et fBM sera toujours beau. En fait, synthétiser fBM une octave à la fois nous permet d'être très efficace - par exemple, en seulement 24 octaves / itération, vous pouvez créer un fBM couvrant la planète Terre entière avec 2 mètres de détail. Si vous faites cela en utilisant des fréquences augmentant linéairement, cela prendra plusieurs ordres de grandeur plus d'itérations.

La dernière note sur la séquence des fréquences: si nous passons de f _i = 2 ⁱ à f _i = 2⋅f _i-1 , cela nous donnera une certaine flexibilité pour doubler les fréquences (ou réduire de moitié les longueurs d'onde) - nous pouvons facilement étendre le cycle et changez chaque octave, par exemple, en remplaçant 2.0 par 2.01, 1.99 et d'autres valeurs similaires afin que les zéros et les pics accumulés de différentes ondes de bruit ne se chevauchent pas exactement, ce qui crée parfois des motifs irréalistes. Dans le cas de 2D-fBM, vous pouvez également faire pivoter légèrement la zone de définition.

Ainsi, dans la nouvelle implémentation logicielle de fBM (), nous avons non seulement remplacé la génération de fréquence à partir d'une formulation de loi de puissance par un processus itératif, mais également changé l'amplitude exponentielle (loi de puissance) par des séries géométriques contrôlées par l'indicateur de «gain» G.Il est nécessaire d'effectuer une transformation à partir de H à G, calculant G = 2 ^-H , qui peut être facilement déduit de la première version du code. Cependant, les programmeurs graphiques ignorent le plus souvent l'exposant Hurst H, ou ne le savent même pas, et travaillent directement avec les valeurs de G.Comme nous savons que H varie dans la plage de 0 à 1, alors G varie de 1 à 0,5. En fait, la plupart des programmeurs définissent une valeur constante de G = 0,5 dans leurs implémentations fBM. Ce code ne sera pas aussi flexible que l'utilisation de la variable G, mais il y a de bonnes raisons à cela, et bientôt nous les découvrirons.

Auto-similitude

Comme mentionné ci-dessus, le paramètre H détermine l'auto-similitude de la courbe. Bien sûr, il s'agit d'une auto-similitude statistique. Autrement dit, dans le cas du fBM unidimensionnel (), si nous rapprochons la caméra horizontalement du graphique par U, alors de combien avons-nous besoin pour nous rapprocher verticalement du graphique par V pour obtenir une courbe qui aurait la même apparence? Eh bien, puisque a = f ^-H , alors a⋅V = (f⋅U) ^-H = f ^-H ⋅U ^-H = a⋅U ^-H , c'est-à-dire V = U ^-H . Donc, si nous rapprochons la caméra de fBM par un indicateur horizontal de 2, alors verticalement, nous devons changer l'échelle à 2 ^-H . Mais 2 ^-H est G! Et ce n'est pas une coïncidence: lorsque nous utilisons G pour mettre à l'échelle les amplitudes de bruit, nous, par définition, construisons l'auto-similitude fBM avec un facteur d'échelle G = 2 ^-H .


Le mouvement brownien (H = 1/2) et le zoom anisotrope sont indiqués à gauche. À droite, fBM (H = 1) et zoom isotrope.

Code: https://www.shadertoy.com/view/WsV3zz

Et les montagnes procédurales? Le mouvement brownien standard a une valeur de H = 1/2, ce qui nous donne G = 0,707107 ... À ces valeurs, une courbe est générée qui, lorsqu'elle est agrandie, a exactement la même apparence si elle est mise à l'échelle anisotrope le long de X et Y (s'il s'agit d'une courbe unidimensionnelle). Et en fait: pour chaque facteur de zoom horizontal U, nous devons redimensionner la courbe verticalement de V = sqrt (U), ce qui n'est pas très naturel. Cependant, les graphiques des bourses se rapprochent très souvent de H = 1/2, car en théorie, chaque incrément ou décrément de la valeur des actions ne dépend pas des changements précédents (n'oubliez pas que BM est un processus sans mémoire). Bien sûr, en pratique, certaines dépendances sont présentes, et ces courbes sont plus proches de H = 0,6.

Mais le processus naturel contient plus de «mémoire» en soi, et l'auto-similitude est beaucoup plus isotrope. Par exemple, une montagne plus haute est plus large à sa base du même montant, c'est-à-dire les montagnes ne s'étirent généralement pas et ne s'amincissent pas. Par conséquent, cela nous fait comprendre que pour les montagnes, G devrait être 1/2 - le même zoom horizontal et vertical. Cela correspond à H = 1, c'est-à-dire que les profils de montagne doivent être plus lisses que la courbe boursière. En fait, c'est le cas, et un peu plus tard nous mesurerons de vrais profils pour le confirmer. Mais par expérience, nous savons que G = 0,5 crée de beaux reliefs fractals et des nuages, donc G = 0,5 est en effet la valeur G la plus populaire pour toutes les implémentations fbm.

Mais maintenant, nous avons une compréhension plus approfondie de H, G et fBM en général. Nous savons que si la valeur de G est plus proche de 1, alors fBM sera encore plus fou que BM pur. Et en fait: pour G = 1, ce qui correspond à H = 0, on obtient le fBM le plus bruyant de tous.

Toutes ces fonctions fBM paramétrées ont des noms, par exemple, «bruit rose» à H = 0, G = 1 ou «bruit brun» à H = 1/2, G = sqrt (2), hérités du domaine du traitement numérique du signal (Digital Traitement du signal) et sont bien connus des personnes ayant des problèmes de sommeil. Examinons plus profondément le DSP et calculons les caractéristiques spectrales pour obtenir une compréhension plus approfondie de la fBM.

Perspective du traitement du signal

Si vous pensez à l'analyse de Fourier ou à la synthèse sonore additive, l'implémentation fBM () ci-dessus est similaire à la transformation de Fourier inverse, qui est discrète comme la transformée de Fourier discrète (DFT), mais très clairsemée et utilise une base différente fonction (essentiellement très différente de IFT, mais laissez-moi vous expliquer). En fait, nous pouvons générer fBM (), des graphiques informatiques et même des surfaces océaniques en utilisant IFFT, mais cela devient rapidement un projet très coûteux. La raison en est que l'IFFT ne combine pas de manière additive les ondes de bruit, mais les sinusoïdes, mais les sinusoïdes ne remplissent pas très efficacement le spectre de puissance énergétique, car chaque sinusoïde affecte une fréquence. Cependant, les fonctions de bruit ont des spectres larges qui couvrent de longs intervalles de fréquence avec une seule onde. Le bruit de gradient et le bruit de valeur ont des graphiques riches et denses de densité spectrale. Jetez un œil aux graphiques:


Onde sinusoïdale


Bruit de valeur


Bruit dégradé
Notez que dans le spectre du bruit de valeur et du bruit de gradient, la majeure partie de l'énergie est concentrée dans les basses fréquences, mais elle est plus large - un choix idéal pour remplir rapidement tout le spectre avec plusieurs copies décalées et à l'échelle. Un autre problème de fBM à onde sinusoïdale est le suivant. qu'il génère, bien entendu, des motifs répétitifs, qui sont le plus souvent indésirables, bien qu'ils puissent être utiles pour générer des textures homogènes. L'avantage de fBM () basé sur sin () est qu'il est superproductif, car les fonctions trigonométriques sont exécutées dans le fer beaucoup plus rapidement que le bruit de construction en utilisant des polynômes et des hachages / lut, il est donc parfois utile d'utiliser fBM basé sur les ondes sinusoïdales de des considérations de performance, même si des paysages pauvres sont créés.

Examinons maintenant les graphiques de la densité de spectres pour fBM avec différentes valeurs de H.Portez une attention particulière aux marques sur l'axe vertical, car les trois graphiques sont normalisés et ne décrivent pas les mêmes pentes, bien qu'à première vue, ils se ressemblent presque. Si nous désignons la pente négative de ces graphes spectraux par «B», alors comme ces graphes ont une échelle logarithmique, le spectre suivra une loi de puissance de la forme f ^-B . Dans ce test, j'utilise 10 octaves de bruit de gradient normal pour construire le fBM illustré ci-dessous.


G = 1,0 (H = 0)


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


G = 0,5 (H = 1)

Comme nous pouvons le voir, l'énergie fBM avec H = 0 (G = 1) s'atténue à 3 dB par octave, ou, en fait, revient en valeur à la fréquence. Il s'agit d'une loi de puissance f ^-1 (B = 1), qui est appelée «bruit rose» et sonne comme de la pluie.

fBM () avec H = 1/2 (G = 0,707) génère un spectre qui s'atténue plus rapidement, à 6 dB par octave, c'est-à-dire qu'il a moins de hautes fréquences. En fait, cela semble plus profond, comme si vous entendiez de la pluie, mais cette fois depuis votre chambre avec les fenêtres fermées. L'atténuation de 6 dB / octave signifie que l'énergie est proportionnelle à f ^-2 (B = 2), et c'est en fait une caractéristique du mouvement brownien dans le DSP.

Enfin, notre fBM préféré à partir de l'infographie avec H = 1 (G = 0,5) génère un tracé de densité spectrale avec une décroissance de 9 dB / octave, c'est-à-dire que l'énergie est inversement proportionnelle au cube de fréquence (f ^-3 , B = 3). Il s'agit d'un signal à fréquence constamment basse, ce qui correspond à un processus à mémoire de corrélation positive, dont nous avons parlé au début. Ce type de signal n'a pas son propre nom, j'ai donc la tentation de l'appeler «bruit jaune» (simplement parce que ce nom n'est plus utilisé pour rien). Comme nous le savons, il est isotrope, ce qui signifie qu'il modélise beaucoup de formes naturelles auto-répétitives.

En fait, je vais confirmer mes propos sur la similitude avec la nature en faisant les mesures données dans la prochaine section de l'article.

Le titre	H	G = 2 -H	B = 2H + 1	dB / oct	Son
Bleu	-	-	+1	+3	Vaporisez de l'eau. Lien
Blanc	-	-	0	0	Vent dans les feuilles. Lien
Rose	0	1	-1	-3	La pluie. Lien
Marron	1/2	sqrt (2)	-2	-6	Rain a entendu de la maison. Lien
Jaune	1	1/2	-3	-9	Moteur derrière la porte

Mesures

Je dois d'abord vous avertir que ce sera une expérience très non scientifique, mais je veux quand même la partager. J'ai pris des photos de chaînes de montagnes parallèles au plan image pour éviter une distorsion de perspective. J'ai ensuite divisé les images en noir et blanc, puis converti la surface de contact du ciel et des montagnes en un signal 1D. Ensuite, je l'ai interprété comme un fichier son WAV et calculé son graphique de fréquence, comme c'est le cas avec les signaux synthétiques fBM () que j'ai analysés ci-dessus. J'ai sélectionné des images avec une résolution suffisamment élevée pour que l'algorithme FFT ait des données importantes pour le travail.


Source: Reporter grec


Source: Wikipedia







Il semble que les résultats indiquent vraiment que les profils de montagne suivent une distribution de fréquence de -9 dB / octave, ce qui correspond à B = -3 ou H = 1 ou G = 0,5, ou, en d'autres termes, du bruit jaune.

Bien sûr, l'expérience n'a pas été rigoureuse, mais elle confirme notre compréhension intuitive et ce que nous savons déjà de l'expérience et du travail avec l'infographie. Mais j'espère que maintenant nous avons commencé à mieux comprendre cela!