0

As the title says I am trying to find all connected components in an image using recursive dfs.

I based the principle algorithm on the pseudo over here https://www.programiz.com/dsa/graph-dfs

What I get is a recursion depth exceedet error.

Usually I would troubleshoot this by checking the base case for the specific recursion, but I cant seem to find the issue.

Since every pixel is either zero or will be marked as visited at some point in time, I feel the recursion should terminate at some point.

Are there other ways for troubleshooting such recursion errors?

import cv2
import numpy as np


class Image:
    def __init__(self, path):
        self.img = cv2.imread(path, cv2.IMREAD_GRAYSCALE)
        self.n, self.m = self.img.shape
        self.visited = {(i, j): False for i in range(self.n)
                        for j in range(self.m)}
        self.components = []

    def threshold(self):
        self.img[self.img >= 200] = 255
        self.img[self.img < 200] = 0

    def neighbours(self, px):
        (i, j) = px
        corners = [(i+x, j+y) for x in range(-1, 2) for y in range(-1, 2)
                   if (i+x, j+y) != (i, j)
                   and (0 <= i+x < self.n)
                   and (0 <= j+y < self.m)]
        return corners

    def dfs(self):
        self.threshold()
        component = 0
        for i in range(self.n):
            for j in range(self.m):
                if not self.visited.get((i, j)) and self.img[i][j] == 255:
                    self.components.append([(i, j)])
                    self.explore((i, j), component)
                    component += 1

    def explore(self, px, component):
        self.visited[px] = True
        self.components[component].append(px)
        for neigh in self.neighbours(px):
            if not self.visited.get(neigh) and self.img[neigh[0]][neigh[1]] == 255:
                self.explore(neigh, component)


img = Image("dots.png")
img.dfs()

Solved

I had to set the maximum recursion depth

import sys
sys.setrecursionlimit(new_limit)
Community
  • 1
  • 1
  • Perhaps the recursion will terminate at some point, but the image you are using contains too many pixels for this to finish. https://stackoverflow.com/questions/3323001/what-is-the-maximum-recursion-depth-in-python-and-how-to-increase-it If there is a strongly-connected image with lots of pixels, will you not reach the maximum depth at some point? – plum 0 Jul 23 '19 at 14:59
  • At most this code will call explore once on every vertex. I tested this on a 100x300 which would mean at most 30.000 calls. But the image tested consists of two dots maybe 30 pixels in diameter, which would imply even less calls, since all the other non object pixels are zero, and therefore not explored. –  Jul 23 '19 at 15:32
  • Just tried setting a different recursion depth as suggested, works fine now. Thanks. –  Jul 23 '19 at 15:38
  • Glad to help, but perhaps you can optimize your solution to be more efficient to eliminate the need for changing the recursion depth. – plum 0 Jul 23 '19 at 15:44
  • But if you thing about it, the approach is rather efficient, since every pixel is visited once at most. If I were to improve on that, dfs would have to be thrown overboard. Do you have any suggestions? –  Jul 23 '19 at 17:02

0 Answers0