поиск компонент связности

scorobei42ru

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

BSCurt

компонент связности в матрице из нулей и единиц
Что это вообще такое?

nely25

Я так понял, речь о сегментации изображений (image segmentation но каких-то странных, двуцветных.

BoBochka

Это называется задачей поиска компонент связности (blobs) на бинарном изображении (binary image). Погуглите по ключевым словам вроде следующих: blob analysis for a binary image, blob detection.
Имеются готовые библиотеки для blob analysis. Поищите в интернете, что Вам лучше подходит.
Вообще же, если писать код на С++ (или Java думаю, проще всего взять библиотеку OpenCV и использовать её методы контурного анализа для поиска компонент связности на бинарном изображении.

BoBochka

проще всего взять библиотеку OpenCV и использовать её методы контурного анализа для поиска компонент связности на бинарном изображении.
А можно написать свой алгоритм поиска (замкнутых) контуров на бинарном изображении. Вроде бы этот алгоритм не очень сложный (см. инет).

Vikuschechka9

а может это матрица инцидентности

stm7543347

Я так понял, речь о сегментации изображений (image segmentation но каких-то странных, двуцветных.
Я так понял, речь о компонентах связности графов.

scorobei42ru

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

scorobei42ru

нет, это не матрица инцидентности вершин графа, а просто матрица из нулей и единиц. компонента связности - максимальное множество точек (то есть индексов - позиций в матрице таких что в матрице на соответствующих местах стоят 1, и из каждой в каждую можно пройти по пути, в котором каждая следующая точка-сосед предыдущей, и в матрице на соотв. местах 1.
Оставить комментарий
Имя или ник:
Комментарий: