Преобразование изображений в формат Apple HiRes

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

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

Я не нашел способа распределять ошибку в пределах строки, как это делает Флойд. Поэтому ошибки диффундируют только вниз.

Цвета квантуются блоками по 7 пикселей, соответствующих одному байту в HiRes. Перебираются все значения байта, а также все варианты комбинаций младшего и старшего битов в следующем байте. Предыдущий байт уже известен на момент вычисления, поэтому из него берутся два старших бита. На основе этих данных рассчитываются цвета 9 пикселей с учётом выбранной палитры и правил заливки. Затем вычисляется сумма квадратов расстояний в RGB пространстве между 7 пикселями оригинала и 7 средними пикселями HiRes. Выбирается такое значение байта, для которого это расстояние наименьшее. Два предполагаемых бита следующего байта отбрасываются и после этого не используются.

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

Затем полученная полная строка рендерится согласно правилам HiRes режима.

Далее используется модифицированный алгоритм Флойда-Стайнберга для диффузии ошибки. Для каждого пикселя k созданной строки вычисляется разница между цветом оригинала и квантованным цветом. Эта ошибка распределяется на 3 пикселя k-1, k и k+1 и добавляется к цветам оригинала в следующей строке.

Изображения в заголовке темы созданы написанной мной утилитой на Node.js. Исходный код можно взять на GitHub: snake-scaly/dither-hires