# shapeFit: Point cloud cylinder/circle fit In TreeLS: Terrestrial Point Cloud Processing of Forest Data

## Description

Fits a 3D cylinder or 2D circle on a set of 3D points, retrieving the optimized parameters.

## Usage

  1 2 3 4 5 6 7 8 9 10 shapeFit( stem_segment = NULL, shape = "circle", algorithm = "ransac", n = 10, conf = 0.95, inliers = 0.9, n_best = 10, z_dev = 30 ) 

## Arguments

 stem_segment NULL or a LAS object with a single stem segment. When NULL returns a parameterized function to be used as input in other functions (e.g. tlsInventory). shape character, either "circle" or "cylinder". algorithm optimization method for estimating the shape's parameters. Currently available: "ransac", "irls", "nm", "qr" (circle only) ,"bf" (cylinder only). n numeric - number of points selected on every RANSAC iteration. conf numeric - confidence level. inliers numeric - expected proportion of inliers among stem segments' point cloud chunks. n_best integer - estimate optimal RANSAC parameters as the median of the n_best estimations with lowest error. z_dev numeric - maximum angle deviation for brute force cylinder estimation (bf), i.e. angle, in degrees (0-90), that a cylinder can be tilted in relation to a perfect vertival axis (Z = c(0,0,1)).

## Details

The ransac and irls methods are robust, which means they estimate the circle/cylinder parameters in a way that takes into consideration outlier effects (noise). If the input data is already noise free, the nm or qr algorithms can be used with as good reliability, while being much faster.

## Least Squares Circle Fit

The circle fit methods applied in TreeLS estimate the circle parameters (its center's XY coordinates and radius) from a pre-selected (denoised) set of points in a least squares fashion by applying either QR decompostion, used in combination with the RANSAC algorithm, or Nelder-Mead simplex optimization combined the IRLS approach.

The parameters returned by the circle fit methods are:

• X,Y: 2D circle center coordinates

• Radius: 2D circle radius, in point cloud units

• Error: model circle error from the least squares fit

• AvgHeight: average height of the stem segment's points

• N: number of points belonging to the stem segment

## Least Squares Cylinder Fit

The cylinder fit methods implemented in TreeLS estimate a 3D cylinder's axis direction and radius. The algorithm used internally to optimize the cylinder parameters is the Nelder-Mead simplex, which takes as objective function the model describing the distance from any point to a modelled cylinder's surface on a regular 3D cylinder point cloud:

\mjdeqn

D_p = |(p - q) \times a| - rDp = abs((p - q) x a) - r

where:

• Dp: distance from a point to the model cylinder's surface

• p: a point on the cylinder's surface

• q: a point on the cylinder's axis

• a: unit vector of cylinder's direction

The Nelder-Mead algorithm minimizes the sum of squared Dp from a set of points belonging to a stem segment - in the context of TreeLS.

The parameters returned by the cylinder fit methods are:

• rho,theta,phi,alpha: 3D cylinder estimated axis parameters (Liang et al. 2012)

• Radius: 3D cylinder radius, in point cloud units

• Error: model cylinder error from the least squares fit

• AvgHeight: average height of the stem segment's points

• N: number of points belonging to the stem segment

• PX,PY,PZ: absolute center positions of the stem segment points, in point cloud units (used for plotting)

## Random Sample Consensus (RANSAC) Algorithm

The RANdom SAmple Consensus algorithm is a method that relies on resampling a data set as many times as necessary to find a subset comprised of only inliers - e.g. observations belonging to a desired model. The RANSAC algorithm provides a way of estimating the necessary number of iterations necessary to fit a model using inliers only, at least once, as shown in the equation: \mjdeqnk = log(1 - p) / log(1 - w^n)k = log(1 - p) / log(1 - w^n) where:

• k: number of iterations

• p: confidence level, i.e. desired probability of success

• w: proportion of inliers expected in the full dataset

• n: number of observations sampled on every iteration

The models reiterated in TreeLS usually relate to circle or cylinder fitting over a set of 3D coordinates, selecting the best possible model through the RANSAC algorithm

## Iterative Reweighted Least Squares (IRLS) Algorithm

irls circle or cylinder estimation methods perform automatic outlier assigning through iterative reweighting with M-estimators, followed by a Nelder-Mead optimization of squared distance sums to determine the best circle/cylinder parameters for a given point cloud. The reweighting strategy used in TreeLS is based on Liang et al. (2012). The Nelder-Mead algorithm implemented in Rcpp was provided by kthohr/optim.

## Brute Force Cylinder Fit

The brute force cylinder fit approach estimates the axis rotation angles by brute force combined with 2D ransac circle fit. The coordinates of a point cloud representing a single cylinder are iteratively rotated up to a pre defined threshold, and for every iteration a circle is estimated after rotation is performed. The rotation that minimizes the circle parameters the most is used to describe the axis direction of the cylinder with the circle's radius.

The parameters returned by the brute force cylinder fit method are:

• X,Y: 2D circle center coordinates after rotation

• Radius: 3D circle radius, in point cloud units

• Error: model circle error from the RANSAC least squares fit, after rotation

• DX,DY: absolute rotation angles (in degrees) applied to the X and Y axes, respectively

• AvgHeight: average height of the stem segment's points

• N: number of points belonging to the stem segment

## References

Liang, X. et al., 2012. Automatic stem mapping using single-scan terrestrial laser scanning. IEEE Transactions on Geoscience and Remote Sensing, 50(2), pp.661–670.

Olofsson, K., Holmgren, J. & Olsson, H., 2014. Tree stem and height measurements using terrestrial laser scanning and the RANSAC algorithm. Remote Sensing, 6(5), pp.4323–4344.

Conto, T. et al., 2017. Performance of stem denoising and stem modelling algorithms on single tree point clouds from terrestrial laser scanning. Computers and Electronics in Agriculture, v. 143, p. 165-176.

## Examples

 1 2 3 4 5 6 7 8 file = system.file("extdata", "pine.laz", package="TreeLS") tls = readTLS(file) segment = filter_poi(tls, Z > 1 & Z < 2) pars = shapeFit(segment, shape='circle', algorithm='irls') segment@data %$% plot(Y ~ X, pch=20, asp=1) pars %$% points(X,Y,col='red', pch=3, cex=2) pars %\$% lines(c(X,X+Radius),c(Y,Y), col='red',lwd=2,lty=2) 

### Example output

Loading required package: data.table

Attaching package: ‘raster’

The following object is masked from ‘package:magrittr’:

extract

The following object is masked from ‘package:data.table’:

shift

Warning messages:
1: In rgl.init(initValue, onlyNULL) : RGL: unable to open X11 display
2: 'rgl.init' failed, running with 'rgl.useNULL = TRUE'.


TreeLS documentation built on Aug. 26, 2020, 5:14 p.m.