Сегментация изображений на основе минимального остовного дерева позволяет разбить цифровое изображение на области точек с похожими свойствами, например, по однородности. Представление областей изображения высокого уровня упрощает задачи анализа изображения, такие как подсчёт объектов или обнаружение изменений, поскольку свойства области (например, средняя яркость или форма) могут сравниваться легче, чем просто пиксели.
Причины появления методов на основе графов Для ускорения сегментации больших изображений работа может быть разделена нескольким ЦПУ. Это означает выполнение разбиения изображения на плитки (области), которые обрабатываются независимо. Однако области, заходящие за границу плитки, могут быть расщеплены или потеряны, если фрагменты не удовлетворяют требованиям минимального размера фрагментов для алгоритма сегментации. Тривиальный обход проблемы заключается в перекрытии плиток, то есть, когда позволяется каждому процессору рассматривать дополнительные пиксели около границы плитки. К сожалению, это увеличивает загрузку процессоров, поскольку процессоры на обеих сторонах границы плитки осуществляют избыточную работу. Также только объекты, меньшие перекрытия плиток, гарантированно сохраняются, это означает, что длинные объекты, такие как реки при воздушной съёмке, с большой вероятностью будут разбиты на части. В некоторых случаях независимые плитки могут быть слиты с получением примерно правильных результатов.
Альтернатива существует в виде методов сегментации на основе графов. Присущая графам информация о связности позволяет проведение независимой работы на частях исходного изображения с последующим соединением этой работы для получения точного результата, как если бы обработка шла глобально.
От изображения к графам Возможность вместе независимых частей изображения подталкивает к добавлению к пикселям информации о связности. Это может рассматриваться как граф, узлами (вершинами) которого являются пиксели, а рёбра представляют связи между пикселями. Простым и сравнительно эффективным по памяти вариантом этого графа является решётка, где каждый пиксель связан с соседними по четырём сторонам света. Поскольку связь соседей пикселя симметрична, результирующий граф является неориентированным и только половина его рёбер (например, к каждому восточному и южному соседу) необходимо сохранять. На конечном шаге алгоритм занимается кодированием информации о похожести по весам рёбер, так что исходное изображение больше не нужно. В простейшем случае веса рёбер вычисляется как разница интенсивности пикселей.
Алгоритмы сегментации на основе наименьшего остовного дерева Минимальное остовное дерево (, MST) является подмножеством рёбер минимального веса графа без циклов, таким, что все узлы этими рёбрами связаны. В 2004 Фелценцвальб предложил метод сегментации, основанный на MST алгоритме Краскала. Рёбра рассматриваются в порядке возрастания веса, их конечные точки (пиксели) включаются в области, если они не образуют цикла в графе и пиксели «подобны» существующим пикселям областей. Обнаружение циклов возможно за почти постоянное время с помощью системы непересекающихся множеств. Похожесть пикселей решается эвристически, сравнивая веса с посегментными порогами. Алгоритм получает несколько различных MST (остовных деревьев), то есть лес. Каждое дерево соответствует сегменту. Сложность алгоритма квазилинейная, поскольку сортировка рёбер возможна за линейное время через сортировку подсчётом.
В 2009 Вассенберг с сотрудниками разработал алгоритм, который вычисляет несколько независимых минимальных остовных лесов (), а затем сшивает их вместе. Это позволяет параллельную обработку без разбиения объектов границами плиток. Вместо фиксированного порогового значения веса используется начальная для оценки нижней границы порогового значения, которая может сократить как пересегментацию, так и недосегментацию. Измерения показывают, что реализация превосходит последовательный алгоритм Фелценцвальба на порядок.
Примечания
Литература
Ссылки Information on the PHMSF algorithm (Parallel Heuristic for Minimum Spanning Forests)
Категория:Остовное дерево Категория:Сегментация изображений