Системи Итеративни Функции (Iterated Functions System - IFS)

Един от най-мощните начини да се изобразяват фрактали, метод намерил приложение и в други области е метода на системите итеративни функции (IFS).

IFS представляват система от определен клас функции, преобразуващи едно многомерно множество в друго. Най-простата IFS се състои от афинни трансформации за равнина:

x' = x * а + y * b + e

y' = x * c + y * d + f

Тази система може да се представи и матрично по този начин:

Афинни трансформации

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

Намаляващи трансфомации. Атрактори

Мащабиращите трансформации са обикновено намаляващи, т.е. точките ще се сближават и формите ще стават по-малки. Така един IFS фрактал ще е съставен от по-малки копия на себе си, които от своя страна, ще се състоят от копия на себе си и т.н. и този начин на построяване на фрактала ще осигури неговото основно свойство - самоподобието.

За трансформация, която намалява разстоянието между точките повече от 1 път т.е. кофициентът на мащабиране е по-малък от 1, съгласно теоремата на Банах, в намаленото копие съществува неподвижна точка, и то само една. Тази точка се нарича още атрактор.Теоремата е наречена в чест на полския математик Стефан Банах, установил и доказал това твърдение през 1922 г. Системите итеративни функции са пример за прилагането на тази теория.

Iterated Systems Inc

Теорията е разработена математически от Джон Хътчинсън (John Hutchinson), но методът става популярен, след като през 1988 г. британският математик Майкъл Барнсли (Michael Barnsley) вижда в този метод потенциал за свиване(архивиране) и съхранение на графична информация. Майкъл Барнсли и Алан Слоун (Alan Sloan) основават корпорацията Iterated Systems Inc. през 1987 г., която получава над 20 патента, свързани с фракталната компресия.

Майкъл Барнсли нарекъл своя метод метод на фракталното архивиране на информацията и създал алгоритъм, който може да компресира информацията 500-1000 пъти. Методът е най-подходящ за текстури и естествени изображения заради факта, че части от изображението често приличат на други части от същото изображение.

Аспирантът на Барнсли, Арно Жакен (Arnaud Jacquin) реализира първия автоматичен алгоритъм, който разделя изображението на отделни блокове области или домейни(domain blocks) и генерира по-малки блокове (range subimage blocks).

Информацията за една трансформация се събира на няколко байта, докато изображението, създадено с IFS, може да отнеме и няколко мегабайта.

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

В момента две фирми, Total Multimedia Inc. и Dimension твърдят, че притежават изключителни права за технологията итеративна видео компресия, но няма все още работещ продукт.

Описание

Накратко методът може да се опише така: Изображението се кодира с няколкопрости афинни трансформации, т.е. с коефициентите на тези трансформации.

Например, закодирайки някакво изображение с две афинни трансформации, ние еднозначно го определяме с помощта на 12-те коефициента. Ако се зададе някаква начална точка (например x=0, y=0) и стартираме итерационния процес, то след първата итерация ще получим две точки, след втората - четири, след третата - осем и т.н. След няколко десетки итерации съвкупността от получените точки ще описва закодираното изображение.

Но проблемът се състои в това, че понякога е трудно да се намерят коефициентите на IFS.

Като пример за използване на IFS за построяване на фрактални структури, да разгледаме няколко известни фрактални криви. Ще отделим в техните структури подобните части и за всяка от тях ще изчислим коефициентите на афинно преобразование. В афинния колаж ще бъдат включени толкова афинни преобразования, колкото са частите, подобни на цялото изображение.

Дракон на Хартер-Хейтуел

Да построим IFS за "дракона" на Хартер-Хейтуел. За тази цел да разположим първото поколение на този фрактал в координатната мрежа на дисплея 640 x 350 . Да обозначим точките получената начупена линия A, B, C. По правилата за построение, този фрактал има две части, подобни на цялото - на схемата вдясно това са начупените линии ADB и BEC. Знаейки координатите на краищата на тези отсечки, може да се изчислят коефициентите на две афинни преобразования, превръщащи начупената линия ABC в ADB и BEC:

x' = -0.5*x -0.5*y + 490 y' = 0.5*x -0.5*y + 120 x' = 0.5*x -0.5*y + 340 y' = 0.5*x +0.5*y - 110

Задавайки начална стартова точка (например x=0 y=0) и въздействайки итерационно на нея с помощта на тази IFS, можем да проследим развитието на фракталната структура, така добре известна ни от книгата на Майкъл Крайтън "Юрски парк", или т.н. "дракон" на Хартер-Хейтуей. Неговия код (кратко описание) е набор от коефициенти на две афинни преобразования.

0 1 2 3 4 5 6 7 8 9 10 11

Крива на Кох

По същия начин, може да се изгради IFS за кривата на Кох. Тази крива има четири части и са необходими са 4 трансформации..

x' = 0.333*x + 13.333
y' = 0.333*y + 200

x' = 0.333*x + 413.333
y' = 0.333*y + 200

x' = 0.167*x + 0.289*y + 130
y' = -0.289*x + 0.167*y + 256

x' = 0.167*x - 0.289*y + 403
y' = 0.289*x + 0.167*y + 71

След 1000 итерации кривата придобива вида: 

Папрат на Барнсли

Един от най-впечатляващите примери за приложението на IFS, разбира се, е кодът на папрат, разработен от Барнсли с четири намаляващи афинни трансформации, като резултатът поразително наподобява листата на растението.

Майкъл Барнсли е използвал фрактали за моделиране на разнообразна гама от явления в науката и технологиите, но най-изумителни са растителните структури. Опитът му да имитира природата с математически модели става източник на вдъхновение за мнозина художници.

Коефициентите за изграждане на изображението на папрат са в следната таблица:

a	b	c	d	e	f	p	Елемент
0	0	0	0.16	0	0	0.01	Стъбло
0.85	0.04	-0.04	0.85	0	1.6	0.85	Редици малки листенца
0.2	-0.26	0.23	0.22	0	1.6	0.07	Най-голямо лява листо
-0.15	0.28	0.26	0.24	0	0.44	0.07	Най-голямо дясна листо

В таблицата, колоните "а" до "е" са коефициентите на уравнението, а "р" представлява коефициентът на вероятност за всяка трансформация, управляваща водещ елемент на изображението на обекта.

Началната форма може да бъде произволна

Ако трансформацията е намаляваща, тя ще сближава все повече точките и след безкрайно много итерации, докато изображението ще се доближи максимално до атрактора. По тази начин става без значение каква е началната форма. За да се убедите, че тя може да е произволна, разгледайте анимациите:

1	2	3	4	5	6	7	8

1	2	3	4	5	6	7	8

Изображението на папрат можем да получим и от итерации на правоъгълници. Резултатът от всяко преобразуване се получава от четири редукции и четири трансформации на предшестващото изображение. Едно преобразувани осъществява особено рязка редукция, в резултат на която изображението се смачква във вертикална линия, тази линия образува стъбло.

1	2	3	4	5

Виждате, че дори да започваме от една и съща фигура, резултатите са съвсем различни, а ако започваме с различни фигури, можем да получим един и същ резултат. Това означава, че първичната фигура е без значение, определящи са самите афинни трансформации.

 Ако започнем, да речем с правоъгълник, след всяка стъпка (итерация) броят на правоъгълниците ще се увеличи четири пъти, а след m преобразувания ще станат 4^m броя. След четири итерации на оригиналното изображение (в този случай правоъгълник) той все още се различава. След известно количество итерации, фигурата намалява и се насочва бързо към атрактора. За да стане правоъгълникът достатъчно малък и да се забележи основната форма на изображението (в случая папрат), трябва да се направят поне около 50 итерации, а следователно, да се изчислят и нарисуват 4⁵⁰ (около 10³⁰) правоъгълници. Това са твърде много правоъгълници и твърде много време за изчисления, а за да се стигне до атрактора има по-добър начин.

Игра на хаос

Майкъл Барнсли е изобретил алгоритъм, наречен "игра на хаос", който се състои в следното:

1	2	3	4	5	6	7	8	9

Нека приложим метода върху триъгълника на Серпински. По-просто е да се използват точки. Така се изчислява много по-лесно, защото се трансформира само една точка от триъгълника. Ще започнем с един въображаем триъгълник и да номерираме върховете му с 1, 2, и 3. Избираме произволно място. Генерираме произволни число между 1 и 3. Следващата точка е средата между първата точка и генерирания случайно номер на върха на триъгълника. Продължаваме да генерираме случайни числа и да изобразяваме средите. След около хиляда итерации, ще видим триъгълника на Серпински.

Сега да опитаме същия метод за листото папрат на Барнсли. Играта започва с избор на произволна точка от равнината. Тогава избираме произволно число от 1 до 4 или все едно, че хвърляме 4-странно зарче. Всяка страна съответства на една от четирите трансформации, които определят формата на листо папрат и така на случаен принцип избираме една от трансформациите { f₁, f₂, f₃, f₄}, която след това се прилага на избраната точка от равнината и тя се премества на новото си място. Повтаряме операцията отново спрямо точката, получена на предишната стъпка и т.н. Точките, получени от последователното хвърляне на зара, скоро ще започнат да оформят крайния образ. Но пак е необходимо твърде много време.

Алгоритъмът

И така, да опишем алгоритъма накратко:

1. Избираме общия брой итерации, които ще се изпълняват и го означаваме с m. .
2. Определяме общия брой възможни трансформации като k .
3. Обозначаваме всяка трансформация с цяло число от 1 до k .
4. Избираме произволна точка и я означаваме с a.
5. Генерираме случайно число от 1 до k.
6. Намираме стойността на новата точка a= f_k(a) като резултат от случайно избраната функция под номер k, f_k с аргумент произволната точка a от стъпка 4.
7. Построяваме a.
8. Връщаме се на стъпка 5, повтаряйки стъпки от 5 до 8 m пъти.

Прилагайки този алгоритъм на папратта на Барнсли, получаваме:

1	2	3	4	5	6	7	8	9	10	11	12

Коефициентите на вероятност

В този пример всяка функция  f_k като (k е една от възможните функции, има еднаква вероятност да се случи. Крайните изображение може да се получават много по-бързо, ако за всяка  f_k се прикрепи съответна вероятност P_k, като по този начин едни функции  f_k ще станат по-вероятни и ще се падат по-често от други. Така процесът се ускорява и всички фрагменти на изображението се появяват еднакво бързо. Тези коефициенти на вероятност са в таблицата на коефициентите за папратта на Барнсли.

Основни понятия и лексика

• Афинни (линейни) трансформации
• Системи Итеративни Функции (Iterated Functions System - IFS)
• Атрактори
• Игра на хаос
• Коефициенти на вероятност
• Фрактали
• Дракон на Хартер-Хейтуел
• Крива на Кох
• Папрат на Барнсли
• Джон Хътчинсън
• Майкъл Барнсли

Продължение:

Алгебрични (динамични, нелинейни) фрактали

Източници:

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

Fractal Geometry, Yale University, Michael Frame, Benoit Mandelbrot (1924-2010), and Nial Neger

Введение во фракталы, Шабаршин А.А.

Fractals: Useful Beauty (General Introduction to Fractal Geometry)

Язык фракталов, ХАРТМУТ ЮРГЕНС, ХАЙНЦ-ОТТО ПАЙТГЕН, ДИТМАР ЗАУПЕ

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