In computer vision and image processing we use many ideas of other areas of computer science to solve our challenges. The problem I’ll talk about is the following: given a monochromatic image I want to obtain the groups of foreground pixels that are isolated by a white region. The name given to these groups is connected component.
In a connected component, given a point inside it, I can walk to any other point inside it using only points that are inside too. This image illustrates what I mean. Each color is a connected component.
Using OpenCV
OpenCV is a famous computer vision library that has TONS of cool features and is widely used. It handles opening various kinds of image and video files and has the code to find the connected components of an image (including the holes in the components).
The first thing to know is how to open an image e how to compile your first program. Compilation instructions for Windows and for Linux. This program opens an image and saves a copy as result.png. We will expand this example to give the above result.
Finding the connected components
To find the connected components we will use the cvFindContours function from OpenCV. With the right parameters this function returns a list with the contours of each connected components and for each component the contour of the holes inside it.
CvMemStorage e CvContour
In OpenCV, whenever we use any type of Dynamic Structure we need to use a CvMemStorage to hold the memory for it. Since cvFindContours returns a list, we must create a CvMemStorage and pass to this function. The code that should be added follows (a complete version of the program will be avaiable in the end of the article.
Declare the variables:
CvMemStorage *mem;
CvSeq *contours, *ptr;
And add this code on the /*ADD CODE HERE*/ line:
cvThreshold(img, img, 150, 255, CV_THRESH_BINARY);
mem = cvCreateMemStorage(0);
cvFindContours(img, mem, &contours;, sizeof(CvContour), CV_RETR_CCOMP,
CV_CHAIN_APPROX_SIMPLE, cvPoint(0,0));
The parameter CV_RETR_CCOMP tells the function that the contours of the connected components should be extracted. CV_CHAIN_APPROX_SIMPLE approximates the contour the a polygon and each contour is represented by the list of vertexes of that polygon. The updated code is here.
Sequences and OpenCV
OpenCV uses the type CvSeq to build sequences of objects. In a CvSeq there’s 4 pointers: h_next, h_prev, v_next e v_prev, that point to other sequences. h_next and h_prev point to sequences on the same level and v_next and v_prev points to sequences on other levels. In our case this is great: on the first level are the outer contours of the connected components and on the second level are the contours of the holes of each component.
Drawing the connected components
We’ll complete the example painting the connect components on a new image. We use the cvDrawContours function. Add the following after the last code. The updated code is here.
for (ptr = contours; ptr != NULL; ptr = ptr->h_next) {
CvScalar color = CV_RGB( rand()&255, rand()&255, rand()&255 );
cvDrawContours(cc_color, ptr, color, CV_RGB(0,0,0), -1, CV_FILLED, 8, cvPoint(0,0));
}
And that it! Now compile the program and run it with this image. You should get the first image as the result 🙂
More tasks with connected components
There are other common tasks that are related to connected components. I’ll list three of them here:
Get the bounding box of a component
We use the function cvBoundingRect. It receives a CvSeq or CvContour and another parameter that asks if the box should be recalculated (1) or if you can take the value from CvContour (0). It returns a CvRect, that contains 4 attributes: x, y, width e height.
Approximate a component by a polygon
We can use cvApproxPoly, that approximates a contour by a polygon. This is done when using CV_CHAIN_APPROX_SIMPLE, but I don’t know if the same method is used.
Test if a point is inside a connected component
We can use cvPointPolygonTest to test if a point is inside some polygon. Since we can approximate a contour by a polygon we can use this function to check if a point belongs to a connected component. We must not forget to check if the point is outside the holes in the component.
For another interesting use of connected components you can check this other article.
Conclusion
This is only an introduction of how to work with connected components. There are various algorithms and techniques that use connected components and this can give you some help to understand and implement them.
