Skip to content
Snippets Groups Projects

DBSCAN

Merged Sebastian Hahta requested to merge feature/clustering into master
6 files
+ 3250
1
Compare changes
  • Side-by-side
  • Inline
Files
6
#ifndef HPP_FTL_ALGORITHMS_DBSCAN_
#define HPP_FTL_ALGORITHMS_DBSCAN_
#include <vector>
#include <deque>
#include <opencv2/core/core.hpp>
namespace ftl {
template<typename T>
void dbscan(const std::vector<T> &points,
std::function<std::vector<size_t>(const std::vector<T>&, size_t, float)> RangeQuery,
unsigned int min_points, float radius,
std::vector<short> &labels, std::vector<T> &centroids) {
const short NONE = -1;
const short NOISE = -2;
labels.resize(points.size());
std::fill(labels.begin(), labels.end(), NONE);
int cluster_count = 0;
for (unsigned i = 0; i < points.size(); i++) {
short cluster = NONE;
if (labels[i] != NONE) {
continue;
}
// get neighbours of points[i]
std::vector<size_t> neighbors = RangeQuery(points, i, radius);
if (neighbors.size() < min_points) {
labels[i] = NOISE;
continue;
}
// assign new cluster id
cluster = cluster_count++;
labels[i] = cluster;
T centroid = points[i];
int n_points = 1;
std::deque<size_t> seed_set;
for (const auto &n : neighbors) {
seed_set.push_back(n);
}
while(!seed_set.empty()) {
auto i_n = seed_set.front();
seed_set.pop_front();
if (labels[i_n] == NOISE) {
// add to cluster (few lines down)
}
else if (labels[i_n] != NONE){
continue;
}
labels[i_n] = cluster;
centroid += points[i_n];
n_points++;
neighbors = RangeQuery(points, i_n, radius);
if (neighbors.size() < min_points) {
continue;
}
else {
for (const auto &n : neighbors) {
seed_set.push_back(n);
}
}
}
centroids.push_back(centroid/n_points);
}
}
}
#endif
Loading