Водораздел (обработка изображений) - Watershed (image processing)

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

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

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

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

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

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

Определения

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

Водораздел от наводнения

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Немаркированные пиксели - это линии водораздела.

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

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

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

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

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

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

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

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

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

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

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

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

Иерархии

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

Примечания

  1. ^ Л. Найман и М. Шмитт. Водораздел непрерывной функции. В обработке сигналов (специальный выпуск по математической морфологии), Vol. 38 (1994), страницы 99–112
  2. ^ Семинар Сержа Бёшера и Кристиана Лантуэя по обработке изображений, краям в реальном времени и обнаружению движения (1979). http://cmm.ensmp.fr/~beucher/publi/watershed.pdf
  3. ^ Барнс, Р., Леман, К., Мулла, Д., 2014. Приоритетное наводнение: оптимальный алгоритм заполнения депрессии и обозначения водоразделов для цифровых моделей рельефа. Компьютеры и науки о Земле 62, 117–127. Дои:10.1016 / j.cageo.2013.04.024
  4. ^ Дж. Кусти, Дж. Бертран, Л. Найман и М. Купри. Вырезы водоразделов: минимальные размеры лесов и принцип капли воды, IEEE Transactions on Pattern Analysis and Machine Intelligence 31 (8) pp. 1362-1374, 2009 г.,
  5. ^ Серж Бойше и Фернан Мейер. Морфологический подход к сегментации: трансформация водораздела. В Математическая морфология в обработке изображений (Под ред. Э. Р. Догерти), страницы 433–481 (1993).
  6. ^ М. Купри, Г. Бертран. Топологическое преобразование серого водораздела. В Proc. ofSPIE 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. Дои:10.1016 / j.cageo.2013.04.024
  10. ^ Барнс, Р., 2016. Параллельное заполнение депрессии приоритетным потоком для цифровых моделей рельефа триллиона ячеек на настольных компьютерах или кластерах. Компьютеры и науки о Земле. Дои:10.1016 / j.cageo.2016.07.001
  11. ^ Дорр, Ф. Дж. С., и Флоренс, А. Дж. (2020). Анализ изображений микро-XRT и методология машинного обучения для характеристики составов капсул с несколькими частицами. Международный журнал фармацевтики: X, 2, 100041. https://doi.org/10.1016/j.ijpx.2020.100041
  12. ^ Жан Кусти, Жиль Бертран, Лоран Наджман и Мишель Купри. Вырезы водоразделов: минимальные размеры лесов и принцип капли воды. IEEE Transactions по анализу шаблонов и машинному анализу. 31 (8). Август 2009. С. 1362–1374.
  13. ^ Седрик Аллен, Жан-Ив Одибер, Мишель Купри и Рено Керивен: "Некоторые связи между минимальными вырубками, оптимальной протяженностью лесов и водоразделами ", Image and Vision Computing, 2009 г.
  14. ^ Фалькао, А. Стольфи, Дж. Де Аленкар Лотуфо, Р.: "Преобразование лесовосстановления изображений: теория, алгоритмы и приложения ", В ПАМИ, 2004 г.
  15. ^ Жан Кусти, Жиль Бертран, Лоран Наджман и Мишель Купри. Вырубки водоразделов: прореживание, кратчайшие леса и топологические водоразделы. IEEE Transactions по анализу шаблонов и машинному анализу. 32 (5). 2010. С. 925–939.
  16. ^ Грейди, Л .: "Случайные блуждания для сегментации изображений ". ПАМИ, 2006 г.
  17. ^ Камилла Купри, Лео Грейди, Лоран Наджман и Хьюг Талбот "Power Watershads: единая платформа оптимизации на основе графов ”, 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.

Рекомендации

внешняя ссылка