Розробка методів і алгоритмів інтерполяції самоподібними множинами

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

ВІННИЦЬКИЙ ДЕРЖАВНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ

КОСТРОВА КАТЕРИНА ЮРІЇВНА

УДК 658.512.011.56; 519.21

РОЗРОБКА МЕТОДУ І АЛГОРИТМІВ ІНТЕРПОЛЯЦІЇ САМОПОДІБНИМИ МНОЖИНАМИ

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

Автореферат

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

кандидата технічних наук

Вінниця - 2000

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

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

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

Офіційні опоненти: доктор технічних наук, професор Лежнюк Петро Дем'янович, Вінницький державний технічний університет, завідувач кафедри електричних станцій та систем, кандидат фізико-математичних наук, старший науковий співробітник, Фінін Георгій Семенович, Міжнародний Соломонів Університет, м. Київ, перший проректор

Провідна установа: Державний університет "Львівська політехніка", кафедра систем автоматизованого проектування, Міністерство освіти і науки України, м. Львів

Захист відбудеться 15 вересня 2000 р. о 9-30 годині на засіданні спеціалізованої вченої ради Д 05.052.01 у Вінницькому державному технічному університеті за адресою: 21021, м. Вінниця, Хмельницьке шосе, 95.

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

Автореферат розісланий 29 червня 2000 р.

Вчений секретар

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

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

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

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

1) дозволяють працювати з нерівновіддаленими вузлами інтерполяції;

2) застосовні для інтерполяції не гладких функцій;

3) не вимагають значних обчислювальних витрат.

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

Слід також відзначити, що відомі пакети фрактальної обробки даних (наприклад, програмне забезпечення американської фірми Iterated Systems Inc.) призначені для архівації зображень і не дозволяють вирішити стандартну задачу інтерполяції в двовимірному евклідовому просторі.

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційне дослідження проводиться згідно з напрямком досліджень за держбюджетною науково-дослідною роботою на тему "Розробка алгоритмічних засад і програмних засобів моделювання інформаційних систем" (номер у державному реєстрі - 0197У012883), що затверджено Міністерством освіти України на 1997-1999 роки, яка виконувалась у Вінницькому державному технічному університеті протягом зазначеного періоду.

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

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

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

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

2. Дослідження методу інтерполяції самоподібними множинами в двовимірному евклідовому просторі.

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

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

5. Застосування розроблених методу й алгоритмів для поліпшення якості збільшених зображень.

Наукова новизна отриманих результатів:

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

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

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

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

Запропоновані метод і алгоритми інтерполяції використані для підвищення якості збільшених зображень у програмному продукті для людей з вадами зору L&H Magnifier, що розроблюється компаніями "Комп'ютерні Мультимедіа Системи", Україна і Lernaut & Hauspie, Бельгія.

Створено спеціалізоване програмне забезпечення Self-Affine Interpolation - SAI для інтерполяції самоподібними та самоафінними множинами, що використовується при вивченні курсу "Обчислювальні методи і застосування ЕОМ" (розділ "Методи обробки даних") у Вінницькому державному технічному університеті.

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

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

Особистий внесок здобувача. Серед приведених нижче в списку опублікованих праць за темою дисертації в співавторстві здобувачем опубліковано роботи за номерами 2, 7, 10, 11. У роботі 2 дисертантом зроблено визначення самоподібних та самоафінних множин, аналіз різних ступенів самоподібності множин. Подано головну ідею інтерполяції самоподібними множинами. Описано застосування цього виду інтерполяції для стиску та відновлення звукових файлів. У роботі 7 дисертантом описано конкретні алгоритми інтерполяції самоподібними множинами. Зроблено висновок щодо вибору різних видів алгоритмів відносно ступеня осциляції функції. У роботі 10 дисертантом доведено ефективність застосування фрактальної обробки графічної інформації, наведено діаграми та рисунки. У роботі 11 дисертантом представлено графічні матеріали роботи алгоритмів моделювання фрактальних множин, дано порівняльний аналіз існуючих пакетів фрактального моделювання та принципів кодування графічних зображень. Розроблено пакет програм моделювання фрактальних множин на базі фіксованої кількості самоподібних перетворень.

Апробація результатів дисертації. Результати досліджень, викладені в дисертаційній роботі, пройшли апробацію на семи наукових конференціях і симпозіумах: ІІІ науково-технічна конференція "Вимірювальна та обчислювальна техніка в технологічних процесах і конверсії виробництва" (м. Хмельницький, 1995), ІІІ міжнародна науково-технічна конференція "Контроль и управление в технических системах" (м. Вінниця, 1995), науково-технічна конференція з міжнародною участю "Приборостроение-96". (м. Вінниця - Судак, 1996), I міжнародний електронний форум "Электроника и молодежь в XXI веке" (м. Харків, 1997), IV міжнародна науково-технічна конференція "Контроль и управление в технических системах (КУТС-97)" (Вінниця, 1997), 20th International Scientific Symposium of students and young research workers (Zielona Gora, 1998).

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

Обсяг і структура дисертації. Дисертаційна робота складається з вступу, 4 розділів, загальних висновків, списка використаних літературних джерел і 16 додатків. Загальний обсяг дисертації 164 сторінки, з яких основний зміст викладено на 124 сторінках друкованого тексту, містить 65 рисунків, 4 таблиці. Список використаних джерел складається з 147 найменувань.

ОСНОВНИЙ ЗМІСТ РОБОТИ

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

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

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

На основі проведеного аналізу зроблено такі висновки:

1. Є доцільною розробка методу й алгоритмів інтерполяції, що дозволяв би:

- працювати з нерівновіддаленими вузлами інтерполяції;

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

- використовувати в якості вузлів інтерполяції як окремі точки простору, так і множини, що належать цьому просторові;

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

2. Обробка даних на основі фрактального аналізу дозволяє створити метод і алгоритми, що задовольняють даним вимогам.

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

Нехай, - деяка впорядкована скінчена множина двовимірного евклідового простору, а - оператор Хатчинсона, який задовольняє таким умовам:

1) послідовність множин

, , … , ,

є збіжною відносно метрики Хаусдорфа;

2) множина належить множині, отриманій на -ій ітерації

,

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

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

Нехай, - скінчена впорядкована множина точок двовимірного евклідового простору.

Визначимо -співвідношення як

, , ;

, , ;

, , ;

, , ;

, , ,

де - кут між векторами та.

Накладемо такі обмеження на елементи множини :

1) , ;

2) ;

3) ,

де - самоподібна розмірність множини .

Визначимо тепер афінні перетворення у такий спосіб:

, ,

де - паралельне перенесення на вектор;

- поворот на кут відносно центру;

- гомотетія з центром в і коефіцієнтом.

Нехай - множина скінчених множин евклідового простору і. Визначимо оператор Хатчинсона , побудований на основі афінних перетворень:

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

Розглянемо таку послідовність множин:

, , , …, , …

де,.

Доведено, що:

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

2) інтерполяційні множини Хатчинсона , , є самоподібними фрактальними множинами;

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

,

Де , , .

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

, ,

причому виконуються такі умови:

1) , ;

2) множини та , , попарно не перекривають одна одну;

3) , ,

де - афінні перетворення з коефіцієнтом гомотетії та коефіцієнтом стиску відносно однієї осі.

Розроблено дві модифікації методу:

1) інтерполяція самоподібними множинами на підставі декількох множин з однією загальною точкою для кожної пари множин;

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

У першому випадку початкову множину подають як об'єднання підмножин

або

, .

У другому випадку початкову множину подають як об'єднання підмножин

або

.

На підставі кожної з підмножин будується інтерполяційна множина Хатчинсона потрібного рангу:

,

,

,

,

.

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

Доведено, що:

1) інтерполяційні множини Хатчинсона є об'єднаними самоподібними фрактальними множинами;

2) похибка модифікацій методу інтерполяції самоподібними множинами визначається за формулою:

,

де ,

,

,.

Обидві модифікації узагальнено для об'єднаних самоафінних множин.

В третьому розділі дано опис розроблених алгоритмів інтерполяції самоподібними та самоафінними множинами (АСП- та АСА-Алгоритмів) та їх об'єктно-орієнтованого дизайну.

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

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

Проведено порівняння за точністю і складністю розроблених АСП- і АСА-Алгоритмів і ряду поширених алгоритмів (інтерполяції за Лагранжем - L(x), сплайн-інтерполяції - Sp(x), лінійної інтерполяції - Lin(x)) для декількох тестових функцій (багаточлен, гармонійні коливання, фрактальна функція). На рис. 4. наведено графіки середніх значень експериментальних похибок для всіх алгоритмів по всіх тестових функціях.

На підставі проведених досліджень зроблено такі висновки:

1) для кожної тестової функції існують як мінімум два придатних АСП- або АСА-Алгоритми;

2) для інтерполяції фрактальних функцій АСП- або АСА-Алгоритми є єдиним коректним розв'язанням - їхня похибка набагато менше (на 11.83), ніж у стандартних алгоритмів;

3) мінімальна похибка придатних АСП- або АСА-Алгоритмів при інтерполяції стандартних функцій приблизно дорівнює мінімальній похибці стандартних алгоритмів (різниця варіюється від 0.33 до 1.5);

4) середня похибка АСП- або АСА-Алгоритмів (варіюється від 3.54 до 4.79) порівняна із середньою похибкою кращого зі стандартних алгоритмів (4.17);

5) для одержання найбільш точних результатів інтерполяції при виборі АСП- або АСА-Алгоритму варто використовувати рекомендації щодо вибору АСП- чи АСА-Алгоритму.

Проведено порівняльний аналіз АСП- і АСА-Алгоритмів та деяких відомих алгоритмів за швидкодією, на підставі якого зроблено такі висновки:

1) серед АСА- і АСП-Алгоритмів максимальну складність має АСА-Алгоритм, мінімальну - АСП-Т1-Алгоритм;

2) серед усіх порівнюваних алгоритмів інтерполяції максимальну складність має АСА-Алгоритм, мінімальну - АСП-Т1-Алгоритм;

3) усі стандартні алгоритми мають меншу складність, ніж АСП-Алгоритм і АСА-Алгоритм;

4) усі стандартні алгоритми мають більшу складність, ніж АСА-Т1-Алгоритм, АСП-Т2-Алгоритм і АСА-Т1-Алгоритм;

5) АСП-Т1-Алгоритм і АСП-Т2-Алгоритм виконують у середньому на 46% менш складних обчислювальних операцій (множення і ділення), ніж алгоритм лінійної інтерполяції - найменш складний алгоритм серед усіх стандартних алгоритмів.

Четвертий розділ присвячено практичному використанню розроблених методу та алгоритмів.

Описано спеціалізоване програмне забезпечення "Self-Affine Interpolation" - SAI, що реалізує усі АСП- і АСА-Алгоритми. Сформульовано принципи, яким повинно відповідати SAI; показано, що створений програмний продукт відповідає всім необхідним вимогам.

Описано дві методики роботи з SAI:

1) методика використання, що містить рекомендації по застосуванню SAI і посібник користувача;

2) методика подальшої розробки, що містить опис модулів SAI і лістінги програмного коду.

Дано поняття "технологія згладжування зображень" (anti-aliasing technology), описані причини виникнення перекручувань у збільшених зображеннях. Проаналізовано основні алгоритми технології згладжування зображень з урахуванням їх переваг та недоліків.

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

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

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

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

ВИСНОВКИ

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

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

На основі проведеного аналізу сформульовано основні задачі, які розв'язані в роботі.

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

1) дозволяє працювати з нерівновіддаленими вузлами інтерполяції;

2) застосовується для інтерполяції не гладких і скрізь недиференційованих функцій;

3) використовує як вузли інтерполяції як окремі точки простору, так і множини, що належать цьому просторові.

Доведено, що процес побудови інтерполяційних множин Хатчинсона є збіжним процесом і має фіксовану похибку, визначену відповідно до теореми Стефана Банаха про нерухому точку. Доведено, що інтерполяційні множини Хатчинсона є самоподібними фрактальними множинами.

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

Розглянуто дві модифікації методу інтерполяції самоподібними множинами:

1) інтерполяція самоподібними множинами на підставі декількох множин з однією загальною точкою для кожної пари множин;

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

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

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

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

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

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

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

Розроблено програмне забезпечення "Self-Affine Interpolation" - SAI, що реалізує усі створені алгоритми. Описано методику використання SAI та методику подальшої розробки. Проаналізовано проблеми, що виникають при інтерполяції самоподібними множинами, а також можливі шляхи їх вирішення.

Дано поняття "технологія згладжування зображень" (anti-aliasing technology), описані причини виникнення перекручувань у збільшених зображеннях. Проаналізовано основні алгоритми технології згладжування зображень з урахуванням їх переваг та недоліків.

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

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

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

Розроблені метод і алгоритми інтерполяції пройшли успішну апробацію на фірмах "Комп'ютерні Мультимедіа Системи", Україна та Lernaut & Hauspie, Бельгія, де їх було використано для поліпшення якості збільшених зображень у спеціалізованому програмному продукті для людей з вадами зору.

СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Кострова К.Ю. Алгоритми фрактальної інтерполяції // Вісник ВПІ. - 1997. - № 2. - С. 27-30.

2. Квєтний Р.Н., Кострова К.Ю. Стиск звуку на базі інтерполяції самоподібними множинами // Вимірювальна та обчислювальна техніка в технологічних процесах (Технологічний університет Поділля, м. Хмельницький). - 1998. - № 4(6). - С.91-94.

3. Кострова К.Ю. Алгоритмічні інтерполяції самоподібними множинами // Вимірювальна та обчислювальна техніка в технологічних процесах (Технологічний університет Поділля, м. Хмельницький).- 1999. - № 1(7). - С.30-34.

4. Catherine Kostrova. Fractal Data Processing // 20 International Scientific Symposium of students and young research workers. - Zielona Gora (Poland).- 1998.- V. III: Informatics. - P. 42-44.

5. Кострова Е.Ю. Алгоритмы обработки данных на основе самоподобных множеств // Приборостроение - 99. Труды филиала МГТУ им. Н.Э. Баумана. Спецвыпуск. - Калуга: Изд. Н. Бочкаревой. - 1999. - С.191-198.

6. Кострова Е.Ю. Численное интегрирование фрактальным методом // Праці 4-ої Міжнародної наук.-техн.конф. "Контроль і управління в технічних системах" (КУТС -97). - Т.1. - Вінниця: УНІВЕРСУМ-Вінниця. - 1997. - С. 193-196.

7. Кветний Р.Н., Кострова Е.Ю. Интерполяция самоподобными множествами // Праці 4-ої Міжнародної наук.-техн.конф. "Контроль і управління в технічних системах" (КУТС-97). - Т.1. - Вінниця: УНІВЕРСУМ-Вінниця.- 1997. - С. 197-201.

8. Кострова Е.Ю. Влияние значения крутизны кривой на выбор алгоритма фрактальной интерполяции // Материалы 1-го Международного молодежного форума "Электроника и молодежь в ХХІ веке". - Харьков. - 1997.- С.173.

9. Кострова Е.Ю. Разработка семейства алгоритмов фрактальной интерполяции // Материалы 1-го Международного молодежного форума "Электроника и молодежь в ХХІ веке". - Харьков. - 1997. - С.267.

10. Квєтний Р.Н., Кострова К.Ю. Застосування фрактальних алгоритмів в засобах обробки експериментальних даних на ЕОМ // Праці 3-ої наук.-техн. конф."Вимірювальна та обчислювальна техніка в технологічних процесах і конверсії виробництва". - Хмельницький. - 1995. - С.192.

11. Квєтний Р.Н., Кострова К.Ю. Застосування фрактальної обробки інформації при математичному моделюванні систем контролю та управління // Тезисы докладов Ш Международной научно - технической конференции "Контроль и управление в технических системах". - Винница.- 1995.- Ч.1.- С.104.

12. Кострова Е.Ю. Разработка алгоритма фрактальной интерполяции // Тезисы докладов научн.-техн. конф. с международным участием "Приборостроение - 1996". - Винница-Судак. - 1996. - Ч.2. - С.10.

13. Свідоцтво про державну реєстрацію прав автора на твір ПА № 1275 від 15.07.98. Комп'ютерна програма "Алгоритм інтерполяції на основі самоподібних множин" / Кострова К.Ю.

АНОТАЦІЇ

Кострова К.Ю. Розробка методу та алгоритмів інтерполяції самоподібними множинами. - Рукопис.

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

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

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

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

Розроблені метод і алгоритми інтерполяції використані для підвищення якості збільшених зображень у програмному продукті для людей з вадами зору L&H Magnifier.

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

Kostrova C.Y. The Development of the Method and Algorithms of the Interpolation based on the Self-Similar Multitudes. - Manuscript.

Thesis for the candidate's degree by the specialty 01.05.02 - mathematical modeling and computer methods/ - Vinnitsa State Technical University, Vinnitsa, 2000.

The dissertation is devoted to the development of the method and algorithms of the interpolation based on the self-similar multitudes. The method and algorithms are described for the 2-dimensional Euclidean space.

The suggested method of the interpolation consists in finding the defined Hutchinson operator and building the necessary interpolation multitude based on this operator.

Seven algorithms are developed based on the suggested method. It's proved that their accuracy and speed aren't worse and sometimes better than the same characteristics of the well-known interpolation algorithms (the suggested algorithms are quicker by 40-50 percents).

The new approach to the anti-aliasing technology is described. It is used in L&H Magnifier product - the special software for low-vision people.

Key words: interpolation, data processing, self-similar multitude, self-affine multitude, fractal, Hutchinson operator, Hausdorff metric, anti-aliasing technology.

Кострова Е.Ю. Разработка метода и алгоритмов интерполяции самоподобными множествами. - Рукопись.

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

Диссертация посвящена разработке метода и алгоритмов интерполяции самоподобными множествами в двумерном эвклидовом пространстве.

Предложен метод интерполяции самоподобными множествами, который состоит в нахождении оператора Хатчинсона и построении при помощи этого оператора интерполяционного множества нужного ранга. Доказано, что интерполяционные множества Хатчинсона являются самоподобными фрактальными множествами, а погрешность метода интерполяции определяется согласно т. С. Банаха о неподвижной точке. Метод интерполяции самоподобными множествами обобщен для самоафинных множеств.

Рассмотрены две модификации метода: интерполяция самоподобными (самоафинными) множествами на основе нескольких множеств с одной общей точкой для каждой пары множеств и интерполяция самоподобными (самоафинными) множествами на основе нескольких множеств с двумя общими точками для каждой пары множеств.

На основании предложенного метода созданы алгоритмы интерполяции (7 алгоритмов). Описан их объектно-ориентированный дизайн, выведены формулы для расчета количества вычислительных операций, проведено сравнение разработанных алгоритмов и ряда известных алгоритмов (интерполяция по Лагранжу, сплайн-интерполяция). Показано, что точность и быстродействие предложенных алгоритмов не уступает, а зачастую и превышает аналогичные показатели известных алгоритмов примерно на 40-50 процентов.

На основании предложенных алгоритмов создано специализированное программное обеспечение Self-Affine Interpolation для изучения интерполяции самоподобными и самоафинными множествами, для которого написаны методика пользователя и методика разработчика.

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

Метод и алгоритмы интерполяции самоподобными множествами использованы для улучшения качества увеличенных изображений в программном продукте для слабовидящих людей L&H Magnifier, разрабатываемого компаниями "Компьютерные Мультимедиа Системы", Украина и Lernaut & Hauspie, Бельгия. Тестирование L&H Magnifier показало адекватность предложенного подхода к сглаживанию контуров увеличенных изображений.

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

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