Алгоритм маркировки подключенных компонентов в Python

Question

У меня есть изображение в оттенках серого, написанное от руки. Я хочу извлечь компоненты из этого серого изображения, применяя алгоритм CCL с 8 путями. Пожалуйста, предоставьте код на python, чтобы сделать это только путем импорта OpenCV и numpy. Я разработал неполный код, если кто-то может выполнить эту задачу, которая будет очень полезна для меня.

Вот алгоритм:

1. Матрица подключенных компонентов инициализируется с размером матрицы изображения.
2. Метка инициализируется и увеличивается для каждого обнаруженного объекта на изображении.
3. Счетчик инициализируется для подсчета количества объектов.
4. Сканирование основной строки запускается для всего изображения.
5. Если обнаружен пиксель объекта, то следующие шаги повторяются, пока (Index! = 0)
   1. Установите соответствующий пиксель на 0 в изображении.
   2. Вектор (индекс) обновляется со всеми соседними пикселями текущих установленных пикселей.
   3. Уникальные пиксели сохраняются, а повторяющиеся пиксели удаляются.
   4. Установите пиксели, обозначенные индексом, для отметки в матрице подключенного компонента.
   5. Увеличить маркер для другого объекта на изображении. 6. Поместите маркер для другого объекта на изображении.

Answer 1

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

• сканирование изображения строка за строкой;

• когда вы встретите пиксель 1, установите новую метку и выполните операцию заливки, заменив 1 новой меткой.

Заполнение потока может быть реализовано очень просто:

• установить начальный пиксель на новую метку;

• рекурсивно заполнить восемь соседей, если у них есть 1.

https://en.wikipedia.org/wiki/Flood_fill

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

def FloodFill(X, Y, Label):
    I[X,Y]= Label
    for all 8-way neighbors (X'=X±1, Y'=Y±1, inside image):
        if I[X',Y'] == 1:
            FloodFill(X', Y', Label)

def CCL(Image I):
    Label= 1
    for Y in range(I.Height):
        for X in range(I.Width):
            if I[X, Y] == 1:
                Label+= 1
                FloodFill(X, Y, Label)

Поэтому я бы порекомендовал версию scanline, которая немного сложнее.

https://en.wikipedia.org/wiki/Flood_fill#Scanline_fill