stringtranslate.com

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

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

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

Определения

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

Водораздел затоплением

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

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

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

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

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

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

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

  1. Пометьте каждый минимум отдельной меткой. Инициализируйте множество S с помеченными узлами.
  2. Извлеките из S узел x минимальной высоты F , то есть F ( x ) = min{ F ( y )| y  ∈  S }. Присвойте метку x каждому непомеченному узлу y, смежному с x , и вставьте y в  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 и др. [13] установили связи, связывающие Graph Cuts с оптимальными остовными лесами. Точнее, они показали, что когда мощность весов графа превышает определенное число, разрез, минимизирующий энергию разрезов графа, является разрезом по максимальному остовному лесу.

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

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

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

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

Иерархии

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

Примечания

  1. ^ Л. Наджман и М. Шмитт. Водораздел непрерывной функции. В журнале Signal Processing (Специальный выпуск по математической морфологии.), том 38 (1994), страницы 99–112.
  2. ^ Семинар Сержа Бёшера и Кристиана Лантуежа по обработке изображений, обнаружению контуров и движения в реальном времени (1979). http://cmm.ensmp.fr/~beucher/publi/watershed.pdf
  3. ^ Barnes, R., Lehman, C., Mulla, D., 2014. Priority-flood: Оптимальный алгоритм заполнения впадин и маркировки водоразделов для цифровых моделей рельефа. Computers & Geosciences 62, 117–127. doi :10.1016/j.cageo.2013.04.024
  4. ^ J. Cousty, G. Bertrand, L. Najman и M. Couprie. Водораздельные разрезы: минимальное покрытие лесов и принцип падения воды, IEEE Transactions on Pattern Analysis and Machine Intelligence 31(8) стр. 1362-1374, 2009,
  5. ^ Серж Беухер и Фернанд Мейер. Морфологический подход к сегментации: преобразование водораздела. В «Математической морфологии в обработке изображений » (ред. ER Dougherty), страницы 433–481 (1993).
  6. ^ M. Couprie, G. Bertrand. Топологическое преобразование водораздела в оттенках серого. В Proc. of 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. ^ Barnes, R., Lehman, C., Mulla, D., 2014. Priority-flood: Оптимальный алгоритм заполнения впадин и маркировки водоразделов для цифровых моделей рельефа. Computers & Geosciences 62, 117–127. doi :10.1016/j.cageo.2013.04.024
  10. ^ Barnes, R., 2016. Параллельное приоритетное заполнение понижений уровня воды для цифровых моделей рельефа с триллионами ячеек на настольных компьютерах или кластерах. Компьютеры и науки о Земле. doi :10.1016/j.cageo.2016.07.001
  11. ^ Doerr, FJS, & Florence, AJ (2020). Анализ изображений микро-XRT и методология машинного обучения для характеристики составов капсул из нескольких частиц. Международный журнал фармацевтики: 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. ^ Фалькао, А. X. Столфи, Х. де Аленкар Лотуфо, Р.: «Преобразование леса изображений: теория, алгоритмы и приложения», в PAMI, 2004
  15. ^ Жан Кусти, Жиль Бертран, Лоран Наджман и Мишель Купри. Водораздельные разрезы: прореживания, леса кратчайших путей и топологические водоразделы. Труды IEEE по анализу паттернов и машинному интеллекту. 32 (5). 2010. С. 925–939.
  16. ^ Грейди, Л.: «Случайные блуждания для сегментации изображений». PAMI, 2006
  17. ^ Камиль Купри, Лео Грейди, Лоран Наджман и Хьюз Талбот, «Энергетические водоразделы: унифицированная графовая оптимизационная структура», Труды IEEE по анализу шаблонов и машинному интеллекту, том 33, № 7, стр. 1384-1399, июль 2011 г.
  18. ^ Лоран Наджман, Мишель Шмитт. Геодезическая выпуклость контуров водоразделов и иерархическая сегментация. Труды IEEE по анализу паттернов и машинному интеллекту, Институт инженеров по электротехнике и электронике, 1996, 18 (12), стр. 1163-1173.
  19. ^ Лоран Наджман. Об эквивалентности иерархических сегментаций и ультраметрических водоразделов. Журнал математической визуализации и зрения, Springer Verlag, 2011, 40 (3), стр. 231-247.

Ссылки

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