Ruído aleatório baseado em sementes

16

Atualmente, estou trabalhando em um programa que deve gerar ruído aleatório em uma tela com base nas 'coordenadas' de um pixel. As coordenadas devem ter a mesma cor sempre que você reiniciar o programa. No entanto, usando o util.Random do Java, os resultados obtidos não são tão aleatórios quanto eu gostaria:

captura de tela

Eu pensei que se eu usasse as coordenadas combinadas (como em um número inteiro formado pelas duas coordenadas próximas umas das outras), cada coordenada teria um número diferente. Usando esse número como uma semente, eu esperava obter números aleatórios diferentes para cada coordenada para usar no valor rgb dessa coordenada.

Este é o código que eu usei:

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

O padrão criado pelo programa é devido ao modo como a função Aleatória do java funciona ou estou fazendo algo errado e devo tentar uma abordagem diferente?

Atualização: Agora, tentei me livrar dos problemas relacionados à concatenação usando o seguinte 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 alguma forma, isso também forneceu uma (na minha opinião) imagem suficientemente aleatória:

miar imagem

Esse código, no entanto, é processado novamente três vezes por pixel. Mesmo que isso não seja um problema para mim no momento, considero alterar esse código caso precise de uma melhor performance posteriormente.

libélula
fonte
3
Não tenho certeza sobre o Random do Java, mas tenho certeza de que não é realmente aleatório ... Leia en.wikipedia.org/wiki/Pseudorandom_number_generator Você entenderá por que vê esses padrões.
Salketer
23
Algo crucial que está faltando nas outras respostas: não faça nova propagação do RNG para cada pixel. Semeie uma vez e gere valores consecutivos para todos os pixels da sua imagem com base nisso.
Konrad Rudolph
4
Nota: uma geração de número pseudo-aleatório pode ser distribuída uniformemente em uma dimensão , mas falha ao usar mais de uma dimensão ... você está efetivamente gerando pontos em 3D (r, ge eb e 3 coordenadas diferentes), portanto, você precisa de um gerador aleatório que garante não apenas que os valores gerados sejam distribuídos uniformemente, mas também os trigêmeos gerados sejam distribuídos uniformemente no espaço 3D.
Bakuriu 27/10/16
6
@Bakuriu Se X, Y e Z são variáveis ​​aleatórias uniformes independentes, então tenho certeza (X, Y, Z) é uniforme no espaço 3D.
Jack M
2
Você pode experimentar o uso de diferentes RNGs, como o Mersenne Twister .
Kevin

Respostas:

21

A java.util.Randomclasse de Java geralmente fornece sequências de números pseudo-aleatórios que são bons o suficiente para uso em jogos 1 . No entanto, essa característica se aplica apenas a uma sequência de várias amostras com base em uma semente. Quando você reinicializa o RNG com o aumento dos valores de sementes e olha apenas para o primeiro valor de cada sequência, as características de aleatoriedade não serão tão boas.

O que você poderia fazer:

  • Use a mesma semente para gerar pedaços inteiros de pixels por vez. Por exemplo, quando você precisar do valor da cor do pixel 425: 487, alimente as coordenadas 400: 400 no RNG, gere 10000 cores aleatórias e use a cor no índice 2587 (25 * 100 + 87). Os pedaços gerados dessa maneira devem ser armazenados em cache para evitar a geração dessas 10000 cores aleatórias para cada pixel daquele pedaço.
  • Em vez de usar um gerador de números aleatórios, use uma função de resumo da mensagem para transformar um par de coordenadas em um valor de cor. A saída da maioria dos MDFs é imprevisível o suficiente para realizar a maioria dos testes de aleatoriedade. A saída geralmente é superior aos 24 bits necessários para um valor RGB, mas truncá-los normalmente não é problema.

    Para melhorar o desempenho, você pode combinar a geração de resumo de mensagens com pedaços. Gere pequenos pedaços de pixels, que são grandes o suficiente para usar todo o comprimento de uma saída da sua função Digest.

1 quando for absolutamente essencial que ninguém possa prever o próximo número, use o mais lento, mas menos previsíveljava.security.SecureRandom

Philipp
fonte
13

As coordenadas devem ter a mesma cor em todos os que você reinicia o programa

Nesse caso, você desejará usar uma função de ruído determinístico, como o ruído Perlin ou simplex .

( Veja esta pergunta para obter mais informações sobre o ruído Perlin com algumas fotos bonitas. )

Na maioria das vezes, o uso de uma random()função interna ou similar fornecerá valores diferentes toda vez que o programa for executado, pois eles podem usar o relógio como entrada ou algum outro valor pseudo-aleatório.

Outra opção é gerar um "mapa de ruído" uma vez, offline, e depois usá-lo como sua fonte de números aleatórios mais tarde.

Na sua implementação, você está concatenando as representações de string de xe y. Isso é ruim, pois não é exclusivo em todo o domínio. Por exemplo,

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

Boa sorte!

3Dave
fonte
11
Bom argumento sobre os números concatenados. No entanto, o programa sempre fornece exatamente o mesmo resultado se eu executar o programa várias vezes. Também considerei o ruído perlin / simplex, posso dar uma olhada nisso e ver se funciona melhor. Estou no entanto ainda não sei por que Java cria padrões, para o problema de concatenação não parece resolvê-lo inteiramente
libélula
11
Não é suficiente simplesmente semear Random com um valor de semente constante antes de gerar os pixels?
Jack M
11
@JackM Isso depende inteiramente do algoritmo PRNG em jogo.
precisa saber é o seguinte
4
"Uma vez vi uma implementação rand () que usava cada valor como uma semente para o próximo valor." Não é assim que a maioria dos geradores de números pseudoaleatórios não criptográficos funciona? Eles usam o número aleatório anterior (ou estado) como entrada para gerar o próximo número / estado aleatório.
JAB
2
@DavidLively Virtualmente todos os PRNGs fazem isso ou algo equivalente, a menos que seu estado interno seja maior que o intervalo de números que eles geram (por exemplo, trava Mersenne), e mesmo assim a sequência de números aleatórios é, naturalmente, inteiramente determinada pela semente.
Konrad Rudolph
9

Vamos ver o que você está fazendo exatamente:

  • Você percorre todos os pixels um por um
  • Para cada pixel, você usa a concatenação de suas coordenadas como uma semente
  • Você então inicia um novo aleatório a partir da semente fornecida e retira 3 números

Tudo isso soa bem, mas você está recebendo um padrão porque:

Pixel em 1,11 e pixel em 11,1 são semeados no número 111, portanto eles certamente terão a mesma cor.

Além disso, desde que você sempre ande da mesma maneira, poderá usar apenas um gerador, sem precisar usar um para cada pixel. Um para toda a imagem serve! Ainda haverá algum tipo de padrão por causa da pseudo-aleatoriedade. O @David_Lively está certo sobre o uso de algum algoritmo Noise, que fará com que pareça mais aleatório.

Salketer
fonte
O fato é que a visão da imagem deve ser capaz de mudar (para coordenadas positivas). Portanto, esta abordagem não vai funcionar completamente
libélula
4
Na verdade, "tudo isso" não soa bem - a repetição de um RNG determinístico para cada pixel é uma estratégia terrível, a menos que a semente em si seja de um RNG criptográfico (e mesmo assim é uma estratégia instável por razões não relacionadas à distribuição).
Konrad Rudolph
você pode incluir a maneira correta de concatenar os números nesse contexto. Ou seja. (x + y * width)
Taemyr 28/10
1

Faça um gerador de cores e depois produza suas cores para o seu azulejo. Semente apenas uma vez! Você não precisa propagar mais do que isso, pelo menos por peça.

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

E o uso será como segue:

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

Com isso, se você não estiver satisfeito com o resultado, mude a Randomsemente. Além disso, você só precisa armazenar / comunicar a semente e os tamanhos para que todos os clientes tenham a mesma imagem.

Olivier Grégoire
fonte
1

Em vez de usar o Random, considere usar um resumo de hash como MD5. Ele fornece um valor 'aleatório' difícil de prever com base em uma determinada entrada, mas sempre o mesmo valor para a mesma entrada.

Exemplo:

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: Não sei de onde vem Color.rgb888 (..); portanto, não sei qual é o intervalo permitido. 0-255 é normal embora.

Melhorias a considerar:

  • Torne as variáveis ​​MessageDigest e ByteBuffer fora da classe, para melhorar o desempenho. Você precisará redefinir o ByteBuffer para fazer isso, e o método não será mais seguro para threads.
  • A matriz de resumo conterá os valores de bytes de 0 a 255, se você quiser outros intervalos, precisará fazer algumas contas neles.
  • Se você quiser resultados 'aleatórios' diferentes, poderá adicionar algum tipo de 'semente'. Por exemplo, mude para ByteBuffer.allocate (12) e adicione um .putInt (semente).
cranphin
fonte
1

Outros apontaram que uma maneira de obter o comportamento desejado é usar uma função hash, também conhecida como "função de resumo da mensagem". O problema é que eles geralmente são baseados em algoritmos como o MD5, que é criptograficamente seguro (ou seja, muito, muito, muito aleatório), mas muito lento. Se você usar uma função de hash criptográfico toda vez que precisar de um pixel aleatório, terá problemas de desempenho bastante graves.

No entanto, existem funções de hash não criptográficas que podem produzir valores aleatórios o suficiente para o seu objetivo, além de rápidos. O que eu geralmente busco é murmurar . Eu não sou um usuário Java, mas parece que há pelo menos uma implementação Java disponível. Se você achar que realmente precisa que cada pixel seja gerado a partir de suas coordenadas, em vez de gerá-los todos de uma vez e armazená-los em uma textura, essa seria uma boa maneira de fazê-lo.

Nathaniel
fonte
1

Eu usaria um primo acima de 2000 (resolução típica máxima)
Isso minimizará (ou eliminará sementes 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
fonte
0

Randomé aleatório o suficiente. Você está usando errado por dois motivos principais.

  • Não foi projetado para ser repetidamente repetido. As propriedades aleatórias são válidas apenas para uma única sequência de números aleatórios.
  • Existe uma enorme correlação Integer.valueOf(Integer.toString(x)+Integer.toString(y))entre os pixels que você está propagando.

Eu usaria apenas algumas variações do código a seguir, onde você pode escolher uma função de hash (não use Integer.getHashCode) nas respostas em /programming/9624963/java-simplest-integer- cerquilha

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

onde a função hash poderia ser

Jimmy
fonte
0

Você pode tentar usar a hora atual do relógio do sistema como uma semente como esta:

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

Espero que produza um valor mais aleatório.

desenvolvedor anônimo
fonte
Porém, isso não cria o valor da dame para a coordenada da dame sempre.
libélula
0

Aqui está uma função de sombreador estático de uma linha que eu criei - poltergeist (Noisy Ghost).

É necessária uma coordenada 2D e uma semente e é renderizada em monotonia, conforme solicitado. É executado em fps em tempo real, independentemente da resolução da tela. É para isso que servem as GPUs.

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

Qualquer resolução, qualquer textura, em qualquer dispositivo (móvel também) que suporte GL (que é praticamente qualquer tela).

Veja-o funcionando aqui, agora!

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

Você pode incluir facilmente esse shader no seu programa java usando o opengl padrão ou em qualquer navegador usando o webgl padrão.

Apenas por diversão, eu jogo a luva para qualquer um vencer o Poltergeist em qualidade e desempenho em todos os dispositivos. Regras barulhentas do fantasma! Invicto!

Birkensocks
fonte