DFS в пикселе изображения

Question

Я практикую DFS с этим изображением, и я хочу сосчитать белое пятно на изображении

, но DFS заканчивается так:

def dfs(img,j,i,width,height):
    print(j,i)
    if j < 0 or i< 0 or j>= height or i>= width or (img[j,i,0] == 0 and img[j,i,1] == 0 and img[j,i,2] == 0):
        cv2.imshow("hi",img)
        cv2.waitKey(0) 
        return 
    img[j,i,0] = 0
    img[j,i,1] = 0
    img[j,i,2] = 0


    dfs(img,j+1,i,width,height)
    dfs(img,j-1,i,width,height)
    dfs(img,j,i+1,width,height)
    dfs(img,j,i-1,width,height)




if __name__ == "__main__":
    img = cv2.imread(r"D:\secret\Problem3\test2-gray.bmp")

    count = 0
    img = cv2.resize(img, (400, 400), interpolation=cv2.INTER_CUBIC)
    og_img = img.copy()
    width,height = img.shape[0],img.shape[1]
    for j in range(height):
        for i in range(width):
            if (img[j,i] >0).all():
                count += 1
                dfs(img,j,i,width,height)
    cv2.imshow("hi",img)
    cv2.waitKey(0)

Я думаю, что что-то не так с конечным утверждением в dfs, но не могу понять, кто-нибудь может дать мне подсказку? спасибо!

Answer 1

Вы достигли предела рекурсии Python. Вы можете попытаться установить его выше с помощью https://docs.python.org/3/library/sys.html#sys .setrecursionlimit , но лучшим вариантом является обработка стека рекурсии самостоятельно, например:

def dfs(img,j,i,width,height):
    todo = [(j,i)]
    while todo:
        j,i = todo.pop()
        if not (0 <= j < height) or not (0 <= i < width) or (img[j,i] == 0).all():
            continue
        img[j,i,0] = 0
        img[j,i,1] = 0
        img[j,i,2] = 0
        sz += 1
        todo += [(j+1,i), (j-1,i), (j,i+1), (j,i-1)]

Answer 2

Мне кажется, проблема в том, что вы повторно посещаете уже обработанные пиксели. Поскольку вы устанавливаете их в «0» (черный), функция dfs возвращается до того, как она посетила все белые пиксели.

Попробуйте использовать set() или что-то еще для отслеживания уже посещенных пикселей, а затем проверьте каждый пиксель, если он уже есть в наборе.

Пример для вашего l oop:

  for j in range(height):
        for i in range(width):
            visited_pixels = set()
            if (img[j,i] >0).all():
                count += 1
                visited_pixels.add((j, i))
                dfs(img,j,i,width,height, visited_pixels)

Затем в функции:

def dfs(img,j,i,width,height, visited_pixels):
    if (j, i) in visited_pixels:
        return
    if (your_if_statement)
    ...
    visited_pixels.add(j, i)