Université d’Ottawa
Faculté de génie
École de science
d’informatique
et de génie électrique
University of Ottawa
Faculty of Engineering
School of Electrical
Engineering
and Computer Science
Object detection with the DBScan algorithm
Programming Exercise P1
(10%)
CSI2110 Data Structures and Algorithms
Fall 2022
This assignment to be done individually.
Programming P1 Nov 1 before 23:55
Late penalty : -30% for late from 1 minute to 24 hs.
Problem Description
In this programming assignment, you will implement a data clustering algorithm named DBSCAN -
Density-Based Spatial Clustering of Applications with Noise. Given a large set of data points in a space
of a
itrary dimension and given a distance metric, this algorithm can discover clusters of different
shapes and sizes, marking as outliers isolated points in low-density regions (i.e. points whose nearest
neighbors are too far away).
The DBSCAN algorithm uses two parameters:
• minPts: The minimum number of points (a threshold) in the neighborhood of a point for this one
to be considered to belong to a dense region.
• eps (ε): A distance measure that is used to identify the points in the neighborhood of any point.
CSI 2110 page 2
_________________________________________________________________________________________________
DBSCAN Algo:
DB contains the list of all points
label(P) of all P is initialized to undefined
DBSCAN(DB, eps, minPts) {
C := 0 /* Cluster counter */
for each point P in Sequence DB {
XXXXXXXXXXif label(P) ≠ undefined then continue /* Already processed */
XXXXXXXXXXNeighbors N := RangeQuery(DB, P, eps) /* Find neighbors */
XXXXXXXXXXif |N| < minPts then { /* Density check */
XXXXXXXXXXlabel(P) := Noise /* Label as Noise */
XXXXXXXXXXcontinue
}
XXXXXXXXXXC := C + 1 /* next cluster label */
XXXXXXXXXXlabel(P) := C /* Label initial point */
XXXXXXXXXXStack S.push{N} /* Neighbors to expand */
XXXXXXXXXXwhile not S.empty() {
XXXXXXXXXXQ = S.pop() /* Process point Q */
XXXXXXXXXXif label(Q) = Noise then label(Q) := C /* Noise becomes border pt */
XXXXXXXXXXif label(Q) ≠ undefined then continue /* Previously processed */
XXXXXXXXXXlabel(Q) := C /* Label neighbor */
XXXXXXXXXXNeighbors N := RangeQuery(DB, Q, eps) /* Find neighbors */
XXXXXXXXXXif |N| ≥ minPts then { /* Density check */
XXXXXXXXXXS.push{N} /* Add neighbors to stack */
}
}
}
}
RangeQuery(DB, Q, eps) {
Sequence N := empty list
for each point P in Sequence DB { /* Scan all points in DB */
XXXXXXXXXXif distance(Q, P) ≤ eps then { /* Compute distance */
XXXXXXXXXXN.add(P) /* Add to result */
}
}
return N
}
* NOTE: S.push{N} means push all elements of list N into stack S */
* Reference: https:
en.wikipedia.org/wiki/DBSCAN */
Problem to solve
The intelligent vehicles of the future will be equipped with a multitude of sensors in order to capture
information about the su
ounding scene and thus being able to autonomously navigate. One of these
sensors is the Laser Scanner or LiDAR (Light Detection And Ranging). Using a LiDAR, the vehicle can
scan the scene in front by sweeping few laser beams (typically between 8 to 64 lasers).
CSI 2110 page 3
_________________________________________________________________________________________________
https:
www.semanticscholar.org/pape
Ego-vehicle-localisation-using-LIDAR-and-compressed-Aronsson-
Eriksson/010d3f269728a76ef62ead440541bc9481bc4a58
Each time a laser beam hit an object, the laser light bounce back to the LiDAR from which a precise
distance can be estimated. A complete scan of the scene with these lasers will therefore generate a large
set of 3D points (also called point cloud) that co
espond to the structure of the scene. The figure on the
next pageshows a typical point cloud captured by a car equipped with a LiDAR; note that to facilitate
the visualization, the points are color-coded based on their height with respect to the ground. A view of
the same scene captured by a camera is also shown.
CSI 2110 page 4
_________________________________________________________________________________________________
As it can be seen, each object of the scene will be represented by several 3D points. These object’s
points should form a cluster. The objective of Part 1 of your programming assignment is therefore to run
the DBSCAN algorithm on a LiDAR point cloud in order to detect the objects around the vehicle.
Your task
You will receive 3 datasets, each containing the LiDAR point cloud for a particular scene. The points
are listed in a CSV file, one point per line.
x,y,z
XXXXXXXXXX, XXXXXXXXXX, XXXXXXXXXX
XXXXXXXXXX, XXXXXXXXXX, XXXXXXXXXX
XXXXXXXXXX, XXXXXXXXXX, XXXXXXXXXX
XXXXXXXXXX, XXXXXXXXXX, XXXXXXXXXX
…
We ask you to use the DBSCAN algorithm in order to cluster the points of a LiDAR frame. At the end of
the process, each cluster should co
espond to a scene object. You have to select the specific parameter
values of the DBSCANalgorithm that seems to produce the best results; but you have to use the same
parameters for the three datasets.
Your program takes as input the dataset filename and the value of the two DB-Scan parameters (eps,
MinPts). As output, it produces a CSV file that will contain the point coordinates and co
esponding
cluster labels. An RGB color value, unique for each cluster, is also associated to each point; this color
will be used to display the resulting clustered point cloud. Each RBG value is a number between 0.0 and
1.0. A display tool that reads this output file will be provided to you.
x,y,z,C,R,G,B
XXXXXXXXXX, XXXXXXXXXX, XXXXXXXXXX,1,1.0,0.0,0.0
XXXXXXXXXX, XXXXXXXXXX, XXXXXXXXXX,1,1.0,0.0,0.0
XXXXXXXXXX, XXXXXXXXXX, XXXXXXXXXX,1,1.0,0.0,0.0
XXXXXXXXXX, XXXXXXXXXX, XXXXXXXXXX,2,1.0,0.5,0.0
…
CSI 2110 page 5
_________________________________________________________________________________________________
Programming
Your solution must include the following Java classes, attributes and methods:
• The Point3D class that includes
o getX, getY and getZ methods returning double
! public double getX()
! public double getY()
! public double getZ()
o a cluster label
! int
o a distance method that computes the Euclidean distance between