Обробка зображень та мультимедіа

Модуль 2

Лекція 12. Класифікація, нейронні мережі та комп’ютерна корекція зображень

ЛЕКЦІЯ 12 КЛАСИФІКАЦІЯ, НЕЙРОННІ МЕРЕЖІ ТА КОМП’ЮТЕРНА КОРЕКЦІЯ ЗОБРАЖЕНЬ

  1. 12.1    МЕТОДИ КЛАСИФІКАЦІЇ ЕЛЕМЕНТІВ ЗОБРАЖЕНЬ

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

  1. 1)  ймовірностний критерій якості класифікації;
  2. 2)  оптимальна стратегія статистичної класифікації;
  3. 3)  класифікатор Байєса;
  4. 4)  мінімаксний класифікатор;
  5. 5)  класифікатор Неймана-Пірсона.

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

  1. 1. Множина XxY є імовірнісним простором з імовірнісною мірою P. Прецеденти (x1, y1), … (xn, yn) з’являються випадково і незалежно у відповідності з розподілом p.
  2. 2. Відомі щільності розподілу класів py(x) = p(x| Ky), yєY, що називаються функціями правдоподібності.
  3. 3. Відомі ймовірності появи об’єктів кожного з класів Py(x) = P(Ky), yєY, що називаються апріорними ймовірностями.

Базуючись на даних гіпотезах, принцип максимуму апостеріорної ймовірності записується в наступному вигляді:

F(x)= argmax P(Ky| x) = argmax py(x) Py

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

Існують системи виявлення об'єктів зображення, що базуються на "наївному" баєсовому методі. Даний метод ґрунтується на побудові емпіричної щільності розподілу ймовірностей класів по навчальній вибірці за припущення про незалежність компонентів вектора ознак.

Практичні результати є наступними:

  1.  Алгоритм побудови "наївного" баєсового класифікатора схильний до перенавчання;
  2.  Алгоритм побудови "наївного" баєсового класифікатора чутливий до шуму, тому що базується на емпіричних функціях щільності розподілу;
  3.  Швидкість роботи самого класифікатора висока, основний час може займати обчислення вектора ознак.

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

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

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

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

1. Евристичні методи:

а)  повна евристична модель, де експертом складається набір правил, що описують зображення об'єкта (будується модель), згідно з якими здійснюється розпізнавання;

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

2. Метод порівняння з шаблоном. Складається шаблон для зображення всього об'єкта чи його характерних ознак. Також вводиться функція перевірки відповідності.

3. Методи з навчанням по прецедентах. Модель автоматично будується на основі набору зображень об'єкта, складених заздалегідь з можливих вхідних даних системи.

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

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

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

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

Метод опорних векторів був успішно застосований для задачі розпізнавання об'єктів зображення. Метод характеризується наступним:

  1. висока стійкість до перенавчання;

  2. чутливість до шуму може регулюватися за рахунок зменшення точності;

  3. в системах розпізнавання об'єктів метод дає прискорення в декілька разів у порівнянні з нейронними мережами.

SNoW – особливий вид нейронної мережі. Вектор ознак бінарний. Мережа складається з двох (по числу можливих класів) лінійних нейронів, зв'язаних з компонентами вектора ознак. Класифікація проходить за принципом “переможець забирає все”. Метод SNoW вважається досить ефективним методом для розв’язання задач виявлення об'єктів зображення. Відповідно до деяких досліджень SNoW перевершує по своїм параметрам метод опорних векторів.

Сlassіfіer boostіng – це підхід до розв’язання задачі класифікації, шляхом комбінування примітивних класифікаторів в один більш сильний класифікатор. Основна ідея методу полягає в ітеративній мінімізації опуклого функціонала помилки класифікації, шляхом додавання в набір класифікаторів чергового слабкого класифікатора. Для систем розпізнавання об'єктів зображення був застосований каскадний підхід, який полягає в побудові каскаду із комплексу слабких класифікаторів, що працює за принципом послідовних наближень. Характеристики каскадного методу перевершують всі інші системи.

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


  1. 12.2    ЗАСТОСУВАННЯ НЕЙРОННИХ МЕРЕЖ

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

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

Суть НМ полягає в тому, що мережа складається з елементів, котрі називаються формальними нейронами (formal neuron). Кожен нейрон приймає набір сигналів, що надходять на його входи від одної групи таких же нейронів, обробляє сигнали з врахуванням попередніх сигналів і адаптації до них на основі процедур навчання і передає результати обробки другій групі нейронів. Зв'язки між нейронами кодуються вагами, що відображають важливість їх інформації для визначення загального результату. Основний принцип настроювання нейронної мережі полягає в застосуванні процедур оптимізації та адаптації на основі певних критеріїв, здатності до перенавчання.

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

Переважна кількість прикладних нейронних систем передбачає використання багатошарових персептронів (назва „персептрон” походить з англійського perceptron – сприйняття, оскільки перші зразки таких структур призначались для моделювання зору). Популярність персептронів зумовлена широким колом доступних для них задач. Загалом вони вирішують задачу апроксимації багатовимірних функцій, іншими словами – побудову багатовимірного відображення F : x→y , яке узагальнює заданий набір прикладів (еталонних пар даних) {xa ,ya } .

Залежно від типу вихідних змінних (тип вхідних не має вирішального значення), апроксимація функції може набувати вигляду:

  класифікації (дискретний набір вихідних значень);

  регресії (неперервні вихідні дані).

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

Рисунок 1. – Персептронна система розпізнавання зображень

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

Припустимо, що вектор Х є зображенням демонстраційної карти, яка піддається розпізнаванню. Кожну компоненту Хi (квадратик зображення карти) вектора Х перемножують на відповідну компоненту wi вектора ваг W. Ці добутки сумують. Якщо сума перевищує поріг q , то вихід нейрона y дорівнює одиниці (індикатор запалюється), у протилежному випадку – нуль. Цю операцію компактно записують у векторній формі: Y = XW . Для навчання мережі образ X подають на вхід і обчислюють вихід Y . Якщо вихід правильний, то нічого не змінюється. Однак якщо вихід неправильний, то ваги, приєднані до входів, що підсилюють помилковий результат, модифікуються, щоб зменшити помилку.

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

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

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

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

  1. 12.3    КОРЕКЦІЯ ЗОБРАЖЕНЬ В МАШИННІЙ ГРАФІЦІ

    1. 12.3.1    Основні ефекти

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

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

З алгоритмічної точки зору, одержання цих ефектів не представляє особливих труднощів. Складається матриця чисел, що називають ядром згортки. Матриця розміром 3-на-3 містить три рядки по три числа в кожному. Щоб перетворити один піксел у зображенні перемножуються значення його кольорів на число в центрі ядра. Потім перемножується вісім значень кольорів пікселів, що оточують центральний піксел, на відповідні їм коефіцієнти ядра. Підсумовуються всі дев'ять значень. В результаті отримуємо нове значення кольору центрального піксела. Цей процес повторюється для кожного піксела в зображенні. Таким чином зображення фільтрується. Коефіцієнти ядра визначають результат процесу фільтрації. Ядро розмивання може, наприклад, складатися із сукупності коефіцієнтів, кожний із який менший 1, а їхня сума складає 1. Це означає, що кожний піксел поглине щось із кольорів сусідів, але повна яскравість зображення залишиться незмінною. (Якщо сума коефіцієнтів більша чим 1, яскравість збільшиться; якщо менша ніж 1, яскравість зменшиться.) У ядрі різкості центральний коефіцієнт більший 1, а оточений він від'ємними числами, сума яких на одиницю менша центрального коефіцієнта. У такий спосіб збільшується любий існуючий контраст між кольором піксела і кольорами його сусідів  

Розмивання і збільшення різкості.  

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

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

Збільшення різкості досягається точно так само, як і розмивання, за винятком того, що використовуються інше ядро. Будем перетворювати те саме зображення що і колись, але з іншлю ціллю - збільшити якість зображення.  

При опрацюванні кожного піксела в зображенні використовується ядро різкості розміром 3х3. Червона, зелена і синя колірні складові обробляються окремо і пізніше об'єднуються, щоб сформувати 24-бітне значення кольору. Від'ємні ваги навколо центру ядра збільшують контраст між центральним пікселом і сусідами. Кінцеве зображення буде більш чітке за оригінал.

Тиснення.  

Тиснення робиться майже так, як і розмивання і збільшення різкості. Процес починається зі звичайним кольоровим зображенням.  

  1. Кожний піксел у зображенні обробляється ядром (маскою) тиснення розміром 3х3. На відміну від ядер розмивання і різкості, у яких сума коефіцієнтів повинна дорівнювати 1, сума ваг у ядрі тиснення дорівняє 0 (градієнтна маска). Це означає, що "фоновим" пікселам (пікселам, що не знаходяться на межах переходу від одного кольору до іншого) присвоюються нульові значення, а нефоновим пікселам - значення, відмінні від нуля.  
  2. Після того, як значення піксела оброблено ядром тиснення, до нього додається число 128. У такий спосіб значенням фонових пікселів стане середній сірий колір (червоний = 128, зелений = 128, синій = 128). Суми, що перевищують 255, можна округлити до 255 або взяти залишок по модулю 255, щоб значення виявилося між  0  і  255.  
  3. У такому варіанті зображення, контури здаються видавленими над поверхнею. Напрямок підсвічування зображення можна змінювати, змінюючи позиції чисел 1 і -1 у ядрі. Якщо, наприклад, поміняти місцями значення 1 і -1, те має місце реверсування напрямку підсвічування.  

Акварелізація  

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

Перший крок у застосуванні акварельного фільтра - згладжування кольорів у зображенні. Одним із способів згладжування є процес медіанного усереднення кольору в кожній точці. Значення кольору кожного піксела і його 24 сусідів поміщають в список і сортують від меншого до більшого. Медіанне (тринадцяте) значення кольору в списку призначається центральному пікселу.

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

12.3.2     Усунення ступінчатого ефекту (аліазингу)

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

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

Недолік цього методу полягає в великій обчислювальній складності, яка залежить від роздільної здатності координатного простору, оскільки зі збільшенням лінійних розмірів зображення в n разів, його площа збільшується уn2 разів. Практично, для анімації сцени з частотою 10Гц, що містить близько 200 тис. трикутників, збільшення дискретизації в 16 разів вимагає технічних засобів з швидкодією 16 GFLOPS. Враховуючи, що пікова продуктивність сучасних процесорів не перевищує 100 MFLOPS , така продуктивність не досяжна навіть для сучасних графічних станцій.

Згідно з другим методом усунення ступінчастості, піксель розглядається не як умовна точка, а як скінчена область . Метод базується на згортці функції. Для згладжування беруть згортку сигналів для зображення з ядром згортки, а результат використовують для визначення атрибутів пікселя.

Як функцію згортки часто використовують прямокутну функцію  h(x), 0<х<1. За допомогою неї отримують задовільні результати, хоч трикутний та гауссовський фільтри дають ще більш якісне згладжування. Метод згортки порівняно з методом растеризації дає краще згладжене зображення, але характеризується значно більшою обчислювальною складністю.

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

Рис. 2. Усунення ефекту алиазингу векторної границі

Алгоритм А. Руа в процесі визначення інтенсивності кольору пікселя врахо¬вує площі двох суміжних пікселів — основного та допоміжного. При цьому обчислювальний процес визначення координат та інтенсивностей кольору точок розділений. Алгоритм дає придатні результати, але вимагає виконання «довгих» операцій, що суттєво обмежує його використання.

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

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

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

Нехай відрізок прямої в першому октанті задається своїми більшим М та меншим N приростами на координатній осі. Відомо, що крокові переміщення всіх відрізків прямих з приростами  пМ  і  пМ  ідентичні і повторюються черезМ тактів, де п – ціле число. Якщо IM – значення інтенсивності кольору, з яким необхідно відтворити відрізок прямої, то для визначення невідомого параметра IK для інтерполювання відрізка прямої, складемо пропорцію  

Звідки отримаємо, де k – кутовий коефіцієнт нахилу прямої.

Таким чином, інтерполювання відрізка прямої з параметрами  М  та  N можна звести до інтерполювання за  М  тактів відрізка прямої з параметрами IM  та  IK. При позитивному значенні рціночної фукнції насищенчсть кольору дорівнює (Fi–IK), а при негативному - модулю Fi.

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

 

12.3.3      Алгоритми триангуляції 

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

Генерація об'ємних зображень представляє складну обчислювальну задачу, у зв'язку з чим на практиці виконують її декомпозицію. Складні зображення формують фрагментарно, для чого їх розбивають на складові частини. Процес розбиття поверхні об'єктів на полігони отримав назву тесселяціі. Ця стадія на даному етапі розвитку машинної графіки проводиться повністю програмно незалежно від технічного рівня 3D-апаратури.

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

На практиці найбільш часто здійснюється розбиття зображень на трикутники. Це пояснюється наступними причинами:

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

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

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

Рис. 3 а) полігональна область б) триангуляційних мережа

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

Рис. 4. Зафарбовування граней об'єкту

Останнім етапом є застосування алгоритмів згладжування, які усувається ребристої поверхні, ефект Маха. На рисунку 5 представлена вже гладка півсфера з плавним переходом напівтонів і областями освітлення.

Рис.5. Згладжування поверхні

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

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

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

Розглянемо найбільш поширені алгоритми триангуляції полігонів.

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

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

Рис.6 а) Опуклий полігон      б) Неопуклий полігон

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

Наведемо універсальний алгоритм. Триангуляцію будь-якого полігону можна здійснити за наступним універсальним алгоритмом.

Вибирається крайня ліва вершина і між двома її суміжними сторонами проводиться діагональ. При цьому можуть мати місце наступні два випадки: рис.7а - діагональ ас є хордою; рис.7б - діагональ ас не хорда, так як всередину трикутника abc потрапляє вершина d полігону (у загальному випадку їх може бути декілька). З усіх вершин всередині трикутника abc вершина d найбільш віддалена від сторони ас. Цю вершину будемо називати вершиною, що вторгається. У разі, коли вершин, які вторгаються немає, то отриманий трикутник заносять у сітку трикутників, і алгоритм рекурсивно обробляє залишився полігон до тих пір, поки він не виродиться в трикутник.

Рис.7. а) діагональ ас – хорда     б) виявлена вершина, що вторгається

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

 

Рис. 8. Триангуляція з використанням внутрішньої точки

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

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

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

Рис.9. Два варіанти триангуляції для одного набору точок

Розглянемо триангуляцію точок на площині за методом Делоне. Ця триангуляція добре збалансована в тому сенсі, що формуються трикутники які наближаються до рівнокутної форми (рис.9а). Триангульовані зображення на рис. 9б не може бути віднесено до триангуляції Делоне.

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

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

Алгоритми триангуляції реалізовані в багатьох професійних графічних пакетах 3D-моделювання, таких як 3D Studio MAX, OpenGL Optimizer, LightWave та ін. Ці пакети дозволяють не тільки використовувати різні алгоритми для триангуляції, але й додавати користувачам свої.

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

 

Лекція 11. Стиснення та кодування зображень Лекція 7. Методи нелокальної обробки та просторової фільтрації зображень
© 2023 СумДУ
created with Lectur'EDbeta