Ruido aleatorio basado en semilla

16

Actualmente estoy trabajando en un programa que debería generar ruido aleatorio en una pantalla basada en las 'coordenadas' de un píxel. Las coordenadas deben tener el mismo color cada vez que reinicie el programa. Sin embargo, usando el util.Random de Java, los resultados que obtengo no son tan aleatorios como me gustaría:

imprimir pantalla

Pensé que si usaba las coordenadas combinadas (como en un entero formado a partir de ambas coordenadas una al lado de la otra) cada coordenada tendría un número diferente. Al usar ese número como semilla, esperaba obtener un número aleatorio diferente para cada coordenada que se usaría para el valor rgb de esa coordenada.

Este es el código que usé:

public class Generate {

static Random Random;

    public static int TileColor(int x, int y){          
        Random = new Random(Integer.valueOf(Integer.toString(x)+Integer.toString(y)));
        int b = 1 + Random.nextInt(50);
        int g = 1 + Random.nextInt(50);
        int r = 1 + Random.nextInt(50);
        int color = -Color.rgb888(r, g, b);
        return color;
    }
}

¿El patrón que crea el programa se debe a la forma en que funciona la función Aleatoria de Java o estoy haciendo algo mal? ¿Debería intentar un enfoque diferente?

Actualización: ahora intenté deshacerme de los problemas relacionados con la concatenación utilizando el siguiente código:

public static int TileColor(int x, int y){  
            Randomy = new Random(y);
            Randomx = new Random(x);
            Random = new Random(Integer.valueOf(Integer.toString(Randomx.nextInt(1234))+Integer.toString(Randomy.nextInt(1234))));
            int b = 1 + Random.nextInt(100);
            int g = 1 + Random.nextInt(100);
            int r = 1 + Random.nextInt(100);
            int color = -Color.rgb888(r, g, b);
            return color;
}

De alguna manera, esto también proporcionó (en mi opinión) una imagen suficientemente aleatoria:

mew image

Sin embargo, este código se reinicia tres veces por píxel. Aunque esto no es un problema para mí en este momento, considero cambiar este código en caso de que necesite una mejor actuación más adelante.

libélula
fuente
3
No estoy seguro acerca de Random de Java, pero estoy bastante seguro de que no es realmente aleatorio ... Leer en.wikipedia.org/wiki/Pseudorandom_number_generator Entenderás por qué ves esos patrones.
Salketer
23
Algo crucial que falta en las otras respuestas: no reiniciar el RNG por cada píxel. Siembra una vez y genera valores consecutivos para todos los píxeles de tu imagen basados ​​en eso.
Konrad Rudolph
44
Nota: un número de pseudoaleatorio generaot puede estar distribuido uniformemente en una dimensión , pero falla cuando se usa más de una dimensión ... efectivamente está generando puntos en 3D (r, gyb y 3 coordenadas diferentes) por lo que necesita un generador aleatorio que garantiza no solo que los valores que genera están distribuidos uniformemente, sino que también los tripletes que genera están distribuidos uniformemente en el espacio 3D.
Bakuriu
66
@Bakuriu Si X, Y y Z son variables aleatorias uniformes independientes, entonces estoy bastante seguro (X, Y, Z) es uniforme en el espacio 3d.
Jack M
2
Podrías experimentar usando diferentes RNG, como el Mersenne Twister .
Kevin

Respuestas:

21

La java.util.Randomclase de Java generalmente te proporciona secuencias de números pseudoaleatorios que son lo suficientemente buenos para usar en los juegos 1 . Sin embargo, esa característica solo se aplica a una secuencia de muestras múltiples basadas en una semilla. Cuando reinicializa el RNG con valores de semilla incrementales y solo mira el primer valor de cada secuencia, las características de aleatoriedad no serán tan buenas.

Lo que podrías hacer en su lugar:

  • Use la misma semilla para generar fragmentos enteros de píxeles a la vez. Por ejemplo, cuando necesita el valor de color del píxel 425: 487, alimente las coordenadas 400: 400 en el RNG, genere 10000 colores aleatorios y use el color en el índice 2587 (25 * 100 + 87). Los fragmentos generados de esa manera deben almacenarse en caché para evitar volver a generar esos 10000 colores aleatorios por cada píxel de ese fragmento.
  • En lugar de usar un generador de números aleatorios, use una función de resumen de mensaje para convertir un par de coordenadas en un valor de color. El resultado de la mayoría de los MDF es lo suficientemente impredecible como para cumplir con la mayoría de las pruebas de aleatoriedad. La salida suele ser superior a los 24 bits que necesita para un valor RGB, pero truncarlos no suele ser un problema.

    Para mejorar el rendimiento, puede combinar la generación de resumen de mensajes con fragmentos. Genere pequeños fragmentos de píxeles que sean lo suficientemente grandes como para utilizar la longitud total de una salida de su función de resumen.

1 cuando es absolutamente esencial que nadie pueda predecir el próximo número, use el más lento pero menos predeciblejava.security.SecureRandom

Philipp
fuente
13

Las coordenadas deben tener el mismo color cada vez que reinicie el programa.

En ese caso, querrás usar una función de ruido determinista como el ruido Perlin o el ruido simplex .

( Consulte esta pregunta para obtener más información sobre el ruido Perlin con algunas imágenes bonitas ) .

En su mayor parte, el uso de una función incorporada random()o similar le dará diferentes valores cada vez que ejecute el programa, ya que pueden usar el reloj como entrada o algún otro valor pseudoaleatorio.

Otra opción es generar un "mapa de ruido" una vez, sin conexión, y luego usarlo como fuente de números aleatorios más adelante.

En su implementación, está concatenando las representaciones de cadena de x y y. Eso es malo, ya que no es único en todo el dominio. Por ejemplo,

x    y   concatenated
40   20  4020
402   0  4020
10   10  1010
101   0  1010
12   34  1234
123   4  1234
1   234  1234

¡Buena suerte!

3Dave
fuente
1
Buen punto sobre los números concatenados. Sin embargo, el programa siempre da exactamente el mismo resultado si ejecuto el programa varias veces. También he considerado el ruido perlin / simplex, podría echarle un vistazo y ver si funciona mejor. Sin embargo estoy seguro de por qué aún no Java no crear patrones, para no parece que el problema de la concatenación de resolver por completo
la libélula
1
¿No es suficiente simplemente sembrar aleatoriamente con un valor de semilla constante antes de generar los píxeles?
Jack M
1
@JackM Eso depende completamente del algoritmo PRNG en juego.
3Dave
44
"Una vez vi una implementación de rand () que usaba cada valor como semilla para el siguiente valor". ¿No es así como funcionan la mayoría de los generadores de números pseudoaleatorios no criptográficos? Utilizan el número aleatorio anterior (o estado) como entrada para generar el siguiente número / estado aleatorio.
JAB
2
@DavidLively Prácticamente todos los PRNG hacen esto o algo equivalente, a menos que su estado interno sea mayor que el rango de números que generan (por ejemplo, los trabalenguas de Mersenne), e incluso entonces la secuencia de números aleatorios está determinada por completo por la semilla.
Konrad Rudolph
9

Veamos qué estás haciendo exactamente:

  • Recorres todos los píxeles uno por uno
  • Para cada píxel, usa la concatenación de sus coordenadas como semilla
  • Luego comienza un nuevo azar de la semilla dada y saca 3 números

Todo esto suena bien, pero está recibiendo un patrón porque:

El píxel en 1,11 y el píxel en 11,1 tienen ambos el número 111, por lo que seguramente tendrán el mismo color.

Además, siempre que realice el ciclo de la misma manera, puede usar solo un generador, sin necesidad de usar uno para cada píxel. ¡Uno para toda la imagen servirá! Todavía habrá algún tipo de patrón debido a la seudoaleatoriedad. @David_Lively tiene razón sobre el uso de algún algoritmo de ruido, lo hará parecer más aleatorio.

Salketer
fuente
La cuestión es que la vista de la imagen debería poder cambiar (más a coordenadas positivas). Así que este enfoque no funcionará por completo
libélula
44
En realidad, "todo esto" no suena bien: restituir un RNG determinista para cada píxel es una estrategia terrible a menos que la semilla en sí sea de un RNG criptográfico (e incluso entonces es una estrategia inestable por razones no relacionadas con la distribución).
Konrad Rudolph
puede incluir la forma correcta de concatenar los números en este contexto. Es decir. (x + y * ancho)
Taemyr
1

Haga un generador de color, luego produzca sus colores para su mosaico. ¡Semilla solo una vez! No necesita sembrar más que eso, al menos por ficha.

public class RandomColorGenerator {
  private final int minValue;
  private final int range;
  private final Random random;
  public RandomColorGenerator(int minValue, int maxValue, Random random) {
    if (minValue > maxValue || (long)maxValue - (long)minValue > (long)Integer.MAX_VALUE) {
      throw new IllegalArgumentException();
    }
    this.minValue = minValue;
    this.range = maxValue - minValue + 1;
    this.random = Objects.requireNonNull(random);
  }

  public int nextColor() {
    int r = minValue + random.nextInt(range);
    int g = minValue + random.nextInt(range);
    int b = minValue + random.nextInt(range);
    return -Color.rgb888(r, g, b);
  }
}

public class Tile {
  private final int[][] colors;
  public Tile(int width, int height, RandomColorGenerator colorGenerator) {
    this.colors = new int[width][height];
    for (int x = 0; x < width; x++) {
      for (int y = 0; y < height; y++) {
        this.colors[x][y] = colorGenerator.nextColor();
      }
    }
  }

  public int getColor(int x, int y) {
    return colors[x][y];
  }
}

Y el uso será como sigue:

RandomColorGenerator generator = new RandomColorGenerator(1, 100, new Random(0xcafebabe));
Tile tile = new Tile(300, 200, generator);
...
// getting the color for x, y:
tile.getColor(x, y);

Con esto, si no está satisfecho con el resultado, simplemente cambie la Randomsemilla. Además, solo tiene que almacenar / comunicar la semilla y los tamaños para que todos los clientes tengan la misma imagen.

Olivier Grégoire
fuente
1

En lugar de usar Random, considere usar un resumen de hash como MD5. Proporciona un valor 'aleatorio' difícil de predecir basado en una determinada entrada, pero siempre el mismo valor para la misma entrada.

Ejemplo:

public static int TileColor(int x, int y){
        final MessageDigest md = MessageDigest.getInstance("MD5");
        final ByteBuffer b = ByteBuffer.allocate(8);
        b.putInt(x).putInt(y);
        final byte[] digest = md.digest(b.array());
        return -Color.rgb888(digest[0], digest[1], digest[2]);
}

NOTA: No sé de dónde viene Color.rgb888 (..), así que no sé cuál es el rango permitido. Sin embargo, 0-255 es normal.

Mejoras a considerar:

  • Cree las variables MessageDigest y ByteBuffer fuera de la clase para mejorar el rendimiento. Deberá restablecer el ByteBuffer para hacer eso, y el método ya no será seguro para subprocesos.
  • La matriz de resumen contendrá valores de bytes 0-255, si desea otros rangos, tendrá que hacer algunos cálculos matemáticos sobre ellos.
  • Si desea resultados 'aleatorios' diferentes, puede agregar algún tipo de 'semilla'. Por ejemplo, cambie a ByteBuffer.allocate (12) y agregue un .putInt (semilla).
cranphin
fuente
1

Otros han señalado que una forma de obtener el comportamiento que desea es utilizar una función hash, también conocida como "función de resumen de mensajes". El problema es que a menudo se basan en algoritmos como MD5, que es criptográficamente seguro (es decir, muy, muy aleatorio) pero muy lento. Si utiliza una función hash criptográfica cada vez que necesita un píxel aleatorio, se encontrará con problemas de rendimiento bastante graves.

Sin embargo, hay funciones hash no criptográficas que pueden producir valores que son lo suficientemente aleatorios para su propósito y al mismo tiempo son rápidos. El que generalmente busco es murmurhash . No soy un usuario de Java, pero parece que hay al menos una implementación de Java disponible. Si descubre que realmente necesita que cada píxel se genere a partir de sus coordenadas, en lugar de generarlos todos a la vez y almacenarlos en una textura, entonces esta sería una buena manera de hacerlo.

Nathaniel
fuente
1

Usaría un primer sobre 2000 (resolución típica máxima)
Esto minimizará (o eliminará semillas duplicadas)

public class Generate {

    static Random Random;

    public static int TileColor(int x, int y){          
        Random = new Random(x + 2213 * y);
        int b = 1 + Random.nextInt(50);
        int g = 1 + Random.nextInt(50);
        int r = 1 + Random.nextInt(50);
        int color = -Color.rgb888(r, g, b);
        return color;
    }
}
paparazzo
fuente
0

Randomes lo suficientemente aleatorio Lo estás usando mal por dos razones principales.

  • No fue diseñado para ser re-sembrado repetidamente. Las propiedades aleatorias solo se mantienen para una sola secuencia de números aleatorios.
  • Hay una gran correlación Integer.valueOf(Integer.toString(x)+Integer.toString(y))entre los píxeles con los que está sembrando.

Simplemente usaría alguna variación del siguiente código, donde puede elegir una función hash (no use Integer.getHashCode) de las respuestas en /programming/9624963/java-simplest-integer- picadillo

public static int TileColor(int x, int y) {
    return hash(x ^ hash(y));
}

donde podría estar la función hash

Palanqueta
fuente
0

Puede intentar usar la hora actual del sistema como una semilla como esta:

Random random = new Random(System.currentTimeMillis())

Esperemos que produzca un valor más aleatorio.

desarrollador anónimo
fuente
Sin embargo, eso no crea el valor de dama para la coordenada de dama cada vez.
libélula
0

Aquí hay una función de sombreador estático de una línea que se me ocurrió: poltergeist (Noisy Ghost).

Toma una coordenada 2D y una semilla, y se procesa en tono monótono según lo solicitado. Se ejecuta en fps en tiempo real, independientemente de la resolución de la pantalla. Para eso están las GPU.

// poltergeist (noisy ghost) pseudo-random noise generator function
// [email protected] 03/24/2015

precision highp float;

float poltergeist(in vec2 coordinate, in float seed) 
{
    return fract(sin(dot(coordinate*seed, vec2(12.9898, 78.233)))*43758.5453); 
}

void mainImage(out vec4 fragColor, in vec2 fragCoord) 
{   
    fragColor = vec4(poltergeist(fragCoord, iGlobalTime)); 
}

Cualquier resolución, cualquier textura, en cualquier dispositivo (también móvil) compatible con GL (que es prácticamente cualquier con una pantalla).

¡Véalo corriendo aquí, ahora mismo!

https://www.shadertoy.com/view/ltB3zD

Puede incluir fácilmente este sombreador en su programa java usando opengl estándar, o en cualquier navegador usando webgl estándar.

Solo por diversión, tiro el guante para que cualquiera pueda vencer a Poltergeist en calidad y rendimiento en todos los dispositivos. ¡Ruidoso fantasma gobierna! Invicto!

Birkensocks
fuente