Description du problme 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. Cet exercice de programmation vous demande de programmer un algorithme de groupement de donnes appel DBSCAN. Soit un ensemble de points dans un espace de dimension quelconque et soit une mtrique de distance, cet algorithme permet de trouver les groupements de points de dimension et formes diverses tout en identifiant les points isols n'appartement aucun groupement (i.e. les points pour lesquels leurs plus proches voisins sont loigns). L'algorithme DBSCAN utilise deux paramtres : minPts: le nombre minimum de voisins qu'un point doit avoir pour tre considr tre dans une rgion dense. eps (E): la distance permettant d'identifier les points appartenant au voisinage d'un point donn. DBSCAN Algo: // DB contains the list of all points // label (P) of all P is initialized to undefined DBSCAN (DB, eps, minPts) C = 0 { for each point P in Sequence DB { if label (P) # undefined then continue Neighbors N = RangeQuery (DB, P, eps) if NminPts then { } label (P) = Noise continue C=C1 label (P) = C Stack S.push {N} while not S.empty() { Q = s.pop() if label (Q) = Noise then label (Q) = C if label (Q) undefined then continue label (Q) = C /* Cluster counter */ /* Already processed */ /* Find neighbors */ /* Density check */ /* Label as Noise */ /* next cluster label */ /* Label initial point */ /* Neighbors to expand */ /* Process point Q */ /* Noise becomes border pt */ /* Previously processed */ /* Label neighbor */ Neighbors N = RangeQuery (DB, Q, eps) /* Find neighbors */ if N minPts then { S.push{N} /* Density check */ /* Add neighbors to stack */ RangeQuery (DB, Q, eps) { Sequence N := empty list for each point P in Sequence DB { if distance (Q, P) eps then ( N.add(P) /* Scan all points in DB */ /* Compute distance */ /* 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 */ Problme rsoudre 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). Les vhicules intelligents du futur seront quips d'une multitude de senseurs afin de capter l'information sur la scne qui les entourent de faon pouvoir naviguer de manire autonome. L'un de ces senseurs est le Scanneur Laser, aussi appel LiDAR. En utilisant un tel LiDAR, le vhicule peut examiner la scne devant lui par balayage de faisceaux laser (typiquement entre 8 et 64). T Laser beams LIDAR 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. Chaque fois qu'un faisceau laser atteint un objet, la lumire laser rebondit et retourne vers le LiDAR; celui-ci peut alors estimer la distance cet objet. Un balayage complet de la scne avec des faisceaux laser gnre donc un grand ensemble de points 3D (ou nuage de points) reprsentant la structure de la scne. La figure de la page suivante montre un tel nuage de points tel que capt par un vhicule quip d'un LiDAR; notre qu'afin de faciliter la visualisation, les points utilisent un code de couleur bas sur la hauteur des points par rapport la route. Une image de cette mme scne telle que capte par une camra est aussi montre. 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. Tel que vous pouvez le constater, chaque objet de la scne est reprsent par plusieurs points 3D. Ces points appartenant un objet devraient normalement crer un groupe. L'objectif de la Partie 1 de votre projet de programmation consiste donc utiliser l'algorithme de DBSCAN afin d'identifier les objets autour du vhicule. Votre tche 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 CSI 2510 page 5 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 Vous recevrez trois fichiers de donnes. Chacun de ces fichiers correspond une capture LiDAR (une trame). Les points de cette trame sont lists dans un fichier CSV, avec un point par ligne. 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 ... Nous vous demandons donc d'utiliser l'algorithme DBSCAN afin de grouper les points d'une trame LiDAR. A la fin du processus, chacun des groupes de points devraient correspondre un objet de la scne. Vous devrez choisir la valeur des paramtres de l'algorithme DBCAN qui semble produire les meilleurs rsultats; mais vous devez utiliser les mmes paramtres pour les trois ensembles de donnes traiter. Votre programme prendra en entre le nom du fichier contenant les points ainsi que la valeur des deux paramtres de l'algorithme DBSCAN utiliser. En sortie, votre programme doit produire un fichier CSV contenant la liste des points et l'tiquette du groupe auquel chaque point appartient. De plus, une couleur RGB sera associe chaque tiquette; cette couleur sera utilise afin de visualiser les points et leur groupe. Chaque valeur RGB est un nombre entre 0.0 et 1.0. Un outil de visualisation de nuage de points vous sera fourni. 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 Programmation Your solution must include the following Java classes, attributes and methods: The Point3D class that includes getX, getY and getZ methods returning double public double getX() public double getY() public double getZ () a cluster label int a distance method that computes the Euclidean distance between two points public double distance (Point3D pt) The DBScan class that includes a constructor that accepts a List of Point3D public DBScan (List ) setEps and setMinPts methods public double setEps (double eps) public double setMinPts (double minPts) the findClusters method that executes the DBScan algorithm public void findClusters () a getNumberOfClusters method public int getNumberOfClusters () o a getPoints that returns the list of Point3D public List getPoints () CSI 2510 page 7 the read static method that accept a filename and returns a list of Point3D public static List read (String filename) the save method that saves all the points with their cluster label and associated RGB color public void save (String filename) Note that inside the DBScan algorithm, you must use a stack as indicated in the algorithm description A Stack class (to be used inside the DBScan algorithm) with push and pop methods you can use your implementation or the one in the Java API The NearestNeighbors class that includes a constructor that accepts a List of Point3D Nearest Neighbors (List ) a rangeQuery method that finds the nearest neighbors of a 3D point public List rangeQuery (double eps) You can also create other classes and methods. Vous pouvez aussi crer d'autres classes ou mthodes. Warning: You will find on the Web, numerous implementations of the DBSCAN algorithm. You cannot use them! Do not even look at them! You have to program yourself the algorithm from scratch; not doing so will be considered plagiarism. The name of the output file must be the same than the one of the input file but to which you append the word 'clusters', the value of the parameters used and the number of clusters found using the format filename_clusters_eps_minPts_nclusters. For example, with the input file data.csv, the output file could be: data_clusters_1.2_10_57.csv Finally, running your program must be done by specifying the input filename, the parameters eps and minpts, exactly as follows: java DBScan data.csv 1.2 10 The parameter values shown are just an example, you can use other values. Before exiting, the program will save the output file and will display to the console the size of all clusters found, from the largest one to the smallest one. And the last value displayed is the number of noise points found. CSI 2510 page 8 Avertissement: Vous trouverez sur le Web de nombreuses versions de l'algorithme DBSCAN. Vous ne pouvez pas utiliser celles-ci! Ne les regardez mme pas! Vous devez programmer vous-mme l'algorithme partir de rien. Utiliser ou s'inspirer d'une source externe sera considr comme du plagiat. Le nom du fichier de sortie doit tre le mme que celui du fichier d'entre mais en y ajoutant le mot 'clusters' et la valeur des paramtres utilis ainsi que le nombre de groupes trouve, en utilisant la convention filename_clusters_eps_minPts_nclusters. Par exemple pour le fichier data.csv, vous pourriez produire le fichier: data_clusters_1.2_10_57.csv Finalement, votre programme doit se lancer en spcifiant le nom du fichier de sortie ainsi que la valeur des paramtres eps et minpts. Ceci doit se faire exactement comme suit : java DBScan data.csv 1.2 10 Les valeurs de paramtres montrs sont simplement titre d'exemple, vous pouvez utiliser d'autres valeurs. Avant de se terminer, votre programme sauvegarde le fichier de sortie et affiche la console la taille des groupes trouvs du plus grand au plus petit. Et la dernire valeur affiche est le nombre de points 'outliers' trouvs. Grille de correction Correctness of the solution: 20% Quality of programming (structures, organisation, etc) 20% Quality of documentation (comments and headers) 20% Adherence to instructions (file format, required methods): 20% 20% Abstract data types and classes used: All your files must include a header that includes your name and student number. All the files must be submitted in a single zip file. Tous vos fichiers doivent inclure un entte incluant votre nom et numro d'tudiant. Tous ces fichiers doivent tre soumis dans un fichier zip. Description du problme 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. Cet exercice de programmation vous demande de programmer un algorithme de groupement de donnes appel DBSCAN. Soit un ensemble de points dans un espace de dimension quelconque et soit une mtrique de distance, cet algorithme permet de trouver les groupements de points de dimension et formes diverses tout en identifiant les points isols n'appartement aucun groupement (i.e. les points pour lesquels leurs plus proches voisins sont loigns). L'algorithme DBSCAN utilise deux paramtres : minPts: le nombre minimum de voisins qu'un point doit avoir pour tre considr tre dans une rgion dense. eps (E): la distance permettant d'identifier les points appartenant au voisinage d'un point donn. DBSCAN Algo: // DB contains the list of all points // label (P) of all P is initialized to undefined DBSCAN (DB, eps, minPts) C = 0 { for each point P in Sequence DB { if label (P) # undefined then continue Neighbors N = RangeQuery (DB, P, eps) if NminPts then { } label (P) = Noise continue C=C1 label (P) = C Stack S.push {N} while not S.empty() { Q = s.pop() if label (Q) = Noise then label (Q) = C if label (Q) undefined then continue label (Q) = C /* Cluster counter */ /* Already processed */ /* Find neighbors */ /* Density check */ /* Label as Noise */ /* next cluster label */ /* Label initial point */ /* Neighbors to expand */ /* Process point Q */ /* Noise becomes border pt */ /* Previously processed */ /* Label neighbor */ Neighbors N = RangeQuery (DB, Q, eps) /* Find neighbors */ if N minPts then { S.push{N} /* Density check */ /* Add neighbors to stack */ RangeQuery (DB, Q, eps) { Sequence N := empty list for each point P in Sequence DB { if distance (Q, P) eps then ( N.add(P) /* Scan all points in DB */ /* Compute distance */ /* 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 */ Problme rsoudre 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). Les vhicules intelligents du futur seront quips d'une multitude de senseurs afin de capter l'information sur la scne qui les entourent de faon pouvoir naviguer de manire autonome. L'un de ces senseurs est le Scanneur Laser, aussi appel LiDAR. En utilisant un tel LiDAR, le vhicule peut examiner la scne devant lui par balayage de faisceaux laser (typiquement entre 8 et 64). T Laser beams LIDAR 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. Chaque fois qu'un faisceau laser atteint un objet, la lumire laser rebondit et retourne vers le LiDAR; celui-ci peut alors estimer la distance cet objet. Un balayage complet de la scne avec des faisceaux laser gnre donc un grand ensemble de points 3D (ou nuage de points) reprsentant la structure de la scne. La figure de la page suivante montre un tel nuage de points tel que capt par un vhicule quip d'un LiDAR; notre qu'afin de faciliter la visualisation, les points utilisent un code de couleur bas sur la hauteur des points par rapport la route. Une image de cette mme scne telle que capte par une camra est aussi montre. 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. Tel que vous pouvez le constater, chaque objet de la scne est reprsent par plusieurs points 3D. Ces points appartenant un objet devraient normalement crer un groupe. L'objectif de la Partie 1 de votre projet de programmation consiste donc utiliser l'algorithme de DBSCAN afin d'identifier les objets autour du vhicule. Votre tche 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 CSI 2510 page 5 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 Vous recevrez trois fichiers de donnes. Chacun de ces fichiers correspond une capture LiDAR (une trame). Les points de cette trame sont lists dans un fichier CSV, avec un point par ligne. 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 ... Nous vous demandons donc d'utiliser l'algorithme DBSCAN afin de grouper les points d'une trame LiDAR. A la fin du processus, chacun des groupes de points devraient correspondre un objet de la scne. Vous devrez choisir la valeur des paramtres de l'algorithme DBCAN qui semble produire les meilleurs rsultats; mais vous devez utiliser les mmes paramtres pour les trois ensembles de donnes traiter. Votre programme prendra en entre le nom du fichier contenant les points ainsi que la valeur des deux paramtres de l'algorithme DBSCAN utiliser. En sortie, votre programme doit produire un fichier CSV contenant la liste des points et l'tiquette du groupe auquel chaque point appartient. De plus, une couleur RGB sera associe chaque tiquette; cette couleur sera utilise afin de visualiser les points et leur groupe. Chaque valeur RGB est un nombre entre 0.0 et 1.0. Un outil de visualisation de nuage de points vous sera fourni. 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 Programmation Your solution must include the following Java classes, attributes and methods: The Point3D class that includes getX, getY and getZ methods returning double public double getX() public double getY() public double getZ () a cluster label int a distance method that computes the Euclidean distance between two points public double distance (Point3D pt) The DBScan class that includes a constructor that accepts a List of Point3D public DBScan (List ) setEps and setMinPts methods public double setEps (double eps) public double setMinPts (double minPts) the findClusters method that executes the DBScan algorithm public void findClusters () a getNumberOfClusters method public int getNumberOfClusters () o a getPoints that returns the list of Point3D public List getPoints () CSI 2510 page 7 the read static method that accept a filename and returns a list of Point3D public static List read (String filename) the save method that saves all the points with their cluster label and associated RGB color public void save (String filename) Note that inside the DBScan algorithm, you must use a stack as indicated in the algorithm description A Stack class (to be used inside the DBScan algorithm) with push and pop methods you can use your implementation or the one in the Java API The NearestNeighbors class that includes a constructor that accepts a List of Point3D Nearest Neighbors (List ) a rangeQuery method that finds the nearest neighbors of a 3D point public List rangeQuery (double eps) You can also create other classes and methods. Vous pouvez aussi crer d'autres classes ou mthodes. Warning: You will find on the Web, numerous implementations of the DBSCAN algorithm. You cannot use them! Do not even look at them! You have to program yourself the algorithm from scratch; not doing so will be considered plagiarism. The name of the output file must be the same than the one of the input file but to which you append the word 'clusters', the value of the parameters used and the number of clusters found using the format filename_clusters_eps_minPts_nclusters. For example, with the input file data.csv, the output file could be: data_clusters_1.2_10_57.csv Finally, running your program must be done by specifying the input filename, the parameters eps and minpts, exactly as follows: java DBScan data.csv 1.2 10 The parameter values shown are just an example, you can use other values. Before exiting, the program will save the output file and will display to the console the size of all clusters found, from the largest one to the smallest one. And the last value displayed is the number of noise points found. CSI 2510 page 8 Avertissement: Vous trouverez sur le Web de nombreuses versions de l'algorithme DBSCAN. Vous ne pouvez pas utiliser celles-ci! Ne les regardez mme pas! Vous devez programmer vous-mme l'algorithme partir de rien. Utiliser ou s'inspirer d'une source externe sera considr comme du plagiat. Le nom du fichier de sortie doit tre le mme que celui du fichier d'entre mais en y ajoutant le mot 'clusters' et la valeur des paramtres utilis ainsi que le nombre de groupes trouve, en utilisant la convention filename_clusters_eps_minPts_nclusters. Par exemple pour le fichier data.csv, vous pourriez produire le fichier: data_clusters_1.2_10_57.csv Finalement, votre programme doit se lancer en spcifiant le nom du fichier de sortie ainsi que la valeur des paramtres eps et minpts. Ceci doit se faire exactement comme suit : java DBScan data.csv 1.2 10 Les valeurs de paramtres montrs sont simplement titre d'exemple, vous pouvez utiliser d'autres valeurs. Avant de se terminer, votre programme sauvegarde le fichier de sortie et affiche la console la taille des groupes trouvs du plus grand au plus petit. Et la dernire valeur affiche est le nombre de points 'outliers' trouvs. Grille de correction Correctness of the solution: 20% Quality of programming (structures, organisation, etc) 20% Quality of documentation (comments and headers) 20% Adherence to instructions (file format, required methods): 20% 20% Abstract data types and classes used: All your files must include a header that includes your name and student number. All the files must be submitted in a single zip file. Tous vos fichiers doivent inclure un entte incluant votre nom et numro d'tudiant. Tous ces fichiers doivent tre soumis dans un fichier zip. Description du problme 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. Cet exercice de programmation vous demande de programmer un algorithme de groupement de donnes appel DBSCAN. Soit un ensemble de points dans un espace de dimension quelconque et soit une mtrique de distance, cet algorithme permet de trouver les groupements de points de dimension et formes diverses tout en identifiant les points isols n'appartement aucun groupement (i.e. les points pour lesquels leurs plus proches voisins sont loigns). L'algorithme DBSCAN utilise deux paramtres : minPts: le nombre minimum de voisins qu'un point doit avoir pour tre considr tre dans une rgion dense. eps (E): la distance permettant d'identifier les points appartenant au voisinage d'un point donn. DBSCAN Algo: // DB contains the list of all points // label (P) of all P is initialized to undefined DBSCAN (DB, eps, minPts) C = 0 { for each point P in Sequence DB { if label (P) # undefined then continue Neighbors N = RangeQuery (DB, P, eps) if NminPts then { } label (P) = Noise continue C=C1 label (P) = C Stack S.push {N} while not S.empty() { Q = s.pop() if label (Q) = Noise then label (Q) = C if label (Q) undefined then continue label (Q) = C /* Cluster counter */ /* Already processed */ /* Find neighbors */ /* Density check */ /* Label as Noise */ /* next cluster label */ /* Label initial point */ /* Neighbors to expand */ /* Process point Q */ /* Noise becomes border pt */ /* Previously processed */ /* Label neighbor */ Neighbors N = RangeQuery (DB, Q, eps) /* Find neighbors */ if N minPts then { S.push{N} /* Density check */ /* Add neighbors to stack */ RangeQuery (DB, Q, eps) { Sequence N := empty list for each point P in Sequence DB { if distance (Q, P) eps then ( N.add(P) /* Scan all points in DB */ /* Compute distance */ /* 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 */ Problme rsoudre 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). Les vhicules intelligents du futur seront quips d'une multitude de senseurs afin de capter l'information sur la scne qui les entourent de faon pouvoir naviguer de manire autonome. L'un de ces senseurs est le Scanneur Laser, aussi appel LiDAR. En utilisant un tel LiDAR, le vhicule peut examiner la scne devant lui par balayage de faisceaux laser (typiquement entre 8 et 64). T Laser beams LIDAR 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. Chaque fois qu'un faisceau laser atteint un objet, la lumire laser rebondit et retourne vers le LiDAR; celui-ci peut alors estimer la distance cet objet. Un balayage complet de la scne avec des faisceaux laser gnre donc un grand ensemble de points 3D (ou nuage de points) reprsentant la structure de la scne. La figure de la page suivante montre un tel nuage de points tel que capt par un vhicule quip d'un LiDAR; notre qu'afin de faciliter la visualisation, les points utilisent un code de couleur bas sur la hauteur des points par rapport la route. Une image de cette mme scne telle que capte par une camra est aussi montre. 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. Tel que vous pouvez le constater, chaque objet de la scne est reprsent par plusieurs points 3D. Ces points appartenant un objet devraient normalement crer un groupe. L'objectif de la Partie 1 de votre projet de programmation consiste donc utiliser l'algorithme de DBSCAN afin d'identifier les objets autour du vhicule. Votre tche 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 CSI 2510 page 5 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 Vous recevrez trois fichiers de donnes. Chacun de ces fichiers correspond une capture LiDAR (une trame). Les points de cette trame sont lists dans un fichier CSV, avec un point par ligne. 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 ... Nous vous demandons donc d'utiliser l'algorithme DBSCAN afin de grouper les points d'une trame LiDAR. A la fin du processus, chacun des groupes de points devraient correspondre un objet de la scne. Vous devrez choisir la valeur des paramtres de l'algorithme DBCAN qui semble produire les meilleurs rsultats; mais vous devez utiliser les mmes paramtres pour les trois ensembles de donnes traiter. Votre programme prendra en entre le nom du fichier contenant les points ainsi que la valeur des deux paramtres de l'algorithme DBSCAN utiliser. En sortie, votre programme doit produire un fichier CSV contenant la liste des points et l'tiquette du groupe auquel chaque point appartient. De plus, une couleur RGB sera associe chaque tiquette; cette couleur sera utilise afin de visualiser les points et leur groupe. Chaque valeur RGB est un nombre entre 0.0 et 1.0. Un outil de visualisation de nuage de points vous sera fourni. 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 Programmation Your solution must include the following Java classes, attributes and methods: The Point3D class that includes getX, getY and getZ methods returning double public double getX() public double getY() public double getZ () a cluster label int a distance method that computes the Euclidean distance between two points public double distance (Point3D pt) The DBScan class that includes a constructor that accepts a List of Point3D public DBScan (List ) setEps and setMinPts methods public double setEps (double eps) public double setMinPts (double minPts) the findClusters method that executes the DBScan algorithm public void findClusters () a getNumberOfClusters method public int getNumberOfClusters () o a getPoints that returns the list of Point3D public List getPoints () CSI 2510 page 7 the read static method that accept a filename and returns a list of Point3D public static List read (String filename) the save method that saves all the points with their cluster label and associated RGB color public void save (String filename) Note that inside the DBScan algorithm, you must use a stack as indicated in the algorithm description A Stack class (to be used inside the DBScan algorithm) with push and pop methods you can use your implementation or the one in the Java API The NearestNeighbors class that includes a constructor that accepts a List of Point3D Nearest Neighbors (List ) a rangeQuery method that finds the nearest neighbors of a 3D point public List rangeQuery (double eps) You can also create other classes and methods. Vous pouvez aussi crer d'autres classes ou mthodes. Warning: You will find on the Web, numerous implementations of the DBSCAN algorithm. You cannot use them! Do not even look at them! You have to program yourself the algorithm from scratch; not doing so will be considered plagiarism. The name of the output file must be the same than the one of the input file but to which you append the word 'clusters', the value of the parameters used and the number of clusters found using the format filename_clusters_eps_minPts_nclusters. For example, with the input file data.csv, the output file could be: data_clusters_1.2_10_57.csv Finally, running your program must be done by specifying the input filename, the parameters eps and minpts, exactly as follows: java DBScan data.csv 1.2 10 The parameter values shown are just an example, you can use other values. Before exiting, the program will save the output file and will display to the console the size of all clusters found, from the largest one to the smallest one. And the last value displayed is the number of noise points found. CSI 2510 page 8 Avertissement: Vous trouverez sur le Web de nombreuses versions de l'algorithme DBSCAN. Vous ne pouvez pas utiliser celles-ci! Ne les regardez mme pas! Vous devez programmer vous-mme l'algorithme partir de rien. Utiliser ou s'inspirer d'une source externe sera considr comme du plagiat. Le nom du fichier de sortie doit tre le mme que celui du fichier d'entre mais en y ajoutant le mot 'clusters' et la valeur des paramtres utilis ainsi que le nombre de groupes trouve, en utilisant la convention filename_clusters_eps_minPts_nclusters. Par exemple pour le fichier data.csv, vous pourriez produire le fichier: data_clusters_1.2_10_57.csv Finalement, votre programme doit se lancer en spcifiant le nom du fichier de sortie ainsi que la valeur des paramtres eps et minpts. Ceci doit se faire exactement comme suit : java DBScan data.csv 1.2 10 Les valeurs de paramtres montrs sont simplement titre d'exemple, vous pouvez utiliser d'autres valeurs. Avant de se terminer, votre programme sauvegarde le fichier de sortie et affiche la console la taille des groupes trouvs du plus grand au plus petit. Et la dernire valeur affiche est le nombre de points 'outliers' trouvs. Grille de correction Correctness of the solution: 20% Quality of programming (structures, organisation, etc) 20% Quality of documentation (comments and headers) 20% Adherence to instructions (file format, required methods): 20% 20% Abstract data types and classes used: All your files must include a header that includes your name and student number. All the files must be submitted in a single zip file. Tous vos fichiers doivent inclure un entte incluant votre nom et numro d'tudiant. Tous ces fichiers doivent tre soumis dans un fichier zip.