Сегментация на основе минимального связующего дерева
Сегментация изображения направлена на разделение цифрового изображения на области пикселей со схожими свойствами, например однородностью. [1] Представление области более высокого уровня упрощает задачи анализа изображений, такие как подсчет объектов или обнаружение изменений, поскольку атрибуты области (например, средняя интенсивность или форма) [2] ) сравнивать легче, чем необработанные пиксели.
Мотивация использования графовых методов
[ редактировать ]Чтобы ускорить сегментацию больших изображений, работу можно было разделить между несколькими процессорами . Одним из способов достижения этой цели является разделение изображений на фрагменты, которые обрабатываются независимо. Однако регионы, расположенные между границей фрагмента, могут быть разделены или потеряны, если фрагменты не соответствуют минимальным требованиям к размеру алгоритма сегментации. Тривиальный обходной путь заключается в перекрытии тайлов, то есть позволяет каждому процессору учитывать дополнительные пиксели вокруг границы тайла. К сожалению, это увеличивает вычислительную нагрузку, поскольку процессоры по обе стороны границы тайла выполняют избыточную работу. Кроме того, гарантированно сохраняются только объекты, размер которых меньше перекрытия плитки, а это означает, что длинные объекты, такие как реки на аэрофотоснимках, по-прежнему могут быть разделены. В некоторых случаях результаты независимых плиток можно объединить, чтобы приблизить истинные результаты. [3] Альтернатива существует в виде методов сегментации на основе графов. Информация о связности, присущая графам, позволяет выполнять независимую работу над частями исходного изображения и повторно соединять их для получения точного результата, как если бы обработка происходила глобально.
От изображений к графикам
[ редактировать ]Возможность объединения независимых фрагментов изображений мотивирует добавлять к пикселям информацию о связности. Это можно рассматривать как граф, узлами которого являются пиксели, а ребра представляют связи между пикселями. Простой и сравнительно компактный вариант — это граф-сетка , в которой каждый пиксель связан со своими соседями в четырех основных направлениях . Поскольку отношение соседства пикселей симметрично, результирующий граф является неориентированным , и необходимо сохранить только половину его ребер (например, восточного и южного соседа каждого пикселя). Последний шаг требует кодирования информации о сходстве пикселей в весах ребер, чтобы исходное изображение больше не требовалось. В простейшем случае веса ребер вычисляются как разница интенсивностей пикселей.
Алгоритмы сегментации минимального связующего дерева
[ редактировать ]Минимальное связующее дерево с минимальным весом и без циклов (MST) — это подмножество ребер графа , в котором все узлы соединены. В 2004 году Фельценшвальб представил метод сегментации. [4] на основе алгоритма MST Крускала . Ребра рассматриваются в порядке возрастания веса; их конечные пиксели объединяются в регион, если это не вызывает цикличности графика и если пиксели «похожи» на пиксели существующих регионов. Обнаружение циклов возможно практически за постоянное время с помощью структуры данных с непересекающимся набором данных . [5] Сходство пикселей оценивается с помощью эвристики, которая сравнивает вес с пороговым значением для каждого сегмента. Алгоритм выводит несколько непересекающихся MST, т.е. лес; каждое дерево соответствует сегменту. Сложность алгоритма квазилинейна, поскольку сортировка ребер возможна за линейное время посредством подсчета sort .
В 2009 году Вассенберг и др. разработал алгоритм [6] который вычисляет несколько независимых минимальных охватывающих лесов, а затем объединяет их вместе. Это обеспечивает параллельную обработку без разделения объектов по границам плитки. Вместо фиксированного порога веса начальная маркировка связанных компонентов для оценки нижней границы порога используется , что может уменьшить как чрезмерную, так и недостаточную сегментацию. Измерения показывают, что реализация на порядок превосходит последовательный алгоритм Фельценшвалба.
В 2017 году Саглам и Байкан использовали последовательное представление минимального остовного дерева Прима и предложили новый критерий разрезания для сегментации изображений. [7] Они создают MST с помощью алгоритма MST Прима, используя структуру данных кучи Фибоначчи. Этот метод достигает важных успехов на тестовых изображениях за короткое время выполнения.
Ссылки
[ редактировать ]- ^ Харалик, Роберт М .; Шапиро, Линда Г. (январь 1985 г.), «Методы сегментации изображений», Компьютерное зрение, графика и обработка изображений , 29 (1): 100–132, doi : 10.1016/s0734-189x(85)90153-7
- ^ Иваринен, Юкка; Пеура, Маркус; Сареля, Яакко; Виза, Ари (1997), «Сравнение комбинированных дескрипторов формы объектов неправильной формы» , Кларк, Адриан Ф. (редактор), Труды Британской конференции по машинному зрению, 1997, BMVC 1997, Университет Эссекса, Великобритания, 1997 , Британский Ассоциация машинного зрения
- ^ Чен, Минхуа; Павлидис, Теодосиос (1990), «Сшивание изображений для сегментации в параллельной архитектуре», Транзакции IEEE по анализу шаблонов и машинному интеллекту , 12 (6): 588–594, doi : 10.1109/34.56195
- ^ Фельценшвальб, Педро Ф .; Хуттенлохер, Дэниел П. (2004), «Эффективная сегментация изображений на основе графов», International Journal of Computer Vision , 59 (2): 167–181, doi : 10.1023/B:VISI.0000022288.19776.77 , S2CID 207663697
- ^ Харфст, Грегори К.; Рейнгольд, Эдвард М. (2000), «Амортизированный анализ структуры данных объединения и поиска на основе потенциала», SIGACT News , 31 (3): 86–95, doi : 10.1145/356458.356463 , S2CID 14779624
- ^ Вассенберг, Ян; Миддельманн, Вольфганг; Сандерс, Питер (2009), «Эффективный параллельный алгоритм для сегментации изображений на основе графов», Цзян, Сяои; Петков, Николай (ред.), Компьютерный анализ изображений и закономерностей, 13-я Международная конференция, CAIP 2009, Мюнстер, Германия, 2–4 сентября 2009 г., Материалы докладов , Конспекты лекций по информатике, том. 5702, Springer, стр. 1003–1010, doi : 10.1007/978-3-642-03767-2_122 , ISBN. 978-3-642-03766-5
- ^ Саглам, Али; Байкан, Нурдан Ахан (2017), «Последовательная сегментация изображений на основе минимального представления связующего дерева», Pattern Recognition Letters , 87 : 155–162, Bibcode : 2017PaReL..87..155S , doi : 10.1016/j.patrec.2016.06. 001