Connected componenet labeling using BFS

Question

I am solving Connected component labeling algorithm using BFS algorithm. The original image im will be labeled into out image.

When the blob is small this code works. However when I change the starting point to have a large blob, the code either reach maximum depth of recursion or has segmentation fault. How to avoid these problems?

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 could be easily implemented in iterative way. Here is a sample in 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]);
                                }
                        }
                }
        }        
}

Answer 2

As far as a python solution, I often use this non-recursive solution:

def bfs(graph,start):
    # Breadth-first search to find pixels connected
    # graph is array with some pixels true and others false
    # start is x, y
    if not graph[start[0]][start[1]]:
        return
    visited = []
    w, h = len(graph)-1, len(graph[0])-1
    queue = [start]
    while queue:
        x, y = queue.pop(0)
        neighbors = []
        if x<w:
            neighbors.append((x+1,y))
        if x>0:
            neighbors.append((x-1,y))
        if y<h:
            neighbors.append((x,y+1))
        if y>0:
            neighbors.append((x,y-1))   
        for n in neighbors:
            if n not in visited and graph[n[0]][n[1]]:
                visited.append(n)
                queue.append(n)
    return visited

This version which I wrote for a past project takes a 2-d python array as input, and explores neighboring pixels that are True, or One. To see it used in context, I wrote it for this.