Как использовать непересекающиеся наборы в маркировке подключенных компонентов?

Question

Мне трудно использовать непересекающиеся наборы в маркировке подключенных компонентов. Я рассмотрел много примеров, а также этот вопрос , где Bo Tian обеспечил очень хорошую реализацию Disjoint Sets в виде связанного списка C ++. Я уже реализовал в своей программе маркировку подключенного компонента (метки - это простые целые числа), но мне очень трудно разрешать эквивалентности среди меток с непересекающимися наборами.

Может кто-нибудь помочь мне в этом - возможно, используя реализацию Бо Тиана? Я думаю, что это также поможет другим, когда они придут к этому.

EDIT

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

Answer 1

Лес с несвязанным множеством предоставляет две операции:

• Объединение , которое берет два объекта и связывает их, и
• Найти , который принимает два объекта и возвращает идентификатор группы, в которой они находятся.

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

Чтобы использовать лес несвязанного множества,вы бы начали с помещения каждого объекта в свой кластер.С этого момента, каждый раз, когда вы хотите отметить, что два разных объекта находятся в одном кластере, вы будете использовать операцию union , чтобы связать их вместе.В самом конце, вы бы позвонили find в каждой точке, чтобы определить, к какому кластеру она принадлежит, и оттуда могли бы прочитать, к какой группе все принадлежит.

Надеюсь, это поможет!

Answer 2

Есть блог о маркировке подключенных компонентов с несвязанным набором:

http://www.keithlantz.net/2011/04/c-implementation-of-the-connected-component-labeling-method-using-the-disjoint-set-data-structure/

Answer 3

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

Один из способов найти непересекающиеся множества (после маркировки) - использовать алгоритм Union-Find .Проверьте следующую статью.Вы поймете с нуля, как реализована маркировка и поиск непересекающихся множеств.Иллюстрации также приведены с образцами входных и выходных матриц.

http://www.codeding.com/articles/connected-sets-labeling

Answer 4

Проверьте это руководство по DJS . Единственная модификация состоит в том, что во время объединения вы должны соединять большее с меньшим, поэтому root всегда является минимальным из набора.