Respostas rápidas para suas perguntas individuais

O que você faz se sua imagem não tiver o mesmo tamanho em cada eixo?

O artigo usa imagens quadradas com comprimentos laterais com uma potência de 2. Isso facilita a explicação, mas não é necessário para o algoritmo funcionar. Veja a seção 3.1:

Sem perda de generalidade, podemos assumir que n é uma potência de 2.

Ou seja, essa suposição não é necessária para que o algoritmo funcione.

É possível executar o JFA em cada eixo separadamente e ainda obter resultados decentes?

A execução de cada eixo separadamente provavelmente dará mais resultados de pixel incorretos e , na maioria dos casos , leva mais tempo para ser executada. Em casos extremos em que um dos comprimentos laterais da imagem é menor que 8 (o número de direções de salto), pode ser mais rápido, pois o algoritmo trata essas 8 direções sequencialmente, mas para qualquer imagem mais ampla, a separação dos eixos perde a vantagem de tratá-los. em paralelo.

Na minha situação, idealmente, estou procurando apoiar tanto as sementes de ponto único quanto as de forma arbitrária

O artigo menciona sementes de formato arbitrário na seção 6 da subposição "Diagrama generalizado de Voronoi":

... nossos algoritmos tratam sementes generalizadas como coleções de sementes pontuais e, portanto, esperam herdar o bom desempenho obtido para sementes pontuais.

Portanto, desde que seja adequado ao seu objetivo modelar formas arbitrárias como coleções de pixels, você não precisa fazer nenhum ajuste no algoritmo. Simplesmente alimente uma textura que rotule todos os pixels em uma semente de forma arbitrária com o mesmo número de semente, mas com locais diferentes.

Sementes possivelmente até pesadas, em que a distância a uma semente é ajustada por um multiplicador e / ou um somador para dar mais ou menos influência

Para "ponderação em sementes como multiplicativa e aditiva", o artigo apenas menciona a possibilidade de passar na seção 8, como potencial trabalho futuro. No entanto, isso deve ser simples de implementar, desde que a ponderação desejada possa ser incluída nos dados de semente que são transmitidos de pixel em pixel.

O algoritmo atual passa <s, position(s)>para especificar uma semente e sua posição, e apenas uma semente é armazenada por pixel por vez. Estender isso para armazenar <s, position(s), weight(s)>fornece todas as informações necessárias para ponderar a função de distância e calcular se a nova semente que está sendo passada para um pixel está mais próxima do que a que está armazenando atualmente.

Você pode até incluir dois pesos, um multiplicativo e um aditivo, e apenas definir o multiplicativo como 1 e o aditivo como 0 quando não for necessário. Em seguida, seu algoritmo incluiria a possibilidade de ser usado para sementes com pesos multiplicativos, sementes com pesos aditivos ou mesmo uma combinação de ambas de uma vez ou parte de cada uma. Isso só precisaria

<s, position(s), multiplicative(s), additive(s)>

e o algoritmo atual seria equivalente a esse novo algoritmo usando

<s, position(s), 1, 0>

Explicação detalhada do porquê

$\log()$

O algoritmo não precisa ser adaptado para diferentes comprimentos laterais

Se os comprimentos laterais não forem iguais e não forem potências de 2, não há necessidade de adaptar o algoritmo. Ele já lida com pixels na borda da imagem para os quais algumas das direções de salto levam para fora da imagem. Como o algoritmo já omite as informações de propagação para direções que saem da imagem, uma largura ou altura que não seja uma potência de 2 não será um problema. Para uma imagem de largura W e altura H, o tamanho máximo do salto necessário será

2^{⌈ \log (max (W, H)) ⌉ - 1}

$\large2^{\lceil\log(\max(W,H))\rceil-1}$

No caso de largura e altura iguais N, isso reduz a

2^{⌈ \log (N) ⌉ - 1}

$\large2^{\lceil\log(N)\rceil-1}$

No caso de um comprimento lateral N que é uma potência de 2, isso reduz a

2^{\log (N) - 1} = N / 2

$\large2^{\log(N)-1}=N/2$

conforme usado no papel.

Em termos mais intuitivos, arredonde o comprimento máximo do lado até a próxima potência de 2 e reduza-o pela metade para obter o tamanho máximo do salto.

Isso sempre é suficiente para cobrir todos os pixels da imagem e todos os outros pixels da imagem, pois o deslocamento para qualquer pixel estará no intervalo de 0 a N-1 se o maior comprimento lateral for N. Combinações dos poderes de 2 de 0 a N / 2 cobrirá todos os números inteiros até N-1 se N for uma potência de 2 e se N não for uma potência de 2, o intervalo coberto só poderá ser maior do que o necessário, devido ao limite máximo do logaritmo ( arredondando para a próxima potência de 2).

Imagens com lados sem potência de 2 não serão drasticamente menos eficientes

O número de saltos depende do comprimento lateral mais longo, digamos L. Se L é uma potência de 2, então o número de saltos é . Se L não for uma potência de 2, o número de saltos será . Para uma imagem razoavelmente grande, isso não será uma grande diferença. $\log(L)$ $\lceil\log(L)\rceil$

Por exemplo, uma imagem 1024 por 1024 exigirá 10 iterações de salto. Uma imagem de 512 por 512 exigirá 9 iterações de salto. Qualquer coisa entre os dois tamanhos também exigirá 10 iterações. Mesmo no pior caso de uma imagem com apenas uma potência de 2, como uma imagem de 513 por 513, será necessária apenas 1 iteração adicional, que nessa escala é aproximadamente 11% a mais (10 em vez de 9).

Imagens não quadradas são menos eficientes por área

Como o número de iterações necessárias é determinado pelo maior comprimento lateral, o tempo gasto para uma imagem de 1024 por 1024 será o mesmo que para uma imagem de 1024 por 16. Uma imagem quadrada permite que uma área maior seja coberta no mesmo número de iterações.

É provável que a separação de eixos reduza a qualidade

A seção 5 do artigo descreve possíveis erros. Cada pixel é alcançável por um caminho de qualquer outro pixel, mas alguns caminhos não trazem a semente mais próxima correta, porque essa semente não é a mais próxima de um pixel anterior no caminho. Diz-se que um pixel que não permite que uma semente se propague além da "matou". Se a semente mais próxima de um pixel for eliminada em todos os caminhos para esse pixel, o pixel registrará outra semente e haverá uma cor incorreta na imagem final.

Apenas existe um caminho que não mata a semente para que o resultado final esteja correto. Cores incorretas ocorrem apenas quando todos os caminhos da semente correta para um determinado pixel são bloqueados.

Se um caminho envolver saltos horizontais e verticais alternados, os eixos de separação tornarão esse caminho impossível (todos os saltos horizontais serão executados antes de todos os saltos verticais, impossibilitando a alternância). Saltos diagonais não serão possíveis. Portanto, qualquer caminho que alterne ou contenha saltos diagonais será excluído. Cada pixel ainda terá um caminho para todos os outros pixels, mas como agora existem menos caminhos, há mais chances de um determinado pixel ser impedido de receber a semente correta, portanto, o resultado final será mais suscetível a erros.

É provável que eixos separados façam com que o algoritmo demore mais

A eficiência provavelmente seria reduzida pela separação dos eixos, pois as inundações não seriam mais feitas em paralelo, mas seriam repetidas para cada eixo. Para 2D, isso provavelmente levaria aproximadamente o dobro do tempo e, para o 3D, aproximadamente três vezes mais.

Isso pode ser mitigado pela falta de saltos diagonais, mas eu ainda esperaria uma redução geral na eficiência.

Trichoplax
fonte

Eu já comecei a experimentar um pouco disso. Descobri que a amostragem em um sinal de + (5 leituras), em vez dos 9 completos, não mostrou diferenças nos meus testes, mas tenho certeza que com situações mais complexas, haveria diferenças. Fazer um x jfa completo e, em seguida, um jfa y completo comete muitos erros. Estarei interessado em ouvir mais detalhes / informações, se tiver, mas aceitando sua resposta: P

Alan Wolfe

Esqueceu-se, aqui está o link para um dos meus experimentos: shadertoy.com/view/Mdy3D3 #

Alan Wolfe

Interessante que aparentemente funcione tão bem com apenas 5 leituras - especialmente porque elas não podem ser paralelizadas. Como o documento lista os casos que levam ao erro, talvez você possa configurá-los deliberadamente e ver se 5 instruções de salto ainda são boas.

Trichoplax

Parece que você está pronto para postar sua própria resposta ...