Distribuya los objetos en un cubo para que tengan una distancia máxima entre ellos.

11

Estoy tratando de usar una cámara a color para rastrear múltiples objetos en el espacio. Cada objeto tendrá un color diferente y para poder distinguir bien entre cada objeto, estoy tratando de asegurarme de que cada color asignado a un objeto sea tan diferente de cualquier color en cualquier otro objeto como sea posible.

En el espacio RGB, tenemos tres planos, todos con valores entre 0 y 255. En este cubo , me gustaría distribuir los colores para que haya tanta distancia entre ellos y otros como sea posible Una restricción adicional es que y (o tan cerca de ellos como sea posible) deben incluirse en los colores, porque quiero asegurarme de que ninguno de mis objetos toman cualquier color porque el fondo probablemente será uno de estos colores.n ( 0 , 0 , 0 ) ( 255 , 255 , 255 ) n ( n - 2 )(0,0,0)/(255,255,255)n(0,0,0)(255,255,255)n(n−2)

Probablemente, (incluyendo negro y while) no será más de alrededor de 14.n

Gracias de antemano por cualquier sugerencia sobre cómo obtener estos colores.

algorithms optimization computational-geometry Mate
fuente
2
Creo que solo debe considerar un espacio bidimensional, porque su cámara probablemente no podrá distinguir objetos que tengan el mismo color pero diferentes intensidades. Sin embargo, el problema es interesante.
Stéphane Gimenez
Las tres dimensiones provienen de los tres planos de color: rojo, verde y azul, donde cada uno puede tomar independientemente los valores de 0-255. En el espacio RGB, no creo que haya intensidad. Hay otros espacios de color que podrían ser más adecuados para esto, ya que podrían ser solo 2D, aunque no sé mucho sobre ellos.
Matt
Si puede controlar con precisión la cantidad de luz proyectada sobre los objetos, entonces está bien. En el espacio RGB (100, 100, 100) y (200, 200, 200) son lo que llamé el mismo color (gris) con diferentes intensidades.
Stéphane Gimenez
@ Matt, Stephane parece estar sugiriendo que use un cubo HSL o HSV en lugar de un cubo RGB. Los colores están asignados, más o menos, pero luego puede ignorar el componente S para un mapa 2D. Iría más allá para sugerir una escala 1D en H solo en un SV o SL elegido que mantendría sus colores en un "tono" estético similar. ¡El algoritmo de distribución igual sobre 1D también es más simple!
Jason Kleban
1
Sí, la distancia máxima por pares. @ uosɐſ HSV en realidad parecía devolver mejores resultados que RGB. Incluso utilizando los tres planos HSV, podría seleccionar mejor los colores individuales en función de la distancia a cada color ideal.
Matt

Respuestas:

4

Todos los colores estarán en la superficie del cubo RGB, a menos que me equivoque, por la misma razón que toda la carga eléctrica aparece en la superficie de los conductores eléctricos. Esto sugiere el siguiente método para determinar los colores:

  • interpretar el espacio de color RGB como un espacio cartesiano XYZ;
  • interpretar los colores candidatos como partículas cargadas, por ejemplo, electrones;
  • encontrar el estado de baja energía del sistema mediante, por ejemplo, recocido simulado;

Para , una simulación altamente precisa debería ser bastante rápida; podría usar una técnica Runge Kutta, o incluso el método de Euler con un pequeño paso de tiempo probablemente podría hacerlo (mucho más fácil de implementar / comprender). Podría sugerir la serie "Recetas numéricas" para la integración numérica / técnicas de cuadratura de interés.n∼15

Una vez que las partículas convergen, tiene la disposición de los colores al interpretar los puntos como colores. Inicialmente, las partículas se pueden organizar aleatoriamente en la superficie del cubo, con un poco de espacio (ayuda a los problemas de convergencia y estabilidad). Poner grupos pequeños en las caras del cubo debería funcionar.

Para evitar quedarse atascado en un mínimo local (en lugar de global), puede "pulsar" algún pequeño campo eléctrico aleatorio después de la convergencia y ver si el sistema vuelve a la misma configuración, o una diferente. Es poco probable que las partículas colocadas al azar hagan eso en este escenario, pero es posible.

EDITAR:

Como se señaló en los comentarios, la suposición de que las soluciones óptimas deberían estar solo en la superficie probablemente no se cumple para todas las geometrías en el caso discreto.

Afortunadamente, esto tiene poca relación con el resto de la técnica descrita anteriormente. Las partículas se pueden colocar inicialmente en cualquier lugar; solo deje espacio entre los pares de partículas para la estabilidad y la cobertura, y luego repita el sistema para converger, luego pulse varias veces (posiblemente con mayor intensidad) para ver si puede lograr que el sistema converja a una configuración diferente (posiblemente mejor) .

También tenga en cuenta que creo que este método maximizará algo así como "distancia media (¿armónica?) Entre pares de partículas". Si desea maximizar la distancia mínima entre pares de partículas, o algún otro promedio (¿geométrico?) Entre pares de partículas, esto puede no darle la mejor solución.

En cualquier caso, creo que esta técnica le brindará una manera fácil de encontrar buenos conjuntos de colores aproximadamente óptimos ... probablemente no sea necesario obtener soluciones "óptimas" reales para su caso de uso. Naturalmente, si se desea una solución exacta y demostrablemente óptima, la simulación numérica probablemente no sea la mejor opción.

Patrick87
fuente
3
Para mejor solución es colocar uno de los nodos en el centro del cubo y colocar a los demás en las esquinas del cubo, por lo que sus suposiciones no son ciertas. n=9
@SaeedAmiri Observación interesante ... el problema puede muy bien ser la naturaleza discreta de este problema, en comparación con la discusión física habitual de las densidades de carga. Sin embargo, vale la pena señalar que no hay razón para que la simulación numérica con recocido físico aún no encuentre la solución que usted describe; editando la respuesta para volver a reflejar su comentario y esta idea.
Patrick87
Veré si puedo descubrir cómo hacer esto en matlab (con simulannealbnd). La dificultad que imagino será en traducir el problema en una función matemática que matlab pueda intentar minimizar.
Matt
ps mi pensamiento inicial fue usar los vértices de un poliedro (icosaedro), ya que también pensé que la solución probablemente los tendría en la superficie, pero no estaba seguro de si eso sería cierto.
Matt
En matlab escribí una función, que dado un conjunto de puntos (x, y, z), calcula la suma de las distancias euclidianas por pares entre cada par de puntos en el conjunto. Luego divido uno por el resultado y se supone que matlab encuentra el mínimo de esta función. Pero matlab no lo hace bien, por ejemplo, para 4 puntos 3D devuelve los siguientes puntos x1, x2, x3, x4; y1, y2 .... (rango 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 obstante, creo que es un problema de matlab, así que aceptaré esto.
Matt