Сжатие неподвижных изображений
Несжатое цветное изображение это сетка отсчётов, и сетка эта большая. Грегори К. Уоллес, описывая предложение JPEG, оценивал оцифрованный цветной кадр телевизионного разрешения примерно в миллион байт, а кадр с разрешением 35-миллиметровой плёнки примерно в десять раз больше. Получить такой кадр может быть дёшево. Но файл всё равно может оказаться слишком тяжёлым, чтобы его хранить или пересылать. Эти байты и есть пиксели. Путь одного из них от модели до экрана прослеживает заметка От модели к пикселю. Сжатие это следующий шаг, когда те же отсчёты должны занимать меньше места на диске и в канале связи.
Для этого есть два семейства методов. Метод без потерь восстанавливает каждый отсчёт. Метод с потерями этого не делает. Архивы, медицинские снимки, технические чертежи, клипарт и комиксы обычно сжимают без потерь, потому что изменённый отсчёт означает изменённый факт. Фотография может пожертвовать небольшой долей точности и сильно уменьшиться. Если разницу невозможно заметить, такое сжатие называют визуально без потерь. Если же ещё сильнее снизить битрейт, повреждения уже можно показать пальцем: блоки, ореолы вдоль краёв, цвет, потерявший оттенки.
Уоллес в 1991 году оценивал тогдашний уровень техники примерно от одной десятой до одной пятидесятой исходного размера для типичного изображения, причём без изменений, которые заметил бы зритель. Степень сжатия это настройка, а не закон природы. Кодер должен позволять пользователю самому выбирать компромисс.
Без чего глаз обойдётся
Изменение яркости заметнее, чем изменение цвета. Субдискретизация цветности сохраняет сетку яркости, а часть цветовых отсчётов усредняет или просто отбрасывает. Второй способ экономии отбрасывает большинство цветов и оставляет короткий список. GIF и PNG могут хранить в заголовке палитру, часто из 256 цветов. Тогда пиксель хранит номер в этом списке, а не собственные значения красного, зелёного и синего. Дизеринг рассеивает ошибку округления крапинками, чтобы плавный переход не распадался на плоские полосы. Блочные палитры идут ещё дальше и дают участку 4 на 4 всего два или четыре цвета. Так работают BTC, S3TC и родственные им схемы, и поэтому сжатая игровая текстура вблизи может выглядеть постеризованной, а издали вполне прилично.
Восемь на восемь
Грегори К. Уоллес описал победивший метод в статье The JPEG Still Picture Compression Standard в журнале Communications of the ACM за апрель 1991 года. Он был председателем Joint Photographic Experts Group и работал в Digital Equipment Corporation. JPEG был совместной работой ISO и CCITT по сжатию полутоновых неподвижных изображений, как в оттенках серого, так и цветных. В июне 1987 года группа рассмотрела изображения по двенадцати предложениям и отобрала три. В январе 1988 года второй, более строгий просмотр выбрал адаптивное дискретное косинусное преобразование на блоках 8 на 8. С 1988 по 1990 год прорабатывали детали, чтобы файл одного производителя открывался на машине другого. Когда Уоллес опубликовал статью, часть 1 стандарта проходила голосование как проект комитета: ISO/IEC CD 10918-1, голосование по которому началось в феврале 1991 года. Рекомендация T.81, текст той же работы от ITU-T, датирована сентябрём 1992 года.
Само косинусное преобразование старше комитета. Насир Ахмед, Т. Натараджан и К. Р. Рао опубликовали его в 1974 году. На блоке 8 на 8 оно заменяет 64 отсчёта на 64 коэффициента. У гладкого участка почти вся энергия приходится на первые, низкочастотные коэффициенты. Квантование делит каждый коэффициент на шаг из таблицы и округляет результат. Именно при этом округлении и теряется информация. Высокочастотные коэффициенты, отсутствие которых зритель заметит меньше всего, часто округляются до нуля. Оставшиеся считывают зигзагом, который собирает эти нули в один длинный хвост, а код Хаффмана записывает серии. Дэвид А. Хаффман опубликовал этот код в 1952 году в Proceedings of the IRE. Проект JPEG допускал и другой энтропийный кодер, арифметический. Базовый последовательный кодек использует код Хаффмана.
| Шаг | Что происходит |
|---|---|
| Сдвиг | Беззнаковые отсчёты становятся знаковыми, с центром в нуле |
| Прямое ДКП | 64 отсчёта превращаются в 64 косинусных коэффициента |
| Квантование | Каждый коэффициент делят на шаг из таблицы и округляют |
| Зигзаг | Коэффициенты переставляют так, чтобы нули шли подряд |
| Хаффман | Кодируются серии нулей и оставшиеся значения |
В базовом режиме изображение проходят за один раз, слева направо и сверху вниз. Отдельного алгоритма для цвета нет. Каждую цветовую составляющую сжимают как отдельное изображение в оттенках серого. Кодер может закончить одну составляющую и перейти к следующей, а может по очереди брать блоки 8 на 8 из каждой составляющей. Перед преобразованием отсчёты из диапазона от 0 до 2P−1 сдвигают в знаковые значения. P это число бит на отсчёт.
Проект описывал ещё три режима работы. Прогрессивное кодирование держит коэффициенты в буфере и передаёт несколько проходов, сначала грубый, потом всё более чёткие. Именно это нужно на медленной линии: сначала узнаваемая картинка, а остальное, пока вы ждёте. Кодирование без потерь восстанавливает каждый отсчёт, но сжимает слабее. Иерархическое кодирование хранит несколько разрешений, так что маленькое изображение можно получить, не распаковывая большое.
Методы, которые восстанавливают все отсчёты
Кодирование длин серий подсчитывает, сколько раз подряд повторяется значение, и записывает это число рядом с ним. В PCX это основной способ сжатия. BMP, TGA и TIFF тоже могут его использовать. LZW, алгоритм Абрахама Лемпеля, Якоба Зива и Терри Уэлча 1984 года, пополняет словарь уже встречавшихся строк. GIF, появившийся в 1987 году, сжимает данные с помощью такого словаря, и TIFF тоже так умеет. DEFLATE, метод Фила Каца, описанный в RFC 1951 в мае 1996 года, это компрессор внутри PNG, а также внутри MNG и TIFF. PNG сначала предсказывает отсчёт по соседним и сохраняет ошибку предсказания. Затем DEFLATE сжимает эти ошибки, которые меньше и однообразнее, чем сами отсчёты.
Ещё раньше факс доказал, что один общий метод сжатия может сделать устройство массовым. Рекомендация CCITT T.4 1980 года описывает метод факса группы 3. Он сжимает двухуровневые изображения: краска или пустое место. Фотографию он не сжимает. Уоллес сравнивал JPEG именно с этим ограничением: та же надежда на один метод для многих производителей, но теперь для изображения с оттенками серого.
После блоков
JPEG 2000 разрабатывали с 1997 по 2000 год. В нём нет косинусных блоков 8 на 8. Для сжатия с потерями используется вейвлет CDF 9/7 Альбера Коэна, Ингрид Добеши и Жан-Кристофа Фово 1992 года. Для сжатия без потерь используется вейвлет 5/3 Дидье Ле Галля и Али Дж. Табатабаи 1988 года. В 2004 году это семейство, включая Motion JPEG 2000, выбрали для кодирования изображения в цифровом кино. При сильном сжатии в старом JPEG проступает сетка, потому что преобразование никогда не заглядывало за край своего блока. Вейвлет распределяет ошибку иначе. Но при малом бюджете бит он всё равно отбрасывает информацию.
Пиковое отношение сигнала к шуму (PSNR) оценивает ошибку в отсчётах одним числом. А решения по JPEG в 1987 и 1988 годах принимали на глаз, скрывая от зрителей, какой метод перед ними. Файл может выиграть по этому числу и всё равно выглядеть неестественно. Контур в масштабируемой векторной графике никогда не проходил через преобразование 8 на 8. Плоские изображения: пиксели, спрайты и векторы это граница между таким списком фигур и сеткой, которую уменьшают эти алгоритмы.