Фильтр 9/7: четыре шага, нормировка и ошибка

Если можешь отменить четыре lifting-шага и отделяешь нормировку от квантования, переходи к «Теперь сам».

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

После 5/3 строка из восьми отсчётов превращалась в восемь коэффициентов. В названии 9/7 появились большие числа. Должно ли теперь получиться девять средних и семь деталей? Нет: числа относятся к длинам двух связанных фильтров: при анализе низкая полоса L использует девять отсчётов, а высокая полоса H - семь. Это не количество выходных коэффициентов: один уровень снова делит данные на две половины. Вдали от границы это видно из шагов ниже: первый прогноз детали охватывает три входных отсчёта; обновление низкой полосы расширяет опору до пяти; следующий прогноз детали - до семи; последнее обновление низкой полосы - до девяти. На границе используют заданное продолжение строки, поэтому часть позиций совпадает.

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

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

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

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

Механизм: четыре чередующихся исправления

Из строки чётной длины выделим e - отсчёты с чётными индексами, d - отсчёты с нечётными. Индексация начинается с нуля. Условимся о симметричном продолжении: справа при запросе e за последним элементом повторяем последний e; слева при запросе d перед первым элементом повторяем первый d. Например, для двух пар это e[2]=e[1] и d[−1]=d[0]. Так край не заменяется произвольным нулём.

Применим последовательно четыре шага:

d[i] += A * (e[i] + e[i+1])
e[i] += B * (d[i-1] + d[i])
d[i] += C * (e[i] + e[i+1])
e[i] += D * (d[i-1] + d[i])

Здесь += означает прибавление к текущему значению, а новые значения предыдущего шага уже участвуют в следующем. Коэффициенты выбранного разложения 9/7: A=−1,586134342059924; B=−0,052980118572961; C=0,882911075530934; D=0,443506852043971. После этих шагов зададим L=e/K и H=d·K, где K=1,230174104914001. Нормировка фиксирует единицы коэффициентов. С другой парой масштабов получились бы другие числа при той же исходной строке.

Повторное подставление формул друг в друга превращает эти короткие шаги в взвешенную сумму нескольких исходных соседей. Такая сумма называется свёрткой с фильтром. Например, первый шаг использует три отсчёта: odd + A*left_even + A*right_even. После следующих исправлений зависимость распространяется дальше, что и связывает lifting с длинными фильтрами 9/7.

Правило

Для обратного хода сначала верни масштабы e=L·K, d=H/K. Потом вычитай поправки в порядке D,C,B,A, каждый раз используя уже восстановленную нужную половину. Прямой и обратный ход должны совпадать по коэффициентам и продолжению границ. Вещественный lifting не выдавай за точное целочисленное кодирование без потерь.

Выбранный масштаб сохраняет низкие коэффициенты постоянной строки: для входа из десяток получаются L≈10 и H≈0. Это удобная проверка нормировки. Встречаются и другие нормировки той же пары фильтров. Сравнивать таблицы коэффициентов можно только после проверки порядка полос, знаков и масштаба.

Разбор: строка из четырёх чисел

Возьмём [4,10,6,2]: e=[4,6], d=[10,2]. Первое исправление даёт d[0]=10+A·(4+6)≈−5,861343, а на правой границе d[1]=2+A·(6+6)≈−17,033612. Именно удвоение последнего e реализует наше продолжение границы. Если взять справа ноль, уже второй коэффициент будет другим.

Следующие исправления и нормировка дают L≈[7,063928;5,968036], H≈[5,642892;−5,285783]. Полная программа ниже печатает также обратный ход. В ней нет промежуточного округления до шести знаков: это только формат показа результата. Вычисления продолжаются с полной доступной точностью Python float.

A, B = -1.586134342059924, -0.052980118572961
C, D = 0.882911075530934, 0.443506852043971
K = 1.230174104914001


def change(e, d, coefficient, odd):
    if odd:
        return [d[i]+coefficient*(e[i]+e[min(i+1,len(e)-1)])
                for i in range(len(d))]
    return [e[i]+coefficient*(d[max(i-1,0)]+d[i])
            for i in range(len(e))]


def forward(x):
    e, d = x[::2], x[1::2]
    d = change(e, d, A, True)
    e = change(e, d, B, False)
    d = change(e, d, C, True)
    e = change(e, d, D, False)
    return [v/K for v in e] + [v*K for v in d]


def inverse(c):
    m = len(c)//2
    e, d = [v*K for v in c[:m]], [v/K for v in c[m:]]
    e = change(e, d, -D, False)
    d = change(e, d, -C, True)
    e = change(e, d, -B, False)
    d = change(e, d, -A, True)
    return [v for pair in zip(e, d) for v in pair]


x = [4., 10., 6., 2.]
c = forward(x)
print("9/7:", [round(v, 6) for v in c])
print("обратный:", [round(v, 6) for v in inverse(c)])
q = [round(v/2)*2 for v in c]
z = inverse(q)
print("шаг 2:", q)
print("восстановление:", [round(v, 6) for v in z])
print("MSE:", round(sum((a-b)**2 for a,b in zip(x,z))/len(x), 6))
print("постоянная:", [round(v, 6) for v in forward([10.]*4)])
error = max(abs(a-b) for a,b in zip(x,inverse(c)))
print("ошибка арифметики < 1e-12:", error < 1e-12)

9/7: [7.063928, 5.968036, 5.642892, -5.285783]
обратный: [4.0, 10.0, 6.0, 2.0]
шаг 2: [8, 6, 6, -6]
восстановление: [4.825435, 10.800238, 6.087282, 1.399525]
MSE: 0.422478
постоянная: [10.0, 10.0, -0.0, -0.0]
ошибка арифметики < 1e-12: True

Предикат в последней строке проверяет ошибку меньше 10^−12 на данном примере. Он не утверждает побитового совпадения вещественных представлений и не доказывает, что любые платформы или любые длины строк дадут ту же максимальную ошибку. Для проверки реализации нужны разные длины, края, постоянные строки и импульсы.

Разбор: откуда появляется ошибка с шагом два

Теперь округлим каждый коэффициент к ближайшему кратному двум. Программа получает [8,6,6,−6], затем восстанавливает приблизительно [4,825435;10,800238;6,087282;1,399525]. MSE равна 0,422478. Обратный алгоритм выполнен, но его входом были изменённые коэффициенты. Он точно обращает другой набор чисел, поэтому не обязан вернуть прежние пикселы.

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

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

Сохраняют L,H с одним масштабом, а декодируют с другим. На постоянном входе вместо десяток возникает неверная яркость, и ошибку ошибочно ищут в арифметическом кодере. Либо применяют нулевое продолжение только у декодера: внутренние пикселы выглядят правдоподобно, а вдоль границы появляются заметные расхождения.

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

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

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

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

Теперь сам

Получены L=5,H=8, а нормировка задаёт K=2. Какие e,d поступят в начало обратного lifting? Если последним прямым шагом было e += 0,5*(d_left+d_right), как отменить его при d_left=2,d_right=6?