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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

Причины появления методов на основе графов[править | править код]

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

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

От изображения к графам[править | править код]

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

Алгоритмы сегментации на основе наименьшего остовного дерева[править | править код]

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

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

Примечания[править | править код]

  1. ↑ Haralick, Shapiro, 1985.
  2. ↑ Iivarinen, Peura, Sarela, Visa, 1997, с. 430–439.
  3. ↑ Chen, Pavlidis, 1990, с. 588–594.
  4. ↑ Felzenszwalb, Huttenlocher, 2004.
  5. ↑ Harfst, Reingold, 2000, с. 86–95.
  6. ↑ Wassenberg, Middelmann, Sanders, 2009, с. 1003–1010.

Литература[править | править код]

  • Haralick R., Shapiro L. Image Segmentation Techniques // CVGIP. — 1985. — Январь (вып. 29).
  • Iivarinen J., Peura M., Sarela J., Visa A. Comparison of combined shape descriptors for irregular objects // 8th BMVC. — 1997.
  • Chen M.-H., Pavlidis T. Image seaming for segmentation on parallel architecture // PAMI. — 1990. — Июнь (т. 12, вып. 6).
  • Felzenszwalb P., Huttenlocher D. Efficient Graph-Based Image Segmentation // IJCV. — 2004. — Сентябрь (т. 59, вып. 2).
  • Harfst G., Reingold E. A Potential-Based Amortized Analysis of the Union-Find Data Structure // SIGACT. — 2000. — Сентябрь (т. 31).
  • Wassenberg J., Middelmann W., Sanders P. An Efficient Parallel Algorithm for Graph-Based Image Segmentation // Computer Analysis of Images and Patterns. — 2009. — Т. 5702. — (LNCS).

Ссылки[править | править код]

Источник — https://ru.wikipedia.org/w/index.php?title=Сегментация_изображений_на_основе_минимального_остовного_дерева&oldid=111714236