Фрактальный алгоритм сжатия информации. Обзор алгоритмов сжатия с потерями Фрактальное сжатие изображений c#

Фрактальный алгоритм

История фрактального сжатия

Рождение фрактальной геометрии обычно связывают с выходом в 1977 году книги Б. Мандельброта "Фрактальная геометрия природы". Одна из основных идей книги заключалась в том, что средствами традиционной геометрии (то есть используя линии и поверхности), чрезвычайно сложно представить природные объекты. Фрактальная геометрия задает их очень просто.

В 1981 году Джон Хатчинсон опубликовал статью "Фракталы и самоподобие", в которой была представлена теория построения фракталов с помощью системы итерируемых функций (IFS , Iterated Function System). Четыре года спустя появилась статья Майкла Барнсли и Стефана Демко, в которой приводилась уже достаточно стройная теория IFS. В 1987 году Барнсли основал Iterated Systems, компанию, основной деятельностью которой является создание новых алгоритмов и ПО с использованием фракталов. Всего через год, в 1988 году, он выпустил фундаментальный труд "Фракталы повсюду". Помимо описания IFS, в ней был получен результат, известный сейчас как Collage Theorem, который лежит в основе математического обоснования идеи фрактальной компрессии.

Первая статья об успехах Барнсли в области компрессии появилась в журнале BYTE в январе 1988 года. В ней не описывалось решение обратной задачи, но приводилось несколько изображений, сжатых с коэффициентом 1:10000, что было совершенно ошеломительно. Но практически сразу было отмечено, что несмотря на броские названия ("Темный лес", "Побережье Монтере", "Поле подсолнухов") изображения в действительности имели искусственную природу. Это, вызвало массу скептических замечаний, подогреваемых еще и заявлением Барнсли о том, что "среднее изображение требует для сжатия порядка 100 часов работы на мощной двухпроцессорной рабочей станции, причем с участием человека".

Отношение к новому методу изменилось в 1992 году, когда Арнауд Джеквин, один из сотрудников Барнсли, при защите диссертации описал практический алгоритм и опубликовал его. Этот алгоритм был крайне медленным и не претендовал на компрессию в 10000 раз (полноцветное 24-разрядное изображение с его помощью могло быть сжато без существенных потерь с коэффициентом 1:8 - 1:50); но его несомненным достоинством было то, что вмешательство человека удалось полностью исключить. Сегодня все известные программы фрактальной компрессии базируются на алгоритме Джеквина. В 1993 году вышел первый коммерческий продукт компании Iterated Systems. Ему было посвящено достаточно много публикаций, но о коммерческом успехе речь не шла, продукт был достаточно "сырой", компания не предпринимала никаких рекламных шагов, и приобрести программу было тяжело.

В 1994 году Ювал Фишер были предоставил во всеобщее пользование исходные тексты исследовательской программы, в которой использовалось разложение изображения в квадродерево и были реализованы алгоритмы оптимизации поиска. Позднее появилось еще несколько исследовательских проектов, которые в качестве начального варианта программы использовали программу Фишера. В июле 1995 года в Тронхейме (Швеция) состоялась первая школа-конференция, посвященная фрактальной компрессии.

Идея метода

Фрактальная архивация основана на том, что мы представляем изображение в более компактной форме – с помощью коэффициентов системы итерируемых функций (Iterated Function System – далее по тексту как IFS). Строго говоря, IFS представляет собой набор трехмерных аффинных преобразований , в нашем случае переводящих одно изображение в другое. Преобразованию подвергаются точки в трехмерном пространстве (х_координата, у_координата, яркость).

Наиболее наглядно этот процесс продемонстрировал Барнсли в своей книге "Fractal Image Compression". Там введено понятие Фотокопировальной Машины, состоящей из экрана, на котором изображена исходная картинка, и системы линз, проецирующих изображение на другой экран:

• Линзы могут проецировать часть изображения произвольной формы в любое другое место нового изображения.
• Области, в которые проецируются изображения, не пересекаются.
• Линза может менять яркость и уменьшать контрастность.
• Линза может зеркально отражать и поворачивать свой фрагмент изображения.
• Линза должна масштабировать (уменьшать) свой фрагмент изображения.

Расставляя линзы и меняя их характеристики, мы можем управлять получаемым изображением. Одна итерация работы машины заключается в том, что по исходному изображению с помощью проектирования строится новое, после чего новое берется в качестве исходного. Утверждается, что в процессе итераций мы получим изображение, которое перестанет изменяться. Оно будет зависеть только от расположения и характеристик линз, и не будет зависеть от исходной картинки. Это изображение называется "неподвижной точкой" или аттрактором данной IFS . Соответствующая теория гарантирует наличие ровно одной неподвижной точки для каждой IFS.

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

Наиболее известны два изображения, полученных с помощью IFS : "треугольник Серпинского" и "папоротник Барнсли".

"Треугольник Серпинского" задается тремя, а "папоротник Барнсли" четырьмя аффинными преобразованиями (или, в нашей терминологии, "линзами"). Каждое преобразование кодируется считанными байтами, в то время как изображение, построенное с их помощью, может занимать и несколько мегабайт.

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

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

Математические основы фрактального сжатия

Определение. Преобразование w:R 2 –> R 2 , представимое в виде

где a, b, c, d, e, f, p, q, r, s, t, u действительные числа и (x y z) принадлежит R 3 называется трехмерным аффинным преобразованием.

Определение. Пусть f:X –> X – преобразование в пространстве Х. Точка x f принадлежащая X такая, что f(x f)=x f называется неподвижной точкой (аттрактором) преобразования.

Определение. Пусть f:X–>X в метрическом пространстве (Х, d) называется сжимающим, если существует число s: 0 <= s < 1, такое, что d(f(x),f(y)) <= s * d(x,y) длялюбых x,y принадлежащих X.

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

Теорема (О сжимающем преобразовании). Пусть f:X –> X в полном метрическом пространстве (Х, d). Тогда существует в точности одна неподвижная точка x f принадлежащая X этого преобразования, и для любой точки x принадлежащей X последовательность {f n (x): n=0,1,2…} сходится к x f .

Более общая формулировка этой теоремы гарантирует нам сходимость.

Определение. Изображением называется функция S, определенная на единичном квадрате и принимающая значения от 0 до 1 или S(x,y) принадлежит для любых x,y принадлежащих .

Пусть трехмерное аффинное преобразование w f:R 3 –> R 3 , записано в виде

При этом, если интерпретировать значение S как яркость соответствующих точек, она уменьшится в p раз (преобразование обязано быть сжимающим) и изменится на сдвиг q.

Определение. Конечная совокупность W сжимающих трехмерных аффинных преобразований w i , определенных на областях D i , таких, что w i (D i) = R i и пересечение R i с R j является пустым множеством, называется системой итерируемых функций (IFS).

Системе итерируемых функций однозначно сопоставляется неподвижная точка – изображение. Таким образом, процесс компрессии заключается в поиске коэффициентов системы, а процесс декомпрессии – в проведении итераций системы до стабилизации полученного изображения (неподвижной точки IFS). На практике бывает достаточно 7-16 итераций. Области R i в именуются ранговыми, а области D i – доменными.

Типовая схема фрактального сжатия

С учётом вышесказанного, схема компрессии выглядит так: изображение R разбивают на ранговые области R i . Далее для каждой области R i находят область D i и преобразование w i такие, что выполняются следующие условия:

1. D i по размерам больше R i .
2. w i (R i) имеет ту же форму, размеры и положение, что и R i .
3. Коэффициент преобразования должен быть меньше единицы.
4. Значение должно быть как можно меньше.

Первые три условия означают, что отображение w i будет сжимающим. А в силу четвёртого условия кодируемое изображение R и его образ W(R) будут похожи друг на друга. В идеале R = W(R). А это означает, что изображение R и будет являться неподвижной точкой W. Именно здесь используется подобие различных частей изображения. Как оказалось, практически все реальные изображения содержат такие похожие друг на друга, с точностью до аффинного преобразования , части.

Таким образом, для компрессии изображения W нужно:

1. Разбить изображение на ранговые области R i (непересекающиеся области, покрывающие все изображение).
2. Для каждой ранговой области R i найти область D i , и отображение w i , с указанными выше свойствами.
3. Запомнить коэффициенты аффинных преобразований W, положения доменных областей D i , а также разбиение изображения на домены.

Соответственно, для декомпрессии изображения нужно будет:JPEG существует возможность увеличить степень сжатия за счет увеличения потерь. Кроме того, оба алгоритма очень хорошо распараллеливаются.

Различия начинаются, если мы рассмотрим время, необходимое алгоритмам для архивации/разархивации. Так, фрактальный алгоритм сжимает в сотни и даже в тысячи раз дольше, чем JPEG . Распаковка изображения, наоборот, произойдет в 5-10 раз быстрее. Поэтому, если изображение будет сжато только один раз, а передано по сети и распаковано множество раз, то выгодней использовать фрактальный алгоритм.

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

Вытеснение JPEG фрактальным алгоритмом в повсеместном использовании произойдет еще не скоро (хотя бы в силу низкой скорости архивации последнего), однако в области приложений мультимедиа, в компьютерных играх его использование вполне оправдано.

Характеристики фрактального алгоритма

Коэффициенты компрессии: 2-2000 (Задается пользователем).

Класс изображений: Полноцветные 24 битные изображения или изображения в градациях серого без резких переходов цветов (фотографии). Желательно, чтобы области большей значимости (для восприятия) были более контрастными и резкими, а области меньшей значимости - неконтрастными и размытыми.

Симметричность: 100-100000.

Характерные особенности: Может свободно масштабировать изображение при разархивации, увеличивая его в 2-4 раза без появления "лестничного эффекта". При увеличении степени компрессии появляется "блочный" эффект на границах блоков в изображении.

Назад

К cодержанию

Вперёд

В декабре 1992 года, перед самым Рождеством, компания Microsoft выпустила свой новый компакт-диск Microsoft Encarta. С тех пор эта мультимедиа-энциклопедия, содержащая информацию о животных, цветах, деревьях и живописных местах, не покидает списки наиболее популярных энциклопедий на компакт-дисках. В недавнем опросе Microsoft Encarta опять заняла первое место, опередив ближайшего конкурента - Комптоновскую мультимедиа-энциклопедию. Причина подобной популярности кроется в удобстве использования, высоком качестве статей и, главное, в большом количестве материалов. На диск записано 7 часов звука, 100 анимационных роликов, примерно 800 масштабируемых карт, а также 7000.качественных фотографий. И все это - на одном диске! Напомним, что обычный компакт-диск в 650 Мбайт без использования компрессии может содержать либо 56 минут качественного звука, либо 1 час видео разрешения с разрешением 320х200 в формате MPEG-1, либо 700 полноцветных изображений размером 640х480. Чтобы разместить больше информации, необходимы достаточно эффективные алгоритмы архивации. Мы не будем останавливаться на методах архивации для видео и звука, рассмотрим историю фрактального сжатия графической информации. Рождение фрактальной геометрии обычно связывают с выходом в 1977 году книги Б. Мандельброта "Фрактальная геометрия природы". Одна из основных идей книги заключалась в том, что средствами традиционной геометрии (то есть, используя линии и поверхности), чрезвычайно сложно представить природные объекты. Фрактальная геометрия задает их очень просто. В 1981 году Джон Хатчинсон опубликовал статью "Фракталы и самоподобие", в которой была представлена теория построения фракталов с помощью системы итерируемых функций (IFS, Iterated Function System). Спустя четыре года появилась статья Майкла Барнсли и Стефана Демко, в которой приводилась уже достаточно стройная теория IFS. В 1987 году Барнсли основал Iterated Systems, компанию, основной деятельностью которой является создание новых алгоритмов и ПО с использованием фракталов. Всего через год, в 1988 году, он выпустил фундаментальный труд "Фракталы повсюду". Помимо описания IFS, в ней был получен результат, известный сейчас как Collage Theorem, который лежит в основе математического обоснования идеи фрактальной компрессии. Если построение изображений с помощью фрактальной математики можно назвать прямой задачей, то построение по изображению IFS - это обратная задача. Довольно долго она считалась неразрешимой. Первая статья об успехах Барнсли в области компрессии появилась в журнале BYTE в январе 1988 года. В ней не описывалось решение обратной задачи, но приводилось несколько изображений, сжатых с коэффициентом 1:10000, что было совершенно ошеломительно. Но практически сразу было отмечено, что несмотря на броские названия ("Темный лес", "Побережье Монтере", "Поле подсолнухов") изображения в действительности имели искусственную природу. Это, вызвало массу скептических замечаний, подогреваемых еще и заявлением Барнсли о том, что "среднее изображение требует для сжатия порядка 100 часов работы на мощной двухпроцессорной рабочей станции, причем с участием человека". Когда в 1991 году впервые была опубликована информация о возможностях фрактального сжатия, она наделала много шуму. Майкл Барнсли, один из разработчиков алгоритма, утверждал, что разработан способ нахождения коэффициентов фрактала, сколь угодно близкого к исходной картинке. Фракталы, эти красивые образы динамических систем, ранее использовались в машинной графике в основном для построения изображений неба, листьев, гор, травы. Красивое и, что важнее, достоверно имитирующее природный объект изображение могло быть задано всего несколькими коэффициентами. Неудивительно, что идея использовать фракталы при сжатии возникала и раньше, но считалось практически невозможным построить соответствующий алгоритм, который подбирал бы коэффициенты за приемлемое время. Итак, в 1991 году такой алгоритм был найден. Кроме того, в дальнейших его статьях декларировался ряд уникальных возможностей новой технологии. Так, фрактальный архиватор позволяет, например, при распаковке произвольно менять разрешение (размеры) изображения без появления эффекта зернистости. Более того, он распаковывает гораздо быстрее, чем ближайший конкурент, JPEG, и не только статическую графику, но и видео. В качестве примера приводилась программа, показывающая на машине с процессором i386/33 МГц цветной видеофильм с частотой 20 кадров в секунду без всякой аппаратной поддержки. В отличие от JPEG, в алгоритм изначально заложена возможность управлять степенью потерь на участках с максимальными потерями качества. Коэффициент сжатия изображений в целом примерно как у JPEG, но на некоторых реальных картинках достигалось сжатие в 10000 (!) раз. В 1992 году Арнауд Джеквин, один из сотрудников Барнсли, при защите диссертации описал практический алгоритм и опубликовал его. Этот алгоритм был крайне медленным и не претендовал на компрессию в 10000 раз (полноцветное 24-разрядное изображение с его помощью могло быть сжато без существенных потерь с коэффициентом 1:8 - 1:50); но его несомненным достоинством было то, что вмешательство человека удалось полностью исключить. Сегодня все известные программы фрактальной компрессии базируются на алгоритме Джеквина. В 1993 году вышел первый коммерческий продукт компании Iterated Systems. Ему было посвящено достаточно много публикаций, но о коммерческом успехе речь не шла, продукт был достаточно "сырой", компания не предпринимала никаких рекламных шагов, и приобрести программу было тяжело. В 1994 году Ювал Фишер были предоставил во всеобщее пользование исходные тексты исследовательской программы, в которой использовалось разложение изображения в квадродерево и были реализованы алгоритмы оптимизации поиска. Позднее появилось еще несколько исследовательских проектов, которые в качестве начального варианта программы использовали программу Фишера. В июле 1995 года в Тронхейме (Швеция) состоялась первая школа-конференция, посвященная фрактальной компрессии. Таким образом, многие важные события в области фрактальной компрессии произошли за последние три года: алгоритм только-только начинает развиваться. Как уже отмечалось, недостатком алгоритма фрактального сжатия является большое время кодирования. Решение этой проблемы в 1999 году предложил Д.С.Ватолин в своей статье "Использование ДКП для ускорения фрактального сжатия изображения". В работе рассматривается применение дискретного косинусоидального преобразования (ДКП) для ускорения работы фрактального алгоритма сжатия изображений. ДКП используется для разбиения всего множества блоков в изображении на 256 классов, что позволяет достичь почти 100-кратного ускорения работы алгоритма при приемлемых потерях в качестве изображения. В отличие от других работ, в данной статье детально описан разработанный алгоритм и полученные результаты.

Идея фрактального сжатия изображений зародилась относительно недавно – в 70-х годах прошлого века. Считается, что наиболее активно эта область начала развиваться после выхода книги Бенуа Мандельброта “Фрактальная геометрия природы”. Точного определения фрактальных объектов не существует, но принято считать, что фракталы – это объекты, обладающее свойством самоподобия, т. е. такие, где часть объекта выглядит как целый объект. Классическим примером фрактала является лист папоротника – так называемый папоротник Барнсли.

Идея фрактального сжатия основывается именно на свойстве самоподобия. Но существуют две проблемы: во – первых, ничто не гарантирует наличие свойства самоподобия у произвольного изображения; во – вторых, если даже объект и является фрактальным, как выделить ту область (или области), на основе которых сроится изображение. Следовательно, необходим некий теоретический базис, позволяющий решать эти проблемы. Такой базис существует и приведен ниже.

2.ТЕОРЕТИЧЕСКИЙ БАЗИС.

2.1ЧЕРНО – БЕЛЫЕ ИЗОБРАЖЕНИЯ.

2.1.1.Метрические пространства.

Метрикой d в пространстве X называется функция двух аргументов d(x,y) такая, что:

Тогда (X,d) – метрическое пространство. Последовательность точек называется сходящейся к точке x, если

Метрическое пространство, где каждая последовательность Коши сходится к точке этого пространства, называется полным метрическим пространством.

Точка x называется предельной точкой множества X, если существует последовательность точек из Х, сходящаяся к точке x.

Множество в метрическом пространстве называется замкнутым , если оно содержит все свои предельные точки. Множество B из (X, d) называется ограниченным , если существует точка x 0 из X и конечное значение R > 0, такие что для любого x из B выполняется условие d(x,x 0)

2.1.2 Компактные множества и пространство Хаусдорфа.

Множество C в метрическом пространстве (X, d) называется компактным , если каждая бесконечная последовательность из C имеет сходящуюся в С подпоследовательность.

Определим пространство Хаусдорфа.

Пусть (Х, d) – полное метрическое пространство. Определим H(X) как пространство, состоящее из компактных подмножеств множества Х. Т.е., каждая точка в H(X) – это компактное подмножество из Х.

Рассмотрим произвольную точку x из Х и произвольное B из H(X). Положим по определению

d(x, B) = min{d(x, y): y Î B}.

В силу компактности множества B минимум существует и ограничен. Рассмотрим теперь произвольные A,B Î H(X) и определим расстояние между ними как d(A, B) = max{d(x, B): x Î A} Компактность А обеспечивает существование и конечность максимума, но d(A, B) не задает метрику, т.к., в общем случае d(A, B) № d(B,A).

Определим новую меру расстояния h(A, B):

h(A, B) = max{d(A, B), d(B, A)}.

Теперь мы получили метрику в пространстве H(X). Метрика h называется метрикой Хаусдорфа , а метрическое пространство (H(X), h) – метрическим пространством Хаусдорфа .

2.1.3 Сжимающие отображения.

Преобразование f: X® X в метрическом пространстве (X, d) называется сжимающим отображением, если существует константа s, 0 £ s £ s*d(x 1 , x 2) для всех x 1 , x 2 Î X. Константа s называется коэффициентом сжатия отображения f. Точка х 0 называется неподвижной точкой (аттрактором) сжимающего отображения f, если f(x 0) = x 0 .

Теорема о сжимающих отображениях.

Пусть f: X® X сжимающее отображение на полном метрическом пространстве (X, d). Тогда f имеет одну и только одну неподвижную точку х 0 Î Х, и для любого х 0 Î Х f n (x)® x 0 .

2.1.4. Системы итерируемых функцмй.

Пусть {w 1 , … , w N } – конечный набор сжимающих отображений в (X, d) с коэффициентами сжатия s 1 , … , s N . Определим отображение W, на компактные множества точек из Х следующим образом:

W(B) = w 1 (B) И … И w N (B) для каждого B Î Н(Х).

Таким образом получили сжимающее отображение W: H(X) ® H(X) с коэффициентом сжатия

s = max{s 1 , …, s N }

Система итерируемых функций (IFS) состоит из полного метрического пространства (Х, d) и конечного множества сжимающих отображений w n:X ® X с коэффициентами сжатия s n . Коэффициент сжатия IFS определяется как s = max{s 1 , …, s N }.

IFS будем обозначать как {X, w n: n = 1,2,…, N}.

Теорема коллажа. Пусть L – точка пространства Н(Х). Задано некоторое e > 0. Выберем IFS {X, w n: n = 1,2,…,N} с коэффициентом сжатия s, 0 Ј e, Тогда h(L,A) Ј h(L, W(L))/(1-s) Ј e / (1-s) , Где A – аттрактор данной IFS.

2.1.5. Аффинные преобразования.

Аффинные преобразования – преобразования вида

Аффинные преобразования осуществляют сжатие/растяжение, перенос и поворот объекта.

2.1.5. Кодирование изображений.

Для получения коэффициентов нужного аффинного преобразования (в простейших случаях) достаточно решить 2 системы их 3-х уравнений с 3-мя неизвестными. В качестве примера рассмотрим построение Треугольника Серпинского. Это изображение описывается 3-мя преобразованиями:

1-е переводит точки {1,2,3} в точки {1,4,6};

2-e: {1,2,3} – в {4,2,5};

3-e: {1,2,3} – в {6,5,3},

(см. рисунок слева внизу).

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

2.1.7 Декодирование изображений.

2.1.7.1 Детерминистический алгоритм.

Детерминистический алгоритм для построения изображения, являющегося аттрактором IFS, напрямую применяет теорему о сжимающем отображении к любому начальному изображению B из H(X). Алгоритм строит последовательность изображений А n , многократно применяя IFS отображение W = {w 1, … , w N}. Если мы положим A 0 =B, то процесс может быть записан в виде A n = W(A n-1). По теореме о сжимающем отображении, A n сходится к аттрактору данной IFS.Ниже приведен пример работы детерминистического алгоритма – первые несколько итераций и конечное изображение, близкое к аттрактору.

2.1.7.2 Вероятностный алгоритм.

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

Более предпочтительным является использование вероятностного алгоритма: Вероятностный алгоритм связывает с каждым преобразованием w i из IFS вероятность p i . Эти вероятности определяют, насколько плотно каждая часть изображения – аттрактора покрыта точками.Вероятности преобразований можно вычислять как отношение модуля определителя основной матрицы преобразования к сумме модулей определителей основных матриц всех преобразований из IFS.

Алгоритм построения изображения:

1) For n = 1 to number_of_points_in_image do

2) (x,y) = random(B)

3) for I=1 to number_of_iterations do

4)   p = random(0,1)

5)   (x,y) = W k (x,y) //где вероятность р соответствует преобр-ю W k

Ниже приведен пример работы вероятностного алгоритма.

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

Действительно, пусть изображение имеет размеры n x m. Тогда общее число точек в нем N = n x m. Пусть число черных точек равно b, пусть число точек, используемых для построения изображения равно M. Вероятность того, что случайно выбранная точка окажется черной, равна b/N.

Вероятность того, что все выбранные точки окажутся черными, равна

Таким образом, для того, чтобы алгоритм сработал корректно с вероятностью большей, чем 1-e , где e О (0, 1), требуется выполнение неравенства log b/N e £ M

Рассмотрим пример. Пусть e = 0,01. Тогда для корректной работы вероятностного алгоритма при начальном изображении размера 300х300 с единственной белой точкой требуется

M > log 89999/90000 0.01 > 414463

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

2.1 ИЗОБРАЖЕНИЯ В ГРАДАЦИЯХ СЕРОГО.

2.2.1 Метрическое пространство.

Изображения в градациях серого можно рассматривать как вещественные функции f(x,y) , определенные на единичном квадрате I2=I x I..

На этих функциях можно ввести метрику следующим образом:

Пусть F – пространство вещественных функции, интегрируемых с квадратом на I2 с введенной метрикой. Тогда (F,d) – полное метрическое пространство и в нем выполняется теорема о сжимающих отображениях.

Поскольку работать мы будем с цифровыми изображениями, которые по сути являются матрицами фиксированных значений функции f(x,y), взятых в фиксированных точках (xi, yj), в этом случае можно пользоваться среднеквадратичной метрикой (rms):

2.2.2 PIFS и аффинные преобразования изображений в градациях серого.

В этом разделе используются IFS специального вида – системы итерируемых кусочно-определенных функций (PIFS) . PIFS состоит из полного метрического пространства X, набора подобластей D i из Х и набора сжимающих отображений w i: D i ® X, i=1, 2, … , n.

2.2.2.1 Аффинные преобразования.

Пусть w 0 i – аффинное преобразование, переводящее в себя единичный квадрат I2. W 0 i (x,y) = A i (x,y)T +b i , где А i – некоторая матрица размера 2х2, b i – вектор размера 2х1. Пусть D i – некоторая подобласть I2, и пусть R i – область значений преобразования w 0 i: w 0 i (D i) = R i . Определим отображение w i:F ® F, действующее на изображение f(x,y) :

(если w 0i - обратимо и (х,у) из R i).

Константа s i управляет контрастностью, o i управляет яркостью. w i – это базовое аффинное преобразование изображений в градациях серого.

2.2.2.2 Сжимающие отображения.

Для того, чтобы отображение wi было сжимающим потребуем выполнение условия

d 2 (w i (f), w i (g)) Ј s*d 2 (f, g).

Теорема о сжимающем отображении.

Пусть {R i } образуют покрытие множества I2, и при этом попарно не пересекаются. Пусть v i – PIFS вида v i:D i ® R i для некоторого множества доменных областей D i .Для каждого v i определим соответствующее сжатие w i на пространстве изображений F указанным выше способом. Пусть W(f(x,y)) = w i (f(x,y)) для (x ,y) из R i . Тогда W является сжатием на F, имеет единственную неподвижную точку f W и W n (f) ® f W при n ® Ґ для любых изображений f.

Теорема коллажа.

Пусть задано изображение в градациях серого f . Пусть W – сжимающее отображение такое, что d 2 (f,W(f)) Ј e . Тогда d 2 (f, f W) Ј e /(1-s), где s - коэффициент сжатия отображения W, f w - аттрактор PIFS.

2.2.3 Фрактальное кодирование.

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

Базовый алгоритм кодирования выглядит следующим образом:

1)Разбиваем исходное изображение на непересекающиеся ранговые блоки.

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

3)Для каждого рангового блока находим домен и соответствующее преобразование, которое наилучшим образом покрывает ранговый блок

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

2.2.4 Декодирование изображений.

Изображение декодируется путем итеративного применения преобразования W к произвольному начальному изображению g, где W(g(x,y)) = w i (g(x,y)), для (x,y) из R i . Если преобразования были выбраны корректны, то итерация W n (g) будет близка к исходному значению f при некотором приемлемом значении n. Важно, что в соответствии с теоремой о сжимающем отображении процесс будет сходиться независимо от выбора начального изображения. В качестве примера можно рассмотреть построение изображения «вид на УрГУ» на основе изображения «вид на УПИ». Слева направо – начальное изображение, 1-ая итерация, 2-ая итерация, аттрактор.

3.РЕАЛИЗАЦИЯ.

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

3.1 Программа Fract0.

BC/NW 2008, №1 (12): 4

BC/NW 2008, №2 (13): 11 .1

ИССЛЕДОВАНИЕ СПОСОБОВ УСКОРЕНИЯ МЕТОДА ФРАКТАЛЬНОГО СЖАТИЯ ИЗОБРАЖЕНИЙ

Калязин Н.А., Гольцов А.Г.

(Москва, Московский энергетический институт(технический университет), Россия)

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

Рассматриваемый метод имеет ряд преимуществ, среди которых:

- потенциально высокая степень сжатия,

- малое время распаковки,

- возможность восстанавливать лишь часть изображения,

- возможность восстанавливать изображение произвольного размера,

- широкие возможности в выборе параметров сжатия.

Метод ярко выраженно асимметричный. Это означает, что время сжатия существенно больше времени распаковки. Коэффициент симметричности метода (отношение времени сжатия ко времени распаковки) может достигать 1000-10000 . Таким образом, задача ускорения работы метода фрактального сжатия весьма актуальна.

Рассмотрим принципы, лежащие в основе метода.

Ключевым понятием метода является система итерируемых функций (IFS , Iterated Function System ), возможность применения которых к проблеме сжатия изображений впервые была исследована Майклом Барнсли .

IFS представляет собой набор трехмерных аффинных преобразований, переводящих одно изображение в другое. Преобразованию подвергаются точки в трехмерном пространстве (координата по оси X , координата по оси Y , яркость).

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

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

- области, в которые проецируются изображения, не пересекаются,

- линза может менять яркость и уменьшать контрастность,

- линза может зеркально отражать и поворачивать свой фрагмент изображения,

- линза должна масштабировать (причем только уменьшая) свой фрагмент изображения.

Рис.1. Машина Барнсли

Расставляя линзы и меняя их характеристики, можно управлять получаемым изображением. Одна итерация такой машины заключается в том, что по исходному изображению с помощью проектирования строится новое, после чего новое берется в качестве исходного. Утверждается, что в процессе итераций получится изображение, которое перестанет меняться. Оно будет зависеть только от расположения и характеристик линз, и не будет зависеть от исходной картинки. Это изображение называется «неподвижной точкой» или аттрактором данной IFS . Теория гарантирует наличие ровно одной неподвижной точки для каждой IFS .

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

Наиболее известны два изображения, полученных с помощью IFS : «треугольник Серпинского» (рис.2) и «папоротник Барнсли» (рис. 3).

Рис. 2. «Треугольник Серпинского»

Рис.3. «Папоротник Барнсли»

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

Фактически, фрактальная компрессия – это поиск самоподобных областей в изображении и определение для них параметров аффинных преобразований.

Рис. 4. Самоподобные области в изображениях

,(1)

где a , b , c , d , e , f – действительные числа и , называется двумерным аффинным преобразованием.

Преобразование , представимое в виде

,(2)

где a , b , c , d , e , f , q , r , s , t , u – действительные числа и , называется трехмерным аффинным преобразованием.

Пусть - преобразование в пространстве X . Точка , такая что , называется неподвижной точкой (аттрактором преобразования).

Преобразование в метрическом пространстве ( X , d ) называется сжимающим, если существует число s : , такое, что

.(3)

Теорема о сжимающем преобразовании.

Пусть - сжимающее преобразование в полном метрическом пространстве ( X , d ). Тогда существует в точности одна неподвижная точка этого преобразования и для любой точки последовательность сходится к .

Изображением называется функция S , определенная на единичном квадрате и принимающая значения от 0 до 1 или .

Пусть трехмерное аффинное преобразование записано в виде

(4)

и определено на компактном множестве декартова квадрата . Тогда оно переведет часть поверхности S в область , расположенную со сдвигом ( e , f ) и поворотом, заданным матрицей

.(5)

При этом если интерпретировать значения функции как яркость соответствующих точек, она уменьшится в p раз (преобразование должно быть сжимающим) и измениться на сдвиг q .

Конечная совокупность W сжимающих трехмерных аффинных преобразований , определенных на областях , таких, что и , называется системой итерируемых функций (IFS ) .

Системе итерируемых функций однозначно ставится в соответствие неподвижная точка – изображение. Таким образом, процесс компрессии заключается в поиске коэффициентов системы, а процесс декомпрессии – впроведений итераций системы до стабилизации полученного изображения (неподвижной точки IFS ).

В дальнейшем области будут именоваться блоками, а области - доменными (рис. 5).

Рис. 5. Перевод доменного блока в ранговый

Проиллюстрируем итерационный процесс восстановления ранее сжатого изображения (рис. 6).

Рис. 6. Исходное изображение

На каждой итерации производится применение IFS к текущему изображению. На рис. 7. показаны изображения, соответствующие каждой из 10-ти первых итераций (включая 0-ю).

Рис. 7. Процесс восстановления изображения

Для оценки качества восстановленного изображения применяется количественная оценка искажений, называемая пиковым соотношением сигнал/шум (PSNR – peak signal - to - noise ratio ) . Она рассчитывается по следующим формулам:

(6)

(7)

где и - количества столбов и строк, M – максимальное значение яркости пикселя, - пиксельное значение исходного изображения в i -ой строке и j -м столбце, а - пиксельное значение декодированного изображения, rms – погрешность, вычисленная по методу наименьших квадратов.

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

Опишем более подробно последовательность действий, выполняемых при сжатии изображения.

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

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

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

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

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

1. Все блоки являются квадратами со сторонами, параллельными сторонам изображения. Таким образом, изображение равномерной сеткой разбивается на набор ранговых блоков (рис. 8а).

2. При переводе доменного блока в ранговый уменьшение размеров производится ровно в 2 раза. Это существенно упрощает как компрессор, так и декомпрессор, так как задача масштабирования небольших блоков является нетривиальной.

3. Доменные блоки берутся «через точку» и по вертикали, и по горизонтали (рис. 8б).

4. При переводе доменного блока в ранговый поворот квадрата возможен только на 0, 90, 180 и 270 градусов. Также допускается зеркальное отражение. Общее число возможных преобразований (считая пустое) – 8.

Рис. 8. Принцип разбиения изображения на ранговые (а) и доменные блоки (б)

Степень подобия рангового и доменного блоков я вычислял при помощи следующей формулы:

,(8)

где r и d – соответственно значения яркостей пикселей рангового и доменного блоков, M – математическое ожидание значений яркостей соответствующего блока.

Эта формула основана на расчете коэффициента корреляции.

При восстановлении исходного изображения была использована формула

,(9)

где r – значение блока восстанавливаемого изображения, d – значение блока преобразовываемого изображения, p – изменение контраста блока, q – сдвиг по яркости блока.

Чтобы найти коэффициент p , я использовал квадратный корень из отношения дисперсий рангового и доменного блоков:

,(10)

где D – дисперсия значений яркости пикселей соответствующего блока; для тех доменных блоков, у которых msr > 0, и формулу

(11)

для тех доменных блоков, у которых msr < 0.

Чтобы найти коэффициент q , я использовал формулу:

.(12)

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

Предположим, что n x m - размер исходного изображения в пикселях, rsz – сторона рангового блока.

Тогда количество ранговых блоков в изображении будет

,(13)

а доменных (помня, что сторона доменного блока всегда вдвое больше стороны рангового)

.(14)

Таким образом, необходимо произвести rnum x dnum поблочных сопоставлений, что уже для изображения размером 512 x 512 и стороной рангового блока 8 пикселей составляет 251 920 384. Не стоит забывать, что в рассматриваемом нами алгоритме в каждом таком сопоставлении необходимо организовать цикл по всем пикселям блока для расчета математического ожидания и дисперсии. Более того, время, затрачиваемое на сжатие изображения в градациях серого, в простейшем случае утраивается, если речь идет о цветном изображений (так как для представления информации о яркости и цвете пикселя требуется как минимум три составляющих).

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

Существует два основных направления таких исследований :

Сокращение числапоблочных сопоставлений,

Ускорение сопоставлений путем повышений производительности вычислений.

К первому направлению относятся методы:

Выделение особенностей доменных блоков,

Классификация доменов.

Второе направление подразумевает использование высокопроизводительных систем и параллельных вычислений.

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

Основываясь на данной предпосылке, я попытался написать параллельную программу на языке Си с использованием библиотеки MPI (Message Passing Interface ). Для эксперимента использовался вычислительный кластер МЭИ, имеющий в своем составе 16 узлов, каждый из которых состоит из двух двухъядерных процессоров AMD Opteron x86_64 , 2.2 ГГц . Пиковая производительность кластера составляет 281.6 GFlop/s.

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

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

На рис. 9 представлены зависимости времени сжатия изображения от числа параллельных процессов (рис. 9а) и коэффициента ускорения от числа параллельных процессов (рис. 9б) для изображения с разрешением 256 x 256 пикселей. Из диаграммы на рис. 9а следует, что характер зависимости времени сжатия изображения от числа параллельных процессов не меняется при изменении значения стороны рангового блока. Из диаграммы на рис. 9б следует, коэффициент ускорения не зависит от значения стороны рангового блока и численно весьма близок числу параллельных процессов. Последнее наблюдение подтверждает тезис о том, что метод фрактального сжатия хорошо поддается распараллеливанию.

Рис. 9. Зависимости времени сжатия изображения от числа параллельных процессов (а) и коэффициента ускорения от числа параллельных процессов (б) для изображения с разрешением 256 x 256 пикселей. Линии на каждой из диаграмм соответствуют различным значениям стороны рангового блока

На рис. 10 представлены зависимости времени сжатия изображения от числа параллельных процессов (рис. 10а) и коэффициента ускорения от числа параллельных процессов (рис. 10б) при стороне рангового блока равной 4 пикселя. Из диаграммы на рис. 10а следует, что характер зависимости времени сжатия от числа процессов не меняется при изменении разрешения сжимаемого изображения. Из диаграммы на рис. 10б следует, что коэффициент ускорения не меняется и от разрешения сжимаемого изображения. Это говорит о том, что фрактальный метод сжатия одинаково хорошо распараллеливается для изображений всех размеров.

Рис. 10. Зависимости времени сжатия изображения от числа параллельных процессов (а) и коэффициента ускорения от числа параллельных процессов (б) при стороне рангового блока равной 4 пикселя. Линии на каждой из диаграмм соответствуют разрешениям исходного изображения

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

ЛИТЕРАТУРА

1. Ватолин Д. С. Тенденции развития алгоритмов сжатия статических растровых изображений // Открытые системы сегодня. - 1995. - № 8 (29). – с. 25–30.

2. Barnsley Michael F. Fractal Image Compression, AK Peters, Ltd., 1993.

3. Barnsley Michael F. Fractals Everywhere, second edition, Academic Press, San Diego , 1993.

4. Jacquin A. Image Coding Based on a Fractal Theory of Iterated Contractive Image Transformations // IEEE Transactions on Image Processing. 1992. Vol . 1, N 1. P . 18–30.

5. Ватолин Д., Ратушняк А., Смирнов М., Юкин В. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. – М.: ДИАЛОГ-МИФИ, 2003. – 384 с.

6. Уэльстид С. Фракталы и вейвлеты для сжатия изображений в действии: Учебное пособие. – М.: Издательство Триумф, 2003, - 320 с.

7. Информационно-аналитический центр parallel . ru , “Кластерные установки России и СНГ”,http://parallel.ru/russia/russian_clusters.html.

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

Фрактальное сжатие изображений.

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

Основа метода фрактального кодирования - это обнаружение самоподобных участков в изображении. Впервые возможность применения теории систем итерируемых функций к проблеме сжатия изображения была исследована Майклом Барнсли (англ. Michael Barnsley и Аланом Слоуном (англ. Alan Sloan).

Майкл Барнсли.

Они запатентовали свою идею в 1990 и 1991 годах. Фрактальная архивация основана на том, что с помощью коэффициентов системы итерируемых функций изображение представляется в более компактной форме. Наиболее наглядно этот процесс продемонстрировал сам Барнсли в своей книге "Фрактальное сжатие изображения". В ней введено понятие Фотокопировальной Машины, состоящей из экрана, на котором изображена исходная картинка, и системы линз, проецирующих изображение на другой экран. Каждая линза проецирует часть исходного изображения. Расставляя линзы и меняя их характеристики, можно управлять получаемым изображением. На линзы накладывается требование: они должны уменьшать в размерах проектируемую часть изображения. Кроме того, они могут менять яркость фрагмента и проецируют не круги, а области с произвольной границей.

Один шаг Машины состоит в построении с помощью проецирования по исходному изображению нового. Утверждается, что на некотором шаге изображение перестанет изменяться. Оно будет зависеть только от расположения и характеристик линз и не будет зависеть от исходной картинки. Это изображение называется неподвижной точкой или аттрактором данной СИФ. Collage Theorem (один из принципов фрактального сжатия) гарантирует наличие ровно одной неподвижной точки для каждой СИФ. Поскольку отображение линз является сжимающим, каждая линза в явном виде задает самоподобные области в нашем изображении. Благодаря самоподобию мы получаем сложную структуру изображения при любом увеличении.

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

Папоротник Барнсли (слева) и треугольник Серпинского (справа).

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

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

Применение фракталов в медицине.

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

Примеры фракталоподобных структур в организме человека: бронхи, сосуды, мышцы.

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

Пример кардиограммы.

Также фракталы могут использоваться (пока на стадии успешных экспериментов) в обработке медицинских рентгеновских изображений.

Пример рентгеновского снимка.

Рентгеновские снимки обработанные с помощью фрактальных алгоритмов дают более качественную картинку а соответственно и более качественную диагностику!!

Еще одна область в медицине где активно могут применятся фракталы - это гастроэнтерология. До настоящего времени и зачастую по сей день для диагностики заболеваний ЖКТ используются зондовые методы, которые связаны с необходимостью введения различной толщины зондов, что неприятно как для больного, так и для медперсонала. Кроме того, подобная техника проведения исследований значительно сужает объем их применения ввиду невозможности использования у соматически тяжелых больных, у больных в раннем послеоперационном периоде и т.п. Именно этой причиной объясняется не прекращающийся интерес физиологов и клиницистов к изучению моторно-эвакуаторной деятельности желудка и кишечника, а также к разработке новых методов, позволяющих адекватно, не только качественно, но и количественно оценивать интенсивность и характер моторной активности различных отделов ЖКТ. В качестве дополнительных методов исследования МЭФ применяются методы, основанные на измерении электрической активности органов. Исследования биоэлектрической активности органов ЖКТ положили начало созданию нового метода исследования в медицине, получившего название электрогастроэнтерография. Электрогастроэнтерография - метод исследования, позволяющий оценить биоэлектрическую активность желудка, двенадцатиперстной кишки и других отделов ЖКТ.

Пример электрогастроэнтерограммы.

Он основан на регистрации изменений электрического потенциала от органов ЖКТ, то есть снятие электрогастроэнтерограмм (ЭГЭГ). Применение фрактального анализа к получаемым биоэлектрическим сигналам от органов, позволяет эффективно судить о моторной функции органов и ЖКТ и успешно диагностировать различные заболевания.

Также ещё необходимо упомянуть о недавнем открытии американских учёных о том, что если составить карты адгезии (адгезия (от лат. adhaesio - прилипание) в физике - сцепление поверхностей разнородных твёрдых и/или жидких тел) поверхностей нормальных и раковых клеток, то окажутся что эти карты имею разную фрактальную размерность. Возможно это открытие в будущем поможет открыть новые эффективные методы диагностики и лечения онкологических заболеваний.

Карты адгезии поверхностей раковых и нормальных клеток

Применение фракталов в естественных науках.

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

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

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

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

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

Пример твёрдого тела - кристаллы.

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

Турбулентность.

Применение фракталов в телекоммуникациях.

В телекоммуникациях фракталы используются для создания фрактальных антенн. Фрактальные антенны – относительно новый класс электрически малых антенн (ЭМА), принципиально отличающийся своей геометрией от известных решений. По сути, традиционная эволюция антенн базировалась на евклидовой геометрии, оперирующей объектами целочисленной размерности (линия, круг, эллипс, параболоид и т. п.). Фрактальная антенны с удивительно компактным дизайном обеспечивает превосходную широкополосную производительность в маленьком форм-факторе. Достаточно компактны для установки или встраивания в различных местах, фрактальные антенны используются для морских, воздушных транспортных средств, или персональных устройств. На изображении выше пример фрактальной антенны.

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

Фракталы как элементы визуализации и спецэффектов.

Фракталы притягивают и завораживают своей красотой и бесконечностью. Именно поэтому (но и не только) фракталы очень часто используют для создания различного рода визуализаций, видеоинсталляций, создания спецэффектов в компьютерной графике и т.д.

Начнём пожалуй с игр. Сегодня в очень многих играх (пожалуй самый яркий пример Minecraft), где присутствуют разного рода природные ландшафты, так или иначе используются фрактальные алгоритмы. Этот способ довольно эффективно зарекомендовал себя. Дело в том, что настоящие природные объекты имеют в основе своей фрактальную структуру. Взяв это на вооружение, программисты предприняли попытку создать компьютерные ландшафты на основе фрактальных алгоритмов. Наблюдая сегодняшнее многообразие игр, где можно наблюдать красивые природные ландшафты, можно сделать вывод, о том, что это им с успехом удалось. Более того создано большое количество программ для генерации ландшафтов и пейзажей, основанных на фрактальных алгоритмах.

Моделирование ландшафта на основе фрактальных алгоритмов с помощью программы Fractal Landscapes.

Скриншот игры Minecraft.

Не обходится без фракталов и в кино. По сути в кино для создания различных фантастических пейзажей, как и в играх используются тот же принцип. Действительно, зачем каждый раз создавать новое дерево или гору, тратя на это кучу времени, когда всё это можно во много раз быстрее сделать с помощью компьютерных программ работающих на фрактальных алгоритмах. Интересный факт: в известном космическом хорроре Ридли Скотта "Чужой" в эпизоде когда команда спускается на поверхность планеты, монитор в корабле передаёт изображение поверхности планеты в виде сетки. Как раз таки это изображение и было создано при помощи фрактальной геометрии. Фрактальная геометрия позволяет художникам по спецэфффектам без труда создавать такие объекты как облака, дым, пламя, звёздное небо и т.д.

Теперь немного затронем тему фрактальной анимации. Фрактальные изображения, созданные в различных генераторах необычайно красивы. Что уж тогда говорить о фрактальной анимации, это действительное потрясающее зрелище. В первую очередь здесь стоит упомянуть о ресурсе Electric sheep. Electric sheep - ресурс использующий распределённые вычисления для создания фрактальной анимации основанной на алгоритме fractal flame (разработан Скотом Дрейвсом). Проще говоря на ваш компьютер устанавливается программное обеспечение, которое использует вашу машину для вычисления и рендера фрактальной анимации, одновременно с этим загружая и демонстрируя вам уже готовую фрактальную анимацию в виде так называемых "живых" обоев. При этом эти самые обои сохраняются на компьютере в определённой папке и их можно оттуда вытащить, чтобы затем использовать для своих целей, например в видеомонтаже (правда длина роликов коротковата - 5 секунд). Но имея в своём распоряжении программу Апофизис и скрипт к ней Apophymator, вы сможете без особого труда создавать свою анимацию (благо уроков по этой теме в сети множество) сколь угодно длинную, главное чтобы ваша машина была достаточно мощной.

Скриншоты анимации Electric sheep:

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

Фрактальную анимацию в качестве визуализации используют разработчики программ напрямую не относящиеся к фракталогенераторам. К примеру хорошо известный проигрыватель Winamp имеет в своём наборе большое количество визуализаций (плагин milkdrop) в которых явно прослеживаются элементы фракталов (например анимированное множество Жюлиа). Скриншоты визуализаций в плагине milkdrop для проигрывателя Winamp:

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

Оригинал статьи можно прочесть в мартовском номере журнала Компьюарт.