Visual Cell Detection With Flood-Fill
A practical application of the flood-fill algorithm
Here’s the problem: you have a microscope slide (like the one below) containing hundreds of cells. You also have sets of related data, like Oxygen concentration at each location in the slide.
In order to meaningfully process this related data in the context of the cells in the slide, you need to know the location of each cell in the slide, so that it can be mapped to the corresponding Oxygen concentration at its location.
Manual Approach
You could go ahead and visually mark the locations of each cell in the slide by hand. Then you could map each identified cell location to its location in the corresponding dataset and collect the Oxygen concentrations that way.
This has two immediate drawbacks, however:
- It takes a lot of time to mark the locations of 200 cells, and having to do this for hundreds of slides is unreasonable.
- It isn’t very precise. A person would approximate the cell’s location to one point when in reality each cell spans over a varyingly shaped and sized portion of the cell. This is problematic if you wanted to study the relationship between a cell’s location and another variable like Oxygen concentration because the cell’s location wouldn’t be precise enough.
Better: An Automated Approach
The solution to these two drawbacks of manually labeling cells is to automate the process. This could be done by applying fancier machine vision techniques, but I chose to instead use a simpler approach that centers around the flood-fill algorithm. I chose this approach because I hold the belief that if a simpler approach works as well as you need it to, you should use it.
To be very clear, let’s look at what we want to achieve at the end of the day:
The Goal of the Algorithm
Take as input: an image file containing several cells. Produce as output: a list of the cells in the image, each represented by a list of the pixel locations it occupies
Solving an Easier Problem
A real slide of cells poses many problems:
- There is noise, meaning things other than cells appear in the “background” of the image
- The cells are unusually shaped and sometimes touching each other
To solve the core of the problem without worrying about these issues, let's make a “perfect world” slide of cells:
This will now be much easier to work with than the example that was first shown because we won’t have to worry about filtering/pre-processing the image. To essentially group together the colored pixels, we can use an algorithm called flood-fill.
The Flood Fill Algorithm
A nice way to visualize flood-fill is to think of the paint bucket tool in a drawing application. It basically pours the paint on a particular region of color, stopping at the border where the color changes. As you can imagine, we could use this technique to solve our problem: pour the color black at each colored pixel; all of the pixels we end up coloring are part of that cell.
Flood-fill works by checking a starting pixel and painting that pixel the new color if necessary. It then calls flood-fill again recursively on the four surrounding pixels. A basic implementation of flood-fill, which takes all non-black pixels in the starting region and makes them black (like coloring the red cells black in the image above). In this example, image is a matrix (2-D list) of floats representing pixel values in a grayscale image.
def flood_fill(x, y, width, height):
"""
x: starting pixel row index
y: starting pixel column index
width: the width of the image
height: the height of the image
Blackens all non-black pixels in the same region as the starting
pixel
"""
# Base Case: the cell is already black
if image[x][y] == 0:
return
# Recursive Case: the cell is not black
image[x][y] = 0
# Invoke flood fill on all surrounding cells:
if x > 0:
flood_fill(x - 1, y)
if x + 1 < width:
flood_fill(x + 1, y)
if y > 0:
flood_fill(x, y - 1)
if y + 1 < slide.height:
flood_fill(x, y + 1)In our case, we want to expand on flood-fill a little, allowing us to keep track of which cells we colored, as that is ultimately our goal: to know which pixels are part of a particular cell in the image. That can be done in several ways, but I chose to do it by defining an inner function to do flood fill and having it append the pixel location to a list every time it colors a pixel.
def explore_cell(self, slide, base_x, base_y):
'''
Finds all pixels that are part of the cell that contains
the base pixel
:param slide: the slide to search
:param base_x: the X coordinate of any pixel contained in the cell
:param base_y: the Y coordinate of any pixel contained in the cell
:returns pixels: the pixels that cover the cell containing the
base pixel
'''
cell_pixels = [] def flood_fill(x, y):
if slide[x][y] == 0:
return
cell_pixels.append((x, y))
slide[x][y] = 0
# Invoke flood fill on all surrounding cells:
if x > 0:
flood_fill(x - 1, y)
if x + 1 < len(slide[0]):
flood_fill(x + 1, y)
if y > 0:
flood_fill(x, y - 1)
if y + 1 < len(slide):
flood_fill(x, y + 1) flood_fill(base_x, base_y)return cell_pixels
Now we can just run explore_cell on each pixel in the image, and by the end we will have a complete set of all of the cells in the slide.
Returning to the Original Problem
The above flood-fill solution works fine for simplified examples like the one I created. However, in the real world, we have to deal with noise and oddly shaped cells. If we run our above code on a real slide, for example, it will hit the recursion depth limit and crash because it keeps on coloring the entire image, thinking that noise is part of the cell. In order to get this solution to work, we are going to have to do some cleaning up.
Filtering the Image
I arrived at the following filtering process through some trial and error, combined with common practices for dealing with noise like this.
Converting to Grayscale
- To start the filtering process, we convert the image to grayscale to simplify things and avoid having to worry about three color channels. We can just average the three colors to achieve this.
Applying a Noise Gate
Because there is still noise in the image, we can next apply a simple noise gate. To do this, we basically consider each pixel, and if it is below a certain threshold value (such as 0.1), when we set it to zero. Otherwise, we set it to 1. This helps to get rid of a lot of the low amplitude background noise in the image. Also, it simplifies the image greatly by making every pixel basically a boolean, so we don’t have to consider the difference between a light gray and a dark gray cell.
Cell Size Filter
There are still a bunch of individual pixels or groups of a few pixels throughout the image, which are the result of high-intensity noise that wasn’t removed by the simple noise gate. To fix this, we can filter out based on cell size, and basically say that any cell smaller than 5 pixels or so is not actually a cell. The result of this is as follows:
At this point, the image is clean enough that our original approach can process it.
Results
I had several example slides that were hand-counted, and the results were pretty positive. It detected around 98% of the cells, and visually you can see that it closely identifies the correct shape of the cells, which is good for a detailed pixel-level analysis of data collected about the cells.
Conclusion
In order to solve this problem of detecting cells in a noisy image of a slide, I first made it into an easier problem that I could solve. I used an existing algorithm (flood-fill) to solve that problem, and took steps (filtering) to make that solution applicable to the real-world problem I had at hand.
All-in-all, it was a nice problem to solve and I am glad I was approached with it. I hope sharing it here is inspiring in some way. You can check out the repository here.
Cheers!
