Ближайший цвет RGB из списка цветов - PullRequest
Новая
       5

Ближайший цвет RGB из списка цветов

0 голосов
/ 08 февраля 2019

Я был на собеседовании, и меня попросили создать эффективный алгоритм для решения следующей задачи:

Ввод:

У нас есть список цветов RGB.Каждый цвет представлен 3 координатами <x,y,z> от 0 до 255. Этот список никогда не меняется.

Мы получаем каждый раз какой-то дополнительный цвет ( не обязательно из списка выше), и нам нужновернуть ближайший (по расстоянию) цвет из списка к дополнительному цвету.

Примечания:

  1. Мы можем выполнить некоторую предварительную обработку списка цветов, поскольку список никогда не меняется.

  2. Расстояние между цветами, определенное как: d = ((x2 - x1)^2 + (y2 - y1)^2 + (z2 - z1)^2)^1/2

Пример:

Позвольте: Список: {<1,1,1>,<1,0,1>,<2,2,2>,<0,1,0>} Дополнительный цвет: <0,0,0>

Результат: Минимальное расстояние до <0,0,0> равно <0,1,0>.

Моя попытка решить эту проблему:

  1. Очевидно, что мы можем выполнить предварительную обработку и сохранить все цветовые пары в мире, а также сохранить расстояние, и мы можем получить решение за время выполнения O (1), но с огромнымпамять (255^3*n)

  2. Самым наивным решением является циклическое перемещение по списку и вычисление расстояния между каждым цветом из списка до дополнительного цвета и возврат цвета с минимальным расстоянием,Это берет O(n), где n - длина списка цветов.

Я пытался, возможно, сделать какую-то сортировку списка с координатами x, y, z и сохранить 3 отсортированного списка илиСортировка по расстоянию до <0,0,0>, но я понятия не имею, как продолжить это.

Я также видел это , но вопрос не в алгоритмическом подходе к проблеме.

1 Ответ

0 голосов
/ 08 февраля 2019

Предварительная обработка полной таблицы поиска не так уж немыслима в наше время.Если у вас меньше 256 эталонных цветов, в необходимом массиве есть 256³ (не 255³) ​​записей, что составляет 17 МБ.(Удвоение для 65536 цветов.) Но вам действительно нужны веские причины, чтобы использовать такое устройство.

Если количество цветов разумное, наивное решение вполне приемлемо.

Для большего числацветов (скажем, от 10 и выше) возможны несколько практических решений:

  • kD-дерево (где k = 3);время запроса близко к O (Log N);

  • октре;время запроса близко к O (Log N), если цвета не кластеризованы;

  • сетка (например, 4096 ячеек размера 16);время запроса O (N), но в удачных случаях асимптотическую константу можно сделать очень маленькой.

Инструменты вычислительной геометрии могут предложить трехмерную диаграмму Вороного, объединенную с локатором вТрехмерное подразделение, но оно сложное и довольно сложное для реализации, даже если оно будет поддерживать гарантированное время запроса O (Log N).

Я бы лично предпочел kD-дерево.

...