Lifting 5/3: целочисленное преобразование без потерь

Если восстановишь чётные и нечётные отсчёты из s,d, включая отрицательные детали на границе, переходи к «Теперь сам».

Как думаешь, любое округление делает алгоритм необратимым

Округлённое среднее пары действительно не определяет пару. Но рассмотрим другую операцию над двумя числами: оставить a неизменным, а b заменить на b−floor(a/2). Чтобы вернуть b, прибавим то же floor(a/2). Мы не пытаемся обратить округление: нам известен его исходный аргумент, потому что a сохранено.

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

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

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

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

Механизм: предсказание и обновление

Разберём строку чётной длины 2m. Нумерация исходных позиций с нуля. Чётные отсчёты назовём e[i]=x[2i], нечётные o[i]=x[2i+1]. Предсказываем нечётный отсчёт средним соседних чётных: d[i]=o[i]−((e[i]+e[i+1])//2). Это деталь, разность между действительным значением и предсказанием.

Затем обновляем чётную часть: s[i]=e[i]+((d[i−1]+d[i]+2)//4). Поправка использует соседние детали и перераспределяет низкочастотную информацию. Деление // округляет вниз, включая отрицательные числители. Например, −1//4=−1; усечение к нулю дало бы 0 и описывало бы другой алгоритм.

Для конечной строки явно зададим зеркальное продолжение на концах: в последнем предсказании e[m]=e[m−1], в первом обновлении d[−1]=d[0]. В файле модели разместим все s, затем все d. Это согласованная схема одного уровня для чётной длины и начала с чётной позиции. Полный стандарт обрабатывает также нечётные размеры и другие положения границ.

Правило

Обратный lifting отменяет обновление: e[i]=s[i]−((d[i−1]+d[i]+2)//4). Затем отменяет предсказание: o[i]=d[i]+((e[i]+e[i+1])//2). Используй те же граничные значения и округления, после чего перемежай e,o. Сохранённые целые коэффициенты дают точное восстановление исходных целых.

Проверка обратимости следует подстановкой: первое вычитание снимает ровно ту поправку, которая была прибавлена к e. После этого известны исходные e, и прибавление предсказания возвращает o. Не нужно надеяться, что ошибка округления окажется «малой»: она вообще не должна влиять на точность обратного хода.

Разбор: одна строка с обеими границами

У входа [8,5,7,9,12,10,6,4] чётная часть [8,7,12,6], нечётная [5,9,10,4]. Первая деталь 5−(8+7)//2=−2. Последняя использует повтор последнего чётного: 4−(6+6)//2=−2. Полный набор деталей [−2,0,1,−2].

Первое обновление: 8+(-2-2+2)//4=7. Далее получаем низкую часть [7,7,12,6]. В обратном ходе из первого низкого коэффициента 7 вычитаем −1 и возвращаем 8. Только после восстановления всей чётной части можно восстанавливать нечётную.

from itertools import product


def forward(row):
    even, odd = row[::2], row[1::2]
    m = len(even)
    detail = [odd[i] - (even[i] + even[min(i + 1, m - 1)]) // 2
              for i in range(m)]
    low = [even[i] + (detail[max(i - 1, 0)] + detail[i] + 2) // 4
           for i in range(m)]
    return low + detail


def inverse(coeff):
    m = len(coeff) // 2
    low, detail = coeff[:m], coeff[m:]
    even = [low[i] - (detail[max(i - 1, 0)] + detail[i] + 2) // 4
            for i in range(m)]
    odd = [detail[i] + (even[i] + even[min(i + 1, m - 1)]) // 2
           for i in range(m)]
    result = []
    for a, b in zip(even, odd):
        result += [a, b]
    return result


for row in [[8, 5, 7, 9, 12, 10, 6, 4], [-3, -1, 2, 0]]:
    coeff = forward(row)
    print("вход:", row)
    print("низкие и детали:", coeff)
    print("обратно:", inverse(coeff))
checked = 0
for values in product([-1, 0, 1], repeat=6):
    row = list(values)
    assert inverse(forward(row)) == row
    checked += 1
print("проверены строки:", checked)

вход: [8, 5, 7, 9, 12, 10, 6, 4]
низкие и детали: [7, 7, 12, 6, -2, 0, 1, -2]
обратно: [8, 5, 7, 9, 12, 10, 6, 4]
вход: [-3, -1, 2, 0]
низкие и детали: [-3, 2, 0, -2]
обратно: [-3, -1, 2, 0]
проверены строки: 729

Список из восьми коэффициентов содержит четыре s и четыре d, а не отсчёты в первоначальном порядке. Вывод «обратно» совпал с входом. Вторая строка включает отрицательные исходные значения: правило округления работает без отдельной приблизительной арифметики. Последний перебор проверил все 3⁶=729 строк длины 6 над {−1,0,1}; общее доказательство дано подстановкой выше.

product([-1,0,1],repeat=6) перебирает все шесть позиций, в каждой выбирая один из трёх вариантов. repeat задаёт число позиций, а не повтор уже готового списка. Поэтому в проверке именно 729 строк.

Разбор: почему нельзя заменить // усечением

Пусть соседние детали −3 и 0. Числитель обновления равен −3+0+2=−1. Округление вниз даёт −1. Если прямой ход прибавил −1, а обратный вычел усечённое к нулю значение 0, чётный отсчёт изменится на единицу. Через предсказание эта ошибка может перейти и в нечётные позиции.

Можно построить другую обратимую схему с другим согласованным округлением, но это не делает её тем же преобразованием 5/3 и не обеспечивает совместимость с декодером, ожидающим данную формулу. Точное соглашение важнее привычки языка программирования: в разных языках деление отрицательных целых различается.

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

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

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

Для картинки алгоритм применяют по строкам и столбцам, затем повторяют над LL. В обратном ходе отменяют и порядок направлений, и порядок уровней. Каждый шаг касается линейного числа отсчётов; геометрическое уменьшение LL сохраняет суммарную работу O(N) для N пикселов.

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

Обратимый путь JPEG 2000 использует целочисленное преобразование 5/3. Понимание lifting позволяет отдельно проверить математику, границы и разрядность, прежде чем искать ошибку в энтропийном декодере. Если все коэффициенты сохранены, а исходные целые не восстановились, недостаточно назвать результат «почти точным»: это нарушение обещания выбранного пути.

Теперь сам

Даны s=[7,7], d=[−2,0]. Используя правила урока, восстанови четыре отсчёта. Какое действие отменяется первым и почему нельзя заменить граничную d[−1] нулём?