Учитывая значение RGB, что будет лучшим способом найти наиболее близкое совпадение в базе данных?

Question

У меня есть значение rgb, и если его нет в таблице цветов в моей базе данных, мне нужно найти ближайший цвет. Я думал сравнить все значения и найти разницу (в красном, зеленом и синем), а затем взять среднее. Наименьшее среднее отклонение должно быть ближайшего цвета. Мне кажется, что должен быть лучший путь. Есть идеи?

Answer 1

Рассматривая цвет как вектор в 3-мерном пространстве, вы можете легко вычислить разницу, используя 3d-пифагоры:

d = sqrt((r2-r1)^2 + (g2-g1)^2 + (b2-b1)^2)

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

Например, используя типичный взвешенный подход :

d = sqrt(((r2-r1)*0.3)^2 + ((g2-g1)*0.59)^2 + ((b2-b1)*0.11)^2)

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

Существуют также различные способы оптимизации этого расчета. Например, поскольку вы на самом деле не интересуетесь фактическим значением d, вы можете обойтись без квадратного корня:

d =   ((r2-r1)*0.30)^2
    + ((g2-g1)*0.59)^2
    + ((b2-b1)*0.11)^2

Обратите внимание, что во многих языках программирования, основанных на C-синтаксисе (например, C #), ^ не означает «повышение до степени», а скорее «двоичный исключающий или».

Так что, если бы это был C #, вы бы использовали Math.Pow, чтобы вычислить эту часть, или просто разверните и выполните умножение.

Добавлено : Судя по странице Разница в цвете в Википедии , существуют различные стандарты, которые пытаются обрабатывать различия в восприятии. Например, тот, который называется CIE94, использует другую формулу, в цветовой модели L*C*h, которая выглядит так, что на нее стоит обратить внимание, но зависит от того, насколько точной вы хотите, чтобы она была.

Answer 2

Евклидово расстояние difference = sqrt(sqr(red1 - red2) + sqr(green1 - green2) + sqr(blue1 - blue2)) - это стандартный способ для определения сходства двух цветов.

Однако, если у вас есть цвета в простом списке, то для поиска ближайшего цвета необходимо вычислить расстояние от нового цвета для каждого цвета в списке. Это операция O (n).

sqrt() - дорогостоящая операция, и если вы просто сравниваете два расстояния, вы можете просто пропустить sqrt().

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

Answer 3

Следующее делает именно то, что вы описываете:

select (abs(my_R - t.r) + abs(my_G - t.g) + abs(my_B - t.b)) / 3 as difference, t.*
from RGBtable t
order by difference desc;

Однако, вы можете получить лучшие результаты с чем-то нелинейным. В подходе «возьми средние», если цвет цели (25, 25, 25), цвет (45, 25, 25) будет ближе, чем (35, 35, 35). Тем не менее, держу пари, что второй будет выглядеть более внимательно, поскольку он также будет серым.

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

Answer 4

Пусть база данных сделает это за вас:

select top 1
  c.r,
  c.b,
  c.g
from
  color c
order by
  (square(c.r - @r) + square(c.g - @g) + square(c.b - @b))

Где @r, @g и @b - значения r, g, b для цвета, который вы ищете (синтаксис параметров SQL Server, поскольку вы не указали базу данных). Обратите внимание, что для этого все равно придется выполнять сканирование таблицы, поскольку в order by есть вызов функции.

Обратите внимание, что дополнительный вызов квадратного корня на самом деле не требуется, так как это монотонная функция. Не то чтобы это, вероятно, имело бы большое значение, но все же.

Answer 5

На один шаг лучше среднего - ближайший квадратный корень:

((delta red)^2 + (delta green)^2 + (delta blue)^2)^0.5

Это минимизирует расстояние в трехмерном цветовом пространстве.

Поскольку корень строго увеличивается, вы можете вместо этого искать максимум квадрата. То, как вы выразите это в SQL, будет зависеть от того, какую СУБД вы используете.

Answer 6

Если посмотреть на страницу Википедии о разнице в цвете , идея состоит в том, чтобы рассматривать цвета RGB как точки в трех измерениях. Разница между двумя цветами равна расстоянию между двумя точками:

difference = sqrt((red1 - red2)^2 + (green1 - green2)^2 + (blue1 - blue2)^2)

Answer 7

Сравнение образца цвета со всем списком цветов каждый раз, вероятно, не оптимально. Это можно оптимизировать, поместив цвета из списка цветов в дерево поиска. Если вы сравниваете образец цвета по его значению Красный, Зеленый и Синий (RGB), вы должны поместить цвета из списка цветов в трехмерное дерево поиска. Дерево поиска можно создать один раз и сохранить в файле (json, xml) или в базе данных. Это может стоить того, если важна скорость, например Есть много точек для сравнения.

• Используйте [k-d tree] со значениями R, G и B 0-256 в качестве координат X, Y и Z 1 .
• Или другой тип поиск ближайшего соседа .

Answer 8

Рассчитайте среднее значение и расстояние следующим образом:

(r + g + b) / 3 = average
(r - average) + (g - average) + (b - average) = distance

Это должно дать вам хорошее представление о ближайшем значении.