Реферат - Теория фракталов

Подождите немного. Документ загружается.

Глава 2. Применение теории фракталов в информатике

Область применения фракталов достаточно широка и разнообразна, она

охватывает такие сферы человеческой деятельности, как естествознание,

литература, радиотехника, информатика и др. [7].

Фракталы широко применяются в компьютерной графике для

построения изображений природных объектов, таких, как деревья, кусты,

горные ландшафты, поверхности морей и т.д. Существует множество

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

Существуют алгоритмы сжатия изображения с помощью фракталов.

Они основаны на идее о том, что вместо самого изображения можно хранить

сжимающее отображение, для которого это изображение (или некоторое

близкое к нему) является неподвижной точкой. Система назначения IP-

адресов в сети Netsukuku использует принцип фрактального сжатия

информации для компактного сохранения информации об узлах сети.

Каждый узел сети Netsukuku хранит всего 4 Кб информации о состоянии

соседних узлов, при этом любой новый узел подключается к общей сети без

необходимости в центральном регулировании раздачи IP-адресов, что,

например, характерно для сети Интернет. Таким образом, принцип

фрактального сжатия информации гарантирует полностью

децентрализованную, а следовательно, максимально устойчивую работу всей

сети [7].

Алгоритмы фрактального сжатия информации и их программная

реализация достаточно подробно рассмотрены С. Уэлстидом [6]. Краткое

описание представлено ниже [1].

Основа метода фрактального кодирования — это обнаружение

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

теории систем итерируемых функций (англ. Iterated Function System, сокр.

IFS) к проблеме сжатия изображения была исследована Майклом Барнсли и

Аланом Слоуном в начале 80-х гг. прошлого века. Они запатентовали свою

идею в 1990 и 1991 гг. А. Жакен представил метод фрактального

кодирования, в котором используются системы доменных и ранговых блоков

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

Этот подход стал основой для большинства методов фрактального

кодирования, применяемых сегодня. Он был усовершенствован Ювалом

Фишером и рядом других исследователей.

В соответствии с данным методом изображение разбивается на

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

subimages) и определяется множество перекрывающихся доменных

подизображений (англ. domain subimages). Для каждого рангового блока

алгоритм кодирования находит наиболее подходящий доменный блок и

аффинное преобразование, которое переводит этот доменный блок в данный

ранговый блок. Структура изображения отображается в систему ранговых

блоков, доменных блоков и преобразований.

Идея заключается в следующем: предположим что исходное

изображение является неподвижной точкой некоего сжимающего

отображения. Тогда можно вместо самого изображения запомнить каким-

либо образом это отображение, а для восстановления достаточно

многократно применить это отображение к любому стартовому

изображению.

По теореме Банаха, такие итерации всегда приводят к неподвижной

точке, то есть к исходному изображению. На практике вся трудность

заключается в отыскании по изображению наиболее подходящего

сжимающего отображения и в компактном его хранении. Как правило,

алгоритмы поиска отображения (то есть алгоритмы сжатия) в значительной

степени переборные и требуют больших вычислительных затрат. В то же

время, алгоритмы восстановления достаточно эффективны и быстры.

Вкратце метод, предложенный Барнсли, можно описать следующим

образом. Изображение кодируется несколькими простыми преобразованиями

(в нашем случае аффинными), то есть определяется коэффициентами этих

преобразований (в нашем случае A, B, C, D, E, F).

Например, изображение кривой Коха можно закодировать четырьмя

аффинными преобразованиями, мы однозначно определим его с помощью

всего 24-х коэффициентов.

Далее, поставив чёрную точку в любой точке картинки, мы будем

применять наши преобразования в случайном порядке некоторое (достаточно

большое) число раз (этот метод ещё называют фрактальным пинг-понгом).

В результате точка обязательно перейдёт куда-то внутрь чёрной

области на исходном изображении. Проделав такую операцию много раз мы

заполним все чёрное пространство, тем самым восстановив картинку.

В качестве примера программной реализации приведем листинг

фрагмента программы итерационного построения листа папоротника на

языке Си [6].

iter = 0;

do {

// If clear_scr flag is Bet, clear the window between

// iterations. The structures gr_setup and gr contain

// window graphics parameters,

if (clear^Bcr)

draw__border (gr__setup, gr, CLEAR_WINDOW) ;

iter++/

for (i=l;i<=nrows;i++)

for (j=l;j<=ncols;j++)

if (old__image[i] [ j] ) (

// Map the old image array to the virtual X-Y

// plane:

// Map 1 to x min and ncols to x max:

х = ((float) (3-D/ (float) (ncols-1)) *x_range +

gr__setup->x_min;

// Map nrows to yjmin and 1 to y_max:

у = ((float)(nrows - i)/

(float)(nrows-1))*y_range +

gr_se tup->y_jniin;

// Loop through all the transformations

// (no_of_fns) in the IFS:

for (k = l;k<=no_of_fns;k++) (

ifs = *(coeff_struct *) (coeff_list~>at(k)) ;

xnew = ifs.a*x + ifs.b*y + ifs.e;

ynew = ifs.c*x + ifs.d*y + ifs.f;

if (fabs(xnew) + fabs(ynew) > IFS_TOO_BIG) {

message_puts (MBJSXCLAIM,"IFSPROC",

"This system diverges I\r\n"

"Check to see that all transformations\r\n"

"are contractions.");

goto exit_proc;

} // end if

// Map the virtual X-Y plane back to the new

// image array:

// Map x_min to 1 and xjnax to ncols:

col = ((xnew - gr_setup->x_jniin) /x^range) * (ncols-1) + 1;

/ / Map y__min to nrows and y__max to 1:

row = nrows -((ynew - gr_setup->y_jnin)

/y_range)*(nrows-1)/

new__image[row] [col] = 1;

// Plot the X-Y point in the window in color:

xy__to__window_color (gr,xnew,ynew, rgb_ifs_color (ifs));

} // end k

} // end if, i, j

// Move new_image to old_image, and reset new_image:

for (i=l;i<=nrows;i++)

for (j=l;j<=ncols;j++) {

old_image[i][j] = new_image[i][j];

new_image[i][j] =0;

)

} while (! terminating_jproc ()) ;

Для хранения двоичных изображений, получаемых в результате

итераций, введены два массива - old_image и new__image. Каждый из этих

массивов состоит из единиц и нулей, где единица означает пиксель

двоичного изображения. Каждый из этих массивов размещается динамически

чтобы соответствовать размерам экрана: nrows  ncols. Чтобы обрабатывать

эти изображения с помощью IFS, нам необходимо перейти от массива

изображения к плоскости X-Y. Эта плоскость - не что иное, как сетка X-Y.

Рис. 5. Представление взаимоотношений между массивом изображения программе и на

виртуальной Х-У плоскости, где действует IFS. Массив изображения состоит из единиц и нулей,

где единица означает точку двоичного изображения. Каждый ненулевой элемент «старого

изображения» отображается на плоскость Х-У. IFS действует на эту точку, генерируя, в

общем случае, N новых точек. Эти новые точки отображаются затем в массив «нового

изображения». В завершение каждой итерации массив «нового изображения» переписывается в

массив «старого изображения» для подготовки к следующей итерации.

На рисунке 5 показано, как работает итерационный процесс. Каждый

ненулевой элемент массива oid_image отображается в точку с координатами

(х, у) на плоскости X-Y. Затем над этой точкой выполняется каждое из

аффинных преобразований из IFS. Число функций преобразования

обозначено в программе как no__of_fns. Идентификатор coeff_list - это

список указателей, каждый из которых указывает на структуру coeff_struct,

которая содержит аффинные коэффициенты. Новая точка (xnew,ynew)

строится на экране дисплея с помощью функции xy__to_window_color. Цвет

точки был выбран, когда задавалось преобразование. Затем точка

(xnew,ynew) отображается обратно в массив с именем new_image. Для

завершения итерации массив new__image копируется в массив old_image,

элементы массива new__image приравниваются нулю, и начинается новая

итерация. Итерации прекращаются, когда пользователь вызывает процедуру

termininating_proc, которая фиксирует щелчки мыши или нажатие клавиши

Esc. Результат применения алгоритма представлен на рисунке 6.

Рис. 6. Детерминистический алгоритм, примененный к IFS папоротника с четырьмя аффинными

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

после:(а) 2 итераций, (b) 3 итераций, (с) 10 итераций, (d) 30 итераций.

Основная сложность фрактального сжатия заключается в том, что для

нахождения соответствующих доменных блоков вообще говоря требуется

полный перебор. Поскольку при этом переборе каждый раз должны

сравниваться два массива, данная операция получается достаточно

длительной. Сравнительно простым преобразованием её можно свести к

операции скалярного произведения двух массивов, однако даже скалярное

произведение вычисляется сравнительно длительное время.

На данный момент известно достаточно большое количество

алгоритмов оптимизации перебора, возникающего при фрактальном сжатии,

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

этой проблеме, и во время активных исследований (1992—1996 года)

выходило до 300 статей в год. Наиболее эффективными оказались два

направления исследований: метод выделения особенностей (feature

extraction) и метод классификации доменов (classification of domains) [1].

Заключение

Исследование теории фракталов позволяет сделать следующие выводы.

1. Основным понятием теории фракталов является понятие фрактала,

которое не имеет однозначного математического определения, его подвиды

определяются через метод построения фрактала. С этой точки зрения

выделяют конструктивные (фрактал как геометрическая фигура) и

динамические (фрактал как множество точек) фракталы.

2. Несмотря на разницу в определениях, любой фрактал

характеризуется тремя параметрами: нерегулярность, самоподобие, дробная

метрическая размерность (либо метрическая размерность выше

топологической).

3. Фракталы имеют несложную программную реализацию, основанную

на итерационных алгоритмах: в основе построения конструктивных

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

(аффинных) преобразованиях, в основе построения динамических фракталов

– вероятностный метод.

4. Применение фракталов в информатике осуществляется главным

образом для сжатия информации в целях увеличения скорости ее передачи в

компьютерных сетях и уменьшения места на диске, отводимого под хранение

данных. Другим популярным направлением использования фракталов

является компьютерная графика.

Библиография

1. Алгоритм фрактального сжатия // Википедия, версия 05.11.2010. Режим

доступа: http://ru.wikipedia.org/wiki/Алгоритм_фрактального_сжатия.

2. Кроновер, Р.М. Фракталы и хаос в динамических системах. Основы

теории. М.: Постмаркет, 2000. – 352 с.

3. Мандельброт, Б. Фрактальная геометрия природы. М.: Институт

компьютерных исследований, 2002. – 656 с.

4. Морозов, А.Д. Введение в теорию фракталов. – Москва-Ижевск:

Институт компьютерных исследований, 2002. – 160 с.

5. Ногих С.Р., Дурнин М.К., Шестопалов А.В. Процессовые фракталы и

фрактально подобные процессы / Моделирование процессов в

синергетических системах. / Международная конференция "Байкальские

чтения II по моделированию процессов в синергетических системах" (18-

23 июля 2002, ИВТ, Максимиха - восточное побережье озера Байкал). -

Улан-Удэ - Томск: Изд-во ТГУ, 2002. - с.277-279.

6. Уэлстид, С. Фракталы и вейвлеты для сжатия изображений в действии:

Учебное пособ. – М.: Издательство «Триумф», 2003. – 320 с.: ил.

7. Фрактал // Википедия, версия 23.04.2011. Режим доступа:

http://ru.wikipedia.org/wiki/Фрактал.

8. Фракталы и теория бифуркации. Режим доступа:

http://fractbifur.narod.ru/html/index1.html.

9. Шредер, М. Фракталы, хаос, степенные законы. Миниатюры из

бесконечного рая. – Ижевск: НИЦ «Регулярная и хаотическая динамика»,

2001. – 528 с.