programming assignment
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 arbitrary 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 { if label(P) ≠ undefined then continue /* Already processed */ Neighbors N := RangeQuery(DB, P, eps) /* Find neighbors */ if |N| < minpts then { /* density check */ label(p) := noise /* label as noise */ continue } c := c + 1 /* next cluster label */ label(p) := c /* label initial point */ stack s.push{n} /* neighbors to expand */ while not s.empty() { q = s.pop() /* process point q */ if label(q) = noise then label(q) := c /* noise becomes border pt */ if label(q) ≠ undefined then continue /* previously processed */ label(q) := c /* label neighbor */ neighbors n := rangequery(db, q, eps) /* find neighbors */ if |n| ≥ minpts then { /* density check */ s.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 */ if distance(q, p) ≤ eps then { /* compute distance */ n.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 surrounding 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/paper/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 correspond 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 -5.057771786205823,-4.132708931956775,0.2428091883181846 -5.0355177525576,-4.088825974461278,0.241137471769056 -5.125807925277937,-4.136111826946676,0.2448524059120176 -5.079222136014556,-4.072855314440647,0.2420290529642492 … 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 correspond 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 corresponding 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 -5.057771786205823,-4.132708931956775,0.2428091883181846,1,1.0,0.0,0.0 -5.0355177525576,-4.088825974461278,0.241137471769056,1,1.0,0.0,0.0 -5.125807925277937,-4.136111826946676,0.2448524059120176,1,1.0,0.0,0.0 -5.079222136014556,-4.072855314440647,0.2420290529642492,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 minpts="" then="" {="" *="" density="" check="" */="" label(p)="" :="Noise" *="" label="" as="" noise="" */="" continue="" }="" c="" :="C" +="" 1="" *="" next="" cluster="" label="" */="" label(p)="" :="C" *="" label="" initial="" point="" */="" stack="" s.push{n}="" *="" neighbors="" to="" expand="" */="" while="" not="" s.empty()="" {="" q="S.pop()" *="" process="" point="" q="" */="" if="" label(q)="Noise" then="" label(q)="" :="C" *="" noise="" becomes="" border="" pt="" */="" if="" label(q)="" ≠="" undefined="" then="" continue="" *="" previously="" processed="" */="" label(q)="" :="C" *="" label="" neighbor="" */="" neighbors="" n="" :="RangeQuery(DB," q,="" eps)="" *="" find="" neighbors="" */="" if="" |n|="" ≥="" minpts="" then="" {="" *="" density="" check="" */="" s.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="" */="" if="" distance(q,="" p)="" ≤="" eps="" then="" {="" *="" compute="" distance="" */="" n.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="" surrounding="" 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/paper/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="" correspond="" 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="" -5.057771786205823,-4.132708931956775,0.2428091883181846="" -5.0355177525576,-4.088825974461278,0.241137471769056="" -5.125807925277937,-4.136111826946676,0.2448524059120176="" -5.079222136014556,-4.072855314440647,0.2420290529642492="" …="" 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="" correspond="" 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="" corresponding="" 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="" -5.057771786205823,-4.132708931956775,0.2428091883181846,1,1.0,0.0,0.0="" -5.0355177525576,-4.088825974461278,0.241137471769056,1,1.0,0.0,0.0="" -5.125807925277937,-4.136111826946676,0.2448524059120176,1,1.0,0.0,0.0="" -5.079222136014556,-4.072855314440647,0.2420290529642492,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="">