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

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

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

Рельеф величины градиента
Изображение величины градиента
Водораздел градиента
Водораздел градиента (рельеф)

Определения

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Алгоритм заливки Мейера

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

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

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

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

Алгоритмы оптимального остовного леса (вырезы водораздела)

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

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

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

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

В 2007 г. К. Аллен и др. ^[13] установлены связи, связывающие сокращения графов с оптимальными остовными лесами. Точнее, они показывают, что когда мощность весов графа превышает определенное число, разрез, минимизирующий энергию сокращений графа, является разрезом по максимальному остовному лесу.

Леса с кратчайшим путем

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

Случайный ходок

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

Иерархии

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

Примечания

^ Л. Найман и М. Шмитт. Водораздел непрерывной функции . В книге «Обработка сигналов» (Специальный выпуск по математической морфологии), Vol. 38 (1994), страницы 99–112.
^ Семинар Сержа Бейшера и Кристиана Лантуежа по обработке изображений, обнаружению границ в реальном времени и движению (1979). http://cmm.ensmp.fr/~beucher/publi/watershed.pdf
^ Барнс, Р., Леман, К., Мулла, Д., 2014. Приоритетное наводнение: оптимальный алгоритм заполнения впадин и маркировки водоразделов для цифровых моделей рельефа . Компьютеры и науки о Земле 62, 117–127. дои : 10.1016/j.cageo.2013.04.024
^ Дж. Кусти, Г. Бертран, Л. Наджман и М. Купри. Сокращение водораздела: минимальные охватывающие леса и принцип капли воды , Транзакции IEEE по анализу шаблонов и машинному интеллекту 31 (8), стр. 1362-1374, 2009 г.,
^ Серж Бойшер и Фернан Мейер. Морфологический подход к сегментации: водораздельная трансформация . В книге «Математическая морфология в обработке изображений» (под ред. Э. Р. Догерти), страницы 433–481 (1993).
^ М. Купри, Г. Бертран. Топологическое преобразование водораздела в оттенках серого. В 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
^ Г. Бертран. О топологических водоразделах . Журнал математического изображения и видения, 22 (2–3), страницы 217–230 (2005).
^ Мишель Купри, Лоран Нажман, Жиль Бертран. Квазилинейные алгоритмы для топологического водораздела . Журнал математического изображения и видения, Springer Verlag, 2005, 22 (2–3), стр. 231–249.
^ Барнс, Р., Леман, К., Мулла, Д., 2014. Приоритетное наводнение: оптимальный алгоритм заполнения впадин и маркировки водоразделов для цифровых моделей рельефа . Компьютеры и науки о Земле 62, 117–127. дои : 10.1016/j.cageo.2013.04.024
^ Барнс, Р., 2016. Параллельное заполнение впадин с приоритетом наводнения для цифровых моделей рельефа с триллионом ячеек на настольных компьютерах или кластерах. Компьютеры и геонауки. дои : 10.1016/j.cageo.2016.07.001
^ Дорр, FJS, и Флоренс, AJ (2020). Методика анализа микрорентгеновских изображений и машинного обучения для характеристики составов капсул, состоящих из нескольких частиц. Международный фармацевтический журнал: X, 2, 100041. https://doi.org/10.1016/j.ijpx.2020.100041.
^ Жан Кусти, Жиль Бертран, Лоран Нажман и Мишель Купри. Вырубка водораздела: минимальные леса и принцип капли воды . Транзакции IEEE по анализу шаблонов и машинному интеллекту. 31 (8). Август 2009 г., стр. 1362–1374.
^ Седрик Аллен, Жан-Ив Одибер, Мишель Купри и Рено Керивен: « Некоторые связи между минимальными вырубками, оптимальным охватом лесов и водоразделами », Image and Vision Computing, 2009.
^ Фалькао, А. С. Столфи, Ж. де Аленкар Лотуфо, Р.: « Преобразование леса изображений: теория, алгоритмы и приложения », В PAMI, 2004 г.
^ Жан Кусти, Жиль Бертран, Лоран Нажман и Мишель Купри. Вырезы водоразделов: прореживания, кратчайшие леса и топологические водоразделы . Транзакции IEEE по анализу шаблонов и машинному интеллекту. 32 (5). 2010. стр. 925–939.
^ Грейди, Л.: « Случайные блуждания для сегментации изображений ». ПАМИ, 2006 г.
^ Камилла Купри, Лео Грейди, Лоран Наджман и Хью Талбот, « Водоразделы власти: унифицированная структура оптимизации на основе графов », Транзакции IEEE по анализу шаблонов и машинному интеллекту, том 33, № 7, стр. 1384-1399, июль 2011 год
^ Лоран Найман, Мишель Шмитт. Геодезическая заметность водораздельных контуров и иерархическая сегментация . Транзакции IEEE по анализу закономерностей и машинному интеллекту, Институт инженеров по электротехнике и электронике, 1996, 18 (12), стр. 1163–1173.
^ Лоран Наджман. Об эквивалентности иерархических сегментаций и ультраметрических водоразделов . Журнал математического изображения и видения, Springer Verlag, 2011, 40 (3), стр. 231–247.

Ссылки

Фернан Мейер. Оптимальный алгоритм для водораздела. Через 8 ^мне Конгресс по распознаванию образов и искусственному интеллекту , Vol. 2 (1991), страницы 847–857, Лион, Франция.
Люк Винсент и Пьер Сойль. Водоразделы в цифровых пространствах: эффективный алгоритм, основанный на иммерсионном моделировании . В транзакциях IEEE по анализу шаблонов и машинному интеллекту , Vol. 13, Числ. 6 (1991), страницы 583–598.
Л. Найман и М. Шмитт. Геодезическая заметность контуров водоразделов и иерархическая сегментация . В транзакциях IEEE по анализу шаблонов и машинному интеллекту , Vol. 18, Числ. 12 (1996), страницы 1163–1173.
JBTM Рёрдинк и А. Мейстер. Водораздельное преобразование: определения, алгоритмы и стратегии распараллеливания . В Fundamenta Informaticae 41 (2000), стр. 187–228.
Лоран Нажман, Мишель Купри и Жиль Бертран. Водоразделы, мозаика и парадигма возникновения . В книге «Дискретная прикладная математика» , Vol. 147, Числ. 2–3 (2005), страницы 301–324.

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

Преобразование водораздела с анимацией алгоритма водораздела.
Топологическое преобразование водораздела с статьями, слайдами лекций и исходным кодом.
Плагин водораздела с открытым исходным кодом для ImageJ .
The Topology ToolKit (2D и 3D водоразделы на основе комплекса Морзе )

[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 по анализу шаблонов и машинному интеллекту 31 (8), стр. 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] Г. Бертран. О топологических водоразделах . Журнал математического изображения и видения, 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] Дорр, FJS, и Флоренс, AJ (2020). Методика анализа микрорентгеновских изображений и машинного обучения для характеристики составов капсул, состоящих из нескольких частиц. Международный фармацевтический журнал: X, 2, 100041. https://doi.org/10.1016/j.ijpx.2020.100041.

[12] Жан Кусти, Жиль Бертран, Лоран Нажман и Мишель Купри. Вырубка водораздела: минимальные леса и принцип капли воды . Транзакции IEEE по анализу шаблонов и машинному интеллекту. 31 (8). Август 2009 г., стр. 1362–1374.

[13] Седрик Аллен, Жан-Ив Одибер, Мишель Купри и Рено Керивен: « Некоторые связи между минимальными вырубками, оптимальным охватом лесов и водоразделами », Image and Vision Computing, 2009.

[14] Фалькао, А. С. Столфи, Ж. де Аленкар Лотуфо, Р.: « Преобразование леса изображений: теория, алгоритмы и приложения », В PAMI, 2004 г.

[15] Жан Кусти, Жиль Бертран, Лоран Нажман и Мишель Купри. Вырезы водоразделов: прореживания, кратчайшие леса и топологические водоразделы . Транзакции IEEE по анализу шаблонов и машинному интеллекту. 32 (5). 2010. стр. 925–939.

[16] Грейди, Л.: « Случайные блуждания для сегментации изображений ». ПАМИ, 2006 г.

[17] Камилла Купри, Лео Грейди, Лоран Наджман и Хью Талбот, « Водоразделы власти: унифицированная структура оптимизации на основе графов », Транзакции IEEE по анализу шаблонов и машинному интеллекту, том 33, № 7, стр. 1384-1399, июль 2011 год

[18] Лоран Найман, Мишель Шмитт. Геодезическая заметность водораздельных контуров и иерархическая сегментация . Транзакции IEEE по анализу закономерностей и машинному интеллекту, Институт инженеров по электротехнике и электронике, 1996, 18 (12), стр. 1163–1173.

[19] Лоран Наджман. Об эквивалентности иерархических сегментаций и ультраметрических водоразделов . Журнал математического изображения и видения, Springer Verlag, 2011, 40 (3), стр. 231–247.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]