Ask Your Question

Clustring white pixels in binary image

asked 2013-10-01 05:44:25 -0500

updated 2013-10-01 05:47:01 -0500

I have a binary image (black and white pixels), and I'd like to cluster the white pixels into groups (objects), depending on the distance to each other, and retrieve the centroid of each cluster.

this is an example image in which I have to work on: Image (frame on purple)

I'd like to check if a clustering approach would provide the results I am looking for, which means that I'm trying to avoid implementing an algorithm myself before knowing it will be worth it. Does openCV have a method to do what I need?


edit retag flag offensive close merge delete

2 answers

Sort by ยป oldest newest most voted

answered 2013-10-01 10:07:46 -0500

ThomasB gravatar image

updated 2013-10-02 01:41:23 -0500

Uchiyama did a Paper on his so called "Random dot markers" where he searches for black blobs (inverse of your binary-image..) before applying the LLAH to identify the markers. I'm not entirely sure whether I used parts of his algorithm (Source available at ) or was unsatisfied and implemented it on my own, at least my comment in the header says it's somewhere grabbed from there.

However, I found a pretty nice implementation I did a year ago - not really tested but working. The output of it is the following;

Cluster Results clusters_result.png

I hope that works for you as well.

#include <iostream>

#include <opencv2/core/core.hpp>
#include <opencv2/highgui/highgui.hpp>
#include <opencv2/imgproc/imgproc.hpp>

#include "keyExtraction.h"

using namespace cv;
using namespace std;

int main() 

    Mat m = imread("/home/tbergmueller/clusters.png", CV_LOAD_IMAGE_GRAYSCALE);

    Mat debug; // for output only
    cvtColor(m,debug, CV_GRAY2BGR); // convert to BGR to allow red numbers printed to this mat

    bitwise_not(m,m); // Invert because my algorithm is for searching black regions

    CvMat cMat = m;
    avPoint* clusters = NULL; // important: init with NULL, otherwise algo crashes

    int nrOfPoints = avExtractKeys(&cMat,&clusters);

    cout << "Found " << nrOfPoints << " points" << endl;

    for(int i=0; i<nrOfPoints; i++)
        stringstream ss;
        ss << i;

        Point p(clusters[i].center.x, clusters[i].center.y);
        putText(debug,ss.str(),p,CV_FONT_HERSHEY_COMPLEX, 0.5, CV_RGB(255,0,0), 1, CV_AA);

    imshow("Debug", debug);

    return 0;

I uploaded the complete source if you want;

edit flag offensive delete link more


Nice solution! One note: your link seems not working properly.

Guanta gravatar imageGuanta ( 2013-10-01 10:55:40 -0500 )edit

First of all, thank you for taking the time for such an elaborate response. I have some questions about this method though. Apart from the fact that it looks for black blobs instead of white, how does this method differs from a simple findCountours approach?

I will look deeply into it!

Pedro Batista gravatar imagePedro Batista ( 2013-10-02 03:56:10 -0500 )edit

I never profiled it in detail, but it's way faster (and simpler) as a contour-detection since it just accumulates pixels by applying a small kernel (5 pixels as far as I remember) instead of the rather complex contour detection that has far more logic behind. By the way, you might want to skip the thresholding-process and some other parts in my implementation or simply adopt the mylabel.cpp/.h files in Uchiyama's code, where I got the labelling process from. His code is available here:

ThomasB gravatar imageThomasB ( 2013-10-02 05:34:18 -0500 )edit

I'm not being able to use the code, it shows "error LNK2001: unresolved external symbol avExtractKeys" . Did you encounter this issue?

Pedro Batista gravatar imagePedro Batista ( 2013-10-02 05:54:28 -0500 )edit

I guess you just tried to run the code from the post here? Download the complete Source from the link I provided (, it contains 4 source files (avtypes.h, avKeyExtraction.c/h and the main-file, which is included in the post here.) Don't forget to link with libraries opencv_core, opencv_highgui and opencv_imgproc

ThomasB gravatar imageThomasB ( 2013-10-02 07:21:42 -0500 )edit

No, I downloaded all the files, included the .h in my project and tried to use the functions. It is weird, because I can create a variable of type avPoint* without complaints from the compiler, but I can't call the function avExtractKeys. I tried to manually add all the functions in my code but I still can't compile :/

Pedro Batista gravatar imagePedro Batista ( 2013-10-02 07:54:26 -0500 )edit

I got it to work. thanks :)

Pedro Batista gravatar imagePedro Batista ( 2013-10-02 08:38:53 -0500 )edit

Good =) Note that Ushiyama's, from whom parts of the code are written, allows you with his license to use his code only for non-commercial projects only.

ThomasB gravatar imageThomasB ( 2013-10-02 09:05:48 -0500 )edit

Wow, this really works well and fast on bin images. But I took the time to read the scientific paper behind this method and I got the idea that the point isn't to aggregate connected regions, but to recognize random dotted markers on images. The results are very good, but now I am curious as to how this is working

Pedro Batista gravatar imagePedro Batista ( 2013-10-02 10:08:16 -0500 )edit

Its actually "just" a pre-processing step combined with feature detection (recognition of the black dots on the random dot markers). The LLAH uses the coordinates retrieved with this method to calc the id of a random dot marker based on the nearest neighbors of one, two or more points. So it's just a very small but important part of the Random Dot Marker identification process.

ThomasB gravatar imageThomasB ( 2013-10-03 02:48:29 -0500 )edit

answered 2013-10-01 08:33:51 -0500

Guanta gravatar image

As far as I understood, you'd like to apply some form of agglomerative clustering approach. Unfortunately this is not implemented and you need to implement it yourself.

If you know the number of clusters beforehand you could use kmeans-clustering on the x,y-coordinates of the white pixels...

edit flag offensive delete link more



The number of clusters may vary, and there is no way to know how many there are beforehand

Pedro Batista gravatar imagePedro Batista ( 2013-10-01 09:11:20 -0500 )edit
Login/Signup to Answer

Question Tools



Asked: 2013-10-01 05:44:25 -0500

Seen: 3,091 times

Last updated: Oct 02 '13