C21 · Храним и сравниваем
Сжатие, ранг и информация
Представление может хранить не каждый пиксель, а коэффициенты. Важно различать число коэффициентов, ошибку и реальное число байтов файла.
Теория
Сначала сохраним каждый пиксель: RLE и PNG
Сжатие без потерь меняет запись чисел, но позволяет восстановить их точно. Длинную полосу одинаковых значений можно записать парой «значение, сколько раз»: это RLE. Оно хорошо работает на полосах, но может увеличить запись пёстрой картинки. PNG использует другой путь: сначала предсказывает значение по уже известным соседям, затем сжимает последовательность остатков.
Без потерь: другая запись тех же чисел
Сначала возьмём маленькую чёрно-белую картинку: 8 × 4 пикселя. В каждом пикселе один байт яркости: 0 — чёрный, 255 — белый. Без потерь означает: после распаковки все эти числа должны совпасть, а не просто выглядеть похоже.
RLE: сколько раз подряд повторяется значение?
Читаем только первую строку слева направо. Вместо каждого повтора запишем пару «количество, значение». В этом примере оба числа занимают по одному байту. Нажми на пару, чтобы увидеть её участок.
8 байт → 4 байта пар → те же 8 байт. Здесь RLE помогает. На чередующихся значениях он, наоборот, увеличит запись.
PNG: предсказать соседа, сохранить разницу
PNG не кодирует изображение этим RLE. Сначала он обратимо преобразует байты строк, затем сжимает их DEFLATE. В нашей 8-битной картинке байт и пиксель совпадают; в RGB такая же операция выполняется отдельно над байтами каналов.
Нажми на картинку или используй стрелки. Рамка — выбранный байт; пунктир — используемые соседи.
Sub берёт исходный байт слева. У левого края вместо отсутствующего соседа берём 0.
48 − 48 = 0
Сохраняем остаток по модулю 256: 0
(0 + 48) mod 256 = 48
Другой предсказатель меняет запись, но не распакованные пиксели.
Предсказание само не сжимает: 32 байта превратились в 36 с четырьмя метками фильтра. Выигрыш появляется на следующем шаге, если в этой записи стало больше повторяющихся последовательностей. Маленькая разница −8 хранится байтом 248: при распаковке сложение по модулю 256 вернёт исходное значение.
DEFLATE: повторяем последовательность, а не только один цвет
Читаем 36 байт по порядку. LZ77 оставляет одиночный байт или команду «вернись на d байт и скопируй n байт». Хаффман записывает эти команды битами. Выбери команду: ниже показаны именно её биты в потоке нашего PNG.
В строках выше подчёркнуты записываемые байты. Пунктир сверху отмечает уже записанные байты, откуда начинается копирование. Если длина больше расстояния, скопированные байты тут же становятся источником следующего повтора.
Первый байт 1 — это тип фильтра Sub. Он записан буквально.
00110001Биты показаны в порядке передачи. Здесь таблица Хаффмана фиксированная, а не подобранная под частоты. Реальный PNG-кодировщик может выбирать другие фильтры для разных строк и динамические таблицы.
Из чего складывается настоящий размер файла?
- Сигнатура
- 8 B
- IHDR
- 25 B
- IDAT
- 45 B
- IEND
- 12 B
- Весь PNG
- 90 B
IDAT: 12 байт обрамления + 6 байт zlib + 27 байт DEFLATE. У маленькой картинки заголовки занимают больше самих пикселей. Это измеренный размер полного файла, а не оценка по числу ненулевых значений.
JPEG: что можно отбросить и где возникает ошибка
Для фотографии часто допускают небольшую ошибку ради меньшего файла. JPEG разделяет яркостный и цветовые компоненты, обрабатывает небольшие блоки и записывает их как сумму простых узоров. Главная потеря в базовом процессе — округление коэффициентов после деления на шаг. Последующее кодирование коэффициентов само по себе не добавляет эту ошибку.
JPEG: какие изменения можно оставить незаметными?
Дальше — обычный путь JPEG на основе DCT, со сжатием с потерями. В отличие от PNG здесь восстановленные числа могут отличаться. Не весь JPEG обязан быть с потерями: стандарт содержит и другие режимы; ниже мы разбираем распространённый вариант для фотографий.
- RGB → Y′CbCrОтделяем яркостную составляющую от двух цветоразностных. Преобразование ещё не означает сжатие.RGB 210, 90, 50Y′ 121.3Cb 87.8Cr 191.3
- Цвет можно хранить режеПри 4:2:0 на участок 2 × 2 приходится 4 отсчёта Y′, но по одному Cb и Cr. Это отдельная потеря цветовых деталей. При 4:4:4 этот шаг пропускается.Y′Y′Y′Y′CbCr
- Каждый канал → блоки 8 × 8 → DCTИз значений вычитаем 128. Затем 64 значения блока превращаются в 64 коэффициента пространственных узоров. Без округления обратное DCT восстанавливает блок: само преобразование не выбрасывает информацию.
- Квантование: здесь появляется ошибкаКоэффициент делим на выбранный шаг Q и округляем. При восстановлении умножаем на Q. Например: 23 / 10 → 2 → 20. Разницу 3 уже не вернуть. Для разных частот используют разные шаги.23÷ 102× 1020
- Зигзаг → серии нулей → битыКоэффициенты читают от низких частот к высоким. DC кодируют разностью с предыдущим блоком; AC — длинами серий нулей и значениями. Хаффман упаковывает символы без новых потерь. Сам по себе порядок «зигзаг» тоже ничего не теряет.
- Обратный путь → восстановление → ошибкаРаспаковать биты, вернуть коэффициенты, выполнить обратное DCT, восстановить цвет. Сравнивать нужно и детали изображения, и разность с оригиналом. Число сохранённых коэффициентов — не размер JPEG-файла.
В следующем примере разберём один блок: какой узор задаёт коэффициент, что делает округление и как это меняет восстановленные пиксели.
Косинусные плитки складываются в блок
DCT-II раскладывает блок 8×8 по вещественным косинусным базисам. Левый верхний коэффициент DC хранит среднее с выбранной нормировкой; движение вправо и вниз добавляет более частые изменения. Нулевые коэффициенты не вносят вклад в обратную сборку.
Каждая плитка имеет светлые и тёмные части относительно нуля: это знаки слагаемых, а не готовая фотография. Коэффициент умножает всю плитку. Нулевой коэффициент ничего не добавляет, отрицательный меняет знаки её вкладов. Все 64 вклада вместе точно собирают исходный блок.
Один рисунок и его вклад
Меняй горизонтальную и вертикальную частоты. Слева форма рисунка, справа — тот же рисунок, умноженный на свой коэффициент исходного блока. Обе шкалы фиксированы: слабый коэффициент делает правую плитку бледнее. Частоты 0 и 0 дают постоянный рисунок.
Точные значения — в разборе точки
Синий − · белый 0 · красный +; шкала -0.25…0.25
Точные значения — в разборе точки
Синий − · белый 0 · красный +; шкала -0.25…0.25
Разобрать выбранную точку
Что показывает график
Частота выбирает форму, коэффициент — сколько её прибавить или вычесть. Даже маленький коэффициент относится ко всему блоку, а не к одному пикселю.
Параметры и подробности
Это один из 64 рисунков блока. Частоты задают форму, коэффициент — знак и силу вклада. Обе плитки показаны на одной фиксированной шкале −0.25…0.25; более сильный вклад насыщает экранный цвет, но точные значения не обрезаются. Отрицательный вклад означает вычитание, а не отрицательную яркость готовой фотографии.
Выбери точку на изображении. Стрелки перемещают её; Home и End — к краям строки. Просмотр не изменяет вычисление.
Для изменения примера нужен JavaScript и Canvas. Рассчитанные изображения доступны выше.
Какие слагаемые можно отбросить
Теперь складываем несколько плиток. Сторона квадрата 1 оставляет только постоянный DC; сторона 2 — четыре позиции, сторона 4 — шестнадцать. Сравни результат при неизменном исходном блоке: чем больше быстрых изменений сохранено, тем лучше передаются мелкие детали.
Отбрасывание высоких частот и округление коэффициентов — разные потери. Первое убирает выбранные рисунки целиком, второе меняет силу оставшихся. У резкого края могут появиться колебания. Удаление коэффициентов ещё не означает получение JPEG: подсчёт байтов требует настоящего кодирования.
Сколько частот оставить
Начни с одного коэффициента, расширяй квадрат частот. В стадиях выбери коэффициенты и нажми на одну ячейку; стадии «Базис» и «Его вклад» показывают, какую косинусную плитку она добавляет. Затем включи квантование.
Точные значения — в разборе точки
Серая шкала 0…1: от чёрного к белому.
Точные значения — в разборе точки
Серая шкала 0…1: от чёрного к белому.
Разобрать выбранную точку
Что показывает график
Один DC-коэффициент даёт среднее блока. Полные 8×8 без квантования возвращают исходное; грубые коэффициенты дают потерю деталей и звон.
- MSE
- 0.0025
- RMSE
- 0.05
- PSNR (диапазон 0–1)
- 26.019 dB
- Сохранённые позиции
- 16
Параметры и подробности
Ортонормированная DCT-II: квадрат низких частот k×k, затем равномерное квантование. Это не JPEG-файл: нет цветового преобразования, JPEG-таблиц, zigzag или энтропийного кодирования.
Выбери точку на изображении. Стрелки перемещают её; Home и End — к краям строки. Просмотр не изменяет вычисление.
Для изменения примера нужен JavaScript и Canvas. Рассчитанные изображения доступны выше.
SVD учится базису именно этой матрицы
SVD представляет A как сумму . Каждый внешний продукт — слой ранга один; первые r дают лучшее приближение ранга не выше r по сумме квадратов ошибки. Здесь направления вычисляются по Jacobi-вращениями, что достаточно для маленькой учебной сцены, но чувствительно к обусловленности.
Для хранения r слоёв нужны два вектора на слой и значения σ; при большом r это может быть дороже исходного массива. PCA набора изображений работает с другой организацией матрицы и обычно центрирует данные. Она не тождественна SVD одной фотографии, хотя связана с ней математически.
Складываем слои ранга один
Выбери вертикальный вектор, горизонтальный и их слой. Каждая клетка слоя — произведение двух выбранных чисел. Нажми на слой, чтобы проверить это умножение; затем добавляй слои по убыванию сингулярных значений.
Точные значения — в разборе точки
Синий − · белый 0 · красный +; шкала -4…4
- Слой ранга 1
- Предыдущая сумма + новый слой
Точные значения — в разборе точки
Серая шкала 0…1: от чёрного к белому.
Разобрать выбранную точку
Что показывает график
Сингулярные значения определяются исходной матрицей и поэтому не меняются при выборе ранга. Отметка показывает, сколько первых слоёв вошло в текущую картинку; оставшийся хвост отброшен.
- σ
- Слои включены до этого номера: 3
Ошибка квадратичного приближения не растёт при добавлении слоёв. Но хранить больше слоёв не обязательно выгодно по числу байтов.
- MSE
- 0.0005
- RMSE
- 0.0218
- PSNR (диапазон 0–1)
- 33.221 dB
- Сохранённая энергия матрицы
- 99.8505 %
Параметры и подробности
Jacobi-диагонализация AᵀA, затем A VᵣVᵣᵀ. Ограниченная учебная матрица 16×16: нормальные уравнения теряют точность на плохо обусловленных данных. Число слоёв не равно размеру файла.
Выбери точку на изображении. Стрелки перемещают её; Home и End — к краям строки. Просмотр не изменяет вычисление.
Для изменения примера нужен JavaScript и Canvas. Рассчитанные изображения доступны выше.
Потеря информации и кодирование — разные шаги
Справка и следующие методы
После квантования значения повторяются чаще. RLE кодирует длины повторов; Huffman и арифметическое кодирование используют вероятности символов. Энтропия характеризует ожидаемую информацию модели, но не является точным размером короткого файла с заголовком. Lossless-кодирование должно восстанавливать исходные символы точно.
PNG, WebP, AVIF и другие форматы имеют разные режимы, совместимость и расходы. Разреженные представления хранят немногие значимые коэффициенты в выбранном словаре. Compressed sensing требует специальных предположений о разреженности и измерениях; это не обещание восстановить любую картинку из любых нескольких пикселей. Оценивать нужно кривую качество—реальные байты для конкретного кодека.
Практика
Проверь идею на другом условии. Следуй задаче над изображениями; разбор точки поможет объяснить результат. Эта практика не оценивается.
Четыре позиции против шестнадцати
Начни с квадрата 2×2 — это четыре коэффициента. Сравни с 4×4, выбери один добавленный коэффициент и посмотри его косинусный вклад. Только после этого включай квантование.
Точные значения — в разборе точки
Серая шкала 0…1: от чёрного к белому.
Точные значения — в разборе точки
Серая шкала 0…1: от чёрного к белому.
Разобрать выбранную точку
Что показывает график
Дополнительная позиция полезна, если её коэффициент несёт деталь. Число сохранённых позиций ещё не сообщает число байтов; нулевые коэффициенты тоже занимают позиции в этой схеме.
- MSE
- 0.007
- RMSE
- 0.0839
- PSNR (диапазон 0–1)
- 21.5258 dB
- Сохранённые позиции
- 4
Параметры и подробности
Ортонормированная DCT-II: квадрат низких частот k×k, затем равномерное квантование. Это не JPEG-файл: нет цветового преобразования, JPEG-таблиц, zigzag или энтропийного кодирования.
Выбери точку на изображении. Стрелки перемещают её; Home и End — к краям строки. Просмотр не изменяет вычисление.
Для изменения примера нужен JavaScript и Canvas. Рассчитанные изображения доступны выше.
Игры
Четыре позиции против шестнадцати
Сколько низких частот оставили в образце? Подбери сторону квадрата коэффициентов; квантование остаётся выключенным.
Точные значения — в разборе точки
Серая шкала 0…1: от чёрного к белому.
Точные значения — в разборе точки
Серая шкала 0…1: от чёрного к белому.
Точные значения — в разборе точки
Серая шкала 0…1: от чёрного к белому.
Сравни результат с образцом.
Разобрать выбранную точку
Что показывает график
Дополнительная позиция полезна, если её коэффициент несёт деталь. Число сохранённых позиций ещё не сообщает число байтов; нулевые коэффициенты тоже занимают позиции в этой схеме.
- MSE
- 0.007
- RMSE
- 0.0839
- PSNR (диапазон 0–1)
- 21.5258 dB
- Сохранённые позиции
- 4
Параметры и подробности
Ортонормированная DCT-II: квадрат низких частот k×k, затем равномерное квантование. Это не JPEG-файл: нет цветового преобразования, JPEG-таблиц, zigzag или энтропийного кодирования.
Выбери точку на изображении. Стрелки перемещают её; Home и End — к краям строки. Просмотр не изменяет вычисление.
Для изменения примера нужен JavaScript и Canvas. Рассчитанные изображения доступны выше.
Проверь объяснение
Вопрос 1 из 5
Оставили только DC DCT. Что получится?
Точные значения — в разборе точки
Серая шкала 0…1: от чёрного к белому.
Точные значения — в разборе точки
Серая шкала 0…1: от чёрного к белому.
Точные значения — в разборе точки
Серая шкала 0…1: от чёрного к белому.
Точные значения — в разборе точки
Серая шкала 0…1: от чёрного к белому.
Точные значения — в разборе точки
Синий − · белый 0 · красный +; шкала -4…4
Точные значения — в разборе точки
Синий − · белый 0 · красный +; шкала -1…1
Выбери один ответ. Он проверится сразу.
Ограничения и материалы
Границы этого примера
Выполняются DCT 8×8, прямое квантование и низкоранговое приближение 16×16. Число позиций не выдаётся за размер JPEG; полноценный кодек и compressed sensing не реализованы.