Optimal Scan Locations for Terrain Mapping

Oil Spill Survey, First – of – its – Kind with Drone
January 13, 2020

The main objective of this study is the development of a simulation and optimization method for wide-area terrain mapping with terrestrial laser scanning (TLS). The problem can be stated as follows: given a prior digital surface model (DSM) of a region of interest (e.g. from airborne lidar or structure-from-motion photogrammetry), determine the minimum number of scan locations required to seamlessly scan the terrain in the region for a given scanner range and angular field-of-view (FOV). An optimization method for measurement setup is developed using multiple viewshed analysis and simulated annealing (SA) constrained by the system performance characteristics and survey specifications. The method is evaluated at a sediment and erosion control facility with hilly terrain by comparing random scan locations versus optimized three to six scan locations. Statistical results illustrate that average visibility for random sampling increases gradually with scan locations. However, random sampling clearly underperforms in terms of scan visibility relative to five or six optimized scan locations with an average visibility of 100%. Similar patterns in optimized scan locations demonstrate that certain terrain morphometry at the study site is an essential factor for TLS survey design. Finally, an optimized solution is compared to a brute-force manual solution for determining four scan locations for conducting surveys at the study site. Results show the effectiveness of the optimization method for selecting combinations of scan locations that enable more efficient TLS survey coverage over a wider terrain area compared to manual selection. Furthermore, results demonstrate the adaptability of the method to take into consideration different scan parameters and survey conditions, such as pre-determined scan locations that may be required (e.g. a survey control monument).

1. Introduction

Landscapes undergo constant evolution through natural erosions and anthropogenic events (Dean and Dalrymple 2002; Starek et al. 2011). It is more important nowadays than ever to effectively monitor the highly variable evolution processes and understand their nature in order to support decision-making with respect to human settlement, environmental conservation, ground and air transportation and so forth. Studies of landscape morphology using three-dimensional (3D) terrain surface products from satellite remote sensing have been extensively investigated, mostly at regional and global scales given relatively large pixel spacing and limited vertical accuracy (Mukul et al. 2017; Yap et al. 2018).

The advent of light detection and ranging (lidar) technology mounted in airborne and terrestrial platforms has made it possible to accurately and rapidly monitor dynamic terrain evolution (Mitasova et al. 2010). Compared to airborne lidar, terrestrial lidar, more commonly referred to as terrestrial laser scanning (TLS), is advantageous for very high-resolution mapping of localized terrain providing sub-cm scanning resolutions and a few mm point measurement accuracies (Starek et al. 2011). TLS has been widely adopted to examine landform dynamics (Feagin et al. 2012; Guisado-Pintado, Jackson, and Rogers 2019) and ecological resilience at coastal zones (Nguyen et al. 2018; Owers, Rogers, and Woodroffe 2018). 3D TLS surveying and visualization techniques have also been established for the documentation and preservation of cultural heritages (Lezzerini et al. 2016; Liang et al. 2018). Studies have also leveraged repeated surveys for change detection of landslide movement (Barbarella, Fiani, and Lugli 2015; Prokop and Panholzer 2009) and crop growth monitoring (Hoffmeister et al. 2016).

Investigations have disclosed that the overall scanning and mapping performance varies dependent upon quantity and distribution of scan locations (Heritage et al. 2009; Olsen et al. 2009). Different from airborne lidar for which survey planning methodologies have been well documented for choosing appropriate parameters such as flight height, overlap, and sampling rate (Renslow 2012), best practices for planning TLS surveys have not reached agreement owing to the complexity of topographical variability as well as the heterogeneous nature of TLS surveys associated with variable point density (O’Banion and Olsen 2018). Due to limited TLS scanning ranges and occlusion, multiple scans may be required to merge together to form a seamless model of the scene. Jia and Lichti (2017) introduced a method for optimization of indoor TLS survey networks by constraining the problem based on scan location and incidence angles. Similar to the work here, heuristic algorithms were employed to find optimal solutions, but it was designed for scanning of wall segments, not natural terrain. To advance TLS surveying practices in the outdoors and achieve a digital elevation model (DEM) of specified resolution and completeness, O’Banion and Olsen (2018) developed a TLS acquisition planning tool to assist in estimating the minimum required quantity of scans and scanning resolution. While the study aimed to balance surveying efficiency and desired quality specifications for adequate DEM completeness, optimized scan planning and placement over a specific topography remained unclear. For contiguous mapping of terrain over wide areas (> a few hundred metres horizontally), TLS survey planning poses several obstacles that must be overcome. The selected measurement set-up, sampling resolution, and other survey design factors as well as inherent system characteristics will influence the measurement capabilities and efficiency of repeat-coverage surveys for monitoring terrain change.

To develop an effective planning method for terrain monitoring with TLS, this research investigates the influence of scan configuration on surface coverage capability with the goal of optimizing TLS data acquisition while minimizing information loss. This problem can be formulated as a constrained multiple viewshed analysis, which falls under the broader domain of combinatorial optimization (e.g. travelling salesman problem). The multiple viewshed problem runs on the order of O(nm ) for nm where O is the notation to express the time complexity of an algorithm, n is the number of candidate view locations and m is the number of viewpoints. Such problems quickly become computationally intractable. For example, n = 3000 candidates and m = 5 viewpoints has a runtime on the order of about 2 × 1017. Prior research efforts have developed efficient multiple viewshed algorithms for geospatial modelling applications (Andrade et al. 2011; Franklin 2000; O’Sullivan and Turner 2001). For optimizing TLS surveys over wide-terrain areas (i.e. multiple scan positions are necessary to provide contiguous coverage), researchers have shown that simulated annealing (SA) among other heuristic algorithms can produce adequate results in terms of multiple viewshed performance and computational efficiency (Kim, Rana, and Wise 2004; Adewole, Otubamowo, and Egunjobi 2012; Yu et al. 2016).

As a substantive extension to a method first introduced in a previously published conference poster (Starek, Mitasova, and Harmon 2010), this paper develops a simulation and optimization method for TLS survey design to map terrain based on multiple viewshed analysis and SA constrained by scanner characteristics and survey specifications. The terrestrial lidar scan positioning problem is unique relative to other multiple viewshed problems because of the constraints imposed by scanner performance, terrain geometry, and needs for certain amounts of scan overlap and spacing to enable effective registration.

2. Materials and methods

2.1. Study site and survey data

Managed and maintained by North Carolina State University, the study was carried out at an experimental watershed within the 450 m × 450 m Sediment and Erosion Control Research and Education Facility (SECREF). Centred at 35° 44.2ʹ N, 78° 40.7ʹ W within the Piedmont region’s eastern boundary of North Carolina (Figure 1), the SECREF comprises a catchment for two sub-watersheds. Dense grassland is the dominant land cover type in the field, but tillage and other agricultural practices are sometimes performed (Starek et al. 2011). The experimental site is mainly used for the research of soil erosion processes and landscape modification triggered by significant overland flow events.

Figure 1. (a) Experimental watershed site with an orthophotograph draped over an airborne lidar-derived 1 m-resolution 450 m × 450 m DSM. The field consists mostly of dense grassland, but it is subjected to anthropogenic modification by tillage and other agricultural practices. Shaded box represents survey area of focus that includes major elevation variability of the bare earth terrain. The star located lower right is the main drainage outlet. (b) 1 m-resolution DSM of terrain and land cover generated from airborne lidar data used to perform viewshed analysis. The field was subjected to rill erosion along the hillsides during heavy rain events and gully erosion within a drainage basin formed by the confluence of runoff from two main hillslopes.Display full size

Efforts have been made on developing geodetic techniques for rapid data acquisition and processing to accurately measure the terrain (Mitasova, Mitas, and Harmon 2005; Mitasova et al. 2010; Starek et al. 2011). TLS data of watershed terrain were acquired with an in-house Leica ScanStation 2 scanner (Table 1 and Figure 2) that is capable of capturing cm-level changes in terrain and vegetation over the SECREF study site (Leica-geosystems 2018). Because the area is relatively large (450 m × 450 m), multiple scans must be acquired to generate seamless and high-spatial resolution coverage of the region.

Table 1. Specification of the terrestrial scanner and survey.

CSVDisplay Table

Figure 2. Instrumentation. (a) Leica ScanStation 2 scanner. (b) Image mosaic of the study area acquired from Leica ScanStation 2 high-resolution digital camera at a particular scan position. (c) Point cloud generated from two co-registered scans covering an approximately 200 m × 200 m flat area. The upper right corner is a forest. (d) Example point cloud overlaid on the image mosaic shown in (b) coloured by elevation.Display full size

In order to facilitate multiple viewshed analysis to optimize scan locations under study, airborne lidar data from a 2001 North Carolina Floodplain Mapping Programme (NCFMP) were employed, and its first-return point cloud was interpolated to generate a 1 m a priori digital surface model (DSM) of the terrain and land cover elevation (Figure 1). Although the focus here is on optimizing TLS scan positions for mapping terrain (e.g. generating DEMs of the topography), a DSM of the scene is requisite input for TLS viewshed analysis to account for scan occlusion due to trees, buildings, or other features that may impact survey design. If the region of interest consists of terrain only, then the a priori DSM in this context will be equivalent to a DEM of the ground surface (often called a bare-earth DEM or digital terrain model (DTM)).

2.2. Multiple scan location optimization

In this study, the problem to be solved can be stated as follows: for a given scanner configuration (particularly scanner range, angular field of view, and height) and a priori DSM of the survey area (e.g. from airborne lidar), identify m scan locations (viewpoints) that optimize the percentage of n pixels that are visible in the model as expressed in the following cost function (Kim, Rana, and Wise 2004): max(C(v))=∑mi=1∑nj=1vij

(1)

where m represents the number of scan points, n depicts the number of pixels in the grid, v denotes viewshed indicator at the location indexed by i and j, and C(v) is defined as cumulative viewshed that shows combined coverage of all viewsheds with varying degrees of overlapping. In the a priori DSM, the viewshed indicator v in Equation (1) is determined by a laser scanner’s line of sight (LOS) that is calculated by performing LOS analysis from the scanner location to each pixel within a given distance. Specifically, a viewshed indicator v, which is associated with a specific scanner location A and a pixel point B, is defined as (2)

where P is any pixel point between A and B, θA,B depicts the elevation angle from A to B, and θP depicts the elevation angle from A to P. The cost function Equation (1) is subject to 0≤ ∑mi=1vij ≤m for j=1,2,⋯,n(3) 0≤ ∑nj=1vij ≤n for i=1,2,⋯,m(4) 0≤ ∑mi=1∑nj=1vij ≤mn

(5)

Equation (3) explains that a particular pixel can be observed by some or even all viewpoints given a terrain geometry. Similarly, as stated in Equation (4), a laser scanner can see the whole terrain surface with maximum visibility if it is set up at the optimal location. Based on Equations (3–4), Equation (5) indicates the maximum theoretical cumulative viewshed that the cost function Equation (1) can achieve.

Furthermore, the TLS positioning problem is unique relative to other multiple viewshed problems because of the constraints on scanner performance, terrain geometry, scanner spacing distance, and the potential need for certain amounts of scan overlap to enable effective registration. Table 2 lists practical constraints that complement Equations (3–5) to determine whether an area represented by the a priori DSM is visible from a respective TLS scan location. Figure 3 further illustrates the defined scan constraints in this study.

Table 2. Scan constraint parameters for multiple viewshed analysis used in the study.

CSVDisplay Table

Figure 3. Illustration of defined scan constraints. (a) An orthophotograph demonstrating all possible scan locations (red dots) given a scan location spacing of 5 m at the SECREF. All the possible scan locations are within the survey area of focus represented by the shaded box in Figure 1 (a). A scan at a particular location (cyan dot) can reach up to 150 m, which covers the entire yellow zone. The black polygons in (a) represent local sub-watersheds delineation at the study site. (b) The Leica ScanStation 2 system scanning all directions horizontally at a scan height of 1.6 m above ground.Display full size

The goal is to optimize per cent coverage of a TLS survey given m scan locations and a respective set of scan constraints as specified in Table 2 for an input a priori DSM. The listed parameters are scanner dependent and tuneable based upon TLS survey specifications. A conservative scan range of 150 m was used instead of the scanner’s reported range of 300 m (see Table 1) to account for reduction in effective range due to lower surface albedo over the vegetated terrain, and reduction in point density extending radially away from the scanner. For this specific study site and TLS, scans were typically acquired with a horizontal stepping angle of 1 × 10−3 rad. This equates to 15 cm point spacing at 150 m radius away from the scanner. In practice, scans were performed at regular spacing intervals to ensure that the average point density (spacing) within a contiguously mapped region was sufficient for creating decimetre resolution DEMs. By setting a 150 m range for viewshed computation, this ensures that any area of the terrain represented by a set of DSM grid cells viewable from a respective scan location will have, in theory, a 15 cm or less point spacing based on the stepping angle above. The scanner height (Table 2) was set to 1.6 m to reflect the tripod height typically used for operating the scanner in the field. A full 360° field-of-view (FOV) was enforced to provide full scanner coverage.

Adjustment of the scan location spacing (Table 2) must take into consideration a performance tradeoff between per cent coverage and scan-to-scan overlap. A relatively larger scan spacing helps maintain better per cent coverage in general (assuming the same number of m candidate scan positions) while reducing scan overlap causing sparser point cloud density, and vice versa when reducing scan spacing. In this study, compromise has been made and 5 m scan location spacing was selected to account for point cloud density to assist in registration of neighbouring clouds beyond pursuing maximum per cent coverage. The scan spacing also dictates the number of candidate scan locations that are examined as explained further below.

2.3. SA optimization approach

SA is a heuristic algorithm that simulates the physical annealing process to find the global optimum of a given cost function on an iterative basis. It can deal with arbitrary systems with high nonlinearity and complex constraints. Given a discrete search space, SA allows the search process to occasionally proceed in an unfavourable direction, allowing the algorithm to likely escape from local extrema and reach the global optimum.

In this study, as illustrated in Figure 4, the annealing procedure is implemented as a pair of nested loops following the procedure first outlined in (Liu, Kao, and Wang 1994). The search is started by defining initial controlling parameters: temperature, T, cooling ratio, R, inner loop control, L, frozen ratio, F r, and threshold of acceptance rate, P th. Then a randomized solution X0=[(x01,y01) (x02,y02) ⋯ (x0m,y0m)]T

(6)

Figure 4. Flowchart of optimizing multiple scan locations based on the SA algorithm. The inner loop of the algorithm where the temperature is fixed is included in dashed rectangle with cyan background.Display full size

is generated, where (x0i,y0i) represents initial horizontal coordinates before iterations at scan location i and i∈ [1,2,⋯,m]

. In an inner loop where temperature is fixed, a neighbouring solution X of X 0 that decreases the energy is accepted. On the other hand, the algorithm also accepts bad solutions according to the Metropolis’ criterion in order not to converge locally (Metropolis et al. 1953). The inner loop is the core of the annealing procedure, and the iteration time, L, is proportional to the neighbourhood size for candidate scan locations and a user-defined sample space parameter, S (see Table 3). Acceptance moves during the inner loop procedure are incrementally counted and used to compute the fraction of acceptance moves, P, by dividing the total number of accepted moves by the iteration time, L. When the inner loop exits, the temperature is then decreased in the outer loop based on the threshold of acceptance rate, P th, as follows (Figure 4). If the fraction of acceptance moves, P, at the current temperature is larger than P th, the temperature is considered to be too high, and the temperature is divided by 2 following a binary search pattern. Else, if the fraction of acceptance moves, P, of a temperature is less than or equal to P th, the temperature is reduced slowly using the cooling ratio, R.

Table 3. Annealing controlling parameters.

CSVDisplay Table

As the annealing procedure evolves, the process accepts less bad solutions at each temperature until at very low temperature the algorithm converges to an optimized solution and reaches a frozen state (i.e. no further improvement in the cost is likely). Exit criterion is governed by the user-defined frozen ratio, F r, and a counter. The counter is incremented by one each time the run length at a temperature has been reached for which the percentage of accepted moves is less than or equal to F r, and is reset to 0 each time the percentage of accepted moves of a temperature is larger than F r. When the counter reaches a value of 5, the process is considered to be frozen (Liu, Kao, and Wang 1994).

Table 3 summarizes annealing controlling parameters and values used in this study. Tuning of the user-defined control parameters for a given problem are generally done through empirical design by evaluating various combinations of parameter settings on two key factors: solution quality and run time. SA performance is often influenced by initial temperature T(0) and cooling ratio R (Baños et al. 2013). Starting with very high initial temperatures and a larger cooling rate allows longer and slower cooling, respectively, at the expense of increased computational time. In this work, a very high initial temperature value of 1 × 106 was evaluated but it was found that a lower temperature at 1 × 104 provided similar solution quality with less computational time. Studies have shown that a larger R, S, or P th or a smaller F r can yield a better solution (a smaller percentage above the best-found solution) at the cost of more run time (Liu, Kao, and Wang 1994; Baños et al. 2013). Hence, some trade-off must be chosen between the solution quality and the run time. This work tested a small set of recommended values based on empirical results determined in prior studies (Liu, Kao, and Wang 1994; Schneider and Kirkpatrick 2006; Saruhan 2014). Values that provided a good solution performance at a reasonable computational expense were adopted and are shown in Table 3 for R, S, P th, and F r.

It is also worth noting that the value of parameter n is not an inherent SA parameter but is dependent on the resolution, spatial extent of the DSM, and scan location spacing. Increasing the scan position spacing decreases the number of available candidate scan locations (viewpoints), which stem from the set of a priori DSM grid cell locations. For example, a scan location spacing of 0 m implies all grid cells are available as candidate scan locations whereas a spacing of 10 m implies every 10th grid cell location is used as a candidate scan location (assuming a 1 m resolution DSM as used here). For this study, 5 m spacing was implemented by regularly sampling every 5th grid cell in the DSM within a rectangular extent defined around the primary area of interest (see Figure 1(a)). Zones/cells of the DSM representing forested land cover or buildings were excluded as candidate viewpoints. However, if one desired to include a scan location on top of a building, such as on a flat roof, the position could be included from the DSM. The selected 5 m scan location spacing used in this study resulted in a relatively large number of candidate viewpoints (n = 3074). As shown in Table 3, this value is used to compute the size of neighbourhood, N s, for candidate scan locations, which is dependent on the number of scan locations, m. Inner loop control, L, is then defined proportional to N s and the user-defined sample space control parameter, S.

3. Results

3.1. Cumulative viewsheds and scan locations

Before showing cumulative viewsheds and the associated scan locations via SA optimization, it is of value to display how viewsheds from different locations can vary due to terrain. Individual viewsheds were computed at all of the n possible viewpoints using open-source GRASS GIS software (GRASS Development Team 2018). As an example, three different scanner placement points at the SECREF watershed under study are visualized in Figure 5. The green dots in Figures 5(a-b) denote scanner locations, and LOS viewshed areas are delineated in blue. Figure 5(c) shows an example viewshed overlaid on a shaded-relief DSM of the study area (scan location is identified as a cross-hatch). It is suggested that a substantial difference of viewshed coverage can be achieved dependent on scan location, scanner specifications, and DSM complexity.

Figure 5. Individual viewsheds at three different locations at the SECREF watershed under study overlaid on an aerial image of the site, i.e. (a) and (b), and a shaded relief of the DSM (c). The polygons in (a) and (b) represent local sub-watersheds delineation at the study site. The green dots denote scanner locations, and LOS viewshed areas are depicted in blue. The lower half of the study site, separated by the dashed lines in (a) and (b), is a focus area for erosion and runoff assessment.Display full size

Cumulative viewshed results examining optimal placement for m = 3, 4, and 5 scan locations are presented in Figuress 6(a-c). Results show combined coverage of all viewsheds with varying degrees of overlapping. The cyan dots depict actual scanner locations optimized via SA processing, and a circled scanning area centred on each cyan dot location can be observed. The relatively dark colour in the survey area of focus suggests multiple overlaps. It is obvious that having five scan locations provides more complete coverage in general than that of only three or four locations in the study case. Furthermore, having five scan locations enables more degrees of overlapping for favourable point cloud density.

Figure 6. Cumulative viewshed results and scan locations obtained from SA at the survey area of focus as shown in Figure 1(a). Figure 6 shows the nadir view of cumulative viewshed and scan locations (i.e. cyan dots) for optimized scan locations m = 3, 4, and 5, respectively. The areas with darker colour indicate more scan overlap.Display full size

To demonstrate the effectiveness of the developed method, SA algorithm was executed independently 10 times against random scan locations for scenarios of m = 3, 4, 5, and 6, respectively. Figure 7 shows the average visibility computed from solutions obtained from 10 executions between random sampling and SA for each of the = 3 to 6 scenarios. The statistical results illustrate that average visibility for random sampling increases gradually with scan locations. However, random sampling clearly underperforms SA in terms of scan visibility given the constraints discussed in Section 2.2. In addition, an average visibility of 100% can be achieved when m = 5 or 6, meaning that the developed method can stably cover the whole survey area under study in each of the algorithm executions. That being said, we will not be able to benefit from a larger m in terms of scan visibility, unless more point cloud overlap is desired. Furthermore, the results reveal that the majority of selected scan locations are located along ridgelines between those scenarios (Figure 8). The similarity in the topographical pattern of the scan locations demonstrates that terrain morphometry (here ridgelines) tends to be an essential factor for the optimization design of survey locations using cost function Equation (1).

Figure 7. Average visibility for SA against random sampling for optimized scan locations m = 3, 4, 5, and 6, respectively. The total number of pixels reaches up to 76,007. SA enables high viewshed visibility even with only three scan locations for the study area. The viewshed visibility becomes saturated when m = 5, whereas random sampling only achieves approximately 63%.Display full size

Figure 8. Display of scan locations on a 3D model at the survey area of focus as shown in Figure 1(a). Figure 8 shows the oblique view of SA selected scan locations overlaid on a DEM for m = 4, 5, and 6, respectively. The majority of selected scan locations are located along ridgelines.Display full size

3.2. Practical application for terrain modelling with TLS

A series of 32 individual viewsheds were created from DSM grid cell locations manually distributed at roughly equal intervals within the lower half of the study site (Figure 9(a)). Some locations were pre-defined locations used for repeat TLS surveying at the study site based on the needs to survey control and scan-to-scan registration distances. Other locations targeted ridgelines and other higher elevation vantage points. Denser spacing along the roadway at the bottom was due to ease of accessibility. The viewsheds were constrained by the scanner values shown in Table 2 except for the max range was set to 200 m and scan spacing was based on the manual gridding process described above. Figure 9(b) shows an example viewshed computed for scan position 9. This location was a pre-determined scan location with a geodetic control mark utilized for each TLS survey conducted at the study site.

Figure 9. (a) Shows the distribution of 32 manually selected TLS scan locations for evaluating individual viewsheds within the lower half of the study site (dashed line). (b) Shows a viewshed computed from scan location 9, which was a pre-determined scan location with a geodetic control mark utilized for each survey conducted at the study site.Display full size

A cumulative viewshed result generated from four scan locations was then selected manually using a ‘brute force’ approach. Three scan locations in addition to scan position 9 were selected based on manual inspection of viewsheds by comparing their overlap to ensure sufficient coverage for the lower half of the study site. Figure 10(a) shows the cumulative viewshed result generated from the four scan locations selected manually using the ‘brute force’ approach. This type of manual evaluation process is tedious, inefficient, does not provide any type of near-optimal performance guarantee, and limited in practicality for TLS survey design. As observed in Figure 10(a), coverage in the lower half of the study site was sufficient but the upper half of the study site was largely uncovered. It is also important to mention that scan position 9 discussed above is labelled position 1 in the figure.

Figure 10. (a) Cumulative viewshed generated from four scan locations based on manual selection. Scan position 1 is the same pre-defined scan location (formerly called position 9) as shown in Figure 9 and discussed in the text above. (b) Cumulative viewshed generated from three optimized scan locations and pre-determined scan position 1. The polygons represent local sub-watersheds delineated at the study site. The lower half of the study site, separated by the dashed line, is a focus area for erosion and runoff assessment. (b) provides a substantially higher cumulative viewshed coverage than (a) by using the same number of scan locations (m = 4).Display full size

To evaluate the effectiveness of the developed optimization approach, a solution was run for m = 4 scan locations constrained by the values shown in Table 2 except for a scanner range of 200 m. One of the positions was set to scan position 9 so only three newly ‘optimized’ scan locations were determined. Figure 10(b) shows the cumulative viewshed result of the three optimized scan locations plus scan position 9 (shown as position 1 in the figure). It is worth noting that the lower half of the study site was the primary focus of TLS surveys for erosion and runoff assessment. While the manual approach only selected scan locations within the lower half of the study site, the optimization approach was permitted to search any possible locations within the upper half to highlight the advantage of the optimization strategy over manual selection with a possibly smaller number of scans to achieve comparable viewshed within the same area. When comparing to the manual selection result (Figure 10(a)), the three optimized locations plus scan position 1 provide a cumulative viewshed with nearly identical coverage in the lower half of study site and, furthermore, cover a substantial amount of area in the upper half. Examining Figure 10(b) in more detail, scan position 3 is located along a ridge line, which makes sense given the higher vantage point, and interestingly, scan position 2 is located nearby to the manually determined scan position 2 but at a slightly higher vantage point (Figure 10(a)). Comparing to the manual selection process, which provided less scan coverage for the same number of scan locations, results show that the developed optimization method is effective at determining combinations of scan locations for wide-area terrain surveying with TLS. Furthermore, results show that the developed method is adaptable and can take into consideration pre-determined scan locations that may be desired for terrain monitoring, such as a permanent survey control monument.

As an example of the optimized locations used in practice, repeat TLS surveys were conducted roughly one month apart at the study site. For each survey date, three TLS scans were conducted at optimized scan locations 2 and 3 and pre-determined position 1 (Figure 10(b)). DEMs of the exposed terrain and field cover were then generated from the TLS surveys at 0.2 m resolution using the regularized spline under tension spatial interpolation routine (v.surf.rst) within GRASS GIS (Mitasova, Mitas, and Harmon 2005). Figure 11(a) shows the 1 m airborne lidar DSM. Figure 11(b) shows the 0.2 m resolution DEMs for the two TLS surveys for a portion of the field (red box in Figure 11(a)) generated from the m = 3 scan locations. As observed, very fine-scale details of tillage, vegetation, and subtle changes in land cover and terrain can be observed across the approximately one month span of the survey.

Figure 11. (a) 1 m resolution airborne lidar DSM shown as a grey-scale shaded relief. The red box shows the portion of the field covered by the TLS-derived DEMs. (b) 0.2 m resolution TLS-derived DEMs (land cover objects removed minus the grassy vegetation) collected at the study site back in November and December 2009 shown as coloured shaded reliefs. The surveys were conducted from m = 3 scan locations, two of which were based on optimized locations. The DEMs show detailed and subtle changes in the field’s topography and grassland cover over the roughly 1-month duration.Display full size

4. Discussion and conclusion

In this paper, an optimization method for terrain mapping with TLS was introduced using multiple viewshed analysis and SA. Experimentation was based on TLS surveys conducted at a watershed maintained by North Carolina State University. Given a prior DSM and survey specifications, viewsheds were computed for each scan location candidate to determine visibility. SA algorithm was performed to solve for an optimal solution in which the number and locations of viewpoints required to seamlessly scan the region based on TLS specifications were identified. The results suggested that the developed method could be a very useful and powerful tool for characterizing data acquisition capabilities for a given laser scanner, number of scans, and terrain scene enabling more efficient survey design. Comparison to brute-force selection results demonstrated that the developed method can enable efficient survey design given laser scanner capabilities and terrain scene information. In addition, the developed method has the potential to be used with extensions beyond scan positioning. For example, the developed method can be applied to simulate scanner performance in complex terrain and land cover. However, several considerations related to the scan location optimization method need to be discussed and are summarized below.

First, like many heuristic algorithms, SA requires delicate tuning of the parameters to account for overall performance in each study case. The precision of the parameter values, particularly temperature-decreasing strategy and iteration times within the inner loop, used in implementation can have a significant effect upon the quality of optimization results. Regrettably, accurate determination of SA parameters is still an open-ended problem. There is no single solution or recommendation as to how to select each one of them and it is often problem specific. Experimental design and analytical methods (e.g. Liu, Kao, and Wang 1994; Frausto-Solis et al. 2007; Baños et al. 2013) have been performed to assist tuning the parameters and are worth considering to refine the developed optimization method. As explained in the methods section, this work took advantage of prior empirical work on evaluating SA parameter sensitivity to define parameter values.

Second, scanner dependent constraints such as the scan range, scan height, and FOV must be correctly identified from TLS specifications and programmed before implementing the introduced optimization method. Selection of the scan location spacing is a performance balance between scan-to-scan overlap and per cent coverage. In theory, a scan location spacing of zero fully releases the spacing constraint between two survey locations. In this study, 5 m scan location spacing was selected to account for point cloud density beyond pursuing maximum per cent coverage while ensuring a sufficient number of candidate viewpoints. A greater scan spacing (e.g. 10 m) can be considered should the surveys aim for further improved per cent coverage at the expense of reduced candidate selections. Selection of scan location spacing also depends on geomorphometry of the terrain. Surveying a topographically homogeneous terrain may be achievable with a relatively large spacing (e.g. 100 m) and low number of candidate scan positions, whereas highly varying and undulating terrain with land cover will require, in general, searching through a much larger candidate space and more combined viewpoints for continuous coverage. Other possible constraints such as scan angle relative to the terrain, maximum scan location separation, accessibility, and travel cost can also be imposed on the main cost function to develop a more robust solution.

In addition, tradeoff between the DSM pixel resolution and the time engaged needs to be balanced. For the purposes of this study, the a priori DSM utilized was set at 1 m, which was based on the average point density of the airborne lidar data set utilized to generate the DSM. It represented the most spatially detailed terrain model of the scene available at the time of the study, and as such, the effect of DSM resolution on the simulation results was not examined. In theory, increasing the resolution of the input DSM, assuming it is accurate, will capture more spatial detail of the terrain and occluding land cover. In return, this should result in a more realistic solution of TLS scan coverage for a given number of m scan positions by the developed method. However, a solution with higher DSM pixel resolution over the same area requires a greater number of candidate view locations, which may dramatically increase run time.

The time complexity of SA varies and will depend upon the exact nature of the problem, parameterization settings, and implementation method (Kim, Rana, and Wise 2004). Although some studies attempted to estimate theoretical time complexities for a given SA implementation and problem, run times are generally evaluated empirically. For instance, the SA implementation used in this work was adapted from the method first introduced by Liu, Kao, and Wang (1994) to solve location-allocation problems, which is analogous to the multiple viewshed problem. Their study reported that five scan locations (= 5) with a low number of candidate scan locations (n = 20) resulted in a run time of 70 s. However, if n = 100 without changing the m value, the run time escalated to 1320 s. While their article was published 26 years ago with outdated central processing unit (CPU) capability, this same trend on computational load holds. In modern times, a small number of n is prohibitively impossible for most survey practices given the detailed and growing resolutions of input DSMs for viewshed computation, such as from airborne lidar. This higher resolution is desirable. In our study case, n = 3074 based on the 5 m location spacing for a 1 m DSM. At 1 m spacing using all available DSM grid cells, this would result in n = 76,007 possible viewpoint candidates. Squeezing the location spacing can further increase the number of candidate locations, but run time must be significantly compromised to allow for results to be obtained from highly favourable resolutions.

Finally, this study selected SA as the heuristic algorithm for solving the multiple viewshed problem because studies have shown it to produce adequate results among other heuristic algorithms in terms of multiple viewshed performance and computational efficiency (Kim, Rana, and Wise 2004; Adewole, Otubamowo, and Egunjobi 2012; Yu et al. 2016). However, there are numerous alternative heuristic algorithms, including more recent variants of SA, for solving combinatorial optimization problems like the multiple viewshed problem. One well-known alternative is the genetic algorithm (GA). Several studies have compared the performance of SA and GA implementations and results show that SA can consistently converge faster to an optimal solution, but in terms of solution quality, GA outperforms SA under many circumstances (Adewole, Otubamowo, and Egunjobi 2012; Jia and Lichti 2017; Kerr and Mullen 2019). In general, both heuristics have good searching capabilities; however, GA enables the evaluation of numerous solutions at each stage in the search based on the population size whereas SA evaluates only a single candidate at each stage (Jia and Lichti 2017). Therefore, GA as a search algorithm provides both exploration and exploitation capabilities whereas SA is biased towards exploitation only (Chen, Xudiera, and Montgomery 2012). This is advantageous for problems with more than one optimal solution and can potentially be advantageous for improving the solution quality of TLS simulation and viewshed optimization. Other factors to consider are the ability to effectively tune the parameters for a given algorithm and tradeoffs in performance gain versus computational load. The optimization framework presented here was developed in Matlab with viewshed generation performed by GRASS GIS and is easily adaptable to other heuristic methods including GA.

Future work will focus on modifying the optimization routine for achieving adequate solution quality by assessing different heuristic algorithms including genetic algorithms while maintaining low computational load and formulating more constraints to better account for scan location and registration geometry.

Originally posted at https://www.tandfonline.com/doi/full/10.1080/01431161.2020.1752952

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.