图像像素中的 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

我认为问题在于您重新访问了已经处理过的像素。由于您将它们设置为“0”（黑色），因此 dfs 函数 returns 在访问所有白色像素之前。

尝试使用 set() 或其他东西来跟踪已经访问过的像素，然后检查每个像素是否已经在集合中。

循环示例：

  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)

Answer 2

您达到了 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)]

图像像素中的 DFS

Dfs in image pixel

python

algorithm

graph-algorithm