Как стать автором
Обновить

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

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

Мне кажется, в общем случае это не так. Из теории динамических систем известно, что может быть несколько аттракторов. И изображение будет приближаться к одному из них в зависимости от того, в бассейне какого аттрактора оно находилось.
Если мы говорим вообще о динамической системе — то да. Но если мы работаем в пространстве R^n, а система состоит из сжимающих аффинных преобразований, то аттрактор будет только один. Это доказал Гатчинсон в 1981 году.
Кто скажет как зовут девушку — молодец!)
Для меня стало неожиданностью, что легендарная тестовая фотография всех картиносжимальщиков на самом деле из Playboy.

www-2.cs.cmu.edu/%7Echuck/lennapg/
Полный вариант (уберите детей от телевизора): i2.listal.com/image/1705778/936full-lena-soderberg.jpg
Я то в курсе. И для меня эта история тоже удивила. Просто хотелось поделиться с хабрасообществом. Так же советую почитать про 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
А на практике, насколько визуально качественный результат сжатия? Потому что изображение 6 довольно-таки квадратное.
Если верить этому сайту (а не верить Йелю я причин не вижу), то при коэффициенте сжатия 6.07:1 результат будет такой:
image

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

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

image

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

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

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

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

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

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


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

Публикации

Истории