Именно так, не для чайников, а от чайников. Так как чайник в этом вопросе — я, и я излагаю свои наивные попытки решения этой проблемы.

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

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

Первая задача — составление оптимального ограниченного набора цветов, которые более-менее близки ко всем важным цветам кодируемого изображения. Грубо говоря, есть фотография с 16 миллионами цветов, а нужно выбрать 256, или, скажем, 16 наиболее важных цветов, которых достаточно для наиболее точного приближения к исходному изображению. Это как раз про те самые цветовые кубы и их рекурсивное деление пополам. Также это про построение гистограмм. Могут быть и другие подходы.

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

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

Для радикального ускорения кодирования видео мне нужно решить только частный случай первой задачи и полный случай второй задачи.

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

Однако, в пределах кадра мне нужно вычислять усечённые варианты палитры для каждого макроблока. Например, весь кадр имеет палитру 256 цветов, но в пределах макроблока мне нужно выбрать наиболее важные 8 цветов и кодировать только их.

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

Я полагаю, что ускорить поиск похожих цветов при усечении палитры внутри макроблока можно составлением таблицы 256*256: для каждого цвета можно составить список наиболее похожих на него цветов по убыванию похожести. То есть, в начале такой таблицы для каждого индекса находится такой же индекс, потом индекс самого похожего цвета, потом индекс чуть менее похожего цвета. Пока неясным моментом является алгоритм быстрого пропуска альтернативных цветов в таких таблицах, уже исключённых из числа доступных внутри макроблока.

Что касается быстрого маппинга, у меня тоже есть идея с пробелами. Так как моя палитра используется многократно, а память современных ПК измеряется десятками гигабайт, можно составить лукап-таблицу ужасающего размера 256*256*256=16777216 ячеек. То есть жалкие 16 мегабайт. В каждой ячейке которой будет находиться индекс наиболее похожего цвета. Берём значение RGB, используем его как смещение в таблице, получаем индекс цвета. Максимально быстро, чего не скажешь про подготовку 16-мегабайтной таблички.

Мой частный случай немного упрощает эту задачу. Мне нужна палитра системы VGA, не с 8, а с 6 битами на компоненту RGB. Размер таблички таким образом получается всего 256 килобайт, и такую табличку можно рассчитать довольно быстро. Причём сделать это можно без всяких хитрых формул, прямо тем же самым ExoQuant: взять традиционное изображение палитры со всеми возможными цветами и преобразовать его в индексированный цвет.

Не вполне ясным моментом в этом надёжном плане является дитеринг. Метод с табличкой сам по себе даёт только простое преобразование цвета. Для моих целей не нужен метод с распространением ошибки типа Флойда-Стейнберга, но фильтр Байера или любой другой упорядоченный дитеринг очень пригодился бы.

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