Дослідження можливостей розпаралелювання алгоритмів виділення контурів об'єктів за технологією CUDA

АВТОРЕФЕРАТ

Вступ

Актуальність теми роботи

Передбачувана наукова новизна

Плановані практичні результати

Рішення задач і результати досліджень

Висновки

Вступ

Контурний аналіз — сукупність методів виділення, опису та перетворення контурів зображення. Це є важливий етап обробки зображень і розпізнавання зорових образів. Контур в цілому визначає форму зображення і містить всю необхідну інформацію для розпізнавання зображень за їх формою. Такий підхід дозволяє не розглядати внутрішні точки зображення і тим самим скоротити обсяг оброблюваної інформації. Як наслідок, це може забезпечити роботу системи розпізнавання в реальному часі. Так само даний підхід дозволить скоротити пам'яті, що використовується системою розпізнавання.^[1]

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

Актуальність теми роботи

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

Слід зазначити, що над проблемою виділення контурів працюють також вчені різних країн. Наприклад, професор університету Південної Флориди Судеп Саркар, професор і голова департаменту наук та обчислювальної техніки Кевін Бауер (університет Нотр-Дам), доктор, керівник Дрексельской лабораторії автоматизованих систем Пауль О.

Передбачувана наукова новизна

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

Плановані практичні результати

За результатами досліджень планується створити програмну реалізацію модифікованого алгоритму, здатного ефективно і швидко визначати контури на зображеннях. Основною умовою для роботи такої програми є наявність відеокарти компанії nVidia з технологією CUDA (чіпи GeForce серії 6 і вище)^[6] на ПК, з якого буде проводитися запуск програми.

Рішення задач і результати досліджень

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

Для реалізації процедури виділення контуру за допомогою нейронної мережі було прийнято таку модель. На вхід нейронної мережі подається зображення вікна спостереження розміром m Х n. Це зображення задовольняє наступним вимогам:

1. Зображення завжди містить елемент контуру, тобто в будь-якому представленому зображенні міститься кордон перепаду яркостей об'єкта і фону.
2. На зображенні тільки один контур, тобто не передбачається робота алгоритму з множинними контурами.
3. На зображенні може бути присутнім адитивний шум Гауса, який перешкоджає правильній роботі алгоритму.

На виході необхідно отримати основні параметри прямої, що апроксимує кордон перепаду яскравості: u  — інтенсивність фону, u + h — інтенсивність об'єкта, d — відстані від центру вікна до прямої, φ  — кут нахилу прямої. Дані параметри показані на рис. 1.

Рисунок 1 — Кордон об'єкт / фон в елементарному вікні ^[5]

 

Для реалізації цієї моделі, враховуючи статистичний характер моделі, була обрана нейронна мережа типу багатошаровий персептрон. Мережа складається з двох шарів. У першому шарі 10 нейронів, в другому 4.^[5] Всі штучні нейрони використовують логічну функцію активації. Архітектура мережі зображена на рис. 2.

Рисунок 2 — Нейронна мережа

 

Слід звернути особливу увагу на першу вимогу до вікна зображення. Оскільки вікна, які подаються на вхід нейромережі, повинні обов'язково містити частину кордону, і при тому тільки одну (вимога 2), то необхідно якимось чином ці вікна знайти. Одним з варіантів рішення цієї задачі є знаходження попереднього контуру більш швидким і грубим методом. Потім знайдене наближення контуру розбивається на ділянки, які уточнюються на нейромережі. Крім того, окремим завданням є збір розрізнених ділянок контурів в один безперервний контур. Вирішити це завдання можна, приміром, знаходячи середню точку між двома крайніми точками апроксимуючої прямої у двох сусідніх вікон.^[4] Процес знаходження кордонів схематично показаний на рисунку 3.

Рисунок 3 — Процес знаходження кордонів зображень

Анімація була створена в Adobe PhotoShop CS2; складається з 6 кадрів с затримкою 1с між кадрами; кількість циклів повторення обмежено 10ма; об'єм анимации — 27 Кб, розмір 250х250 пікселів

 

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

Крок 1. Фільтрація шуму у вихідному зображенні. Фільтр Гауса можна обчислити за допомогою простої маски. Після того як потрібна маска була розрахована, згладжування Гауса може бути виконано за допомогою стандартних методів згортки. Маски згортки, як правило, набагато менші, ніж саме зображення. У результаті, маска рухається над зображенням, маніпулюючи квадратом пікселів за один раз. Чим більше ширина маски Гауса, тим менше чутливість детектора до шуму. Локалізація помилки у виявленні країв так само трохи збільшується зі збільшенням ширини Гауссіана.^[5]

Крок 2. Знаходження краю сили шляхом обчислення градієнта зображення. Оператор Собеля виконує 2-D просторовий вимір градієнта у зображенні, і можуть бути знайдені наближені градієнти абсолютних величин (краю сил) в кожній точці. Оператор Собеля використовує пари масок 3x3 згортки: оцінки градієнту в напрямку х (стовпці) і оцінки градієнту в Y-напрямку (рядків).

Величина, або край сили, градієнта потім апроксимується за формулою: |G| = |Gx| + |Gy|

Крок 3. Усунення смуг шляхом обчислення гістерезису. Смуга - це розбиття контуру краю, викликане оператором вихідного коливання вище і нижче порогового рівня. Якщо єдиний поріг, T1 застосовується до зображення та край має середню силу, рівну T1, то з-за шуму, будуть випадки, коли край опускається нижче порогового рівня. Рівною мірою край буде також поширюватися вище за поріг прийняття краю, схожого на пунктирну лінію. Щоб уникнути цього, гістерезис використовує 2 порога, високий і низький. Будь-який піксель в зображенні, який має значення більше, ніж T1 імовірно є крайовим пікселем, і негайно позначається як такий. Потім, будь-які пікселі, що з'єднуються з цим крайовим пікселем, і які мають значення, більше, ніж T2, також вибираються як крайові пікселі. Для початку руху вздовж края потрібен градієнт T2, а для закінчення – градіент нижче T1.^[4]

Цей алгоритм також може бути распаралелен для розрахунку на програмно-апаратному комплексі CUDA шляхом розбиття зображення на дільниці і обробки цих ділянок на різних процесорах.

У результаті все зображення розбивається на вікна розміром m X n, придатні для обробки нейромережею, але обробці піддаються тільки ті з них, які містять рівно одну ділянку контуру.

Висновки

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

Література

1. Фурман Я.А., Юрьев А.Н., Яншин В.В. Цифровые методы обработки и распознавания бинарных изображений. — Красноярск, 1992. — 248с. http://www.4tivo.com/education/2329-cifrovye-metody-obrabotki-i.html^[↑]
2. Green B. Canny Edge Detection Tutoria // Drexel Autonomous Systems Lab., 2002. — http://www.pages.drexel.edu/~weg22/can_tut.html ^[↑]
3. Сирота А.А., Соломатин А.И. Статистические алгоритмы обнаружения границ объектов на изображениях. — Воронеж: Вестник ВГУ, № 1, 2008. — www.vestnik.vsu.ru/.../sirota_2.pdf^[↑]
4. Чудовская А.К. Возможности распараллеливания алгоритмов выделения контура по технологии CUDA // Искусственный интеллект.— Донецк: ІПШІ МОН і НАН України “Наука і освіта”, 2010.
5. Прэтт У. Цифровая обработка изображений, том 2 — Москва: Мир, 1982 — 478с.
6. Лосев С. Перспективы параллельных вычислений на GPU от Nvidia — Hard’n’Soft, №6 — 2009. — www.nvidia.eu/cuda/files/HardnSoft_026_027_trends_Cuda.pdf

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

Автобіографіяs

Автореферат