BFS를 사용하여 연결된 컴포넌트 라벨링

Question

BFS 알고리즘을 사용하여 연결된 컴포넌트 라벨링 알고리즘을 해결 중입니다. 원래 이미지 인 im은 아웃 이미지로 레이블됩니다.

얼룩이 작을 때이 코드는 작동합니다. 그러나 큰 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]); 
           } 
         } 
       } 
     }   
} 

Answer 2

파이썬 솔루션으로, 나는 종종이 아닌 재귀 솔루션을 사용 지금까지 :

이

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 

나는 과거의 프로젝트를 위해 쓴이 버전은 2 소요를 D 파이썬 배열을 입력으로 사용하고 True 또는 One 인 이웃 픽셀을 탐색합니다. 컨텍스트에서 사용 된 것을 보려면 this으로 썼습니다.