Сегментирование двойного массива меток

Question

Проблема:

У меня есть большой двойной (2d) массив, заполненный различными метками.Каждый элемент (ячейка) в массиве double содержит набор меток, а некоторые элементы в массиве double могут быть пустыми.Мне нужен алгоритм для группировки элементов в двойном массиве в отдельные сегменты.Сегмент определяется как набор пикселей, которые находятся рядом в двойном массиве, и одна метка, которая является общей для всех этих пикселей в сегменте.(Диагональная смежность не считается, и я не кластеризирую пустые ячейки).

|-------|-------|-------|
| Jane  | Joe   |       |
| Jack  | Jane  |       |
|-------|-------|-------|
| Jane  | Jane  |       |
|       | Joe   |       |
|-------|-------|-------|
|       | Jack  | Jane  |
|       | Joe   |       |
|-------|-------|-------|

В приведенном выше расположении меток, распределенных по девяти элементам, самый большой кластер - это кластер «Jane», занимающий четыре верхнихлевые ячейки.

Что я учел:

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

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

Почему мне это не нравится:

Как иПриведенный выше алгоритм не учитывает случай, когда элемент в двойном массиве может быть связан с двумя уникальными сегментами, один в горизонтальном направлении и один в вертикальном направлении.Чтобы правильно обрабатывать эти случаи, мне нужно будет выполнить тест для этого конкретного случая, а затем реализовать метод, который будет связывать проверяемый элемент с сегментом, а затем объединять два смежных идентичных сегмента.

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

Есть предложения?

Редактировать:

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

Segment 1 - Jane: (1,3), (2,3), (1,2), (2,2)
Segment 2 - Joe: (2,3), (2,2), (2,1)

Answer 1

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

Повторите для всех ярлыков, и все готово.

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

Я собираюсь назвать одну запись "пикселем""и весь массив -" изображение ".

Алгоритм примерно равен

for each pixel in the image
  for each label in the pixel
    1. remove the label
    2. mark the current pixel
    3. for each marked pixel, look in every adjacent pixel for the label
    4. remove any labels found
    5. if labels are found, clear marks, and mark the newly label-removed pixels
    6. if anything is marked, go back to 3
    7. report the set of points where you removed labels

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