Geometrically modeling 2D scattered points: a review of the potential for methodologically improving mobile laser scanning in data processing

Abstract

As a state-of-the-art mapping technology, mobile laser scanning (MLS) is increasingly applied to fields such as digital presentations of city environments. However, its application has recently met a bottleneck in data processing. It has been found that conventional methods for geometrically modeling 3D scattered points are inadequate when dealing with large volumes of MLS data. In fact, this is a challenge that has already been noted in the MLS-relevant fields, e.g. remote sensing, robot perception, and pattern recognition. A variety of algorithms under the schematic frame of analysis, modeling and synthesis (AMS) have been developed in these fields. The AMS paradigm is to first extract the implicit geometric primitives within each scan profile by geometrically modeling its 2D scattered points (GM2P). The resultant 2D geometric primitives are then integrated to restore the real 3D geometrical models. In this process, GM2P is a kernel procedure whereby a review of the GM2P algorithms is assumed to be of significance for developing new efficient algorithms for geometrically modeling 3D scattered points. This idea is supported by MLS sampling often being executed via parallel scan profiles. Indeed, the results of the literature review indicate an avenue for methodologically improving MLS in data processing.

Keywords:

• MLS
• geometrically modeling
• scattered points
• GM2P
• AMS
• scan profile

1. Introduction

1.1. Background

As a state-of-the-art mapping technology, mobile laser scanning (MLS) has developed quickly (Zampa and Conforti 2009; Graham 2010). This is demonstrated by the large amount of commercial and research-purposed MLS systems established during the past decade (Petrie 2010). These MLS systems can record the object-backscattered echoes attributed with 3D coordinates and other properties (e.g. echo intensity) (Barber, Mills, and Smith-Voysey 2008). Data samplings with such rich attributes enable MLS to characterize the geometric, radiometric and even semantic features of the targets. Moreover, MLS shows the strengths of high flexibility and high sampling density. All of these advantages have introduced MLS into many application fields such as digital city (Nebiker, Bleisch, and Christen 2010) and digital traffic (Pu et al. 2011). The representative cases can refer to previous attempts to apply MLS to urban object classification (Zhao and Shibasaki 2003), culvert investigation (Lin and Hyyppä 2010), and pole-like object recognition (Lehtomäki et al. 2010).

However, the functional roles of MLS are still far from being fully played due to a bottleneck encountered in data processing, i.e. directly manipulating hundreds of millions of laser points is complicated and time-consuming. For instance, the extraction of discrete planes from a gridded point cloud needs to iteratively traverse 34 kinds of point layouts as the possible geometric primitives (Kenmochi et al. 2008). As regards more complex geometrical structures, even modeling-oriented algorithms such as Hough transform (Décoret et al. 2003) may run into a serious problem in respect to efficiency, and efficiency-optimized random sample consensus (RANSAC) methods behave unsatisfactorily (Schnabel, Wahl, and Klein 2007). Thus, new efficient algorithms for geometrically modeling 3D point clouds, or even more efficient schematic frames at higher theoretical levels, are necessitated in MLS data processing.

1.2. Schematic frame

In order to deal with the above issue, one alternative solution at the schematic frame level is to extract geometrical models of the objects, since explicit structural features can retrieve many other types of information (Hyyppä et al. 2001). Compared to 3D scattered points, the usage of geometrical models composed of geometric primitives and parameter specifications can bring about significant savings in data storage space and data processing runtime (Biosca and Lerma 2008). In order to determine a feasible schematic frame, the peculiar characteristics of MLS need to be taken into account. The typical sampling pattern of MLS is via parallel scan profiles (Jaakkola et al. 2008). This mapping mechanism can inspire an efficient solution plan under the schematic frame of analysis, modeling and synthesis (AMS) (Bartneck and Lyons 2009). The AMS scheme is intuitively illustrated in Figure 1. The basic paradigm is to first extract all of the 2D geometric primitives by geometrically modeling 2D scattered points in each scan profile, segmented in advance according to the inherent scan profiles or artificially-defined transects (Starly et al. 2005). The ultimate aim of 3D geometrical modeling is then accomplished merely by integrating the resultant 2D geometric primitives. Actually, this kind of bottom-up strategy for object reconstruction can derive from the methods for 3D point clouds processing addressed in previous publications. For example, as in the pan local-to-global logic, building model reconstruction was fulfilled by gradual accumulation of planar surfaces (Maas and Vosselman 1999).

Figure 1. Schematic diagram of geometrically modeling 3D scattered points under the AMS frame.

In principle, the premise necessitated for supporting the application of AMS (mainly for its first step of ‘analysis’) can be easily satisfied by MLS. That is, the capacity of marking scan profile indices is possessed by most MLS systems. Theoretically, this auto-marking facilitates using a block-by-block routine for sequentially processing and even on-line processing MLS data of large volumes. Next, the kernel procedure of exercising AMS is to geometrically model 2D scattered points (GM2P) in each ‘isolated’ scan profile. When GM2P is applied, the shapes in the scan profiles still represented by relatively considerable echoes can then be characterized by simple geometric primitives. This can maintain the efficiency of MLS data processing, even though the data volume keeps growing as a result of the vehicle moving. GM2P can also provide explicit morphological units for the reconstruction of the final 3D models. However, this does not mean that geometrically modeling 2D scattered points is an easy task, because diverse shapes may be encountered. Hence, a review of the GM2P algorithms under the AMS schematic frame (referred to as the AMS-GM2P schematic frame hereafter, or AMS-GM2P for short) will be implicative for enhancing MLS-based geometrically modeling objects.

2. Review premise

2.1. Fields

With the highest relevance to MLS data processing, three typical research fields – remote sensing (RS) based on the general sense of light detection and ranging (Lidar), robot perception (RP) and pattern recognition (PR) – are included in the literature review. Relevant studies have been carried out in the PR field for quite some time, whereas studies in the RP and RS fields date back 15 and 10 years, respectively.

2.1.1. Lidar-based remote sensing

Apart from MLS, the Lidar-based remote sensing community also includes satellite-based laser scanning (Duncanson, Niemann, and Wulder 2010), airborne laser scanning (ALS) (Wulder et al. 2007) and static terrestrial laser scanning (TLS) (Lovell et al. 2011). In fact, the AMS schematic frame stressed in this study has already been noted and attempted in the ALS and TLS branches. For example, airborne Lidar with the inherent function of scan profiling has been tried out in connection with forest canopy inventories (Nelson, Parker, and Hom 2003). ALS without this function has also been used in this way, and it has been implemented by artificially extracting scan profiles from its data (Sithole and Vosselman 2006). As regards TLS, the strategy of layering point clouds, i.e. a variant mode of GM2P, has been employed to locate tree stem positions (Lovell et al. 2011).

2.1.2. Robot perception

MLS systems can be intuitively regarded as the enhanced versions of robot sensory modules. In some cases, it is even hard to distinguish between robot Lidar and MLS in terms of system configuration (Yuan, Zhao, and Zhang 2010). Thus, some methods developed for robot perception of its environments are also valid for MLS data processing, and vice versa. For example, aerospace explorations based on robots, e.g. Lunar rovers with laser rangefinder (Krotkov et al. 1999) and Mars rovers with teleoperator manoeuvre assistance (Farahani 2007), have often been tried out with MLS-based information extractions in field trials. This rule works for the GM2P algorithms as well. Moreover, the GM2P scheme has also been implemented in the field of robot perception by means of hardware settings, since many of RP-purposed laser systems are simply configured with 2D laser rangefinders for improved efficiency (Forsberg, Larsson, and Wernersson 1995; Adams et al. 2008). In other words, RP scanners each time focus only on the horizontal scan profiles of the surroundings, and many algorithms rooted in robot scans substantially belong to the GM2P schematic frame.

2.1.3. Pattern recognition

In a broader sense, the GM2P algorithms have long been exploited in pattern recognition. After all, the necessity often arises for recognizing objects represented by 2D scattered points, even involving images with targets characterized by sparse pixels. Pattern recognition has also offered a higher-level theoretical description of this kind of problems. According to Sagerer and Niemann (1997), a segmented object can be defined by its parts and their attributes and relations. The parts are the main results of decomposing an object into simpler constituents (parts here are the 2D geometrical models in the MLS scan profiles). The attributes describe some physical or geometrical properties of the parts. The relations are not attached to the parts, but describe their geometrical configurations. Hence, the segmentation of the object into parts is of key importance in context understanding. Studies about parts, attributes and relations have been carried out in many PR-related application fields, such as computer vision (Jiang and Bunke 1994), machine intelligence (Hoover et al. 1996), pattern modeling (Verbeek, Vlassis, and Kröse 2002), computer-aided design (Wu et al. 2004), and diagnostic medical imaging (Ecabert et al. 2008). A summary of the existing GM2P algorithms in the pan field of pattern recognition can offer theoretical guidance towards developing effective techniques for MLS-based object representation.

2.2. Outline

After the most relevant fields have been determined, the basic outline of this review was designed as manifested in Figure 2. For the ultimate goal of developing efficient methods for geometrically modeling 3D scattered points, particularly with MLS data characteristics taken into account, two schematic frames can be adopted – AMS and directly modeling 3D points. AMS was the focus in this study. Next, the AMS-schemed methods can be divided into two major groups according to data forms – scattered points and rastered images. Actually, rasterized imagery is also a good data form for the purpose of geometrical modeling, because numerous mature methods in digital image processing (DIP) (Gonzalez and Woods 2007) can be directly used. However, the process of rasterization may introduce some omission errors into information extraction. Thus, the original scattered points were emphasized here. Finally, the related GM2P algorithms were further reviewed according to the common routines, i.e. definition of scan profiles, extraction of geometrical primitives, and integration of 2D models into 3D space. The review work will be deployed in the triangle with the three fields and three procedures considered crosswise.

Figure 2. Global outline of this review aimed at the GM2P scheme and summary statistics of the referred works in different fields.

3. Investigation of specific algorithms

The review of specific algorithms follows the paradigm of the AMS frame, and its ‘modeling’ procedure will be further divided into two explicit steps – segmentation of scattered points in each scan profile and geometrically modeling 2D scattered points.

3.1. Definition of scan profiles

3.1.1. Inherent scan profiles

In general, inherent scan profiles are directly provided by mapping modules such as MLS systems in urban surveys (Lin and Hyyppä 2011) and 2D range finders in robot navigation (Borges and Aldon 2004). With support from hardware settings, the definition of scan profiles can be easily fulfilled in this scenario. However, the point needing to be stressed here is that different configurations for the measurement of inherent scan profiles may result in different influences on the choice of the appropriate GM2P algorithms in the following steps. This is due to the resultant scan profiles possibly representing the object structures from different points of view. For example, the Riegl VMX-250 (Riegl 2010), Roamer (Kukko et al. 2007), and Sensei (Jaakkola et al. 2010) tend to observe the objects from different view angles. Hence, the patterns of morphological clues and geometric primitives are different for the same objects, and the related GM2P algorithms need to be adapted.

3.1.2. Artificially-defined transects

The other approach to defining scan profiles is based on artificially-defined transects. Although this plan requires more effort in setting up the rules for extracting scan profiles, it does turn out to be more flexible and robust in multiple situations. Typical cases using artificially-defined transects are known to have occurred in studies on forest growth investigations. Specifically, forest growth was derived based on two artificially-drawn scan profiles in airborne Lidar data, which was actually mapped in the spiral-scanning mode (Yu et al. 2006). Another case was one where gridding of ALS scattered points by interpolation was followed by the scan profiles being manually defined for bridge detection (Sithole and Vosselman 2006). There were also some efforts involving the proposed concept of profiling Lidar (Wulder et al. 2007), wherein ‘profiling’ was defined in accordance with its function rather than its configuration. In other words, this ‘profiling’ was still artificially defined by extracting ground elevation profiles with a filtering window according to the flight transects.

3.2. Segmentation of scattered points in each scan profile

After the definition of scan profiles, the segmentation of 2D scattered points in each scan profile needs to be conducted as a preparatory step for the AMS procedure of ‘modeling’. The specific operation is to partition the 2D scattered points in each scan profile into homogeneous subsets, each of which corresponds to an explicit morphology. The resultant point subsets can facilitate extracting the embedded geometric primitives. The basic principles of segmentation here can refer to the previous works aimed at range images. However, it should be noted that the scan profiles containing 2D scattered points are different from range images in data form. Apart from the relative locations, the points in range images have other attributes such as range or echo intensity from which the basic criteria for segmentation have been derived: discontinuity and similarity. For the scan profiles discussed in the present study, similarity cannot be relied on since no other attributes are attached to its points. For example, segmentation based on watershed (Kwak et al. 2007) and edge detection (Senthilkumaran and Rajesh 2009), depending on the criterion of point property gradients, cannot be applied directly in this case. Hence, the homogeneity criteria for segmentation of the scan profiles here can only assume the discontinuity of the scattered points (namely, the distances between the scattered points) in implicit forms (e.g. continuity as a local criterion) or in parametric forms (e.g. an algebraic equation as a global criterion), as summarized by Gächter, Nguyen, and Siegwart (2006). Correspondingly, the methods available for segmentation of 2D scattered points are divided into two dominant schematic categories – primitive-independent and primitive-dependent – in terms of their relevance to the presumed geometrical primitives.

3.2.1. Primitive-independent

The algorithms of primitive-independent schematics (Table 1) can segment 2D scattered points without struggling for the potential geometrical primitives. Theoretically, the target points can be divided into multi-groups only based on the distances between them.

Table 1. Summary of the algorithms of primitive-independent schematics for segmentation.

Schematic	Principle	Algorithms	Note
Thresholding	Discontinuity	Ohlander, Price, and Reddy (1978)	Threshold value up to the histograms of the point distance
		Dietmayer, Sparbert, and Streller (2001)	Distance between two consecutive points as the criterion of point unity
Clustering	Local closeness (e.g. point distance)	Santos et al. (2003)	A breakpoint detector tuned manually
		Borges and Aldon (2004)	An adaptive breakpoint detector
		Morsdorf et al. (2004)	A K-means clustering algorithm
		Hinks et al. (2009)	An integral k-nearest neighbor (kNN) clustering algorithm
		Yuan et al. (2010)	A fuzzy clustering algorithm based on maximum entropy theory
		Fernández et al. (2010)	A distance-based convolution clustering (DCC) algorithm
Graph partitioning	Weighted and undirected graph	Zahn (1971)	Minimum spanning tree-based segmentation
		Wu and Leahy (1993)	Minimum cut
		Shi and Malik (2000)	Normalized cut
		Grady (2006)	Random walker
		Grady and Schwartz (2006)	Isoperimetric partitioning

3.2.2. Primitive-dependent

The algorithms of primitive-dependent segmentation schematics (Table 2) are often mixed with the following procedure of exerting GM2P. Particularly for iterative methods, it is often hard to set apart their implementations of segmentation and modeling. Thus, the segmentation methods of this kind here are only listed with simple descriptions, since a lot of specific cases in the next subsection still involve segmentation schematics such as region growing and split-and-merge.

Table 2. Summary of the algorithms of primitive-dependent schematics for segmentation.

Schematic	Pattern	Algorithms	Note
Region growing	Bottom-up segmentation	Shapiro and Stockman (2001)	Acquiring subsets iteratively by merging the seed regions with their adjacent components with same homogeneous properties
Split-and-merge	Top-down segmentation	Horowitz and Pavlidis (1976)	Points are split recursively into homogeneous subsets

3.3. Geometrically modeling 2D scattered points

Geometrically modeling 2D scattered points here is aimed at two common types of geometric primitives – line and curve. The latter also covers closed circles. The following reviews are divided according to these two primitives, respectively.

3.3.1. Geometrical primitive - line

For line-related point groups after primitive-independent segmentation, linear regression based on least-square fitting (Leon 2009) is the fundamental routine for acquiring their explicit line functions. However, for MLS mapping, simple linear regression is not enough, since various technical restrictions may be encountered, e.g. point groups with inconsistently-defined outliers or diverse objects with different requirements in data processing. In fact, many potential methods for tackling these special restrictions have been proposed in the referenced fields. For example, the total-least-squares algorithm (Forsyth and Ponce 2003) was assumed to compute the line parameters of a line and the covariance matrix of its inlier set. This technique can overcome the well-known bias issue of the least-squares method, which tends to put more weight on noisy and outlying points. Its equation details can refer to (Arras and Siegwart 1997), where another key idea inspired by the Hough Transform strategy is found. Specifically, the related algorithm first transforms the line extraction issue into a search problem in the model space (i.e. line parameter domain) and then executes the agglomerative hierarchical clustering (AHC) procedure (Agarwal, Alam, and Biswas 2010) to calculate the adjacent line segments. One drawback of this algorithm is that it is complex to implement. A weight linear fitting algorithm has also been proposed by Yuan, Zhao, and Zhang (2010).

Principal component analysis (PCA) (Brigitte and Rouanet 2004) is also a classical plan for handling this challenge. Based on orthogonal transformation, this approach converts a set of observations of possibly correlated variables into a set of values of uncorrelated variables (i.e. principal components). The first principal component can be extracted to delineate the possible line, and this process can be illustrated by seeking the normal vectors in crown reconstructions (Kato et al. 2009). Essentially, line-oriented modeling is not restricted only to fitting the point groups with appropriate line equations. The process of geometrical modeling sometimes also comprises the procedure of line extraction. The representative algorithms dependent on this synthesized schematic frame are presented in Table 3. In addition, there are also many variant or enhanced versions of the above methods, but they are not listed here in details. For a more comprehensive comparison of the performance of the methods listed above, reference here is made to Nguyen et al. (2005). The other details concerning their performances on line extraction in terms of environment sizes can also be found in Fernández et al. (2010).

Table 3. Summary of the seven typical categories of line extraction algorithms.

Category	Algorithms	Application cases	Note
Successive edge following (SEF)	Siadat et al. (1997)	–	The idea is that during line searching, defining a new line is restarted when the distance between two consecutive points exceeds a certain threshold value
Split-and-merge (S&M)	Pavlidis and Horowitz (1974)	Borges and Aldon (2004)	Its basic plan is to conduct the line-guided points splitting and subsets merging
Incremental algorithm (IA)	Vandorpe et al. (1996)	Borges and Aldon (2004)	A specific line-tracking (LT) algorithm is proposed in accordance to this principle
		Duda and Hart (1973)	An iterative end point fit (IEPF) algorithm is proposed: A line is constructed using the first and last scan points. Next, two subsets are created taking the most distant point as the splitting point. This procedure is repeated recursively for all the subsets until the validation criterion fails
Hough transform (HT)	Gonzalez and Woods (2007)	Pfister, Roumeliotis, and Burdick (2003)	It is brought into robotic field for extracting line from scan images
		Fernández et al. (2010)	A reduced Hough transform line tracker (REHOLT) algorithm is proposed for line modeling with DCC for line extraction
Expectation-maximization (EM)	Forsyth and Ponce (2003)	Pfister, Roumeliotis, and Burdick (2003)	EM is a probabilistic approach and is commonly used in the variable-missing problems, e.g. as a line extraction tool in computer vision and robot perception
Random sample consensus (RANSAC)	Fischler and Bolles (1981)	Forsyth and Ponce (2003)	This is a generic segmentation method popular in computer vision and can be used with many types of features once the feature models are got
		Zuliani Kenney, and Manjunath. (2005)	A multi-RANSAC is proposed for the case of multiple lines embedded in the scattered points
J-Linkage (JL)	Tolso and Fusiello (2008)	–	This algorithm is based on a tailored agglomerative clustering. It does not require prior specification of the number of models, nor does it necessitate parameters tuning.

3.3.2. Geometrical primitive - curve

The geometrical forms of curves, such as irregular curves, circles, ellipses and irregular close rings, can be fitted with specific parametric formulations. In this scenario, the highlights are to extract the embedded geometric models from the segmented point groups. Furthermore, the related formula coefficients need to be resolved.

For geometrically modeling circles and ellipses, common ellipse-fitting methods can work effectively. Several ellipse-fitting algorithms in the three review fields are listed in Table 4.

Table 4. Summary of the representative ellipse-fitting algorithms.

Field	Algorithms	Note
PR	Gander, Golub, and Strebel (1994)	A least-squares fitting algorithm for circles and ellipses
	Fitzgibbon, Pilu, and Fisher (1999)	A direct least square fitting algorithm for ellipses
	Zuliani, Kenney, and Manjunath (2005)	A multi-RANSAC fitting algorithm
	Tolso and Fusiello (2008)	A J-linkage algorithm from a synthetic perspective of curve extraction and then modeling
RP	Premebida and Nunes (2005)	A review of the relevant algorithms
	Xavier et al. (2005)	An application of locating the pole-shaped objects.
RS	Aschoff and Spiecker, 2004	An application of tree trunk modeling based on TLS
	Lin and Hyyppä (2011)	An application of crown profile modeling based on MLS
	Pitas (2000)	A Hough transformation algorithm for circle rings measured partially

As regards irregular curves and irregular close rings, their geometrical models can be obtained by exploring their principal curves (Kégl et al. 2000). In practice, principal curves are often modelled as the integrations of line segments, but this does not mean that the methods aimed at geometrical primitives of lines are enough. The determination of the lengths of individual line segments and the total number of line segments is a tough problem, far more difficult than the pure process of line fitting. To address this issue, some vector quantification techniques have been used to find the approximations to principal curves, and several representative techniques are listed in Table 5. The k-segments algorithm has been introduced into MLS data processing for crown modeling in scan profiles (Lin and Hyyppä 2011). Indeed, the scheme of principal curves has supplied an effective and flexible way for dealing with the complex distributions of 2D scattered points.

Table 5. Summary of the representative algorithms for finding principal curves.

Algorithms	Note
Kohonen (1995)	A self-organizing map (SOM) algorithm.
Bishop, Svensén, and Williams (1998)	A generative topographic mapping (GTM) algorithm
Verbeek, Vlassis, and Kröse (2002)	A k-segments algorithm
Zhang and Chen (2006)	A constraint k-segments algorithm
Verbeek, Vlassis, and Kröse (2006)	A soft k-segments algorithm

3.4. Integration of 2D models

The reports about integration of 2D geometrical models into full 3D models have proved to be few in number, since neither considerable GM2P algorithms have been developed nor have scan profiles been extensively exploited in previous studies. Some relevant works are listed as follows. The Scan Line Grouping (SGL) algorithm based on region growing has been proposed by Jiang and Bunke (1994). Its primitives are straight line segments instead of individual points. This algorithm has gained some applications in the field of mobile robotics (e.g. Natonek 1998; Leger 1999) due to its simplicity and speed. Similar algorithms for planar surfaces have been developed by Haindl and Žid (1997), and some have even been extended to curved surfaces (Jiang, Bunke, and Meier 2000; Khalifa, Moussa, and Kamel 2003). Apart from the integration of all parallel 2D models at the same time, the derived 2D models can also be iteratively fused in already existing 3D models. The algorithm of matching them can refer to Gruen and Akca (2005), and this algorithm was based on least-square fitting.

4. Discussions

4.1. Potential application scenarios

The applicability of the summarized practices following the literature review and the derived clues helpful for developing new modeling methods keep strengthening, particularly with the range of MLS applications being continuously extended. This works specifically as follows. MLS systems based on sport utility vehicles (SUVs) can cope with most plain terrains. MLS systems carried by rail-based vehicles can measure dense tree vegetation along the tracks (Mettenleiter et al. 2008). Pedal-powered, and even human-propelled, tricycles equipped with laser scanners and positioning devices can survey streets, e.g. for the purpose of compiling Google Maps (Petrie 2010). A boat-based mobile mapping system (BoMMS) with a Faro LS880 scanner can be used for monitoring river-sides (Alho et al. 2009). A sled-borne MLS system has been used for mapping the thickness of snow (Kaasalainen et al. 2011). As regards dense forests or forests in mountainous areas, these hard-to-reach places have induced researchers to construct the Sensei system possessing the hybrid functions of terrestrial MLS and low-altitude ALS (Lin, Hyyppä, and Jaakkola 2011). With light-weight laser scanners becoming increasingly more available, backpack-styled MLS systems (Ellum 2001) have also been envisaged and prototyped by the research team of these authors.

The referred solution plans are also valid for more than the targeted scenario of MLS-based object representation. In fact, they can work in many other fields, ranging from computer-aided designing (Wu et al. 2004) to diagnostic medical imaging (Ecabert et al. 2008). From the perspective of generation of 3D points, the feasible sources include Lidar (Vosselman et al. 2004) and image matching often used in aerial photogrammetry (Leberl et al. 2010) and photography based on small unmanned aerial vehicles (UAVs) (Rosnell and Honkavaara 2012). As regards the latter technique, its present-day thriving study is referred to as a comeback of traditional stereo photogrammetry (Haala 2009). These all suggest that more and more means capable of yielding 3D points are available, and thus, the algorithms sought for geometrically modeling the resultant points have more applicable fields.

These varying application projects have resulted in a huge variety of AMS-GM2P-applicable scenarios. Specifically, the environments concerned comprise forests, plains, rivers, cities, etc. The referred objects include tree stems, snow, watercourses, buildings, etc. The outer shapes suitable in this context include cylinders, planes, curve surfaces, lines, etc. The possible geometrical primitives in 2D scan profiles contain points, lines, curves, ellipses, etc. In principle, the scenarios may cover different objects, different shapes, different scales, different reflectivity, different details, etc. All of these aspects need to be considered in the processes of GM2P. Namely, for each application case, a set of analysis-synthesis rules and a group of geometric models need to be pre-determined for object representation. Attempts at introducing the plan of object based image analysis (OBIA) into the Lidar field have also been made (Blaschke and Tomljenović 2012). Overall, the potential strategies for geometrically modeling 2D scattered points are theoretically scenario-oriented or object-oriented.

4.2. Pros and cons

While one of the potential strengths of the referred AMS-GM2P scheme frame is efficiency, no such exploitations and comparisons have been conducted as yet. Actually, it is difficult to evaluate the significance of the GM2P-schemed algorithms for object modeling in terms of efficiency. The reason lies in the fact that the ‘efficiency’ derived from the GM2P operations at the schematic level is beyond the traditional concept of data processing runtime at the algorithmic level. In a specific application case with similar-sized point clouds, the runtime of an algorithm under the AMS-GM2P frame may be worse than a comparative algorithm designed directly in a 3D sense.

However, overall efficiency extending from methodology development to model output may be better. The rationale is that the AMS frame supplies a flexible measure for manipulation of scattered points, and the GM2P scheme offers a high potential for predicting the semantic shapes of objects. For example, the strategy of sub-sampling is a potential technique. That is, 2D geometrical modeling can be deployed on every few scan profiles, and the spacing of sub-sampling is determined according to the relations between the sizes of objects and the frequencies of scan profiling. Based on this technique, a multi-level modeling scheme can be established. The possible locations of the targets are initially sought by sub-sampling, and the scan profiles comprising the targets are extracted. The extracted scan profiles are then geometrically modeled in more explicit 2D modes, and 3D models can be achieved by integration of these 2D models. By this means, the overall efficiency can be dramatically improved. Hence, the contribution of reviewing the GM2P-schemed algorithms is to offer an alternative way for modeling 3D scattered points, which is an efficient solution frame for the MLS data processing community as a whole.

The second aspect for discussion is the different configurations of laser scanning systems, since they may correspond to different 2D geometrical primitives for the same object and hence different integration patterns. For example, if the scan profiles are configured perpendicular to the terrain surface, the 2D geometric primitives of lighting poles and tree stems are line segments. Then, the related 3D models are acquired by circular clustering of parallel vertical line segments. If the scan profiles cross the terrain surface with a tilt angle, the related 2D geometric primitives are open curves. The same 3D models can then be achieved by parallel clustering of the resultant tilt open curves, after which they are fitted with a cylinder. It can be seen from this comparison that the relations of parts in modeling are dependent on both the shapes of objects and the sampling modes. As regards the explicit error models in geometric primitive extraction from 2D range scans, a large number of sophisticated error models have been discussed in (Diosi and Kleeman 2003).

The third aspect for discussion is nonparallel scan profiles, often occurring at the corners of roads where vehicles change routines. Special methods for the integration of 2D geometrical models need to deal with this disadvantageous situation. Nonetheless, such scenarios need to be first detected. This is implemented by comparing the normal vectors of two adjacent scan profiles. If there is an angle between them larger than the prescribed threshold, the scan profiles need to be marked out. Then, for the associated laser points, one possible robust solution is to segment the points related with the objects and then to geometrically model them directly in a 3D sense.

5. Conclusion

This review is aimed at resolving the implicative, but complicated, challenge of retrieving the geometrical models of the objects represented by 3D scattered points, which is explosively emphasized with the rapid development of MLS and stereo photogrammetry technology. In other words, this work is helpful in the endeavour to solve the type of technical bottlenecks currently encountered in the RS community. In addition to Lidar-based remote sensing in a 3D sense, robot perception and pattern recognition are also major associated domains. It was found that one alternative schematic in common is based on the AMS-GM2P methodological frame. The following literature review did supply a great number of algorithms that can be referenced for MLS-based object modeling. Overall, this review serves as more than a summary of the GM2P-schemed approaches for inspiring and enhancing the development of new algorithms under the same theoretical frame. Furthermore, this endeavor can open up a potential avenue for methodically improving the entire MLS field in terms of object representation in practical applications.

Acknowledgements

The authors are grateful for financial support from the Academy of Finland (Project ‘Towards improved characterization of map objects’).