Варіаційна модель задачі просторової інтерполяції статичних зображень
Існуючі методи просторової інтерполяції цифрових зображень. Розробка адаптивного методу інтерполяції зображень, основу якого складає відтворення їх топографічних карт. Алгоритм каркасної інтерполяції зображень. Варіаційна модель задачі реконструкції.
| Рубрика | Экономико-математическое моделирование |
| Вид | автореферат |
| Язык | украинский |
| Дата добавления | 26.07.2014 |
| Размер файла | 249,4 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
НАЦІОНАЛЬНА МЕТАЛУРГІЙНА АКАДЕМІЯ УКРАЇНИ
УДК 004.932
ВАРІАЦІЙНА МОДЕЛЬ ЗАДАЧІ ПРОСТОРОВОЇ ІНТЕРПОЛЯЦІЇ СТАТИЧНИХ ЗОБРАЖЕНЬ
01.05.02 - Математичне моделювання та обчислювальні методи
Автореферат
дисертації на здобуття наукового ступеня
кандидата технічних наук
Сердюк Марина Євгеніївна
Дніпропетровськ - 2008
Дисертацією є рукопис.
Робота виконана на кафедрі диференціальних рівнянь механіко-математичного факультету Дніпропетровського національного університету Міністерства освіти і науки України.
Науковий керівник:доктор фізико-математичних наук, професор Когут Петро Ілліч, Дніпропетровський національний університет, професор кафедри диференціальних рівнянь, м. Дніпропетровськ.
Офіційні опоненти: доктор технічних наук, професор Корчинський Володимир Михайлович, Дніпропетровський національний університет, завідувач кафедри електронних засобів телекомунікацій, м. Дніпропетровськ;
доктор технічних наук, професор Шумейко Олександр Олексійович, Дніпродзержинський державний технічний університет, професор кафедри програмного забезпечення та обчислювальної техніки, м. Дніпродзержинськ.
Захист відбудеться “18” червня 2008 р. о “12:30” годині на засіданні спеціалізованої вченої ради Д 08.084.01 у Національній металургійній академії України за адресою: 49600, м. Дніпропетровськ, пр. Гагаріна, 4.
З дисертацією можна ознайомитися у бібліотеці Національної металургійної академії України за адресою: 49600, м. Дніпропетровськ, пр. Гагаріна, 4. інтерполяція адаптивний зображення топографічний
Автореферат розісланий “16” травня 2008 р.
Вчений секретар
спеціалізованої вченої ради О.І. Дерев'янко
ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ
Актуальність теми. Сучасний стрімкий розвиток цифрових відео-технологій та технологій швидкісної передачі графічної інформації ставить проблему покращення зорової якості цифрових зображень як одну з найактуальніших в цій області. В першу чергу це обумовлено тим, що графічний тип інформації є найбільш сприйнятним та інформативним для психовізуальної системи людини. Тому важливою задачею в даному аспекті є підвищення якості такої інформації, збереження її реалістичності після перетворень, усунення цифрових спотворень.
Одним із основних перетворень графічної інформації є зміна просторових розмірів зображень, або інакше, їх просторова інтерполяція. Такі перетворення використовуються як в анімаційних проектах, так і в практичних задачах обробки зображень (проблеми розпізнавання образів, медична діагностика, астрономія та молекулярна біологія, картографія та автонавігація, космічне фотосканування, та ін.). Методи зміни просторових розмірів зображень лежать в основі алгоритмів апаратного масштабування, які використовуються при відтворенні графічної інформації в пристроях з фіксованою роздільчою здатністю (плазмові панелі, рідко-кристалічні дисплеї). Отже, візуальна якість результуючих зображень після зміни їх просторових розмірів суттєво залежить від методів просторової інтерполяції. Одним із основних недоліків більшості відомих на сьогодні алгоритмів та методів просторової інтерполяції цифрових зображень є поява в результуючих зображеннях таких візуальних спотворень, як „сходинковий” ефект в контурних лініях, дублюючі контури, недостатня чіткість. Отже, актуальною є розробка нових методів просторової інтерполяції зображень та нових підходів до побудови алгоритмів зміни просторової щільності пікселів, які б були адаптованими до широкого класу цифрових зображень та дозволяли зберегти достатньо високу якість результуючих зображень.
Зв'язок роботи з науковими програмами, планами, темами. Робота виконана у відповідності до наукового напряму розвитку “Новітні комп'ютерні засоби та технології інформатизації суспільства” відповідно закону України “Про пріоритетні напрями розвитку науки і техніки” №2623-III від 11.07.2001р.
Обраний напрямок досліджень пов'язаний з тематикою держбюджетних науково-дослідницьких робіт у Дніпропетровському національному університеті залізничного транспорту (тема № 33127.06.07 - „Проведення робіт по технічному діагностуванню вагонів експлуатаційного парку Укрзалізниці, термін служби яких закінчився, на предмет продовження терміну їх експлуатації” ) та з напрямком досліджень кафедри диференціальних рівнянь Дніпропетровського національного університету.
Мета і задачі дослідження. Метою дисертаційної роботи є розробка методу просторової інтерполяції статичних зображень, який би відрізнявся збереженням достатньої гладкості контурних ліній, плавністю тональних переходів і достатньою різкістю та чіткістю результуючого зображення. Для досягнення поставленої мети вирішувались наступні задачі.
1. Аналіз існуючих методів просторової інтерполяції цифрових зображень.
2. Розробка математичної моделі зображень, яка б узгоджувалася з основними постулатами математичної морфології та особливостями психовізуальної системи людини.
3. Розробка адаптивного методу інтерполяції зображень, основу якого складає відтворення їх топографічних карт.
4. Розробка алгоритму каркасної інтерполяції зображень.
5. Розробка та дослідження варіаційної моделі задачі реконструкції зображення поза межами його каркасу.
6. Розробка та дослідження апроксимативної моделі задачі реконструкції зображення.
7. Експериментальне дослідження отриманих результатів на прикладах масштабування зображень за допомогою розробленого методу та з використанням відомих методів. Порівняння отриманих результатів як за візуальною якістю, так і за формальними оцінками їх якості.
Об'єкт дослідження - просторова інтерполяція статичних цифрових зображень в растрових форматах.
Предмет дослідження - математичні моделі та методи для перетворень просторових розмірів (тобто зміни щільності пікселів) цифрових зображень.
Методи дослідження. Для вирішення поставлених задач дисертації були використані основні положення теорії цифрових зображень, теорії метричних просторів, теорії міри та функцій з обмеженою варіацією, методи функціонального аналізу, основні положення варіаційного числення, теорії сплайнів.
Наукова новизна отриманих результатів. Запропоновано новий підхід до побудови алгоритмів просторової інтерполяції зображень, який базується на відтворенні частки топографічної карти зображення, що містить всі пікселі вихідного малюнка, відтворенні каркасу зображення і значень на ньому породжуючої функції та реконструкції зображення на всій області за інтерпольованими значеннями на каркасі.
Таким чином, наукова новизна роботи визначається наступними теоретичними й практичними результатами:
- здійснено подальший розвиток методів просторової інтерполяції статичних зображень;
- запропоновано новий підхід до побудови алгоритмів просторової інтерполяції зображень, який поєднує ідеї адаптивних методів обробки зображень та методів варіаційного аналізу;
- введено поняття каркасу зображення та розроблено принципово новий алгоритм його адаптивного конструювання для широкого класу цифрових зображень;
- отримано аналітичне подання для шеститочкового інтерполяційного сплайну з мінімальною локальною кривизною, залучення якого дозволяє отримати візуально кращі результати адаптивного відтворення каркасу та інтерполяції породжуючої функції зображення на ньому (на відміну від нині існуючих підходів);
- вперше запропонована постановка задачі реконструкції зображення за його каркасною інтерполяцією та наведена її варіаційна модель; доведено існування розв'язків поставленої задачі на класі функцій з обмеженою варіацією;
- запропонована апроксимативна модель задачі реконструкції зображень, яка покладена в основу побудови чисельних процедур їх просторової інтерполяції. Встановлено факт розв'язності відповідної варіаційної задачі та доведено, що розв'язки таких задач прямують у відповідних топологіях до розв'язків вихідної задачі реконструкції зображень;
- проведено порівняльний аналіз результатів просторової інтерполяції, одержаних за допомогою запропонованого методу та існуючими методами, реалізованими в програмах "Photoshop" і "IrfanView".
Практичне значення одержаних результатів. Практична вагомість отриманих результатів роботи полягає в наступному:
- запропоновано алгоритмічну процедуру адаптивного конструювання каркасів статичних зображень;
- розроблено алгоритм відтворення породжуючих функцій статичних зображень в околі їх топографічних карт;
- розроблено апроксимативну модель задачі реконструкції зображень та на її основі створено алгоритм розв'язання цієї задачі;
- запропонований в роботі підхід до розв'язання задачі просторової інтерполяції статичних зображень покладено в основу створеного програмного забезпечення "Space Interpolation".
Результати досліджень, які отримані в дисертаційній роботі, впроваджено в ГНДЛ кафедри „Вагони та вагонне господарство” Дніпропетровського національного університету залізничного транспорту для аналізу зображень елементів рам вагонів з метою оцінки наявності в них дефектів, що підтверджується актом впровадження. Результати дисертаційної роботи також використані підприємством ТОВ “Єкатеринославська мануфактура” в програмному забезпеченні для допечатної обробки зображень при виготовленні поліграфічної продукції, а також Центром стоматології “Аранта” для аналізу рентгенограм лицевого скелету, що підтверджується відповідними актами впровадження.
Особистий внесок здобувача. Всі основні результати дисертаційної роботи були отримані автором особисто. У роботах, що опубліковані у співавторстві, здобувачу належить: у статтях [1], [2] - алгоритм каркасної інтерполяції статичних зображень, аналітичне подання для шеститочкового інтерполяційного сплайну з мінімальною локальною кривизною; у статті [3] - дослідження основних властивостей оператора кривизни на множині функцій з обмеженою варіацією; у статті [4] - математична модель задачі реконструкції зображень за їх каркасною інтерполяцією, дослідження її розв'язності.
Апробація результатів. Основні наукові результати й положення дисертаційної роботи були представлені та обговорені на наукових конференціях “Дни науки - 2007”, “Научное пространство Европы - 2007” (м. Дніпропетровськ), на міжнародній науково-практичній конференції „Современные информационные технологии на транспорте, в промышленности и образовании” (м. Дніпропетровськ, 2007), на міжнародній конференції “Компьютерная математика в образовании и научных исследованиях” (м. Феодосія, 2007), 5-й Міжнародній науково-практичній конференції „Математичне та програмне забезпечення інтелектуальних систем” (м. Дніпропетровськ, 2007), на наукових семінарах кафедр диференціальних рівнянь та прикладної математики ДНУ, на регіональному науковому семінарі кафедри інформаційних технологій і систем НМетАУ «Математичне моделювання, проблеми прикладної інформатики та управління».
Публікації. За результатами наукових досліджень опубліковано дев'ять друкованих праць: п'ять статей у спеціальних виданнях [1-5], що входять до переліку ВАК України, та чотири у вигляді матеріалів наукових конференцій [6-9].
Структура і обсяг роботи. Дисертаційна робота складається із вступу, чотирьох розділів, висновків, списку використаної літератури із 72 джерел і додатка. Загальний обсяг дисертації становить 163 сторінки, основного тексту (без додатків) - 139 сторінок, ілюстрацій - 28, таблиць -1.
ОСНОВНИЙ ЗМІСТ РОБОТИ
У вступі розкриті суть та стан проблеми, обґрунтована актуальність теми дисертації, сформульована мета і задачі дослідження. Визначено методи дослідження та наукову новизну отриманих результатів. Розглянуто практичне значення та впровадження результатів дисертації. Наведено відомості про особистий внесок здобувача, апробацію роботи, публікації, зв'язок роботи з науковими програмами.
В першому розділі проведено аналіз найбільш відомих методів просторової інтерполяції статичних зображень, таких як метод найближчого сусідства, білінійна, біквадратична, бікубічна інтерполяція, B-сплайн інтерполяція та ін. Зазначено, що в більшості цих методів зображення тлумачиться як кусково-неперервна функція двох аргументів, що визначена на прямокутному носії. Загальною рисою цих підходів є побудова так званих сепарабельних інтерполяційних фільтрів. Це означає, що зміна щільності пікселів для будь-якого зображення спочатку реалізується за x-координатою (горизонтальний zooming), і лише потім за y-координатою (вертикальний zooming). Власне ця обставина і приводить до появи в результуючому зображенні таких візуальних артефактів як розмитість, “сходинковий” ефект в похилих контурах, поява дублюючих контурів і т.п. Причиною цього служить наявність в будь-якому околі довільного чіткого контуру високочастотних складових зображення, тобто має місце суттєва зміна значень функції зображення в сусідніх чи близьких між собою пікселах.
Проаналізовані також інші відомі підходи до вирішення задачі просторової інтерполяції статичних зображень. Зокрема, це методи адаптивної інтерполяції та методи контурно-направленої інтерполяції, в основі яких лежить використання локальних моделей контурних ліній і залучення в їх околі контурно-направлених методів відтворення значень функції зображення I. Основним недоліком цих підходів є поява дублюючих контурів. Причиною цього є нетривіальна проблема узгодження значень інтерпольованої функції I(x, y) на границях околів з різною “геометрією”. Проте, вдале залучення таких методів покращення якості інтерпольованих зображень, як метод маскування нечіткостей та залучення нелінійних фільтрів суттєво залежить від конкретних типів зображень (наприклад рентгенограм, топографічних карт та їм подібних).
На основі проведеного аналізу існуючих публікацій зроблено висновок про те, що проблема просторової інтерполяції статичних зображень залишається актуальною, а численні методи та алгоритми її якісного розв'язання не є адаптованими до широкого класу цифрових зображень.
У другому розділі наведені основні теоретичні положення та результати, які торкаються математичних аспектів теорії метричних просторів, множин Каччіполі, теорії міри, функцій з обмеженою варіацією та інших базових понять теорії цифрових зображень. Основна увага приділена функціональному тлумаченню основних морфологічних постулатів, які торкаються як геометричних характеристик двовимірних зображень, так і особливостей їх психосприйняття візуальною системою людини. Показано, що у відповідності до основних постулатів математичної морфології поняття “зображення” доцільно тлумачити як лінійний неперервний функціонал (розподілення), який означено на класі фінітних функцій з прямокутним носієм. Процес відтворення цифрових зображень доречно зводити до побудови його породжуючої функції в певному функціональному класі. Отже, результат відтворення будь-якого зображення може по суті залежати від функціональних властивостей того класу розподілень, якому воно належатиме.
Зауважено, що доцільно розрізняти поняття цифрового “зображення” та цифрового “малюнка”. Якщо зображення - це розподілення, носієм якого є прямокутна область в і яке визначене на широкому класі тестових функцій, то цифровий малюнок - це результат дії відповідного розподілення на спеціальним чином підібрану сукупність тестових функцій.
Відомо, що вся геометрична інформація про будь-яке зображення міститься в сукупності його множин рівнів, а точніше, в сукупності зв'язних компонент таких множин. Виникає питання про величину периметра множин рівнів. В зв'язку з цим введено поняття регулярного зображення.
Регулярним називається зображення I, якщо знайдеться інтегровна функція I:Д>[0, 1] така, що:
- для всіх ;
- при кожному значенні множини рівнів
мають скінченний периметр.
Для простоти зображення розглядаються в шкалі сірих відтінків зі значеннями від 0 до 1.
На множині всіх регулярних зображень виділено клас зображень, які є допустимими в задачах просторової інтерполяції. А саме, допустимими вважатимемо такі зображення, породжуючі функції яких належать класу функцій з обмеженою варіацією: . Таке тлумачення статичних зображень є характерним тим, що якщо , то майже при кожному значенні відповідна множина рівня є множиною скінченного периметру в .
В третьому розділі запропоновано адаптивний метод інтерполяції статичних зображень, який дозволяє відтворити значення породжуючих функцій довільних зображень в околі тієї частини їх топографічної карти, яка містить вихідну дискретну сітку. Для реалізації даного підходу запропонована постановка задачі каркасної інтерполяції, яка по своїй суті є двоетапною задачею: перша - відтворення каркасу вихідного зображення, друга - відтворення на каркасі породжуючої функції зображення.
Нехай - довільна непуста підмножина R2, - дискретна сітка на множині . Множину будемо називати каркасом для зображення , якщо є зв'язною множиною, і при цьому виконуються наступні умови:
, , ,
де через позначено границю множини . Каркас будемо називати допустимим для , якщо він не містить одночасно ребер та для будь-якого . Приклад допустимого каркасу показано на малюнку 1.
В основу конструювання каркасів покладені міркування щодо топологічної близькості топографічної карти зображення до остову його каркасної структури . Остов каркасу містить (як свої власні підмножини) ті фрагменти ліній рівнів відповідного цифрового малюнка , які проходять через точки дискретної множини .
Якщо - допустимий каркас зображення , то зображення будемо називати каркасною інтерполяцією для при виконанні наступних умов:
1) його образ на піксельну сітку співпадає з ;
2) ;
3) знайдуться функція і диз'юнктивне розбиття множини такі, що:
для всіх ;
Тут через позначено простір неперервних на функцій, перша та друга похідні яких є інтегровними на з своїми квадратами. Тоді задача каркасної інтерполяції полягає, по-перше, у відтворенні каркасу зображення , а по-друге, у відтворенні функції на побудованому каркасі.
Для коректного розв'язання задачі каркасної інтерполяції, яка б узгоджувалася з принципом “неперервного продовження” Гесталтіста, запропоновано залучення 6-точкових сплайнів. З цією метою наведена постановка оптимізаційної задачі побудови таких сплайнів.
Функцію будемо називати 6-точковим сплайном, побудованим на ланцюгу вхідних даних якщо, де включення рівносильне виконанню умов
.
За допомогою системи Maple отримано аналітичне подання такого сплайну:
Треба відзначити, що у випадку, коли ланцюг вхідних даних є таким, що при всіх , то для довільних .
Побудований таким чином сплайн має мінімальну локальну кривизну і дозволяє отримати найкращий прогноз значення функції в центральній точці. Цей сплайн використовується в алгоритмах будування каркасу і відтворення на ньому породжуючої функції зображення.
Процедура побудови каркасної структури полягає в наступному. Для кожного піксела визначається ланцюг із шести ланок, в якому піксел, що розглядається, є центральним. Приклади таких ланцюгів наведені на малюнку 2.
Рис.2. Приклади ланцюгів в множині
Рис.3. Приклад направленого околу точки
З усіх можливих структур такого типу обирається та, на якій найкращим чином за допомогою шеститочкових сплайнів наближається значення функції зображення в обраному пікселі. Таким чином здійснюється спроба знайти ту лінію рівня, на якій лежить обраний піксел. Далі на двох центральних ланках отриманої структури певним чином будується направлений окіл піксела , приклад якого наведений на малюнку 3. Позначимо через зону впливу обраного піксела - замкнену кулю радіуса 1/2 з центром в точці , а - сукупність всіх пікселів, сусідніх з . Введемо множину
.
Тоді каркас вихідного зображення визначається як:
.
Отже, побудувавши направлені околи для всіх точок піксельної сітки , отримуємо каркас вихідного зображення.
Наступним кроком після будування каркасу є відтворення значень функції зображення на цьому каркасі. Функцію будемо вважати відтвореною в задачі каркасної інтерполяції, якщо правило, за яким визначається її значення в кожній точці каркасу , забезпечує виконання властивостей .
Для відтворення значень функції зображення на каркасі також залучаються шеститочкові сплайни, які будуються на значеннях зображення в точках відповідного ланцюга. В результаті правило для відтворення значення функції в довільній точці з направленого околу має вигляд:
де шеститочкові сплайни будуються на системах точок
: ,
: ,
- відстань від до центрального піксела ланцюга за метрикою , і - третя та четверта ланки ланцюга, зсунутого таким чином, щоб покрити точку . Таким чином, процедура розв'язання задачі каркасної інтерполяції реалізована.
У четвертому розділі розглянута задача реконструкції зображення , тобто задача інтерполяції функції на множину . Для вирішення цієї задачі запропоновано варіаційний підхід. При цьому враховується умова, що результуюче зображення повинно відповідати принципу “неперервного продовження” Гесталтіста, згідно з яким візуальне сприйняття будь-якого зображення зберігає гладку неперервність всіх контурів замість різких та обривистих їх змін.
Позначимо через векторне поле градієнтів функції на множині , тобто є векторним полем із значеннями в , яке задовольняє умову
і .
Будемо вважати, що має слід на границі множини . За побудовою границя каркаса завжди підлягає декомпозиції на дві складові , де . В зв'язку з цим вважатимемо, що є заданими дві функції та такі, що
майже скрізь на , майже скрізь на ,
де і - одиничні вектори зовнішньої нормалі до границі множин і В відповідно. Задача реконструкції зображення полягає в визначенні функції та векторного поля таких, що поле , з однієї сторони, повинно успадковувати геометрію поля градієнтів функції u, а з іншої - бути близьким на границі до поля . Окрім цього, на каркасі функція повинна бути близькою до функції . При цьому кривизна ліній рівнів , в області повинна бути мінімальною.
Відомо, що кривизна ліній рівнів в точці x визначається як , де через позначено одиничний вектор нормалі до кривої . Проте таке означення не є прийнятним для випадку, коли є функцією з обмеженою варіацією, оскільки такі функції не є диференційованими в класичному розумінні.
Введемо до розгляду наступні функціональні простори
,
де довільне число, а оператор означено як .
Будемо казати, що пара належить графіку оператора (скорочено ), якщо , і при цьому існує розподілення таке, що
, (1)
, (2)
майже скрізь на . (3)
Значення оператора - оператора дивергенції на розподіленні , що є розв'язком крайової задачі (1)-(3) з умовою Неймана на границі області, будемо використовувати для характеристики кривизни ліній рівня .
Доведено, що множина завжди непуста, а оператор - монотонний. Встановлено наступний результат.
Твердження 1. Оператор є секвенційно замкненим в добутку сильної топології на та топології *-слабкої збіжності на , тобто, якщо , сильно в , а *-слабко в , то .
Для формальної постановки задачі реконструкції введемо наступний функціональний простір
(4)
На елементах простору означимо функціонал:
(5)
Тут - додатні вагові коефіцієнти, - регуляризуюче ядро таке, що k(x)>0 всюди на . Через позначено оператор згортки: .
Будемо казати, що зображення є результатом реконструкції за каркасною інтерполяцією його дискретних значень на дискретній сітці , якщо для всіх , , де
(6)
а пара є розв'язком наступної варіаційної задачі
(7)
Наведемо деякі пояснення щодо вибору структури цільового функціоналу (5). Наявність в ньому виразу визначає такий спосіб реконструкції зображення, при якому кривизна ліній рівнів була би мінімальною, оскільки значення оператора дивергенції на розподіленнях асоціюється з кривизною ліній рівня реконструйованого зображення. Третій доданок введено в функціонал для забезпечення його коерцитивності. Наявність в функціоналі виразу продиктована принципом “неперервного продовження” Гесталтіста, згідно з яким ті лінії рівня, які перетинають границю каркасу , повинні зберігати свій напрям близьким до на . Терм є релаксаційною формою умови близькості функцій та на множині .
Таким чином, задача реконструкції зображення полягає в визначенні пари , яка є розв'язком задачі (7). Доведено, що функціонал (5) є напівнеперервним знизу та коерцитивним в . В силу відомих результатів варіаційного числення цей функціонал досягає свого мінімального значення на . Отже, сформульована задача умовної мінімізації має розв'язок на класі функцій з обмеженою варіацією. Має місце наступний результат.
Теорема 1. Нехай - задані додатні величини, - довільна функція. Тоді при кожному значенні знайдеться таке, що множина розв'язків задачі (7) є непустою.
Одна з проблем, яка виникає на даному етапі, полягає в наступному: як визначити векторне поле на тих ділянках, де зображення має постійну інтенсивність () , або взагалі не існує. Для вирішення цієї проблеми розглянуто параметризовану задачу умовної мінімізації
(8)
на множині
(9)
Показано, що ця задача може розглядатися як апроксимативна модель задачі реконструкції статичних зображень (7). При цьому, за своїм змістом, термін “апроксимація” означає, що розв'язки задачі (8)-(9) прямують при до розв'язку вихідної задачі реконструкції зображень в певній топології. Доведено наступний результат.
Теорема 2. Для будь-якого апроксимативна задача (8) має розв'язок такий, що послідовність пар
де , збігається до розв'язку задачі реконструкції при в наступному сенсі
сильно в ,
*-слабко в .
Апроксимативна модель задачі реконструкції зображень покладена в основу процедури чисельного дослідження задачі умовної мінімізації (7). В чисельному алгоритмі використано метод найскорішого спуску із залученням наступних співвідношень
, (10)
, (11)
які повинні підкорятися відповідним початковим та крайовим умовам. Для врахування обмежень, які задаються структурою множини , залучаються ідеї методу штрафу. Проблеми диференційованості норми в вирішуються введенням нового обмеження типу . В результаті отримуємо модифіковану задачу умовної мінімізації, для якої будується ітераційна процедура із залученням співвідношень (10)-(11) та їх дискретизації за часом. Реалізація цієї процедури дозволяє побудувати збіжну послідовність пар при кожному . В якості початкового наближення можна вибрати результат каркасної інтерполяції , який поширено на всю область за будь-яким відомим методом просторової інтерполяції.
Запропонована в роботі методика розв'язання задачі просторової інтерполяції статичних зображень була покладена в основу проектування та розробки програмного забезпечення “Space Interpolation”. На основі порівняння якості інтерпольованих зображень, отриманих як за допомогою відомих методів просторової інтерполяції, так і засобами “Space Interpolation”, можна зробити наступний висновок: залучення запропонованого в роботі підходу дозволяє уникнути появи ряду візуальних артефактів і зберегти при цьому високу візуальну якість результуючих зображень.
ОСНОВНІ РЕЗУЛЬТАТИ РОБОТИ Й ВИСНОВКИ
В дисертаційній роботі запропоновано новий підхід до побудови алгоритмів просторової інтерполяції статичних зображень, який базується на розв'язанні наступної триєдиної задачі: 1) адаптивна побудова каркасу зображення, в основі якої лежить відтворення найбільш інформативної частки його топографічної карти; 2) розв'язання проблеми каркасної інтерполяції зображення, тобто відтворення на каркасі значень породжуючої функції; 3) розв'язання проблеми реконструкції зображення на всій області за інтерпольованими значеннями на побудованому каркасі.
В зв'язку з цим основними результатами роботи є:
1. Запропоновано постановку задачі каркасної інтерполяції статичних зображень, яка по своїй суті є двоетапною задачею: перша - відтворення каркасу вихідного зображення, а друга - відтворення на каркасі його породжуючої функції.
2. Запропоновано алгоритм відтворення значень породжуючих функцій довільних зображень в околі тієї частини їх топографічної карти, яка містить вихідну дискретну сітку. Алгоритм передбачає двоетапну схему реалізації. На першому етапі реалізується процедура побудови каркасу - деякої перфорованої множини, що є підмножиною носія вихідного зображення; другий етап полягає у відтворенні породжуючої функції на побудованому каркасі.
3. Розроблено алгоритм конструювання каркасу зображення, остов якого є близьким до топографічної карти зображення. В основу алгоритму покладено розв'язання певної оптимізаційної задачі.
4. Для коректного розв'язання задачі каркасної інтерполяції, яке б узгоджувалось з принципом “неперервного продовження” Гесталтіста, запропоновано залучення шеститочкових сплайнів. З цією метою наведена постановка оптимізаційної задачі побудови таких сплайнів та отримано її аналітичний розв'язок.
5. Наведена постановка задачі реконструкції зображення за його каркасною інтерполяцією.
6. На класі функцій з обмеженою варіацією означено оператор кривизни їх ліній рівнів та досліджено його основні властивості.
7. Для задачі реконструкції зображень за їх каркасною інтерполяцією запропонована її варіаційна постановка, яка передбачає мінімізацію певного функціоналу на певній множині допустимих функцій. Для цього визначена структура цільового функціонала та множини допустимих розв'язків.
8. Доведено, що на класі функцій з обмеженою варіацією задача реконструкції зображень є розв'язною.
9. Запропонована апроксимативна модель задачі реконструкції зображень, яка покладена в основу побудови чисельних процедур її розв'язання. Встановлено факт розв'язності відповідної варіаційної задачі та доведено, що розв'язки таких задач прямують у відповідних топологіях до розв'язків вихідної задачі реконструкції зображень.
10. Запропонований в роботі адаптивний підхід до розв'язання задачі просторової інтерполяції статичних зображень покладено в основу створеного програмного забезпечення “Space Interpolation”, яке орієнтоване на обробку статичних зображень формату *.bmp .
11. Практична реалізація процедури просторової інтерполяції статичних зображень, яка виконувалася засобами програми “Space Interpolation”, в порівнянні з нині існуючими методами розв'язання таких задач, показала, що запропонований підхід дозволяє уникнути появи ряду візуальних артефактів, які зазвичай мають місце в реалізації операції просторового zooming'у статичних зображень, та зберегти достатньо високу візуальну якість результуючих зображень.
СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ
1. Сердюк М. Є. Задачі каркасної інтерполяції статичних зображень / М. Є. Сердюк, П. І. Когут // Вестник Херсонского национального технического университета. - 2007. - № 2(28). - С.153-157.
2. Сердюк М. Є. Алгоритмічний підхід до задач каркасної інтерполяції статичних зображень / М. Є. Сердюк, П. І. Когут // Математичне моделювання. - Дніпродзержинськ, 2007. - № 2(17). - С. 3-7.
3. Сердюк М. Є. Про оператор кривизни на множині функцій з обмеженою варіацією та його основні властивості / М. Є. Сердюк, П. І. Когут // Питання прикладної математики і математичного моделювання : зб.наук.пр. - Дніпропетровськ : Вид-во ДНУ, 2007. - С. 153-160.
4. Сердюк М. Є. Про задачу реконструкції зображень за їх каркасною інтерполяцією / М. Є. Сердюк, П. І. Когут // Системні технології. Регіональний міжвузівський збірник наукових праць. - Дніпропетровськ, 2007. - № 3(50). - С. 35-45.
5. Сердюк М. Є. Апроксимативна модель задачі реконструкції зображень / М. Є. Сердюк // Адаптивні системи автоматичного управління. Міжвідомчий науково-технічний збірник. - Дніпропетровськ : Системні технології, 2007. - № 10(30). - С. 112-120.
6. Сердюк М. Є. Каркасна інтерполяція статичних зображень з використанням 6-точкових сепарабельних сплайнів / М. Є. Сердюк // Дни науки - 2007 : материалы III международной научно-практической конференции, 1-15 апр. 2007 г. - Днепропетровск : Наука и образование, 2007. - Т.9. - С. 9-15.
7. Сердюк М. Є. Задача реконструкції статичних зображень за їх каркасною інтерполяцією / М. Є. Сердюк // Научное пространство Европы - 2007 : материалы III международной научно-практической конференции, 16-30 апр. 2007 г. - Днепропетровск : Наука и образование, 2007. - Т.7. - С. 23-26.
8. Сердюк М. Є. Оператор кривизни на множині функцій з обмеженою варіацією / М. Є. Сердюк // Сучасні інформаційні технології на транспорті, в промисловості та освіті : міжнародна науково-практична конференція, 14-15 трав. 2007 р. : тези допов. - Дніпропетровськ, 2007. - С. 77.
9. Сердюк М.Є. Просторова інтерполяція статичних зображень / М. Є. Сердюк // Математичне та програмне забезпечення інтелектуальних систем : п'ята міжнародна науково-практична конференція, 14-16 листоп. 2007 р. : тези допов. - Дніпропетровськ, 2007. - С.173-174.
АНОТАЦІЯ
Сердюк М. Є. Варіаційна модель задачі просторової інтерполяції статичних зображень. - Рукопис.
Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 01.05.02 - Математичне моделювання та обчислювальні методи. - Національна металургійна академія України, Дніпропетровськ, 2008.
Дисертацію присвячено розробці нового підходу до побудови алгоритмів просторової інтерполяції статичних зображень. Запропоновано метод, перший етап якого полягає в розв'язанні задачі каркасної інтерполяції зображення, другий - в розв'язанні проблеми реконструкції зображення на всій області за інтерпольованими значеннями на каркасі. Запропоновано алгоритм адаптивної побудови каркасу зображення, остов якого є близьким до його топографічної карти, та алгоритм відтворення значень породжуючих функцій зображень на побудованому каркасі. Отримано аналітичне подання для шеститочкового інтерполяційного сплайну з мінімальною локальною кривизною, який використовується в алгоритмах. Запропонована варіаційна постановка задачі реконструкції зображення. Доведено її розв'язність на класі функцій з обмеженою варіацією. Наведена апроксимативна модель задачі реконструкції зображень, яка покладена в основу побудови чисельних процедур їх просторової інтерполяції. Встановлено факт її розв'язності та доведено, що розв'язки таких задач прямують у відповідних топологіях до розв'язків вихідної задачі реконструкції зображень. Практична реалізація методу показала, що запропонований підхід дозволяє уникнути появи ряду візуальних артефактів і зберегти достатньо високу візуальну якість результуючих зображень.
Ключові слова: просторова інтерполяція зображень, топографічна карта зображення, каркасна інтерполяція, інтерполяційний сплайн, реконструкція зображень, варіаційна модель.
АННОТАЦИЯ
Сердюк М. Е. Вариационная модель задачи пространственной интерполяции статических изображений. - Рукопись.
Диссертация на соискание ученой степени кандидата технических наук по специальности 01.05.02 - Математическое моделирование и вычислительные методы. - Национальная металлургическая академия Украины, Днепропетровск, 2008.
Диссертация посвящена разработке нового подхода к построению алгоритмов пространственной интерполяции статических изображений, который основан на восстановлении наиболее информативной части топографической карты изображения. Предложен метод, состоящий из двух этапов. На первом этапе решается задача каркасной интерполяции статических изображений, которая предполагает, во-первых, построение каркаса изображения - некоторого перфорированного множества, являющегося подмножеством носителя исходного изображения, во-вторых, восстановление порождающей функции изображения на построенном каркасе. На втором этапе решается задача реконструкции изображения на всей области по интерполированным значениям на каркасе.
Изображение рассматривается как линейный непрерывный функционал (распределение), определенный на классе финитных функций с прямоугольным носителем. На множестве всех возможных изображений выделен класс изображений, порождающие функции которых являются функциями с ограниченной вариацией. Такие изображения принимаются как допустимые в задачах пространственной интерполяции.
Приведена постановка задачи каркасной интерполяции. Разработан алгоритм построения каркаса изображения, остов которого является приближением топографической карты изображения и содержит все точки исходной дискретной сетки. В основу алгоритма положено решение определенной оптимизационной задачи. Для корректного решения задачи каркасной интерполяции, которое соответствовало бы принципу “непрерывного продолжения” Гесталтиста, предложено использовать шеститочечные интерполяционные сплайны минимальной локальной кривизны. Приведена постановка оптимизационной задачи построения таких сплайнов и получено ее аналитическое решение. Разработан алгоритм восстановления порождающей функции изображения на построенном каркасе.
Приведена постановка задачи реконструкции изображения на всей области по значениям на каркасе. На множестве функций с ограниченной вариацией определен оператор кривизны их линий уровня. Показано, что таким оператором может выступать оператор дивергенции на распределениях, которые являются решениями определенной краевой задачи с условием Неймана на границе. Исследованы основные топологические свойства такого оператора. Для задачи реконструкции изображений по их каркасной интерполяции предложена ее вариационная постановка, которая предполагает минимизацию определенного функционала на множестве допустимых функций. Определена структура целевого функционала. При этом учтены следующие факторы: а) близость на границе каркаса векторного поля градиентов функции изображения к векторному полю функции каркасной интерполяции; б) близость на каркасе функции изображения и функции каркасной интерполяции; в) обеспечение такого способа реконструкции изображения, при котором кривизна линий уровней была бы минимальной; г) удовлетворение определенным условиям коэрцитивности целевого функционала для обеспечения разрешимости исходной задачи. Предложенная структура целевого функционала обеспечивает соответствие результирующего изображения принципу “непрерывного продолжения” Гесталтиста. Доказано, что на классе функций с ограниченной вариацией поставленная вариационная задача имеет решение. Для численного исследования задачи реконструкции изображений предложена аппроксимационная модель. Доказана ее корректность. Установлен факт разрешимости соответствующей вариационной задачи. Показано, что решения предложенной аппроксимационной модели сходятся в соответствующих топологиях к решениям исходной задачи реконструкции изображений. Предложен алгоритм численного решения задачи реконструкции изображений.
Предложенный в работе адаптивный подход к решению задачи пространственной интерполяции статических изображений положен в основу разработанного программного обеспечения “Space Interpolation”, которое ориентировано на обработку статических изображений формата *.bmp. Практическая реализация процедуры пространственной интерполяции статических изображений, которая выполнялась средствами программы “Space Interpolation”, в сравнении с ныне существующими методами решения таких задач, показала, что предложенный подход позволяет не только избежать появления ряда визуальных артефактов, но и сохранить достаточно высокое качество результирующих изображений.
Результаты исследований внедрены в ОНИЛ кафедры „Вагоны и вагонное хозяйство” Днепропетровского национального университета железнодорожного транспорта, использованы в программном обеспечении на предприятии ООО “Екатеринославская мануфактура” для допечатной обработки изображений при изготовлении полиграфической продукции, а также в программном обеспечении для анализа рентгенограмм в Центре стоматологии “Аранта”, что подтверждается соответствующими актами внедрения.
Ключевые слова: пространственная интерполяция изображений, топографическая карта изображения, каркасная интерполяция, интерполяционный сплайн, реконструкция изображений, вариационная модель.
ABSTRACT
Serdyuk M. Ye. Variational model of still images space interpolation problem. - Manuscript.
Thesis for a candidate of technical science degree by specialty 01.05.02 - Mathematical simulation and computation methods. - National Metallurgical Academy of Ukraine, Dnepropetrovsk, 2008.
The dissertation is devoted to development of a new approach to the space interpolation of still images. Two-steps method is proposed. The method is based on sequential realization of the skeleton interpolation and the reconstruction problem of images.
The statement of the skeleton interpolation problem and the algorithm of skeleton construction are proposed. This algorithm is based on the reconstruction of the part of image topographic map, which contains all points of the pixel grid. For given skeleton the algorithm of image function reconstruction at the points of skeleton is developed. The analytic representation of six-point interpolation spline with minimal curvature is received. This spline is used in the algorithms mentioned above.
For the problem of image reconstruction outside the skeleton its variational formulation is given. It is proved that this problem has solution on the class of bounded variation functions. For the image reconstruction problem its approximate model is proposed. It is shown that the approximate problem is solvability and its solution converge to a solution of the original with respect to the appropriate topologies.
Practical realization of the introduced method showed that new method allowed to reduce visual artifacts and to save sufficiently good quality of resulting image.
Key words: image space interpolation, topographic map, skeleton interpolation, interpolation spline, image reconstruction, variational model .
Підписано до друку 17.04.2008 р. Формат 60х90/16.
Ум. друк. арк. 0,9. Обл. вид. арк. 1.
Наклад - 100 прим. Замовлення № 407.
Друкарня ДНУ. 49050, м. Дніпропетровськ, вул. Наукова, 5.
Размещено на Allbest.ru
...Подобные документы
Математична модель задачі лінійного програмування, її вирішення за допомогою симплекс-методу. Побудова екстремумів функцій в області, визначеній нерівностями, за допомогою графічного методу. Математична модель транспортної задачі та її опорний план.
контрольная работа [241,7 K], добавлен 28.03.2011Норми затрат ресурсів. Математична модель задачі. Рішення прямої задачі лінійного програмування симплексним методом. Основний алгоритм симплекс-методу. Область допустимих рішень. Розв’язок методом симплексних таблиць. Мінімальне значення цільової функції.
контрольная работа [234,6 K], добавлен 28.03.2011Побудування математичної моделі задачі. Розв'язання задачі за допомогою лінійного програмування та симплексним методом. Наявність негативних коефіцієнтів в індексному рядку. Основний алгоритм симплексного методу. Оптимальний план двоїстої задачі.
контрольная работа [274,8 K], добавлен 28.03.2011Загальна модель задачі математичного програмування, задача лінійного програмування та особливості симплекс–методу для розв’язання задач лінійного програмування Економіко–математична модель конкретної задачі, алгоритм її вирішення за допомогою Exel.
контрольная работа [109,7 K], добавлен 24.11.2010Багатокритеріальність, існуючі методи розв’язку задач лінійного програмування. Симплекс метод в порівнянні з графічним. Вибір методу розв’язання багатокритеріальної задачі лінійного програмування. Вирішення задачі визначення максимального прибутку.
курсовая работа [143,7 K], добавлен 15.12.2014Розробка оптимізаційної моделі бюджету доходів та витрат на прикладі ВАТ "ІнГЗК". Теоретичні аспекти застосування моделі транспортної задачі в економічних процесах. Економічна і математична постановки транспортної задачі та методи її розв'язання.
курсовая работа [585,1 K], добавлен 19.04.2011Знаходження плану випуску продукції, що дає максимальну виручку. Побудування таблиці, що відображає умову задачі та математичну модель. Запис двоїстої задачі та розрахунок рентабельності продукції з застосуванням табличного процесору "Microsoft Excel".
лабораторная работа [1,0 M], добавлен 26.11.2014Методика та головні етапи складання математичної моделі рішення заданої задачі, її елементи: цільові функції, обчислення. Розв’язок задачі за допомогою методу Гоморі: алгоритм програми, ітерації. Розрахунок задачі методом "Розгалуджень та обмежень".
курсовая работа [88,1 K], добавлен 31.08.2014Розробка математичної моделі задачі заміни устаткування та її розв'язання за допомогою електронних таблиць Microsoft Excel. Визначення оптимальної стратегії експлуатації устаткування, щоб сумарні витрати були мінімальними. Економіко-математична модель.
задача [271,3 K], добавлен 24.09.2014Задача на знаходження ефективності від виконання робіт митниками. Цільова функція, система обмежень. Продуктивність призначення робітника на роботу. Оптимальний (максимальний) варіант призначення. Математична модель задачі на призначення на мінімум.
контрольная работа [940,4 K], добавлен 24.09.2014Математична модель задачі лінійного програмування та її розв’язок симплекс-методом. Опорний план математичної моделі транспортної задачі. Оптимальний план двоїстої задачі. Рішення графічним методом екстремумів функції в області, визначеній нерівностями.
контрольная работа [290,0 K], добавлен 28.03.2011Поняття задачі лінійного програмування та різні форми її задання. Загальна характеристика транспортної задачі, її математична модель. Графічний метод для визначення оптимального плану задач лінійного програмування. Правило побудови двоїстої задачі.
контрольная работа [1,5 M], добавлен 04.09.2015Математична модель задачі по визначенню асортименту, що максимізує прибуток. Оптимальний план двоїстої задачі. Загальна вартість перевезень за оптимальним планом. Знаходження графічним методом екстремумів функцій в області, визначеній нерівностями.
контрольная работа [299,1 K], добавлен 28.03.2011Складання математичної моделі задачі. Побудова симплексної таблиці. Розв’язок задачі лінійного програмування симплексним методом. Рішення двоїстої задачі та складання матриці. Знаходження графічним методом екстремумів функцій, визначеній нерівностями.
контрольная работа [239,0 K], добавлен 28.03.2011Складання математичної моделі задачі комівояжера. Її розв'язок за допомогою електронних таблиць Microsoft Excel. Знаходження оптимального плану обходу міст комівояжером за заданими критеріями. Інтерпретація графічно отриманого розв’язку даної задачі.
контрольная работа [244,8 K], добавлен 24.09.2014Визначення оптимального бюджету для реклами на радіо і телебаченні. План перевезень залізної руди на збагачувальні фабрики, що забезпечує мінімальні сукупні транспортні витрати. Модель лінійного програмування для визначення максимального розміру доходу.
контрольная работа [2,3 M], добавлен 24.09.2014Поняття логістичних ланцюгів. Методи побудови початкового опорного плану. Визначення та розрахунок потенціалу кожної вершини. Методи пошуку оптимального рішення. Алгоритм оптимізації транспортної задачі: логістичного ланцюга за допомогою симплекс-методу.
дипломная работа [1,1 M], добавлен 20.11.2013Поняття інвестування, цінних паперів і фондового ринку. Математичне та алгоритмічне вирішення задачі формування портфеля (розрахунок Марковіца та нечітка модель). Визначення архітектури програмного забезпечення та його інформаційно-логічної схеми.
дипломная работа [2,7 M], добавлен 11.03.2011Розробка математичної моделі задачі оптимізації, розв’язання її засобами "Пошук рішення" в MS Excel. Класичні методи дослідження функцій на оптимум. Графічне розв’язання задачі лінійного програмування. Метод штучного базису. Двоїстий симплекс-метод.
контрольная работа [755,6 K], добавлен 26.12.2011Побудова математичної моделі плану перевезення зерна на елеватори, який мінімізує транспортні витрати. Розв’язок задачі симплексним методом. Знаходження графічним методом екстремумів функцій, визначеній нерівностями. Порядок рішення транспортної задачі.
контрольная работа [326,2 K], добавлен 28.03.2011
