Flood Fill

easyPROImage SegmentationComputer Vision 2

Implement a flood fill algorithm on a given 2D grid, starting from a specified position $(sr, sc)$ , to replace all connected pixels with the same original value with a new value. The connection between pixels is defined by 4-connectivity, where two pixels are considered connected if they are adjacent horizontally or vertically.

The flood fill operation is a fundamental concept in image segmentation, which is crucial in computer vision for separating objects or regions of interest from the rest of the image. This process can be viewed as a graph traversal problem, where each pixel represents a node, and the connections between them are edges. The goal is to traverse the graph, starting from a given node, and update all connected nodes that share the same original value.

Here are the steps to achieve this:

Identify the starting position $(sr, sc)$ and the new value.
Determine the original value of the starting pixel.
Check if the starting pixel already has the new value.
Traverse the grid, updating all connected pixels with the same original value.

\text{Connected pixels: } (r, c) \text{ and } (r', c') \text{ if } |r-r'| + |c-c'| = 1

This technique is widely used in image editing software.

Example

Input

grid = [[1, 1, 1], [1, 1, 0], [1, 0, 1]]
sr = 1, sc = 1, new_val = 2

Output

[[2, 2, 2], [2, 2, 0], [2, 0, 1]]

Reasoning

Inputs: grid is a $3 \times 3$ image of integer pixel values, $(sr, sc) = (1, 1)$ is the seed pixel (0-indexed row and column), and new_val $= 2$ is the paint colour.
The seed holds the value $1$ , so the region to repaint is every $1$ reachable from $(1, 1)$ by steps with $|r-r'| + |c-c'| = 1$ (up, down, left, right only).
From $(1, 1)$ the direct neighbours $(0, 1)$ , $(1, 0)$ are $1$ ; $(1, 2)$ and $(2, 1)$ are $0$ , so they block. From $(0, 1)$ we reach $(0, 0)$ and $(0, 2)$ , and from $(1, 0)$ we reach $(2, 0)$ . All 6 become $2$ .
Pixel $(2, 2)$ is also $1$ , but its only neighbours $(1, 2)$ and $(2, 1)$ are $0$ . A diagonal touch does not count, so it stays 1.
Output: [[2, 2, 2], [2, 2, 0], [2, 0, 1]], same shape as the input. Notice that a pixel's value alone is not enough: it must be connected to the seed. If new_val already equalled $1$ , nothing would change.

Constraints

grid is a 2D list of integers
(sr, sc) is a valid position in the grid
new_val is an integer
Use 4-connectivity (up, down, left, right)
Return the modified grid

More from Computer Vision 2

1D Bilateral Filterhard Image Sharpening with Unsharp Maskmedium Gaussian Blurmedium Gaussian Kernel Generationeasy 2D Image Convolutioneasy

Flood Fill

Example

Constraints

More from Computer Vision 2

Background Knowledge

Algorithm/Approach

Continue the full explanation

Editor locked