Acta Polytechnica doi:10.14311/AP.2018.58.0165 Acta Polytechnica 58(3):165–170, 2018 © Czech Technical University in Prague, 2018 available online at http://ojs.cvut.cz/ojs/index.php/ap AUTOMATIC CLASSIFICATION OF POINT CLOUDS FOR HIGHWAY DOCUMENTATION Martina Hůlková, Karel Pavelka∗, Eva Matoušková Department of Geomatics, Faculty of Civil Engineering, Czech Technical University in Prague, Czech Republic ∗ corresponding author: pavelka@fsv.cvut.cz Abstract. Mobile laser scanning systems confirmed the capability for detailed roadway documentation. Hand in hand with enormous datasets acquired by these systems is the increase in the demands on the fast and effective processing of these datasets. The crucial part of the roadway datasets processing, as well as in many other applications, is the extraction of objects of interest from point clouds. In this work, an approach to the rough classification of mobile laser scanning data based on raster image processing techniques is presented. The developed method offers a solution for a computationally low demanding classification of the highway environment. The aim of this method is to provide a background for the easier use of more sophisticated algorithms and a specific analysis. The method is evaluated using different metrics on a 1.8km long dataset obtained by LYNX Mobile Mapper over a highway. Keywords: mobile laser scanning; road inventory; classification; image processing. 1. Introduction Mobile laser scanning (MLS), a highly efficient tool for acquiring dense point clouds, has been accepted as a standard for the mapping of road corridors. It is applicable in areas, such as project planning, project development, construction, operations, maintenance, safety, research, and asset management [1]. Most of these applications demand a complete description of the road geometry and all objects on, above or near the road surface. For an efficient use of the acquired datasets, a tool for extraction of all objects in the scene is needed. Despite the fact that the concept of the method for overall structure recognition from mobile laser scanned point clouds was presented in [2], most of the later presented works still focuses on the detection of a sole object type. Among other things, the detection of road markings from road surface points [3], detection of vertical traffic signs and extrac- tion of its main geometric parameters [4], detection of tunnel luminaires [5] and detection of pole-like objects in urban scenes [6] can be noted. The high accuracy of these narrowly focused sophisticated methods is of- ten related to high computational demands. However, these demands can be decreased by decreasing the number of input points. The solution can be found in the rough classification of the point cloud into sev- eral basic classes, which serve as a background for a further sophisticated analysis. 2. Concept The concept of the method for a rough point cloud classification of roadway scenes is based on the follow- ing premises: (1.) The point cloud classification problem can be transformed into an image classification problem, which enables the application of techniques for the image processing of the classification and re- duce the computational demands of spatial queries (much lower on raster images than on unorga- nized/organized point cloud). (2.) Characteristics of classified objects are known and can be used for the classification (refers to knowledge based methods). (3.) Many of the formerly presented algorithms for ground point filtering have reached a satisfying per- formance and the presented method can profit from their outputs (a prior knowledge of the terrain po- sition is demanded). (4.) The basic concept of the method prefers low com- putational demands to absolute accuracy. 3. Dataset The point cloud used for the method development and evaluation was acquired in 2009 by LYNX Mobile Mapper and it represents the highway D11 in the Czech Republic. Ten blocks of a size of 200 × 200m were selected for the development phase and a 1.8 km long continuous strip (divided into 9 blocks) for the evaluation. Both datasets (for development and eval- uation) contain objects from all classes and reflect the variability of the scenes (dense and sparse vegetation, cutting and embankment). The Input file has a form of a text file (.txt) and contains the following information: class, x, y, zover ground, intensity, z (in this order, blank space is used as a delimiter). The method uses both the absolute altitude of a point (z) and the relative height of the point over the terrain (zover ground) for classi- fication, therefore, a prior knowledge of the terrain position is demanded. The estimation of the terrain 165 http://dx.doi.org/10.14311/AP.2018.58.0165 http://ojs.cvut.cz/ojs/index.php/ap M. Hůlková, K. Pavelka, E. Matoušková Acta Polytechnica Figure 1. The diagram of the presented method. position and computation of the height over the ter- rain were accomplished by the automatic functions of the TerraScan software. 4. Description of the method The process of classification consists of three steps: the creation of images displaying selected point cloud characteristics, the classification of images and apply- ing the results of the classification on the point cloud (Figure 1). The presented method focuses on highway scenes outside the city and the selection of the classes corre- sponds to the common objects present in these scenes. Points are divided into ten classes, see Table 1. The dataset used for the testing and detailed pro- cess of classification are described in the following paragraphs. 4.1. Point clouds into raster images In order to arrange the easy and fast production of raster images for the classification, the data in the point cloud were divided into voxels and a matrix summarizing the information about individual voxels (later called the voxel matrix) was created to serve as an intermediate between the point cloud and raster im- age. The size of a voxel was 0.20 × 0.20 × 0.10m. The density in used dataset varies between units and hun- dreds per square meter – the density of point clouds from the MLS steeply decreases with the distance from the scanning system. The size of the voxel was limited by the lowest density in the observed scene. The resolution in the first two dimensions correspond 01 Unclass (points, which cannot be assigned to any other class) 02 Ground 03 Roadway 04 Vehicles (temporary objects on the roadway) 05 Gates (all objects above the roadway – toll gates, power lines, ecoducts etc.) 06 Crash-barriers 07 Poles (pole-like objects, e.g., utility poles and delineator posts) 08 Signs (vertical traffic signs and other boards) 09 Walls ((noise) walls and (wire) fences) 10 Vegetation Table 1. Classes of points. to the former pixel size in raster images. A higher resolution leads to an abundance of empty pixels and a lower resolution causes that many pixels contain points from more than one object. The third dimen- sion has a higher resolution to ensure the classification of low objects. The voxel matrix is a four dimensional matrix – the first three dimensions refer to the position of individual voxels (x, y and zover ground, transformed into the voxel matrix coordinate system) and the last dimension refers to four parameters describing points, which belong to the corresponding voxel – number of points belonging to the voxel, minimal height of 166 vol. 58 no. 3/2018 Automatic Classification of Point Clouds for Highway Documentation the point over terrain, maximal intensity (reflectivity), and minimal altitude. This voxel matrix serves as a source for the raster image creation. For instance, the raster image of potential crash barrier points is based on a number of points included in voxels between 0.5m and 1.0m height over terrain (based on minimal height set for crash barriers in the Czech Republic – 0.75m [7]). 4.2. Raster image classification Objects belonging to different classes are situated in different heights over the terrain. When points are projected on a horizontal plane to create a raster image, one pixel can comprise of points from differ- ent classes (objects from different classes can have overlaps); hence the classification cannot be done on one raster image, but each class should be classified separately. For each class, a raster image (or images), which displays the parameter that is significant for the class, is derived from the voxel matrix. These parameters are selected according to specific characteristics of the class. For instance, the roadway is a smooth surface of a low slope and it is situated near the mobile mapping system during the data capture, so the point den- sity on the roadway is higher than on other surfaces. Therefore, the roadway class is based on a combina- tion of three raster images, which display maximal height of points over terrain, local slope, and point density. Another example is crash barriers, whose parameters fulfil specified criteria (e.g., in height, size, position). The crash barriers class is based on an image displaying the point density in a specific height over terrain. The created image (or combination of images) dis- plays points potentially belonging to the selected class. The next steps have to confirm which pixels/group of pixels really belong to the class and which do not. For that purpose, image processing techniques from the following categories are applied to the image (usually in the same order, but some of them repeatedly): • image segmentation by thresholding (image bina- rization); • image filtering (to emphasize certain features or remove other features); • object-oriented classification (based on objects shape, size, and context). The creation of a primary image displaying po- tential class pixels and the application of previously mentioned image processing techniques are repeated for each class (from 03 – roadway to 10 – vegetation) and lead to production of images representing indi- vidual classes. The class gates is represented by three raster images – the first, called gates, represents parts of objects in height 4.5m over the terrain and higher, the others, called gate end and gate column, represent lower parts of the same objects. The resulting raster images serve for the classification of the point cloud. Figure 2. Classification – from raster image to point cloud. The process of the image creation and classification was developed and evaluated on selected datasets. Re- gardless how sophisticated the automatic classification is, it sometimes fails. This failure manifests itself in the form of two types of errors – FN (false negative – point should belong to the class but it is not classified) and FP (false positive – point should not belong to the class but it is classified). The efforts made in order to decrease one error type lead usually to an increase of the other error type, therefore, a decision has to be made between minimizing FN and FP errors for every class. 4.3. Raster image into point cloud It is clear, from the previous example, that the pixels of a same position on classified raster images can belong to more than one class. The transmission of classification results from raster images into the point cloud is realized in a way presented by the diagram in Figure 2. The points, in the first step, are divided into two groups according to the height over the terrain – the points lower than 0.025m over the terrain are assumed to be a part of the class roadway (in case that the point belongs to a pixel classified as the roadway class) or ground (in the opposite case). From the second group, 167 M. Hůlková, K. Pavelka, E. Matoušková Acta Polytechnica Manual classification Class 1 2 3 4 5 6 7 8 9 10 1 76.0 0.1 0 1.7 0.4 0.3 5.5 1 10.5 3 2 9.3 91.3 1 0 0.1 0.1 0 0 0.6 0.2 3 1 8.5 99.0 0 0 0 0 0 0 0 4 0.3 0 0 69.3 0 0 11.1 2.7 0 0 5 0.2 0 0 0 98.6 0 0 0 0 0 6 9.5 0 0 29.0 0.8 99.7 0 1.4 0 0 7 0.1 0 0 0 0 0 83.4 0.7 0 0 8 0.1 0 0 0 0 0 0 94.1 0 0 9 0.7 0 0 0 0 0 0 0 87.4 0.1 A ut om at ic cl as si fic at io n 10 2.8 0 0 0 0.1 0 0 0 1.5 96.8 Table 2. Confusion matrix [%]. Class 1 2 3 4 5 6 7 8 9 10 FN [%] 24.1 8.7 1.0 30.7 1.4 0.3 16.6 5.9 12.6 3.3 FP [%] 4.1 13.2 2.3 19.2 2.4 27.8 43.8 15.6 18.1 3.5 Table 3. False negative (FN) and false positive (FP) errors. Figure 3. Automatically classified point cloud. points are tested to be higher than 4.5m over the ter- rain and incident to the gates class or not. If not, each pixel is tested to raster images of other classes, respec- tively to their importance. First comes the smaller objects connected to the traffic management, such as vertical traffic signs and delineator posts (signs and poles), then other objects connected to the traf- fic safety (crash barriers), other manmade structures (walls), vegetation and afterwards, all temporary ob- jects (vehicles) and objects or parts of objects, which stay unclassified (unclass). The described workflow is very fast and simple, but offers a limited possibility of overlapping the objects classification. 5. Results The presented method was tested on a 1.8 km long part of the D11 highway divided into nine blocks (200 × 200m). The reference data were manually clas- sified. The manual classification was conducted using TerraScan software – at first, tools for a semiautomatic classification were used. Then, the classified dataset was carefully inspected by a human expert and clas- sification was manually improved when needed. The quantitative evaluation of the method is based on a comparison of an automatically (by the presented method) and manually classified dataset; it includes a confusion matrix generation (Table 2) and a summary of FN and FP errors (Table 3). Names of classes in tables are replaced by codes: 1 – unclass, 2 – ground, 3 – roadway, 4 – vehicles, 5 – gates, 6 – crash barriers, 7 – poles, 8 – signs, 9 – walls, 10 – vegetation. The tested dataset consists of more than 32 million points and 94.5% of the points were classified correctly (Figure 3). The detailed results of the classification are presented in the confusion matrix (Tab. 1). The high- est classification accuracy was achieved for roadway, gates, and vegetation classes (classification accuracy over 96% and amount of both error types lower than 4%). The lowest classification accuracy was achieved 168 vol. 58 no. 3/2018 Automatic Classification of Point Clouds for Highway Documentation Class 1 2 3 4 5 6 7 8 9 10 Completeness 0.76 0.91 0.99 0.69 0.99 1.00 0.83 0.94 0.87 0.97 Correctness 0.96 0.87 0.98 0.81 0.98 0.72 0.56 0.84 0.82 0.97 F-rate 0.85 0.89 0.98 0.75 0.98 0.84 0.67 0.89 0.85 0.97 Table 4. Completeness and correctness of proposed method. Classification objects Completeness Correctness F-rate Ref. Vertical traffic sings. outside city 0.94 0.98 – [8] Pole-like objects. city 0.95 0.99 – [6] Classes – building, road, pole, car, tree, unclassified; city 0.83–0.94* [9] Vertical traffic signs 0.93 0.92 0.93 [10] *results from five datasets Table 5. Examples of classification algorithms. for the vehicles (69.3%) and poles classes (83.4%). The low accuracy of the vehicles classification was ex- pected. The class vehicles contains temporary objects, which should be removed before executing any analy- sis on the point cloud. The classification parameters were set to minimize the classification of any objects belonging to other classes; the setting preferred the higher number of FN to FP errors. The poles class had a significantly higher number of both types of errors. The algorithm had correctly classified 54 out of 59 objects; however, the left 5 unclassified objects are represented by 16.6% of points. The enormous number of FP errors (43.8%) is mainly represented by points from tree trunks, which are hard to distinguish from utility poles. The class crash barriers has a high number of FP errors (27.8%); most of these false pos- itives should belong to the vehicles class. Vehicles in a point cloud sometimes form long linear objects and when projected into the image, they appear similar to crash barriers. Despite of the simple principle of the presented method, the results achieved by this method (Table 4) are comparable to the results of more sophisticated classification methods presented in the last year five years (Table 5). 5.1. Examples of errors Despite of the relatively high accuracy of the presented method, there were still a number of situations in which the algorithm fails. It was highly problematic to distinguish between tree trunks and utility poles. The main difference between these two objects is the tree crown; however, in dense forest stands, it is usual that the number of points describing individual trees (especially tree crowns) strongly decrease with the distance from the mobile scanning system (Figure 4). Highly reflective surfaces (typical for vertical traffic signs) can cause multiple reflections, which appear in a form of a shadow behind the surface (Figure 5). The reflecting object, together with the shadow, creates a Figure 4. Tree trunk assigned to poles (purple). Figure 5. Vertical traffic signs assigned to vehicles (red). complex object, which has different parameters than the original one and can be wrongly classified. Steep slopes, terrain discontinuities and bridges typ- ically cause difficulties for ground filtering algorithms. Classification of objects on terrain discontinuities, such as retaining walls or ends of bridges, remains prob- lematic (Figure 6). More details about the presented method and its evaluation can be found in [11]. 169 M. Hůlková, K. Pavelka, E. Matoušková Acta Polytechnica Figure 6. Retaining wall assigned to signs (yellow) and vegetation (green). 6. Conclusions Both the manual and automatic classification of a tested dataset were executed on a standard office com- puter. The manual classification lasted 19 hours while the automatic classification lasted only 54 minutes. The automatic classification achieved the overall clas- sification accuracy of 94.5%, however the accuracy of individual classes significantly varies. Despite the achieved accuracy of the presented method, which exceeded the expectations and did not stay far be- hind other methods for the point cloud classification, there are still opportunities for a further enhancement. The misclassification of tree trunks to the poles class and long vehicles to crash barriers class remains espe- cially challenging. The basic concept of the presented method – the transfer of a point cloud classification problem into a raster classification and the execution of spatial queries on a pixel to pixel basis instead of the point to point basis – is connected to low computa- tional demands and high efficiency, which compensate the error rate of a method given by the method prin- ciple. Acknowledgements The research has been supported by the student grant of CTU in Prague: SGS17/068/OHK1/1T/11. The acqui- sition of MLS dataset was supported by the Ministry of Transport of the Czech Republic under project CG912- 105-520. References [1] Olsen, M. J.: Guidelines for the Use of Mobile LiDAR in Transportation Applications. National Academy of Sciences, Washington, DC., 2013. ISSN 0077-5614, ISBN 978-0-309-25914-9. [2] Pu, S. el al.: Recognizing Basic Structures from Mobile Laser Scanning Data for Road Inventory Studies. ISPRS Journal of Photogrammetry and Remote Sensing 66 (2011), pp.528-539. doi:10.1016/j.isprsjprs.2011.08.006 [3] Guan, H. et al.: Using Mobile LiDAR Data for Rapidly Updating Road Markings. IEEE Trans. Intell. Transp. Syst. 2015, 16, pp.2457–2466. doi:10.1109/TITS.2015.2409192 [4] Soilán, M. et al.: Traffic sign detection in MLS acquired point clouds for geometric and image-based semantic inventory. ISPRS Journal of Photogrammetry and Remote Sensing 2016, 114, pp. 92–101. doi:10.1016/j.isprsjprs.2016.01.019 [5] Puente, I. et al.: Automatic detection of road tunnel luminaires using a mobile LiDAR system. Measurement, 47 (2014), pp. 569-575, doi:10.1016/j.measurement.2013.09.044 [6] Rodrígues-Cuenca, B. et al.: Automatic Detection and Classification of Pole-Like Objects in Urban Point Cloud Data Using an Anomaly Detection Algorithm. Remote Sens. 2015, 7, 12680-12703. doi:10.3390/rs71012680 [7] TP 114 - Svodidla na pozemních komunikacích, 2015. Technické podmínky, Ministerstvo dopravy. http://www.pjpk.cz/technicke-podminky-tp/ [2018-06-15]. [8] Riveiro, B. et al.: Automatic Segmentation and Shape-Based Classification of Retro-Reflective Traffic Signs from Mobile LiDAR Data. IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing, 2016, vol. 9, iss. 1, pp. 295-303. doi:10.1109/JSTARS.2015.2461680 [9] Aijazi, A.K.; Checchin, P.; Trassoudaine, L.: Segmentation Based Classification of 3D Urban Point Clouds: A Super-Voxel Based Approach with Evaluation. Remote Sens., 2013, 5, pp1624-1650. doi:10.3390/rs5041624 [10] Yu, Y. et al.: Learning Hierarchical Features for Automated Extraction of Road Markings From 3-D Mobile LiDAR Point Clouds. IEEE J. Sel. Top. Appl. Earth Obs. Remote Sens. 2015;8:709–726. doi:10.1109/JSTARS.2014.2347276 [11] Hůlková, M.: Mobilní laserové skenování v dopravě. Praha, 2017. Disertační práce. ČVUT v Praze, Fakulta stavební, katedra geomatiky. 170 http://dx.doi.org/10.1016/j.isprsjprs.2011.08.006 http://dx.doi.org/10.1109/TITS.2015.2409192 http://dx.doi.org/10.1016/j.isprsjprs.2016.01.019 http://dx.doi.org/10.1016/j.measurement.2013.09.044 http://dx.doi.org/10.3390/rs71012680 http://www.pjpk.cz/technicke-podminky-tp/ http://dx.doi.org/10.1109/JSTARS.2015.2461680 http://dx.doi.org/10.3390/rs5041624 http://dx.doi.org/10.1109/JSTARS.2014.2347276 Acta Polytechnica 58(3):165–170, 2018 1 Introduction 2 Concept 3 Dataset 4 Description of the method 4.1 Point clouds into raster images 4.2 Raster image classification 4.3 Raster image into point cloud 5 Results 5.1 Examples of errors 6 Conclusions Acknowledgements References