JPEG: квантование, зигзаг и кодирование коэффициентов

Если отличаешь коды коэффициентов от восстановленных значений и можешь разобрать RUN,SIZE,EOB и ZRL, переходи к «Теперь сам».

Как думаешь, почему в фотографии вдруг появились длинные нули

RLE хорошо сжимает серии одинаковых значений, но в сырой фотографии соседние пикселы редко равны побитно. После ДКП многие веса небольшие. Если коэффициент 1,4 разделить на шаг 8 и округлить, получится 0. Несколько таких результатов подряд превращаются в серию нулей, которой раньше в пиксельном массиве не было.

Нули возникают из выбранной точности. Зигзаг только меняет порядок, а Хаффман только кодирует символы. Приписывать каждому шагу свойство «сжимает с потерями» неправильно: источник утраты находится в конкретных необратимых операциях.

На что это похоже

Передавая измерения линейкой с крупными делениями, ты сообщаешь номер ближайшего деления. Получатель умножает его на шаг шкалы. Он знает, куда попало измерение, но не знает точное исходное положение между делениями.

Можно использовать разные шкалы для разных величин. В JPEG таблица задаёт шаг для каждого положения коэффициента. Более грубые шаги для части AC позволяют экономить биты ценой деталей. Но последствия зависят от изображения: на текстовых контурах грубая сетка может стать заметнее, чем на плавном фоне.

Механизм: код и восстановленный коэффициент

Для коэффициента F и шага Q>0 вычисляют K=round(F/Q). В этой главе учебные расчёты округляют точную половину от нуля; не переносим без проверки договорённость Python round, которая выбирает чётное. Восстановленный коэффициент F̂=K·Q. При таком ближайшем округлении |F−F̂|≤Q/2; граница относится к одному коэффициенту до обратного преобразования.

Для целых F,Q можно избежать float: возьми знак F и умножь его на (2·|F|+Q)//(2Q). При F=10,Q=4 получаем код 3 и восстановление 12. При F=−14,Q=8 код −2 и восстановление −16. Нельзя называть потерей разность между F и K: эти величины имеют разные масштабы.

После квантования 64 числа обходят зигзагом по диагоналям индексов: (0,0),(0,1),(1,0),(2,0),(1,1),(0,2),…. Так низкие суммы индексов обычно оказываются раньше высоких. Обход не сортирует по фактической величине: крупный высокочастотный коэффициент останется на своём месте, чтобы декодер смог восстановить матрицу.

Правило

Квантование выбирает точность; зигзаг, дифференциальное и энтропийное кодирование передают выбранные целые коэффициенты без дополнительной потери. Декодер обязан получить те же таблицы и правильно прочитать категории, знаки и границы блоков. Высокое значение настройки «качество» само по себе не обещает полного совпадения исходных пикселов.

Базовый последовательный режим использует Хаффмана. Семейство JPEG включает и другие процессы; поэтому слова «любой JPEG всегда использует этот один конвейер» слишком сильны. Здесь разбираем именно блочный последовательный путь, а не все синтаксические режимы T.81 и контейнеры, которые могут хранить его данные.

В последовательном режиме выбранного процесса блок получает все свои коэффициенты в одном скане компоненты. Прогрессивный ДКП-процесс может сначала передать DC и часть диапазона AC, а затем другие частоты или уточняющие разряды коэффициентов. Декодер хранит частично известные коэффициенты и обновляет приближение картинки. Сам порядок проходов не обязан добавлять потери: при одинаковых конечных квантизованных коэффициентах можно получить ту же реконструкцию. Это другой режим JPEG, не вейвлетный конвейер JPEG 2000.

Разбор: квантуем и считаем цену ошибки

def quantize(c, q):
    sign = 1 if c >= 0 else -1
    return sign * ((2 * abs(c) + q) // (2 * q))


def amplitude(value):
    size = abs(value).bit_length()
    bits = value if value >= 0 else value + (1 << size) - 1
    return size, format(bits, f"0{size}b") if size else ""


def ac_symbols(values):
    result, run = [], 0
    for value in values:
        if value == 0:
            run += 1
            continue
        while run >= 16:
            result.append(("ZRL",))
            run -= 16
        size, bits = amplitude(value)
        result.append((run, size, bits))
        run = 0
    if run:
        result.append(("EOB",))
    return result


coeff = [13, -14, 1, 0, -2, 7]
steps = [4, 8, 4, 4, 4, 8]
codes = [quantize(c, q) for c, q in zip(coeff, steps)]
restored = [k * q for k, q in zip(codes, steps)]
print("коды:", codes)
print("восстановлено:", restored)
print("квадратичная ошибка:",
      sum((a - b) ** 2 for a, b in zip(coeff, restored)))
print("разность DC:", 23 - 17, "категория/биты:", amplitude(23 - 17))
print("AC:", ac_symbols([0] * 17 + [-5] + [0] * 45))

коды: [3, -2, 0, 0, -1, 1]
восстановлено: [12, -16, 0, 0, -4, 8]
квадратичная ошибка: 11
разность DC: 6 категория/биты: (3, '110')
AC: [('ZRL',), (1, 3, '010'), ('EOB',)]

Массив шагов применяется поэлементно. Первый коэффициент 13 превращается в код 3 и восстановленное значение 12; его квадрат ошибки равен 1. У −14 восстановление −16 и квадрат 4. Вместе с остальными значениями сумма 11. Это ошибка пространства коэффициентов; связь с пиксельной ошибкой требует той ортонормировки, которую разобрали в прошлом уроке, и учёта дальнейшего округления.

Таблица квантования является частью данных для восстановления, а не тайным знанием декодера. В формате передают используемые таблицы и соответствие компонент. Параметр «качество» интерфейса может выбирать таблицы по правилам конкретной программы, поэтому одинаковые номера настроек разных программ не гарантируют одинаковый результат.

Разбор: DC, серия нулей и знак −5

DC разных блоков одной компоненты часто близки. Вместо очередного DC передают его разность с предыдущим. Для 17 и 23 разность равна 6. Её SIZE, число битов модуля, равно 3; положительная амплитуда записывается как 110. Предыдущее значение обновляется по правилам скана и точек перезапуска.

Для AC символ содержит RUN - число предшествующих нулей - и SIZE ненулевой амплитуды. Отдельно следуют SIZE битов. Для отрицательной амплитуды используют особое правило: при размере s передают value+(2^s−1). Для −5 размер 3, передаётся 2, то есть 010. Размер определяет, как прочитать этот знак.

Специальный символ ZRL означает 16 нулей AC, EOB - нулевой остаток блока. В примере сначала 17 нулей, затем −5 и нулевой хвост: ZRL, затем RUN=1,SIZE=3, амплитуда 010, затем EOB. Сами пары RUN,SIZE кодируются таблицей Хаффмана. В коде bit_length() считает число двоичных разрядов положительного модуля, а 1 << s означает степень 2**s. Запись format(2,"03b") даёт строку 010: двоичное представление с шириной три и ведущими нулями. Программа печатает промежуточные символы, не маркеры и байты настоящего файла. Показать этот этап отдельно полезно: ошибки знака, хвоста и длинной серии можно поймать до работы с упаковкой битов.

Что ломается без этого

За EOB принимают конец изображения и прекращают декодирование после первого блока. Или считают DC отдельно от предыдущего значения другой компоненты, смешивая предикторы. Картинка тогда может читаться синтаксически, но иметь неверную яркость блоков.

При сильном квантовании независимые блоки могут восстановиться с разной средней яркостью: возникают границы квадратов. У резких контуров могут появляться колебания, похожие на ореол. Это последствия грубого представления сигнала, а не обязательно ошибки декодера. Повторное сохранение с новым квантованием способно добавить искажения.

Зачем это в работе

Разбирая, почему фотография потеряла детали, проверь шаги квантования и дискретизацию цветности, а при сломанной распаковке - таблицы, категории и состояние DC. Эти причины требуют разных исправлений. Увеличение точности не починит неверный разбор знака, а правильный энтропийный кодер не вернёт уже удалённые коэффициенты.

Теперь сам

Коэффициент −6 квантуется шагом 4 с половинами от нуля. Найди код, восстановленное значение и квадрат ошибки. Затем назови RUN и SIZE для четырёх нулей перед значением 9.