Факультет компьютерних наук та технологій
Кафедра автоматизованих систем управління
Специальність Інформаційні системи і технології в техніці та бізнесі
Обробка цифрових зображень є вкрай важливим процесом, який має широкий спектр застосування, починаючи від визначення номера машини учасника дорожнього руху та закінчуючи виявленням злоякісних новоутворень в організмі людини [1].
Сегментація - це процес поділу чого-небудь цілісного на складові частини, між якими існують виражені відмінності. У випадку з цифровими зображеннями, сегментація - це процес розподілу пікселів зображення по групах, всередині яких зберігається деякий критерій схожості елементів. У свою чергу, між цими групами існує певна відмінність.
Сегментування є однією з найважливіших і найбільш трудомістких задач в області обробки цифрових зображень. На поточний момент існує значна кількість методів і алгоритмів сегментації, кожен з яких має свої сильні і слабкі сторони. Основними принципами [2]], на яких будуються алгоритми сегментації зображень є:
Однак, не дивлячись на різноманіття, універсального підходу не існує. Кожна область застосування має свою специфіку, через що вимоги до алгоритму сегментації значно різняться.
Сучасний рівень розвитку технологій в області комп'ютерної діагностики уможливлює надання цифрованої візуальної інформації з високою роздільною здатністю.
Підвищення ступеня детальності зображення дозволяє відобразити більший обсяг інформації, що в ряді областей матиме критичне значення. Пропорційно до обсягу інформації, зростає і об’єм самих зображень. Це призводить до того, що існуючі методи обробки значно втрачають в ефективності. Це сприяє тому, що задача підвищення швидкодії та ефективності алгоритмів сегментації зображення стає все більш актуальною.
Виникає необхідність у пошуку рішення, яке забезпечило б значне підвищення продуктивності методів сегментування зображень.
Випускна кваліфікаційна робота присвячена вирішенню задачі підвищення ефективності і продуктивності алгоритмів сегментації зображень. Для знаходження рішення передбачається використання ройових алгоритмів на апаратній базі сучасних GPGPU [3]. В якості програмної платформи виступить стандарт паралельних обчислень OpenCL [4], а також багатоплатформова об'єктно-орієнтована мова програмування високого рівня Java [5].
Метою проведених досліджень є розробка інструментальних засобів паралельної сегментації тривимірних зображень з використанням методів ройового інтелекту. Основні завдання дослідження:
Об'єкт дослідження: методи сегментації цифрових зображень.
Предмет дослідження: паралельна сегментація зображень із застосуванням ройових алгоритмів.
В рамках виконання випускної кваліфікаційної роботи магістранта передбачається отримання теоретичних результатів за наступними напрямками:
Для отримання експериментальної оцінки теоретичних результатів необхідно розробити інструментальні засоби сегментації. Розробка передбачає наступні кроки:
Тема сегментації цифрових зображень не є новою. На поточний момент існує безліч методів і алгоритмів, багато з яких себе добре зарекомендували. Значна частина існуючих підходів розроблена і представлена університетами Європи, США, а також провідних країн Азії та Південної Америки.
Методи сегментування, що використовують алгоритми кластеризації, на поточний момент являють собою класичне рішення задачі обробки зображень.
Прикладом сучасного варіанту застосування таких алгоритмів є метод, поданий М. Алмазруі в статті
GPU-based fuzzy C-means clustering algorithm for image segmentation
[6].
Об'єктом експерименту став набір медичних зображень головного мозку людини. Алгоритм сегментації виконувався паралельно, апаратною платформою виступив сучасний GPGPU NVIDIA Tesla C2050.
Програмною основою став стандарт паралельних обчислень CUDA. При збереженні задовільного рівня якості вихідного результату,
розпаралелювання забезпечило 674-кратне прискорення, в порівнянні з послідовним виконанням алгоритму.
Отримані результати явно вказують на перспективність використання паралельних обчислень.
Більш інноваційним рішенням завдання сегментації може стати застосування евристичних алгоритмів.
Стаття Parallel particle swarm optimization for image segmentation
[7] за авторством А. Крістіаді
демонструє використання алгоритму рою частинок (PSO) для сегментування зображення із застосуванням кластеризації.
При проведенні експерименту також використовувалися технології паралельних обчислень CUDA.
Результати експерименту показали, що, при невеликому обсязі вхідної інформації, розпаралелювання себе не виправдовує - послідовна реалізація демонструє кращий результат. Однак, із зростанням рівня якості та об’єму зображення, ситуація докорінно змінюється: паралельна версія алгоритму показує 1.7-кратний приріст продуктивності. Це пов'язано з тим, що застосування паралелізму також вимагає певних ресурсів, обсяг яких нівелюється при обробці більших масивів даних.
В статті І. Чжу GPU accelerated fuzzy connected image segmentation by using CUDA
[8]
наводиться опис розпаралелювання алгоритму сегментації, в основі якого лежить метод нечітких зв'язностей.
Об'єктом експерименту виступили зображення томографії головного мозку здорової людини. Результати проведення експерименту показали, що, в порівнянні з послідовною версією алгоритму, розпаралелювання дало 14.4-кратний приріст в швидкості виконання. Примітним є той факт, що ефективність паралелізму зростає при роботі з об'ємом даних більшого розміру.
Іншим, досить популярним і добре себе зарекомендувавшим, є метод сегментації з використанням алгоритму розростання областей.
В статті П.Н. Хаппа A parallel region growing algorithm for image segmentation on GPUs
[9] описується застосування
розпаралеленої версії даного алгоритму для сегментування зображення.
В процесі реалізації алгоритму, автор зіткнувся з необхідністю вирішення деяких нетривіальних задач, пов'язаних зі структурою пам'яті сучасних GPU. Процес вирішення цих проблем черговий раз підтвердив необхідність розуміння і врахування специфіки апаратної платформи GPU для її успішної експлуатації.
Результати експерименту показали відсутність значної різниці в якості результату сегментації за допомогою початкової та модифікованої в догоду паралелізму версій алгоритму. Кратність прискорення в порівнянні з послідовним виконанням на CPU варіюється від 1.38 до 6.86, вона підвищується при збільшенні обсягу оброблюваної візуальної інформації.
В статті П.Ф. Фельзенцвальба Efficient graph-based image segmentation
[10] представлений
метод сегментації зображення з використанням алгоритму розбиття графа.
Результати експерименту показали продуктивність і гнучкість представленого методу сегментування. Незважаючи на те, що алгоритм був представлений досить давно, він і на сьогодні залишається продуктивним, ефективним і здатний видавати задовільні результат при невеликих витратах часу.
Публікація Використання бджолиних алгоритмів для вирішення комбінаторних задач
[11] за авторством В.М. Курейчика
демонструє використання різних алгоритмів для знаходження рішення комбінаторної задачі розбиття графа.
Результати виконання експериментів показали, що ройові евристичні алгоритми на порядок краще справляються з поставленим завданням. При цьому, мурашиний алгоритм краще підходить для вирішення невеликих задач, а бджолиний алгоритм показує більш високу ефективність при збільшенні обсягу вхідних даних.
У публікації В.В. Курейчика Ройовий алгоритм в задачах оптимізації
[12] наводиться опис роботи алгоритму,
заснованого на поведінці колонії медоносних бджіл, при вирішенні оптимізаційних задач проектування.
У публікації наведено оцінку часової складності алгоритму, його математична модель, а також опис знаходження оптимуму цільової функції з його використанням.
На закінчення дається твердження про здібності алгоритму до розпаралелювання отримання оптимальних і квазіоптимальних рішень.
На кафедрі автоматизованих систем управління (АСУ), факультету комп'ютерних наук і технологій Донецького національного технічного університету
проводяться дослідження і розробки в області евристичних алгоритмів. Прикладом значущих робіт може служити монографія Метаевристики
за авторством Ю.А. Скобцова і Е.Е. Федорова [13].
Серед магістрантів кафедри АСУ проводилися дослідження і розробки в області застосування евристичних алгоритмів до задачі сегментації зображень.
Прикладом результатів таких досліджень стала випускна кваліфікаційна робота магістранта С.А. Ель-Хатіба
Комп'ютерна система сегментації медичних зображень на основі алгоритму мурашиних колоній
[14],
а також його публікація, вже в якості аспіранта, Комп'ютерна система сегментації медичних зображень методом рою частинок
[15].
Основою методу [16] є представлення зображення у вигляді графа, в якому вершини - це пікселі зображення. Довжина ребер між вершинами визначається різницею характеристик двох сусідніх пікселів, на підставі яких здійснюється сегментація. Значення довжини ребра розраховується за формулою (1):
Початковий етап алгоритму передбачає порівняння пікселів з 4 (північний, південний, західний, східний) або 8 сусідніми (додаються проміжні). Такий підхід дозволяє зробити вибір на користь продуктивності або ж якості кінцевого результату. Після проходження даного етапу буде отримано велику кількість розрізнених сегментів. Далі, згідно з критерієм (2) відбувається об'єднання цих сегментів:
Рис. 1. Об'єднання сегментів
На практиці, при програмній реалізації даного алгоритму, більш ефективним підходом буде обробка масиву ребер графа, відсортованих по зростанню їх ваги. Кожне ребро проходить перевірку на можливість об'єднання сегментів, які воно з'єднує. Слід розуміти, що на початковому етапі кожен піксель являє собою окремий сегмент.
Даний алгоритм добре масштабується і дозволяє визначати кінцевий результат, ґрунтуючись на поточних пріоритетах в сторону підвищення якості і, як наслідок, трудомісткості, або ж в сторону підвищення продуктивності зі збереженням мінімально прийнятної якості результату сегментації.
Окрім вже зазначеної можливості регулювання кількості ребер в графі, існує спосіб модифікації розрахункової формули різниці пікселів (3):
Змінні в цій формулі визначаються тим, що в якості розрахункової характеристики пікселів при сегментації взяті значення колірної моделі RGB. Крім них, в формулу додані координати пікселя в трьох площинах (мова йде про тривимірні зображення).
Це лише один з варіантів структури розрахункової формули. Гнучкість обраного алгоритму надає можливість вибору оптимальних характеристик пікселів, які дозволять виконати високоякісну сегментацію, відповідно з оцінкою параметрів вихідного зображення. Отже, не виключається залучення додаткових моделей, які дозволять провести ефективну оцінку вхідного зображення і на її підставі визначити значення, які будуть використовуватися при сегментації.
На поточному етапі виконання випускної кваліфікаційної роботи передбачається [17] використовувати ройовий алгоритм для ефективного розподілу потужностей обраної апаратної бази.
Природа алгоритму бджолиної колонії передбачає його видатний рівень ефективності при виконанні завдання розподілу наявних трудових ресурсів, якими в даному випадку виступають обчислювальні одиниці графічного прискорювача, які здатні виконувати різні поставлені завдання паралельно.
Оптимізація розподілу навантаження з використанням алгоритму бджолиної колонії вимагає попередньої оцінки обсягу і деяких інших критеріїв вхідної інформації.
Основою представленого підходу є розподіл пікселів початкового зображення на кілька блоків за певним критерієм. Для кожного такого блоку, за формулою (4), буде розраховано кількість виділених обчислювальних одиниць:
В рамках кожного блоку, виділені одиниці слід розділити на фактичні робочі групи, розмір яких визначається специфікаціями обраної програмної платформи розпаралелювання, а також фізичною структурою поточної апаратної бази.
Ключові моменти описуваного процесу сегментації зображень можуть бути схематично представлені таким чином (рис. 2):
Рис. 2. Алгоритм сегментації (Анімація: 133 кб, 8 кадрів, необм. число повторів)
Передбачається, що програмною основою розпаралелювання представленого алгоритму виступить універсальний багатоплатформовий стандарт паралельних обчислень OpenCL. Серед провідних стандартів в сфері паралельних обчислень (CUDA, OpenCL, OpenMP і ін.), обраний відрізняється багатоплатформовостю і легкістю інтеграції в різні системи, при цьому відставання в продуктивності від основного конкурента CUDA незначне і з виходом нових версій стандарту стає все менше [18].
На поточний момент, реалізована послідовна версія алгоритму, який сегментує двовимірні медичні зображення МРТ, розміром 512 на 512 пікселів. Програмна реалізація забезпечена засобами платформи Java.
При проведенні експерименту, сегментація зображення здійснювалася кількома версіями алгоритму (з використанням 4-ох складного і 8-ми складного графа) при різних значеннях аргументу k. Результати вимірів часу наведені в таблиці 1.
| № | Складність графу | k | Витрачений час, сек |
|---|---|---|---|
| 1 | 4 | 300 | 31,188 |
| 2 | 4 | 3000 | 27,438 |
| 3 | 4 | 30000 | 30,971 |
| 4 | 8 | 300 | 35,094 |
| 5 | 8 | 3000 | 34,693 |
| 6 | 8 | 30000 | 35,024 |
Результати експерименту свідчать про те, що, на даному етапі реалізації алгоритму, використання 4-ох зв'язкового графа не надає значної переваги в швидкості виконання. При цьому, з суб'єктивної точки зору, 8-ми зв'язний граф забезпечує більш високий рівень якості кінцевого результату. На рис. 3 представлене вихідне зображення, яке використовувалося при проведенні експерименту.
Рис. 3 Початкове зображення
На рисунках 4(а) та 4(б) представлені результати сегментації зображень при значенні k = 3000.
Рис. 4. Результати сегментації
Випускна кваліфікаційна робота магістранта присвячена дослідженням методів сегментації зображень і розробці інструментальних засобів паралельного сегментування, які в перспективі дозволили б знизити трудомісткість розробки систем, що мають своєю основою модулі обробки медичних цифрових зображень.
На поточному етапі виконання роботи забезпечено досягнення наступних цілей:
Подальшим напрямком досліджень і розробки буде:
На момент написання реферату, магістерська робота не завершена. Остаточне завершення планується в травні 2018 року. Повний текст роботи та матеріали по темі можуть бути отримані у магістранта або його наукового керівника не раніше зазначеної дати.