Créditos ao Hobbies de Calvin por empurrar minha ideia de desafio na direção certa.
Considere um conjunto de pontos no plano, que chamaremos de sites , e associe uma cor a cada site. Agora você pode pintar o plano inteiro colorindo cada ponto com a cor do site mais próximo. Isso é chamado de mapa de Voronoi (ou diagrama de Voronoi ). Em princípio, os mapas de Voronoi podem ser definidos para qualquer métrica de distância, mas simplesmente usaremos a distância euclidiana usual r = √(x² + y²)
. ( Observação: você não precisa necessariamente saber como calcular e renderizar um deles para competir nesse desafio.)
Aqui está um exemplo com 100 sites:
Se você olhar para qualquer célula, todos os pontos nessa célula estarão mais próximos do site correspondente do que em qualquer outro site.
Sua tarefa é aproximar uma determinada imagem com um mapa de Voronoi. Você recebe a imagem em qualquer formato gráfico de varredura conveniente, além de um N inteiro . Você deve produzir até N sites e uma cor para cada site, de modo que o mapa Voronoi baseado nesses sites se assemelhe à imagem de entrada o mais próximo possível.
Você pode usar o snippet de pilha na parte inferior deste desafio para renderizar um mapa Voronoi a partir de sua saída ou pode renderizá-lo você mesmo, se preferir.
Você pode usar funções internas ou de terceiros para calcular um mapa Voronoi a partir de um conjunto de sites (se necessário).
Como é um concurso de popularidade, ganha a resposta com o maior número de votos. Os eleitores são incentivados a julgar as respostas
- quão bem as imagens originais e suas cores são aproximadas.
- quão bem o algoritmo funciona em diferentes tipos de imagens.
- quão bem o algoritmo funciona para N pequeno .
- se o algoritmo agrupa adaptativamente pontos nas regiões da imagem que exigem mais detalhes.
Imagens de teste
Aqui estão algumas imagens para testar seu algoritmo (alguns de nossos suspeitos comuns, outros novos). Clique nas imagens para versões maiores.
A praia na primeira fila foi desenhada por Olivia Bell e incluída com sua permissão.
Se você quer um desafio extra, tente Yoshi com um fundo branco e acerte a linha da barriga.
Você pode encontrar todas essas imagens de teste nesta galeria de imagens, onde é possível fazer o download de todas elas como um arquivo zip. O álbum também contém um diagrama aleatório de Voronoi como outro teste. Para referência, aqui estão os dados que os geraram .
Inclua diagramas de exemplo para uma variedade de imagens diferentes e N , por exemplo, 100, 300, 1000, 3000 (além de pastas para algumas das especificações de célula correspondentes). Você pode usar ou omitir bordas pretas entre as células como achar melhor (isso pode parecer melhor em algumas imagens do que em outras). Não inclua os sites (exceto em um exemplo separado, talvez se você quiser explicar como o posicionamento do site funciona, é claro).
Se você deseja mostrar um grande número de resultados, pode criar uma galeria no imgur.com , para manter o tamanho das respostas razoáveis. Como alternativa, coloque miniaturas em sua postagem e faça links para imagens maiores, como fiz na resposta de referência . Você pode obter as pequenas miniaturas anexando s
o nome do arquivo no link imgur.com (por exemplo, I3XrT.png
-> I3XrTs.png
). Além disso, fique à vontade para usar outras imagens de teste, se encontrar algo legal.
Renderer
Cole sua saída no seguinte snippet de pilha para renderizar seus resultados. O formato exato da lista é irrelevante, desde que cada célula seja especificada por 5 números de ponto flutuante na ordem x y r g b
, onde x
e y
são as coordenadas do site da célula e r g b
os canais de cores vermelho, verde e azul no intervalo 0 ≤ r, g, b ≤ 1
.
O trecho fornece opções para especificar uma largura de linha das bordas da célula e se os sites da célula devem ou não ser exibidos (o último principalmente para fins de depuração). Mas observe que a saída só é renderizada novamente quando as especificações da célula são alteradas - portanto, se você modificar algumas das outras opções, adicione um espaço às células ou algo assim.
Créditos maciços a Raymond Hill por escrever esta realmente agradável biblioteca JS Voronoi .
Desafios relacionados
fonte
Respostas:
Amostra de disco de Poisson ponderada em Python + scipy + scikit-image
Minha solução é bastante complexa. Eu faço um pré-processamento na imagem para remover o ruído e obter um mapeamento de quão interessante é cada ponto (usando uma combinação de entropia local e detecção de borda):
Depois, escolho os pontos de amostragem usando a amostragem de disco de Poisson com um giro: a distância do círculo é determinada pelo peso que determinamos anteriormente.
Depois que tenho os pontos de amostragem, divido a imagem em segmentos voronoi e atribuo a média L * a * b * dos valores de cores dentro de cada segmento a cada segmento.
Tenho muitas heurísticas e também preciso fazer um pouco de matemática para garantir que o número de pontos de amostra esteja próximo
N
. FicoN
exatamente superando um pouco e depois removendo alguns pontos com uma heurística.Em termos de tempo de execução, esse filtro não é barato , mas nenhuma imagem abaixo levou mais de 5 segundos para ser criada.
Sem mais delongas:
Imagens
Respectivamente,
N
é 100, 300, 1000 e 3000:fonte
C ++
Minha abordagem é bastante lenta, mas estou muito feliz com a qualidade dos resultados que ela fornece, principalmente com relação à preservação de arestas. Por exemplo, aqui está Yoshi e a Cornell Box com apenas 1000 sites cada:
Existem duas partes principais que o fazem funcionar. O primeiro, incorporado na
evaluate()
função, pega um conjunto de locais candidatos, define as cores ideais e retorna uma pontuação para o PSNR do mosaico Voronoi renderizado versus a imagem de destino. As cores de cada site são determinadas pela média dos pixels da imagem de destino cobertos pela célula ao redor do site. Uso o algoritmo de Welford para ajudar a calcular a melhor cor para cada célula e o PSNR resultante, usando apenas uma única passagem sobre a imagem, explorando a relação entre variação, MSE e PSNR. Isso reduz o problema a encontrar o melhor conjunto de locais do site sem levar em consideração a cor.A segunda parte, então, incorporada
main()
, tenta encontrar esse conjunto. Começa escolhendo um conjunto de pontos aleatoriamente. Em seguida, em cada etapa, ele remove um ponto (round-robin) e testa um conjunto de pontos candidatos aleatórios para substituí-lo. O que produz o PSNR mais alto do grupo é aceito e mantido. Efetivamente, isso faz com que o site salte para um novo local e geralmente melhora a imagem bit a bit. Observe que o algoritmo intencionalmente não retém o local original como candidato. Às vezes, isso significa que o salto diminui a qualidade geral da imagem. Permitir que isso aconteça ajuda a evitar ficar preso nos máximos locais. Também fornece um critério de parada; o programa termina após executar um certo número de etapas sem melhorar o melhor conjunto de sites encontrado até o momento.Observe que essa implementação é bastante básica e pode facilmente levar horas de tempo no núcleo da CPU, especialmente à medida que o número de sites aumenta. Ele recalcula o mapa completo de Voronoi para todos os candidatos e a força bruta testa a distância de todos os sites de cada pixel. Como cada operação envolve remover um ponto de cada vez e adicionar outro, as alterações reais na imagem em cada etapa serão razoavelmente locais. Existem algoritmos para a atualização incremental eficiente de um diagrama de Voronoi e acredito que eles dariam a esse algoritmo uma tremenda aceleração. Para este concurso, no entanto, escolhi manter as coisas simples e com força bruta.
Código
Corrida
O programa é independente e não possui dependências externas além da biblioteca padrão, mas exige que as imagens estejam no formato binário PPM . Eu uso o ImageMagick para converter imagens em PPM, embora o GIMP e muitos outros programas também possam fazê-lo.
Para compilá-lo, salve o programa como
voronoi.cpp
e, em seguida, execute:Espero que provavelmente funcione no Windows com versões recentes do Visual Studio, embora ainda não tenha tentado. Você quer ter certeza de que está compilando com o C ++ 11 ou melhor e o OpenMP ativado, se o fizer. O OpenMP não é estritamente necessário, mas ajuda muito a tornar os tempos de execução mais toleráveis.
Para executá-lo, faça algo como:
O arquivo posterior será atualizado com os dados do site. A primeira linha terá a largura e a altura da imagem, seguidas pelas linhas dos valores x, y, r, g, b adequados para copiar e colar no renderizador Javascript na descrição do problema.
As três constantes na parte superior do programa permitem ajustá-lo para velocidade versus qualidade. O
decimation
fator aumenta a imagem de destino ao avaliar um conjunto de sites para cores e PSNR. Quanto mais alto, mais rápido o programa será executado. A configuração para 1 usa a imagem em resolução máxima. Acandidates
constante controla quantos candidatos testar em cada etapa. Maior oferece uma chance maior de encontrar um bom local para o qual pular, mas torna o programa mais lento. Finalmente,termination
é quantas etapas o programa pode executar sem melhorar sua produção antes de sair. Aumentá-lo pode dar melhores resultados, mas leva um pouco mais de tempo.Imagens
N
= 100, 300, 1000 e 3000:fonte
IDL, refinamento adaptável
Este método é inspirado no Refinamento de Malha Adaptativa a partir de simulações astronômicas e também na superfície de subdivisão . Esse é o tipo de tarefa em que a IDL se orgulha, que você poderá contar pelo grande número de funções internas que pude usar. : D
Eu produzi alguns dos intermediários para a imagem de teste yoshi de fundo preto, com
n = 1000
.Primeiro, executamos uma escala de cinza da luminância na imagem (usando
ct_luminance
) e aplicamos um filtro Prewitt (prewitt
consulte a Wikipedia ) para uma boa detecção de borda:Depois vem o trabalho grunhido real: subdividimos a imagem em 4 e medimos a variação em cada quadrante da imagem filtrada. Nossa variância é ponderada pelo tamanho da subdivisão (que neste primeiro passo é igual), para que regiões "nervosas" com alta variância não sejam subdivididas cada vez menores. Em seguida, usamos a variação ponderada para segmentar subdivisões com mais detalhes e subdividimos iterativamente cada seção rica em detalhes em 4 adicionais, até atingirmos o número alvo de sites (cada subdivisão contém exatamente um site). Como adicionamos três sites cada vez que iteramos, terminamos com
n - 2 <= N <= n
sites.Fiz uma .webm do processo de subdivisão para esta imagem, que não consigo incorporar, mas está aqui ; a cor em cada subseção é determinada pela variação ponderada. (Fiz o mesmo tipo de vídeo para o yoshi de fundo branco, para comparação, com a tabela de cores invertida para que ela fique em branco em vez de preto; está aqui .) O produto final da subdivisão é semelhante a este:
Depois de termos nossa lista de subdivisões, passamos por cada subdivisão. A localização final do site é a posição do mínimo da imagem Prewitt, ou seja, o pixel menos "nervoso", e a cor da seção é a cor desse pixel; aqui está a imagem original, com sites marcados:
Em seguida, usamos o interno
triangulate
para calcular a triangulação de Delaunay dos sites e o internovoronoi
para definir os vértices de cada polígono de Voronoi, antes de desenhar cada polígono em um buffer de imagem em sua respectiva cor. Por fim, salvamos um instantâneo do buffer de imagem.O código:
Ligue para isso via
voro_map, n, image, output_filename
. Também incluí umwrapper
procedimento, que passou por cada imagem de teste e foi executado com 100, 500 e 1000 sites.Saída coletada aqui e aqui estão algumas miniaturas:
n = 100
n = 500
n = 1000
fonte
Python 3 + PIL + SciPy, k difuso
O algoritmo
A idéia principal é que o agrupamento de k-significa particione naturalmente a imagem nas células Voronoi, uma vez que os pontos estão ligados ao centróide mais próximo. No entanto, precisamos adicionar de alguma forma as cores como uma restrição.
Primeiro, convertemos cada pixel no espaço de cores laboratório , para melhor manipulação das cores.
Então fazemos uma espécie de "detecção de ponta do pobre homem". Para cada pixel, examinamos seus vizinhos ortogonais e diagonais e calculamos a diferença média quadrática da cor. Em seguida, classificamos todos os pixels por essa diferença, com os pixels mais semelhantes aos vizinhos na frente da lista e os pixels mais diferentes dos vizinhos na parte de trás (ou seja, é mais provável que seja um ponto de extremidade). Aqui está um exemplo para o planeta, onde quanto mais brilhante o pixel, mais diferente ele é de seus vizinhos:
(Existe um padrão claro de grade na saída renderizada acima. De acordo com @randomra, isso provavelmente se deve à codificação JPG com perdas ou à imgur de compactação das imagens.)
Em seguida, usamos essa ordem de pixels para provar um grande número de pontos a serem agrupados. Usamos uma distribuição exponencial, priorizando pontos que são mais parecidos com arestas e "interessantes".
Para o agrupamento, primeiro escolhemos
N
centróides, escolhidos aleatoriamente usando a mesma distribuição exponencial acima. Uma iteração inicial é executada e, para cada um dos clusters resultantes, atribuímos uma cor média e um limite de variação de cores. Em seguida, para várias iterações, nós:(Clique para ampliar)
Finalmente, amostramos um grande número de pontos, desta vez usando uma distribuição uniforme. Usando outra árvore kd, atribuímos cada ponto ao centróide mais próximo, formando aglomerados. Em seguida, aproximamos a cor mediana de cada cluster usando um algoritmo de escalada, fornecendo as cores finais das células (idéia para esta etapa graças a @PhiNotPi e @ MartinBüttner).
Notas
Além de emitir um arquivo de texto para o trecho (
OUTFILE
), seDEBUG
estiver definido comoTrue
o programa, também emitirá e sobrescreverá as imagens acima. O algoritmo leva alguns minutos para cada imagem, por isso é uma boa maneira de verificar o progresso que não adiciona muito ao tempo de execução.Saídas de amostra
N = 32:
N = 100:
N = 1000:
N = 3000:
fonte
Mathematica, Células Aleatórias
Esta é a solução de linha de base, para que você tenha uma idéia do mínimo que estou pedindo a você. Dado o nome do arquivo (localmente ou como um URL)
file
e N inn
, o código a seguir simplesmente seleciona N pixels aleatórios e usa as cores encontradas nesses pixels. Isso é realmente ingênuo e não funciona incrivelmente bem, mas quero que vocês superem isso depois de tudo. :)Aqui estão todas as imagens de teste para N = 100 (todas as imagens possuem link para versões maiores):
Como você pode ver, estes são essencialmente inúteis. Embora possam ter algum valor artístico, de uma maneira expressionista, as imagens originais são quase irreconhecíveis.
Para N = 500 , a situação melhora um pouco, mas ainda existem artefatos muito estranhos, as imagens parecem desbotadas e muitas células são desperdiçadas em regiões sem detalhes:
Sua vez!
fonte
Dimensions@ImageData
e nãoImageDimensions
? Você pode evitar o lentoImageData
completamente usandoPixelValue
.Mathematica
Todos sabemos que Martin ama o Mathematica, então deixe-me tentar com o Mathematica.
Meu algoritmo usa pontos aleatórios das bordas da imagem para criar um diagrama voronoi inicial. O diagrama é então pré-modificado por um ajuste iterativo da malha com um filtro médio simples. Isso fornece imagens com alta densidade celular perto de regiões de alto contraste e células visualmente agradáveis sem ângulos malucos.
As imagens a seguir mostram um exemplo do processo em ação. A diversão é um pouco estragada pelo Antialiasing ruim do Mathematicas, mas temos gráficos vetoriais, que devem valer alguma coisa.
Esse algoritmo, sem a amostragem aleatória, pode ser encontrado na
VoronoiMesh
documentação aqui .Imagens de teste (100,300,1000,3000)
Código
fonte
Graphics@Table[ Append[mp, VertexColors -> RGBColor /@ ImageValue[img, First[mp]]], {mp, MeshPrimitives[voronoiRelaxed, 2]}]
Python + SciPy + emcee
O algoritmo que usei é o seguinte:
O algoritmo parece funcionar muito bem. Infelizmente, ele só pode ser executado sensivelmente em imagens pequenas. Não tive tempo de pegar os pontos Voronoi e aplicá-los às imagens maiores. Eles podem ser refinados neste momento. Eu também poderia ter executado o MCMC por mais tempo para obter melhores mínimos. O ponto fraco do algoritmo é que ele é bastante caro. Não tive tempo de aumentar além de 1000 pontos e algumas das imagens de 1000 pontos ainda estão sendo refinadas.
(clique com o botão direito do mouse e visualize a imagem para obter uma versão maior)
Os links para versões maiores são http://imgur.com/a/2IXDT#9 (100 pontos), http://imgur.com/a/bBQ7q (300 pontos) e http://imgur.com/a/rr8wJ (1000 pontos)
Imagens mascaradas sem nitidez se parecem com as seguintes. Pontos aleatórios são selecionados na imagem se um número aleatório for menor que o valor da imagem (normatizado para 1):
Vou postar imagens maiores e os pontos Voronoi, se tiver mais tempo.
Edit: Se você aumentar o número de walkers para 100 * npts, altere a função de custo para alguns quadrados dos desvios em todos os canais e aguarde um longo tempo (aumentando o número de iterações para interromper o loop para 200), é possível criar boas imagens com apenas 100 pontos:
fonte
Usando a energia da imagem como um mapa de pontos-peso
Na minha abordagem para esse desafio, eu queria uma maneira de mapear a "relevância" de uma área de imagem específica com a probabilidade de um ponto específico ser escolhido como um centróide de Voronoi. No entanto, eu ainda queria preservar a sensação artística do mosaico de Voronoi escolhendo aleatoriamente pontos de imagem. Além disso, eu queria operar imagens grandes, para não perder nada no processo de redução de amostras. Meu algoritmo é mais ou menos assim:
Resultados
N
= 100, 500, 1000, 3000fonte