Distribua objetos em um cubo para que eles tenham distância máxima entre si

11

Estou tentando usar uma câmera colorida para rastrear vários objetos no espaço. Cada objeto terá uma cor diferente e, para poder distinguir bem entre cada objeto, estou tentando garantir que cada cor atribuída a um objeto seja tão diferente de qualquer cor quanto possível em qualquer outro objeto.

No espaço RGB, temos três planos, todos com valores entre 0 e 255. Neste cubo , eu gostaria de distribuir as n cores para que haja tanto distância entre si e os outros quanto possível. Uma restrição adicional é que ( 0 , 0 , 0 ) e ( 255 , 255 , 255 ) (ou o mais próximo possível deles) devem ser incluídos no n(0,0,0)/(255,255,255)n(0,0,0)(255,255,255)ncores, porque quero ter certeza de que nenhum dos meus objetos use as duas cores porque o plano de fundo provavelmente será uma dessas cores.(n−2)

Provavelmente, (incluindo preto e preto) não será superior a 14.n

Agradecemos antecipadamente por quaisquer dicas sobre como obter essas cores.

algorithms optimization computational-geometry Matt
fonte
2
Eu acho que você deve considerar apenas um espaço bidimensional, porque sua câmera provavelmente não será capaz de distinguir objetos com a mesma cor, mas com intensidades diferentes. O problema é interessante embora.
Stéphane Gimenez
As três dimensões são provenientes dos três planos de cores: vermelho, verde e azul, onde cada um pode assumir valores de 0 a 255 independentemente. No espaço RGB, acho que não há intensidade. Existem outros espaços de cores que podem ser mais adequados para isso, pois podem ser apenas em 2D, embora eu não saiba muito sobre eles.
Matt
Se você pode controlar com precisão a quantidade de luz projetada nos objetos, clique em OK. No espaço RGB (100, 100, 100) e (200, 200, 200), chamei a mesma cor (cinza) com intensidades diferentes.
Stéphane Gimenez
@ Matt, Stephane parece sugerir que você use um cubo HSL ou HSV em vez de um cubo RGB. As cores são mapeadas, mais ou menos, mas você pode ignorar o componente S para um mapa 2D. Eu sugeriria uma escala 1D somente para H em um SV ou SL escolhido, que manteria suas cores em um "tom" estético semelhante. O algoritmo de distribuição igual a 1D também é mais simples!
precisa
1
Sim, a distância máxima em pares. @ uosɐſ O HSV realmente pareceu retornar melhores resultados do que o RGB. Mesmo usando todos os três planos HSV, eu poderia selecionar melhor cores individuais com base na distância de cada cor ideal.
Matt

Respostas:

4

Todas as cores estarão na superfície do cubo RGB, a menos que eu esteja enganado, pelo mesmo motivo que toda a carga elétrica aparece na superfície dos condutores elétricos. Isso sugere o seguinte método para determinar as cores:

  • interpretar o espaço de cores RGB como um espaço cartesiano XYZ;
  • interpretar cores candidatas como partículas carregadas, por exemplo, elétrons;
  • encontre o estado de baixa energia do sistema através, por exemplo, de recozimento simulado;

n∼15

Depois que as partículas convergem, você tem o arranjo das cores interpretando pontos como cores. Inicialmente, as partículas podem ser dispostas aleatoriamente na superfície do cubo, com um pequeno espaçamento (ajuda a problemas de convergência e estabilidade). Colocar pequenos grupos nas faces do cubo deve funcionar.

Para evitar ficar preso em um mínimo local (em vez de global), você pode "pulsar" algum pequeno campo elétrico aleatório após a convergência e verificar se o sistema volta à mesma configuração ou diferente. É um pouco improvável que partículas colocadas aleatoriamente façam isso neste cenário, mas possível.

EDITAR:

Como apontado nos comentários, a suposição de que soluções ótimas deveriam estar apenas na superfície provavelmente não vale para todas as geometrias no caso discreto.

Felizmente, isso tem pouca influência no restante da técnica descrita acima. Partículas podem ser inicialmente colocadas em qualquer lugar; deixe algum espaço entre pares de partículas para estabilidade e cobertura e, em seguida, itere o sistema para convergência, em seguida, pulsar algumas vezes (possivelmente com intensidade crescente) para ver se você pode fazer com que o sistema converja para uma configuração diferente (possivelmente melhor) .

Observe também que acredito que esse método irá maximizar algo como "(harmônica?) Distância média entre pares de partículas". Se você deseja maximizar a distância mínima entre pares de partículas ou alguma outra média (geométrica?) Entre pares de partículas, isso pode não lhe proporcionar a melhor solução.

De qualquer forma, acho que essa técnica fornecerá uma maneira fácil de criar bons conjuntos de cores aproximadamente ótimos ... obter soluções "ideais" reais provavelmente não é necessário para o seu caso de uso. Naturalmente, se uma solução exata e comprovadamente ótima é desejada, a simulação numérica provavelmente não é o melhor caminho a percorrer.

Patrick87
fonte
3
n=9
@SaeedAmiri Observação interessante ... a questão pode muito bem estar com a natureza discreta desse problema, em comparação com a discussão física usual sobre densidades de carga. Vale ressaltar, no entanto, que não há razão para que a simulação numérica com recozimento físico ainda não encontre a solução que você descreve; resposta de edição para re-selecionar seu comentário e esse insight.
precisa saber é o seguinte
Vou ver se consigo descobrir como fazer isso no matlab (com simulannealbnd). A dificuldade que imagino será em traduzir o problema em uma função matemática que o matlab pode tentar minimizar.
21412 Matt
ps meu pensamento inicial era usar os vértices de um poliedro (icosaedro), já que eu também pensava que a solução provavelmente os teria na superfície, mas então eu não tinha certeza se isso seria verdade.
21412 Matt
No matlab, escrevi uma função que, dada um conjunto de pontos (x, y, z), calcula a soma das distâncias euclidianas em pares entre cada par de pontos no conjunto. Em seguida, divido um pelo resultado e o matlab deve encontrar o mínimo dessa função. Mas o matlab não está certo, por exemplo, para 4 pontos 3D, ele retorna os seguintes x1, x2, x3, x4; y1, y2 .... pontos (intervalo de 0-1): 0,0001, 0,0031, 0,9993, 0,9920 ; 0,9970 0,0004 0,9919 0,0030; 0,0030 0,0003 0,9973 0,5756. No entanto, acho que é um problema do Matlab, por isso vou aceitar isso.
Matt