Водораздел (обработка изображений)
Из Википедии, бесплатной энциклопедии
  (Перенаправлено с алгоритма Watershed )
Перейти к навигации Перейти к поиску

При изучении обработки изображений водораздел - это преобразование, определенное на изображении в градациях серого . Название метафорически относится к геологическому водоразделу или водоразделу, который разделяет соседние водосборные бассейны. Преобразование водораздела рассматривает изображение, с которым оно работает, как топографическую карту , где яркость каждой точки соответствует ее высоте, и находит линии, проходящие вдоль вершин хребтов.

Существуют разные технические определения водораздела. В графах линии водоразделов могут быть определены на узлах, на ребрах или гибридные линии как на узлах, так и на ребрах. Водоразделы также могут быть определены в непрерывной области. [1] Также существует множество различных алгоритмов для вычисления водоразделов. Алгоритмы водораздела используются при обработке изображений в первую очередь для целей сегментации .

  • Снятие величины градиента

  • Градиентная величина изображения

  • Водораздел градиента

  • Водораздел градиента (рельеф)

Определения

В геологии водораздел - это водораздел, разделяющий соседние водосборные бассейны.

Водораздел при наводнении

Идея была предложена в 1979 г. С. Беухером и К. Лантуежулем. [2] Основная идея состояла в том, чтобы разместить источник воды в каждом региональном минимуме рельефа, затопить весь рельеф из источников и построить барьеры, когда встречаются разные источники воды. Полученный набор барьеров представляет собой водораздел от наводнения. С тех пор в этот алгоритм был внесен ряд улучшений, получивших общее название Priority-Flood. [3]

Водораздел по топографической удаленности

Интуитивно капля воды, падающая на топографический рельеф, течет к «ближайшему» минимуму. «Ближайший» минимум - это тот минимум, который лежит в конце пути наискорейшего спуска. С точки зрения топографии это происходит, если точка находится в бассейне этого минимума. Предыдущее определение не проверяет это условие.

Водораздел по принципу капли воды

Интуитивно понятно, что водораздел - это разделение региональных минимумов, из которых капля воды может стекать вниз к отчетливым минимумам. Формализация этой интуитивной идеи была предоставлена ​​в [4] для определения водораздела взвешенного по ребрам графа.

Межпиксельный водораздел

С. Бойчер и Ф. Мейер представили алгоритмическую межпиксельную реализацию метода водораздела [5] со следующей процедурой:

  1. Обозначьте каждый минимум отдельной меткой. Инициализируйте набор S с помеченными узлами.
  2. Извлеките из S узел x минимальной высоты F , то есть F ( x ) = min { F ( y ) | y  ∈  S }. Атрибут метку х к каждому немеченому узлу у прилегающих к й , и вставить у в  S .
  3. Повторяйте шаг 2, пока S не станет пустым.

Топологический водораздел

Предыдущие представления касались водосборных бассейнов, но не производимой разделительной линии. Топологический водораздел был введен М. Купри и Дж. Бертраном в 1997 г. [6] и обладает следующим фундаментальным свойством. Функция W является водоразделом функции F тогда и только тогда, когда W ≤ F и W сохраняет контраст между региональными минимумами F; где контраст между двумя региональными минимумами M 1 и M 2 определяется как минимальная высота, на которую нужно подняться, чтобы перейти от M 1 к M 2 . [7] Эффективный алгоритм подробно описан в статье. [8]

Алгоритм водораздела

Для использования принципа водораздела для сегментации изображения могут использоваться разные подходы .

  • Локальные минимумы градиента изображения могут быть выбраны в качестве маркеров, в этом случае производится чрезмерная сегментация, и второй шаг включает объединение областей.
  • Преобразование водораздела на основе маркеров использует определенные положения маркеров, которые были либо явно определены пользователем, либо определены автоматически с помощью морфологических операторов или другими способами.

Алгоритм наводнения Мейера

Один из наиболее распространенных алгоритмов водораздела был введен Ф. Мейером в начале 1990-х годов, хотя с тех пор в этот алгоритм был внесен ряд улучшений, получивших общее название Priority-Flood [9], включая варианты, подходящие для наборов данных, состоящих из триллионов пикселей. [10]

Алгоритм работает с изображением в оттенках серого. При последовательном затоплении серого рельефа строятся водоразделы с прилегающими водосборными бассейнами. Этот процесс заливки выполняется на градиентном изображении, т.е. бассейны должны выходить по краям. Обычно это приводит к чрезмерной сегментации изображения, особенно для материала с зашумленным изображением, например, данных медицинской компьютерной томографии. Либо изображение должно быть предварительно обработано, либо области должны быть впоследствии объединены на основе критерия сходства.

  1. Выбирается набор маркеров, пикселей, с которых должно начаться заливка. Каждому дается другой ярлык.
  2. Соседние пиксели каждой отмеченной области вставляются в очередь приоритетов с уровнем приоритета, соответствующим величине градиента пикселя.
  3. Пиксель с наивысшим уровнем приоритета извлекается из очереди приоритетов. Если все соседи извлеченного пикселя, которые уже были помечены, имеют одинаковую метку, то пиксель помечается их меткой. Все неотмеченные соседи, которые еще не находятся в очереди с приоритетом, помещаются в очередь с приоритетом.
  4. Повторяйте шаг 3, пока приоритетная очередь не станет пустой.

Непомеченные пиксели являются линиями водораздела.

Пример управляемой маркером трансформации водораздела для популяции фармацевтических гранул. Линии водораздела накладываются черным цветом на стек КТ изображений [11] .

Оптимальные алгоритмы охвата леса (вырубки водоразделов)

Джин Кусти и др. Представили водоразделы как оптимальный пролетный лес. [12] Они устанавливают непротиворечивость этих водосборных бассейнов: их можно эквивалентно определить по их «водосборным бассейнам» (через свойство наискорейшего спуска) или по «разделительным линиям», разделяющим эти водосборные бассейны (через принцип «капля воды»). Затем они доказывают с помощью теоремы эквивалентности свою оптимальность с точки зрения минимальных остовных лесов. После этого они вводят алгоритм линейного времени для их вычисления. Стоит отметить, что аналогичные свойства не проверяются в других фреймворках, и предлагаемый алгоритм является наиболее эффективным из существующих алгоритмов как в теории, так и на практике.

  • Изображение с двумя маркерами (зелеными) и минимальным охватывающим лесом, вычисленным на основе градиента изображения.

  • Результат сегментации по минимальному остовному лесу

Связи с другими алгоритмами компьютерного зрения

Разрезы графа

В 2007 г. C. Allène et al. [13] установили связи, связывающие Graph Cuts с оптимальными остовными лесами. Точнее, они показывают, что когда мощность весов графа превышает определенное число, разрез, минимизирующий энергию разрезов графа, является разрезом на максимальный остовный лес.

Кратчайшие леса

Преобразование лесного просмотра изображений (IFT) Falcao et al. [14] - это процедура для вычисления лесов кратчайших путей. Это было доказано J. Cousty et al. [15] , когда маркеры IFT соответствуют экстремумам весовой функции, вырубка, вызванная лесом, является водоразделом.

Случайный бродяга

Случайным образом ходунка алгоритм сегментации алгоритм решения комбинаторной задачи Дирихле , выполненный с возможностью сегментации изображений Л. Грейди в 2006 году [16] В 2011 году С. Couprie и др. Доказано, что когда мощность весов графа сходится к бесконечности, разрез, минимизирующий энергию случайного блуждающего, является разрезом по максимальному остовному лесу. [17]

Иерархии

Иерархическое преобразование водораздела преобразует результат в отображение графика (т. Е. Определяются отношения соседства сегментированных регионов) и рекурсивно применяет дальнейшие преобразования водораздела. Подробнее см. [18] . Теория, связывающая водораздел с иерархическими сегментами, была развита в [19].

Примечания

  1. ^ Л. Найман и М. Шмитт. Водораздел непрерывного действия . В обработке сигналов (специальный выпуск по математической морфологии), Vol. 38 (1994), страницы 99–112
  2. ^ Serge Beucher и христианская Lantuéj мастерская по обработке изображений,режиме реального времени края и обнаружения движения (1979). http://cmm.ensmp.fr/~beucher/publi/watershed.pdf
  3. ^ Барнс, Р., Леман, К., Мулла, Д., 2014. Приоритетное наводнение: оптимальный алгоритм заполнения депрессии и маркировки водоразделов для цифровых моделей рельефа . Компьютеры и науки о Земле 62, 117–127. DOI : 10.1016 / j.cageo.2013.04.024
  4. ^ Ж. Cousty, Г. Бертран, Л. Найман и М. Couprie. Вырезы водоразделов: минимальные перекрывающие леса и принцип капли воды , IEEE Transactions on Pattern Analysis and Machine Intelligence 31 (8) pp. 1362-1374, 2009,
  5. ^ Серж Бойхер и Фернан Мейер. Морфологический подход к сегментации: трансформация водораздела . В « Математической морфологии в обработке изображений» (под ред. Э. Р. Догерти), страницы 433–481 (1993).
  6. ^ М. Купри, Г. Бертран. Топологическое преобразование серого водораздела. В Proc. SPIE Vision Geometry V, том 3168, страницы 136–146 (1997). http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.3.7654&rep=rep1&type=pdf
  7. ^ Г. Бертран. На топологических водоразделах . Journal of Mathematical Imaging and Vision, 22 (2-3), страницы 217-230 (2005).
  8. ^ Мишель Купри, Лоран Наджман, Жиль Бертран. Квазилинейные алгоритмы топологического водораздела . Журнал математической визуализации и зрения, Springer Verlag, 2005, 22 (2-3), стр. 231-249.
  9. ^ Барнс, Р., Леман, К., Мулла, Д., 2014. Приоритетное наводнение: оптимальный алгоритм заполнения депрессии и маркировки водоразделов для цифровых моделей рельефа . Компьютеры и науки о Земле 62, 117–127. DOI : 10.1016 / j.cageo.2013.04.024
  10. ^ Барнс, Р., 2016. Параллельное заполнение депрессии приоритетным потоком для цифровых моделей рельефа триллиона ячеек на настольных компьютерах или кластерах. Компьютеры и науки о Земле. DOI : 10.1016 / j.cageo.2016.07.001
  11. ^ Doerr, FJS, и Флоренция, AJ (2020). Анализ изображений микро-XRT и методология машинного обучения для характеристики составов капсул с несколькими частицами. Международный журнал фармацевтики: X, 2, 100041. https://doi.org/10.1016/j.ijpx.2020.100041
  12. ^ Жан Cousty, Жиль Бертран, Лоран Найман, и Мишель Couprie. Вырезы водоразделов: минимальные размеры лесов и принцип капли воды . IEEE Transactions по анализу шаблонов и машинному анализу. 31 (8). Август 2009. С. 1362–1374.
  13. ^ Седрик Аллен, Жан-Ив Одибер, Мишель Купри и Рено Керивен: « Некоторые связи между минимальными разрезами, оптимальным охватом лесов и водоразделами », Image and Vision Computing, 2009.
  14. ^ Фалькао, AX Столое, Ж. де Alencar Lotufo, Р.: « лесоразведение образ преобразования: теория, алгоритмы и приложение », в П, 2004
  15. ^ Жан Cousty, Жиль Бертран, Лоран Найман, и Мишель Couprie. Вырубки водоразделов: рубки ухода, кратчайшие леса и топологические водоразделы . IEEE Transactions по анализу шаблонов и машинному анализу. 32 (5). 2010. С. 925–939.
  16. ^ Грейди, Л .: " Случайные блуждания для сегментации изображений ". ПАМИ, 2006 г.
  17. ^ Камилла Купри, Лео Грейди, Лоран Наджман и Хьюг Талбот, « Power Watersheds: Unifying Graph-Based Optimization Framework », IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 33, No. 7, pp. 1384-1399, июль 2011 г.
  18. ^ Лоран Найман, Мишель Шмитт. Геодезическая значимость контуров водоразделов и иерархическая сегментация . IEEE Transactions on Pattern Analysis and Machine Intelligence, Институт инженеров по электротехнике и электронике, 1996, 18 (12), стр.1163-1173.
  19. ^ Лоран Наджман. Об эквивалентности иерархических сегментов и ультраметрических водоразделов . Журнал математической визуализации и зрения, Springer Verlag, 2011, 40 (3), стр. 231-247.

использованная литература

  • Фернан Мейер. Оптимальный алгоритм для воды. Dans 8 me congrès de reconnaissance des formes et Intelligence artificielle , Vol. 2 (1991), страницы 847–857, Лион, Франция.
  • Люк Винсент и Пьер Сойль. Водоразделы в цифровых пространствах: эффективный алгоритм, основанный на иммерсионном моделировании . В IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 13, Чис. 6 (1991), страницы 583–598.
  • Л. Найман и М. Шмитт. Геодезическая выраженность контуров водоразделов и иерархическая сегментация . В IEEE Transactions on Pattern Analysis and Machine Intelligence , Vol. 18, Чис. 12 (1996), страницы 1163–1173.
  • JBTM Roerdink и A. Meijster. Трансформация водораздела: определения, алгоритмы и стратегии распараллеливания . В Fundamenta Informaticae 41 (2000), стр. 187–228.
  • Лоран Наджман, Мишель Купри и Жиль Бертран. Водоразделы, мозаика и парадигма эмерджентности . В дискретной прикладной математике , Vol. 147, Чис. 2–3 (2005), страницы 301–324.

внешние ссылки

  • Преобразование водораздела с анимацией алгоритма водораздела.
  • Преобразование топологического водораздела с документами, слайдами лекций и исходным кодом.
  • Плагин с открытым исходным кодом для ImageJ .
  • Набор инструментов топологии (2D и 3D водоразделы на основе комплекса Морзе )
Получено с https://en.wikipedia.org/w/index.php?title=Watershed_(image_processing)&oldid=1020703625 "
Contribute a better translation