Python中的泛洪填充算法

Question

Python中的泛洪填充算法

5

我是一名有用的助手，以下是您需要翻译的内容：

我对泛洪填充算法完全不了解。我从维基百科上查看了相关内容(http://en.wikipedia.org/wiki/Flood_fill)，但并没有更加明晰。我正在尝试将其应用于以下情况。我有一个矩阵：

matrix = [["a", "a", "b", "a", "a", "b"],
          ["a", "b", "b", "a", "b", "b"],
          ["b", "a", "b", "a", "a", "b"],
          ["b", "a", "b", "a", "b", "b"],
          ["a", "a", "b", "a", "a", "a"],
          ["a", "b", "b", "a", "a", "b"]]

然后我让用户从矩阵中选择一个点。如果在给定的点上是"b"，则不执行任何操作。否则，如果在给定的点上是"a"，我想用泛洪填充算法将该给定点和所有与之相邻或连接的点中的"a"都更改为"c"。

例如，假设用户决定使用matrix[0][0]。那么新的矩阵将是：

matrix = [["c", "c", "b", "a", "a", "b"],
          ["c", "b", "b", "a", "b", "b"],
          ["b", "a", "b", "a", "a", "b"],
          ["b", "a", "b", "a", "b", "b"],
          ["a", "a", "b", "a", "a", "a"],
          ["a", "b", "b", "a", "a", "b"]]

接着上面的例子，假设用户选择了新的点，matrix[3][1]。那么我们会得到以下结果：

matrix = [["c", "c", "b", "a", "a", "b"],
          ["c", "b", "b", "a", "b", "b"],
          ["b", "c", "b", "a", "a", "b"],
          ["b", "c", "b", "a", "b", "b"],
          ["c", "c", "b", "a", "a", "a"],
          ["c", "b", "b", "a", "a", "b"]]

我正在尝试构建一个函数floodfill(matrix, x, y)，到目前为止我得出了以下结果：

def floodfill(matrix, x, y):
    if matrix[y][x] == "b":
        return matrix
    elif matrix[y][x] == ".":
        stack = []

你有什么方法可以引导我继续吗？在这里SO上尝试查看泛洪填充示例，但它们似乎不适合我的情况。至少我无法将这些示例应用到我的代码中。泛洪填充在这里似乎并不是那么受欢迎的主题...但是，再次帮助将不胜感激！

- Waldema

不多。我已经更新了我的第一篇帖子。现在我知道我必须构建一个堆栈。 - Waldema

对于实际的Python实现 - 泛滥填充NumPy数组。 - Divakar

3个回答

3

在Python的图像处理库中有几种洪水填充算法的实现。我知道其中两种：skimage.segmentation.flood和OpenCV的floodFill。前一种使用与Amit回答中相似的算法在Python中实现。后者使用类似的概念性算法在C++中实现，但没有递归，使其效率更高（对于大图像约为25倍）。

要使用OpenCV的floodFill，您需要将矩阵转换为整数的np.array，可以按以下方式完成：

import numpy as np
import cv2

matrix_np = np.asarray(matrix)
numeric_matrix = np.where(matrix_np=="a", 255, 0).astype(np.uint8)
mask = np.zeros(np.asarray(numeric_matrix.shape)+2, dtype=np.uint8)
start_pt = (y,x)
if matrix_np[start_pt]:
  cv2.floodFill(numeric_matrix, mask, start_pt, 255, flags=4)
mask = mask[1:-1, 1:-1]
matrix_np[mask==1] = "c"
matrix = matrix_np.tolist()

使用您上面提供的示例矩阵和x，y =（0,0），这将设置matrix为

[['c', 'c', 'b', 'a', 'a', 'b'],
 ['c', 'b', 'b', 'a', 'b', 'b'],
 ['b', 'a', 'b', 'a', 'a', 'b'],
 ['b', 'a', 'b', 'a', 'b', 'b'],
 ['a', 'a', 'b', 'a', 'a', 'a'],
 ['a', 'b', 'b', 'a', 'a', 'b']]

- Zvika

0

为了更深入地理解，您可以考虑查看我的代码（它易于理解且最易懂）

希望您能理解 :)

from pprint import pprint

print("Input Matrix :")

matrix = [["a", "a", "b", "a", "a", "b"],
          ["a", "b", "b", "a", "b", "b"],
          ["b", "a", "b", "a", "a", "b"],
          ["b", "a", "b", "a", "b", "b"],
          ["a", "a", "b", "a", "a", "a"],
          ["a", "b", "b", "a", "a", "b"]]

pprint(matrix)

# USER INPUT 
row = 3
col = 1

given_item = matrix[row][col]

# MASK PATTERN 
mask = "c"


print("\n")
print("Changing only inner matrix items and skiping items where index is Negative := ")
if (row + col+1) >= 0:
  right = matrix[row][col+1]
  print("right")
else:
  right = "NA"


if (row + col-1) >= 0:
  left = matrix[row][col-1]
  print("left")
else:
  left = "NA"

if (row-1 + col) >= 0:
  top = matrix[row-1][col]
  print("top")
else:
  top = "NA"

if (row+1 + col) >= 0:
  bottom = matrix[row+1][col]
  print("bottom")
else:
  bottom = "NA"


pattern = f"""
            {top}
          {left} {given_item} {right}
            {bottom}
          """

print(pattern)

if right == given_item:
  print(f"masking right {mask}")
  matrix[row][col+1] = mask

if left == given_item:
   print(f"masking left {mask}")
   matrix[row][col-1] = mask

if top == given_item:
   print(f"masking top {top}")
   matrix[row-1][col] = mask

if bottom == given_item:
   print(f"masking bottom {bottom}")
   matrix[row+1][col] = mask

matrix[row][col] = mask

del right
del left
del top
del bottom 

print("Output Matrix :")
pprint(matrix)

输出：行：3，列：1

Input Matrix :
[['a', 'a', 'b', 'a', 'a', 'b'],
 ['a', 'b', 'b', 'a', 'b', 'b'],
 ['b', 'a', 'b', 'a', 'a', 'b'],
 ['b', 'a', 'b', 'a', 'b', 'b'],
 ['a', 'a', 'b', 'a', 'a', 'a'],
 ['a', 'b', 'b', 'a', 'a', 'b']]


Changing only inner matrix items and skiping items where index is Negative := 
right
left
top
bottom

            a
          b a b
            a
          
masking top a
masking bottom a
Output Matrix :
[['a', 'a', 'b', 'a', 'a', 'b'],
 ['a', 'b', 'b', 'a', 'b', 'b'],
 ['b', 'c', 'b', 'a', 'a', 'b'],
 ['b', 'c', 'b', 'a', 'b', 'b'],
 ['a', 'c', 'b', 'a', 'a', 'a'],
 ['a', 'b', 'b', 'a', 'a', 'b']]

输出 := 行 :0 , 列 :0

Input Matrix :
[['a', 'a', 'b', 'a', 'a', 'b'],
 ['a', 'b', 'b', 'a', 'b', 'b'],
 ['b', 'a', 'b', 'a', 'a', 'b'],
 ['b', 'a', 'b', 'a', 'b', 'b'],
 ['a', 'a', 'b', 'a', 'a', 'a'],
 ['a', 'b', 'b', 'a', 'a', 'b']]


Changing only inner matrix items and skiping items where index is Negative := 
right
bottom

            NA
          NA a a
            a
          
masking right c
masking bottom a
Output Matrix :
[['c', 'c', 'b', 'a', 'a', 'b'],
 ['c', 'b', 'b', 'a', 'b', 'b'],
 ['b', 'a', 'b', 'a', 'a', 'b'],
 ['b', 'a', 'b', 'a', 'b', 'b'],
 ['a', 'a', 'b', 'a', 'a', 'a'],
 ['a', 'b', 'b', 'a', 'a', 'b']]

- Vinay Chaudhari

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- amit · Accepted Answer

洪水填充的思路如下：

检查该点是否符合条件。
如果符合条件，则将其更改为 "c"（在您的情况下）- 并调用所有周围单元格的洪水填充。

类似Python伪代码：

def floodfill(matrix, x, y):
    #"hidden" stop clause - not reinvoking for "c" or "b", only for "a".
    if matrix[x][y] == "a":  
        matrix[x][y] = "c" 
        #recursively invoke flood fill on all surrounding cells:
        if x > 0:
            floodfill(matrix,x-1,y)
        if x < len(matrix[y]) - 1:
            floodfill(matrix,x+1,y)
        if y > 0:
            floodfill(matrix,x,y-1)
        if y < len(matrix) - 1:
            floodfill(matrix,x,y+1)