Маркировка подключенного компонента на случайно разделенных данных?

Question

Маркировка подключенного компонента на случайно разделенных данных?

В настоящее время мне поручено реализовать алгоритм CCL в системе баз данных (написано на C ++). Этот алгоритм назначит метку всем значениям данного многомерного массива, превышающим порог, а соседние помеченные значения будут иметь одну и ту же метку.

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

Я не знаю во время выполнения, какой экземпляр отвечает за какую-либо конкретную часть массива, и экземпляры не могут связываться друг с другом до последнего шага слияния.

-= — = — = —

В настоящее время у меня есть эта работа, выполнив следующие действия:

Каждый экземпляр создает массив логических значений размером, равным
количество элементов в массиве и устанавливает все значения в FALSE.
Каждый экземпляр проходит через значения, за которые он отвечает, и
проверяет, превышают ли эти значения пороговое значение; если они, они
измените соответствующее логическое значение в их локальном массиве на TRUE.
Все экземпляры отправляют свои массивы координатору, который
объединяет результаты, используя OR для создания окончательного логического вектора.
Координатор просматривает каждое значение в массиве, пропуская
значения, которые уже помечены. Если значение не помечено и
логическое значение, соответствующее этому значению, равно true, оно присваивает ему
новый ярлык и рекурсивно назначает всех своих соседей (и
соседи соседей и т. д.) того же ярлыка.
Вектор меток возвращается.

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

-= — = — = —

По сути, этот алгоритм автоматически превращается в алгоритм «разделяй и властвуй», но деления совершенно и неуправляемо случайны.

Мы хотим воспользоваться этим делением, выполнив обе развертки CCL для каждого экземпляра, а затем комбинируя эти локальные результаты CCL для координатора; то есть, если два экземпляра создают группы меток, которые соседствуют друг с другом, мы хотим объединить эти две метки без повторного сканирования каждого значения. Этот курсив — это то, что доставляет нам больше всего хлопот, и мы довольно растеряны в отношении того, как действовать дальше. Если у кого-то есть предложения по алгоритмам или структурам данных, которые было бы полезно изучить, это было бы очень полезно.

0

algorithm arrays c++labeling

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

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

То есть,

Определите набор для пар соседних точек:
- { ((x1, y1), (x2, y2)) } для которого
  - Для 4-х подключений: (abs(x2 - x1) + abs(y2 - y1)) <= 1 а также (x1 != x2 && y1 != y2)
  - Для 8-связности: max(abs(x2 - x1), abs(y2 - y1)) <= 1 а также (x1 != x2 && y1 != y2)

Следующий шаг понимания требует знать Отношение эквивалентности. Примечательно, что оно должно удовлетворять:

Рефлексивность
симметричность
транзитивность

Из этих трех требований вытекает интересное следствие:

Предположим, вы получили частичный список отношений эквивалентности, таких как (a, b), (b, c), (c, d), (e, f)
Обратите внимание, что перестановка этого списка, вставка «эквивалентных» отношений эквивалентности (таких как (a, c), учитывая, что (a, b) и (b, c) уже существует) и т. Д.) Не влияют на разбиение.

Необходимо принять во внимание, что интерфейс алгоритма «Disjoint-Set», который будет обсуждаться ниже, является именно списком отношений эквивалентности. Таким образом, можно обработать этот список отношений эквивалентности по-разному и все же получить тот же результат.

к представлять и к описывать алгоритмы, которые вычисляют и обрабатывают связанные компоненты, следует изучить Disjoint-Set.

Нужно изучить фактическую реализацию Disjoint-Set, а также узнать, как она фактически используется (вызывается) из алгоритма связанных компонентов.

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

На этапе строительства только Union Функция должна вызываться из основного цикла.
Find функция используется только внутри Union функция.
Таким образом, можно абстрагировать операции Disjoint-Set, предоставив приемник для потока Union( (x1, y1), (x2, y2) ) сообщение звонки.
Эти вызовы сообщений могут быть асинхронными, помещенными в очередь, произвольно переставленными, пакетными, однако вы хотели бы обрабатывать их, если все такие вызовы в конечном итоге обрабатываются полностью.
Это приведет к избыточным вызовам Unionпотому что не будет проверок, являются ли два узла уже одной и той же меткой до постановки в очередь вызова. Этот вопрос будет рассмотрен в следующей части.

Теперь мы представим способ планирования этих Union сообщения для обработки.

Предположим, что узлы распределены по разным машинам.

Разобьем множество пар смежных пикселей { ((x1, y1), (x2, y2)) } следующее:
- Для каждой машины мы хотели бы найти подмножество пар смежных пикселей, которые находятся на одной машине.
- После этого нам нужно подмножество всего остального — пары смежных пикселей, которые находятся на двух разных машинах.

Чтобы обработать Union-Find на другой машине, достаточно просто
* Создает Union сообщения от одной и той же машины набора пар смежных пикселей
* Затем отфильтруйте Union сообщения для удаления лишних.
* Создает Union сообщения от разных машин набор пар смежных пикселей.
* Выполнять сообщения разных машин над результатами сообщений тех же машин.

Этот ответ написан слишком абстрактно, потому что более конкретный ответ потребует больше подробностей о проблеме, особенно часть о «полностью и неуправляемом случайном разбиении».

0