ДКП: смена координат перед сжатием

Если объясняешь роль DC и AC, читаешь формулу преобразования и отличаешь её от квантования, переходи к «Теперь сам».

Как думаешь, один цвет требует 64 разных чисел

В блоке 8×8 все отсчёты после подготовки яркости равны 3. Можно хранить число 3 шестьдесят четыре раза. А можно сказать: «весь блок постоянный» и записать только величину постоянной составляющей. Для произвольного блока нужны ещё поправки, которые описывают полосы, края и мелкие изменения.

Преобразование не знает заранее, какие поправки понадобятся. Оно вычисляет весь набор из 64 коэффициентов. Если картинка гладкая, многие окажутся малыми; если в каждом соседнем пикселе резкое изменение, значимыми могут быть и высокие частоты. Название преобразования не гарантирует сжатия каждого входа.

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

Цвет краски можно описать количеством красного, зелёного и синего. Та же точка в пространстве описывается через другую тройку согласованных координат. ДКП делает похожую замену: вместо значения в каждой позиции сообщает, сколько каждого заранее известного узора надо сложить.

Чтобы восстановить блок, декодер должен знать те же узоры и нормировку. Если кодировщик умножил один узор на дополнительный коэффициент, а декодер этого не учёл, получит другой блок. Поэтому формулу нельзя сочетать с произвольно выбранным «обратным ДКП» из другого соглашения.

Механизм: веса косинусных узоров

Косинус угла можно представить как горизонтальную координату точки единичной окружности. Значения меняются плавно от 1 к −1 и обратно; выбор разных частот даёт узоры с разным числом смен знака. Для строки длины N зададим C[u,x]=α(u)·cos(π(2x+1)u/(2N)), где α(0)=√(1/N), а при u>0 α(u)=√(2/N). Индексы u и x идут от 0 до N−1.

Коэффициент строки равен F[u]=Σx C[u,x]·p[x]: умножаем отсчёты на веса узора и складываем. Узоры ортонормированы: сумма квадратов весов каждого равна 1, а сумма попарных произведений разных узоров равна 0. Поэтому коэффициенты не смешиваются: обратная формула p[x]=Σu C[u,x]·F[u] возвращает исходные отсчёты.

Для квадратного блока используем те же веса сначала по одной координате, затем по другой: F[u,v]=ΣxΣy C[u,x]·C[v,y]·p[x,y]. Частота u относится к первой координате, v ко второй. Коэффициент F[0,0] сопоставлен постоянному узору, поэтому называется DC; остальные называют AC. При N=8 каждый вес постоянного узора равен 1/√8, значит DC=сумма пикселов/8.

В обычной восьмибитной компоненте перед ДКП вычитают 128 из отсчётов. Это сдвиг диапазона к нулю, а не потеря информации: при восстановлении 128 прибавляют. Постоянный блок яркости 131 после этого имеет значение 3 и DC=24. Без указания сдвига одна цифра DC не определяет среднюю исходную яркость.

Правило

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

Для одного двумерного блока прямое вычисление четырёх вложенных сумм требует O(N⁴) арифметических действий. Два последовательных одномерных преобразования дают O(N³), а быстрые факторизации сокращают работу ещё сильнее. В JPEG размер N фиксирован 8; это сравнение объясняет устройство алгоритма, а не асимптотику по числу блоков картинки. По всей картинке число таких фиксированных блоков пропорционально числу пикселов.

Разбор: четыре коэффициента вместо знакомой ступеньки

В программе блок 4×4 содержит одинаковые строки [10,10,14,14]. Среднее равно 12, поэтому DC=4·12=48. Изменений между строками нет, а вдоль строки есть ступенька; ненулевые AC остаются только в первой строке матрицы коэффициентов. Код использует меньший блок ради читаемости чисел; нормативный базовый JPEG применяет ДКП 8×8.

from math import cos, pi, sqrt


def transform(block, inverse=False):
    n = len(block)
    basis = []
    for u in range(n):
        scale = sqrt(1 / n) if u == 0 else sqrt(2 / n)
        basis.append([scale * cos(pi * (2 * x + 1) * u / (2 * n))
                      for x in range(n)])
    result = [[0.0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            for a in range(n):
                for b in range(n):
                    if inverse:
                        factor = basis[a][i] * basis[b][j]
                    else:
                        factor = basis[i][a] * basis[j][b]
                    result[i][j] += block[a][b] * factor
    return result


def show(row):
    return [0 if abs(x) < 1e-9 else round(x, 6) for x in row]


block = [[10, 10, 14, 14] for _ in range(4)]
coeff = transform(block)
for row in coeff:
    print(show(row))
restored = transform(coeff, inverse=True)
error = max(abs(block[i][j] - restored[i][j])
            for i in range(4) for j in range(4))
energy = sum(x * x for row in block for x in row)
energy_coeff = sum(x * x for row in coeff for x in row)
print("энергия:", energy, round(energy_coeff))
print("ошибка обратного преобразования:", f"{error:.9f}")
constant = transform([[3] * 8 for _ in range(8)])
print("DC постоянного блока 8x8:", round(constant[0][0]))

[48.0, -7.391036, 0, 3.061467]
[0, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]
энергия: 2368 2368
ошибка обратного преобразования: 0.000000000
DC постоянного блока 8x8: 24

Матрица содержит DC 48, горизонтальные коэффициенты около −7,391 и 3,061, остальные нули с учётом точности вывода. Энергия, то есть сумма квадратов, совпала: 2368. Последний ноль в выводе ошибки означает округление показателя до девяти знаков, а не доказательство абсолютно точной арифметики float. Для постоянного блока 8×8 отдельно получен DC=24.

Разбор: зачем сохраняется сумма квадратов

Для двух отсчётов ортонормированная пара имеет вид a=(x+y)/√2, d=(x−y)/√2. Раскрой квадраты: a²+d²=((x+y)²+(x−y)²)/2=x²+y². Перекрёстные слагаемые уничтожились. В ДКП тот же эффект обеспечивается нулевыми попарными произведениями разных узоров и единичной длиной каждого.

Если ошибка двух коэффициентов равна 3 и 4, её сумма квадратов 25. После точного обратного ортонормированного преобразования сумма квадратов ошибок пикселов тоже 25. Но затем пикселы обычно округляют до целых и ограничивают диапазоном 0…255. После этих дополнительных шагов равенство нужно проверять заново; оно относится именно к линейному преобразованию.

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

Говорят, что ДКП «удалило высокие частоты», хотя программа лишь вычислила их веса. Само по себе оно ничего не удаляет. Или отождествляют «низкую частоту» с «малым коэффициентом»: большой край может дать существенную высокочастотную компоненту. Размер коэффициента определяется изображением, номер частоты - выбранным узором.

Ещё одна ошибка - использовать формулу DC=среднее для нашей нормировки 8×8. Здесь DC=8·среднее подготовленного блока. В других реализациях масштаб могут перенести в таблицу квантования, но кодировщик и декодер должны делать это согласованно.

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

Разбирая блочный кодировщик, сначала проверь сдвиг уровня, нормировку и порядок координат. Иначе настройка таблицы квантования будет компенсировать ошибку преобразования, а сравнение искажений окажется бессмысленным. На гладких блоках полезно отдельно проверять постоянную составляющую, на резких границах - ненулевые высокие частоты.

Теперь сам

Все 64 подготовленных отсчёта блока 8×8 равны −2. Каковы DC и остальные коэффициенты? Если сохранить только DC, потеряется ли информация именно на таком блоке?