Сегментація зображення

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

Застосування[ред.ред. код]

Деякими практичними застосуваннями сегментації зображень є:

  • Медичні зображення[2]
    • Виявлення пухлин та інших патологій
    • Визначення обсягів тканин
    • Хірургія за допомогою комп'ютера
    • Діагностика
    • Планування лікування
    • Вивчення анатомічної структури
  • Виділення об'єктів на супутникових світлинах
  • Розпізнавання облич
  • Розпізнавання відбитків пальців
  • Системи управління дорожнім рухом
  • Виявлення стоп-сигналів
  • Комп'ютерний зір

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

Методи, засновані на кластеризації[ред.ред. код]

k-середніх — це ітераційний метод, який використовуєтсья для того, щоб розділити зображення на K кластерів. Базовий алгоритм наведений нижче:

  1. Вибрати K центрів кластерів, випадково або на основі деякої евристики
  2. Помістити кожен піксель зображення в кластер, центр якого найближче до цього пікселя
  3. Знову визначити центри кластерів, усереднюючи всі пікселі в кластері
  4. Повторювати кроки 2 і 3 до збіжності (наприклад, коли пікселі будуть залишатися в тому ж кластері)

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

Цей алгоритм гарантовано сходиться, але він може не привести до оптимального рішення. Якість рішення залежить від початкового множини кластерів і значення K.

Методи з використанням гістограми[ред.ред. код]

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

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

Один недолік цього методу — те, що йому може бути важко знайти значні мінімуми і максимуми на зображенні. У цьому методі класифікації зображень схожі метрика відстаней і зіставлення інтегрованих регіонів.

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

Виділення країв[ред.ред. код]

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

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

Методи розростання областей[ред.ред. код]

Першим був метод розростання областей з насіння. В якості вхідних даних цей метод приймає зображень і набір насіння. Насіння відзначають об'єкти, які потрібно виділити. Області поступово розростаються, порівнюючи всі незайняті сусідні пікселі з областю. Різниця \delta між яскравістю пікселя і середньою яскравістю області використовується як міра схожості. Піксель з найменшою такаю різницею додається у відповідну область. Процес триває доки всі пікселі не будуть додані в один з регіонів.

Метод розростання областей з насіння вимагає додаткового вводу. Результат сегментації залежить від вибору насіння. Шум на зображенні може призвести до погано розміщення насіння. Метод розростання областей без використання насіння — це змінений алгоритм, який не вимагає явного насіння. Він починає з однієї області A_1 — піксель, обраний тут незначно впливає на кінцеву сегментацію. На кожній ітерації він розглядає сусідні пікселі так само, як метод розростання областей з використанням насіння. Але він відрізняється тим, що якщо мінімальна \delta не менша, чим заданний поріг T, то він додається у відповідну область A_j. В іншому випадку піксель вважається таким, що сильно відрізняється від всіх поточних областей A_i і створюється нова область A_{n+1}, яка містить цей піксель.

Один з варіантів цього методу, запропонований Хараліком і Шапіро (1985),[1] заснований на використанні яскравості пікселів. Середнє и дисперсія області та яскравість пікселя-кандидата використовується для побудови тестової статистики. Якщо тестова статистика достатньо мала, то піксель додається до області, і середнє і дисперсія області перераховується. Інакше, піксель ігноруються і використовується для створення нової області.

Методи розрізу графа[ред.ред. код]

Методи розрізу графа можуть бути ефективно застосовані для сегментації зображень. У цих методах зображення представляється як зважений неорієнтований граф. Зазвичай, піксель або група пікселів асоціюється вершиною, а ваги ребер визначають (не) схожість сусідніх пікселів. Потім граф (зображення) розрізається відповідно до критерію, створеному для отримання «хороших» кластерів. Кожна частина вершин (пікселів), одержувана цими алгоритмами, вважається об'єктом на зображенні. деякі популярні алгоритми цієї категорії — це нормалізовані розрізи графів[4], випадкове блукання[5], мінімальний розріз[6],ізопериметричний поділ[7] і сегментація з допомогою мінімального зваженого дерева[8].

Сегментація методом водоподілу[ред.ред. код]

Метод водоподілу — це заснований на областях метод математичної морфології. У географії, вододіл — це хребет, який ділить області різних річкових систем.

a. вихідне зображення; b. сегментоване зображення без попередньої обробки

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

Перший етап видалення шуму в початковому зображенні полягає в застосуванні морфологічних операцій закриття / розкриття, потім обчислюється морфологічний градієнт зображення без шуму і виконується нелінійне перетворення для рівнів сірого на градієнті зображення за допомогою принципу Вебера, останній етап — обчислення вододілу по нелінійному, розбитому на області, градиентному зображенню.[9].

Сегментація за допомогою моделі[ред.ред. код]

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

Багатомасштабна сегментація[ред.ред. код]

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

Критерій сегментації може бути безпідставно складним і може приймати до уваги як локальні, так і глобальні критерії. Загальна вимога — те, що кожна область повинна бути пов'язана в деякому сенсі.

Одновимірна ієрархічна сегментація сигналів[ред.ред. код]

Основоположна робота Віткіна[10][11] у масштабному просторі містила ідею про те, що одновимірний сигнал може бути однозначно сегментований на області, використовуючи всього лише один параметр, керуючий масштабом сегментації.

Програмне забезпечення[ред.ред. код]

Платне[ред.ред. код]

Існує декілька наявних програмних продуктів для сегментації зображень

  • Pac-n-Zoom Color має власне програмне забезпечення, що сегментує понад 16 мільйонів кольорів фотографічної якості. Доступне за адресою http://www.accelerated-io.com/usr_man.htm [1]
  • TurtleSeg інтерактивна програма для сегментації 3D зображень. Вона підтримує велику кількість фоматів медичних зображень та дозволяє користувачам експотрувати сегментовані ними зображення у форматі бінарної маски або 3D поверхні.

Безкоштовне[ред.ред. код]

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

  • ImageMagick використовує алгоритм нечіткої кластеризації.
  • MITK має програмний модуль для самостійної сегментації напівтонових зображень.
  • GRASS GIS має програмний модуль i.smap для сегментації зображень.
  • Population безкоштовна C++ бібліотека для обробки зображень

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

Див. також[ред.ред. код]

Посилання[ред.ред. код]

Примітки[ред.ред. код]

  1. а б в г д Linda G. Shapiro and George C. Stockman (2001): «Computer Vision», pp 279–325, New Jersey, Prentice-Hall, ISBN 0-13-030796-3
  2. Dzung L. Pham, Chenyang Xu, and Jerry L. Prince (2000): «Current Methods in Medical Image Segmentation», Annual Review of Biomedical Engineering, volume 2, pp 315–337
  3. Ron Ohlander, Keith Price, and D. Raj Reddy (1978): «Picture Segmentation Using a Recursive Region Splitting Method», Computer Graphics and Image Processing, volume 8, pp 313–333
  4. Jianbo Shi and Jitendra Malik (2000): «Normalized Cuts and Image Segmentation», IEEE Transactions on pattern analysis and machine intelligence, pp 888–905, Vol. 22, No. 8
  5. Leo Grady (2006): «Random Walks for Image Segmentation», IEEE Transactions on Pattern Analysis and Machine Intelligence, pp. 1768–1783, Vol. 28, No. 11
  6. Z. Wu and R. Leahy (1993): «An optimal graph theoretic approach to data clustering: Theory and its application to image segmentation», IEEE Transactions on Pattern Analysis and Machine Intelligence, pp. 1101–1113, Vol. 15, No. 11
  7. Leo Grady and Eric L. Schwartz (2006): «Isoperimetric Graph Partitioning for Image Segmentation», IEEE Transactions on Pattern Analysis and Machine Intelligence, pp. 469–475, Vol. 28, No. 3
  8. C. T. Zahn (1971): «Graph-theoretical methods for detecting and describing gestalt clusters», IEEE Transactions on Computers, pp. 68-86, Vol. 20, No. 1
  9. Manisha Bhagwat, R. K. Krishna & Vivek Pise: «GSimplified Watershed Transformation», International Journal of Computer Science & Communication, Vol. 1, No. 1, January-June 2010, pp. 175–177
  10. Witkin, A. P. «Scale-space filtering», Proc. 8th Int. Joint Conf. Art. Intell., Karlsruhe, Germany,1019—1022, 1983.
  11. A. Witkin, "Scale-space filtering: A new approach to multi-scale description, " in Proc. IEEE Int. Conf. Acoust., Speech, Signal Processing (ICASSP), vol. 9, San Diego, CA, Mar. 1984, pp. 150–153.