洪水填充算法 - 我的实现中的错误

Question

我正在尝试学习如何在 Python（基于队列）中实现洪水填充算法。基于 Rosetta 页面我准备了我的版本。不幸的是，我花了很多时间，却无法找到我有错误的地方。你能帮帮我吗？

我修改了 scikit-image 中的原始示例 page:

import numpy as np
import matplotlib.pyplot as plt
from skimage import data, filters
#from skimage.segmentation import flood, flood_fill
from flood_algorithm import flood_fill # <---------------- my file

checkers = data.checkerboard()

# Fill a square near the middle with value 127, starting at index (76, 76)

#filled_checkers = flood_fill(checkers, (76, 76), 127) # <-------   skimage version
filled_checkers = flood_fill(checkers, (76, 76), 255, 127) # <-----  my version

fig, ax = plt.subplots(ncols=2, figsize=(10, 5))

ax[0].imshow(checkers, cmap=plt.cm.gray)
ax[0].set_title('Original')
ax[0].axis('off')

ax[1].imshow(filled_checkers, cmap=plt.cm.gray)
ax[1].plot(76, 76, 'wo')  # seed point
ax[1].set_title('After flood fill')
ax[1].axis('off')

plt.show()

我的实现，flood_algorithm.py：

from collections import deque

def flood_fill(input_array, start_point, source_colour, target_colour):
    if not is_inside_image(start_point, input_array.shape):
        return input_array

    if input_array[start_point[0]][start_point[1]] == source_colour:
        # create a queue and enqueue starting pixel
        q = deque()
        q.append(start_point)
    
        while q:
            point = q.popleft()
            
            if is_inside_image(point, input_array.shape):
                if input_array[start_point[0]][start_point[1]] == source_colour:
                    input_array[start_point[0]][start_point[1]] = target_colour
                    
                    q.append((start_point[0] + 1, start_point[1]))
                    q.append((start_point[0] - 1, start_point[1]))
                    q.append((start_point[0]    , start_point[1] + 1))
                    q.append((start_point[0]    , start_point[1] - 1))
    
    return input_array

def is_inside_image(point, input_array_shape):
    return (point[0] > 0) and (point[0] < input_array_shape[0]) and \
           (point[1] > 0) and (point[1] < input_array_shape[1])

Answer 1

在 DFS 循环中，您错误地使用了 start_point。您应该在弹出的 point 上着色并展开，例如：

    while q:
        point = q.popleft()
        
        if is_inside_image(point, input_array.shape):
            if input_array[point[0]][point[1]] == source_colour:
                input_array[point[0]][point[1]] = target_colour
                
                q.append((point[0] + 1, point[1]))
                q.append((point[0] - 1, point[1]))
                q.append((point[0]    , point[1] + 1))
                q.append((point[0]    , point[1] - 1))

洪水填充算法 - 我的实现中的错误

Flood fill algorithm - bug in my implementation

python

algorithm

image-processing

python-3.x

scikit-image