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 visitedfor(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 keypointsfor(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;}
Density-based clustering of image keypoints
c++;performance;algorithm;clustering;opencv
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 cclusters[c].push_back(keypoints->at(i));and a following second lineclustered[neighborPts[j]] = true;afterclusters[current_cluster].push_back(keypoints->at(neighborPts[j]));Concerning the second line, make sure that it is inserted within the if-statement.