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