Received March 10, 2014; Accepted April 17, 2014; Published April 21, 2014
Citation: Bellakaout A, Omari Mohammed C, Mohamed E, Abderrahmane T (2014) Automatic Segmentation of Lidar Data. J Archit Eng Tech 3:128. doi: 10.4172/2168-9717.1000128
Copyright: © 2014 Bellakaout A, et al., This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.
Visit for more related articles at Journal of Architectural Engineering Technology
Topographical technology by Airborne LIDAR (Light Detection and Ranging) generates a precise points cloud with a density of several points per square meter, LIDAR data processing is a crucial step to be used. Extraction of 3D information in automatic way and especially in urban areas from LIDAR data is one of the most difficult problems in computer vision; it is also a necessary step for implementation of several applications that require a high level interpretation of LASER data. Therefore, there is recently an increased interest in this research field and a vast literature. The problematic discussed in this article lies in the differentiation between the sets of points that represent a specified layer of information (construction, vegetation, roads, lines, etc.). This step is called segmentation. The aim of this study is to provide a set of automatic segmentation techniques tailored to different types of 3D data and proposes a methodology to classify LIDAR data with a maximum degree of automaticity using only point cloud data.
Segmentation; LIDAR; 3D; Point cloud; Automatic
For a long time, scientists are studying methods of data collection well as their representation. The advent of LIDAR systems has allowed the collection of a significant number of points in three dimensions in a very short time.
LASER airborne systems are active sensors that incorporate a mechanism for direct georeferencing (coupled Inertial/GPS), light pulses emitted providing a dense 3D point cloud that faithfully represents the topography scanned, which requires a careful and powerful treatment.
Segmentation or automatic classification of 3D LIDAR data from urban scenes has a very important role in the scientific community given its importance for modeling an urban scene, as it can significantly reduce the resources required for data analysis and 3D modeling of cities.
Processing LIDAR point cloud in an automatic way by special algorithms permits to generate plans in an instant way.
The first result of processing LIDAR data is the segmentation of the point cloud into two main classes: ground and above ground. This segmentation can be obtained by using other sources of information such as 2D cadastral data, the signal intensity or just based on the 3D data (X, Y, and Z).
A good segmentation result does not necessarily allow a good interpretation, but we cannot get a good interpretation from a bad segmentation result. We propose, through this paper, a study of the state of the art of different segmentation methods proposed in the literature.
The segmentation can be conducted in three distinct approaches categorized on the basis of type of data used:
The first is based on the point cloud without referring to DSM or other sources of information.
The second relates to derivative products , in other words, the treatment focuses on one of the products generated from the point cloud precisely the DSM, MNT, intensity, height difference image... etc., and in this case the remote sensing methods are used.
And the third segmentation approach uses several complementary data sources, as non-limiting examples, satellite images, aerial photos, cadastral data, digital terrain models... these are multi-source approaches.
Approaches based only on the raw point cloud
In the literature there are a limited number of algorithms for this approach (Figure 1).
The octree structure is a data structure from tree type in which each node can have up to eight sub-nodes. The octree is the most often used to partition a three dimensional space by recursively subdividing it into eight octants.
This method was proposed by Wang and Tseng for LIDAR point cloud, its principle is which is the hierarchical decomposition of the cloud point on the octree structure until the points contained in each node belong to the same plane, the disadvantage of this method is that it is unable to classify them .
In the first step, the surface is calculated with a matrix weight equal to one, this is an average surface between points on the ground and above-ground which generally gives a negative residue at the points of the soil class and reverse to the above-ground class, these residues are used to calculate the weight matrix (Pi) for each measure (Zi).
The weight function is established to affect high coefficients (≈1) to above-ground surface points; which are situated below or adjacent to the middle surface; and affect low coefficient (≈ 0) to the ground surface points (Figure 2).
This method is effective to divide the points into two classes: ground and above-ground surface, this method does not extract the “buildings”, “vegetation” and “linear objects” classes, because the above-ground class contains buildings, vegetation et al., so all 3D objects.
Detection of 3D surfaces is a method introduced for classifying 3D objects in satellite images, a lot of work has been done in this direction, but they often focus only on the signal level. Mohan and Nevatia studies provide an approach to detect and describe 3D objects by perceptual grouping; their purpose is to detect buildings in aerial images .
Koster and Spann, Jiang et al., Liu and Wang and Hoover et al. studies particularly focus on satellite images [5-8]. Boyer and Sarkar conclude that 3D perceptual organization is one of the most important research directions in this area because 3D sensors have become cheaper and available .
In 2002, Lee and Schenk proposed a segmentation process based on the detection of 3D surfaces especially for LIDAR data using the point cloud without any prior interpolation .
This segmentation method allows dividing in automatic way the cloud into two classes which are the soil and buildings class without evoking the vegetation class because it considers that urban scene consists only of land and buildings.
Later than, Filin and Pfeifer propose a method using the “neighborhood system” based on the calculation of normal points of the cloud. This system is based on a distance criterion and the geometric data content. It is designed to follow the height and shape of objects not only their planimetric location within the point cloud [11,12].
Recently, Lari et al., propose an algorithm that organizes the points cloud in tree (kd-tree) by calculating the neighborhood of each point in function of the local density and constructed surface shape by its neighbors then they group points that have the same characteristics. Subsequently, the result of this processing is filtered [13,14].
Approaches based on derivative products
In these approaches, the support is essentially an image produced by the interpolation and/or segmentation. In this case, the segmentation means mainly the generation of objects composed of similar pixels.
A significant number of algorithms and methods were developed to extract 3D objects, especially the buildings from the image generated from the point cloud, this image can be a height picture (DEM), intensity image, or number of return image. Among these algorithms we can mention:
The Maximum likelihood: This method is based on the DSM. Maximum likelihood is used to classify a set of points (n points) into several classes (classes m) . Maas in 1999 and later in 2005 proposed this method of classification which gives mathematically remarkable results [16,17]. Bartels and Wei have developed an approach to improve the accuracy of this kind of segmentation by introducing other information and considering the relationships between different classes . According to Blaschke this type of segmentation must be combined with other sources of information as high-resolution image since it focuses on the treatment of pixels .
The Bayesian network: The Bayesian network is another technique of image processing, it was applied to LIDAR data by Brunn and Weidner in 1997 to discriminate between buildings and vegetation on the basis of a standardized DSM, however it must have an area with a low relief and a relatively high density of points in a regular distribution .
The surface growth: The algorithm of surface growth is used to segment the point cloud, Gorte, Lee and Toni, Rottensteiner, Pu and Vosselman, Rabbani et al., consider the region growing in remote sensing as the growth surface in lasergrammetry.
First, the algorithm separates between planar and nonplanar surfaces, and then the aggregation is done by analyzing the environment of each of them depending on certain parameters such as proximity, slope and normal to the surface [21-25], Kurdi et al., used the combination of Hough transform and RANSAC (random sample consensus) for determining plans roofs.
The Fuzzy logic: Fuzzy logic is an idea that supports the possibility of belonging both at multiple classes, it is a probability of belonging to classes of objects that can appoint a “fuzzy clustering”. It determines the “forces” with which an individual belongs to different classes; this method is introduced by Tovari and Vögtle for LIDAR data .
The edge detection: Heath et al., Jiang and Bunke, Sappa and Devy have developed some algorithms for edge detection for image segmentation, but the major problem is the conversion of 3D data in 2.5 causing a huge loss of quality, precision and even data [27-29].
The distribution analysis: Some studies combine several techniques to analyze the distribution of the points cloud including the Hough transform, RANdom Sample Consensus (RANSAC). Wang and Tseng in their approach organize the point cloud in a voxel space structured in octree trees and use the criteria of coherence and proximity to the segmentation .
As also found in the literature, the algorithms that combine analysis of heights and intensity of scanned points. However the intensity image must be corrected (Song et al., Coren and Sterzia, Hofle and Pfeifer) propose the radiometric correction of image intensity [31-33], Yan et al., concluded that after correction the result of the segmentation is improved by 8% to 12% .
Bartels et al. used the skewness balancing to segment the point cloud into two classes ground and above-ground surface based on altitude [35,36]. Bao et al., analyzed the acuity coefficient (kurtosis) to highlight three classes: ground, above-ground and vegetation . Antonarikis et al., divided the study area into cells of small dimension and calculated for each cell the skewness and acuity . Bao et al. and Liu et al. have also used the two coefficients but with the addition of the intensity component to the height component analysis [39,40].
Crosilla F et al. have developed a sequential procedure which allows using alternately the most effective values ??of the intensity et al., titude to classify a point cloud .
Approaches based on the combination of LIDAR data and other sources
LIDAR data only are not sufficient, according to some researchers, hence the necessity to be combined with other data sources. Chen et al. in their study combines the topographic map and LIDAR data . Habib et al., propose the combination of image and LIDAR data to extract the buildings edges [43,44]. According to Awrangjeb et al. the integration of image and LIDAR data provides a more accurate result by combining the vertical accuracy of LIDAR data and planimetric continuity of the image [45-47].
Advantages and disadvantages of segmentation methods
Table 1 summarizes the advantages and disadvantages of methods studied.
only on the raw point
|The conservation of the original characteristics of
the point cloud (precision, location, topographical
relations); Using the first echo.
|Requires a large memory.
The process of segmentation is adapted according to the study area;
Programs that use this approach are not numerous;
Is based on the idea that the urban scene is composed just by trees and buildings.
|Approaches based on
|Ability to use known and established algorithms in
the field of digital photogrammetry and remote
Easy to handle because they are accessible
through software and / or by open source;
Fast processing and calculating
The 2D character facilitates the processing of
pixels and their neighbors.
|Loss of information caused by the resampling step. (Depending on the pitch of the DSM,
there is a pixel in DSM which contains n points raised by the LIDAR);
False data also caused by the resampling step. (You can find a pixel with wrong spatial
information caused by extrapolation, because the area in question contains no points
Shifting coordinates of LIDAR point (Resampling shifts the point to the pixel center);
The altitude of the pixel is an average value which is only a smoothing of the original
information Z. (weighted average);
Errors are accumulated after each stage of treatment.
|Most segmentation methods found in the
literature are of this family.
|Loss of the positioning accuracy of the original point.|
|Approaches Based on
the combination of
LIDAR data and other
|Use of more data giving more reliability.
Use image processing programs in most cases.
|Requires a large memory and a significant treatment time;
Is based more on DSM;
Is based on the idea that the urban scene is composed of trees and buildings;
Requires dual data source.
Table 1: Advantages and disadvantages of segmentation methods.
This paper highlighted a bibliographic study that summarizes a set of algorithms for LIDAR data segmentation in order to reveal the results found by previous research.
Analyzing all the approaches found in the literature, we find that the concept of automatic segmentation remains a field of research. So far, researchers are trying to find an algorithm that will process the LIDAR data with a maximum level of automaticity based either on the LIDAR data, derivative products, or by combining data with other data sources.
Process the DSM derived from LIDAR point cloud is equivalent to using the remote sensing technics but with a loss of data and qualities, very large researches has been done in this direction.
A limited number of algorithms have treated only the 3D point cloud, but the information extracted is limited compared with the information in the points cloud.
Each algorithm found in the literature provides remarkable results in a specific area, such as the buildings, vegetation or roads extraction, and for specific land characteristics, for example flat urban area, rural area, forested area ... etc.
Algorithm hypothesis, types of processed objects, or the nature of segmented area, all these constraints lead us to think about a process that treats the point cloud without recourse neither to interpolations neither to specific data type and extract the maximum information whatever the type of terrain.
Our vision is to develop a new process in the automatic segmentation field of LIDAR data; this process will produce a set of data layers in the form of point cloud maintaining the original accuracy of the point cloud without any interpolation, and 3D information is extracted whatever the type of terrain.
The topographical survey by technical LIDAR (Light Detection and Ranging) or “lasergrammetrie airlift” generate a cloud with a density of several points per square meter and a precision important enough, the processing of such data is therefore a crucial step and essential to make them usable.
The retrieval of information 3D in a way automatic and especially in urban area from the LIDAR data is one of the most difficult problems in computer vision. At the same time it is an important step for the implementation of several current applications that require interpretation of high level of LASER data. Therefore, there is a growing interest in this field of research in the last few years and a vast literature.
The problem addressed in this article lies in the differentiation between the sets of points which represent a layer of information defined (construction, vegetation, roads, lines, etc.), this is what we call the segmentation.
Segmenting data LIDAR returns to know at what class belongs each of the points and the isolated from the other, this article looks at the state of the art of the automatic segmentation of the cloud of points and proposes a methodology to follow to classify with a maximum degree of automaticity the said data.
Make the best use of Scientific Research and information from our 700 + peer reviewed, Open Access Journals