After understanding how to access pixels and move them around, let’s dive deeper into how we can apply that knowledge towards a technique called labeling.
Labeling is a general term that describes a technique where one would label each graphic element in an image individually in order to refer back to them later during processing. This technique has several applications, including, but not limited to, facial recognition, feature detection, object counting, and so on.
In this post, we will apply labeling to count objects in an image. We will start with a simple picture that contains white elements (bubbles) over a black background and our goal is to figure out how many of these bubbles there are in the picture.
Assumptions and Goals
We will assume the background is completely black (shade 0) and the bubbles are completely white (shade 255). Our goal is to count the total number of bubbles, then count how many are hollow and how many are solid. To make this a bit harder, we will also assume that bubbles can have more than one hole each and will NOT include bubbles that are touching the edge of the picture.
The Algorithm
So let’s do this. First, we need to create the variables that will store the picture we are processing, the height and width of said picture, and the number of bubbles.
#include <iostream>
#include <opencv2/opencv.hpp>
using namespace std;
using namespace cv;
int labeling()
{
Mat bubbles;
int width;
int height;
int allbubbles = 0;
int solidbubbles = 0;
int hollowbubbles = 0;
...
}Since we are considering that each bubble can have more than one hole, we need to create a set structure to make this happen – I will explain this further down the road – then we read the bubbly image from the disk.
...
set<uchar> shades_used;
bubbles = imread("Images/bubbles-2-holes.png", IMREAD_GRAYSCALE);
if (!bubbles.data)
{
cout << "[ERROR] Could not open file" << endl;
return -1;
}
width = bubbles.cols;
height = bubbles.rows;
// Display starting image
imshow("Starting image", bubbles);
....The result so far is a window displaying the image before any processing:
Step 1: Removing edge bubbles
Our first assumption is that we will ignore bubbles that touch the edge of the picture. Just by looking, we can count more than 10 bubbles that need to be gone. In order to achieve that, we will apply a process called flood fill.
When you play with the paint bucket tool in Microsoft Paint, for example, what that does, in fact, is execute the flood fill algorithm. It basically applies the color you define to the pixel you clicked on, plus any neighboring pixel that contains the same color reference as the current one and so on recursively.
Now that we know what the flood fill is, what we will do to remove the edge bubbles is simply iterate over the first and last columns and the first and last rows of the image and look for white pixels. If one is found, we apply a black flood fill to that pixel so that it becomes the background and that edge bubble is finally gone.
So, let’s keep building our algorithm.
...
for (int i = 0; i < height; i++)
{
int j = 0;
if (bubbles.at<uchar>(Point(j, i)) == 255)
floodFill(bubbles, Point(j, i), 0);
}
for (int i = 0; i < height; i++)
{
int j = width - 1;
if (bubbles.at<uchar>(Point(j, i)) == 255)
floodFill(bubbles, Point(j, i), 0);
}
for (int j = 0; j < width; j++)
{
int i = 0;
if (bubbles.at<uchar>(Point(j, i)) == 255)
floodFill(bubbles, Point(j, i), 0);
}
for (int j = 0; j < width; j++)
{
int i = height - 1;
if (bubbles.at<uchar>(Point(j, i)) == 255)
floodFill(bubbles, Point(j, i), 0);
}
imshow("Step 1: Remove edge bubbles", bubbles);
...So far, this is what our processed image looks like:
Step 2: Counting all the bubbles
In order to count our bubbles, we iterate over the whole image and look for occurrences of white pixels. For each white pixel that is found, we apply the flood fill to that pixel. Since we are also labeling these bubbles, we want to apply a different shade of gray to each bubble that’s found so they are uniquely identifiable. Keep in mind we are dealing with a grayscale image, so each pixel can only range in color from 0 to 255. Since 0 is the background, we start labeling the bubbles with 1 and so on.
...
for (int i = 0; i < height; i++)
{
for (int j = 0; j < width; j++)
{
if (bubbles.at<uchar>(i, j) == 255)
{
allbubbles++;
floodFill(bubbles, Point(j, i), allbubbles);
}
}
}
imshow("Step 2: Count all bubbles", bubbles);
...The floodFill method takes as parameters, respectively, the source image, the point where to apply the flood fill, and the shade to paint with. After this is done, we are left with the amount of bubbles in the allbubbles variable and a labeled image.
You can barely tell the difference from the bubbles to the background since their colors are so close to black (0). The good thing is that your computer can 🙂
Step 3: Painting the background white
Now we need to figure out how many bubbles are hollow – with two or more holes – and how many are solid. In order to do that, we’ll paint the background white (255), leaving us with the bubbles, each one having their own unique shades and the remaining black (0) background inside them.
...
floodFill(bubbles, Point(0, 0), 255);
imshow("Step 3: Paint background white", bubbles);
...
Step 4: Searching for hollow bubbles
Now, since the black (0) shade is only found when hollow bubbles occur, we know what to look for. However, it’s not that simple. Since we are also considering that bubbles can have more than one hole each, we need to keep track of which bubbles have been counted and which ones have not.
That is what we are going to use our set for. Since each bubble contains a unique shade, we store that shade in our set whenever we count a bubble, and, for each black pixel found, we check which shade the pixel before that one has – a pixel that belongs to the bubble – and see whether the set already has that shade. If it doesn’t, we count the bubble, but if it does, we don’t.
...
for (int i = 0; i < height; i++)
{
for (int j = 0; j < width; j++)
{
if (bubbles.at<uchar>(i, j) == 0)
{
// Found a hole, which bubble does that belong to?
auto shade = bubbles.at<uchar>(i, j - 1);
auto pos = shades_used.find(shade);
if (pos == shades_used.end())
{
// Shade not found, add it to set and increment hollow bubbles count.
hollowbubbles++;
shades_used.insert(shade);
}
floodFill(bubbles, Point(j, i), 255);
}
}
}
imshow("Step 4: Paint internals white and count hollow", bubbles);
...At this point, whenever we find a black pixel, we flood fill that with white so that it matches the background. This is the result of this process:
Final step: “the count is out!”
At this point in our algorithm, our variables allbubbles and hollowbubbles contain the counts of all bubbles and hollow bubbles respectively. Notice we didn’t count solid bubbles at all, which is fine since solid bubbles equal all bubbles minus hollow ones.
...
solidbubbles = allbubbles - hollowbubbles;
cout << endl;
cout << "The image contains" << endl;
cout << allbubbles << " total bubbles, with:" << endl;
cout << "\t" << solidbubbles << " solid bubbles" << endl;
cout << "\t" << hollowbubbles << " hollow bubbles" << endl;
waitKey();
return 0;
...The output of our program is:
The image contains
21 total bubbles, with:
14 solid bubbles
7 hollow bubblesKnown Limitations
Our algorithm isn’t perfect. In fact, since we are labeling our bubbles with shades of gray, as soon as we have more than 254 bubbles, we are going to have a problem. How can we solve this?
Colorful labeling
As an example, we’ll use an image with more than 300 bubbles.
Since we can’t label these with shades of gray, what if we use actual RGB colors? We can then label them from (1, 0, 0) to (255, 255, 255), leaving us with 16,711,680 possible unique labels. In this example, we won’t go as far as counting hollows and solids, but the principle is the same (just make sure to keep your label range up to (255, 255, 254) in that case since the background will become white eventually).
In this case, we need to load our image with color, not grayscale:
...
bubbles = imread("Images/bubbles-colorful.png", IMREAD_COLOR);
...The algorithm to count and label the bubbles will need to iterate the image entirely and, for each pixel, check whether it’s white (255, 255, 255). If it is, we flood fill that with its own color in the range, increment the number of bubbles and increment the color to the next occurrence.
...
uchar red = 1;
uchar green = 0;
uchar blue = 0;
for (int i = 0; i < height; i++)
{
for (int j = 0; j < width; j++)
{
auto color = bubbles.at<Vec3b>(Point(j, i));
if (color[0] == 255 && color[1] == 255 && color[2] == 255)
{
floodFill(bubbles, Point(j, i), Vec3b(blue, green, red));
allbubbles++;
// Increment color
red = (red + 1 > 255) ? 255 : red + 1;
green = (red == 255) ? green + 1 : green;
blue = (green == 255) ? blue + 1 : blue;
blue = (blue == 255) ? 255 : blue; // We have reached the color limits
}
}
}
imshow("Step 1: Label bubbles with colors", bubbles);
cout << endl;
cout << "The image contains " << allbubbles << " bubbles";
waitKey();
return 0;
...Another thing to keep in mind is that our Vec3b is BGR, not RGB, which explains why our flood fill shade parameter is Vec3b(blue, green, red).
The result of this process is:
And the return of our program is:
The image contains 318 bubblesFinal thoughts
That’s it for this one, folks. I hope this has been informative and stay tuned for more OpenCV tips and tutorials. Make sure to check the previous posts of this ongoing series:
Live long and prosper.