Распределите объекты в кубе так, чтобы они имели максимальное расстояние между собой

Я пытаюсь использовать цветную камеру для отслеживания нескольких объектов в пространстве. Каждый объект будет иметь свой цвет, и чтобы иметь возможность хорошо различать каждый объект, я стараюсь, чтобы каждый цвет, назначенный объекту, отличался от любого цвета на любом другом объекте, насколько это возможно.

В пространстве RGB у нас есть три плоскости, все со значениями от 0 до 255. В этом кубе я хотел бы распределить цветов так, чтобы было столько же Расстояние между собой и другими, насколько это возможно. Дополнительным ограничением является то, что и (или как можно ближе к ним) должны быть включены в $(0,0,0) / (255,255,255)$ $n$ $(0, 0, 0)$ $(255, 255, 255)$ $n$ цветов, потому что я хочу убедиться, что ни один из моих объектов не принимает ни один цвет, потому что фон, вероятно, будет одним из этих цветов. $(n-2)$

Вероятно, (включая черный и время) будет не более 14. $n$

Заранее спасибо за любые указатели о том, как получить эти цвета.

algorithms optimization computational-geometry Matt
источник

Я думаю, вы должны рассматривать только двухмерное пространство, потому что ваша камера, вероятно, не сможет различать объекты, которые имеют одинаковый цвет, но разные интенсивности. Проблема интересная, хотя.

Стефан Гименес

Три измерения происходят из трех цветовых плоскостей: красного, зеленого и синего, где они могут независимо принимать значения от 0 до 255. В пространстве RGB я не думаю, что есть интенсивность. Существуют другие цветовые пространства, которые могут быть более подходящими для этого, поскольку они могут быть только 2D, хотя я не знаю о них много.

Мэтт

Если вы можете точно контролировать количество света, излучаемого на объекты, тогда ОК. В пространстве RGB (100, 100, 100) и (200, 200, 200) есть то, что я назвал одним и тем же цветом (серым) с различной интенсивностью.

Стефан Гименес

@ Matt, Стефан, кажется, предлагает использовать куб HSL или HSV, а не RGB. Цвета отображаются более или менее, но тогда вы можете игнорировать S-компонент для 2D-карты. Я бы пошел дальше, чтобы предложить 1-мерную шкалу по одному H для выбранного SV или SL, которая бы сохраняла ваши цвета в подобном эстетическом «тоне». Алгоритм равного распределения по 1D тоже проще!

Джейсон Клебан

Да, максимальное попарное расстояние. @ uosɐſ HSV на самом деле, похоже, дал лучшие результаты, чем RGB. Даже используя все три плоскости HSV, я мог бы лучше выбирать отдельные цвета в зависимости от расстояния до каждого идеального цвета.

Мэтт

Все цвета будут на поверхности куба RGB, если я не ошибаюсь, по той же причине, по которой весь электрический заряд появляется на поверхности электрических проводников. Это предполагает следующий метод определения цветов:

интерпретировать цветовое пространство RGB как декартово XYZ-пространство;
интерпретировать цвета кандидатов как заряженные частицы, например электроны;
найти низкоэнергетическое состояние системы, например, путем имитации отжига;

$n \sim 15$

Как только частицы сходятся, вы получаете расположение цветов, интерпретируя точки как цвета. Первоначально частицы могут быть расположены случайным образом на поверхности куба с небольшим интервалом (помогает сходимости и проблемам стабильности). Помещение маленьких групп на лицах куба должно работать.

Чтобы не застрять в локальном (а не глобальном) минимуме, вы можете «пульсировать» некоторое небольшое случайное электрическое поле после схождения и посмотреть, возвращается ли система к той же конфигурации или к другой. Несколько маловероятно, что случайно расположенные частицы сделают это в этом сценарии, но возможно.

РЕДАКТИРОВАТЬ:

Как отмечено в комментариях, предположение, что оптимальные решения должны лежать только на поверхности, вероятно, не выполняется для всех геометрий в дискретном случае.

К счастью, это не имеет никакого отношения к остальной технике, описанной выше. Частицы могут быть изначально размещены где угодно; просто оставьте некоторое пространство между парами частиц для стабильности и покрытия, а затем итерируйте систему до сходимости, затем сделайте несколько импульсов (возможно, с увеличением интенсивности), чтобы увидеть, можно ли заставить систему сходиться к какой-то другой (возможно, лучшей) конфигурации ,

Также обратите внимание, что я считаю, что этот метод максимизирует что-то вроде «(гармоника?) Среднего расстояния между парами частиц». Если вы хотите максимизировать минимальное расстояние между парами частиц или какое-либо другое среднее (геометрическое?) Между парами частиц, это может не дать вам наилучшего решения.

В любом случае, я чувствую, что этот метод даст вам простой способ придумать хорошие приблизительно оптимальные наборы цветов ... получение реальных "оптимальных" решений, вероятно, не требуется для вашего варианта использования. Естественно, если требуется точное и доказуемо оптимальное решение, численное моделирование, вероятно, не лучший путь.

Patrick87
источник

n = 9

$n=9$

@SaeedAmiri Интересное наблюдение ... проблема вполне может быть связана с дискретным характером этой проблемы по сравнению с обычным физическим обсуждением плотностей заряда. Однако стоит отметить, что нет никаких причин, по которым численное моделирование с физическим отжигом все равно не могло бы найти решение, которое вы описываете; редактирование ответа, чтобы отразить ваш комментарий и это понимание.

Patrick87

Я посмотрю, смогу ли я понять, как это сделать в matlab (с simulannealbnd). Трудность я полагаю , будет в переводе проблемы в математическую функцию , которая MATLAB можно попробовать свести к минимуму.

Matt

PS Первоначально я думал о том, чтобы использовать вершины многогранника (икосаэдра), так как я также думал, что решение, вероятно, будет иметь их на поверхности, но тогда я не был уверен, что это будет правдой.

Matt

В MATLAB я написал функцию, которая данный набор (х, у, г) точек, он вычисляет сумму расстояний между попарно евклидовыми каждой парой точек в наборе. Затем я делю один на результат и Matlab должен найти минимум этой функции. Но не MATLAB получить это право, например, на 4 3D точек она возвращает следующее x1, x2, x3, x4; y1, y2 .... точек (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. Тем не менее, я думаю, что это вопрос Matlab, поэтому я приму это.

Matt

Распределите объекты в кубе так, чтобы они имели максимальное расстояние между собой

Ответы: