• ЛЕКЦІЯ 10. ІНШІ МАТЕМАТИЧНІ ПЕРЕТВОРЕННЯ ТА ЇХ ЗАСТОСУВАННЯ
  • 10.1 МЕТОДИ ДЕКОМПОЗИЦІЇ ЗОБРАЖЕНЬ
  • 10.2 ФРАКТАЛИ ТА ЇХ ЗАСТОСУВАННЯ
    • 10.2.1 Визначення.
    • 10.2.2 ​Класифікація фракталів.

ЛЕКЦІЯ 10. ІНШІ МАТЕМАТИЧНІ ПЕРЕТВОРЕННЯ ТА ЇХ ЗАСТОСУВАННЯ

 

1. 10.1    МЕТОДИ ДЕКОМПОЗИЦІЇ ЗОБРАЖЕНЬ

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

1. 1) синтез фільтрів на основі власних векторів зображення або його кореляційної матриці;
2. 2) відбір головних (найвпливовіших) компонент розкладання на власні або сингулярні вектори – Principal Component Analysis (PCA);
3. 3) модальний аналіз – Empirical mode decomposition (EMD).

Метод РСА реалізують за допомогою сингулярного розкладання (Singular Value Decomposition – SVD). Перевагою SVD є те, що сингулярне розкладання реального сигналу дає систему ортогональних векторів, також реальних. Ортогональність та те, що дані реальні, спрощує алгебраїчні операції з матрицями.

Аналіз за допомогою розкладання по власним та сингулярним векторам застосовують по відношенню до сигналу зображення або його кореляційної матриці. Одною з різновидів кореляційної характеристики зображень є розподіл Вігнера.

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

Алгоритм аналізу зображень за допомогою власних векторів залежить від того, як вони використовуються – як фільтри чи як базис для спектрального аналізу.

 

2. 10.2    ФРАКТАЛИ ТА ЇХ ЗАСТОСУВАННЯ

   10.2.1    Визначення.

У той час як об'єкти, побудовані людиною, такі як промислові та житлові будинки, можуть бути ефективно описані набором простих геометричних примітивів: кубів, сфер, циліндрів, конусів, кольорові текстури природного походження, через свою нерегулярність і фрагментарність, погано піддаються такому опису..У зв'язку із цим, для аналізу таких текстур виявляється природним подання їх у вигляді фрактала з деяким розміром D.

Фрактал (лат. fractus, fractal – дроблений) – термін, який ввів Бенуа Мандельброт в 1975 році для позначення нерегулярних самоподібних множин.

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

Ще один варіант визначення: фрактал – самоподібна множина нецілої розмірності. Самоподібна множина – множина, що представляється у вигляді об'єднання однакових непересічних підмножин подібних до вихідної множини.

Основні властивості фракталів:

  Вони мають тонку структуру, тобто містять довільно малі масштаби.

  Вони занадто нерегулярні, щоб бути описаними традиційною геометричною мовою.

  Вони мають деяку форму самоподоби, допускаючи наближену.

  Вони мають дробову "фрактальну" розмірність, що також називають розмірністю Мінковського.

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

1. 1. побудувати залежність коефіцієнта кореляції від кроку; значення кроку, при якому функція має максимум, є максимальним кроком у діапазоні кроків, що задаються, при оцінці розміру фрактала;
2. 2.  не враховувати оцінку розміру фрактала при низькому коефіцієнті кореляції в тих методах, де використовується оцінка фрактала як середнє значення в серії експериментів;
3. 3.  не включати розмір фрактала в систему ознак для сегментації текстур при значеннях коефіцієнта кореляції < 0,7 .

Оцінка фрактальності текстури є важливою характеристикою при сегментації по розмірі фрактала.

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

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

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

10.2.2    ​Класифікація фракталів.

В основному фрактали ділять на геометричні (рис.1), алгебраїчні й стохастичні. Однак існують і інші класифікації: рукотворні й природні. До рукотворних належать ті фрактали, які були винайдені вченими, вони при будь-якому масштабі володіють фрактальными властивостями. На природні фрактали накладається обмеження на область існування – тобто максимальний і мінімальний розмір, при яких у об'єкта спостерігаються фрактальні властивості.

Рисунок 10.1 – Приклади геометричних фракталів

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

Рисунок 10.2. – Приклад алгебраїчного фракталу. Множина Жюліа́

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

Геометричні фрактали застосовуються для одержання зображень дерев, кущів, берегових ліній тощо. Алгебраїчні та стохастичні – при побудові ландшафтів, поверхні морів, моделей біологічних об'єктів та інше.

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

Для пояснення фрактальної розмірності необхідно ввести поняття топологічної розмірності. Під топологічною розмірністю множини в лінійному просторі розуміють число лінійно незалежних координат в просторі. Фрактальна розмірність множини – розмірність того простору, яке повністю заповнюється множиною. Для зв’язку фрактальної та топологічної розмірності використовують показник Херста Н, який обчислюється за формулою H = D - Dt. Ідеї Хаусдорфа були розвинуті А.С.Безіковичем. В наступні роки розмірність Хаусдорфа-Безіковича отримала застосування в деяких розділах математики, але нічого не передбачувало їй тієї популярності цього поняття за межами математики, яка спостерігається тепер. Частково цьому допомогла наукова діяльність Б.Мандельброта, який в своїх книгах привів яскраві приклади застосування фракталів для пояснення деяких природних явищ. Тобто, фрактальна розмірність, як правило, є невід’ємним нецілим числом, яке показує деяким чином геометричну складність об’єкту.

     Розмірність фрактала D визначається як

(1)

де 1/r – відношення подібності, N – число кроків, необхідне для того, щоб покрити криву.

Практично розмір фрактала для кривої оцінюється шляхом вимірювання довжин кривої при різних розмірах кроку. Розмірність фрактала D може бути оцінена за допомогою наступного рівняння регресії:

(2)

де L – довжина кривої, B – нахил регресії, G – величина кроку, С – константа.

Рисунок 10.3 – Визначення розмірності фрактала на прикладі ламаної кривої, утвореної 4-ма відрізками.

 

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

При цьому площа острова A(δ), обумовлена кількістю квадратів δ, що на ній розташовані, залишається кінцевої. Таким чином, відношення периметра до квадратного кореня із площі розходяться. Мандельброт для випадку фрактальной берегової лінії одержав наступне співвідношення між периметром і площею:

(3)

Це співвідношення виконується для будь-якого еталона довжини δ, досить малого, щоб задовільно виміряти найменший з островів.

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

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

Z[i+1] = Z[i]*Z[i] + C (4)

де Z і C – комплексні змінні. Ітерації виконуються для кожної стартової точки C прямокутної або квадратної області – підмножині комплексної площини. Ітераційний процес триває доти, поки Z[i] не вийде за межі круга заданого радіуса, центр якої лежить у точці (0,0), або після досить великої кількості ітерацій. Залежно від кількості ітерацій, протягом яких Z[i] залишається усередині круга, встановлюється колір точки C. Якщо Z[i] залишається усередині круга протягом досить великої кількості ітерацій, то ця точка растра зафарбовується в чорний колір. Множині Мандельброта (рис. 10.4) належать саме ті точки, які протягом безкінечного числа ітерацій не переходять у нескінченність.

Рисунок 10.4 – а) Множина Мандельброта; б) Збільшена ділянка границі множини Мандельброта

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

Рисунок 10.5 – Перші 5 поколінь сніжинки Коха

 Площа під кривою, якщо прийняти площу утворюючого трикутника за 1, дорівнює:

(5)

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

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

Рисунок 10.6 – Розрахунок розмірності зображення

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

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

Звичайно, для реального природного фракталу існує деякий мінімальний масштаб довжини l_min, такий, що на відстанях l≈l_min, його основна властивість — самоподібність — пропадає. Крім того, на досить великих масштабах довжин l>l_max, де l_max — характерний геометричний розмір об'єктів, ця властивість самоподібності також порушується. Тому властивості природних фракталів розглядаються лише в масштабах l, що задовольняє співвідношенню l_min«l«l_max.

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