ДонНТУ   Портал магістрів

Реферат за темою випускної роботи

Зміст

Вступ

У комп'ютерному зорі, сегментація — це процес поділу цифрового зображення на декілька сегментів (множин пікселів, також званих суперпікселямі). Мета сегментації полягає у спрощенні та / або зміні подання зображення, щоб його було простіше і легше аналізувати. Сегментація зображень зазвичай використовується для того, щоб виділити об'єкти і межі (лінії, криві, і т. д.) на зображеннях. Більш точно, сегментація зображень — це процес присвоєння таких міток кожному пікселю зображення, що пікселі з однаковими мітками мають спільні візуальні характеристики.

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

Актуальність

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

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

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

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

Мета роботи

Метою роботи є дослідження можливості ефективної реалізації алгоритмів сегментації для спрощення задачі розпізнавання об'єктів на двомірних зображеннях

Задачі

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

Очікувані результати

В результаті роботи планується отримати:

Новизна

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

Огляд аналогічних досліджень

Магістрантами ДонНТУ раніше проводилися дослідження з вивчення сегментації зображень. Депутат Е. В., Скобцов Ю. А. [14] досліджували можливість сегментації зображень за допомогою алгоритму мурашиних колоній. Савченко Д.А. [15] також досліджував методи сегментації зображень. Чудовська А.К. [16] проводила дослідження з реалізації алгоритму виділення контурів Кенні з використанням технології NVidia CUDA.

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

Одні з ранніх досліджень проводили Alireza Khotanzad і Abdel Majud Bouarfa. Їх робота [8] присвячена сегментації зображень з використанням порогового алгоритму кластеризації. В результаті їх роботи було отримано восьмикратне прискорення роботи алгоритму при використанні 11 процесорів.

У дослідженнях, проведених Shahram Rahimi, M. Zargham і A. Thakre [12], розглядається можливість розпаралелювання алгоритму C-Mean, що використовує нечітке розбиття пікселів на кластери. Було досягнуто дев'ятикратне прискорення при ефективності близькою до одиниці. В ході досліджень була виявлена прямопропорційна залежність між кількістю процесорів і приростом швидкості сегментації зображення.

Дослідження Nawal Copty, Sanjay Ranka, Geo rey Fox, Ravi V. Shankar [10] також показують хороші результати при розпаралелювання алгоритму зростання регіонів. Дослідження проводилися з використанням обчислювальної системи, побудованої за архітектурою MIMD. В результаті також помічене значне зростання швидкості обробки при використанні великої кількості обчислювальних вузлів.

У роботі Jan Wassenberg, Wolfgang Middelmann і Peter Sanders [2] описали алгоритм сегментації на графах з використанням обчислювальної системи з архітектурою SMP. Час роботи розробленого алгоритму лінійно залежить від розмірності вхідних даних.

Класифікація існуючих алгоритмів

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

Одна з класифікацій алгоритмів поділяє існуючі методи на наступні підмножини (рисунок 1) [5]:

Схема класифікаціі алгоритмів сегментації

Рисунок 1 — Схема класифікаціі алгоритмів сегментації. Анімація — 8 кадрів, затримка 500 мс, 3000 мс для останнього кадру

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

Алгоритми з даної групи можуть давати неточні результати, особливо при високому рівні шуму на зображенні, що вимагає додаткової перед- або пост-обробки зображення [7].

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

Розрізняють декілька видів порогової обробки:

Алгоритми виділення країв дозволяють позначити межі елементів на зображенні. Найбільш відомим таким алгоритмом є детектор країв Кенні (Canny edge detector) [6]

Основні кроки алгоритму:

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

Алгоритми вилучення областей оперують таким поняттям як «регіон» або «область», а також «насіння» — спочатку заданий піксель, з якого надалі виростає область. Спочатку задається декілька центрів («насіння») регіонів на зображенні і далі відбувається зростання цих регіонів за рахунок поглинання сусідніх пікселів. Подібні алгоритми в якості вхідних даних вимагають вказівки центрів регіонів для більш якісної сегментації. [13]

Метод розростання областей з насіння вимагає додаткового введення. Результат сегментації залежить від вибору насіння. Шум на зображенні може викликати те, що насіння погано розміщені. Метод розростання областей без використання насіння — це змінений алгоритм, який не вимагає явних насіння. В якості міри близькості пікселів використовується інтенсивність пікселя і середня інтенсивність по регіону δ.

Алгоритм починає з однієї області A1 — піксель, обраний тут, незначно впливає на кінцеву сегментацію. На кожній ітерації алгоритм розглядає сусідні пікселі так само, як метод розростання областей з використанням насіння. Але метод розростання областей відрізняється тим, що якщо мінімальна δ не менше, ніж заданий поріг T, то піксель додається у відповідну область Aj. В іншому випадку піксель вважається сильно відрізняється від всіх поточних областей Ai і створюється нова область An +1, містить цей піксель.

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

Для того щоб позбутися залежності від початкових значень і автоматизувати алгоритм, можна включити в нього деяку статистичну інформацію і апріорні значення. Наприклад, критерій однорідності, який був запропонований Pohle Toennies [7], робить алгоритми адаптуються до різних значень початкових точок.

Алгоритм, який використовує квадродерева, бере в якості кореня дерева все зображення і якщо воно не є однорідним, то відбувається процес розбиття зображення на 4 області — дочірні вузли кореня. Для синів повторюється аналогічний процес. У свою чергу, якщо 4 сина однорідні, то вони об'єднуються (процес злиття) в один вузол. Процес повторюється рекурсивно до тих пір, поки можливо виконати розбиття і злиття.

Алгоритм зростання регіонів

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

Базові положення алгоритму сегментації (рисунок 2)

Основні положення алгоритму зростання регіонів

Рисунок 2 — Основні положення алгоритму зростання регіонів

a) сегментація повинна бути повною, тобто кожен піксель зображення повинен належати якомусь регіоні;

b) всі пікселі в регіоні повинні бути об'єднані за допомогою заздалегідь визначеного правила (предиката);

c) регіони повинні бути непересічними;

d) всі пікселі в регіоні повинні мати однакове (приблизно однакове) значення властивості, за яким виконується сегментація;

e) властивості пікселів в суміжних регіонах повинні значно відрізнятися один від одного.

Базові концепції вихідних точок

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

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

При виборі вільного пікселя для аналізу можна використовувати методи 4 або 8 сусідів (рисунок 3).

Схема вибору наступного пікселя для аналізу

Рисунок 3 — Схема вибору наступного пікселя для аналізу

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

Перелік посилань

  1. Blasiak Anna. A Comparison of Image Segmentation Methods. Электронный ресурс. Режим доступа http://dspace.nitle.org/bitstream/handle/10090/781/s10csci2007blasiak.pdf?sequence=1 свободный. – Загл. с экрана. – Яз. англ.
  2. Wassenberg Jan. Middelmann Wolfgang, Sanders Peter. An Efficient Parallel Algorithm for Graph-Based Image Segmentation. Электронный ресурс. Режим доступа http://algo2.iti.kit.edu/wassenberg/wassenberg09parallelSegmentation.pdf свободный. - Загл. с экрана. – Яз. англ.
  3. Pantofaru Caroline, Hebert Martial. A Comparison of Image Segmentation Algorithms. Режим доступа http://www.ri.cmu.edu/pub_files/pub4/pantofaru_caroline_2005_1/pantofaru_caroline_2005_1.pdf свободный. - Загл. с экрана. – Яз. англ.
  4. Zhen Ma, João Manuel R. S. Tavares, R. M. Natal Jorge. A review on the current segmentation algorighms for medical images. Режим доступа http://repositorio-aberto.up.pt/bitstream/10216/7125/2/17022.pdfhttp://repositorio-aberto.up.pt/bitstream/10216/7125/2/17022.pdf свободный. – Загл. с экрана. – Яз. англ.
  5. Поршнев С.В., Левашкина А. О. Универсальная классификация алгоритмов сегментации изображений. Электронный ресурс. Режим доступа http://jurnal.org/articles/2008/inf23.html свободный.
  6. Canny, J. A Computational Approach to Edge Detection. Ээлектронный ресурс. Режим доступа http://www.limsi.fr/Individu/vezien/PAPIERS_ACS/canny1986.pdf свободный. - Загл. с экрана. – Яз. англ.
  7. Pohle, R., Toennies, K. D. Segmentation of Medical Images Using Adaptive Region Growing. Электронный ресурс. Режим доступа http://wwwisg.cs.uni-magdeburg.de/bv/pub/pdf/mi_4322_153.pdf свободный. - Загл. с экрана. – Яз. англ.
  8. Alireza Khotanzad, Abdelmajid Bouarfa. Image segmentation by a perallel, non- parametric histogram based clustering algorithm. Электронный ресурс. Режим доступа http://www.cs.gsu.edu/~wkim/index_files/papers/imagesegmentation.pdf свободный. - Загл. с экрана. – Яз. англ.
  9. Brian Fulkerson, Stefano Soatto. Really quick shift: Image segmentation on a GPU. Электронный ресурс. Режим доступа http://www.vision.ucla.edu/papers/fulkersonS10really.pdf свободный. – Загл. с экрана. – Яз. англ.
  10. Nawal Copty , Sanjay Ranka , Geo rey Fox , Ravi V. Shankar. A Data Parallel Algorithm for Solving the Region Growing Problem on the Connection Machine. Режим доступа http://www.new-npac.org/users/fox/pdftotal/sccs-0596.pdf свободный. – Загл. с экрана. – Яз. англ.
  11. Lucas Lattari, Anselmo Montenegro, Aura Conci, Esteban Cluaa, Virginia Mota, Marcelo Bernardes Vieirab, Gabriel Lizarragac. Using graph cuts in GPUs for color based human skin segmentation. Режим доступа http://pire.fiu.edu/publications/Graph_Cuts_2011.pdf свободный. – Загл. с экрана. – Яз. англ.
  12. Shahram Rahimi, M. Zargham, A. Thakre. A Parallel Fuzzy C-Mean algorithm for Image Segmentation. Режим доступа http://opensiuc.lib.siu.edu/cs_pubs/26/ свободный. – Загл. с экрана. – Яз. англ.
  13. Frank Y. Shih, Shouxian Cheng, Automatic seeded region growing for color image segmentation. Электронный ресурс. Режим доступа http://www.csd.uoc.gr/~hy471/papers/AutomaticSRGColor.pdf свободный. – Загл.с экрана. – Яз. англ.
  14. Депутат Е. В., Скобцов Ю. А, Сегментация медицинских изображений с помощью алгоритма муравьиных колоний., Информационные управляющие системы и компьютерный мониторинг 2010/ Сборник материалов к I Всеукраинской научно-технической конференции студентов, аспирантов и молодых ученых.- Донецк, ДонНТУ-2010, с.12-16.
  15. Савченко Д. А., Исследование методов сегментации изображений, Режим доступа http://masters.donntu.ru/2010/fknt/savchenko/diss/index.htm свободный. – Загл.с экрана.
  16. Чудовская А.К., Исследование возможностей распараллеливания алгоритмов выделения контуров объектов по технологии CUDA, Режим доступа http://masters.donntu.ru/2010/fknt/chudovskaja/diss/index.htm свободный. – Загл.с экрана.