Flood fill algorithm - bug in my implementation

Question

I am trying to learn how to implement flood fill algorithm in Python (based on queue). Based on Rosetta page I prepared my version. Unfortunately, I have spent a lot of time and I am not able to find where I have a bug. Could you help me?

I modified original example from 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()

My implementation, 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

In the DFS loop, you incorrectly use start_point. You should color and expand on the popped point like:

    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))