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

[dima_eam]

Правильно ли я понял, что алгоритм выполняется несимметрично и время сжатия > времени восстановления?

[Ocelot]

Правильно. Думаете использовать в криптографии?

[dima_eam]

Пока просто думаю). Читал про фракталы у Вудса/Гонсалеса, но практического применения не нашел.

[kometa_triatlon]

Правильно. Как правило, время кодирования значительно больше времени восстановления. Впрочем, если использовать современные методы оптимизации, то оно вполне разумное. Есть даже плагин для Фотошопа для сохранения изображений в формате FIF (Fractal Image Format).

[dima_eam]

И да, было бы интересно посмотреть реализацию, хотя бы в MATLAB

[kometa_triatlon]

Здесть что-то есть такое.

[Ocelot]

Думаю, фрактальным алгоритмом выгодно сжимать всякие карты и спутниковые снимки: там куча самоподобных элементов. Так ведь?

[kometa_triatlon]

Да, лучше всего идут сложные изображения вроде природных ландшафтов. А рисовать при помощи фракталов горы, или береговую линию — это прям доктор прописал :)

[Bas1l]

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

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

[kometa_triatlon]

Если мы говорим вообще о динамической системе — то да. Но если мы работаем в пространстве R^n, а система состоит из сжимающих аффинных преобразований, то аттрактор будет только один. Это доказал Гатчинсон в 1981 году.

[pomkaster]

Кто скажет как зовут девушку — молодец!)

[zotov]

Для меня стало неожиданностью, что легендарная тестовая фотография всех картиносжимальщиков на самом деле из Playboy.

www-2.cs.cmu.edu/%7Echuck/lennapg/
Полный вариант (уберите детей от телевизора): i2.listal.com/image/1705778/936full-lena-soderberg.jpg

[kometa_triatlon]

Девушку зовут Лена и это целая история.

[pomkaster]

Я то в курсе. И для меня эта история тоже удивила. Просто хотелось поделиться с хабрасообществом. Так же советую почитать про ru.wikipedia.org/wiki/Tom%27s_Diner#.D0.A1.D1.8E.D0.B7.D0.B0.D0.BD.D0.BD.D0.B0_.D0.92.D0.B5.D0.B3.D0.B0_.E2.80.94_.C2.AB.D0.9C.D0.B0.D0.BC.D0.B0_MP3.C2.BB

[Mr_Floppy]

А на практике, насколько визуально качественный результат сжатия? Потому что изображение 6 довольно-таки квадратное.

[kometa_triatlon]

Если верить этому сайту (а не верить Йелю я причин не вижу), то при коэффициенте сжатия 6.07:1 результат будет такой:


А при 25.11:1 такой:

[kometa_triatlon]

Ну то есть, JPEG в общем случае получше будет. Собственно поэтому фрактальное сжатие не распространено так широко. Впрочем, в некоторых случаях оно работает лучше.

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

[klark]

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

Разница — более, чем в 3 раза. Но это была фотография природы…

[kometa_triatlon]

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

[qmax]

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

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

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

[kometa_triatlon]

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

Что касается точности. Точка, понятно, толщины не имеет. Я имею ввиду, что другие точки удалены от неподвижной точки. И после каждой итерации приближаются все ближе и ближе. То есть точность нахождения неподвижной точки при итеративном методе зависит от количества итераций. Подчеркну — при итеративном. Если нужно найти абсолютно точное значение, то можно решить эту задачу аналитически: неподвижная точка есть точка пересечения графика отображения с графиком функции y=x.

[qmax]

Ну так и надо было написать, что преобразование приближает все точки к одной неподвижной.
Математический термин «точность», да ещё и для IT-публики имеет весьма неадекватную интерпретацию.

[qmax]

Математический баттхёрт, continued.

Сжимающее отображение (преобразование) — функция на метрическом пространстве, равномерно уменьшающая расстояние между двумя точками пространства. Например, y=0.5x.

Например, y и x здесь что: векторы? кординаты точки? кординаты разных точек? точка до и после преобразования?
Расстояние между какими точками меняет отображение y=0.5x?

[kometa_triatlon]

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

[qmax]

Это объяснение совершенно неочевидно иллюстрируется примером.