Сегментация на основе минимального остовного дерева - Minimum spanning tree-based segmentation

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

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

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

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

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

Минимальные алгоритмы сегментации связующего дерева

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

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

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

использованная литература

  1. ^ Р. Харалик, Л. Шапиро: методы сегментации изображений. CVGIP 29 (январь 1985 г.)
  2. ^ J. Iivarinen, M. Peura, J. Sarela, A. Visa: Сравнение дескрипторов комбинированных форм для объектов неправильной формы. В: BMVC (1997), стр. 430–439.
  3. ^ М.-Х. Чен, Т. Павлидис: Сшивание изображений для сегментации на параллельной архитектуре. ПАМИ Том. 12 (6), июнь 1990 г., стр. 588–594
  4. ^ П. Фельценшвалб, Д. Хуттенлохер: Эффективная сегментация изображений на основе графов. IJCV 59 (2) (сентябрь 2004 г.)
  5. ^ Г. Харфст, Э. Рейнгольд: потенциальный амортизированный анализ структуры данных Union-Find. SIGACT 31 (сентябрь 2000 г.), стр. 86–95
  6. ^ Дж. Вассенберг, В. Мидделманн, П. Сандерс: Эффективный параллельный алгоритм для сегментации изображений на основе графов. В: Компьютерный анализ изображений и паттернов, LNCS Vol. 5702 (сентябрь 2009 г.) стр. 1003–1010
  7. ^ А. Саглам, Н. А. Байкан: Последовательная сегментация изображений на основе представления минимального остовного дерева. Письма о распознавании образов 87 (2017), стр. 155-162

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