Paint Fill Implementation – Image Editing

Introduction

Most of the image editing software like Microsoft paint, Paint.NET, Adobe Photoshop offer features like paint fill. This post is an attempt to define a simple version of the algorithm which is used to implement paint fill. The problem definition goes like this:

There is a grid with dimensions N*M such that each cell of the grid is colored. The paint fill technique allows a user to choose a color to be filled, say K and a cell C(i,j).

  • If the cell C(i,j) has the same color as K, then do nothing.
  • If the cell C(i,j) has a color L which is different from K then find all the connected cells with color L and fill them with color K.

The Paint Fill Implementation problem

Here is a pictorial representation for the behavior. Imagine the below input grid.

 

Paint Fill Implementation

If I select the cell C and choose the color to be filled as Yellow (Mustard). Then there will be no effect.  If I select the cell C and choose the color to be filled as White. Then all the mustard color cells in the center of the grid will be filled with white.

Here is the output in both the cases:

Paint Fill Implementation

Approaching the problem

The idea behind the problem is pretty simple. You can re-paint all the four adjacent cells around a chosen cell. In this case you cannot re-paint the diagonal cells. First handle the case where the color to be filled matches the color of the cell. Just return back without doing anything.

In rest all cases, check the bounds of the current cell, if the cell is well within the boundary of the grid fill it with the new color. Then recursively fill the four adjacent cell.

Here is the source code for the same

You might notice that we compare the color of the current cell with the original color of the cell C(i,j) for each iteration. The trick is to save the original color before changing the color of the cell C(i,j).

Alternately you can also define an array of moves and iterate over it instead of four lines of recursion

Color is a user defined enum.

Analysis

 

This is essentially a breadth first search in the grid. There is no auxiliary space required, hence it is O(1). For each cell, we test four cells, in the worst case, you will have to fill each of the cell in the grid, so the number of comparisons is four times the number of cells. Hence, it is linear time with respect to the number of cells in the grid.