19 августа 2011 в 13:08

Основы фрактального сжатия изображений из песочницы

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

Для начала все-таки придется немного углубиться в математику и ввести несколько определений.
Нам пригодятся следующие:
  • Метрика — функция, заданная на пространстве, возвращающая расстояние между двумя точками этого пространства. Например, привычная нам Эвклидова метрика. Если на пространстве задана метрика, оно называется метрическим. Метрика должна удовлетворять определенным условиям, но не будем углубляться.
  • Сжимающее отображение (преобразование) — функция на метрическом пространстве, равномерно уменьшающая расстояние между двумя точками пространства. Например, y=0.5x.

Сжимающие отображения обладают важным свойством. Если взять любую точку и начать итеративно применять к ней одно и то же сжимающее отображение: f(f(f...f(x))), то результатом будет всегда одна и та же точка. Чем больше раз применим, тем точнее найдем эту точку. Называется она неподвижной точкой и для каждого сжимающего отображения она существует, причем только одна.

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



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

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

Тут мы переходим на следующий уровень — в пространство изображений. В этом пространстве:
  • Точка пространства — это изображение.
  • Расстояние между точками показывает, насколько похожи изображения между собой, насколько «близки» (естественно, если его задать соответствующим образом).
  • Сжимающее отображение делает два любых изображения более похожими (в смысле заданной метрики).


Имея СИФ, найти аттрактор просто. Во всяком случае, имея под рукой компьютер. Можно взять абсолютно любое начальное изображение и начать применять к нему СИФ. Пример с тем же треугольником, но уже построенным из квадрата:



Получается, что для построения довольно сложной фигуры нам потребовалось 18 коэффициентов. Выигрыш, как говорится, налицо.
Вот если бы мы умели решать обратную задачу — имея аттрактор, строить СИФ… Тогда достаточно взять аттрактор-изображение, похожее на фотографию вашей кошки и можно довольно выгодно его закодировать.

Вот здесь, собственно, начинаются проблемы. Произвольные изображения, в отличие от фракталов, не самоподобны, так что так просто эта задача не решается. Как это сделать придумал в 1992 году Арнольд Жакин, в то время — аспирант Майкла Барнсли, который считается отцом фрактального сжатия.

Самоподобие нам нужно обязательно — иначе ограниченные в своих возможностях аффинные преобразования не смогут правдоподобно приблизить изображения. А если его нет между частью и целым, то можно поискать между частью и частью. Примерно так, видимо, рассуждал и Жакин.

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


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



Можете поиграться сами: Coder demo.

Получение оптимального преобразования — отдельная тема, однако большого труда оно не составляет. Но другой недостаток схемы виден невооруженным глазом. Можете сами подсчитать, сколько доменных блоков размером 32×32 содержит двухмегапиксельное изображение. Полный их перебор для каждого рангового блока и есть основная проблема такого вида сжатия — кодирование занимает очень много времени. Разумеется, с этим борются при помощи различных ухищрений, вроде сужения области поиска или предварительной классификации доменных блоков. С различным ущербом для качества.

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



Пожалуй, для введения информации достаточно. Интересующиеся могут почитать соответствующие статьи в Википедии или соответствующем сообществе.

Подробное изложение можно найти в этой статье, с которой все началось в 1992 году. Большинство материалов, разумеется, на английском.
Дмитрий Прилипко @kometa_triatlon
карма
16,0
рейтинг 0,0
Похожие публикации
Самое читаемое Разработка

Комментарии (25)

  • +1
    Правильно ли я понял, что алгоритм выполняется несимметрично и время сжатия > времени восстановления?
    • –1
      Правильно. Думаете использовать в криптографии?
      • 0
        Пока просто думаю). Читал про фракталы у Вудса/Гонсалеса, но практического применения не нашел.
    • +1
      Правильно. Как правило, время кодирования значительно больше времени восстановления. Впрочем, если использовать современные методы оптимизации, то оно вполне разумное. Есть даже плагин для Фотошопа для сохранения изображений в формате FIF (Fractal Image Format).
  • 0
    И да, было бы интересно посмотреть реализацию, хотя бы в MATLAB
  • 0
    Думаю, фрактальным алгоритмом выгодно сжимать всякие карты и спутниковые снимки: там куча самоподобных элементов. Так ведь?
    • +5
      Да, лучше всего идут сложные изображения вроде природных ландшафтов. А рисовать при помощи фракталов горы, или береговую линию — это прям доктор прописал :)
  • +2
    По поводу этой фразы: «Имея СИФ, найти аттрактор просто.… Можно взять абсолютно любое начальное изображение и начать применять к нему СИФ.»

    Мне кажется, в общем случае это не так. Из теории динамических систем известно, что может быть несколько аттракторов. И изображение будет приближаться к одному из них в зависимости от того, в бассейне какого аттрактора оно находилось.
    • +4
      Если мы говорим вообще о динамической системе — то да. Но если мы работаем в пространстве R^n, а система состоит из сжимающих аффинных преобразований, то аттрактор будет только один. Это доказал Гатчинсон в 1981 году.
  • +2
    Кто скажет как зовут девушку — молодец!)
  • 0
    А на практике, насколько визуально качественный результат сжатия? Потому что изображение 6 довольно-таки квадратное.
    • +2
      Если верить этому сайту (а не верить Йелю я причин не вижу), то при коэффициенте сжатия 6.07:1 результат будет такой:
      image

      А при 25.11:1 такой:
      image
      • +5
        Ну то есть, JPEG в общем случае получше будет. Собственно поэтому фрактальное сжатие не распространено так широко. Впрочем, в некоторых случаях оно работает лучше.

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

        image

        image
  • +1
    В далёком 2008 г. я проводил эксперимент, сравнивая сжатие JPG и фрактальное сжатие:
    www.administrating.ru/fraktalnoe-szhatie-grafiki/

    Разница — более, чем в 3 раза. Но это была фотография природы…
    • 0
      Кстати, по поводу распространения. Патентная политика Барнсли — одна из причин. Но сроки патентов скоро истекают, так что его алгоритмы перейдут в общественное достояние. Но время уже не вернешь.
  • 0
    Сжимающие отображения обладают важным свойством. Если взять любую точку и начать итеративно применять к ней одно и то же сжимающее отображение: f(f(f...f(x))), то результатом будет всегда одна и та же точка. Чем больше раз применим, тем точнее найдем эту точку. Называется она неподвижной точкой и для каждого сжимающего отображения она существует, причем только одна.

    Математический баттхёрт!
    По вашей формулировке, преобразование сжатия переводит все точки в одну, с разной «точностью».
    Под точностью, видимо, имеется ввиду толщина точки, да?

    Незнаю, по каким учебникам вы учили фрактальную геометрию, но в моих атрактр определялся как точка, переводящаяся преобразованием в саму себя (с абсоютной «точностью»).

    • 0
      Аттрактор вы понимаете правильно. Что касается преобразования сжатия — то да, оно при бесконечном применении переводит все точки в одну — неподвижную точку преобразования.

      Что касается точности. Точка, понятно, толщины не имеет. Я имею ввиду, что другие точки удалены от неподвижной точки. И после каждой итерации приближаются все ближе и ближе. То есть точность нахождения неподвижной точки при итеративном методе зависит от количества итераций. Подчеркну — при итеративном. Если нужно найти абсолютно точное значение, то можно решить эту задачу аналитически: неподвижная точка есть точка пересечения графика отображения с графиком функции y=x.
      • 0
        Ну так и надо было написать, что преобразование приближает все точки к одной неподвижной.
        Математический термин «точность», да ещё и для IT-публики имеет весьма неадекватную интерпретацию.
  • 0
    Математический баттхёрт, continued.
    Сжимающее отображение (преобразование) — функция на метрическом пространстве, равномерно уменьшающая расстояние между двумя точками пространства. Например, y=0.5x.


    Например, y и x здесь что: векторы? кординаты точки? кординаты разных точек? точка до и после преобразования?
    Расстояние между какими точками меняет отображение y=0.5x?
    • 0
      Ну, во-первых — вектор и координаты точки — это одно и то же.
      x — аргумент функции, y — ее значение, что непонятного? y(x) = 0.5x.
      Сжимающее отображение — такая функция f(x), что d(x1, x2) <= d(f(x1), f(x2)). Где d — метрика на пространстве. Если взять в качестве f функцию y=0.5x, а в качестве метрики — эвклидову метрику, то можно убедиться, что функция y — сжимающее отображение на пространстве R^n, для любой размерности.
      • 0
        Это объяснение совершенно неочевидно иллюстрируется примером.

Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.