  Low dimensional primitive feature extraction from LiDAR point clouds (such as
planes) forms the basis of majority of LiDAR data processing tasks. A major
challenge in LiDAR data analysis arises from the irregular nature of LiDAR data
that forces practitioners to either regularize the data using some form of
gridding or utilize a triangular mesh such as triangulated irregular network
(TIN). While there have been a handful applications using LiDAR data as a
connected graph, a principled treatment of utilizing graph-theoretical approach
for LiDAR data modelling is still lacking. In this paper, we try to bridge this
gap by utilizing graphical approach for normal estimation from LiDAR point
clouds. We formulate the normal estimation problem in an optimization
framework, where we find the corresponding normal vector for each LiDAR point
by utilizing its nearest neighbors and simultaneously enforcing a graph
smoothness assumption based on point samples. This is a non-linear constrained
convex optimization problem which can then be solved using projected conjugate
gradient descent to yield an unique solution. As an enhancement to our
optimization problem, we also provide different weighted solutions based on the
dot product of the normals and Euclidean distance between the points. In order
to assess the performance of our proposed normal extraction method and
weighting strategies, we first provide a detailed analysis on repeated randomly
generated datasets with four different noise levels and four different tuning
parameters. Finally, we benchmark our proposed method against existing
state-of-the-art approaches on a large scale synthetic plane extraction
dataset. The code for the proposed approach along with the simulations and
benchmarking is available at
https://github.com/arpan-kusari/graph-plane-extraction-simulation.
