Інтерполяція багатовимірних функцій в просторі та часі

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

Вінницький національний технічний університет

ІНТЕРПОЛЯЦІЯ БАГАТОВИМІРНИХ ФУНКЦІЙ В ПРОСТОРІ ТА ЧАСІ

Спеціальність 01.05.02 - Математичне моделювання та обчислювальні методи

Автореферат

дисертації на здобуття наукового ступеня кандидата технічних наук

Юдін Олег Олександрович

Вінниця - 2010

Дисертацією є рукопис

Роботу виконано у Вінницькому національному технічному університеті Міністерства освіти і науки України.

Науковий керівник доктор технічних наук, професор Квєтний Роман Наумович, Вінницький національний технічний університет, завідувач кафедри автоматики та інформаційно-вимірювальної техніки;

Офіційні опоненти: доктор технічних наук, професор Пєтух Анатолій Михайлович, Вінницький національний технічний університет, завідувач кафедри програмного забезпечення;

доктор фізико-математичних наук, старший науковий співробітник Фінін Георгій Семенович, Міжнародний Соломонів університет, м. Київ, перший проректор

Захист відбудеться «_26_» ___03_____ 2010 р. о _930____ годині на засіданні спеціалізованої вченої ради Д 05.052.01 у Вінницькому національному технічному університеті за адресою: 21021, м. Вінниця, вул. Хмельницьке шосе, 95, ГУК, ауд. 210.

З дисертацією можна ознайомитись у бібліотеці Вінницького національного технічного університету за адресою: 21021, м. Вінниця, вул. Хмельницьке шосе, 95.

Автореферат розіслано «_09_» _____02_______ 2010 р.

Вчений секретар спеціалізованої вченої ради С.М. Захарченко

Загальна характеристика роботи

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

Зв'язок роботи з науковими программами, планами, темами. Дисертаційне дослідження проводилось протягом 2004-2009 рр. згідно з напрямком досліджень за держбюджетними науково-дослідними роботами на тему “Методологія розв'язання задач багатовимірної інтерполяції в просторі і часі” № 41-Д-290 (номер держреєстрації 0107U002092) у відповідності до пріоритетних напрямків розвитку науки і техніки в Україні.

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

Завдання дослідження:

1. Аналіз класичних методів інтерполяції, їх модифікацій та галузей застосування;

2. Розробка математичної моделі для розв'язання задачі інтерполяції за допомогою NURBS-кривих з можливістю управляти кривою та пошуком оптимальної інтерполяційної кривої;

3. Розробка математичної моделі та підходу до ефективної сферичної лінійної інтерполяції у багатовимірному просторі. Розробка інтерполяції поворотів у тривимірному просторі з урахуванням часу із застосуванням кватерніонної алгебри;

4. Розробка математичної моделі бікубічної інтерполяції на основі сплайнів Катмулла-Рома для поверхонь в тривимірному просторі;

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

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

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

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

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

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

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

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

4. Вперше розроблено метод інтерполяції кривих бікубічними сплайнами для інтерполяції поверхонь на основі сплайнів Катмулла-Рома, який має меншу обчислювальну складність в порівнянні з вже існуючими методами.

Практичне значення одержаних результатів Полягає в тому, що:

1. Розроблено методику побудови інтерполяційної функції за допомогою NURBS-кривих.

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

3. Розроблено методику лінеаризації за параметром часу сферичної інтерполяції для сфери у просторі будь-якого порядку із заданою максимально допустимою похибкою.

4. Розроблено алгоритм та програму для збільшення зображень із застосуванням інтерполяції відсутніх точок зображення на основі бікубічних сплайнів Катмулла-Рома з високою швидкодією.

Результати дисертаційної роботи включено до звітів з НДР “Розробка і впровадження мережної геоінформаційної аналітичної системи комплексного державного моніторингу поверхневих вод Вінницької області” (№ ДР 0106U011772), “Розробка і впровадження мережної геоінформаційної аналітичної системи комплексного державного моніторингу поверхневих вод Вінницької області” (№ ДР 0105U006685), а також у НДР “Створення Інтернет-порталу для ГІС-систем моніторингу Вінницької області” (№ ДР 0107U012437) і використовуються для моделювання ландшафтів. Результати дисертації впроваджено у Басейновому управлінні водними ресурсами р. Південний Буг і використовуються для інтерполяції показників забруднення води у басейні річки Південний Буг. Також отримані результати впроваджено у навчальному процесі у Вінницькому національному технічному університеті під час викладання лекцій та проведення занять з курсу “Обчислювальні методи та застосування комп'ютерів”, розділ “Методи обробки даних” для студентів спеціальностей 7.091401 “Системи управління і автоматики” на кафедрі автоматики і вимірювальної техніки.

Особистий внесок здобувача. У монографії [1] автору належить підрозділ 2.4, присвячений сферичній інтерполяції у багатовимірному просторі. У статті [3] розроблено модель оптимізації вагових коефіцієнтів кривої для зменшення похибки інтерполяції. У роботі [9] автором було розроблено модель та застосовані кватерніони для інтерполяції обертань разом із переміщенням у просторі. У свідоцтві про реєстрацію авторського права на комп'ютерну програму [10] створено програмний модуль для інтерполяції вимірюваних показників гео-інформаційної системи.

Апробація результатів дисертації. Результати досліджень викладені в науковій роботі пройшли апробацію на наукових конференціях:

1. Інформаційні технології в економічних та технічних системах (ІТЕТС-2005). - м. Кременчук, 2005;

2. XXXIV, XXXV, XXXVІ, XXXVІІ, XXXVІІІ науково-технічних конференціях професорсько-викладацького складу, співробітників та студентів Вінницького національного технічного університету з участю працівників науково-дослідницьких організацій та інженерно-технічних працівників підприємств м. Вінниці та області. - м. Вінниця, 2005, 2006, 2007, 2008, 2009;

3. “Photonics-ODS 2005”, III International Conference on Optoelectronic Information technologies. - Міжнародна конференція оптоелектронних інформаційних технологій. - Вінниця, ВДТУ, 2005;

4. ХІІІ Міжнародна конференція з автоматичного управління (Автоматика-2006). - Вінниця, ВДТУ, 2006;

5. Спільний науковий семінар ВНТУ та хайфського Техніону (Ізраїль). -- Вінниця, ВНТУ. -- 2007;

6. Контроль та управління у складних системах, ІХ Міжнародна конференція. - Вінниця, ВНТУ, 2008.

Публікації. За результатами виконаних досліджень було опубліковано 11 наукових праць, з них: 1 монографія, 6 статей, виданих у науково-технічних журналах, рекомендованих згідно переліку ВАК України, 2 публікації у вигляді тез доповідей та 2 свідоцтва про реєстрацію авторського права на комп'ютерні програми.

Структура і обсяг роботи. Дисертація складається із вступу, чотирьох розділів, висновків, списку використаних джерел та додатків. Загальний обсяг дисертації складає 150 сторінок, з яких основний зміст викладено на 106 сторінках друкованого тексту, містить 30 рисунків та 5 таблиць. Список використаних джерел складається з 128 найменувань. Додатки містять окремі лістинги програм та акти впровадження результатів роботи і викладені на 24 сторінках.

інтерполяція оптимізація лінійний сферичний

Основний зміст роботи

У вступі обґрунтовано актуальність теми, визначено мету та задачі досліджень, відзначено наукову новизну та практичну цінність роботи.

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

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

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

Також увагу приділено підвищенню ефективності застосування за рахунок розширення можливостей методів інтерполяції (метод інтерполяції на основі кривих Без'є, NURBS-кривих). При побудові двовимірних та тривимірних NURBS-кривих (вони використовуються у таких сучасних пакетах програм як Microsoft Office Visio, 3dsMax, AutoCAD та інших), методика не викликає складності, але при збільшені порядку простору складність полягає у способі побудови кривої. При моделюванні параметричних процесів у просторах великих розмінностей потрібен інший підхід до побудови NURBS. При побудові складних геометричних поверхонь використовується велика щільність кускових кривих, що значно ускладнює модель. Створення методу для підвищення точності побудови кривих дасть можливість скоротить кількість обчислювальних операцій. Інші моделі інтерполяції, як, наприклад, сферична інтерполяція кватерніонів, потребують спрощення для забезпечення можливості їх застосування у складних моделях руху об'єктів простору з часом. Підвищення ефективності наведених методів дозволить розширити область їх застосування у пакетах для обробки та моделювання комп'ютерної графіки, комп'ютерних ігор, геоінформаційних систем, при моделюванні складних систем та фізичних процесів, а також у медицині.

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

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

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

, , (1)

де уk - вектор вузлів інтерполяції для k-ої просторової координати,

А - матриця коефіцієнтів,

Вk - вектор вільних членів для k-ої просторової координати,

w - вектор вагових коефіцієнтів,

t - параметр.

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

, (2)

де ,

- вектор проміжних точок.

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

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

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

. (3)

На основі цієї функції розраховано максимальну похибку лінеаризації (4) для кута Щ і встановлено залежність між похибкою та кількістю вузлів інтерполяції.

(4)

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

(5)

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

. (6)

Для побудови бікубічного сплайну потрібна матриця вузлів розміром 4х4. Також виведені формули для обчислення крайових значень для отримання повної інтерполяційної схеми. Інтерполяція проводиться для чотирьох точок між двома середніми (для x0,x1,x2,x3, інтерполяційна крива лежить між x1 та x2). Для охоплення точок x0 і x3 необхідні додаткові умови (х-1 - крайня ліва додаткова точка, х4 - крайня права додаткова точка, х0-х3 - відомі вузли інтерполяції):

, (7)

. (8)

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

У третьому розділі представлено методики та алгоритми, які реалізують запропоновані моделі.

Методика інтерполяції за допомогою NURBS-кривих полягає у застосуванні метода Гауса - Жордана для вирішення системи. Ця методика дозволяє за один прохід розв'язати задачу пошуку контрольних точок для усіх просторових координат багатовимірного простору, через те, що матриці аргументів будуть для них однаковими. Такий підхід дає змогу значно скоротити кількість обчислювальних операцій при підвищенні порядку простору. Виключення коефіцієнтів у прямому ході методу потрібно проводити над матрицею (9).

, (9)

де k - розмірність простору, для якого розраховується крива,

А - матриця коефіцієнтів,

Вi - вектор-стовпчик вільних членів системи для i-ої розмірності простору.

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

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

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

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

Таблиця 1. Обчислювальна складність основних операцій методики для випадку кривої побудованої по чотирьом точкам

Частина методики	Кількість операцій множення	Кількість операцій додавання	Кількість операцій ділення	Кількість повторів операції
Розрахунок значення NURBS-кривої	10	6	1	Лінійно залежить від розмірності простору. Залежить від збіжності ітераційного процесу методу оптимізації та вибору початкових наближень
Складання системи лінійних рівнянь (матриця коефіцієнтів)	20	2	0	Залежить від збіжності ітераційного процесу методу оптимізації
Складання системи лінійних рівнянь (матриця вільних членів)	8	8	0	Лінійно залежить від розмірності простору. Залежить від збіжності ітераційного процесу методу оптимізації
Пошук контрольних точок (розв'язання системи лінійних рівнянь)	6	3	2	Лінійно залежить від розмірності простору.

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

У четвертому розділі розроблено програмне забезпечення, яке реалізує розроблені методики та алгоритми, а також проведені тести швидкодії алгоритмів на ЕОМ.

Для методу інтерполяції на основі NURBS-кривих розроблено UML діаграму компонентів, яка відображає взаємозв'язок функцій програми (файлів пакету прикладних програм МАTLAB). Тестування методу проводилось з багаточленами, тригонометричними функціями, дробово-раціональними функціями, а також з функцією Рунге. Тестування проводилось з методом сплайнової інтерполяції, який входить до пакету MATLAB та методом Лагранжа. Порядок похибок розробленого методу збігається з методом сплайн інтерполяції, але на тестах із дробово-раціональними функціями метод NURBS дає значно меншу похибку. Проведений аналіз обчислювальної складності методів показав, що для декількох точок метод сплайнової інтерполяції є менш складним, але він має досить високу обчислювальну складність на великих обсягах вхідних даних. Це пов'язано із необхідністю у розв'язанні системи лінійних рівнянь, обчислювальна складність якої нелінійно зростає із збільшенням кількості невідомих. При додаванні однієї точки до вихідного набору кількість невідомих зростає на 4. Навідміну від цього, метод на основі NURBS-кривих оперує значно меншою кількістю вихідних даних при порівняно однаковій точності результату.

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

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

загальні висновки по роботі

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

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

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

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

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

6. Запропоновано новий метод побудови кусково-білінійної поверхні на основі методу одновимірної інтерполяції Катмулла-Рома. Цей метод має переваги у швидкодії розрахунку кубічного сплайну у порівнянні із класичними методами кубічної сплайн інтерполяції і тому може бути застосований для побудови інтерполяційних поверхонь. На основі методу розроблено алгоритм та програмне для забезпечення збільшення зображень, дослідним шляхом оцінені похибки інтерполяції в порівнянні із класичним методом Bspline інтерполяції та методом інтерполяції зображень пакету прикладних програм Adobe Photoshop CS4. Навідміну від існуючих методів, розроблений метод дає можливість розрахувати аналітичний вигляд сплайнів, що складають поверхню. Ця відмінність дає можливість підвищити швидкодію методів, які потребують безперервного отримання результатів обробки тих самих даних з різною дискретизацією.

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

Публікації за темою дисертаційної роботи

1. Юдін О. О. Різницеві методи та сплайни в задачах багатовимірної інтерполяції: Монографія / Квєтний Р. Н., Дементьєв В. Ю., Машницький М.О., Юдін О. О. -- Вінниця : УНІВЕРСУМ-Вінниця, 2009. -- 92 с.

2. Юдін О. О. Застосування інтерполяції сплайном Катмулла-Рома для збільшення зображень / О. О. Юдін // Інформаційні технології та комп'ютерна інженерія. -- 2008. -- № 1(11). -- С. 188--194.

3. Юдін О. О. Оптимізація вагових коефіцієнтів інтерполяції NURBS-кривими / О. О. Юдін, Р. Н. Квєтний // Вісник Вінницького політехнічного інституту. -- 2009. -- № 4. -- С. 69--72.

4. Юдін О. О. Нормалізована лінійна інтерполяція при моделюванні руху по сфері у багатовимірному просторі / О. О. Юдін // Вісник Вінницького політехнічного інституту. -- 2007. -- № 1. -- С. 89--91.

5. Юдин О. А. Расширение интерполяции по Лагранжу с использованием Кривих Безье / Юдин О. А. // Нові технології. Науковий вісник Інституту економіки та нових технологій. -- 2005. -- № 3(9). -- С. 117--120.

6. Юдін О. О. Нормалізована лінійна інтерполяція при моделюванні руху по сфері у багатовимірному просторі / Юдін О. О. // Автоматика-2006: Тринадцята міжнародна науково-технічна конференція з автоматичного управління, 25-28 вересня 2006 р.: тези доповіді. -- Вінниця, 2006. -- С. 21.

7. Yudin O. Modern numerical methods of data processing and modelling / R. Kvetny, I. Bogach, O. Yudin // PHOTONICS-ODS 2005: International Conference on Optoelectronics Information technologies, 27-28 April 2005: сonference materials. -- Vinnitsa, 2005. -- Р. 80--81.

8. Свідоцтво про реєстрацію авторського права на твір. Україна. №28123. Комп'ютерна програма «Програмний модуль побудови інтерполяційних моделей географічних поверхонь» / Мокін В. Б., Боцула М. П., Юдін О. О. Дата реєстрації 25.03.2009. -- 4 с.

9. Свідоцтво про реєстрацію авторського права на твір. Україна. №29254. Комп'ютерна програма «Програмний модуль оптимізації функцій, які мають розриви частинних похідних» / Юдін О. О. Дата реєстрації 19.06.2009. -- 4 с.

АнотаціЯ

Юдін О. О. Інтерполяція багатовимірних функцій в просторі та часі. -- Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 01.05.02 - математичне моделювання та обчислювальні методи. -- Вінницький національний технічний університет, Вінниця -- 2010.

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

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

Ключові слова: інтерполяція, багатовимірний простір, NURBS криві, сплайни, кватерніони, методи оптимізації.

Аннотация

Юдин О. А. Интерполяция многомерных функций в пространстве и времени. -- Рукопись.

Диссертация на соискание учёной степени кандидата технических наук по специальности 01.05.02 - математическое моделирование и вычислительные методы. -- Винницкий национальный технический университет. -- Винница. -- 2010.

Диссертация посвящена интерполяции функций многих переменных в пространстве и времени, а также повышению эффективности методов интерполяции.

В работе исследованы существующие методы интерполяции функций одной и многих переменных. Исходя из проведённого анализа, определены направления для возможного усовершенствования методов интерполяции, разработки многомерных аналогов существующих методов и расширения области их применения. В связи с быстрым развитием компьютерной техники появляются возможности обработки больших массивов данных в режиме реального времени. Актуальность разработки и усовершенствования методов интерполяция обусловлена стремительным развитием компьютерной графики, медицины, гео-информационных систем.

В работе разработан подход для интерполяции с помощью NURBS-кривой, который дал возможность расширить область применения данного вида кривой для многомерных пространств. Также была разработана методика повышения точности метода за счет оптимизации весовых коэффициентов кривой, которые задают влияние контрольных точек на кривую и дают возможность получить семейство интерполяционных рациональных функций. Исследовав функцию погрешности, построенную на основе метода наименьших квадратов, был разработан метод оптимизации для функций с разрывом частных производных. Метод оптимизации основан на методе наискорейшего спуска и позволяет исключить недостатки классических методов оптимизации применимо к данному типу функции. В отличие от классического подхода, разработанный подход позволяет расширить область применения данного вида кривой на трехмерное и многомерные пространства. Параметрическая форма кривой дает возможность описывать траектории движения объектов в пространстве в зависимости от времени.

Также был исследован метод сферической интерполяции в многомерных пространствах и его применение на примере интерполяции кватернионов для описания поворотов в компьютерной графике с учётом времени. В диссертации разработана модификация сферической линейной интерполяции для уменьшения вычислительной сложности метода. Проведено замену сферической линейной интерполяции на нормализированную классическую линейную интерполяцию. На основе формулы погрешности данной замены разработано методику проведения интерполирования с заданной максимальной погрешностью.

Также в работе создан метод бикубической интерполяции на основе сплайна Катмулла-Рома. Этот сплайн имеет преимущества по количеству вычислительных операций в сравнении с другими методами интерполяции. Разработка его двумерного аналога метода даёт возможность интерполяции поверхностей по регулярной сетке значительно эффективней, чем при помощи существующих методов сплайн интерполяции. В работе рассмотрены и сформулированы граничные условия сплайнов, что позволяет получить полную интерполяционную картину.

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

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

Ключевые слова: интерполяция, многомерное пространство, NURBS кривые, сплайны, кватернионы, методы оптимизации.

Abstract

Yudin O. O. Interpolation of multidimensional functions in space and time. -- A manuscript.

Thesis for achievement of a candidate's degree on technical sciences on a specialty 01.05.02 - mathematical modeling and numerical methods. -- Vinnytsia National Technical University. -- Vinnytsia. -- 2010.

The thesis is devoted to the interpolation functions of several variables in space and time, and increasing of efficiency of interpolation methods.

In the work was developed an approach for interpolation using the NURBS-curve which gave the opportunity to expand the scope of this type of curve. The accuracy of the method was improved by optimizing the weight coefficients of NURBS. Also has been studied and carried out the linearization of the spherical linear interpolation. Use of the normalized linear interpolation provide the performance enhancement of the method. A method of bicubic spline interpolation was developed on the basis of Catmull-Rome spline, which has advantages in the number of computing operations in comparison with other methods of interpolation. Considered and formulated the splines boundary conditions.

Key words: interpolation, multidimensional space, NURBS curves, splines, quaternions, optimization methods.

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

...