RCT: обратимый цвет с целочисленным округлением

Если выводишь обратные формулы RCT и различаешь деление вниз и к нулю, переходи к «Теперь сам».

Как думаешь, округление обязательно уничтожит цвет

У пиксела RGB=(17,10,4) взвешенная сумма R+2G+B равна 41. Деление на четыре даёт 10,25. Если оставить только целое 10, кажется, что четверть уже потеряна. Но цветовое преобразование передаёт ещё два целых числа: насколько синяя и красная компоненты отличаются от зелёной. Может ли эта дополнительная информация вернуть все три исходных числа?

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

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

Ты записал три суммы расходов за день. Вместо каждой суммы отдельно можно хранить одну опорную сумму и две поправки к ней. Поправки способны быть отрицательными, хотя сами расходы неотрицательны. Запретить отрицательные поправки означало бы изменить описание данных.

В RCT опорная величина устроена немного хитрее среднего: она даёт больший вес зелёной компоненте. Остальные два числа - точные разности. Это смена способа описания того же пиксела. Преобразование не обещает, что каждое новое число станет меньше или что три числа превратятся в два. Оно рассчитывает на статистическую связь компонент: у близких R,G,B разности часто меньше исходных значений и удобнее для дальнейшего кодирования.

Механизм: выразить неизвестное через сохранённые разности

Зафиксируем соглашение о названиях:

Y = (R + 2G + B) // 4
U = B - G
V = R - G

Оператор // означает округление результата вниз, к меньшему целому. Например, −11//4=−3. Это отличается от отбрасывания дробной части к нулю, которое дало бы −2. У другой записи RCT имена двух разностей могут быть переставлены. Поэтому полезно передавать или проверять именно формулы, а не угадывать порядок по буквам U,V.

Из разностей следует R=G+V и B=G+U. Подставим в формулу Y: Y=(4G+U+V)//4. Поскольку G целое, оно точно выходит из округления: Y=G+(U+V)//4. Отсюда получаем обратный ход:

G = Y - (U+V)//4
R = V + G
B = U + G

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

Правило

В выбранном RCT сохраняй Y=(R+2G+B)//4, U=B−G, V=R−G. Восстанавливай сначала G=Y−(U+V)//4, затем R и B прибавлением разностей. Используй деление вниз с обеих сторон. Не обрезай отрицательные разности и не ограничивай промежуточные значения диапазоном исходного пиксела.

Если данные беззнаковые и имеют p битов на компоненту, перед последующими преобразованиями возможен отдельный сдвиг уровня на половину диапазона, 2^(p−1). Его обратный шаг - прибавление того же числа. Знак и разрядность входа должны быть известны; величина сдвига не выбирается произвольно для каждого пиксела. RCT можно применить к уже сдвинутым целым компонентам: доказательство от знака не зависит.

Разбор: четверть не потребовалась

Для (17,10,4) получаем Y=41//4=10, U=−6, V=7. Обратный ход: (U+V)//4=1//4=0, поэтому G=10−0=10. Далее R=7+10=17 и B=−6+10=4. Восстановлены все три компоненты. Хотя при вычислении Y возникло округление, тройка не потеряла информации.

Для другого пиксела (3,8,1) сумма равна 20, Y=5, U=−7, V=−5. Теперь (U+V)//4=−12//4=−3, G=5−(−3)=8, R=−5+8=3, B=−7+8=1. Отрицательное деление относится к обратному ходу даже при неотрицательных исходных компонентах. Это нормальная часть алгоритма.

def rct(rgb):
    r, g, b = rgb
    return ((r + 2*g + b)//4, b-g, r-g)


def inverse(yuv):
    y, u, v = yuv
    g = y - (u+v)//4
    return (v+g, g, u+g)


for rgb in [(17, 10, 4), (3, 8, 1), (-2, -7, 4)]:
    code = rct(rgb)
    print("RGB", rgb, "RCT", code, "обратно", inverse(code))
    assert inverse(code) == rgb
code = rct((3, 8, 2))
y, u, v = code
print("отрицательная сумма:", u+v, "G верное:", y-(u+v)//4,
      "G при округлении к нулю:", y-int((u+v)/4))
count = 0
for r in range(-4, 5):
    for g in range(-4, 5):
        for b in range(-4, 5):
            assert inverse(rct((r, g, b))) == (r, g, b)
            count += 1
print("точных проверок:", count)

RGB (17, 10, 4) RCT (10, -6, 7) обратно (17, 10, 4)
RGB (3, 8, 1) RCT (5, -7, -5) обратно (3, 8, 1)
RGB (-2, -7, 4) RCT (-3, 11, 5) обратно (-2, -7, 4)
отрицательная сумма: -11 G верное: 8 G при округлении к нулю: 7
точных проверок: 729

Программа также проверяет все 729 троек из диапазона −4..4. Это полезная проверка реализации на отрицательных значениях и остатках деления. Само доказательство обратимости находится выше: полный перебор малого диапазона не заменяет алгебраическое объяснение для произвольных целых чисел.

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

Возьмём (3,8,2). Прямой ход даёт Y=21//4=5, U=−6, V=−5. Правильный обратный ход использует −11//4=−3 и получает G=8. Если декодер делит к нулю, то берёт −2 и получает G=7. После прибавления разностей он восстановит (2,7,1), а не (3,8,2). Все три компоненты изменились на единицу из-за одного правила.

Другая ошибка - ограничить U до нуля, потому что «цвет не бывает отрицательным». Тогда исходная разность −6 исчезнет и восстановление уже не сможет узнать, насколько синяя компонента меньше зелёной. Ограничивать к диапазону вывода можно лишь в предусмотренной точке алгоритма; это отдельная потенциально необратимая операция, а не безобидное исправление промежуточных чисел.

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

Сравнивают только Y и решают, что метод уже без потерь. Или записывают отрицательные разности в беззнаковый байт без согласованного представления и получают переполнение. Для промежуточных сумм требуется достаточная разрядность: у восьмибитных компонент выражение R+2G+B может быть больше 255. Python автоматически увеличивает целые числа; фиксированная машинная арифметика требует отдельного расчёта диапазона.

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

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

Ты проверяешь обещание «JPEG 2000 без потерь». Сначала выполни отдельный круговой проход RGB→RCT→RGB, затем подключи целочисленный 5/3, затем кодирование полного набора коэффициентов. Такое разделение показывает, на каком этапе появился первый несовпавший отсчёт. Если цветовой шаг уже неточен, исправление энтропийного кодера не вернёт потерянные значения.

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

Теперь сам

Декодеру передали Y=−3,U=11,V=5. Найди RGB. Затем объясни, почему точный RCT не спасёт изображение, если после 5/3 удалить детали.