Технология JPEG: анализ пространства решений
Изображения в формате JPEG, помимо собственно файлов с расширением .jpg, можно встретить внутри PDF-файлов и TIFF-файлов.
Стейкхолдеров технологии JPEG можно, наверное, разделить на следующие группы:
- разработчики фотоаппаратов и сканеров;
- фотографы (большие фотографии в хорошем разрешении с высокими требованиями к качеству);
- соцсети и CDN’ы типа imgix, которые раздают залитые фоточки неконтролируемого UGC-происхождения, количества и размера в пережатом виде;
- вебмастеры, которые управляют умеренным количеством не-UGC картинок с контролируемым качеством;
- любители отсканированных бумажных книг и прочих исторических источников;
Автор этой статьи принадлежит в основном к последней группе, и точно не принадлежит к числу художественных фотографов. Это должно вносить в повествование определенный перекос, который, тем не менее, полезен как раз для иллюстрации возможных траекторий в пространстве решений.
Кратко о процессе превращения исходного изображения в JPEG:
- color space transformation и downsampling;
- картинка разбивается на блоки 8×8 пикселей (MCU). Если размер картинки не делится нацело на 8, то остальная часть квадратика заполняется какими-нибудь пикселями, а при декодировании просто обрезается;
- DCT (дискретное косинус-преобразование) матрицы из 8×8 пикселей, в результате которого «более важные» с т. з. качества картинки коэффициенты, находятся ближе к верхнему левому углу результирующей матрицы 8×8, а «менее важные» — ближе к правому нижнему углу; всего у нас 8×8=64 коэффициента;
- квантизация: матрица из предыдущего пункта поэлементно делится на матрицу квантизации (которую можно относительно свободно выбирать для каждой конкретной картинки; в результате квантизации получается матрица, в которой элементы из правого нижнего угла обычно равны нулю;
- сжатие коэффициентов (энтропийное кодирование, RLE-кодирование и Huffman-кодирование);
Единственной операцией, при которой происходит потеря информации, является квантизация. Все остальные операции происходят без потерь.
У разных стейкхолдеров разные производственные циклы, в которых варьируются следующие фазы:
- сколько вычислительной мощности и времени доступно в момент генерации JPEG-файла? например, фотоаппарат vs полноценные компьютеры;
- будет ли сгенерированный JPEG-файл конечным результатом? например, это так для стоковой картинки на сайте или для сгенерированной превьюшки;
- будет ли сгенерированный JPEG-файл де-факто исходным изображением? например, это так для отсканированных книжных страниц;
- сколько места в хранилище файлов? места всегда не хватает, но иногда его совсем мало;
- какова финальная технология? JPEG-файл для браузера? PDF-файл? специализированный софт, находящийся под полным контролем, например e-reader?
- можем ли мы определить, чем является изображение? полноцветная фотография или отсканированная черно-белая страница с сепией?
- сколько усилий мы можем потратить на проверку качества результата? фотограф может сидеть в фотошопе часами, CDN’ы могут обеспечить только «приемлемое» качество;
Оставаясь в пределах стандартного JPEG-формата, мы можем варьировать следующее:
- исходные пиксели в рамках модели человеческого восприятия;
- матрицу квантизации (причем мы можем раздельно выбирать подходящую матрицу, а также масштабировать ее в соответствии с требуемым JPEG quality);
- матрицу-результат квантизации, что позволяет до некоторой степени варьировать пиксели результирующего изображения в рамках модели человеческого восприятия;
- схему сжатия коэффициентов;
Выходя за пределы стандартного формата файлов, но сохраняя базовую модель JPEG-кодирования мы можем использовать нестандартную схему сжатия коэффициентов, экономя место для хранения (а также для отображения, если мы контролируем конечное устройство).
Если финальным форматом является стандартный PDF, и нашим исходником являются отсканированные книжные страницы, то мы можем использовать технологию разделения изображений в черно-белую и цветную части. Если мы контролируем конечное устройство, то мы можем использовать другой нестандартный «формат».
Ключевой момент: многие технологии, здесь описанные, помогают уменьшать размер файла. Важно понимать, что на самом деле это обеспечивает возможность улучшать качество картинки, оставаясь в пределах приблизительной цели по размеру файла.
Рассмотрим каждую размерность пространства возможных решений по отдельности.
Исходные пиксели
Технология JPEG-сжатия основана на психовизуальной модели зрения: человеческий глаз терпит потерю высокочастотных деталей изображения; человек лучше воспринимает различия в яркости, чем различия в цвете. Существуют стандартизованные метрики корректности воспроизведения исходной картинки, основанные на формуле SSIM (Structural Similarity), которые можно вычислять автоматически и ставить целевые значения.
Если мы можем варьировать исходные пиксели, оставаясь в рамках целевых значений корректности воспроизведения, то мы, в принципе, можем подбирать такие значения пикселей, которые после квантизации сжимаются лучше, чем без такого подбора. Мы не знаем, использует ли какой-нибудь софт такую технологию.
Матрицы квантизации
Матрицы квантизации являются основным механизмом, обеспечивающим качество воспроизведения при приемлемом коэффициенте сжатия. Есть несколько стандартных дефолтных матриц, включая ту, которая была создана больше 25 лет назад на основе анализа корпуса тестовых изображений, созданных тогда же; если использовать стандартные матрицы, то все будет более-менее в порядке, если не нужно заморачиваться.
Вообще говоря, оптимально было бы генерировать отдельную матрицу квантизации для каждого изображения, анализируя его содержимое. Производители фотоаппаратов используют свои запатентованные методы генерации. Adobe Photoshop, говорят, умеет анализировать изображение и подбирать подходящую матрицу.
Качество сжатия JPEG — это просто вещественный коэффициент, который применяется к элементам стандартных матриц квантизации, заставляя ее отбрасывать все больше и больше информации.
Интересный факт: матрицы квантизации можно использовать в компьютерной криминалистике для идентификации устройства, которым была сделана фотография.
Квантизованные DCT-коэффициенты
Зачастую файлы в формате JPEG являются де-факто исходными материалами, потому что хранить изображения в некомпрессированных форматах нецелесообразно. Также иногда у нас просто нет доступа к исходному материалу на бумаге, а есть, например, только PDF-файл неизвестного происхождения и сомнительного качества. Поэтому для многих приложений имеет смысл аккуратно работать с DCT-коэффициентами как объектами первого класса, по возможности применяя к ним преобразования без потерь.
Работа на уровне матриц DCT-коэффициентов позволяет делать несколько преобразований с минимальными потерями (или вообще без потери). Операции, которые требуют полного перекодирования пикселей, здесь не рассматриваются.
Преобразования с минимальными потерями:
- поворот на 90 и 180 градусов, если размер картинки делится нацело на 8;
- обрезание картинки, особенно если координаты линий отреза делятся нацело на 8;
- масштабирование картинок с коэффициентом сжатия 8/N, где N=9…16; в частности, это означает что можно сжимать картинки с коэффициентом ½ и 2/3.
- перевод картинки из цветного в серое представление (выбрасывается цветовая составляющая);
Так как мы знаем, что следующей операцией после квантизации будет сжатие, то в принципе теоретически мы можем слегка варьировать коэффициенты так, чтобы они лучше сжимались, но при этом декодировались примерно в те же пиксели, что и исходное изображение. Неизвестно, есть ли реализации, использующие этот подход.
Схема сжатия коэффициентов
Стандартный JPEG поддерживает Huffman-сжатие коэффициентов, а также арифметическое кодирование.
Реализация Huffman-сжатия очень часто самая простая и наивная; в частности, компрессор сжимает коэффициенты, рассматривая их как случайные данные. Если мы учтем тот факт, что это коэффициенты двумерной матрицы, которая кодирует изображение, то мы можем получить существенно лучшие результаты. Пережатие коэффициентов на этом уровне происходит без потерь.
Еще один способ улучшить сжатие — перекодировать файл в progressive JPEG. При этом коэффициенты одного порядка группируются вместе, что обычно приводит к уменьшению размера файла. Это тоже операция сжатия без потерь. Кроме того, progressive JPEG быстрее начинает рендериться при загрузке файла, что может быть отдельным дополнительным плюсом на вебе.
Второй стандартный способ сжатия — арифметическое кодирование. К сожалению, этот способ поддерживается только специализированными инструментами, в частности, большинство распространенных браузеров его не поддерживают. Это связано с сомнительным (в прошлом) патентным статусом арифметического кодирования. Простое пережатие картинок с арифметическим кодированием дает существенную экономию размера при отсутствии потерь. Этот способ, конечно, можно использовать, если мы контролируем реализацию клиентского устройства, или же если картинки используются только для хранения.
Если мы полностью контролируем клиентское устройство или если мы хотим только хранить картинки, то мы можем использовать нестандартные схемы сжатия, которые лучше используют тот факт, что объектом сжатия являются картинки. Например, интересная программа PackJPG умеет сжимать JPEG без потерь примерно на 20%, но результат сохраняется в нестандартном формате.
Разделение слоев изображения
Для некоторых картинок, в особенности для сканированных печатных страниц, можно разделить изображение на черный-белый (или другой палитровый) слой и «уточняющую» подложку в полноцветном формате. Оба этих слоя можно сжать раздельно в оптимальном для этого формате. Например, для PDF черно-белый слой можно сжать с помощью JBIG2, а цветной — в JPEG2000, JPEG или PNG.
Аналогичная технология используется в формате DJVU.
Если мы контролируем клиентское устройство, то мы можем делать аналогичные преобразования, например накладывая в HTML картинки друг на друга.
Ссылки на документы и программы
https://en.wikipedia.org/wiki/JPEG очень хорошее обзорное описание. Некоторые параграфы становятся ясны только после изучения других ссылок.
http://www.ijg.org/ референсная реализация формата. Написана на суперпортабельном C, поэтому крайне не оптимизирована.
http://www.libjpeg-turbo.org/ оптимизированная реализация JPEG
http://www.libjpeg-turbo.org/About/Jpeg-9 Критика IJG + http://www.libjpeg-turbo.org/About/SmartScale критика неоднозначной новинки SmartScale
http://www.libjpeg-turbo.org/About/Mozjpeg очень хороший технический анализ Mozjpeg
https://github.com/mozilla/mozjpeg реализация JPEG, оптимизированная под специфические распространенные use-cases
http://jpegclub.org/jpegtran/ утилита для преобразования JPEG-файлов с минимальными потерями
https://linux.die.net/man/1/exiftran утилита для работы с JPEG-файлами, повернутыми с помощью EXIF.
https://github.com/ifad/pdfbeads скрипт для генерации PDF-файлов с помощью разделения слоев
https://en.wikipedia.org/wiki/DjVu#Compression описание разделения слоев в DjVu
https://github.com/packjpg набор библиотек и утилит для низкоуровневой манипуляции JPEG-файлами
http://code.flickr.net/2017/01/05/a-year-without-a-byte/ рассказ о том, как в Flickr оптимизировали хранение и раздачу картинок
Комментарии (7)
dom1n1k
25 февраля 2017 в 14:54
+4↑
↓
Всё это интересно, конечно, но в чем месседж? Статья выглядит вырванной откуда-то — ни постановки проблемы, ни выводов. Анализа тоже не увидел, есть обзор.25 февраля 2017 в 22:07
0↑
↓
Похоже на курсовую — по языку и формату
25 февраля 2017 в 15:42
+1↑
↓
> Единственной операцией, при которой происходит потеря информации, является квантизация.
С чего бы это?!
А downsampling?!
И если вы не очень понимаете процесс, то «color space» — это все цвета, которые в этом пространстве присутствуют; если меняется пространство, то и меняется и состав хранимых цветов. Если наглядно, то для RGB цвета находятся внутри треугольника, а для YCbCr внутри полуэлипса — без потерь не получится одну фигуру вписать в другую.То, что у вас написано в «Разделение слоёв» в самом JPEG уже реализовано: яркостная компонента (ч/б изображение) хранится в высоком разрешении, а уточняющая цветовая компонента (как правило) в более низком.
-
dom1n1k
25 февраля 2017 в 15:58
0↑
↓
Сам по себе переход между RGB и YCrCb взаимно-однозначен и обратим. Потери там только вычислительные, особенно если нужно работать с целыми числами.
Что за полуэллипс — не очень понятно.25 февраля 2017 в 16:30
+1↑
↓
в теории, при бесконечной точности и отрицательных значениях — да, взаимно-однозначен и обратим
на практике — нет :-)Если вы видели визуализацию всяких цветовых пространств sRGB, Adobe RGB и т.п., то там рисуют некоторый сложный цветовой градиент, а на нём треугольники этих цветовых пространств — потому что координат три, а это «срез» по одинаковой яркости. В YCrCb, первая — яркость, а все допустимые цвета на этой плоскости заданы расстоянием до двух «полюсов» — т.е. всё что лежит внутри пересечения двух окружностей. Да, полуэлипс тут не при чём. Но суть не меняется — это довольно разные по своей форме пространства и без существенных потерь данных/точности преобразования между ними невозможны.
-
dom1n1k
25 февраля 2017 в 16:39
0↑
↓
Если имеется в виду хроматическая диаграмма, то охват связанных друг с другом RGB/YCrCb пространств будет совпадать (с точностью до вычислительных погрешностей). YCrCb это представление тех же самых цветов в других координатах. На диаграмме абсолютных цветов будет та же самая фигура.25 февраля 2017 в 16:46
0↑
↓
«вычислительная погрешность» в данном случае довольно велика
