Есть ли алгоритм лучше, чем O (N ^ 2), чтобы взять набор цветов и вернуть цвета, которые контрастируют или отличаются?

Я пытаюсь придумать алгоритм, который может взять набор цветов X и вернуть новый набор цветов X ', который состоит только из контрастных цветов из исходного набора X. Другими словами, я хочу отфильтровать похожие цвета из прошел в цветовой комплектации. Если вы хотите думать о различиях цветов, можно подумать о том, чтобы отфильтровать все цвета, которые находятся на некотором расстоянии k от любого цвета в наборе.

Кто-нибудь знает, как это сделать за линейное время или за O (N). Я в порядке с другими сложностями времени, а также до тех пор, пока это не O (N ^ 2), каждое решение, которое я придумываю, занимает полиномиальное время. Я попытался свести проблему к знаменитому «найти все пары целых чисел в массиве, сумма которых равна K», но это сокращение не сработало. Я использую метрику deltaE, чтобы определить, насколько далеко друг от друга или насколько различны / контрастируют два цвета.


colors algorithm image-processing color-theory
person AyBayBay    schedule 23.12.2016    source источник
comment
не уверен, для чего вы это делаете (неясно и из вашего другого вопроса), но я думаю, что вы ищете методы квантования цвета, которые предназначены для уменьшения количества используемых цветов в изображении с минимальным воздействием по качеству ... обычно для этого используются методы кластеризации, см. Эффективное квантование цвета gif / изображения?, чтобы ускорить вас можно использовать таблицы LUT поиска, чтобы O(N^2) стало O(N.log(N)) или даже меньше   -  person Spektre    schedule 23.12.2016
comment
Если вы хотите сгенерировать новые цвета, вам следует использовать геометрический подход, который O(N^2) такой же, как и вы, но вы должны учитывать, что N^2 - это количество возвращаемых цветов .... так что вы не можете опускаться ниже этого   -  person Spektre    schedule 23.12.2016

Ответы (1)


arrow_upward
0
arrow_downward

Используйте дерево обложек для хранения цветов с метрикой ∆E. Для каждого цвета выполните поиск близости за O (log n) в дереве обложек и отклоните его, если ближайший цвет слишком близок.

person David Eisenstat    schedule 23.12.2016
comment
что вы имеете в виду под поиском близости времени O (logN)? Под этим я предполагаю, что вы имеете в виду найти всех ближайших соседей для данной точки (цвета), в основном все цвета / точки в пределах радиуса шара. Он говорит, что операция O (N). Это должно снова дать мне наихудшую временную сложность N ^ 2. Это еще хуже, потому что это N - это не мой переданный мной набор цветов, который я фильтрую, а пространство всех цветов RGB, которое составляет (256) ^ 3 баллов. Отсюда я получаю временную сложность: cs.princeton .edu / course / archive / spr05 / cos598E / bib / Посмотрите Theorom 3.7 на странице 10. Спасибо за ответ :) - person AyBayBay; 23.12.2016
comment
@AyBayBay FindAllNearest находит для каждой точки ее ближайшего соседа. Вам нужен простой FindNearest, который имеет время работы O (c ^ 12 log n), а c является для вас постоянным (не говоря уже о том, что c ^ 12, вероятно, является значительным завышением на практике). - person David Eisenstat; 23.12.2016
comment
так что выполнение запроса найти все ближайшие для точки p в радиусе R является сложностью logN? Это замечательно! - person AyBayBay; 23.12.2016
comment
Мне только что пришла в голову моя метрика deltaE (с использованием алгоритма CIE94). Не удовлетворяет свойству симметрии метрики расстояния: en.wikipedia.org/wiki/Metric_ ( математика) Будет ли тогда проблемой использовать deltaE в качестве метрики расстояния для моего дерева покрытия? Я где-то читал, что все метрики расстояния должны удовлетворять неравенству треугольника, которое будет использоваться в структурах метрического дерева. - person AyBayBay; 27.12.2016
comment
@AyBayBay Да, это проблема. - person David Eisenstat; 27.12.2016
comment
Таким образом, для использования метрики расстояния в покрывающем дереве (или в любых структурах дерева показателей) метрика расстояния должна удовлетворять всем трем свойствам: [1. d (x, y) = 0 тогда и только тогда, когда x = y 2. d (x, y) = d (y, x) симметрия 3. Неравенство треугольника] ... Правильно ли я понимаю? Если это так, я нашел новую метрику DeltaE, которая использует евклидово расстояние в цветовом пространстве LAB. Если я использую эту метрику DeltaE, то, вероятно, я мог бы просто использовать более простое KD-дерево, верно? Еще раз спасибо за помощь :) - person AyBayBay; 27.12.2016
comment
@AyBayBay Да, это. - person David Eisenstat; 27.12.2016
comment
Почему метрика расстояния не может быть квазиметрикой? В реальной жизни мне кажется, что симметрии труднее удовлетворить (подумайте о картах / навигации и маршрутах). - person AyBayBay; 27.12.2016
comment
неважно, если симметрия не работает, фундаментальное сравнение просто не удастся - person AyBayBay; 27.12.2016