Коцур Дмитро Вікторович Побудова моделі єдиного алгоритмічного середовища на основі діаграми Вороного для розв’язування комплексу задач обробки зображень

brief description

Коцур Дмитро Вікторович, інженер І категорії кафе­дри математичної інформатики Київського національного університету імені Тараса Шевченка: «Побудова моделі єдиного алгоритмічного середовища на основі діаграми Вороного для розв’язування комплексу задач обробки зображень» (01.05.01 - теоретичні основи інформатики та кібернетики). Спецрада Д 26.001.09 у Київському на­ціональному університеті імені Тараса Шевченка

Київський національний університет імені Тараса Шевченка
Міністерство освіти і науки України
Київський національний університет імені Тараса Шевченка
Міністерство освіти і науки України
Кваліфікаційна наукова
праця на правах рукопису
КОЦУР ДМИТРО ВІКТОРОВИЧ
УДК 004.021:004.023:004.932
ДИСЕРТАЦІЯ
ПОБУДОВА МОДЕЛІ ЄДИНОГО АЛГОРИТМІЧНОГО СЕРЕДОВИЩА НА
ОСНОВІ ДІАГРАМИ ВОРОНОГО ДЛЯ РОЗВ’ЯЗУВАННЯ
КОМПЛЕКСУ ЗАДАЧ ОБРОБКИ ЗОБРАЖЕНЬ
01.05.01 – теоретичні основи інформатики та кібернетики
Подається на здобуття наукового ступеня кандидата фізико-математичних наук
Дисертація містить результати власних досліджень. Використання ідей,
результатів і текстів інших авторів мають посилання на відповідне джерело
____________ Д. В. Коцур
Науковий керівник Терещенко Василь Миколайович,
доктор фізико-математичних наук, професор
Київ – 2019

ЗМІСТ
ПЕРЕЛІК УМОВНИХ ПОЗНАЧЕНЬ.................................................................... 18
ВСТУП.................................................................................................................... 19
РОЗДІЛ 1. ПОСТАНОВКА ЗАДАЧ ТА АНАЛІЗ ПІДХОДІВ
ДО РОЗВ’ЯЗАННЯ ЗАДАЧ ОБРОБКИ ЗОБРАЖЕНЬ........................................ 26
1.1. Опис основних задач обробки зображень.................................................. 27
1.2. Аналіз наявних підходів.............................................................................. 28
1.2.1. Методи обробки зображень ................................................................. 28
1.2.2. Програмні пакети, їх переваги та недоліки......................................... 29
1.2.3. Модель єдиного алгоритмічного середовища..................................... 31
1.3. Основні означення....................................................................................... 34
1.3.1. Базові геометричні поняття.................................................................. 35
1.3.2. Двовимірний евклідів простір.............................................................. 36
1.3.3. Основні поняття теорії графів.............................................................. 38
1.4. Складність алгоритмів та модель обчислень ............................................. 40
1.5. Поняття звідності (редукції) задач ............................................................. 44
1.6. Математична модель графічного зображення ........................................... 45
1.6.1. Поняття неперервного зображення ..................................................... 45
1.6.2. Поняття дискретного зображення ....................................................... 46
Висновки до розділу 1........................................................................................ 48
РОЗДІЛ 2. ДІАГРАМА ВОРОНОГО ЯК УНІВЕРСАЛЬНА
СТРУКТУРА ДАНИХ............................................................................................ 50
2.1. Визначення поняття діаграми Вороного.................................................... 50
2.1.1. Діаграма Вороного для множини точок на площині .......................... 51
2.1.2. Діаграма Вороного для множини відрізків на площині ..................... 55
2.1.3. Діаграма Вороного для множини кривих на площині........................ 59
2.1.4. Діаграма Вороного для множини кіл................................................... 61
2.2. Властивості діаграми Вороного.................................................................. 62
15
2.2.1. Властивості діаграми Вороного для множини точок ......................... 62
2.2.2. Властивості діаграми Вороного для множини відрізків .................... 65
2.3. Алгоритми побудови діаграми Вороного .................................................. 67
2.3.1. Реберний список із подвійними зв’язками.......................................... 68
2.3.2. Алгоритм «розділяй та володарюй» .................................................... 70
2.3.3. Алгоритм Форчуна для множини точок.............................................. 76
2.3.4. Алгоритм Форчуна для множини відрізків на площині..................... 82
2.4. Аналіз споріднених задач ........................................................................... 84
Висновки до розділу 2........................................................................................ 89
РОЗДІЛ 3. РОЗРОБКА АПАРАТУ МОДЕЛІ ЄДИНОГО АЛГОРИТМІЧНОГО
СЕРЕДОВИЩА (МЄАС)....................................................................................... 91
3.1. Аналіз критеріїв побудови МЄАС.............................................................. 91
3.1.1. Основні задачі МЄАС .......................................................................... 92
3.1.2. Типи вхідних даних.............................................................................. 93
3.1.3. Аналіз основних вимог до МЄАС ....................................................... 94
3.2. Розробка апарату МЄАС............................................................................. 94
3.2.1. Загальна структура МЄАС................................................................... 95
3.2.2. Етап 1. Попередня обробка .................................................................. 95
3.2.3. Етап 2. Побудова діаграми Вороного.................................................. 97
3.2.4. Етап 3. Подальша обробка ................................................................... 98
3.2.5. Опис уніфікованих структур даних..................................................... 99
3.2.6. Аналіз оцінки складності МЄАС......................................................... 99
3.3. Алгоритми обробки зображень................................................................. 101
3.3.1. Поняття перетворювача зображень ................................................... 101
3.3.2. Приклади перетворювачів зображень ............................................... 102
3.4. Алгоритми векторизації зображень.......................................................... 106
3.4.1. Метод квадратів.................................................................................. 106
3.4.2. Алгоритм Мура................................................................................... 107
3.4.3. Алгоритм Тео-Павлідіса..................................................................... 107
16
3.4.4. Алгоритм «Рухомі квадрати»............................................................. 109
3.5. Апроксимація діаграми Вороного для довільних об’єктів ..................... 110
3.5.1. Методи дискретизації параметричної кривої.................................... 112
3.5.2. Алгоритм побудови апроксимації діаграми Вороного..................... 115
3.5.3. Аналіз складності алгоритму ............................................................. 117
3.6. Серединна вісь та скелетон об’єкта.......................................................... 119
3.6.1. Визначення серединної осі та скелетона об’єкта.............................. 119
3.6.2. Побудова серединної осі на основі діаграми Вороного ................... 120
3.6.3. Методи регуляризації серединної осі................................................ 122
3.6.4. Метод мультиплікативного масштабування ..................................... 125
3.7. Евристичні методи оптимізації роботи МЄАС........................................ 128
3.7.1. Теоретичний базис оптимізаційних евристик................................... 128
3.7.2. Аналіз евристичних алгоритмів......................................................... 132
Висновки до розділу 3...................................................................................... 134
РОЗДІЛ 4. ТЕСТУВАННЯ ТА РЕАЛІЗАЦІЯ..................................................... 136
4.1. Тестування процедур оптимізації МЄАС ................................................ 136
4.1.1. Постановка обчислювального експерименту.................................... 136
4.1.2. Набір даних та основні метрики ........................................................ 137
4.1.3. Параметри евристичних алгоритмів.................................................. 138
4.1.4. Тестування алгоритмів ....................................................................... 139
4.1.5. Результати тестування........................................................................ 142
4.2. Порівняльний аналіз методів регуляризації серединної осі ................... 145
4.3. Демонстрація ефективності роботи МЄАС ............................................. 147
4.3.1. Задача обчислення дескрипторів форми об’єкта .............................. 147
4.3.2. Порівняння методів обчислення ........................................................ 149
4.4. Особливості програмної реалізації........................................................... 150
4.4.1. Основні компоненти МЄАС .............................................................. 150
4.4.2. Організація пам’яті............................................................................. 152
4.4.3. Програмна реалізація МЄАС ............................................................. 152
17
4.4.4. Модульність, основні інтерфейси та класи....................................... 154
Висновки до розділу 4...................................................................................... 154
РОЗДІЛ 5. ПРАКТИЧНЕ ЗАСТОСУВАННЯ МЄАС ........................................ 156
5.1. Побудова скелетона об’єкта заданої форми ............................................ 156
5.2. Задачі сегментації та відстеження клітинних структур .......................... 156
5.2.1. Сегментація філаментів...................................................................... 156
5.2.2. Відстеження філаментів методом активних контурів ...................... 158
5.2.3. Порівняльний аналіз алгоритмів відстеження .................................. 164
5.3. Сегментація біологічних нейронних мереж............................................. 166
5.3.1. Обробка зображення........................................................................... 167
5.3.2. Серединна вісь та сегментація ........................................................... 168
5.3.3. Подальший аналіз структур нейронної мережі................................. 170
5.4. Сегментація судин сітківки ока ................................................................ 170
5.5. Сегментація клітин.................................................................................... 171
Висновки до розділу 5...................................................................................... 172
ВИСНОВКИ ......................................................................................................... 173
СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ............................................................. 176
Додаток 1. Псевдокод процедури обробки діаграми Вороного ........................ 190
Додаток 2. Приклади сегментації мережі нейронів............................................ 191
Додаток 3. Приклади роботи методів регуляризації серединної осі................. 192
Додаток 4. Реалізація базових класів та інтерфейсів МЄАС............................. 194
Додаток 5. Список публікацій здобувача за темою дисертації ......................... 197
Додаток 6. Відомості про апробацію результатів дисертації ............................ 199

bibliography

ВИСНОВКИ
Головним результатом дисертаційної роботи є побудова моделі
алгоритмічного середовища на основі діаграм Вороного, що дає змогу вирішити
важливу наукову проблему створення єдиного алгоритмічного середовища для
ефективного розв'язування класу задач обробки та аналізу зображень.
У дисертаційній роботі отримано такі результати. Уперше:
1. Побудовано концепцію моделі єдиного алгоритмічного середовища
(МЄАС) на основі діаграми Вороного для розв’язування таких класів задач
обробки зображень:
• сегментація об’єктів та структур на зображенні;
• бінаризація зображення;
• трекінг об’єктів та структур на послідовності зображень;
• побудова серединної осі об’єкта на зображенні;
• знаходження областей близькості для множини об’єктів на зображенні;
• визначення чисельних характеристик об’єктів на зображенні.
2. Узагальнено алгоритми побудови апроксимації діаграми Вороного для
множини параметрично заданих кривих на площині, що дає змогу отримати
наближений розв’язок задачі визначення областей близькості. Досліджено
методи параметризації кривих та залежність результату апроксимації від
способу параметризації.
3. Узагальнено в межах МЄАС алгоритми на основі діаграми Вороного для
побудови скелетона (серединної осі) об’єкта з порожнинами. Встановлено,
що порівняно з методами потоншення такі алгоритми надають можливість
отримати скелетон із субпіксельною точністю, що інваріантний до повороту
та масштабування.
4. Розроблено евристичний підхід, який пришвидшує роботу МЄАС шляхом
спрощення представлення та форми об’єкта. Були сформульовані та
доведені основні теореми для евристичних методів оптимізації, а також
174
критерій спрощення форми об’єкта, що є основою побудови евристичних
алгоритмів.
5. Проаналізовано наявні алгоритми спрощення багатокутників та перевірено
їх відповідність критерію оптимізації. У результаті проведеного аналізу
було визначено сім евристичних алгоритмів, які дають змогу оптимізувати
роботу МЄАС.
6. Проведено обчислювальні експерименти на наборі даних MPEG-7 CE
Shape-1 для визначення найефективніших евристик оптимізації МЄАС.
Для прикладу було розглянуто задачу побудови скелетона об’єкта та
виміряно час роботи евристик і методу в цілому. Визначено точність
отриманих результатів у порівнянні з еталоном для різних значень
допустимої похибки алгоритму. Встановлено, що найбільше пришвидшення
(на 30 % з похибкою 10-3
) досягається за допомогою евристик РамераДугласа-Пекера та Вісвалінгама-Уайатта. Визначено, що евристики можуть
погіршувати точність результату. Тому було розроблено правила
застосування евристик залежно від критичних вимог системи (часу та
точності). Для задачі побудови скелетона було експериментально
встановлено, що запропоновані евристики мають ефект регуляризації, тобто
виконують автоматичне видалення розгалужень осі, які відповідають
випадковим збуренням границі об’єкта.
7. Досліджено наявні на сьогодні методи регуляризації серединної осі, а також
запропоновано новий підхід M-Scale на основі діаграми Вороного для
множини кіл (діаграми потужності) та методу мультиплікативного
масштабування. Ефективність роботи методу M-Scale та інших відомих
алгоритмів регуляризації було протестовано на наборі даних MPEG-7 CE
Shape-1. У результаті проведеного порівняльного аналізу було встановлено,
що алгоритми M-Scale та λ-серединна вісь є найефективнішими
алгоритмами регуляризації з найменшою похибкою, а застосування
комбінації алгоритмів M-Scale та λ-серединна вісь надає можливість
175
покращити точність регуляризації на ~10 % порівняно з окремими
алгоритмами.
8. Реалізовано програмний прототип МЄАС на принципах модульності,
розширюваності та універсальності структур даних. На прикладі задачі
підрахунку складеного дескриптора форми об’єкта (опуклість, округлість)
встановлено, що МЄАС без оптимізації дає змогу скоротити час виконання
на 20 % порівняно з іншими алгоритмами. Уведення етапу оптимізації
дозволяє пришвидшити час виконання в середньому в 10 разів при
максимальній похибці 1,0 %.
9. Розроблено ефективний алгоритм відстеження відкритих кривих (контурів,
серединних ліній тонких об’єктів тощо) на основі методу активних
контурів. Запропоновано новий метод обробки кінців кривої шляхом
мінімізації запропонованої функції вартості. Встановлено, що він дає змогу
отримати в 1.5 раза точніший результат (за метрикою Фреше), ніж наявні
методи для задачі відстеження окремих клітинних філаментів.
10.Розроблену МЄАС було успішно застосовано для розв’язання класу
прикладних задач обробки біологічних та медичних зображень:
• сегментація ниткоподібних структур клітини з використанням
флуоресцентних зображень із конфокального мікроскопа на прикладі
мережі, утвореної філаментами кератину або мікротрубочками;
• трекінг ниткоподібних структур цитоскелета клітини на послідовності
флуоресцентних зображень із конфокального мікроскопа, трекінг
окремих актинових, кератинових волокон та мікротрубочок;
• сегментація флуоресцентних знімків мережі нервових клітин, виділення
клітинних тіл, окремих аксонів та дендритів, реконструкція топології
такої мережі та аналіз її зв’язності;
• сегментація судинної системи за знімками сітківки ока, реконструкція
топології судинної системи, виділення окремих розгалужень системи.
Сегментація та виділення окремих клітин епітеліальної тканини за
двоканальними флуоресцентними зображеннями.