python - 使用 BFS 的连接组件标记

Question

我正在使用 BFS 算法解决连通域标记算法。原始图像im将被标记为out图像。

当 blob 较小时，此代码有效。但是，当我将起点更改为具有大 blob 时，代码要么达到最大递归深度，要么出现段错误。如何避免这些问题？

import cv2
import numpy as np
from collections import deque
import sys
import copy

sys.setrecursionlimit(10000000)

def bfs(queue, im, out, label):
    if len(queue) > 0:
        pixel = queue.pop()
        print pixel
        out[pixel] = label

        M, N = im.shape
        for n in neighbors(pixel, M, N):
            if out[n] == 0 and im[n] == im[pixel]:
                queue.append(n)
        out = bfs(queue, im, out, label)
    return out

def neighbors(pixel, M, N):
    if pixel[0] == M - 1 and pixel[1] == N - 1:
        return [(M-2, N-1), (M-1, N-2)]
    elif pixel == (0,0):
        return [(0,1),(1,0)]
    elif pixel == (M - 1, 0):
        return [(M-1, 1), (M-2, 0)]
    elif pixel == (0, N - 1):
        return [(1, N-1), (0, N-2)]
    elif pixel[0] == 0:
        return [(1,pixel[1]), (0, pixel[1]-1), (0 ,pixel[1] + 1)]
    elif pixel[1] == 0:
        return [(pixel[0], 1), (pixel[0]-1, 0), (pixel[0] + 1, 0)]
    elif pixel[0] == M - 1:
        return [(pixel[0], pixel[1] + 1), (pixel[0] - 1, pixel[1]), (pixel[0], pixel[1] - 1)]
    elif pixel[1] == N - 1:
        return [(pixel[0] + 1, pixel[1]), (pixel[0], pixel[1] - 1), (pixel[0] - 1, pixel[1])]
    else: 
        return [(pixel[0] + 1, pixel[1]), (pixel[0], pixel[1] + 1),\
                (pixel[0] - 1, pixel[1]), (pixel[0], pixel[1] - 1)]


im = cv2.imread('33039.png', cv2.IMREAD_GRAYSCALE)
out = np.zeros(im.shape)

queue = deque()
queue.append((10,10))
out = bfs(queue, im, out, 1)

Answer 1

BFS 可以很容易地以迭代的方式实现。这是 CPP 中的示例:

void
bfs(const vector< vector<int> > &g)
{
        // visit self, then neighbors, store neighbors using stack.
        vector<bool> visited(g.size(), false);
        vector<int> s;
        Queue Q;
        Q.enqueue(6);
        while (Q.size() > 0)
        {
                int t = Q.dequeue();
                if (!visited[t])
                {
                        cout << "visit node: " << t << endl;
                        visited[t] = true;
                        for (int i = 0; i < g[t].size(); ++i)
                        {
                                if (!visited[g[t][i]])
                                {
                                        Q.enqueue(g[t][i]);
                                }
                        }
                }
        }        
}