Фрактальное сжатие: хранить преобразования вместо пикселов

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

Как думаешь, можно ли распаковать картинку из другой картинки

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

Для произвольных правил ответ отрицательный. Правило «оставить как есть» сохранит любую начальную картинку. Правило «прибавить один» вообще не остановится. Фрактальный метод опирается на ограниченный класс отображений, для которых независимость предельного результата от начала доказуема.

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

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

IFS, система итерируемых функций, хранит эти правила. Неподвижная точка - картинка x*, для которой T(x*)=x*. Слово «сжатие» здесь имеет два смысла: уменьшение файла и математическое сокращение расстояний. Первое не следует автоматически из второго: ещё надо компактно описать достаточно хорошее приближение нужной картинки.

Механизм: домены, ранги и контракт

Разделим восстановленное изображение на непересекающиеся ранговые блоки. Для каждого кодировщик выбирает доменный фрагмент, обычно большего размера, способ уменьшения, возможный поворот или отражение, контраст s и сдвиг яркости o. Затем приближает ранг выражением s·downsample(domain)+o. В файл идут адрес домена и параметры, а не все его пикселы: домен при декодировании берётся из текущего приближения всей картинки.

Для конечного массива удобно измерять расстояние максимальной разностью пикселов. Усредняющее уменьшение и перестановка не увеличивают это расстояние. Если у всех блоков |s|≤q<1, вся сборка тоже сокращает расстояние не более чем в q раз: d(T(x),T(y))≤q·d(x,y). Здесь q - одна общая граница, не число пикселов. Фиксированное конечное пространство вещественных отсчётов с этой метрикой полно: пределы координат задают допустимый предельный массив.

По теореме о сжимающем отображении существует единственная неподвижная точка, а повторение T к ней сходится. Два старта сближаются как минимум геометрически: после k шагов их расстояние не больше q^k·d(x₀,y₀). Внутреннее округление до целых может изменить отображение и нарушить это доказательство; его нельзя незаметно добавить в модель и оставить прежнюю гарантию.

Правило

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

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

Разбор: выбрать домен и параметры яркости

Пусть уменьшенный домен имеет значения [10,30,50,70], а ранг [21,31,41,51]. Подходит s=0,5 и o=16: ошибка нулевая. Другой домен [40,40,40,40] не передаёт изменений. Лучшее постоянное приближение равно среднему 36, а сумма квадратов ошибок составляет 500.

Чтобы найти s,o по наименьшим квадратам, сначала вычисляют средние домена и ранга. Для непостоянного домена s=Σ(d−mean_d)(r−mean_r)/Σ(d−mean_d)², затем o=mean_r−s·mean_d. У первого домена числитель 1000, знаменатель 2000. После ограничения допустимого контраста сдвиг пересчитывают. При нулевом знаменателе выбирают постоянную модель, а не делят на ноль.

def fit(domain, target):
    mean_d = sum(domain) / len(domain)
    mean_r = sum(target) / len(target)
    denominator = sum((v - mean_d) ** 2 for v in domain)
    if denominator == 0:
        scale = 0.0
    else:
        scale = sum((a - mean_d) * (b - mean_r)
                    for a, b in zip(domain, target)) / denominator
    scale = max(0.0, min(0.9, scale))
    shift = mean_r - scale * mean_d
    error = sum((scale * a + shift - b) ** 2
                for a, b in zip(domain, target))
    return scale, shift, error


def step(image):
    a, b = image
    return [0.5 * b + 10, 0.25 * a + 30]


for domain in [[10, 30, 50, 70], [40, 40, 40, 40]]:
    print("домен:", domain, "параметры/ошибка:",
          fit(domain, [21, 31, 41, 51]))
a, b = [0.0, 0.0], [255.0, 255.0]
for count in range(21):
    if count in [0, 1, 5, 20]:
        print("итерация", count, [round(x, 6) for x in a],
              [round(x, 6) for x in b])
    a, b = step(a), step(b)
original = 36
collage_error = abs(0.5 * original + 15 - original)
print("ошибка одного шага:", collage_error,
      "граница:", collage_error / (1 - 0.5))

домен: [10, 30, 50, 70] параметры/ошибка: (0.5, 16.0, 0.0)
домен: [40, 40, 40, 40] параметры/ошибка: (0.0, 36.0, 500.0)
итерация 0 [0.0, 0.0] [255.0, 255.0]
итерация 1 [10.0, 30.0] [137.5, 93.75]
итерация 5 [28.28125, 37.03125] [30.273438, 38.027344]
итерация 20 [28.571429, 37.142857] [28.571429, 37.142857]
ошибка одного шага: 3.0 граница: 6.0

В программе допустимый контраст ограничен диапазоном 0…0,9. Вторая демонстрация - система двух отсчётов с общим коэффициентом q=0,5. Старт из нулей и из 255 приводит к одному приближению [28,571429;37,142857]. Числа округляются лишь при печати, а не после каждого внутреннего шага. Это иллюстрация теоремы, а не полноценный формат фрактального файла.

Разбор: ошибка одного шага ограничивает итоговую

Обозначим исходную картинку f, результат одного применения правил T(f). Пусть d(f,T(f))≤ε, а T сжимает расстояния с q<1. По неравенству треугольника d(f,x*)≤d(f,T(f))+d(T(f),T(x*))≤ε+q·d(f,x*). Переносим последнее слагаемое и получаем d(f,x*)≤ε/(1−q). Это объясняет, зачем кодировщик подгоняет блоки за один шаг, хотя декодер потом делает много итераций.

Для T(x)=0,5x+15 неподвижная точка 30. Возьмём оригинал 36: после одного шага 33, ошибка ε=3. Граница 3/(1−0,5)=6 совпала с расстоянием от 36 до 30. Если q близок к 1, даже малая ε может давать слабую границу, а сближение разных стартов идёт медленнее.

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

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

Дорогой этап - перебор доменов, ориентаций и параметров для каждого ранга. При R рангах, D доменах, S ориентациях и B пикселах сравнения прямой поиск требует O(R·D·S·B) работы. Классификация доменов и раннее отбрасывание ускоряют поиск, но могут исключить лучший вариант. Быстрый поиск не является частью теоремы сходимости.

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

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

Теперь сам

Для T(x)=0,25x+9 найди неподвижную точку. Исходное значение равно 16. Какова ошибка одного шага и граница ε/(1−q)? Можно ли применить ту же теорему к T(x)=x?