На сегодняшний день есть достаточно много различных форматов; что-то пришло из 90-х (как gif), что-то появилось позже, как webp. Давайте и мы придумаем какой-нибудь формат, который позволит и данные хранить, и объём сэкономить. Однако, наша оптимизация будет с потерей качества; впрочем, так ли это важно в мире, где мода на ламповую 8-битную графику вновь вернулась?
Изначальное описание формата
В нашем формате ставка будет делаться не столько на хранение данных, сколько на экономию на этом, а это значит, что потеря качества нам обеспечена. Впрочем, потеря качества ведь не всегда означает неприемлемость изображения.
Сам файл будет иметь такую структуру:
- Заголовок файла - 1 байт;
- Размер одной линии изображения - 2 байта (что предполагает, что максимальная ширина изображения чуть более 65,5 тысяч точек - есть повод обдумать оптимизацию);
- Массив изображений, где на 1 точку приходится 1 байт;
Экономно, не так ли?
Что будет в заголовке, побитно:
- 1 бит - признак наличия альфа-канала (если включён, то "нулевой" цвет считается прозрачным);
- 2 бита - масштабирование изображения;
- 4 бита - пока в резерве, но им найдётся место.
Однако, тут сразу появляется что-то вроде проблемы: если мы не знаем, что это за файл, то никаких признаков, как его обрабатывать - и не будет.
Планируется, что будет в байте точки, побитно:
- 1,2 биты - номер гаммы
- 3,4 биты - красный цвет
- 5,6 биты - зелёный цвет
- 7,8 биты - синий цвет
Небольшое пояснение: в настоящий момент довольно широкое распространение получила RGB (red-green-blue) модель, согласно которой, выходной цвет является комбинацией смешения трёх цветов. Я буду ориентироваться на неё же.
Важный момент
Для примера, я выбрал пару файлов изображений, но проблему объясню на примере одного из них. Исходный размер JPEG файла - примерно 350 килобайт, при этом он 1200 на 968 точек. Если перемножить размер и перевести в байты - получится примерно 1,1 Мегабайта. Почти в 5 раз тяжелее с потерей качества. И это без учёта заголовка (что примечательно, но несущественно).
Понимая это, я, всё же, попробую поэкспериментировать с созданием нового формата и поищу способы, как можно ужать данные.
Палитры
Обычно, речь идёт о 4 каналах цвета, каждый из которых занимает 1 байт (для одной точки): это, красный, зелёный, синий и прозрачность. Нетрудно посчитать, что размер в памяти 1 точки будет составлять 4 байта, что составляет примерно 4 294 967 296 различных цветов (на самом деле 16 777 216 + степень прозрачности).
Мы же попробуем тут немного сэкономить, потратив всего 2 бита на каждый цвет и отказавшись от прозрачности. Это получается 6 бит или 64 цвета, что хотя и неплохо, но маловато (4 оттенка красного, 4 зелёного и 4 синего). Но у нас остаётся ещё 2 бита, которые мы посвятим изменению гаммы, что позволит нам использовать 256 цветов. Минус такого подхода заключается в невозможности смешивать цвета из разных гамм.
Я написал небольшой код, который позволил составить возможную палитру, но сперва давайте взглянем на оригинальную палитру.
Местами, возникает ощущение повтора цвета, но это не так.
А теперь давайте применим взглянем на нашу палитру. Напомню, первые два бита у нас отданы на выбор палитры. У нас может быть 4 палитры:
- нулевая - стандартная, есть 4 оттенка для каждого из цветов (0, 33, 66 и 100% от исходной цветовой гаммы);
- первая - приоритет красного, всё то же самое, только для красного цвета смещаются и, при смешении, получаются иные оттенки;
- вторая - приоритет зелёного (аналогично красному);
- третья - приоритет синего (аналогично красному);
Получается такая вот палитра:
Границы палитр видны и можно заметить, что некоторые цвета немного пересекаются, хотя оттенки всё равно везде разные. Таким образом мы получили более 440 независимых цветов. С этим можно работать.
Главное, не забыть, что расширяемая цветовая палитра расширяется "изнутри", то есть если изначально смещения цветов были 0, 33, 66 и 100%, до расширение просто добавляет промежуточные цвета, примерно так: 15, 40, 70 и 90% (но эти значения можно и подрегулировать).
Редактор цвета
Теперь, когда у нас есть опорные цвета, давайте поэкспериментируем со сменой цветов. Для этого я напишу небольшую функцию: она будет загружать изображение, проходить по всем её точкам и менять цвета"округлением цвета" в меньшую сторону (то есть ведя в затемнение).
Для тестов я взял пару фотографий
Я написал небольшой код, который позволит мне разбирать фотографию и менять, при необходимости, цвет в пикселях. Он простой.
С помощью него я смог обнулить последовательно каждый из каналов, а также инвертировать цвета. Получается недурно.
Вторая задача - сложней. Надо не просто заменить цвета, а заменить на те, которые есть в нашей палитре. Это не так тривиально, как хотелось бы и вот почему: каждый цвет состоит из 3 чисел как в исходной, так и в нашей интерпретации, однако как "подтянуть" исходный цвет под нужный? Ведь требуется сохранить как тон цвета, так и его оттенок.
К счастью, у нас есть палитра наших цветов и можно попробовать поискать то значение, которое ближе всего; в конце концов цвета записываются числами, уникальные 352 значения.
Попробуем выбирать то значение, которое ближе к имеемому.
Попробуем ещё одно изображение. Интереса ради, я разместил оригинальное и обновлённое рядом.
Должно быть, где-то ошибка. Хотя и используется 139 цветов на втором изображении, есть ряд моментов, которые вызывают вопросы: например, почему белая машина стала чёрной?!
Причина оказалась тривиальна - слишком буквальный поиск "ближайшего" цвета, по величине. А требовалось искать по минимальному отклонению от всех цветов. Вот этот код подбирает нужный цвет:
Зато и результат получился сильно лучше:
Отчего-то очень сильно напоминает бессовестно ужатый jpeg. Может быть он так и работает, подменяя палитры? Интересно, а как будет выглядеть цветная картинка с разводами?
Можно считать, что такая перекодировка цветов нас устраивает. Можно переходить к следующему этапу.
Оценка результата
Итак, у нас получился весьма рабочий способ перевода цветов, но этот процесс надо бы ускорить. Самый простой путь для кодировки/раскодировки - иметь двойную таблицу: цвет оригинальный - цвет упрощённый и цвет упрощённый - цвет оригинальный. Для этого я немного изменил алгоритм генерации цветов таким образом, чтобы он создал уникальную палитру без повторов (предложенная выше палитра имеет некоторое количество цветовых повторов, что логично).
Цветовая схема претерпела небольшие, но не критичные изменения. Давайте составим теперь таблицы.
Короче говоря, я составил таблицы перекодировки. В принципе, довольно удобно кодировки/декодирования: не нужно постоянно рассчитывать новые значения.
Ожидаемый поворот
Как и ожидалось, размер упакованных данных оказался почти в 5 раз больше оригинала. Но сдаваться пока что рано. Существует, как минимум, ещё два способа побороться за размер - это сокращённое кодирование длинных цепочек однотипных данных и использование сжатия.
В этом нам помогут встроенные в браузеры механизмы компрессии:
GZIP позволил сжать примерно до 580 килобайт, DEFLATE дал примерно такой же результат.
Кодировка последовательностей
В принципе, тут ничего сложного нет: в набор данных добавляется некоторый управляющий символ, данные после которого будут содержать управляющую последовательность. Например, следующие 100 точек - чёрного цвета.
Я провёл небольшое исследование - взял уже известный нам файл с разводами и подсчитал, сколько повторяющихся точек одного цвета встречается в нашем файле (после перекодировки цветов разумеется). Экономия возможна, но по самым оптимистичным прикидкам удастся сэкономить приблизительно 150 килобайт из более чем 1 мегабайта. Это не даст нам нужной экономии, увы.
Заключение
Это был весьма любопытный опыт, который позволил сделать несколько выводов:
- Существующие алгоритмы кодирования изображений - действительно хороши;
- Сокращение цветовой схемы совершенно не гарантирует сокращения размера выходного файла;
- Хранение данных о графическом файле по точкам даёт довольно значительный выходной размер, сильно превышающий существующие, однако, при определённых обстоятельствах, он всё равно может быть полезен (например, когда надо быстро отобразить данные, но распаковывать их не хочется);
- Алгоритмы сжатия (вроде gzip или deflate) позволяют добиться сокращения размер выходного файла, но не могут соперничать с традиционными форматами изображений.
- И самое главное: перекодировка палитр по "ближайшим" цветам должна производиться сразу по всем трём опорным цветам (суммарное минимальное отклонение), т.к. в противном случае получается полная ерунда.
Короче говоря, создавать свой собственный формат хранения изображений, экономя на всём, чем только можно - не самая простая задача.
