xmba15 / generic_dbscan

generic DBSCAN on CPU & GPU

📝 c++ generic DBSCAN

---

• c++ generic dbscan library on CPU & GPU. header-only codes for cpu dbscan.
• cpu dbscan uses kd-tree for radius search.
• gpu dbscan or G-DBSCAN uses BFS on nodes of point.

🎉 TODO

---

• Implement generic kd-tree
• Implement generic dbscan
• Create unittest & examples
• GPU DBSCAN

🎛 Dependencies

---

• base dependencies

sudo apt-get install \
    libpcl-dev \

tested with pcl 1.10

• gpu dbscan

CUDA toolkits (tested on cuda 11)

lower pcl version (that uses older eigen version) might not be compatible with cuda

🔨 How to Build

---

# build lib
make default -j`nproc`

# build examples

# build only cpu dbscan
make apps -j`nproc`

# build both cpu and gpu dbscan
make gpu_apps -j`nproc`

🏃 How to Run

---

• This library provides an example with clustering point cloud from livox horizon lidar

# after make apps or make gpu_apps

# cpu
./build/examples/test_pointcloud_clustering [path/to/pcl/file] [eps] [min/points]

# gpu

./build/examples/test_pointcloud_clustering_gpu [path/to/pcl/file] [eps] [min/points]

# eps and min points are parameters of dbscan algorithm

# for example
./build/examples/test_pointcloud_clustering ./data/street_no_ground.pcd 0.7 3 1

# or
./build/examples/test_pointcloud_clustering_gpu ./data/street_no_ground.pcd 0.7 3 1

# change final parameters to 0 to disable visualization

• processing time (average of 10 tests):

# number of points: 11619
# processing time (cpu): 80[ms]
# processing time (gpu): 38[ms]

# difference in speed will get more obvious with point cloud of more points

• Here is the sample result:

🐳 How to Run with Docker

• cpu

# build
docker build -f ./dockerfiles/ubuntu2004_gpu.dockerfile -t dbscan .

# run
docker run -it --rm -v `pwd`:/workspace dbscan

• gpu: change the cuda version here to match your local cuda version before build.

# build
docker build -f ./dockerfiles/ubuntu2004_gpu.dockerfile -t dbscan_gpu .

# run
docker run -it --rm --gpus all -v `pwd`:/workspace dbscan_gpu

💎 References

---

• kdtree
• dbscan
• G-DBSCAN: A GPU Accelerated Algorithm for Density-based Clustering
• SLIC-DBSCAN-CUDA

generic_dbscan's Issues

compiling problem

Thanks for your open source, After compiling the source code, I got the folloewing warning. Do you know how to avoid these warning?

:0:16: warning: ISO C++11 requires whitespace after the macro name
:0:19: warning: ISO C++11 requires whitespace after the macro name
:0:23: warning: ISO C++11 requires whitespace after the macro name
:0:16: warning: ISO C++11 requires whitespace after the macro name
:0:19: warning: ISO C++11 requires whitespace after the macro name
:0:23: warning: ISO C++11 requires whitespace after the macro name

warning: ‘void HandleError(cudaError_t, const char*, int)’ defined but not used [-Wunused-function]
static void HandleError(cudaError_t err, const char* file, int line)
^~~~~~~~~~~

Got a problem running project following to the instructions in Readme.md

Hi everybody,
I'm having a problem running the command according to the instructions in Readme.md,
Please help me solve it so I can run it with my dataset. Thanks a lot!

gpu process time is too large

i run this code in my pc,and the result is the gpu process time is 500 ms and cpu 80 ms?
is any wrong i do?

how to improve the running speed

Thanks for your great work, I have implement this repository on the real program. But I found the speed is not very idea. Is it possible to merge function makeGraphStep1Kernel and makeGraphStep2Kernel, because I found there exists similar calculation in this two functions.

Performance issue

Hi @xmba15 ,

Thanks for this amazing implementation.

I used a Eigen::Vector2d to perform clustering as follows:

template <typename POINT_CLOUD_TYPE>
double at(const POINT_CLOUD_TYPE &p, const int axis) {
  switch (axis) {
  case 0: {
    return p(0);
    break;
  }
  case 1: {
    return p(1);
    break;
  }
  default: {
    throw std::runtime_error("axis out of range");
  }
  }
}
template <typename POINT_CLOUD_TYPE>
double
distance(const POINT_CLOUD_TYPE &p1, const POINT_CLOUD_TYPE &p2,
         const std::function<double(const POINT_CLOUD_TYPE &p, const int axis)>
             &valueAtFunc = ::at<POINT_CLOUD_TYPE>) {
  double result = 0.0;
  for (int i = 0; i < 2; ++i) {
    result += std::pow(valueAtFunc(p1, i) - valueAtFunc(p2, i), 2);
  }
  return std::sqrt(result);
}

int main(int argc, char *argv[]) {

    const double eps = std::stof(argv[3]);

    const int minPoints = std::stoi(argv[4]);
    using DBSCAN = clustering::DBSCAN<2, grid_map::Position,
                                      decltype(points_navigable_zone)>;
    DBSCAN::Ptr dbscan =
        std::make_shared<DBSCAN>(eps, minPoints, ::distance<grid_map::Position>,
                                 ::at<grid_map::Position>);
   
    std::vector<std::vector<int>> clusterIndices;
    std::cout << "POINTS SIZE" << points_navigable_zone.size() << std::endl;
      clusterIndices = dbscan->estimateClusterIndices(points_navigable_zone);

}

Although for just 430 points the time performance is 23 ms using the following parameters:

• eps:0.4
• minPoints: 2

Can you help me understand why the performance is slow?

Thanks,
Bruno