ROI: от выбранного пиксела к коэффициентам

Если находишь коэффициенты, влияющие на выбранный пиксел, и выбираешь достаточный сдвиг, переходи к «Теперь сам».

Как думаешь, одному пикселу нужен один коэффициент

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

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

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

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

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

Механизм: проследить обратный ход

Возьмём один уровень строки длины 8: коэффициенты имеют порядок [L0,L1,L2,L3,H0,H1,H2,H3]. Чтобы увидеть локальную структуру, рассмотрим вещественный каркас 5/3 без целочисленных округлений:

e[i] = L[i] - (H[max(i-1,0)] + H[i])/4
odd[i] = H[i] + (e[i] + e[min(i+1,3)])/2

На краях повторяются ближайшие значения, как в предыдущих опытах. Исходные пикселы расположены в порядке e0,odd0,e1,odd1,e2,odd2,e3,odd3. Пиксел 3 - это odd1. Он зависит от H1,e1,e2. При этом e1 зависит от L1,H0,H1, а e2 - от L2,H1,H2. Итак, требуются L1,L2,H0,H1,H2, то есть индексы [1,2,4,5,6].

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

Правило

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

Если помечены все коэффициенты, непомеченного фона нет и его максимум не определён. Селективный приоритет тогда не нужен: выбирай s=0 и не сдвигай коэффициенты. Правило с максимумом относится к непустому фоновому множеству.

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

Разбор: маска для одной точки

Программа ниже перебирает восемь единичных коэффициентов вещественного каркаса. У коэффициента 1 поддержка [1,2,3], у коэффициента 2 - [3,4,5]. Оба нужны для ROI={3}, хотя коэффициент 2 не имеет того же индекса, что выбранный пиксел. К ним добавляются три детали 4,5,6.

Поддержка коэффициента 7 равна [5,6,7]. Она не пересекает ROI={3}, поэтому этот коэффициент в нашем одноуровневом примере можно не повышать. Проверка через пересечение множеств делает условие однозначным: коэффициент выбирается тогда, когда хотя бы один важный пиксел находится в его поддержке.

def inverse(c):
    m = len(c)//2
    e = [c[i]-(c[m+max(i-1,0)]+c[m+i])/4
         for i in range(m)]
    d = c[m:]
    odd = [d[i]+(e[i]+e[min(i+1,m-1)])/2 for i in range(m)]
    return [v for pair in zip(e,odd) for v in pair]


roi = {3}
selected = []
for k in range(8):
    impulse = [0.]*8
    impulse[k] = 1.
    support = [i for i,v in enumerate(inverse(impulse)) if abs(v)>1e-12]
    print("коэффициент", k, "пикселы", support)
    if roi.intersection(support):
        selected.append(k)
print("ROI", sorted(roi), "нужны", selected)
c = [10, 12, 14, 16, -2, 3, 1, -1]
shift = 5
encoded = [v*(2**shift if k in selected else 1) for k,v in enumerate(c)]
print("масштабированные:", encoded)
outside = max((abs(v) for k,v in enumerate(c)
               if k not in selected), default=0)
print("порог:", 2**shift, "вне ROI максимум:", outside)
restored = [v//2**shift if k in selected else v
            for k,v in enumerate(encoded)]
print("сняли сдвиг:", restored == c)

коэффициент 0 пикселы [0, 1]
коэффициент 1 пикселы [1, 2, 3]
коэффициент 2 пикселы [3, 4, 5]
коэффициент 3 пикселы [5, 6, 7]
коэффициент 4 пикселы [0, 1, 2, 3]
коэффициент 5 пикселы [1, 2, 3, 4, 5]
коэффициент 6 пикселы [3, 4, 5, 6, 7]
коэффициент 7 пикселы [5, 6, 7]
ROI [3] нужны [1, 2, 4, 5, 6]
масштабированные: [10, 384, 448, 16, -64, 96, 32, -1]
порог: 32 вне ROI максимум: 16
сняли сдвиг: True

Для картинки 8×8 с таким же разделимым преобразованием и одной ROI-точкой(3,3) получится произведение найденных одномерных наборов: по каждой оси индексы 1,2,4,5,6. В выбранном представлении коэффициентов это 25 пар индексов. Так становится видно, почему пиксельная маска 1×1 не превращается просто в маску 1×1 внутри каждой полосы. Для других фильтров число и форма зависимостей изменятся.

Разбор: достаточный и недостаточный сдвиг

Коэффициенты [10,12,14,16,−2,3,1,−1], помечены 1,2,4,5,6. Вне ROI остаются 10,16,−1; максимальный модуль 16. Если выбрать s=3, то помеченная единица станет 8, а фоновый коэффициент 16 всё ещё начнётся в более старшей битовой плоскости. Одного факта «мы сдвинули» мало.

При s=5 порог равен 32. Теперь помеченные ненулевые величины имеют модули как минимум 32, а фон меньше 32. Получаются [10,384,448,16,−64,96,32,−1]. Декодер может определить повышенные величины по порогу и вернуть им масштаб. В программе используется известная маска для наглядной проверки; пороговое различение на этих данных даст тот же набор ненулевых коэффициентов.

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

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

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

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

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

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

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

Теперь сам

Фоновый максимальный модуль равен 7, помеченная деталь равна−3. Какой минимальный целый s удовлетворяет правилу? Что передаётся вместо−3? Потребуется ли при восстановлении знак?