Gibt es eine (Familie von) monoton nicht abnehmenden Rauschfunktionen?

10

Ich möchte, dass eine Funktion ein Objekt animiert, das sich im Laufe der Zeit von Punkt A nach Punkt B bewegt, so dass es zu einem festgelegten Zeitpunkt B erreicht, seine Position jedoch zu jeder Zeit zufällig kontinuierlich gestört wird, aber niemals rückwärts geht. Die Objekte bewegen sich entlang gerader Linien, daher benötige ich nur eine Dimension.

Mathematisch bedeutet das, dass ich nach einem stetigen f (x), x ∈ [0,1] suche, so dass:

  • f (0) = 0
  • f (1) = 1
  • x <y → f (x) ≤ f (y)
  • An "den meisten" Punkten hat f (x + d) - f (x) keine offensichtliche Beziehung zu d. (Die Funktion nimmt nicht gleichmäßig zu oder ist auf andere Weise vorhersehbar. Ich denke, das entspricht auch der Aussage, dass kein Grad der Ableitung eine Konstante ist.)

Idealerweise möchte ich tatsächlich eine Möglichkeit haben, eine Familie dieser Funktionen zu haben, die einen Samenzustand liefert. Ich würde für meine derzeitige Verwendung mindestens 4 Bit Seed (16 mögliche Funktionen) benötigen, aber da dies nicht viel ist, können Sie noch mehr bereitstellen.

Um verschiedene Probleme mit Akkumulationsfehlern zu vermeiden, würde ich es vorziehen, wenn die Funktion keinen internen Status erfordert. Das heißt, ich möchte, dass es eine echte Funktion ist, keine programmierende "Funktion".


quelle
3
Ihre dritte und vierte Anforderung kann als angenähert werden f'(x)>0, sodass die normalisierte Integration des Absolutwerts einer Rauschfunktion alle Ihre Anforderungen erfüllt. Leider kenne ich keine einfache Möglichkeit, das zu berechnen, aber vielleicht tut es jemand anderes. :)
SkimFlux
Würde eine Störung der Senkrechten Ihrer Funktion eine sofortige Neigung bewirken?
kaoD
Wenn Sie sagen "Um verschiedene Probleme mit Akkumulationsfehlern zu vermeiden", dachte ich, Sie machen sich Sorgen um die Präzision. Aufgrund Ihrer zahlreichen Kommentare scheinen Sie sich mit den Leistungskosten übermäßig vieler Bewertungen zu befassen. Sie sollten genau angeben, welchen Leistungs- und Speicherbeschränkungen wir unterliegen - die Anforderung ist ohnehin nicht hilfreich, da man scheinbar Funktionen mit Status konstruieren kann, die keine Akkumulationsfehler aufweisen (Was bedeutet das überhaupt?). Auch Ihr 4. Punkt ist falsch. Ein triviales Beispiel: Keine Ableitung von e ^ x ist konstant, also ist es nicht gleichbedeutend damit, das zu sagen.
Superbest

Antworten:

4

Für diesen Beitrag ist y = f (t), wobei t der Parameter ist, den Sie variieren (Zeit / Fortschritt) und y die Entfernung zum Ziel ist. Ich werde also in Bezug auf Punkte auf 2D-Plots sprechen, bei denen die horizontale Achse Zeit / Fortschritt und die vertikale Achse Entfernung ist.

Ich denke, Sie können eine kubische Bezier-Kurve mit dem ersten Punkt bei (0, 1) und dem vierten (letzten) Punkt bei (1, 0) erstellen. Die beiden Mittelpunkte können zufällig (x = Rand, y = Rand) innerhalb dieses 1-mal-1-Rechtecks ​​platziert werden. Ich kann dies nicht analytisch überprüfen, aber wenn ich nur mit einem Applet herumspiele (ja, mach weiter und lache), scheint es, dass die Bezier-Kurve mit einer solchen Einschränkung niemals abnehmen wird.

Dies ist Ihre Elementarfunktion b (p1, p2), die einen nicht abnehmenden Pfad von Punkt p1 zu Punkt p2 bereitstellt.

Jetzt können Sie ab (p (1) = (0, 1), p (n) = (1, 0)) erzeugen und eine Anzahl von p (i) entlang dieser Kurve so auswählen, dass 1

Im Wesentlichen generieren Sie einen "allgemeinen" Pfad, teilen ihn dann in Segmente auf und generieren jedes Segment neu.

Da Sie eine mathematische Funktion wünschen: Angenommen, die obige Prozedur ist in eine Funktion y = f (t, s) gepackt, die Ihnen den Abstand bei t für die Funktion des Samens s gibt. Du wirst brauchen:

  • 4 Zufallszahlen zum Platzieren der 2 Mittelpunkte des Haupt-Bezier-Splines (von (0, 1) bis (1, 0))
  • n-1 Zahlen für die Grenzen jedes Segments, wenn Sie n Segmente haben (das erste Segment beginnt immer bei (0, 1), dh t = 0, und das letzte endet bei (1,0), dh t = 1)
  • 1 Zahl, wenn Sie die Anzahl der Segmente zufällig bestimmen möchten
  • 4 weitere Zahlen zum Platzieren der Mittelpunkte des Splines des Segments, auf dem Sie landen

Jeder Samen muss also eines der folgenden liefern:

  • 7 + n reelle Zahlen zwischen 0 und 1 (wenn Sie die Anzahl der Segmente steuern möchten)
  • 7 reelle Zahlen und eine ganze Zahl größer als 1 (für eine zufällige Anzahl von Segmenten)

Ich kann mir vorstellen, dass Sie beides erreichen können, indem Sie einfach eine Reihe von Zahlen als Startwerte angeben. Alternativ können Sie beispielsweise eine Zahl s als Startwert angeben und dann den integrierten Zufallszahlengenerator mit rand (s), rand (s + 1), rand (s + 2) usw. aufrufen (oder mit initialisieren) s und rufen Sie dann rand.NextNumber weiter auf.

Beachten Sie, dass Sie, obwohl die gesamte Funktion f (t, s) aus vielen Segmenten besteht, nur ein Segment für jedes t auswerten. Sie werden müssen wiederholt die Grenzen der Segmente mit dieser Methode berechnen, weil Sie sie sortieren müssen sicherstellen , dass keine zwei Segmente überlappen. Sie können diese zusätzliche Arbeit wahrscheinlich optimieren und loswerden und nur die Endpunkte eines Segments für jeden Anruf finden, aber es ist mir momentan nicht klar.

Bezier-Kurven sind ebenfalls nicht erforderlich, ein sich entsprechend verhaltender Spline reicht aus.

Ich habe eine Matlab-Beispielimplementierung erstellt.

Die Bezier-Funktion (vektorisiert):

function p = bezier(t, points)
% p = bezier(t, points) takes 4 2-dimensional points defined by 2-by-4 matrix
% points and gives the value of the Bezier curve between these points at t.
% 
% t can be a number or 1-by-n vector. p will be an n-by-2 matrix.
    coeffs = [
        (1-t').^3, ...
        3*(1-t').^2.*t', ...
        3*(1-t').*t'.^2, ...
        t'.^3
    ];

    p = coeffs * points;
end

Die oben beschriebene zusammengesetzte Bezier-Funktion (absichtlich unentdeckt gelassen, um zu verdeutlichen, wie viel Auswertung für jeden Aufruf erforderlich ist):

function p = bezier_compound(t, ends, s)
% p = bezier(t, points) takes 2 2-dimensional endpoints defined by a 2-by-2
% matrix ends and gives the value of a "compound" Bezier curve between
% these points at t.
% 
% t can be a number or 1-by-n vector. s must be a 1-by-7+m vector of random
% numbers from 0 to 1. p will be an n-by-2 matrix. 
    %% Generate a list of segment boundaries
    seg_bounds = [0, sort(s(9:end)), 1];

    %% Find which segment t falls on
    seg = find(seg_bounds(1:end-1)<=t, 1, 'last');

    %% Find the points that segment boundaries evaluate to
    points(1, :) = ends(1, :);
    points(2, :) = [s(1), s(2)];
    points(3, :) = [s(3), s(4)];
    points(4, :) = ends(2, :);

    p1 = bezier(seg_bounds(seg), points);
    p4 = bezier(seg_bounds(seg+1), points);

    %% Random middle points
    p2 = [s(5), s(6)] .* (p4-p1) + p1;
    p3 = [s(7), s(8)] .* (p4-p1) + p1;

    %% Gather together these points
    p_seg = [p1; p2; p3; p4];

    %% Find what part of this segment t falls on
    t_seg = (t-seg_bounds(seg))/(seg_bounds(seg+1)-seg_bounds(seg));

    %% Evaluate
    p = bezier(t_seg, p_seg);    
end

Das Skript, das die Funktion für einen zufälligen Startwert darstellt (beachten Sie, dass dies der einzige Ort ist, an dem eine zufällige Funktion aufgerufen wird. Die Zufallsvariablen werden von diesem einen zufälligen Array an alle anderen Codes weitergegeben):

clear
clc

% How many samples of the function to plot (higher = higher resolution)
points = 1000;

ends = [
    0, 0;
    1, 1;
    ];

% a row vector of 12 random points
r = rand(1, 12);

p = zeros(points, 2);

for i=0:points-1
    t = i/points;
    p(i+1, :) = bezier_compound(t, ends, r);
end

% We take a 1-p to invert along y-axis here because it was easier to
% implement a function for slowly moving away from a point towards another.
scatter(p(:, 1), 1-p(:, 2), '.');
xlabel('Time');
ylabel('Distance to target');

Hier ist eine Beispielausgabe:

Geben Sie hier die Bildbeschreibung ein

Es scheint die meisten Ihrer Kriterien zu erfüllen. Jedoch:

  • Es gibt "Ecken". Dies kann durch geeignete Verwendung von Bezier-Kurven möglich sein.
  • Es sieht "offensichtlich" wie Splines aus, obwohl Sie nicht wirklich erraten können, was es nach einer nicht trivialen Zeit tun wird, wenn Sie den Samen nicht kennen.
  • Es weicht sehr selten zu stark in Richtung Ecke ab (kann durch Spielen mit der Verteilung des Saatgutgenerators behoben werden).
  • Die kubische Bezier-Funktion kann aufgrund dieser Einschränkungen keinen Bereich in der Nähe der Ecke erreichen.
Superbest
quelle
1

Ich denke, anstatt eine Reihe transformierter Cosinus zu mischen (wie es die Punktprodukte im Perlin-Rauschen geben), könnten Sie mehrere monotone Funktionen mischen, die bei f (0) = 0 beginnen, wie f (x) = x oder 2x, oder x ^ 2 usw. Da Ihre Domain auf 0 => 1 beschränkt ist, können Sie auch Triggerfunktionen einblenden, die wie cos (90 * x + 270) zur Rechnung innerhalb dieser Domain passen. Um Ihre Methoden so zu normalisieren, dass sie bei 1 enden, können Sie einfach die gewichtete Summe dieser monotonen Methoden beginnend bei f (0) = 0 durch f (1) teilen. So etwas sollte auch ziemlich einfach zu invertieren sein (was ich von dem Punkt über zustandslose reale Funktionen im Vergleich zu Programmierfunktionen möchte).

Hoffe das hilft.

Gary Dahl
quelle
1

Man kann dieses grobe Bild analysieren. Geben Sie hier die Bildbeschreibung ein Sie können eine Funktion erhalten, die Ihre Animation im laufenden Betrieb ausführt, indem Sie eine einheitliche Rand-Funktion verwenden. Ich weiß, dass dies nicht die exakte mathematische Formel ist, aber es gibt tatsächlich keine mathematische Formel für eine Zufallsfunktion, und selbst wenn es eine gäbe, würden Sie viel codieren, um dies zu erreichen. Da Sie keine Bedingungen für die Laufruhe angegeben haben, ist das Geschwindigkeitsprofil $ C ^ 0 $ kontinuierlich (da Sie sich jedoch nicht mit Robotern befassen, müssen Sie sich keine Gedanken über diskontinuierliche Beschleunigungsprofile machen).

Teodron
quelle
"Es gibt eigentlich keine mathematische Formel für eine Zufallsfunktion" Ich möchte eine Rauschfunktion, keine Zufallsfunktion. Es ist gut dokumentiert, dass Rauschfunktionen vorhanden sind. Stückweise Definitionen wie diese neigen auch dazu, entweder Ineffizienz (Auswertung wird zu O (Stücke), was bei langen Zeitskalen zu einem Problem wird), unreine Funktionen (Auswertung in O (1), muss aber die vorherige Position beibehalten) oder Über- mögliche Funktionen einschränken (z. B. liegen alle Wendepunkte in festen Intervallen).
Hmm, sorry, ich dachte, dass Rauschfunktionen auch eine Zufallszahlengeneratorprozedur verwenden und dass diese auch von einem diskreten Satz von Führungs- / Schlüsselpunkten abhängen, um eine Form zu erhalten (ich sah, dass Perlin Noise erwähnt wurde .. dass man über Pseudozufalls arbeitet Zahlengeneratoren, die ziemlich schwer zu integrieren sind, daher keine analytische Lösung). Kann man eine Rauschfunktion analytisch integrieren? Ich frage mich , ob einer von ihnen könnte ein Kandidat Link
teodron
Perlin-Rauschen nimmt beispielsweise einen Startzustand von 255 8-Bit-Zahlen an, erzeugt jedoch zufälliges Rauschen in unendlicher Entfernung in drei Dimensionen. Es ist nicht wirklich genau, sie als "Leitpunkte" zu beschreiben. Mathematisch sind sie eher weitere 256 Parameter, die Sie nicht weiter bereitstellen möchten. Wie Sie sagen, ist es im Wesentlichen nicht integrierbar, aber es ist eine reine Funktion. Die Seite, auf die Sie verlinkt haben, ist eine schlechte Erklärung für Perlin-Rauschen (es ist nicht wirklich Perlin-Rauschen, das er erklärt). Ob es für irgendeine Art von Rauschfunktion möglich ist ... nun, das ist die Frage, nicht wahr?
1

Die übliche Art, eine zunehmende Folge von N Zufallszahlen aus [0,1] zu erzeugen, besteht darin, N Zufallszahlen in einem beliebigen Bereich zu erzeugen, sie dann alle durch ihre Gesamtsumme zu dividieren und sie dann einzeln zu summieren, um die zu erhalten Reihenfolge.

Generieren Sie die Sequenz 2, 2, 5, 8, 6.
Ihre Summe ist 23, also sind unsere Zahlen 2/23, 2/23, 5/23, 8/23 und 6/23.
Unsere letzte Sequenz ist 2/23, 4/23, 9/23, 17/23, 23/23

Dies kann durch Generieren dieser Werte für X und Y auf 2D erweitert werden. Sie können N erhöhen, um die gewünschte Granularität zu erhalten.


In der ähnlichen Antwort von @ teodron haben Sie Effizienzprobleme mit großen Zeitskalen angeführt. Ohne das eigentliche Problem zu kennen, kann ich nicht sagen, ob dieses Anliegen berechtigt ist. Eine andere Möglichkeit wäre, für kleines N zu generieren und das Ergebnis einfach zu glätten. Je nach Anwendung kann dies tatsächlich zu besseren Ergebnissen führen.

Geben Sie hier die Bildbeschreibung ein
N = 100, keine Glättung

Geben Sie hier die Bildbeschreibung ein
N = 15 mit Glättung

BlueRaja - Danny Pflughoeft
quelle
Was auch immer Sie für die Glättung tun, es scheint, dass das Ergebnis nicht einmal eine Funktion ist (um x = 0,95); Ich bin mir nicht sicher, ob dies ein Artefakt Ihres Grafikprogramms oder ein Fehler ist. Die Monotonie scheint auch um 0,7 verletzt zu sein. Wie auch immer, ich bin mit "dem üblichen Weg" vertraut - ich stelle diese Frage, weil ich vermute, dass der übliche Weg beschissen ist. Pre-Perlin-Rauschen, schließlich hatte niemand ein Problem mit riesigen LUTs von Wertrauschen, es war nur "der übliche Weg". Heute haben wir einen Weg, der wesentlich flexibler und effizienter ist.
3
Ich stimme BlueRaja zu: Es gibt bekannte, einfach zu implementierende Methoden zum Glätten, ohne die Monotonie zu verletzen, unabhängig vom Beispiel. Zum Beispiel gleitender Durchschnitt oder Zeichnen von Splines. Das Anliegen von @JoeWreschnig ist jedoch nicht irrelevant. Spielregeln und -mechaniken können von Objekten abhängen, die sich niemals zurückziehen, um zu funktionieren. Es ist selten eine gute Idee anzunehmen, dass Dinge, die der Fragesteller nicht wirklich braucht, was er sagt, dass er braucht.
Superbest
1
@BlueRaja: Meine grundlegenden Beschwerden über solche stückweisen Ansätze sind in meiner Antwort auf Teodrone beschrieben. Es geht nicht darum, "das starrste und mathematisch genaueste Ergebnis" zu finden - es geht darum, mit einem uns bisher unbekannten mathematischen Werkzeug neue Möglichkeiten zu eröffnen. Betrachten Sie erneut die Analogie zwischen Riesenwert-Rausch-LUTs und Perlin-Rauschen. Nicht jede Frage auf der Website muss von Anfang an "gut genug" beantwortet werden. Jeder halbwegs intelligente CS-Student könnte zwischen den Vorlesungen herausspringen - manchmal lasst uns fotografieren, um etwas Originelles und Professionelles zu tun, okay?
1
Oder wir könnten diese Seite einfach weiter in 90% elementarer Verwirrung über Transformationsmatrizen schwelgen lassen, 10% "hilf mir, keine Spiele mehr zu spielen!" Das macht eine großartige Q & A-Site, zu der jeder Profi gerne kommen wird.
2
@ Joe: Das ist, ähm, unangebracht. Sie haben nach einer Lösung gefragt, die Ihren Kriterien entspricht. Ich habe Ihnen eine gegeben. Nur weil es einfach ist, macht es nicht schlecht.
BlueRaja - Danny Pflughoeft
1

Ich schlage diese Implementierung vor, die von der Summe der Oktaven inspiriert ist, die im fraktalen Rauschen zu finden sind, wobei hier und da ein bisschen billiger Arsch schlurft. Ich glaube, es ist ziemlich schnell und kann eingestellt werden, indem weniger Oktaven als in den Parametern gespeichert werden, mit einem Genauigkeitsverlust von ungefähr 1/2^octave.

Sie können es als stückweise Implementierung betrachten, die nur O-Zeit (log (Teile)) benötigt . Das Parameterarray wird sowohl für die Pivot-Position zum Teilen und Erobern als auch für die zurückgelegte Strecke beim Erreichen des Pivots verwendet.

template<int N> struct Trajectory
{
    Trajectory(int seed = 0)
    {
        /* The behaviour can be tuned by changing 0.2 and 0.6 below. */
        if (seed)
            srand(seed);
        for (int i = 0; i < N; i++)
            m_params[i] = 0.2 + 0.6 * (double)(rand() % 4096) / 4096;
    }

    double Get(double t, int depth = N)
    {
        double min = 0.0, max = 1.0;
        for (int i = 0, dir = 0; i < N && i < depth; i++)
        {
            int j = (dir + 1 + i) % N;
            double mid = min + (max - min) * m_params[j];
            if (t < m_params[i])
            {
                dir += 1;
                t = t / m_params[i];
                max = mid;
            }
            else
            {
                dir ^= i;
                t = (t - m_params[i]) / (1.0 - m_params[i]);
                min = mid;
            }
        }
        t = (3.0 - 2.0 * t) * t * t; // Optional smoothing
        return min + (max - min) * t;
    }

    double m_params[N];
};

Dies könnte durch Vorberechnung der Gleitkommadivisionen beschleunigt werden, wobei dreimal so viele Informationen gespeichert werden.

Dies ist ein kurzes Beispiel:

fünf verschiedene Flugbahnen

Das Beispiel wurde mit dem folgenden Code erhalten:

for (int run = 0; run < 5; run++)
{
    /* Create a new shuffled trajectory */
    Trajectory<12> traj;

    /* Print dots */
    for (double t = 0; t <= 1.0; t += 0.0001)
        printf("%g %g\n", t, traj.Get(t));
}
Sam Hocevar
quelle
0

Laut denken und Kalkül zugeben ist nicht meine Stärke ... ist das vielleicht nicht möglich? Um ein offensichtliches Muster zu vermeiden, muss der Durchschnitt der Rauschfunktion über jede Änderung von x nahe Null sein, und um Monotonie zu gewährleisten, muss die Rauschamplitude über diese Änderung von x kleiner sein als die Änderung von x, wie es jede größere Amplitude könnte führen zu einem niedrigeren Wert bei x 'relativ zu x. Dies würde jedoch bedeuten, dass eine solche Funktion beim Reduzieren von dx gegen 0 auch dA (wobei A die Amplitude ist) gegen Null reduzieren muss, was bedeutet, dass Sie keinen Beitrag von einer kompatiblen Rauschfunktion erhalten.

Ich kann mir vorstellen, dass es möglich ist, eine Funktion zu formulieren, die den Rauschbeitrag allmählich verringert, wenn sich x 1 nähert, aber Ihnen eine gekrümmte Funktion gibt, die sich verlangsamt, wenn sich x 1 nähert, was meiner Meinung nach nicht das ist, was Sie wollen.

Kylotan
quelle
1
Ich kann Millionen von Graphen solcher Funktionen zeichnen, und wie SkimFlux sagt, ergibt die Integration einer Rauschfunktion eine praktisch äquivalente Funktion, wenn Sie sie normalisieren. Die Funktionen existieren also , es ist nur eine Frage, ob sie machbar codiert werden können . Daher hier anstelle von math.se fragen.
Zum Beispiel hat jede Funktion, die langsamer wird, wenn sich x 1 nähert, eine äquivalente "umgekehrte" Funktion g(x) = 1 - f(1 - x), die stattdessen beschleunigt, wenn x von 0 abweicht.
Sicher, die Funktionen existieren - Sie können eine zeichnen, wie es Teodron getan hat - aber sind es "Rausch" -Funktionen? Rauschen impliziert eine kontinuierliche Funktion, die auf einer pseudozufälligen Eingabe mit einer impliziten Amplitude relativ zu einer Grundlinie basiert. Und wenn diese Amplitude zu hoch ist, können Sie nicht garantieren, dass der Unterschied zwischen den Schritten niedrig genug ist, um den Ausgang monoton zu halten. Mir fällt jedoch ein, dass die Dichte des Rauschens und der Interpolationsschritt so gestaltet werden könnten, dass sie Ihren Spezifikationen entsprechen, über die ich etwas mehr nachdenken werde.
Kylotan
Rauschen bedeutet nur, dass es "unvorhersehbar" ist, es sagt nichts über die Generierungsmethoden aus (oder sogar technisch gesehen über Kontinuität, obwohl Sie für Animationen fast immer kohärentes Rauschen wünschen). Es ist wahr, dass die festen Endpunkte die mögliche Amplitude dieser Funktion etwas, aber nicht vollständig einschränken. Andere Rauschfunktionen haben ähnliche Eigenschaften, z. B. Perlin (x) = 0 für eine beliebige Ganzzahl x. Monotonie ist eine stärkere Garantie als diese, aber ich denke nicht, dass sie so viel stärker ist, dass es unmöglich wird.
@JoeWreschnig Ich bin mir sicher, dass Sie wissen, dass die Perlin-Rauschfunktion offensichtlich gegen mehrere Ihrer Kriterien verstößt. Erstens geht es an Gitterknoten durch 0, so dass f (x + d) -f (x) ein konstantes Vielfaches von d für ein bestimmtes (regelmäßig beabstandetes) x ist. Aufgrund dieses cleveren Caching-Tricks wird es außerdem für große Gitter wiederholt. Für klassisches Rauschen sollte die Referenzimplementierung eine Gitterkachel (x, y) haben, die mit der Kachel (x + 256, y + 256) identisch ist. Sie sollten angeben, ob und in welchem ​​Umfang dies akzeptabel ist.
Superbest