Density-based clustering of image keypoints

Question

I have implemented the DBSCAN algorithm for clustering image keypoints. I have been following the pseudocode on the wiki page pretty strictly, and it's working, but I get the feeling its a very naive implementation and could be improved in terms of performance. I was hoping you could offer me some feedback on how to improve it.

/* DBSCAN - density-based spatial clustering of applications with noise */

vector<vector<KeyPoint>> DBSCAN_keypoints(vector<KeyPoint> *keypoints, float eps, int minPts)
{
vector<vector<KeyPoint>> clusters;
vector<bool> clustered;
vector<int> noise;
vector<bool> visited;
vector<int> neighborPts;
vector<int> neighborPts_;
int c;

int noKeys = keypoints->size();

//init clustered and visited
for(int k = 0; k < noKeys; k++)
{
    clustered.push_back(false);
    visited.push_back(false);
}

//C =0;
c = 0;
clusters.push_back(vector<KeyPoint>()); //will stay empty?

//for each unvisted point P in dataset keypoints
for(int i = 0; i < noKeys; i++)
{
    if(!visited[i])
    {
        //Mark P as visited
        visited[i] = true;
        neighborPts = regionQuery(keypoints,&keypoints->at(i),eps);
        if(neighborPts.size() < minPts)
            //Mark P as Noise
            noise.push_back(i);
        else
        {
            clusters.push_back(vector<KeyPoint>());
            c++;
            //expand cluster
            // add P to cluster c
            clusters[c].push_back(keypoints->at(i));
            //for each point P' in neighborPts
            for(int j = 0; j < neighborPts.size(); j++)
            {
                //if P' is not visited
                if(!visited[neighborPts[j]])
                {
                    //Mark P' as visited
                    visited[neighborPts[j]] = true;
                    neighborPts_ = regionQuery(keypoints,&keypoints->at(neighborPts[j]),eps);
                    if(neighborPts_.size() >= minPts)
                    {
                        neighborPts.insert(neighborPts.end(),neighborPts_.begin(),neighborPts_.end());
                    }
                }
                // if P' is not yet a member of any cluster
                // add P' to cluster c
                if(!clustered[neighborPts[j]])
                    clusters[c].push_back(keypoints->at(neighborPts[j]));
            }
        }

    }
}
return clusters;
}

vector<int> regionQuery(vector<KeyPoint> *keypoints, KeyPoint *keypoint, float eps)
{
float dist;
vector<int> retKeys;
for(int i = 0; i< keypoints->size(); i++)
{
    dist = sqrt(pow((keypoint->pt.x - keypoints->at(i).pt.x),2)+pow((keypoint->pt.y - keypoints->at(i).pt.y),2));
    if(dist <= eps && dist != 0.0f)
    {
        retKeys.push_back(i);
    }
}
return retKeys;
}

Answer 1

Just for correctness and not for performance reasons:
You nowhere mark any key as being clustered. As a result, keys may be clustered multiple times. In case all keys shall be clustered maximum one time, one may do the following modifications to the code above:

Add a following first line

clustered[i] = true; 

behind

// add P to cluster c
clusters[c].push_back(keypoints->at(i));

and a following second line

clustered[neighborPts[j]] = true;

after

clusters[current_cluster].push_back(keypoints->at(neighborPts[j]));

Concerning the second line, make sure that it is inserted within the if-statement.

Answer 2

Your implementation is fine. There's a few little things that could change but overall wouldn't do much for efficiency. For instance, having the noise vector doesn't really do anything and sqrt() is computationally-demanding, so squaring eps before the loop then checking if(dist <= epsSquared) etc.

These are little things, and I imagine you are talking about the algorithm overall? If so, then there's little you can do. It is an \$O(n^2)\$ complexity algorithm so there's nothing you can really do to speed it up.

Answer 3

The only chance is you can introduce an indexing structure (as said in the wiki article) to execute in neighborhood query. Once I had to cluster a set of points with their spatial coordinates in an image, and I found that use of the color information of points for indexing could greatly reduce the execution time of the algorithm. Finding an indexing structure may not possible for all applications but it is worth to give a try to find a one.