Геометрія фракталів

Размещено на http://www.allbest.ru/

Дніпропетровський ліцей інформаційних технологій при

Дніпропетровському національному університеті

Кафедра: математики

КУРСОВА РОБОТА

Тема: Геометрія фракталів

Виконав:

Ліцеїст 10-Г класу

Шинкаренко Віталій Русланович

Дніпро 2020

Зміст

1. Вступ

1.1 Фрактал. Історія його виникнення

2. Основна частина

2.1 Класифікація фракталів

2.1.1 Геометричні фрактали

2.1.2 Алгебраїчні фрактали

2.1.3 Стохастичні фрактали

2.2 Типи самоподібності у фракталах

2.3 Розмірність фракталів

2.4 Використання фракталів

1.Вступ

1.1 Фрактал. Історія його виникнення

Все, що створено людиною, обмежено площинами. Коли зустрічається об'єкт у природі, то спочатку можна побачити, що описати його форму можна лише наближено й допоможуть в цьому фрактали. Де закінчуються правильні форми Евклідової геометрії, там зустрічаються фрактали.

Фрактамл (лат. fractus -- подрібнений, дробовий) - нерегулярна, самоподібна структура. У широкому розумінні фрактал означає фігуру, малі частини якої в довільному збільшенні є подібними до неї самої (мал.1).

Об'єкти, які тепер називаються фракталами, досліджувались задовго до того, як їм було дано таку назву. В етноматематиці, наприклад в роботах Рона Еглаша "Африканські Фрактали", задокументовано поширені фрактальні геометричні фігури в мистецтві тубільців. У 1525 році німецький митець Альбрехт Дюрер опублікував свою працю "Керівництво Художника", один із розділів якої має назву "Черепичні шаблони, утворені пентагонами". Пентагон Дюрера багато в чому є схожим на килим Серпінського, але замість квадратів використовуються п'ятикутники. Джексон Поллок (американський експресіоніст 50-тих років) малював об'єкти, дуже схожі на фрактали.

Ідею "рекурсивної самоподібності" було висунуто філософом Лейбніцом, який також розробив багато з деталей цієї ідеї. У 1872 Карл Веєрштрасс знайшов приклад функції з неінтуітивною особливістю, скрізь неперервної, але ніде недиференційованої -- графік цієї функції тепер називався б фракталом. У 1904 Хельга Фон Кох, незадоволений занадто абстрактним та аналітичним означенням Веєрштрасса, розробив більш геометричне означення схожої функції, яка тепер має назву сніжинки Коха. Ідею самоподібних кривих, котрі складаються із частин, схожих на ціле, було далі розвинено Полем П'єром Леві, який у своїй роботі "Криві та поверхні на площині та у просторі", виданій 1938 року, описав нову фрактальну криву, відому тепер як Крива Леві (мал.2 а, б, в).

Ґеорг Кантор навів приклади підмножин дійсних чисел із незвичними властивостями -- ці множини Кантора тепер також визнаються як фрактали.

Ітераційні функції на комплексній площині досліджувались в кінці XIX та на початку XX століття Анрі Пуанкаре, Феліксом Кляйном, П'єром Фату та Ґастоном Жюліа. Проте за браком сучасної комп'ютерної графіки у них забракло засобів відобразити красу багатьох із відкритих ними об'єктів.

У 1975 році Мандельброт використав слово фрактал як назву для об'єктів, розмірність Хаусдорфа яких є більшою за топологічну розмірність, наприклад Крива Хильберта (мал.3 а,б,в,г).

2. Основна частина

2.1 Класифікація фракталів

2.1.1 Геометричні фрактали

Фрактали цього класу самі наочні. У двомірному випадку їх отримують за допомогою деякої ламаної (або поверхні в тривимірному випадку), званої генератором. За один крок алгоритму кожен з відрізків, що становлять ламану, замінюється на ламану-генератор, у відповідному масштабі. В результаті нескінченного повторення цієї процедури, виходить геометричний фрактал. . Побудова триадной кривої Кох. Розглянемо один з таких фрактальних об'єктів - триадную криву Кох .

Побудова кривої починається з відрізка одиничної довжини - це 0-е покоління кривої Кох. Далі кожна ланка (в нульовому поколінні один відрізок) замінюється на який утворює елемент, позначений на рис.1 через n = 1. В результаті такої заміни виходить наступне покоління кривої Кох. У 1-му поколінні - це крива з чотирьох прямолінійних ланок, кожне довжиною по 1/3. Для отримання 3-го покоління проробляються ті ж дії - кожна ланка замінюється на зменшений утворює елемент. Отже, для отримання кожного наступного покоління, все ланки попереднього покоління необхідно замінити зменшеним утворюючим елементом. Крива n-го покоління при будь-якому кінцевому n називається предфракталом.

На рис.1 представлені п'ять поколінь кривої. При n прагне до нескінченності крива Кох стає фрактальним об'єктом.

Алгебраїчні фрактали

Це найбільша група фракталів. Отримують їх за допомогою нелінійних процесів в n-мірних просторах. Найбільш вивчені двомірні процеси. Інтерпретуючи нелінійний ітераційний процес, як дискретну динамічну систему, можна користуватись термінологією теорії цих систем: фазовий портрет, сталий процес, аттрактор і т.д.

Відомо, що нелінійні динамічні системи мають декількома стійкими станами. Той стан, в якому опинилася динамічна система після деякого числа ітерацій, залежить від її початкового стану. Тому кожне стійкий стан (або як кажуть - аттрактор) володіє деякою областю початкових станів, з яких система обов'язково потрапить в розглянуті кінцеві стану. Таким чином фазовий простір системи розбивається на області тяжіння аттракторов. Якщо фазовим є двомірний простір, то фарбуючи області тяжіння різними кольорами, можна отримати колірний фазовий портрет цієї системи (ітераційного процесу). Змінюючи алгоритм вибору кольору, можна отримати складні фрактальні картини з химерними кольоровими візерунками. Несподіванкою для математиків стала можливість за допомогою примітивних алгоритмів породжувати дуже складні нетривіальні структури.

2.12 Стохастичні фрактали

Ще одним відомим класом фракталів є стохастичні фрактали, які виходять в тому випадку, якщо в ітераційне процесі випадковим чином змінювати будь-які його параметри. При цьому виходять об'єкти дуже схожі на природні - несиметричні дерева, порізані берегові лінії і т.д. Двовимірні стохастичні фрактали використовуються при моделюванні рельєфу місцевості і поверхні моря [2].

Існують і інші класифікації фракталів, наприклад розподіл фракталів на детерміновані (алгебраїчні і геометричні) і недетерміновані (стохастичні).

2.2 Типи самоподібності у фракталах

Точна самоподібність -- Це найсильніший тип самоподібності; фрактал виглядає однаково при різних збільшеннях. У фракталів, згенерованих з використанням ітераційних функцій, часто виявляється точна самоподібність.

Майже самоподібність -- Слабка форма самоподібності; фрактал виглядає приблизно (але не точно) самоподібним при різних збільшеннях. Майже самоподібні фрактали містять малі копії цілого фракталу у перекручених та вироджених формах. Фрактали, згенеровані з використанням рекурентних відношень, зазвичай є майже (але не точно) самоподібними.

Статистична самоподібність -- Це найслабкіша форма самоподібності; фрактал має чисельні або статистичні міри, що зберігаються при збільшенні. Найприйнятніші означення «фракталів» просто містять в собі деякий вид статистичної самоподібності (розмірність фракталу, саме по собі, є чисельною мірою, що зберігається при збільшенні). Ймовірнісні фрактали є прикладами фракталів, які є статистично, але не майже й не точно самоподібними.

2.3 Розмірність фракталів

З математичної точки зору, фрактал - це передусім множина з дробовою розмірністю (fractional dimension). Ми добре уявляємо собі, що точка має розмірність 0, коло та відрізок - розмірність 1, куб та сфера - 2. З одномірними об'єктами ми пов'язуємо поняття довжини, з двухмірними - площі і т.д.

Але як можна уявити собі множину з розмірністю 3/2? Для цього необхідно дещо проміжне між довжиною та площиною, і якщо довжину умовно назвати 1-мірою, а площу - 2-мірою, то необхідна (3/2)-міра. Хаусдорф визначив таку б-міру для будь-якого б?0 і на цій основі кожній множині в евклідовому просторі надав у відповідність число.

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

Фрактальна розмірність множини - розмірність того простору, яке повністю заповнюється множиною. Для зв'язку фрактальної та топологічної розмірності використовують показник Херста Н, який обчислюється за формулою H = D - Dt. Ідеї Хаусдорфа були розвинуті А.С.Безіковичем.

В наступні роки розмірність Хаусдорфа-Безіковича отримала застосування в деяких розділах математики, але нічого не передбачувало їй тієї популярності цього поняття за межами математики, яка спостерігається тепер. Частково цьому допомогла наукова діяльність Б.Мандельброта, який в своїх книгах привів яскраві приклади застосування фракталів для пояснення деяких природних явищ. Тобто, фрактальна розмірність, як правило, є невід'ємним нецілим числом, яке показує деяким чином геометричну складність об'єкту.

Розмірність фрактала визначається як (2.30) де - співвідношення подібності, - число кроків, необхідне для того, щоб покрити криву. Рисунок 2.11 - Визначення розміру фрактала на прикладі чотирьох ламаних ліній. Практично розмір фрактала для кривої оцінюється шляхом вимірювання довжин кривої при різних розмірах кроку. Розмірність фрактала D може бути оцінена за допомогою наступного рівняння регресії: (2.31) де L - довжина кривої, B - нахил регресії, G - величина кроку, С - константа. Розглянемо докладніше реалізацію фрактального підходу до аналізу хмар. В основу цього методу покладене виведене Мандельбротом співвідношення між периметром і площею об'єкта.

Для окружностей, квадратів, рівносторонніх трикутників та інших багатокутників відношення периметра до квадратного кореня із площі, що ним обмежується не залежить від розміру фігури і є постійною величиною для даного сімейства. Аналогічно для сімейства подібних островів відношення довжини нефрактальної берегової лінії будь-якого острова до квадратного кореня з його площі не залежить від розміру площі. Однак, якщо берегова лінія фрактальна, то її довжина залежить від довжини еталона і прямує до безкінечності якщо еталон також прямує до нуля. При цьому площа острова , обумовлена кількістю квадратів , що на ній розташовані, залишається кінцевої. Таким чином, відношення периметра до квадратного кореня із площі розходяться.

Мандельброт для випадку фрактальной берегової лінії одержав наступне співвідношення між периметром і площею: (2.32) Це співвідношення виконується для будь-якого еталона довжини , досить малого, щоб задовільно виміряти найменший з островів.

Співвідношення (2.32) застосовується при дослідженні геометрії хмар і зон дощу, розміри яких заключені в широких межах від 1 до З'ясувалося, що периметр хмари пов'язаний з його площею співвідношенням (2.32) з фрактальним розміром D = 1,35 ± 0,05. При цьому ці оцінки виявилися справедливі як для купчастих, так і для пір'ястих хмар. У роботі А. Вальдфогеля, присвяченій аналізу фрактальної розмірності хмар з потужними конвективними струмами, було встановлене співвідношення між периметром і площею для послідовності моментів часу (з інтервалом в 1 хвилину) у площині перетину для постійного коефіцієнта відбиття. Основні висновки можуть бути наступними: для хмар, периметр яких більше 8 км, розмір фрактала приблизно збігається з розміром менш потужних хмар і становить 1,36 ± 0,1; для хмар з периметром від 3 км до 8 км D=1,0 ± 0,1 і, нарешті, хмари з периметром менш 3 км не є фракталами.

2.4 Використання фракталів

фрактал фігура подібний

З недавнього часу фрактальні методи почали використовувати при розробці методів розпізнавання образів на радіолокаційних зображеннях. Суть їх полягає в наступному. Важко локалізувати танк замаскований серед кущів. Важко, навіть коли є якісний сигнал від теле- та теплотелевізора. Набагато легше зробити це за допомогою фрактальних методів. Як вже було сказано вище, обриси штучних об'єктів - танків, автомобілів - створені лініями, які описуються рівняннями цілого порядку. А ось об'єкти природні - рельєф, дерева - фрактальні, тобто мають фрактальну розмірність. Ось на цьому принципі і побудовані нові системи розпізнавання образів.

Системи розпізнавання не бачать кущ, але дуже добре розпізнають штучний об'єкт, схований за кущом. Маскувальне забарвлення може допомогти, але якщо воно не створене кривими другого порядку, як звичайно. Іншими словами, якщо ми виміряємо розмірність зображення якогось природного ландшафту, то вона буде дробова. Розмірність геометричної фігури рівна близько 2 (через похибку вимірювання). А коли накласти, наприклад, прямокутник (як це показано на рисунку) на природне зображення, то розмірність всієї картинки різко поміняється.

Розрахунок розмірності зображення Основною перевагою даного методу над іншими є те, що не потрібно витрачати зусилля і час на покращення якості зображення. Це не дуже впливає на результат. Інша перевага полягає в нижчій вимозі до високої роздільної здатності зображень, порівняно з іншими методами. На результат впливає лише площа, яку займає штучний об'єкт на зображенні, а не контраст, як звичайно. Самоподібність (self-similarity) є основною характеристикою фракталу і означає, що він більш-менш одноманітно побудований у широкому діапазоні масштабів. Так, при збільшенні, маленькі фрагменти фракталу виходять дуже схожими на більші. В ідеальному випадку така самоподібність приводить до того, що фрактальний об'єкт є інваріантним до збільшень. Звичайно, для реального природного фракталу існує деякий мінімальний масштаб довжини lmin, такий, що на відстанях l?lmin, його основна властивість -- самоподібність -- пропадає. Крім того, на досить великих масштабах довжин l>lmax, де lmax -- характерний геометричний розмір об'єктів, ця властивість самоподібності також порушується. Тому властивості природних фракталів розглядаються лише в масштабах l, що задовольняє співвідношенню lmin«l«lmax. Відмітимо, що властивість точної самоподібності характерна лише для регулярних фракталів.

Якщо замість детермінованого способу побудови включити в алгоритм їхнього створення деякий елемент випадковості (як це буває, наприклад, у багатьох процесах дифузійного росту кластерів, електричному пробої й т.д.), то виникають так звані випадкові фрактали. Основна їхня відмінність від регулярних полягає в тому, що властивості самоподібності справедливі тільки після відповідного усереднення по всім статистично незалежним реалізаціям об'єкта. При цьому збільшена частина фракталу не точно ідентична вихідному фрагменту, однак їхні статистичні характеристики збігаються. Стиск зображень (image compression). За допомогою фракталів можна стискувати зображення з деякою втратою якості, аналогічно іншим методам стику з втратами. Але фрактальний стиск дає кращі результати. Методи компресії, основані на RLE, класичний алгоритм Хаффмана, LZW, не враховують природи стискуваних даних і тому дають незадовільні результати при обробці зображень.

Фрактальний стиск зображень - це алгоритм стиску зображень з втратами, заснований на застосуванні систем ІFS до зображень. Даний алгоритм відомий тим, що в деяких випадках дозволяє одержати дуже високі коефіцієнти стиску (кращі приклади - до 1000 разів при прийнятній візуальній якості) для реальних фотографій природних об'єктів, що недоступно для інших алгоритмів стиску зображень у принципі. Основна проблема фрактального стиску - це те, що компресія-декомпресія виконується швидко і однозначно, в той час, як пряма процедура потребує від машини великих інтелектуальний можливостей. При компресії можна не зберігати оригінальні розміри зображення, достатньо просто запам'ятати їх відношення. А при декомпресії - задавати ті розміри, які нам найбільше підходять. Така можливість дозволяє вирішити задачу екстраполяції початкового зображення. При встановленні нових розмірів, що перевищують старі, в нове зображення добавляються елементи, подібні іншим елементам зображення. І якщо, оброблюється природній об'єкт (наприклад, гранітний камінь), то заміна не буде помітною. Основа методу фрактального кодування - це виявлення самоподібних ділянок у зображенні. Патенти ідеї були отримані в 1990-1991 роках. Суть фрактального стиску. В основі більшості методів фрактального кодування, що застосовуються сьогодні, використовуються системи доменних і рангових блоків зображення, блоків квадратної форми, що покривають все зображення. Фрактальне кодування напівтонових зображень основане не гіпотезі, згідно з якою, в будь-якому зображенні можна знайти локальну самоподібність різних його частин. Існуючі алгоритми фрактального стиску, як правило, притримуються наступної схеми кодування. Зображення, яке кодується розбивається на множину блоків, що не перекриваються (рангові області), для кожного з яких, в межах цього ж зображення, відшукується блок більшого розміру (домен), пікселі якого, шляхом деякого перетворення, переводились би в пікселі рангової області. При цьому для пошуку оптимальної відповідності рангових областей і доменів необхідний повний перебір варіантів, що веде за собою значні обчислювальні затрати. З перетворень, що переводять домени в рангові області, формується відображення, що переводить зображення в зображення. При цьому, кодом зображення буде місце розташування і розміри рангових областей, а також коефіцієнти перетворень, описуючих самоподібність всередині зображення. Кількість біт, необхідних для опису коду, буде значно менше кількості біт, необхідних для опису початкового зображення. Коефіцієнтом стиску називається відношення бітового представлення зображення до бітового представлення коду. В відомих фрактальних методах стиску зображень значення цього коефіцієнту може досягати 100 при достатньо непоганій якості відновлення. Для відновлення закодованого таким чином зображення використовується принцип стиснених відображень, який говорить, що стискуюче відображення, діюче в повному метричному просторі, має єдину нерухому точку. Відображення, що діє на повному метричному просторі зображень, формується з перетворень, які переводять домени в рангові області [3]. Відповідно до даного методу зображення розбивається на безліч неперекриваючих рангових підзображень і визначається безліч перекриваючих доменних підзображень. Для кожного рангового блоку алгоритм кодування знаходить найбільш підходящий доменний блок і афінне перетворення, що переводить цей доменний блок у даний ранговий блок. Структура зображення відображається в систему рангових блоків, доменних блоків і перетворень. Основна складність фрактального стиску полягає в тому, що для знаходження відповідних доменних блоків, загалом кажучи, потрібен повний перебір.

Оскільки при цьому переборі щораз повинні рівнятися два масиви, дана операція виходить досить тривалою. Порівняно простим перетворенням її можна звести до операції скалярного добутку двох масивів, однак навіть скалярний добуток рахується порівняно тривалий час. Крім стиску, іншою областю фрактальної обробки зображень є їх генерація. В наш час існує множина найрізноманітніших пакетів прикладних програм від простих, які створюють зображення на основі множини Мандельброта (Fractal SSE), до складних, які генерують зображення 3d, анімаційні зображення та IFS-зображення. Всі вони побудовані на основі відкриття Мандельброта: якщо нанести визначені точки на площину комплексних чисел, то можна створювати зображення надзвичайного абстрактного вигляду - множина Мандельброта. В рівняння Мандельброта підставляються координати деякої точки комплексної площини, і результатом є координати іншої точки. Результат, отриманий при вводі координат першої точки, слугує початком для наступної ітерації, її результат підставляється в наступне рівняння і так далі. Обидві ці найголовніші області застосування фрактальних методів в наш час знаходяться на порівняно високому рівні розвитку, незважаючи на те, що фрактальна наука досить молода. Існує надзвичайно велика кількість програм, за допомогою яких можна створити або стиснути зображення і ефективність обробки зображень деяких з цих програм достатньо висока. Потенційним, хоч і менш відомим видом фракталів, є фрактали на основі системи ітераційних функцій (Iterated Function System - IFS). Метод IFS, який застосовується до побудови фрактальних зображень, винайшов Майкл Барнслі. Він базується на самоподібності елементів зображення і полягає в моделюванні малюнка декількома меншими частинами його самого. Найвідомішим IFS-зображенням є чорний папоротник, в якому кожен лист в дійсності являє собою мініатюрний варіант самого папоротника .

Система IFS - це також сукупність стискаючих афінних перетворень. Як відомо, афінні перетворення містять у собі масштабування, поворот і паралельний перенос. Афінне перетворення вважається стискаючим, якщо коефіцієнт масштабування менше одиниці. Розглянемо докладніше побудову кривій Кох з використанням афінних перетворень. Кожний новий елемент кривої містить чотири ланки, отриманих з утворюючого елемента використанням масштабування, повороту й переносу. 1. Для одержання першої ланки досить стиснути вихідний відрізок у три рази. Слід зазначити, що те ж масштабування застосовується для всіх ланок. 2. Наступна ланка будується з використанням всіх можливих перетворень, а саме: стиск у три рази, поворот на - 60 градусів і паралельний перенос на 1/3 по осі X. 3. Третя ланка будується аналогічно другому: стиск у три рази, поворот на 60 градусів, паралельний перенос на 2/3 по осі X. 4. Остання ланка: стиск у три рази, паралельний перенос на 2/3 по осі X. Для синтезу фрактала вибирається початкова точка, до якої застосовується випадковим образом обране з ІFS перетворення, у результаті чого точка переміщується в інший кінець екрана. Ця операція повторюється багато разів (досить 100 ітерацій), і через деякий час точка починає блукати по атрактору (безліч всіх можливих траєкторій), що і буде являти собою зображення фрактала. Кожне нове положення точки зафарбовується кольором, відмінним від фону. Існує теорема, яка доводить, що отриманий атрактор буде замкнутим. Для того, щоб блукаюча точка зафарбовувала нові пікселі, а не блукала по старим, використовують сьомий параметр, що являє собою ймовірність появи конкретного афінного перетворення з набору перетворень ІFS. Якщо вибрати початкову точку так, щоб вона відразу виявилася на атракторі, то вона починає блукати в області цього атрактора, не переміщуючись в інші області екрана. Розглядаючи кожне перетворення окремо, можемо помітити, що де б ми не починали, після декількох ітерацій, точка перестане рухатися по екрану. Точка зупинки називається нерухомою точкою - це розв'язок системи лінійних рівнянь двох змінних, яке знаходиться методом простої ітерації. Нерухома точка кожного перетворення входить до складу атрактора. Тому за початкову точку при побудові фрактала можна взяти нерухому точку першого перетворення з набору ІFS.

Размещено на Allbest.ru