У меня есть требование, которое требует сопоставления образца набора значений цвета с известным набором значений, чтобы найти либо точное совпадение, либо совпадения, находящиеся в пределах приемлемого расстояния. Я не совсем уверен, какой алгоритм лучше всего подходит для этого, и я ищу предложения.
Я думал об использовании SQL-запроса, так как думаю, что это был бы простой подход, однако в идеале это должно было бы выполняться в памяти на сервере приложений или даже на графическом процессоре для максимальной скорости.
Пример:
Допустим, нам дан набор из трех значений цвета RGB, двух синих и оранжевого:
Пример набора:
Цвет 1: 81 177 206 (синий)
Цвет 2: 36, 70, 224 (синий)
Цвет 3: 255, 132, 0 (оранжевый)
Этот набор из 3 значений цвета должен быть сопоставлен с гораздо большим набором значений цвета, чтобы увидеть, существует ли этот набор в нем, либо с одинаковыми точными значениями RGB для каждого из 3 цветов, либо - существует ли какой-либо шаблон, где значение RGB цветов варьируется в приемлемой степени. Предположим, что любой из компонентов RGB может быть до 3 цифр выше или ниже по значению.
Допустим, наш большой набор известных значений цвета, по которым мы будем искать, выглядит так:
Известный набор:
Color 1 Color 2 Color 3
Sample A: [25, 25, 25], [10, 10, 10], [100, 100, 100]
Sample B: [125, 125, 125], [10, 10, 10], [200, 200, 200]
Sample C: [13, 87, 255], [10, 10, 10], [100, 100, 100]
Sample D: [67, 111, 0], [10, 10, 10], [200, 200, 200]
Sample E: [255, 255, 255], [10, 10, 10], [100, 100, 100]
Учитывая этот сценарий, мы не найдем совпадений, когда проверим наш выборочный набор, потому что ни один из известных цветов не имеет Color 1, который хоть сколько-нибудь близок к значениям нашего выборочного набора. Однако давайте добавим в Известный набор еще один цвет, который будет возвращать положительное совпадение:
Sample F: [81,177,206], [36, 70, 224], [255, 132, 0]
Если бы образец F существовал с этими значениями в известном наборе, мы получили бы положительное совпадение, потому что это точные значения RGB в качестве цвета 1 в нашем наборе образцов. Кроме того, нам нужно принять разную степень различий в значениях RGB, поэтому следующее также вернет положительные совпадения, поскольку каждое значение RGB находится в пределах 3 цифр от значений цвета 1 из набора образцов:
Положительные совпадения: (помните, что цвет 1: 81 177 206)
Образец F: 80 177 206 (красный канал находится на расстоянии 1 цифры)
Пример F: 81,175,204 (зеленый и синий каналы на расстоянии 2 цифры)
Образец F: 82 179 208 (все три канала в пределах 3 цифр)
Однако, если расстояние слишком велико, совпадение не будет найдено. Любой компонент RGB должен быть в пределах 3 цифр, чтобы вызвать положительный результат. Таким образом, если бы образец F выглядел следующим образом, мы бы не получили положительный результат, поскольку расстояние слишком велико:
Отрицательные обращения:
Образец F: 85,177,206 (красный канал находится на расстоянии 4 цифр)
Образец F: 81,170, 206 (зеленый канал находится на расстоянии 7 цифр)
Образец F: 81 177,200 (синий канал находится на расстоянии 6 цифр)
До сих пор мы учитывали только цвет 1 из набора образцов. Однако требование требует учета всего набора образцов. Таким образом, если для цвета 1 не удается найти положительных совпадений, мы предполагаем, что совпадений нет вообще, и не рассматриваем цвета 2 и 3 из набора образцов.
Однако, если мы находим положительный результат для Цвета 1, скажем, 80 177 206, что всего на 1 цифру меньше в красном канале 80 против 81, тогда мы делаем продолжение обработки Цвета 2, и если мы находим положительный соответствует этому, затем мы обрабатываем Color 3 и так далее.
Каковы ваши предложения по алгоритму, лучше всего подходящему для этой задачи? Мне нужно что-то, что позволит известному набору очень масштабироваться без слишком большого снижения производительности. Вероятно, в известном наборе будет более 1 миллиона образцов в масштабе.
Я подумал об использовании хеш-таблиц, по одной на каждый цвет, для построения известного набора. Таким образом, я мог проверить совпадение для цвета 1 и, если оно было найдено, проверить хэш-таблицу для цвета 2 и остановиться, когда совпадений больше не было. Если бы я прошел через все 3 цвета/хеш-таблицы с положительными совпадениями, то у меня было бы общее положительное совпадение, в противном случае — нет. Однако этот подход не учитывает дисперсию, необходимую для каждого из каналов RGB для каждого цвета. Было бы слишком много комбинаций, чтобы можно было построить хеш-таблицы, чтобы хранить все это.
Заранее спасибо и спасибо, что дочитали до конца!