Какова будет сложность этого алгоритма цветового квантования?

Question

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

В основном настройка проста - у вас есть набор точек в кубе RGB (от 0 до 255 целочисленных значений на каждой оси). Вы должны заменить каждую из этих точек другой точкой таким образом, чтобы:

• Общее количество баллов после операции должно быть как можно меньше;
• Расстояние от исходной точки до заменяемой точки не превышает некоторых предварительно определенных констант R, G и B на каждой из красной, зеленой и синей осей (они взяты из чувствительности человеческого глаза и в целом настраивается пользователем).

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

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

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

Настройка бонуса: Измените ограничение от констант R, G, B на функцию F (R _{источник} , G _{источник} , B _{источник} , R _target , G _target , B _target ), который возвращает TRUE, если сопоставление будет в порядке, и FALSE, если оно выходит за пределы диапазона.

Answer 1

Учитывая ваши определения, структура изображения (т.е. как организованы пиксели) вообще не имеет значения, единственное, что имеет значение, - это подмножество RGB-триплетов, которые хотя бы один раз появляются на изображении в виде значения пикселей. Пусть это подмножество будет S. Вы хотите найти другое подмножество RGB-триплетов E (кодирование), такое, что для каждого s в S существует аналог e в E, такой что diff (s, e) <= threshold, где threshold это Вы ограничиваете допустимую разницу, а diff (...) уменьшает расстояние триплета до единого числа. Кроме того, вы хотите найти E, который имеет минимальный размер, то есть для любого E 's.t. | E '| <| E |, хотя бы одна пара (s, e) нарушает разностное ограничение. </p>

Эту конкретную проблему нельзя дать асимптотическую оценку сложности, поскольку она имеет только конечный набор экземпляров. Она может быть решена в постоянное время (теоретически) путем предварительного вычисления минимального набора E для каждого подмножества S. Существует огромное количество подмножеств S, но все же только конечное число, поэтому проблема не может быть, например, классифицируется как NP-полная проблема оптимизации или что-нибудь. Фактическое время выполнения вашего алгоритма для этой конкретной проблемы, следовательно, полностью зависит от объема предварительной обработки, которую вы готовы терпеть. Чтобы получить асимптотическую оценку сложности, вам нужно сначала обобщить проблему, чтобы множество проблемных экземпляров строго бесконечно .

Answer 2

Оптимальное квантование - трудная задача NP (Сон Х. Нгуен, Анджей Сковрон - Квантование атрибутов реальной стоимости, 1995).

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

Вы можете модифицировать многие алгоритмы квантования для выбора количества кластеров, пока не будет достигнуто определенное качество, например, в Median Cut и Linde – Buzo – Grey вы можете просто прекратить разделять пространство, когда достигнете предела качества. Это не будет гарантией того, что это глобальный минимум (то есть NP-жесткий), но в LBG вы, по крайней мере, будете знать, что вы находитесь на локальном минимуме.

Answer 3

Вот идея, как мне поступить - к сожалению, это, вероятно, потребует много памяти и будет очень медленным:

Вы создаете структуру данных размером 256x256x256, которая содержит счетчик и список цветов "соседей". Для каждого уникального цвета, который вы найдете на своем изображении, вы увеличиваете счетчик каждой ячейки, которая находится в радиусе сферы вокруг этого цвета. Радиус сферы - это максимально допустимое расстояние, которое вы определили изначально. Вы также добавляете цвет в список соседей каждой ячейки.

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

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