Преобразование Хаара: среднее, деталь и уровни

Если восстановишь пару по среднему и детали, посчитаешь число коэффициентов и разметишь LL,HL,LH,HH, переходи к «Теперь сам».

Как думаешь, почему уменьшенная картинка недостаточна

Есть соседние отсчёты 10 и 14. Их среднее 12 удобно для уменьшенного изображения. Но по одному числу 12 не понять, было ли слева 10 и справа 14, наоборот, или оба значения равнялись 12. Нужно ещё одно число, описывающее отличие.

Возьмём полуразность −2. Тогда исходные значения равны 12+(−2)=10 и 12−(−2)=14. Теперь описание обратимо. Мы не сэкономили число значений: вместо двух пикселов храним среднее и деталь. Зато в гладких областях детали часто близки к нулю, а средние подходят для следующего уровня анализа.

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

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

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

Механизм: один уровень и рекурсивное повторение

Для каждой пары вычислим a=(x+y)/2, d=(x−y)/2. Первые N/2 позиций заполним средними, следующие N/2 деталями. Обратный шаг: x=a+d, y=a−d. Если строка имеет длину, равную степени двойки, повторим разложение только над её первой половиной, затем четвертью и так далее. Остановимся на одном среднем всего сигнала.

Например, из четырёх отсчётов [10,14,30,34] получаем средние [12,32] и детали [−2,−2]. Средние дают ещё пару: среднее 22, деталь −10. Итог [22,−10,−2,−2]. Первый коэффициент относится ко всей строке, второй различает её половины, два последних уточняют соседние пары.

Наше соглашение использует деление на 2, поэтому это не ортонормировка из урока ДКП. Для пары a²+d²=(x²+y²)/2. Если нужна ортонормированная версия Хаара, делят на √2, а не на 2. Обе версии обратимы, но формулы энергии и таблицы квантования нельзя переносить между ними без пересчёта масштаба.

Правило

Храни и средние, и детали, чтобы сохранить обратимость. На следующем уровне разлагай только низкочастотную часть. Для восстановления отменяй уровни от самого грубого к самому мелкому и используй ту же нормировку. Хаар здесь объясняет идею полос; он не является обязательным преобразованием JPEG 2000 Part 1.

При N отсчётах первый шаг обрабатывает N значений, второй N/2, третий N/4. Сумма меньше 2N, поэтому полный одномерный алгоритм работает за O(N). Полная запись содержит одно среднее и 1+2+4+…+N/2=N−1 деталей: ровно N коэффициентов. Заявить сжатие «вдвое» на одном этом шаге нельзя.

Разбор: полное разложение строки

def split(row):
    low, detail = [], []
    for i in range(0, len(row), 2):
        low.append((row[i] + row[i + 1]) / 2)
        detail.append((row[i] - row[i + 1]) / 2)
    return low + detail


def join(row):
    m, result = len(row) // 2, []
    for i in range(m):
        result += [row[i] + row[m + i], row[i] - row[m + i]]
    return result


def forward(row):
    result = list(row)
    size = len(result)
    while size > 1:
        result[:size] = split(result[:size])
        size //= 2
    return result


def inverse(row):
    result, size = list(row), 2
    while size <= len(result):
        result[:size] = join(result[:size])
        size *= 2
    return result


row = [10, 14, 12, 16, 30, 34, 32, 36]
coeff = forward(row)
print("полное разложение:", coeff)
print("обратно:", inverse(coeff))
coarse = [coeff[0]] + [0] * (len(coeff) - 1)
print("без деталей:", inverse(coarse))
block = [[10, 14, 30, 34], [12, 16, 32, 36],
         [20, 24, 40, 44], [22, 26, 42, 46]]
rows = [split(row) for row in block]
columns = [split(list(col)) for col in zip(*rows)]
print("один двумерный уровень:")
for row in zip(*columns):
    print(list(row))

полное разложение: [23.0, -10.0, -1.0, -1.0, -2.0, -2.0, -2.0, -2.0]
обратно: [10.0, 14.0, 12.0, 16.0, 30.0, 34.0, 32.0, 36.0]
без деталей: [23.0, 23.0, 23.0, 23.0, 23.0, 23.0, 23.0, 23.0]
один двумерный уровень:
[13.0, 33.0, -2.0, -2.0]
[23.0, 43.0, -2.0, -2.0]
[-1.0, -1.0, 0.0, 0.0]
[-1.0, -1.0, 0.0, 0.0]

Первое число 23 - среднее восьми исходных отсчётов. Деталь −10 различает две половины со средними 13 и 33. Две детали −1 уточняют четверти, а четыре детали −2 возвращают соседние пары. Полный обратный ход совпал с входом. Когда все детали заменили нулями, получилась постоянная строка из 23. Это уже намеренная потеря, а не свойство самого преобразования.

Если отбросить лишь самые мелкие детали, останутся парные средние: [12,12,14,14,32,32,34,34]. Так видно, какой масштаб утрачен. Не всякая высокочастотная деталь мала: резкая граница или текстура может создать большой коэффициент, который грубое квантование испортит заметно.

Разбор: четыре области двумерного уровня

Сначала применим парный шаг ко всем строкам, затем ко всем столбцам результата. Верхняя левая четверть содержит средние по обеим координатам, LL. Обозначим первой буквой фильтр по горизонтали, второй по вертикали. Тогда верхняя правая область HL содержит горизонтальные детали и вертикальные средние, нижняя левая LH - наоборот, нижняя правая HH - детали по обеим координатам. Это соглашение об именах; в библиотеках ориентации иногда называют иначе.

Матрица вывода имеет LL [[13,33],[23,43]], HL заполнена −2, LH заполнена −1, HH нулевая. Такое изображение изменяется по каждой координате отдельно, поэтому диагональная разность здесь нулевая. Картинка с чередующейся шахматной структурой дала бы другой набор деталей.

После второго уровня преобразуем только LL. Для изображения 8×8 останется LL 2×2, три области 2×2 от второго уровня и три области 4×4 от первого: 4+3·4+3·16=64 коэффициента. При L уровнях число обрабатываемых пикселов ограничено геометрической суммой N+N/4+…, то есть O(N) для N пикселов. Прогрессивная доставка может сначала передать грубую часть, затем уточнения.

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

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

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

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

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

Теперь сам

Пара [6,14] превращена в среднее и полуразность. Найди оба коэффициента. Восстанови пару, затем замени деталь нулём. Сколько всего коэффициентов будет у полного разложения сигнала из 16 отсчётов?