Neste artigo, apresento uma nova sequência quase aleatória de baixa divergência que fornece melhorias significativas em relação às seqüências modernas, como Sable, Niederreiter, etc.


Figura 1. Comparação de várias seqüências quase aleatórias com baixa divergência. Observe que o proposto por mim $$$R$ A sequência cria pontos distribuídos de maneira mais uniforme do que todos os outros métodos. Além disso, todos os outros métodos requerem seleção cuidadosa dos parâmetros básicos e, no caso de seleção incorreta, levam à degeneração (por exemplo, no canto superior direito)

Tópicos abordados neste artigo

• Sequências de baixa divergência em uma dimensão
• Métodos de baixa divergência em duas dimensões
• Distância da embalagem
• Conjuntos de baixa discrepância multiclasse
• Sequências quase aleatórias na superfície de uma esfera
• Mosaico plano quase-periódico
• Máscaras pontilhadas em computação gráfica

Há algum tempo, este post foi publicado na página inicial do Hacker News. Você pode ler a discussão dele lá .

Introdução: aleatória versus quase aleatória

Na Figura 1, você pode notar que, com uma amostragem aleatória simples e uniforme de um ponto dentro de um quadrado de unidade, é observado um acúmulo de pontos e também surgem áreas sem pontos (“ruído branco”). Uma sequência quase aleatória de baixa divergência é um método de construir pontos consecutivos (infinitos) de maneira determinística, o que reduz a probabilidade de acumulação (divergência), garantindo uma cobertura uniforme de todo o espaço (“ruído azul”).

Sequências quase aleatórias em uma dimensão

Os métodos para criar sequências quase aleatórias completamente determinadas com baixa divergência em uma dimensão são muito bem estudados e resolvidos em termos gerais. Neste post, considerarei principalmente sequências abertas (infinitas), primeiro em uma dimensão, e depois passarei para dimensões mais altas. A vantagem fundamental de sequências abertas (ou seja, extensível em $$$n$ ) reside no fato de que, se o total de erros com base em um número finito de membros for muito grande, a sequência poderá ser expandida sem descartar todos os pontos calculados anteriores. Existem muitas maneiras de criar sequências abertas. Você pode dividir tipos diferentes em categorias pelo método de construir seus parâmetros (hiper) básicos:

• frações irracionais: Kronecker, Richtmayer, Ramshaw
• (mutuamente) números primos: Van der Corpute, Holton, Foret
• Polinômios Irredutíveis: Niederreiter
• Polinômios primitivos: zibelina

Por uma questão de brevidade, neste post vou comparar principalmente o novo aditivo recursivo $$$R$ - uma sequência que pertence à primeira categoria, ou seja, a métodos recursivos baseados em números irracionais (geralmente chamados de seqüências de Kronecker, Weil ou Richtmeier), que são redes de classificação 1, e uma sequência de Holton, que é baseada na sequência canônica van der Corpute unidimensional. A sequência recursiva canônica da Kronecker é definida como:

$$

$$R_1 (\ alpha): \; \; t_n = \ {s_0 + n \ alpha \}, \ quad n = 1,2,3, ...$$

onde $$$\ alpha$ - qualquer número irracional. Observe que a entrada $$$\ {x \}$ denota a parte fracionária $$$x$ . Nos cálculos, essa função é frequentemente expressa como

$$

$$R_1 (\ alpha): \; \; t_n = s_0 + n \ alfa \; (\ textrm {mod} \; 1); \ quad n = 1,2,3, ...$$

At $$$s_0 = 0$ primeiros membros da sequência $$$R (\ phi)$ igual a:

$$

$$t_n = 0,618, \; 0,236, \; 0,854, \; 0,472, \; 0,090, \; 0,708, \; 0,327, \; 0,944, \; 0,562, \; 0,180, \; 798, \; 416, \; 0,034, \; 0,652, \; 0,271, \; 0,888, ...$$

É importante notar que o significado $$$s_0$ não afeta as características gerais da sequência e, em quase todos os casos, é igual a zero. No entanto, ao calcular a opção $$$s \ neq 0$ fornece um grau adicional de liberdade, que geralmente é útil. Se $$$s \ neq 0$ , a sequência é freqüentemente chamada de "sequência treliçada deslocada". Apesar do fato de que, por padrão $$$s = 0$ Eu acredito que existem considerações teóricas e práticas para as quais o valor deve ser padrão $$$s = 1/2$ . Valor $$$\ alpha$ dando a menor discrepância possível se $$$\ alpha = 1 / \ phi$ onde $$$\ phi$ - Essa é a proporção áurea. Isso é

$$

$$\ phi \ equiv \ frac {\ sqrt {5} +1} {2} \ simeq 1,61803398875 ...;$$

É interessante notar que há um número infinito de outros valores. $$$\ alpha$ , o que também nos permite obter a discrepância ideal e todos eles são relacionados um ao outro pela transformação Mobius

$$

$$\ alpha '= \ frac {p \ alpha + q} {r \ alpha + s} \ quad \ textrm {para todos os números inteiros} \; p, q, r, s \ quad \ textrm {tal que} | ps-qr | = 1$$

Agora, comparamos esse método recursivo com as bem conhecidas seqüências de van der Korput com a ordem inversa das descargas [ van der Korput, 1935 ]. As seqüências de Van der Corpute são na verdade uma família de sequências, cada uma das quais é definida por um hiperparâmetro único $$$b$ . Os primeiros membros da sequência com b = 2 são iguais:

$$

$$t_n ^ {[2]} = \ frac {1} {2}, \ frac {1} {4}, \ frac {3} {4}, \ frac {1} {8}, \ frac {5} {8}, \ frac {3} {8}, \ frac {7} {8}, \ frac {1} {16}, \ frac {9} {16}, \ frac {5} {16}, \ frac {13} {16}, \ frac {3} {16}, \ frac {11} {16}, \ frac {7} {16}, \ frac {15} {16}, ...$$

Na próxima seção, comparamos as características gerais e a eficácia de cada uma dessas seqüências. Considere o problema de calcular uma certa integral

$$

$$A = \ int_0 ^ 1 f (x) \ textrm {d} x$$

Podemos aproximar como:

$$

$$A \ simeq A_n = \ frac {1} {n} \ sum_ {i = 1} ^ {n} f (x_i), \ quad x_i \ in [0,1]$$

• Se $$$\ {x_i \}$ são iguais $$$i / n$ , esta é a fórmula dos retângulos ;
• Se $$$\ {x_i \}$ selecionado aleatoriamente, esse é o método de Monte Carlo ; mas
• Se $$$\ {x_i \}$ são elementos de uma sequência com baixa divergência, então esse é o método quase-Monte Carlo .

O gráfico abaixo mostra curvas de erro típicas. $$$s_n = | A-A_n |$ para aproximar uma certa integral associada a esta função, $$$f (x) = \ textrm {exp} (\ frac {-x ^ 2} {2}), \; x \ in [0,1]$ para: (i) pontos quase aleatórios da recursão aditiva, quando $$$\ alpha = 1 / \ phi$ , (azul); (ii) pontos quase aleatórios da sequência de van der Corput, (laranja); (iii) pontos selecionados aleatoriamente, (verde); (iv) Sequências de zibelina (vermelho).

Isso mostra que para $$$n = 10 ^ 6$ solução de pontos com amostragem aleatória leva a um erro $$$\ simeq 10 ^ {- 4}$ , sequência de van der Corput leva a erro $$$\ simeq 10 ^ {- 6}$ , considerando que $$$R (\ phi)$ - a sequência leva a um erro $$$\ simeq 10 ^ {- 7}$ que em $$$\ sim$ 10 vezes melhor que o erro de van der Corput e $$$\ sim$ 1000 vezes melhor que a amostragem aleatória (uniforme).


Figura 2. Comparação da integração numérica unidimensional usando vários métodos Monte Carlo quase aleatórios. Quanto menor o valor, melhor. Novo $$$R_2$ - a sequência (azul) e a sequência Sable (vermelho) são obviamente as melhores.

Vale a pena mencionar aqui:

• isso corresponde ao conhecimento de que os erros para amostragem aleatória uniforme diminuem assintoticamente para $$$1 / \ sqrt {n}$ , e o erro para ambas as seqüências quase aleatórias tende a $$$1 / n$ .
• Resultados para $$$R_1 (\ phi)$ seqüências (azul) e seqüências Sable (vermelho) são as melhores.
• O gráfico demonstra que a sequência de van der Corpute fornece resultados bons, mas incrivelmente consistentes, para tarefas de integração!
• Pode-se ver aqui que para todos os valores $$$n$ sequência $$$R_1 (\ phi)$ produz melhores resultados do que a sequência de van der Corput.

Nova sequência $$$R_1$ , que é a sequência Kronecker usando a proporção áurea, é uma das melhores opções para os métodos de integração quase-aleatórios Monte Carlo quase aleatórios (Quasirandom Monte Carlo, QMC).

Também é importante notar que, embora $$$\ alpha = \ phi$ teoricamente, fornece uma opção comprovadamente ótima, $$$\ sqrt {2}$ muito perto do ideal e quase qualquer outro valor irracional $$$\ alpha$ fornece curvas de erro superiores para integração unidimensional. É por isso que é frequentemente usado $$$\ alpha = \ sqrt {p}$ para qualquer número primo. Além disso, do ponto de vista dos cálculos, o valor aleatório selecionado no intervalo $$$\ alpha \ em [0,1]$ quase certamente (dentro dos limites da precisão da máquina) será um número irracional e, portanto, é uma boa escolha para uma sequência com baixa divergência. Para legibilidade visual, a figura acima não mostra os resultados da sequência de Niederreiter, porque eles são praticamente indistinguíveis dos resultados das sequências de Sobol e $$$R$ . As seqüências Niederreiter e Sable (juntamente com a seleção otimizada de parâmetros) usadas neste post foram computadas no Mathematica usando o que é chamado de "geradores proprietários fechados e totalmente otimizados da biblioteca Intel MKL" na documentação.

Sequências quase aleatórias em duas dimensões

Os métodos mais modernos para construir uma baixa variação em dimensões mais altas simplesmente combinam (componente por componente) $$$d$ sequências unidimensionais. Por uma questão de brevidade, no post consideraremos principalmente a sequência de Holton [ Holton, 1960 ], a sequência de Sable e $$$d$ tridimensional do Kronecker.

A sequência Holton é construída usando simples $$$d$ várias sequências van der Corpute unidimensionais, cuja base é mutuamente simples para todas as outras. Ou seja, eles são números coprime em pares. Sem dúvida, a opção mais comum devido à sua óbvia simplicidade e lógica é a escolha do primeiro $$$d$ números primos. A distribuição dos primeiros 625 pontos definidos pela sequência (2,3) de Holton é mostrada na Figura 1. Embora muitas seqüências bidimensionais de Holton sejam excelentes fontes de sequências com baixa divergência, é sabido que muitas delas são muito problemáticas e não apresentam baixa divergência. Por exemplo, a Figura 3 mostra que a sequência de Holton (11,13) gera linhas muito perceptíveis. Grandes esforços foram feitos para desenvolver métodos para a seleção de modelos e pares problemáticos. $$$(p_1, p_2)$ . Em dimensões mais altas, o problema se torna ainda mais complicado.

Ao generalizar para dimensões mais altas, os métodos recursivos da Kronecker sofrem dificuldades ainda maiores. Embora usando $$$\ alpha = \ sqrt {p}$ Se forem criadas excelentes seqüências unidimensionais, é extremamente difícil encontrar pares de números primos que possam ser usados ​​como base para um caso bidimensional que não é problemático! Foi sugerido o uso de outros números irracionais conhecidos como solução alternativa, por exemplo $$$\ phi, \ pi, e, ...$ . Eles fornecem resultados moderadamente aceitáveis, mas geralmente não são usados, porque geralmente não são tão bons quanto uma sequência Holton selecionada corretamente. Grandes esforços estão sendo feitos para resolver esses problemas de degeneração.

As soluções propostas usam pular / queimar, pular / afinar. E para codificar (embaralhar) as seqüências finais, outra técnica é usada, freqüentemente usada para superar esse problema. A codificação não pode ser usada para criar uma sequência aberta (infinita) com baixa divergência.


Figura 3. A sequência (11,13) -Holton obviamente não é uma sequência de baixa divergência (esquerda). Também não é a sequência recursiva aditiva (11,13) (no meio). Algumas seqüências recursivas aditivas bidimensionais que usam números irracionais conhecidos são muito boas (à direita).

Da mesma forma, apesar dos resultados geralmente melhores da sequência Sable, sua complexidade e, mais importante, a necessidade de uma seleção muito cuidadosa de hiperparâmetros a tornam menos amigável.

Então, novamente, em $$$d$ medições:

• seqüências típicas do Kronecker requerem uma escolha $$$d$ números irracionais linearmente independentes;
• A sequência de Holton requer $$$d$ prime mutuamente inteiros em pares; mas
• A sequência Sable requer uma escolha $$$d$ números de guia.

Nova sequência $$$R_d$ - o único $$$d$ tridimensional quase aleatória com baixa divergência, não exigindo a escolha de parâmetros básicos.

Generalização da proporção áurea

tl; dr Nesta parte, falarei sobre como construir uma nova classe $$$d$ sequencial aberta (infinita) tridimensional com baixa divergência, não exigindo a escolha de parâmetros básicos, com excelentes propriedades de baixa divergência.

Existem muitas maneiras de generalizar a sequência de Fibonacci e / ou a proporção áurea. O método proposto abaixo para generalizar a proporção áurea não é novo [ Krchadinac, 2005 ]. Além disso, o polinômio característico está associado a muitas áreas da álgebra, incluindo números Perron e números Piso-Vijayaraghavan . No entanto, a conexão explícita entre essa forma generalizada e a construção de seqüências de alta dimensão com baixa divergência é nova nela. Definimos uma visão generalizada da proporção áurea $$$\ phi_d$ como uma raiz positiva única $$$x ^ {d + 1} = x + 1$ . Isto é,

Para $$$d = 1$ , $$$\ phi_1 = 1.61803398874989484820458683436563 ...$ , que é a proporção de ouro canônica.

Para $$$d = 2$ , $$$\ phi_2 = 1.32471795724474602596090885447809 ...$ . Esse valor geralmente é chamado de constante de plástico e possui belas propriedades (veja também aqui ). Supõe-se que esse valor provavelmente seja ideal para o problema bidimensional correspondente [ Hensley, 2002 ].

Para $$$d = 3$ , $$$\ phi_3 = 1.220744084605759475361685349108831 ...$

Para $$$d> 3$ , embora as raízes desta equação não possuam uma forma algébrica fechada, podemos obter facilmente uma aproximação numérica por métodos padrão, por exemplo, o método de Newton ou observando que, para a seguinte sequência $$$R_d (\ phi_d)$ :

$$

$$t_0 = t_1 = ... = t_ {d} = 1;$$

$$

$$t_ {n + d + 1} \; = \; t_ {n + 1} + t_n, \ quad \ textrm {para} \; n = 1,2,3, ..$$

Esta sequência específica de constantes $$$\ phi_d$ foi nomeado em 1928 pelo arquiteto e monge Hans van de Laan como " números harmônicos ". Esses significados especiais podem ser expressos de maneira muito elegante da seguinte maneira:

$$

$$\ phi_1 = \ sqrt {1+ \ sqrt {1+ \ sqrt {1+ \ sqrt {1+ \ sqrt {1 + ...}}}}}$$

$$

$$\ phi_2 = \ sqrt [3] {1+ \ sqrt [3] {1+ \ sqrt [3] {1+ \ sqrt [3] {1+ \ sqrt [3] {1 + ...}}}}}$$

$$

$$\ phi_3 = \ sqrt [4] {1+ \ sqrt [4] {1+ \ sqrt [4] {1+ \ sqrt [4] {1+ \ sqrt [4] {1 + ...}}}}}$$

Também temos a seguinte propriedade muito elegante:

$$

$$\ phi_d = \ lim_ {n \ to \ infty} \; \; \ frac {t_ {n + 1}} {t_n}$$

Essa sequência, às vezes chamada de seqüência generalizada ou diferida de Fibonacci, foi estudada profundamente [ As, 2004 , Wilson, 1993 ], e a sequência para $$$d = 2$ freqüentemente chamada de sequência Padovan [ Stuart, 1996 , OEIS A000931 ], e a sequência $$$d = 3$ listado em [ OEIS A079398 ]. Como mencionado acima, a principal tarefa deste post é descrever a conexão explícita entre essa sequência generalizada e a construção. $$$d$ tridimensionais com baixa divergência.

Resultado principal: os seguintes parâmetros não paramétricos $$$d$ sequência aberta (infinita) tridimensional $$$R_d (\ phi_d)$ apresenta excelentes características de baixa discrepância em comparação com outros métodos existentes.

$$

$$\ mathbf {t} _n = \ {n \ pmb {\ alpha} \}, \ quad n = 1,2,3, ...$$

$$

$$\ textrm {where} \ quad \ pmb {\ alpha} = (\ frac {1} {\ phi_d}, \ frac {1} {\ phi_d ^ 2}, \ frac {1} {\ phi_d ^ 3}, ... \ frac {1} {\ phi_d ^ d})$$

$$

$$\ textrm {e} \; \ phi_d \ \ textrm {é uma raiz positiva única} x ^ {d + 1} = x + 1$$

Para duas dimensões, essa sequência generalizada para $$$n = 150$ mostrado na figura 1. Os pontos são obviamente distribuídos de maneira muito mais uniforme $$$R_2$ sequências -Holton, sequências Kronecker baseadas em $$$(\ sqrt {3}, \ sqrt {7})$ , Niederreiter e Sable. (Devido à complexidade das seqüências Niederreiter e Sable, elas foram computadas no Mathematica usando um código proprietário fornecido pela Intel.) Esse é o tipo de sequência na qual o vetor base $$$\ pmb {\ alpha}$ é uma função de um único valor material, geralmente chamado de sequência de Korobov [Korobov, 1959]

Veja novamente a Figura 1 para comparar várias seqüências bidimensionais e quase aleatórias de baixa divergência.

Código e demonstrações

Em uma dimensão, o pseudocódigo para $$$n$ membro ( $$$n$ = 1,2,3, ....) é definido como

 g = 1.6180339887498948482 a1 = 1.0/g x[n] = (0.5+a1*n) %1 

Em duas dimensões, o pseudocódigo das coordenadas $$$x$ e $$$y$$$$n$ membro ( $$$n$ = 1,2,3, ....) São definidos como

 g = 1.32471795724474602596 a1 = 1.0/g a2 = 1.0/(g*g) x[n] = (0.5+a1*n) %1 y[n] = (0.5+a2*n) %1 

Pseudocódigo em três dimensões para coordenadas $$$x$ , $$$y$ e $$$z$$$$n$ membro ( $$$n$ = 1,2,3, ....) é definido como

 g = 1.22074408460575947536 a1 = 1.0/g a2 = 1.0/(g*g) a3 = 1.0/(g*g*g) x[n] = (0.5+a1*n) %1 y[n] = (0.5+a2*n) %1 z[n] = (0.5+a3*n) %1 

Modelo de código Python. (observe que as matrizes e loops do Python começam do zero!)

 import numpy as np # Using the above nested radical formula for g=phi_d # or you could just hard-code it. # phi(1) = 1.61803398874989484820458683436563 # phi(2) = 1.32471795724474602596090885447809 def phi(d): x=2.0000 for i in range(10): x = pow(1+x,1/(d+1)) return x 

 # Number of dimensions. d=2 # number of required points n=50 g = phi(d) alpha = np.zeros(d) for j in range(d): alpha[j] = pow(1/g,j+1) %1 z = np.zeros((n, d)) # This number can be any real number. # Common default setting is typically seed=0 # But seed = 0.5 is generally better. for i in range(n): z[i] = (seed + alpha*(i+1)) %1 print(z) 

Escrevi o código de forma que correspondesse à notação matemática usada neste post. No entanto, por razões de convenções de programação e / ou eficiência, algumas modificações merecem destaque. Em primeiro lugar, desde $$$R_2$ é uma sequência recursiva aditiva, formulação alternativa $$$z$ que não requer multiplicação de ponto flutuante e mantém alta precisão por muito grande $$$n$ tem a forma

 z[i+1] = (z[i]+alpha) %1 

Em segundo lugar, em linguagens que podem vetorizar, o código de uma função fracionária pode ser vetorizado da seguinte maneira:

 for i in range(n): z[i] = seed + alpha*(i+1) z = z %1 

Finalmente, podemos substituir essas adições de ponto flutuante e números inteiros multiplicando todas as constantes por $$$2 ^ {32}$ e, em seguida, altere a função frac (.) de acordo. Aqui estão as demonstrações do código fonte criadas por outras pessoas com base nesta sequência:

• beta.observablehq.com/@jrus/plastic-sequence , desenvolvido por Jake Rus :
• www.shadertoy.com/view/4dtBWH , desenvolvedor @ Stirners Host (XGKICK):

Distância mínima de embalagem

Novo $$$R_2$ sequência é a única sequência quase - aleatória bidimensional com baixa divergência na qual a distância mínima de empacotamento é reduzida apenas para $$$1 / \ sqrt {n}$ .

Embora a análise técnica padrão do cálculo da discrepância seja avaliar $$$d ^ *$ - discrepâncias, primeiro mencionaremos algumas outras formas geométricas (e talvez muito mais intuitivas!) de demonstrar o quanto a nova sequência é preferível a outros métodos padrão. Se denotarmos a distância entre pontos $$$i$ e $$$j$ para $$$d_ {ij}$ e $$$d_0 = \ textrm {inf} \; d_ {ij}$ o gráfico abaixo mostra como isso varia $$$d_0 (n)$ para $$$R$ (2,3) - sequências de Holton, Sable, Niederreiter e sequências aleatórias. Isso pode ser visto na Figura 6.

Como na figura anterior, o valor mínimo da distância é normalizado pelo coeficiente $$$1 / \ sqrt {n}$ . Você pode perceber que depois $$$n = 300$ pontos em uma sequência aleatória (verde) quase certamente dois pontos aparecem extremamente próximos um do outro. Observa-se também que, embora a sequência de Holton (2,3) seja muito melhor que a amostragem aleatória, ela também, infelizmente, diminui assintoticamente para zero. Para a sequência Sable, o motivo da normalização diminui para zero $$$d_0$ reside no fato de que o próprio Sable mostrou que a sequência do Sable cai a uma velocidade $$$/ n$ - o que é bom, mas obviamente muito pior do que $$$R_2$ que diminui apenas em $$$1 / \ sqrt {n}$ .

Para sequência $$$R (\ phi_2)$ (azul) a distância mínima entre dois pontos cai constantemente no intervalo entre $$$0,549 / \ sqrt {n}$ antes $$$0,868 / \ sqrt {n}$ . Observe que o diâmetro ideal de 0,868 corresponde a um fator de empacotamento de 59,2%. Compare isso com outras embalagens de círculos .

Observe também que a amostragem de disco de Bridson Poisson , que não é expansível para $$$n$ e geralmente é recomendado por padrão, ele ainda cria um fator de empacotamento de 49,4%. Vale considerar que o conceito $$$d_0$ liga firmemente sequências $$$\ phi_d$ baixa discrepância com números / vetores pouco aproximados $$$d$ medições [ Hensley, 2001 ]. Embora saibamos pouco sobre números pouco aproximados em duas dimensões, a construção $$$\ phi_d$ pode nos fornecer uma nova visão de números pouco aproximados em dimensões mais altas.


Figura 4. Distância mínima em pares para várias seqüências com baixa divergência. Note que $$$R_2$ - a sequência (azul) é sempre a melhor opção; Além disso, esta é a única sequência na qual a distância normalizada não tende a zero a $$$n \ rightarrow \ infty$ . A sequência de Holton (laranja) ocupa o segundo lugar, e as seqüências de Sable (verde) e Niederreiter (vermelho) não são tão boas, mas ainda muito melhores que as aleatórias (roxas). Quanto maior, melhor, porque isso corresponde a uma maior distância da embalagem.

Diagramas de Voronoi

Outra maneira de visualizar a distribuição uniforme de pontos é criar um diagrama de Voronoi a partir do primeiro $$$n$ pontos de uma sequência bidimensional com subsequente coloração de cada área, dependendo de sua área . A figura abaixo mostra as tabelas de cores Voronoi para (i) $$$R_2$ sequências; (ii) (2,3) sequências de Holton; (iii) recursão primária; e (iv) amostragem aleatória simples. Para todas as figuras usadas a mesma escala de cores. Aqui, novamente, é óbvio que $$$R_2$ A sequência fornece uma distribuição muito mais uniforme do que a sequência de Holton ou uma amostragem aleatória simples. A imagem é a mesma que acima, colorida apenas de acordo com o número de vértices em cada célula de Voronoi. Não é apenas óbvio aqui que $$$R$ - a sequência fornece uma distribuição mais uniforme que Holton ou amostragem aleatória simples, mas o fato de que os valores-chave são mais perceptíveis $$$n$ consistem em apenas hexágonos! Se considerarmos a sequência generalizada de Fibonacci, então $$$A_1 = A_2 = A_3 = 1; \ quad A_ {n + 3} = A_ {n + 1} + A {n}$ . Isso é $$$A_n$ :

$$exibição $$ $$ \ begin {array} {r} 1 & 1 & 1 & 2 & 2 & 3 & 4 & 5 & 7 \\ 9 & \ textbf {12} & 16 & 21 & 28 & 37 & \ textbf {49} & 65 & 86 \\ 114 & \ textbf {151 } & 200 & 265 & 351 & 465 & \ textbf {616} & 816 & 1081 \\ 1432 & \ textbf {1897} & 2513 & 3329 & 4410 & 5842 & \ textbf {7739} & 10252 & 13581 \\ 17991 & \ textbf {23833} & 31572 & 41824 & 55405 {97229} & 128801 & 170625 \\ 226030 & \ textbf {299426} & 396655 & 525456 & 696081 & 922111 & \ textbf {1221537} & 1618192 & 2143648 \\ \ end {array} $$ display $$

Todos os valores em que $$$n = A_ {9k-2}$ ou $$$n = A_ {9k + 2}$ consistem apenas em hexágonos.


Figura 4. Visualização da forma dos diagramas de Voronoi com base na área de cada polígono de Voronoi para (i) $$$R_2$ sequências; (ii) (2,3) sequências baseadas em números primos; (iii) a sequência (2,3) de Holton; (iv) Niederraiter; (v) zibelina; e (iv) amostragem aleatória simples. As cores indicam o número de lados de cada polígono de Voronoi. Repito: é óbvio que $$$R (\ phi)$ A sequência fornece uma distribuição muito mais uniforme do que qualquer outra sequência com uma baixa divergência.

Em certos valores $$$n$ Grade Voronoi para $$$R_2$ A sequência consiste apenas em hexágonos.

Figura 5. Visualização da forma dos diagramas de Voronoi com base no número de lados de cada polígono de Voronoi para (i) $$$R_2$ sequências; (ii) (2,3) sequências baseadas em números primos; (iii) a sequência (2,3) de Holton; (iv) Niederraiter; (v) zibelina; e (iv) amostragem aleatória simples. As cores indicam o número de lados de cada polígono de Voronoi. Repito: é óbvio que $$$R (\ phi)$ A sequência fornece uma distribuição muito mais uniforme do que qualquer outra sequência com uma baixa divergência.

Ladrilhos quase aleatórios de Delaunay para um avião

$$$R$ sequência é a única sequência quase aleatória de baixa divergência que pode ser usada para criar $$$d$ inclinações quase-periódicas tridimensionais usando sua malha Delaunay.

A triangulação de Delaunay, que é semelhante ao conde Voronoi, oferece uma oportunidade de analisar essas distribuições de maneira diferente. No entanto, mais importante, a triangulação de Delaunay fornece um novo método para a criação de mosaico quase-periódico (mosaico) de um plano. Triangulação de Delaunay $$$R_2$ As sequências fornecem um padrão muito mais uniforme do que uma sequência de Holton ou amostragem aleatória. Em particular, se a triangulação Delaunay de distribuições de pontos for realizada, onde $$$n$ igual a qualquer uma das sequências generalizadas de Fibonacci: $$$A_N = $ 1,1,1,2,3,4,5,7,9,12,16,21,28,37, ...$ , então a triangulação de Delaunay consiste em apenas três triângulos emparelhados de forma idêntica, isto é, em paralelogramos (romboides)! (Exceto para triângulos que têm um vértice comum com um casco convexo.) Além disso,

Em valores $$$n = A_k$ Triangulação de Delaunay $$$R_2$ -sequences forma inclinações quasiperiódicas, cada uma das quais consiste em apenas três triângulos básicos (vermelho, amarelo, azul), que estão sempre conectados em pares e formam um mosaico quasiperiódico (mosaico) bem definido do plano com três paralelogramos (romboides).

Figura 6. Visualização da triangulação de Delaunay para (i) $$$R (\ phi_2)$ sequências; (ii) (2,3) sequências de Holton; (iii) recursão primária; e (iv) amostragem aleatória simples. As cores indicam a área de cada triângulo. Todos os quatro gráficos usam a mesma escala. E aqui novamente, é óbvio que $$$R (\ phi_2)$ A sequência fornece uma distribuição muito mais uniforme do que qualquer outra sequência com uma baixa divergência.
Note que $$$R_2$ baseado em $$$\ phi_2 = 1.32471795724474602596$ sendo o menor número de pisos (um $$$\ phi = 1,61803 ...$ É o maior número de pisos). A conexão de ladrilhos quase-periódicos com números quadráticos e cúbicos de Piso não é nova [ Elkharrat e Masakova], mas acredito que, pela primeira vez, o ladrilho quase-periódico foi criado com base em $$$\ phi_2 = 1.324719 ...$ .

A animação abaixo demonstra como o Delaunay se malha para a sequência $$$R_2$ muda com a adição gradual de pontos. Observe que quando o número de pontos é igual a um membro da sequência generalizada de Fibonacci, toda a grade de Delaunay consiste apenas em paralelogramos vermelhos, azuis e amarelos (romboides), dispostos em uma forma quase-periódica dupla.


Figura 7

Embora o arranjo dos paralelogramos vermelhos demonstre considerável regularidade, pode-se ver claramente que os paralelogramos azul e amarelo são colocados em uma forma quase-periódica. O espectro de Fourier dessa rede pode ser visto na Figura 11, representando os espectros de pontos clássicos. (Observe que uma sequência recursiva baseada em números primos também parece quase periódica no sentido de que é um padrão não repetitivo ordenado. No entanto, seu padrão no intervalo $$$n$ não tão constante e também depende criticamente da escolha dos parâmetros básicos. Portanto, focaremos nosso interesse em inclinações quase-periódicas apenas pela sequência $$$R_2$ .) Consiste em apenas três triângulos: vermelho, amarelo, azul. Observe que nesta sequência $$$R (\ phi_2)$ todos os paralelogramos de cada cor têm o mesmo tamanho e forma. A proporção desses triângulos individuais é incrivelmente elegante. Ou seja

$$

$$\ textrm {Área (vermelha): Área (amarela): Área (azul)} = 1: \ phi_2: \ phi_2 ^ 2$$

O mesmo se aplica à frequência relativa de triângulos:

$$

$$f (\ textrm {vermelho}): f (\ textrm {amarelo}): f (\ textrm {azul}) = 1: \ phi_2: 1$$

A partir disso, segue-se que a área relativa total coberta por esses três triângulos no espaço é:

$$

$$f (\ textrm {vermelho}): f (\ textrm {amarelo}): f (\ textrm {azul}) = 1: \ phi_2 ^ 2: \ phi_2 ^ 2$$

Também pode-se supor que podemos criar esse ladrilho quase-periódico por meio da substituição com base na sequência A. Isso é

$$

$$A \ rightarrow B; \ quad B \ rightarrow C; \ quad C \ rightarrow BA$$

Para três dimensões, se considerarmos a sequência generalizada de Fibonacci, então $$$B_1 = B_2 = B_3 = B_4 = 1; \ quad B_ {n + 4} = B_ {n + 1} + B {n}$ . Isso é

$$

$$B_n = \ {1,1,1,1,2,2,2,3,4,4,5,7,8,9,12,15,17,21,27,32,38,48,59 , 70,86,107,129, ...$$

Em certos valores $$$n = B_k$ Malha 3D Delaunay associada a uma sequência $$$R_3$ , define uma estrutura de cristal quase-periódica.

Embalagem discreta, parte 2

A figura abaixo mostra o primeiro $$$n = 2500$ pontos para cada sequência bidimensional com baixa divergência. Além disso, cada uma das células 50 × 50 = 2500 é colorida em verde somente se contiver exatamente 1 ponto. Ou seja, quanto mais quadrados verdes, mais uniforme é a distribuição de 2500 pontos em 2500 células. A porcentagem de células verdes para cada uma das figuras é a seguinte: $$$R_2$ (75%), Holton (54%), Kronecker (48%), Niederreiter (54%), Sable (49%) e aleatório (38%).

Ondas sonoras

Apenas por diversão, a pedido de um leitor do News Hacker, modelei como todas essas distribuições de pontos quase aleatórios podem soar ! Usei a função Listplay do Mathematica: “O ListPlay [{a1, a2, ...}] cria um objeto que se reproduz como som, cuja amplitude é dada como uma sequência de níveis.” Portanto, sem nenhum comentário, deixarei que você decida por si mesmo quais você gosta mais entre as distribuições quase aleatórias unidimensionais (mono) e distribuições quase aleatórias bidimensionais (estéreo).

	Mono	Stereo
Random	http://extremelearning.com.au/wp-content/uploads/2018/04/random_1D.mp3	http://extremelearning.com.au/wp-content/uploads/2018/04/random_2D.mp3
Sable	http://extremelearning.com.au/wp-content/uploads/2018/04/Sobol_1D.mp3	http://extremelearning.com.au/wp-content/uploads/2018/04/Sobol_2D.mp3
Niederreiter	http://extremelearning.com.au/wp-content/uploads/2018/04/Nied_1D.mp3	http://extremelearning.com.au/wp-content/uploads/2018/04/Nied_2D.mp3
Holton	http://extremelearning.com.au/wp-content/uploads/2018/04/Halton_1D.mp3	http://extremelearning.com.au/wp-content/uploads/2018/04/Halton_2D.mp3
Kronecker	http://extremelearning.com.au/wp-content/uploads/2018/04/Kronecker_1D.mp3	http://extremelearning.com.au/wp-content/uploads/2018/04/Kronecker_2D.mp3
R	http://extremelearning.com.au/wp-content/uploads/2018/04/R1_1D.mp3	http://extremelearning.com.au/wp-content/uploads/2018/04/R2_2D.mp3

Conjuntos de baixa discrepância multiclasse

Algumas seqüências de baixa divergência demonstram o que é chamado de "baixa divergência multi-classe". Até esse momento, assumimos que, quando precisamos distribuir o mais uniformemente possível $$$n$ pontos, todos os pontos são iguais e indistinguíveis um do outro. No entanto, em muitas situações, existem diferentes tipos de pontos. Consideramos o problema da distribuição uniforme $$$n$ para que não apenas todos os pontos sejam distribuídos uniformemente, mas também pontos da mesma classe. Em particular, suponha que haja $$$n_k$ digitar pontos $$$k$ , (onde $$$n_1 + n_2 + n_3 + ... + n_k = n$ ), a distribuição do multiset com uma distribuição baixa é uma distribuição na qual cada $$$n_k$ pontos distribuídos uniformemente. No nosso caso, descobrimos que $$$R$ -A sequência e sequência de Holton é fácil de se adaptar às seqüências de vários conjuntos com baixa divergência, simplesmente colocando pontos alternadamente de cada tipo.

A figura abaixo mostra como eles são distribuídos $$$n = 150$ pontos, enquanto 75 são azuis, 40 são apimentados, 25 são verdes e 10 são vermelhos. Para uma sequência recursiva aditiva, isso é resolvido trivialmente: os primeiros 75 membros correspondem simplesmente a azul, os próximos 40 a laranja, os próximos 25 a verde e os últimos 10 a pontos vermelhos. Essa técnica quase funciona para as seqüências de Holton e Kronecker, mas apresenta um desempenho muito ruim nas seqüências de Niederreiter e Sable. Além disso, não existem técnicas conhecidas para a geração contínua de distribuições de pontos em várias escalas nas sequências Niederreiter e Sable. Isso mostra que distribuições de pontos multiclasses , por exemplo, como os olhos de galinhas , agora podem ser descritas e construídas diretamente usando sequências com baixa divergência.

Sequência $$$R_2$ É uma sequência quase aleatória de baixa divergência que fornece fácil construção de uma baixa divergência de várias classes.

Figura 9. Sequências multiescala com baixa divergência. Em sequência $$$R$ não apenas todos os pontos são distribuídos igualmente, mas também os pontos de cada cor individual.

Pontos quase aleatórios em uma esfera

Nos campos da computação gráfica e da física, muitas vezes é necessário distribuir os pontos na superfície de uma esfera tridimensional o mais uniformemente possível. Ao usar seqüências quase aleatórias abertas (infinitas), esse problema é reduzido apenas à colocação de pontos quase aleatórios distribuídos uniformemente em um quadrado unitário na superfície da esfera usando a projeção igual de Lambert. Transformada de projeção padrão de Lambert, colocando um ponto $$$(u, v) \ em U [0,1] \ to (x, y, z) \ em S ^ 2$ tem a forma:

$$

$$(x, y, z) = (\ cos \ lambda \ cos \ phi, \ cos \ lambda \ sin \ phi, \ sin \ lambda$$

$$

$$\ textrm {onde} \ quad \ cos (\ lambda - \ pi / 2) = (2u-1); \ quad \ phi = 2 \ pi v$$

Uma vez que este $$$\ phi_2$ - a sequência é completamente aberta, permite que você encaixe uma sequência infinita de pontos na superfície da esfera, um ponto de cada vez. Isso contrasta com outros métodos, como a treliça da espiral de Fibonacci , que exigem o conhecimento prévio do número de pontos. Na inspeção visual, podemos novamente ver claramente que, para $$$n = 1200$ novo $$$R (\ phi_2)$ - A sequência é muito melhor distribuída do que a sobreposição de Holton ou a amostragem Kronecker, que, por sua vez, é muito mais uniforme que a amostragem aleatória.


Figura 10

Pontilhado de computação gráfica

A maioria das técnicas modernas de pontilhamento (por exemplo, pontilhamento de Floyd-Steinberg) são baseadas na distribuição de erros, o que não é muito adequado para processamento paralelo e / ou otimização direta na GPU. Nesses casos, o pontilhamento pontual com máscaras de pontilhamento estático (ou seja, completamente dependente da imagem de destino) mostra excelentes características de desempenho. Provavelmente, as máscaras de pontilhamento mais conhecidas e amplamente usadas são baseadas em matrizes Bayer , mas as mais novas tentam simular as características do ruído azul mais perto. A dificuldade não trivial de criar máscaras de pontilhamento com base em seqüências de baixa divergência e / ou ruído azul é que essas sequências de baixa divergência projetam um número inteiro $$$Z$ para um ponto bidimensional no intervalo $$$[0,1) ^ 2$ . Porém, para uma máscara de pontilhamento, é necessária uma função que projete as coordenadas inteiras bidimensionais da máscara rasterizada em valor de brilho / limite real no intervalo $$$[0,1)$ . Sugiro a seguinte abordagem com base em $$$R$-sequências. Para cada pixel (x, y) na máscara, atribuímos seu valor de brilho$$$I(x,y)$ onde:

$$

$$I(x,y) = \alpha_1 x + \alpha_2 y \; ( \textrm{mod} 1);$$

$$

$$\textrm{} \quad \pmb{\alpha} =(\alpha_1,\alpha_2) = (\frac{1}{\phi_2}, \frac{1}{\phi_2^2})$$

$$

$$\textrm{} \; \phi_2\ \textrm{ - } x^3\;=x+1$$

Isso é $$$x = 1.32471795724474602596…$ , o que significa

$$

$$\alpha_1 = 0.75487766624669276; \alpha_2 = 0.569840290998$$

Além disso, se uma função de onda triangular for adicionada para eliminar a descontinuidade causada pela função frac (.) Em cada limite inteiro:

$$

$$T(z) =\begin{cases} 2z, & \text{if } 0\leq z <1/2 \\ 2-2z, & \text{if} 1/2 \leq z < 1 \end{cases}$$

$$

$$I(x,y) = T \left[ \alpha_1 x + \alpha_2 y \; ( \textrm{mod} 1) \right];$$

então a máscara e seu diagrama de Fourier / frequência são aprimorados ainda mais. Também observamos que, desde

$$

$$\lim_{n \rightarrow \infty} \frac{A_n}{A_{n+1}} = 0.754878 ; \quad \lim_{n \rightarrow \infty} \frac{A_n}{A_{n+2}} = 0.56984$$

então a forma da expressão acima está relacionada à seguinte equação congruente

$$

$$A_n x + A_{n+1} y \; (\textrm{mod} A_{n+2}) \textrm{ for integers } \;\; x,y$$

Máscaras R pontilhadas criam resultados que competem com métodos modernos baseados em máscaras de ruído azul. Mas, diferentemente das máscaras de ruído azul, elas não precisam ser calculadas com antecedência, porque podem ser calculadas em tempo real.

Vale ressaltar que essa estrutura também foi proposta por Mittring , mas ele encontra os coeficientes empiricamente (e não reproduz os valores finais). Além disso, ajuda a entender por que a fórmula empírica de Jorge Jimenez usada para criar “Call of Duty” (freqüentemente chamada de “Ruído de gradiente intercalado”) funciona tão bem .

$$

$$I(x,y) = (\textrm{FractionalPart}[52.9829189*\textrm{FractionalPart}[0.06711056*x + 0.00583715*y]]$$

No entanto, ele requer 3 multiplicações de ponto flutuante e dois operadores% 1, e a fórmula anterior mostra que podemos fazer isso com apenas duas multiplicações de ponto flutuante e uma operação% 1. Mais importante, porém, este post fornece uma compreensão matemática mais clara do motivo pelo qual uma máscara de pontilhamento nesta forma é tão eficaz, se não ideal. Os resultados dessa matriz de pontilhamento são mostrados abaixo usando a imagem de teste clássica Lena 256 × 256, bem como um padrão de teste de xadrez como exemplo. Ele também mostra os resultados do uso de máscaras de pontilhamento padrão da Bayer, bem como um exemplo com ruído azul. Os dois métodos mais comuns de ruído azul são a amostragem de discos Void-and-Cluster e Poisson. Por uma questão de brevidade, mostrei apenas os resultados do método Void e cluster. [ Peters] O ruído de gradiente intercalado funciona melhor que o Bayer e o ruído azul, mas não tão bom quanto$$$R$pontilhamento. Você pode ver que o pontilhamento da Bayer mostra uma notável dissonância do branco nas áreas cinza claro. Dithering$$$R$- seqüência e ruído azul são geralmente comparáveis, embora pequenas diferenças possam ser detectadas. Vale a pena notar alguns aspectos do pontilhamento R:

• Ele não é isotrópico! Os espectros de Fourier mostram apenas pontos individuais e discretos. Esta é uma característica clássica de inclinações quase-periódicas e espectros de difração de cristais quase-cristais. Em particular, os espectros de Fourier para$$$R$ As máscaras correspondem ao fato de que a triangulação de Delaunay para a sequência R canônica consiste em mosaico quase-periódico de três paralelogramos.
• O pontilhamento R quando combinado com uma onda triangular fornece uma máscara incrivelmente uniforme!
• R- , .
• , , R- , .
• $$$(I(x,y)$ , .

Figura 11. Da esquerda para a direita: (i) Imagem original (ii) Sequência R combinada com uma função de onda triangular; (iii) a sequência R é separada; (iv) uma máscara de pontilhamento de ruído azul e (v) uma Bayer padrão. As máscaras de pontilhamento da sequência R são bastante competitivas em relação a outras máscaras modernas. Observe que o R2 mostra a melhor qualidade no rosto e nos ombros de Lena. Além disso, diferentemente das máscaras de ruído azul, a máscara R pontilhada é tão simples que não requer cálculos preliminares.

Dimensões mais altas

Semelhante à seção anterior, mas para cinco (5) medições, o gráfico abaixo mostra a distância mínima (global) entre quaisquer dois pontos para $$$R(\phi_5)$sequências (2,3,5,7,11) -Holton e sequências aleatórias. Desta vez, o valor normalizado da distância mínima é normalizado por um fator$$$1/ \sqrt[5]{n}$ . Você pode ver que, devido à “maldição das dimensões”, a distribuição aleatória é melhor do que todas as seqüências com baixa divergência - com exceção de $$$R_5$-sequências. Em$$$R(\phi_5)$ sequências mesmo com $$$n \simeq 10^6$ pontos, a distância mínima entre dois pontos ainda está constantemente próxima $$$0.8/\sqrt{n}$ e sempre mais alto $$$0.631/\sqrt{n}$ .

Sequência $$$R_2$ - o único $$$d$ tridimensional com baixa divergência, na qual a distância da embalagem começa a cair apenas com velocidade $$$n^{-1/d}$ .

Figura 12. Isso mostra que a sequência R (azul) é consistentemente melhor que Holton (laranja); Zibelina (verde); Niederreiter (vermelho); e aleatório (roxo). Lembre-se de que quanto maior, melhor, porque isso corresponde a uma distância maior da embalagem.

Integração numérica

O gráfico a seguir mostra curvas de erro típicas. $$$s_n = |A-A_n|$ para aproximar uma certa integral associada a uma função gaussiana de meia largura $$$\sigma = \sqrt{d}$ , $$$f(x) = \textrm{exp}(\frac{-x^2}{2d}), \; x \in [0,1]$ , enquanto: (i) $$$R_{\phi}$(azul); (ii) sequência de Holton (laranja); (iii) aleatório (verde); (iv) zibelina (vermelho). O gráfico mostra que, para$$$n=10^6$agora há menos diferenças entre a amostragem aleatória e a sequência de Holton. No entanto, como foi mostrado no caso unidimensional,$$$R$- Sequência e Sable são sempre melhores que a sequência de Holton. Também nos permite saber que a sequência de Sable é um pouco melhor.$$$R$ -sequências.


Figura 13. Métodos quase aleatórios de Monte Carlo para integração 8-dimensional. Quanto menor o valor, melhor. A nova sequência R e a sequência Sable mostram-se muito melhores que a sequência Holton.