Сжатие неподвижной картинки
Несжатая цветная картинка это сетка отсчётов, и сетка большая. Грегори К. Уоллес, описывая предложение 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 рисует сетку, потому что преобразование не смотрело дальше края своего блока. Вейвлет размазывает ошибку иначе. При малом бюджете бит он всё равно выбрасывает информацию.
Пиковое отношение сигнала к шуму оценивает ошибку отсчётов одним числом. Выбор JPEG в 1987 и 1988 годах делали глазами, а метод от зрителей прятали. Файл может выиграть по числу и всё равно выглядеть фальшиво. Контур в Масштабируемой векторной графике не проходил через блок 8 на 8. Плоские изображения: пиксели, спрайты и векторы разделяют этот список фигур и сетку, которую эти алгоритмы уменьшают.