Сегментация на основе минимального остовного дерева

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

Мотивация для графических методов

Чтобы ускорить сегментацию больших изображений, работа может быть разделена между несколькими ЦП . Одним из способов достижения этого является разбиение изображений на плитки, которые обрабатываются независимо. Однако регионы, которые охватывают границу плитки, могут быть разделены или потеряны, если фрагменты не соответствуют минимальным требованиям алгоритма сегментации к размеру. Тривиальный обходной путь включает перекрытие плиток, то есть разрешение каждому процессору учитывать дополнительные пиксели вокруг границы своей плитки. К сожалению, это увеличивает вычислительную нагрузку, поскольку процессоры по обе стороны границы плитки выполняют избыточную работу. Кроме того, гарантированно сохраняются только объекты, меньшие, чем перекрытие плитки, что означает, что длинные объекты, такие как реки на аэрофотоснимках, по-прежнему, вероятно, будут разделены. В некоторых случаях результаты независимых плиток могут быть объединены для приближения к истинным результатам. [3] Альтернатива существует в виде методов сегментации на основе графов. Информация о связности, присущая графам, позволяет выполнять независимую работу над частями исходного изображения и повторно соединять их для получения точного результата, как если бы обработка происходила глобально.

От изображений к графикам

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

Алгоритмы сегментации минимального остовного дерева

Минимальное остовное дерево (MST) — это подмножество ребер графа с минимальным весом и без циклов , в котором все узлы соединены. В 2004 году Фельценшвальб представил метод сегментации [4], основанный на алгоритме MST Крускала . Ребра рассматриваются в порядке возрастания веса; их конечные пиксели объединяются в регион, если это не приводит к образованию цикла в графе и если пиксели «похожи» на пиксели существующих регионов. Обнаружение циклов возможно за почти постоянное время с помощью структуры данных непересекающегося множества . [5] Сходство пикселей оценивается эвристикой, которая сравнивает вес с пороговым значением для каждого сегмента. Алгоритм выводит несколько непересекающихся MST, т. е. лес; каждое дерево соответствует сегменту. Сложность алгоритма квазилинейна, поскольку сортировка ребер возможна за линейное время с помощью сортировки подсчетом .

В 2009 году Вассенберг и др. разработали алгоритм [6] , который вычисляет несколько независимых Минимальных Покрывающих Лесов, а затем сшивает их вместе. Это позволяет выполнять параллельную обработку без разделения объектов на границах плиток. Вместо фиксированного порогового значения веса используется начальная маркировка связанных компонентов для оценки нижней границы порогового значения, что может уменьшить как избыточную, так и недостаточную сегментацию. Измерения показывают, что реализация превосходит последовательный алгоритм Фельценшвальба на порядок.

В 2017 году Саглам и Байкан использовали последовательное представление Прима минимального остовного дерева и предложили новый критерий разрезания для сегментации изображений. [7] Они построили MST с помощью алгоритма MST Прима, используя структуру данных кучи Фибоначчи. Метод достигает важного успеха на тестовых изображениях за короткое время выполнения.

Ссылки

  1. ^ Харалик, Роберт М.; Шапиро , Линда Г. (январь 1985 г.), «Методы сегментации изображений», Computer Vision, Graphics, and Image Processing , 29 (1): 100–132 , doi :10.1016/s0734-189x(85)90153-7
  2. ^ Ииваринен, Юкка; Пеура, Маркус; Сареля, Яакко; Виса, Ари (1997), «Сравнение комбинированных дескрипторов формы для нерегулярных объектов», в Кларк, Адриан Ф. (ред.), Труды Британской конференции по машинному зрению 1997, BMVC 1997, Университет Эссекса, Великобритания, 1997 , Британская ассоциация машинного зрения
  3. ^ Чен, Минхуа; Павлидис, Теодосиос (1990), «Сшивание изображений для сегментации на параллельной архитектуре», Труды IEEE по анализу образов и машинному интеллекту , 12 (6): 588– 594, doi :10.1109/34.56195
  4. ^ Фельценсвальб, Педро Ф .; Хуттенлохер, Дэниел П. (2004), «Эффективная сегментация изображений на основе графов», Международный журнал компьютерного зрения , 59 (2): 167– 181, doi :10.1023/B:VISI.0000022288.19776.77, S2CID  207663697
  5. ^ Харфст, Грегори К.; Рейнгольд, Эдвард М. (2000), «Амортизированный анализ структуры данных union-find на основе потенциала», SIGACT News , 31 (3): 86–95 , doi :10.1145/356458.356463, S2CID  14779624
  6. ^ Вассенберг, Ян; Миддельманн, Вольфганг; Сандерс, Питер (2009), «Эффективный параллельный алгоритм для сегментации изображений на основе графов», в Цзян, Сяои; Петков, Николай (ред.), Компьютерный анализ изображений и шаблонов, 13-я международная конференция, CAIP 2009, Мюнстер, Германия, 2-4 сентября 2009 г., Труды , Lecture Notes in Computer Science, т. 5702, Springer, стр.  1003–1010 , doi :10.1007/978-3-642-03767-2_122, ISBN 978-3-642-03766-5
  7. ^ Sağlam, Ali; Baykan, Nurdan Akhan (2017), «Последовательная сегментация изображений на основе представления минимального остовного дерева», Pattern Recognition Letters , 87 : 155–162 , Bibcode : 2017PaReL..87..155S, doi : 10.1016/j.patrec.2016.06.001
  • Информация об алгоритме PHMSF (параллельная эвристика для минимального остовного леса)
Взято с "https://en.wikipedia.org/w/index.php?title=Минимальная_сегментация_на_основе_дерева_связывания&oldid=1187577789"