🛏️ 🌤️ 🤽🏽 Cálculo do centro de massa para O (1) usando imagens integradas 😋 🚶🏿 🌇

Uma imagem integrada é um algoritmo que permite calcular com eficiência a soma dos valores contidos em um subconjunto retangular de uma matriz multidimensional. Sua própria idéia remonta ao estudo das funções de distribuição de probabilidade multidimensional e até agora ele encontrou uma aplicação bem-sucedida nessas áreas que usam diretamente a teoria das probabilidades como o principal kit de ferramentas. Por exemplo, no reconhecimento de padrões.

Hoje vamos considerar um caso curioso de como aplicar imagens integradas em um campo radicalmente diferente - a física computacional. Ou seja, vamos ver o que acontece se calcularmos com eles o centro de massa do campo de pulso e que benefício pode ser derivado dessa simbiose.

Neste artigo vou dizer:

Que tipo de tarefa é essa em questão;
Leia mais sobre imagens integradas;
N (-);
;
, , .

N

Uma solução rigorosa para a interação gravitacional de um sistema de N corpos refere-se a algoritmos com complexidade quadrática: todos os outros corpos no sistema têm um efeito gravitacional em cada corpo ^[1] . Consequentemente, a força da interacção necessidade gravitacional para calcular para cada um dos N ² par / 2.

Para ilustrar quão demorada é uma solução estrita, tente correlacionar a complexidade de calcular um sistema real com o desempenho dos computadores modernos.

Para calcular a força gravitacional entre dois corpos no espaço tridimensional, você deve executar 20 operações com um ponto flutuante (FLOP). No sistema solar, existem cerca de 100 corpos maiores que 200 quilômetros (incluindo o Sol, 9 planetas, planetas anões e satélites) ^[2]. O número aproximado de asteróides em órbita próxima à Terra é de cerca de 20 mil ^[3] . No cinturão de asteróides, existem de 1,1 a 1,9 milhão de corpos com mais de 1 km ^[4] e cerca de um milhão de asteróides similares nos grupos "Trojan" ^[5] e "Greek" de Júpiter. No cinturão de Kuiper, cerca de 100 milhões de objetos maiores que 20 km ^[6] e cerca de 2 trilhões a mais estão na nuvem de Oort ^[7] .

O poder computacional necessário para resolver estritamente o último problema gravitacional é apenas uma ordem de magnitude menor que o poder computacional necessário para simular o trabalho do cérebro humano no nível neural (2,5 × 10 ²⁶ ) ^[8]. É por isso que sua solução rigorosa geralmente é substituída por uma solução aproximada.

Um dos algoritmos mais amplamente utilizados para a solução aproximada do problema gravitacional - Código da Árvore - possui uma complexidade de tempo quaseilinear O (N * logN) ^[9] . O Código da Árvore cria uma árvore espacial e para cada nó nesta árvore calcula a massa total e o centro de massa de todos os corpos que nela caem. Além disso, ao calcular as forças gravitacionais que atuam em cada corpo, o Código da Árvore pode levar em consideração não a influência direta de outros corpos, mas a influência dos nós das árvores e, dependendo da distância, seleciona nós cada vez maiores que contêm parâmetros de um subconjunto de corpos cada vez mais numeroso.

Ilustração da Wikipedia. No corpo do centro estão as massas de nós indicadas por retângulos verdes. Somente as massas dos corpos mais próximos são levadas em conta diretamente.

Problema de gravidade para o campo momentum

O campo de momento é um campo vetorial discreto mv (p) , que associa um par de velocidade e massa a cada ponto do espaço p em consideração . O campo de pulso pode ser definido para um espaço de qualquer dimensão. Um par massa-velocidade caracteriza o momento e representa um vetor da dimensão R + 1, onde R é a dimensão do espaço para o qual o campo de pulso é fornecido. Por exemplo, para R = 2, este poderia ser o vetor { v _x , v _y , m }.

Vale a pena notar que a versão matematicamente tradicional da descrição deste sistema é uma combinação de um campo de velocidade vetorial e um campo de massa escalar. Nesse caso, nos permitimos a liberdade de combinar velocidade e massa em um vetor, já que não pretendemos ser matemáticos.

Uma pequena parte do campo vetorial de pulsos: as massas são indicadas por cor, as direções por setas.O

campo vetorial de pulsos com um tamanho de 729 × 729 elementos. À esquerda estão as massas. À direita são impulsos. Os pulsos nesta ilustração são codificados por cores no formato HSV (Hue é a direção do pulso, e Value exibe linearmente a ordem de seu valor absoluto, de modo que os pulsos menos distinguíveis (Valor = 0,05) sejam da ordem de 10 ^-7 e os pulsos mais brilhantes (Valor = 1 , 0) são da ordem de 10 ³ e superior).

Semelhante a este - métodos de grade para descrever sistemas físicos são amplamente utilizados na astrofísica para simular a evolução das nuvens de gás, a formação de estrelas e galáxias. Isso inclui o método SAMR ^[10] ou o modelo de grade da hidrodinâmica ^[11] .

Como no caso do problema gravitacional dos corpos N, a evolução de um campo discreto deve levar em conta a influência gravitacional de todas as massas que compõem esse campo em cada um de seus elementos discretos. É necessário levar em consideração que a complexidade do problema depende indiretamente da dimensão do espaço R : por exemplo, para um campo em um plano composto por 1000 × 1000 elementos, o número total N será 10 ⁶elementos e um campo do mesmo tamanho no espaço tridimensional já incluirá 10 ⁹ elementos.

No entanto, existem vários truques que permitem resolver aproximadamente o problema gravitacional do campo de momento. O método Multigrid usa discretização hierárquica, suportando várias grades de vários tamanhos ^[12] . A expansão multipolar trata grupos de fontes localizadas próximas umas das outras como um objeto ^[13] . O Multigrid possui complexidade computacional quaseilinear e complexidade de memória logarítmica. Uma das opções de expansão multipolar - FMM - demonstra complexidade computacional linear em troca de menor precisão computacional ^[14] .

Abaixo, consideramos outro método que nos permite resolver o problema gravitacional de um campo discreto de pulsos em tempo quase-linear e que possui complexidade linear na memória.

Imagem integrada

A imagem integral permite calcular o tempo constante a soma dos elementos da imagem original em uma região retangular arbitrária ^[15] . Na computação gráfica, imagens integradas foram originalmente propostas como uma alternativa ao mipmapping e à filtragem anisotrópica ^[16] . Além disso, eles são usados com sucesso no processamento de imagens digitais e em técnicas de reconhecimento de padrões.

Uma imagem integrada é um dos exemplos mais óbvios de uma troca entre complexidade computacional e complexidade da memória. Um algoritmo “ingênuo” para calcular a soma dos elementos da imagem possui uma complexidade de tempo de O (M * N) e uma complexidade de memória de O (1). A imagem integrada permite realizar os mesmos cálculos em tempo O (1) e possui complexidade de memória O (M * N).

Usando uma imagem integrada para calcular a soma de elementos em uma determinada região

O algoritmo para calcular uma imagem integral é muito simples, caracterizado por complexidade computacional linear e é facilmente paralelizado sob GPGPU ^[17] . É implementado como um filtro gaussiano de duas passagens ^[18] : na primeira passagem, as somas parciais para as linhas são consideradas; na segunda, essas somas parciais são acumuladas em colunas.

Cálculo da imagem integrada em duas passagens. À esquerda está a imagem original. No centro estão os valores parciais para as linhas. À direita está a imagem final integrada.

À esquerda, há uma imagem contendo massas de elementos. À direita está sua imagem integral. As imagens à esquerda e à direita usam diferentes escalas logarítmicas.

Uma solução aproximada para o problema gravitacional usando uma imagem integrada

Tendo à sua disposição uma imagem integral das massas, não é difícil adaptar a característica técnica do Código de Árvore e Expansão Multipolar. Portanto, para cada elemento do campo discreto:

Levamos diretamente em consideração a influência das massas apenas dos oito elementos vizinhos;
Levamos em consideração a influência de oito regiões vizinhas, constituídas por nove elementos (3 × 3), calculando a soma de suas massas usando uma imagem integrada;
Em cada etapa subsequente, aumentamos o tamanho da região em 3 vezes (9 × 9, 27 × 27, 81 × 81 etc.) até que essa exceda o tamanho de todo o campo vetorial.

Um cálculo aproximado das forças que atuam em um elemento do campo vetorial de pulsos usando uma imagem integral de massas

A complexidade da solução aproximada do problema gravitacional de um campo de pulsos usando uma imagem integral cresce quase que linearmente, como O (N * 8 * log3 (sqrt (N))) para R = 2 e como O (N * 26 * log3 (cbrt (N))) para R = 3.

No entanto, nesta forma, esta solução tem a mesma desvantagem da técnica Multigrid, a saber, a "rigidez" discreta perceptível dos componentes de baixa frequência da função de gravidade. A maneira mais fácil de demonstrar esse problema é claramente.

As forças nesta ilustração são codificadas por cores no formato HSV (Matiz é a direção da força; o Valor exibe linearmente a ordem de seu valor absoluto, de modo que as forças menos distinguíveis (Valor = 0,05) sejam da ordem de 10 ^-7 e as forças mais brilhantes (Valor = 1, 0) são da ordem de 10 ³ e superior).

Na ilustração acima, o efeito de "rigidez" dos componentes de baixa frequência da função de gravidade é perceptível a olho nu. Mas se em “Multigrid” essa “rigidez” ocorre devido a uma diminuição na frequência de amostragem, então na imagem integrada isso ocorre devido à falta de informações sobre a natureza da distribuição espacial de massas. O fato é que um algoritmo que aproxima forças usando uma imagem integrada considera que o centro de massa coincide com o centro da região.

O centro da ilustração mostra o extremo da massa com uma distribuição de massa relativamente uniforme no restante do campo.O extremo da

massa cai em cada uma das quatro regiões retangulares. Obviamente, a posição do centro de massa de cada região deve coincidir aproximadamente com o elemento indicado pelo branco, cuja massa é três ordens de magnitude maior que a massa da maioria dos elementos da região indicada pelo amarelo. No entanto, nos cálculos dos componentes de baixa frequência da função de gravidade para essas regiões, acredita-se que seus centros de massa coincidam com os centros das regiões indicadas por círculos.

Esse problema pode ser resolvido com a introdução de informações adicionais na imagem integrada, o que permitirá calcular não apenas a soma das massas em uma determinada região, mas também as coordenadas do centro de massa.

Primeiro, vamos tentar imaginar uma imagem, cada elemento contendo suas próprias coordenadas. A imagem integral correspondente conterá a soma das coordenadas. Portanto, a soma de uma região arbitrária dessa imagem integrada, dividida pelo número total de elementos nessa região, será igual às coordenadas do centro dessa região.

Imagem integral de coordenadas

Vamos pegar, por exemplo, a região no canto inferior esquerdo com coordenadas {3; 1} e no canto superior direito com coordenadas {7; 5}. A soma das coordenadas desta região {168; 120} - {18; 45} - {28; 0} + {3; 0} é {125; 75}, o número total de elementos é 25; portanto, as coordenadas do seu centro serão {5; 3}.

Tudo o que falta fazer é generalizar esse caso em particular, no qual consideramos que todos os elementos da imagem têm o mesmo coeficiente de peso igual à unidade. Para levar em consideração pesos diferentes, multiplicaremos as coordenadas dos elementos por eles. E obteremos as coordenadas ponderadas do centro da região se dividirmos a soma das coordenadas ponderadas pela soma dos fatores de ponderação.

Imagem integrada de coordenadas ponderadas. Fonte maior indica pesos

Considere a região no canto inferior esquerdo com coordenadas {2; 1} e no canto superior direito com coordenadas {5; 4}. A soma dos coeficientes de ponderação desta região 4.8 - 1.0 - 0.6 + 0.2 é 3.4 e a soma de suas coordenadas ponderadas {11.1; 13,2} - {0,5; 2,0} - {1,5; 0,0} + {0,1; 0,0} é igual a {9,2; 11.2}. Assim, as coordenadas ponderadas do centro desta região são {2,7; 3.3}.

Para garantir que esse circuito realmente funcione, você pode visualmente - convertendo a imagem integrada com coordenadas ponderadas em um campo de distância usando a transformação de distância ^[19] .

Convertendo uma imagem integrada com coordenadas ponderadas em um campo de distância. À esquerda está uma imagem das massas. A imagem a seguir é a distância do centro de massa para uma região de 3 × 3 elementos. A seguir, é apresentada a distância dos centros de massa para regiões com tamanhos de 9 × 9 e 27 × 27 elementos. Os valores de distância nesta ilustração são normalizados para o tamanho da região usada para amostragem.

Converte uma imagem integrada com coordenadas ponderadas em um campo de distância direcionada. A direção e a distância são codificadas por cores no formato HSV, onde Matiz é a direção, Valor é a distância normalizada. Os valores de distância nesta ilustração são normalizados para o tamanho da região usada para amostragem.

Resumindo todas as opções acima:

, , ( , R = 3) ― , , .
.
O(1).
O(M*N).

. ― . ― .

Hora de prestar atenção a um dos principais recursos das imagens integradas, que ainda limita o escopo de sua aplicação, a saber, consumo de recursos e estabilidade numérica. Portanto, dependendo do intervalo de valores que a imagem original contém, um tipo de dados mais longo pode ser necessário para sua imagem integral. Por exemplo, ao calcular os desvios padrão, além da imagem original (faixa de valores 0..255), uma imagem contendo quadrados dos valores correspondentes (faixa de valores 0..65535) é usada. Nesse caso, a precisão não é suficiente para calcular imagens integradas em larga escala de 32 bits ^[20] .

Uma situação semelhante é observada no caso de imagens integradas com coordenadas ponderadas. Por si só, o valor da soma das coordenadas que devem ser armazenadas na imagem integrada cresce dependendo do tamanho da imagem N: quadraticamente para o caso unidimensional 0 + 1 + 2 + ... + N - 1 = (N - 1) * N / 2 e cubicamente para bidimensional N * (N - 1) * N / 2. Por exemplo, para armazenar a soma de uma coordenada inteira para uma imagem de tamanho 2048 × 2048 (igual a 4292870144), um número inteiro não assinado de 32 bits (cujo valor máximo é 4294967295) é insuficiente. Ao calcular imagens integradas maiores, ocorre um estouro.

O uso de números de ponto flutuante de 32 bits em imagens integradas atrasa o problema do estouro por uma distância astronômica (10 ³⁸ - 10 ¹⁰), mas ao mesmo tempo, a precisão dos cálculos com coordenadas ponderadas é significativamente reduzida devido ao erro de truncamento acumulado durante a soma ^[21] .

O valor absoluto do erro no cálculo do centro de massa ponderado de uma região com um tamanho de 4 × 4 elementos. A imagem integrada contém números de precisão únicos (32 bits).

O valor absoluto do erro no cálculo do centro de massa ponderado de uma região com um tamanho de 32 × 32 elementos. A imagem integrada contém números de precisão únicos (32 bits).

O maior valor absoluto é alcançado pelo cálculo do centro de massa ponderado para pequenas regiões. Um aumento no tamanho da região em duas ordens de grandeza leva a uma diminuição na magnitude do erro absoluto dos cálculos em quatro ordens de grandeza. Nesse caso, não foi encontrada dependência do erro de cálculo no intervalo de valores dos coeficientes de ponderação (que são usados para calcular as coordenadas ponderadas dos elementos).

Um aumento na faixa de pesos não afeta o valor absoluto do erro no cálculo do centro de massa ponderado. O gráfico mostra os erros para a região “pior” (no canto superior direito da imagem integrada). O tamanho da imagem integrada é 256 × 256 elementos.

O valor absoluto do erro no cálculo do centro de massa ponderado diminui com o aumento do tamanho da região. O gráfico mostra os erros para a região “pior” (no canto superior direito da imagem integrada).

Com base na análise descrita acima, podemos concluir que o uso de números de precisão única para calcular centros de massa ponderados usando imagens integradas faz sentido prático apenas para imagens de tamanho de cerca de 512 × 512 elementos. Com um aumento adicional no tamanho, a magnitude do erro se torna comparável ao tamanho do elemento da imagem. E, embora esse erro diminua com o aumento do tamanho da região, são regiões de tamanho pequeno que têm maior impacto no resultado final - a magnitude da força da gravidade - portanto, apenas os erros correspondentes devem ser levados em consideração.

Quanto às imagens maiores, você pode usar coordenadas ponderadas de precisão dupla ou adicionar outro nível de discretização: divida a imagem original em várias partes e leia as imagens integrais separadamente para cada uma dessas partes. Do ponto de vista da complexidade computacional, se mais de uma imagem integral for usada para calcular a soma dos elementos de uma região, mas esse "mais de uma" for uma constante, a complexidade do algoritmo de cálculo da soma não será alterada.

Conclusão

O exemplo acima do uso de uma imagem integrada provavelmente pode ser adaptado para desenvolver um algoritmo ideal O (1) para amostragem por importância (amostragem por importância). Os algoritmos existentes - e extremamente intensivos em recursos do ponto de vista da GPU - têm complexidade linear O (N) e encontram aplicação em métodos modernos de iluminação global ^{[22, 23]} .

Em geral, na minha opinião, imagens integradas são um dos algoritmos mais subestimados. Eles podem ser uma excelente alternativa ao mipmapping e à filtragem anisotrópica ao mesmo tempo, e levando em consideração como o último é implementado na GPU ^{[24, 25]} , é bem possível que eles já sejam uma medida mais eficaz.

Referências

Ver lista

Cálculo do centro de massa para O (1) usando imagens integradas

N

Problema de gravidade para o campo momentum

Imagem integrada

Uma solução aproximada para o problema gravitacional usando uma imagem integrada

Conclusão

Referências

More articles: