¿Existe una (familia de) función (es) de ruido monotónicamente no decreciente?

10

Me gustaría que una función anime un objeto que se mueve del punto A al punto B con el tiempo, de modo que llegue a B en un momento fijo, pero su posición en cualquier momento se perturba aleatoriamente de manera continua, pero nunca retrocede. Los objetos se mueven a lo largo de líneas rectas, por lo que solo necesito una dimensión.

Matemáticamente, eso significa que estoy buscando algunos f (x), x ∈ [0,1] continuos, de modo que:

  • f (0) = 0
  • f (1) = 1
  • x <y → f (x) ≤ f (y)
  • En "la mayoría" de los puntos f (x + d) - f (x) no tiene ninguna relación obvia con d. (La función no aumenta uniformemente ni es predecible; creo que eso también es equivalente a decir que ningún grado de derivada es una constante).

Idealmente, en realidad me gustaría tener alguna forma de tener una familia de estas funciones, proporcionando un estado de semilla. Necesitaría al menos 4 bits de semilla (16 funciones posibles), para mi uso actual, pero dado que no es mucho, siéntase libre de proporcionar aún más.

Para evitar varios problemas con los errores de acumulación, prefiero que la función no requiera ningún tipo de estado interno. Es decir, quiero que sea una función real, no una "función" de programación.


fuente
3
Su tercer y cuarto requisito se pueden aproximar como f'(x)>0, por lo que la integración normalizada del valor absoluto de cualquier función de ruido cumplirá todos sus requisitos. Lamentablemente, no conozco ninguna forma fácil de calcular eso, pero tal vez alguien más sí. :)
SkimFlux
¿Funcionaría perturbar la pendiente perpendicular de su función de pendiente instantánea?
kaoD
Cuando dice "Para evitar varios problemas con los errores de acumulación", pensé que estaba preocupado por la precisión. Parece que, en función de sus muchos comentarios, le preocupa el costo de desempeño de muchas evaluaciones excesivas. Debe indicar exactamente a qué restricciones de rendimiento y memoria estamos sujetos: el requisito no es útil de todos modos porque aparentemente se pueden construir funciones con un estado que no tiene errores de acumulación (¿Qué significa eso, de todos modos?). Además, su cuarto punto está mal. Un ejemplo trivial: ninguna derivada de e ^ x es constante, por lo que no es equivalente a decir eso.
Superbest

Respuestas:

4

Para esta publicación, y = f (t) donde t es el parámetro que usted varía (tiempo / progreso) e y es la distancia al objetivo. Así que hablaré en términos de puntos en diagramas 2D donde el eje horizontal es tiempo / progreso y el vertical es distancia.

Creo que puedes hacer una curva de Bezier cúbica con el primer punto en (0, 1) y el cuarto (último) punto en (1, 0). Los dos puntos medios se pueden colocar aleatoriamente (x = rand, y = rand) dentro de este rectángulo 1 por 1. No puedo verificar esto analíticamente, pero solo jugando con un applet (sí, adelante y riéndose) parece que la curva de Bezier nunca disminuirá con tal restricción.

Esta será su función elemental b (p1, p2) que proporciona una ruta no decreciente desde el punto p1 hasta el punto p2.

Ahora puede generar ab (p (1) = (0, 1), p (n) = (1, 0)) y elegir un número de p (i) a lo largo de esta curva de manera que 1

Esencialmente, está generando una ruta "general", y luego la divide en segmentos y regenera cada segmento.

Como desea una función matemática: Suponga que el procedimiento anterior está empaquetado en una función y = f (t, s) que le da la distancia en t para la función de la semilla s. Necesitará:

  • 4 números aleatorios para colocar los 2 puntos medios de la spline principal de Bezier (de (0, 1) a (1, 0))
  • n-1 números para los límites de cada segmento si tiene n segmentos (el primer segmento siempre comienza en (0, 1), es decir, t = 0 y el último termina en (1,0), es decir, t = 1)
  • 1 número si desea aleatorizar el número de segmentos
  • 4 números más para colocar los puntos medios de la spline del segmento en el que aterriza

Por lo tanto, cada semilla debe suministrar uno de los siguientes:

  • 7 + n números reales entre 0 y 1 (si desea controlar el número de segmentos)
  • 7 números reales y un número entero mayor que 1 (para un número aleatorio de segmentos)

Me imagino que puede lograr cualquiera de estos simplemente suministrando una serie de números como la semilla s. Alternativamente, podría hacer algo como suministrar un número s como semilla, y luego llamar al generador de números aleatorios incorporado con rand (s), rand (s + 1), rand (s + 2) y así sucesivamente (o inicializar con sy luego sigue llamando a rand.NextNumber).

Tenga en cuenta que aunque toda la función f (t, s) esté compuesta por muchos segmentos, solo está evaluando un segmento para cada t. Usted tendrá que calcular repetidamente los límites de los segmentos con este método, ya que tendrá que ordenarlos para asegurarse de que no hay dos segmentos se superponen. Probablemente pueda optimizar y deshacerse de este trabajo adicional y solo encontrar los puntos finales de un segmento para cada llamada, pero no es obvio para mí en este momento.

Además, las curvas de Bezier no son necesarias, cualquier spline que se comporte adecuadamente servirá.

Creé una implementación de muestra de Matlab.

La función Bezier (vectorizada):

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

La función de Bezier compuesta descrita anteriormente (se dejó deliberadamente sin vectorizar para dejar en claro cuánta evaluación se necesita para cada llamada):

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

El script que traza la función para una semilla aleatoria (tenga en cuenta que este es el único lugar donde se llama una función aleatoria, las variables aleatorias a todos los demás códigos se propagan desde esta matriz aleatoria):

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');

Aquí hay una muestra de salida:

ingrese la descripción de la imagen aquí

Parece cumplir con la mayoría de sus criterios. Sin embargo:

  • Hay "rincones". Esto puede ser manejable usando curvas de Bezier más apropiadamente.
  • "Obviamente" parece splines, aunque realmente no puedes adivinar lo que hará después de un período de tiempo no trivial a menos que conozcas la semilla.
  • Muy raramente se desvía demasiado hacia la esquina (se puede arreglar jugando con la distribución del generador de semillas).
  • La función de Bezier cúbico no puede alcanzar un área cerca de la esquina dadas estas restricciones.
Superbest
fuente
1

Supongo que en lugar de mezclar un montón de cosenos transformados (como los productos de punto en el ruido perlin te dan), podrías combinar varias funciones monotónicas que comienzan en f (0) = 0, como f (x) = x, o 2x, o x ^ 2, etc. De hecho, dado que su dominio está limitado a 0 => 1, también puede combinar funciones trigonométricas que se ajusten a la factura dentro de ese dominio como cos (90 * x + 270). Para normalizar sus métodos para terminar en 1, simplemente puede dividir la suma ponderada de estos métodos monotónicos comenzando en f (0) = 0 por f (1). Algo como esto también debería ser bastante fácil de invertir (lo que creo que quiere del bit sobre funciones reales sin estado versus funciones de programación).

Espero que esto ayude.

Gary Dahl
fuente
1

Uno puede analizar esta imagen cruda. ingrese la descripción de la imagen aquí Puede terminar con una función que realiza su animación sobre la marcha, utilizando una función de rand uniforme. Sé que esta no es la fórmula matemática exacta, pero en realidad no hay una fórmula matemática para una función aleatoria, e incluso si hubiera una, estarías codificando mucho para lograr esto. Teniendo en cuenta que no especificó ninguna condición de suavidad, el perfil de velocidad es $ C ^ 0 $ continuo (pero como no se trata de robots, no debe preocuparse por los perfiles de aceleración discontinuos).

teodron
fuente
"en realidad no hay una fórmula matemática para una función aleatoria" Quiero una función de ruido, no una función aleatoria. Las funciones de ruido están bien documentadas para existir. Las definiciones por partes como esta también tienden a crear ineficiencia (la evaluación se convierte en O (piezas) que se convierte en un problema cuando se tienen escalas de tiempo largas), funciones impuras (evaluar en O (1) pero necesita mantener la posición anterior) o restringir las posibles funciones (por ejemplo, todos los puntos de inflexión son a intervalos fijos).
Hmm, lo siento, pensé que las funciones de ruido también usan un procedimiento de generador de números aleatorios y que también dependen de un conjunto discreto de puntos de guía / clave para producir una forma (vi que se mencionaba el ruido de Perlin ... que funciona a través de pseudoaleatorio generadores de números que son bastante difíciles de integrar, por lo tanto, no hay solución analítica). ¿Se puede integrar una función de ruido analíticamente? Me pregunto si uno de estos podría ser un enlace
teodron
Como ejemplo, el ruido Perlin toma un estado inicial de 255 números de 8 bits, pero a partir de eso genera ruido aleatorio en una distancia infinita en tres dimensiones; no es realmente exacto describirlos como "puntos de guía", matemáticamente son más como otros 256 parámetros que no desea seguir proporcionando. Como dices, esencialmente no es integrable, pero es una función pura. La página a la que se vinculó es una mala explicación del ruido de Perlin (no explica realmente el ruido de Perlin). En cuanto a si es posible algún tipo de función de ruido ... bueno, esa es la pregunta, ¿no?
1

La forma habitual de generar una secuencia creciente de N números aleatorios a partir de [0,1] es generar N números aleatorios en cualquier rango, luego dividirlos por su suma total, luego sumar uno por uno para obtener el secuencia.

Genera la secuencia 2, 2, 5, 8, 6.
Su suma es 23, por lo que nuestros números para sumar son 2/23, 2/23, 5/23, 8/23 y 6/23.
Nuestra secuencia final es 2/23, 4/23, 9/23, 17/23, 23/23

Esto puede extenderse a 2D generando estos valores para X e Y. Puede aumentar N para obtener la granularidad que desee.


En la respuesta similar de @teodron, usted citó preocupaciones de eficiencia con grandes escalas de tiempo. Sin saber el problema real que enfrenta, no puedo decir si esa preocupación es válida; pero otra opción sería generar un N pequeño y simplemente suavizar el resultado. Dependiendo de la aplicación, esto puede dar mejores resultados.

ingrese la descripción de la imagen aquí
N = 100, sin suavizado

ingrese la descripción de la imagen aquí
N = 15, con suavizado

BlueRaja - Danny Pflughoeft
fuente
Lo que sea que esté haciendo para suavizar, parece haber hecho que el resultado ni siquiera sea una función (alrededor de x = 0.95); No estoy seguro de si es un artefacto de su programa de gráficos o un error. La monotonicidad también parece ser violada alrededor de 0.7. De todos modos, estoy familiarizado con "la forma habitual". Estoy haciendo esta pregunta porque sospecho que la forma habitual es horrible. El ruido previo a Perlin, después de todo, nadie tenía un problema con las LUT gigantescas de ruido de valor, era "la forma habitual". Hoy, tenemos una forma que es considerablemente más flexible y eficiente.
3
Estoy de acuerdo con BlueRaja: existen formas conocidas y fáciles de implementar de suavizado sin violar la monotonicidad, independientemente del ejemplo. Por ejemplo, promedio móvil o dibujar splines. Sin embargo, la preocupación de @JoeWreschnig no es irrelevante. Las reglas y la mecánica del juego pueden depender de que los objetos nunca se retiren para funcionar: rara vez es una buena idea suponer que las cosas que el autor de la pregunta realmente no necesita lo que dice que necesita.
Superbest
1
@BlueRaja: Mis quejas básicas sobre enfoques por partes como esta se describen en mi respuesta a teodrone. No se trata de encontrar "el resultado más rígido y matemáticamente preciso", se trata de abrir nuevas posibilidades con una herramienta matemática previamente desconocida para nosotros. Nuevamente, considere la analogía entre las LUT de ruido de valor gigante y el ruido de Perlin. No todas las preguntas en el sitio necesitan una respuesta "lo suficientemente buena" como cualquier otra estudiante inteligente de CS a medio camino que pueda golpear entre conferencias; a veces, disparemos para hacer algo original y profesional, ¿de acuerdo?
1
O podríamos seguir dejando que este sitio se revuelva en un 90% de confusión elemental sobre las matrices de transformación, un 10% "¡ayúdenme a dejar de jugar!" Eso hará que sea un sitio increíble de preguntas y respuestas que a todos los profesionales les encantará visitar.
2
@ Joe: Eso, erm, no es necesario. Usted pidió una solución que se ajustara a sus criterios, yo le di una. El hecho de que sea simple no lo hace malo.
BlueRaja - Danny Pflughoeft
1

Sugiero esta implementación inspirada en la suma de octavas encontradas en el ruido fractal, con un poco de culo barato revoloteando aquí y allá. Creo que es razonablemente rápido y se puede ajustar pidiendo menos octavas que las almacenadas en los parámetros con una pérdida de precisión de aproximadamente 1/2^octave.

Podrías verlo como una implementación por partes que solo requiere O (log (piezas)) . La matriz de parámetros se usa tanto para la posición de pivote de dividir y conquistar como para la distancia recorrida al alcanzar el pivote.

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

Podría hacerse más rápido calculando previamente las divisiones de coma flotante, a costa de almacenar el triple de información.

Este es un ejemplo rápido:

cinco trayectorias diferentes

El ejemplo se obtuvo con el siguiente código:

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
fuente
0

Pensar en voz alta y admitir que el cálculo no es mi punto fuerte ... ¿acaso esto no es posible? Para evitar cualquier patrón obvio, el promedio de la función de ruido sobre cualquier cambio en x debe ser cercano a cero, y para garantizar la monotonicidad, la amplitud del ruido sobre ese cambio en x debe ser menor que el cambio en x, ya que cualquier amplitud mayor podría resultar en un valor más bajo en x 'en relación a x. Pero eso significaría que a medida que reduce dx hacia 0, dicha función también debe reducir dA (donde A es la amplitud) hacia cero, lo que significa que no obtendrá ninguna contribución de ninguna función de ruido compatible.

Me imagino que es posible formular una función que disminuya gradualmente la contribución del ruido a medida que x se acerca a 1, pero eso le dará una función curva que se desacelera a medida que x se acerca a 1, que no es lo que creo que desea.

Kylotan
fuente
1
Puedo dibujar millones de gráficos de tales funciones, y como dice SkimFlux, la integración de una función de ruido proporciona una función prácticamente equivalente si la normaliza. Entonces, las funciones existen , es solo cuestión de si pueden ser codificadas de manera factible . Por lo tanto, preguntar aquí en lugar de math.se.
Por ejemplo, cualquier función que desacelera cuando x se acerca a 1 tiene una función equivalente "invertida" g(x) = 1 - f(1 - x), que en cambio acelera a medida que x sale 0.
Claro, las funciones existen, puedes dibujar una como lo hizo Teodron, pero ¿son funciones de 'ruido'? El ruido implica una función continua basada en una entrada pseudoaleatoria con una amplitud implícita relativa a una línea base. Y si esa amplitud es demasiado alta, no puede garantizar que la diferencia entre los pasos sea lo suficientemente baja como para mantener la salida monótona. Pero se me ocurre que la densidad del ruido y el paso de interpolación podrían diseñarse para cumplir con sus especificaciones, sobre lo que voy a pensar un poco más.
Kylotan
El ruido solo significa que es "impredecible", no dice nada sobre los métodos de generación (o incluso, técnicamente, la continuidad, aunque para la animación casi siempre se desea un ruido coherente). Es cierto que los puntos finales fijos limitan un poco la amplitud posible de esta función, pero no del todo. Otras funciones de ruido tienen propiedades similares, por ejemplo, Perlin (x) = 0 para cualquier número entero x. La monotonicidad es una garantía más fuerte que eso, pero no creo que sea mucho más fuerte que lo haga imposible.
@JoeWreschnig Estoy seguro de que sabe que la función de ruido Perlin viola abiertamente varios de sus criterios. En primer lugar, pasa a través de 0 en los nodos de la cuadrícula, por lo que f (x + d) -f (x) es un múltiplo constante de d para cierta x (espaciada regularmente) x. Además, debido a ese ingenioso truco de almacenamiento en caché, se repetirá para cuadrículas grandes. Para el ruido clásico, creo que la implementación de referencia debe tener un mosaico de cuadrícula (x, y) que sea idéntico al mosaico (x + 256, y + 256). Debe indicar si esto es aceptable y en qué medida.
Excelente