Bruch-Brownsche Bewegung

Einführung

fBM steht für Fractional Brownian Motion (fraktionierte Brownsche Bewegung). Bevor wir jedoch über Natur, Fraktale und prozedurale Reliefs sprechen, wollen wir uns kurz mit der Theorie befassen.

Brownsche Bewegung (BM) ist einfach ohne "Fragmentierung" eine Bewegung, bei der sich die Position eines Objekts im Laufe der Zeit in zufälligen Schritten ändert (stellen Sie sich die Sequenzposition position+=white_noise(); ). Aus formaler Sicht ist BM ein Integral des weißen Rauschens. Diese Bewegungen definieren Pfade, die zufällig, aber (statistisch) selbstähnlich sind, d.h. Ein ungefähres Bild des Pfades ähnelt dem gesamten Pfad. Fractional Brownian Motion ist ein ähnlicher Prozess, bei dem Inkremente nicht vollständig unabhängig voneinander sind und in diesem Prozess eine Art Speicher vorhanden ist. Wenn der Speicher eine positive Korrelation aufweist, tendieren Änderungen in einer bestimmten Richtung zu zukünftigen Änderungen in derselben Richtung, und der Pfad ist glatter als bei gewöhnlichem BM. Wenn der Speicher eine negative Korrelation aufweist, folgt auf eine Änderung der positiven Richtung mit hoher Wahrscheinlichkeit eine Änderung der negativen Richtung, und der Pfad ist viel zufälliger. Der Parameter, der das Verhalten des Gedächtnisses oder der Integration und damit die Selbstähnlichkeit, seine fraktale Dimension und sein Leistungsspektrum steuert, wird als Hurst-Exponent bezeichnet und normalerweise auf H reduziert. Aus mathematischer Sicht erlaubt H, weißes Rauschen nur teilweise zu integrieren (z. B. nur 1/3 der Integration) , daher die "Fragmentierung" im Namen), um fBM für alle gewünschten Speichereigenschaften und Erscheinungsbilder zu erstellen. H nimmt Werte im Bereich von 0 bis 1 an, die jeweils ein grobes und glattes fBM beschreiben, und der übliche BM wird bei H = 1/2 erhalten.


Hier wird die Funktion fBM () verwendet, um Topographie, Wolken, Verteilung von Bäumen, deren Farbvariationen und Kronendetails zu erzeugen. "Rainforest", 2016: https://www.shadertoy.com/view/4ttSWf

All dies ist sehr theoretisch und in der Computergrafik wird fBM auf eine völlig andere Weise generiert, aber ich wollte die Theorie erklären, da es wichtig ist, sich daran zu erinnern, auch wenn Sie die Grafiken erstellen. Mal sehen, wie das in der Praxis gemacht wird:

Wie wir wissen, sind selbstähnliche Strukturen, die gleichzeitig zufällig sind, sehr nützlich für die prozedurale Modellierung verschiedener Naturphänomene, von Wolken bis zu Bergen und Texturen der Baumrinde . Es ist intuitiv klar, dass Figuren in der Natur in mehrere große Figuren zerlegt werden können, die die Form als Ganzes beschreiben, eine größere Anzahl mittelgroßer Figuren, die den Hauptumriss oder die Oberfläche der ursprünglichen Figur verzerren, und eine noch größere Anzahl kleiner Figuren, die den Umriss und die Form der beiden vorhergehenden Details ergänzen. Eine solche inkrementelle Methode zum Hinzufügen von Details zu einem Objekt, die uns eine einfache Möglichkeit bietet, die Grenzen der Frequenzbereiche für das Ändern der LOD (Detailebene, Detailebenen) und das Filtern / Glätten von Formen zu begrenzen, erleichtert das Schreiben von Code und das Erstellen visuell schöner Ergebnisse. Daher ist es in Filmen und Spielen weit verbreitet. Ich glaube jedoch nicht, dass fBM vom gesamten Mechanismus gut verstanden wird. In diesem Artikel werde ich beschreiben, wie es funktioniert und wie seine verschiedenen spektralen und visuellen Eigenschaften für verschiedene Werte seines Hauptparameters H verwendet werden, und ich werde dies alles durch Experimente und Messungen ergänzen.

Grundidee

Normalerweise (es gibt viele Möglichkeiten) werden fBMs konstruiert, indem deterministische und glättende Zufälligkeit unter Verwendung der vom Entwickler ausgewählten Rauschfunktion aufgerufen wird ( Wert , Gradient , Zellular , Voronoi , Trigonometrie, Simplex , ... usw., die gewählte Option ist hier nicht sehr wichtig). gefolgt von der Konstruktion der Selbstähnlichkeit. fBMs werden beginnend mit dem Basisrauschensignal implementiert und fügen allmählich kleinere und kleinere detaillierte Rauschaufrufe hinzu. So etwas wie das:

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

Dies ist fBM in seiner reinsten Form. Jedes Signalrauschen (oder "Wellenrauschen"), für das wir "numOctaves" haben, wird additiv mit einer Zwischensumme kombiniert, aber horizontal um die Hälfte komprimiert, wodurch sich seine Wellenlänge im Wesentlichen halbiert und seine Amplitude abnimmt exponentiell. Eine solche Ansammlung von Wellen mit einer koordinierten Abnahme der Wellenlänge und Amplitude erzeugt die Selbstähnlichkeit, die wir in der Natur beobachten. Letztendlich gibt es in jedem Raum Platz für nur wenige große Änderungen, aber es gibt viel Platz für immer kleinere Änderungen. Klingt ganz vernünftig. Tatsächlich finden sich solche Manifestationen des Machtgesetzes überall in der Natur.

Das erste, was Sie feststellen können, ist, dass der oben gezeigte Code den meisten fBM-Implementierungen, die Sie in Shadertoy und anderen Codebeispielen sehen konnten, nicht ganz ähnlich ist. Der folgende Code ähnelt dem oben gezeigten, ist jedoch viel beliebter, da er auf die kostspieligen Funktionen von pow () verzichtet:

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

Beginnen wir also mit numOctaves. Da die Wellenlänge jedes Rauschens zweimal kleiner ist als die vorherige (und die Frequenz zweimal höher ist), wird die Bezeichnung "numFrequences" als Referenz für ein musikalisches Konzept durch "numOctaves" ersetzt: Die Aufteilung einer Oktave zwischen zwei Noten entspricht Verdoppelung der Frequenz der Basisnote. Zusätzlich kann fBM erzeugt werden, indem die Frequenz jedes Rauschens um einen von den beiden unterschiedlichen Betrag erhöht wird. In diesem Fall ist der Begriff „Oktave“ technisch nicht mehr korrekt, wird aber weiterhin verwendet. In einigen Fällen kann es sogar erforderlich sein, Wellen / Rauschen mit Frequenzen zu erzeugen, die mit einem konstanten linearen Koeffizienten zunehmen, und nicht geometrisch, beispielsweise FFT (schnelle Fourier-Transformation; es kann tatsächlich verwendet werden, um periodische fBMs () zu erzeugen, die beim Erstellen von Texturen nützlich sind Ozean). Wie wir später sehen werden, können die meisten Grundfunktionen von Rauschen () die Frequenzen um ein Vielfaches von zwei erhöhen, dh wir benötigen nur sehr wenige Iterationen, und fBM wird immer noch schön sein. Wenn wir fBM jeweils eine Oktave synthetisieren, können wir sehr effektiv sein. Beispielsweise können Sie in nur 24 Oktaven / Iteration fBM erstellen, das den gesamten Planeten Erde mit einem Detail von 2 Metern abdeckt. Wenn Sie dies mit linear ansteigenden Frequenzen tun, dauert es mehrere Größenordnungen mehr Iterationen.

Die letzte Anmerkung zur Frequenzfolge: Wenn wir von f _i = 2 ⁱ zu f _i = 2⋅f _i-1 wechseln, erhalten wir eine gewisse Flexibilität hinsichtlich der Verdoppelung der Frequenzen (oder der Reduzierung um die Hälfte der Wellenlängen) - wir können den Zyklus leicht erweitern und Ändern Sie beispielsweise jede Oktave, indem Sie 2.0 durch 2.01, 1.99 und andere ähnliche Werte ersetzen, damit sich die akkumulierten Nullen und Spitzen verschiedener Rauschwellen nicht genau überlappen, was manchmal zu unrealistischen Mustern führt. Bei 2D-fBM können Sie den Definitionsbereich auch leicht drehen.

In der neuen Software-Implementierung von fBM () haben wir also nicht nur die Frequenzerzeugung aus einer Potenzgesetzformulierung durch einen iterativen Prozess ersetzt, sondern auch die Exponentialamplitude (Potenzgesetz) durch geometrische Reihen geändert, die vom Indikator „Verstärkung“ G gesteuert werden. Es ist erforderlich, eine Transformation von durchzuführen H bis G, Berechnung von G = 2 ^-H , was leicht aus der ersten Version des Codes abgeleitet werden kann. Grafikprogrammierer ignorieren jedoch häufiger den Hurst-Exponenten H oder wissen nicht einmal davon und arbeiten direkt mit den Werten von G. Da wir wissen, dass H im Bereich von 0 bis 1 variiert, variiert G von 1 bis 0,5. Tatsächlich setzen die meisten Programmierer in ihren fBM-Implementierungen einen konstanten Wert von G = 0,5. Dieser Code wird nicht so flexibel sein wie die Verwendung der Variablen G, aber es gibt gute Gründe dafür, und wir werden bald davon erfahren.

Selbstähnlichkeit

Wie oben erwähnt, bestimmt der Parameter H die Selbstähnlichkeit der Kurve. Dies ist natürlich statistische Selbstähnlichkeit. Das heißt, wenn wir im Fall des eindimensionalen fBM () die Kamera durch U horizontal näher an den Graphen bringen, wie viel müssen wir dann durch V vertikal näher an den Graphen heranrücken, um eine Kurve zu erhalten, die gleich aussehen würde? Nun, da a = f ^-H , dann ist a⋅V = (f⋅U) ^-H = f ^-H ⋅U ^-H = a⋅U ^-H , dh V = U ^-H . Wenn wir also die Kamera durch einen horizontalen Indikator von 2 näher an fBM heranrücken, müssen wir vertikal die Skalierung auf 2 ^-H ändern. Aber 2 ^-H ist G! Und dies ist kein Zufall: Wenn wir G verwenden, um Rauschamplituden zu skalieren, bauen wir per Definition Selbstähnlichkeit fBM mit einem Skalierungsfaktor G = 2 ^{-H auf} .


Die Brownsche Bewegung (H = 1/2) und der anisotrope Zoom werden links angezeigt. Rechts ist fBM (H = 1) und isotroper Zoom.

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

Was ist mit prozeduralen Bergen? Die Standard-Brownsche Bewegung hat einen Wert von H = 1/2, was G = 0,707107 ergibt. Bei diesen Werten wird eine Kurve erzeugt, die bei Vergrößerung genau gleich aussieht, wenn sie entlang X und Y anisotrop skaliert wird (wenn es sich um eine eindimensionale Kurve handelt). Und tatsächlich: Für jeden horizontalen Zoomfaktor U müssen wir die Kurve vertikal um V = sqrt (U) skalieren, was nicht sehr natürlich ist. Börsencharts kommen jedoch sehr oft H = 1/2 nahe, da theoretisch jede Erhöhung oder Verringerung des Wertes von Aktien nicht von vorherigen Änderungen abhängt (vergessen Sie nicht, dass BM ein Prozess ohne Speicher ist). In der Praxis sind natürlich bestimmte Abhängigkeiten vorhanden, und diese Kurven liegen näher bei H = 0,6.

Aber der natürliche Prozess enthält mehr „Gedächtnis“ an sich, und die Selbstähnlichkeit ist viel isotroper. Zum Beispiel ist ein höherer Berg an seiner Basis um den gleichen Betrag breiter, d.h. Berge dehnen sich normalerweise nicht aus und werden nicht dünner. Dies macht uns verständlich, dass für die Berge G 1/2 sein sollte - der gleiche horizontale und vertikale Zoom. Dies entspricht H = 1, dh die Bergprofile sollten glatter sein als die Börsenkurve. Tatsächlich ist es so, und wenig später werden wir reale Profile messen, um dies zu bestätigen. Aus Erfahrung wissen wir jedoch, dass G = 0,5 wunderschöne fraktale Reliefs und Wolken erzeugt, sodass G = 0,5 in der Tat der beliebteste G-Wert für alle fbm-Implementierungen ist.

Aber jetzt haben wir ein tieferes Verständnis von H, G und fBM im Allgemeinen. Wir wissen, dass fBM noch verrückter ist als reines BM, wenn der Wert von G näher bei 1 liegt. Und tatsächlich: Für G = 1, was H = 0 entspricht, erhalten wir das lauteste fBM von allen.

Alle diese parametrisierten fBM-Funktionen werden beispielsweise als "rosa Rauschen" bei H = 0, G = 1 oder "braunes Rauschen" bei H = 1/2, G = sqrt (2) bezeichnet, die aus dem Bereich der digitalen Signalverarbeitung (Digital) geerbt werden Signalverarbeitung) und sind Menschen mit Schlafproblemen bekannt. Lassen Sie uns tiefer in den DSP eintauchen und die spektralen Eigenschaften berechnen, um ein tieferes Verständnis von fBM zu erhalten.

Signalverarbeitungsperspektive

Wenn Sie an eine Fourier-Analyse oder eine additive Klangsynthese denken, ähnelt die oben gezeigte Implementierung von fBM () der inversen Fourier-Transformation, die diskret wie die diskrete Fourier-Transformation (DFT) ist, jedoch sehr spärlich und eine andere Basis verwendet Funktion (wesentlich anders als IFT, aber lassen Sie mich erklären). Tatsächlich können wir mit IFFT fBM (), Computergrafiken und sogar Meeresoberflächen erzeugen, aber dies wird schnell zu einem sehr teuren Projekt. Der Grund ist, dass die IFFT nicht additiv Rauschwellen kombiniert, sondern Sinuskurven, aber Sinuskurven füllen das Energieleistungsspektrum nicht sehr effizient aus, da jede Sinuskurve eine Frequenz beeinflusst. Die Rauschfunktionen haben jedoch breite Spektren, die lange Frequenzintervalle mit einer einzelnen Welle abdecken. Sowohl Gradientenrauschen als auch Wertrauschen weisen so reiche und dichte Graphen der spektralen Dichte auf. Schauen Sie sich die Grafiken an:


Sinuswelle


Wert Rauschen


Gradientenrauschen
Beachten Sie, dass im Spektrum sowohl des Wertrauschens als auch des Gradientenrauschens der Großteil der Energie auf die niedrigeren Frequenzen konzentriert ist, jedoch breiter ist - eine ideale Wahl, um das gesamte Spektrum schnell mit mehreren versetzten und skalierten Kopien zu füllen. Ein weiteres Sinuswellen-fBM-Problem ist dieses. dass es natürlich wiederholte Pattene erzeugt, die meistens unerwünscht sind, obwohl sie nützlich sein können, um nahtlose Texturen zu erzeugen. Der Vorteil von fBM () basierend auf sin () ist, dass es überproduktiv ist, da trigonometrische Funktionen in Eisen viel schneller ausgeführt werden als Gebäuderauschen mit Polynomen und Hashes / Lut. Daher lohnt es sich manchmal immer noch , fBM basierend auf Sinuswellen von zu verwenden Leistungsüberlegungen, auch wenn schlechte Landschaften entstehen.

Schauen wir uns nun die Diagramme der Spektrendichte für fBM mit unterschiedlichen Werten von H an. Achten Sie besonders auf die Markierungen auf der vertikalen Achse, da alle drei Diagramme normalisiert sind und nicht die gleichen Steigungen beschreiben, obwohl sie auf den ersten Blick fast gleich aussehen. Wenn wir die negative Steigung dieser Spektraldiagramme als "B" bezeichnen, folgt das Spektrum einem Potenzgesetz der Form f-B, da diese Diagramme eine logarithmische Skala haben. In diesem Test verwende ich 10 Oktaven normales Gradientenrauschen, um das unten gezeigte fBM zu erstellen.


G = 1,0 (H = 0)


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


G = 0,5 (H = 1)

Wie wir sehen können, wird die Energie fBM mit H = 0 (G = 1) mit 3 dB pro Oktave oder tatsächlich mit einem Wert zurück auf die Frequenz gedämpft. Dies ist ein Potenzgesetz f ^-1 (B = 1), das als „rosa Rauschen“ bezeichnet wird und wie Regen klingt.

fBM () mit H = 1/2 (G = 0,707) erzeugt ein Spektrum, das mit 6 dB pro Oktave schneller gedämpft wird, dh weniger hohe Frequenzen aufweist. Es klingt tatsächlich tiefer, als ob Sie Regen hören, aber diesmal aus Ihrem Zimmer mit geschlossenen Fenstern. Die Dämpfung von 6 dB / Oktave bedeutet, dass die Energie proportional zu f ^{-2 ist} (B = 2), und dies ist tatsächlich eine Eigenschaft der Brownschen Bewegung im DSP.

Schließlich erzeugt unser Lieblings-fBM aus Computergrafiken mit H = 1 (G = 0,5) einen Spektraldichtegraphen mit einem Abfall von 9 dB / Oktave, dh die Energie ist umgekehrt proportional zum Frequenzwürfel (f ^-3 , B = 3). Dies ist ein Signal mit einer konstant niedrigen Frequenz, das einem Prozess mit positivem Korrelationsspeicher entspricht, über den wir zu Beginn gesprochen haben. Diese Art von Signal hat keinen eigenen Namen, daher habe ich die Versuchung, es als „gelbes Rauschen“ zu bezeichnen (einfach, weil dieser Name für nichts mehr verwendet wird). Wie wir wissen, ist es isotrop, was bedeutet, dass es viele sich selbst wiederholende natürliche Formen modelliert.

Tatsächlich werde ich meine Worte über die Ähnlichkeit mit der Natur bestätigen, indem ich die im nächsten Abschnitt des Artikels angegebenen Messungen vornehme.

Titel	H.	G = 2 -H	B = 2H + 1	dB / Okt.	Ton
Blau	- -	- -	+1	+3	Wasser sprühen. Link
Weiß	- -	- -	0	0	Wind in den Blättern. Link
Pink	0	1	-1	-3	Der Regen. Link
Braun	1/2	sqrt (2)	-2	-6	Regen von zu Hause gehört. Link
Gelb	1	1/2	-3	-9	Motor hinter der Tür

Messungen

Zuerst muss ich Sie warnen, dass es ein sehr unwissenschaftliches Experiment sein wird, aber ich möchte es trotzdem teilen. Ich habe Bergketten parallel zur Bildebene fotografiert, um perspektivische Verzerrungen zu vermeiden. Dann habe ich die Bilder in Schwarzweiß unterteilt und dann die Kontaktfläche von Himmel und Bergen in ein 1D-Signal umgewandelt. Dann interpretierte ich es als WAV-Sounddatei und berechnete seinen Frequenzgraphen, wie es bei den oben analysierten synthetischen fBM () -Signalen der Fall ist. Ich habe Bilder mit einer ausreichend hohen Auflösung ausgewählt, damit der FFT-Algorithmus signifikante Daten für die Arbeit enthält.


Quelle: Griechischer Reporter


Quelle: Wikipedia







Es scheint, dass die Ergebnisse wirklich darauf hinweisen, dass die Bergprofile einer Häufigkeitsverteilung von -9 dB / Oktave folgen, was B = -3 oder H = 1 oder G = 0,5 oder mit anderen Worten gelbem Rauschen entspricht.

Natürlich war das Experiment nicht streng, aber es bestätigt unser intuitives Verständnis und das, was wir bereits aus Erfahrung und Arbeit mit Computergrafiken wissen. Aber ich hoffe jetzt haben wir begonnen, dies besser zu verstehen!