Filtering Connected Components

Google+ Pinterest LinkedIn Tumblr +

In another article we learned how to extract connected components using OpenCV and how to to some common operations. Now I’ll talk about another useful and common task: filtering connected components to extract only those that pass a certain criteria. And to make things more generic, the criteria will be defined by the caller using function pointers.

Revisiting OpenCV

OpenCV is a cool computer vision and image processing library that is widely used and offers many good features. We will use it to extract and filter the connected components from an image.

Revisiting Connected Component extraction

We can extract the connected components of an image using the cvFindContours function as described here. It stores the contours of the connected components in a list of sequences. Each sequence contains the points of a polygon that approximates that contour and we can navigate this list of sequences using the h_next, h_prev, v_next and v_prev pointers.

CvSeq: Sequences in OpenCV

The CvSeq type is a sequence in OpenCV and it is used to store the contours of the connected components. Since we will filter the connected components, so we need a way to delete a contour from the list. The cvSeqRemove function removes elements from a sequence, but it does not remove an entire sequence from our contour list. To remove a sequence from the list we need to mess with the h_next and h_prev pointers. If we want to remove the first element we just need to make the contours pointer point to the second element. To remove an element in the middle of the list we “jump” him from the sequence. The procedure is simple and smart: if we want to remove the  X element we make the h_next pointer of the previous element point to the one after X and the h_prev of the next element point to the element before X. Just like this:

ptr->h_prev->h_next = ptr->h_next; 

if (ptr->h_next != NULL)
ptr->h_next->h_prev = ptr->h_prev;

Of course we need to check if X has someone after him, so we don’t run into some Segmentation Faults removing the last element.

Defining a custom criteria function using function pointers

To make the filtering criteria generic we will use function pointers. The idea is to submit a contour to a criteria function that accepts or rejects a contour. If the contour is rejected then we remove it from our list of contours. In the end only the accepted contours will remain and we return it. You can learn more about function pointers here.
The prototype of the criteria function will be:

int criteria(CvSeq *contour);

Coding the example: filtering and extracting the connected components

Now we will code the function that will do the job. I’ll post the function’s code below here, the complete working code is available at the end of the article.

CvSeq *extract_and_filter_CC(IplImage *img, int (*criteria) (CvSeq *)) 


{

CvSeq *contours, *ptr;

CvMemStorage *mem = cvCreateMemStorage(0);

cvFindContours(img, mem, &contours, sizeof(CvContour), CV_RETR_CCOMP,

CV_CHAIN_APPROX_SIMPLE, cvPoint(0,0));

ptr = contours;

while (ptr != NULL){

if (criteria(ptr) == 0) {

if (ptr == contours) {

contours = ptr->h_next;

ptr = contours;

ptr->h_prev = NULL;

} else {

ptr->h_prev->h_next = ptr->h_next;

if (ptr->h_next != NULL)

ptr->h_next->h_prev = ptr->h_prev;

ptr = ptr->h_next;

}

} else {

ptr = ptr->h_next;

}

 }

return contours;
}

An example of use

In this example I’ll show a simple function that filters components based on their ratio, getting only connected components that are almost square.

int square(CvSeq *contour)


{

CvRect box = cvBoundingBox(contour);

if (box->w / box->h < 0.6 && box->w / box->h > 0.4)

return 1;

return 0;

}


We call the extract_and_filter_CC function like this:

filtered_cc = extract_and_filter_CC(img, square);

Conclusion

This article describes another application of connected components: to filter parts of the image that do not fit in a certain criteria. It also uses function pointers to make the filtering as generic as possible. This technique is very powerful and can be used in conjunction to other techniques to remove noise an image or to extract especial parts of the image.

The complete working code with comments is available here.

Share.

About Author

Leave A Reply