  In recent years new application areas have emerged in which one aims to
capture the geometry of objects by means of three-dimensional point clouds.
Often the obtained data consist of a dense sampling of the object's surface,
containing many redundant 3D points. These unnecessary data samples lead to
high computational effort in subsequent processing steps. Thus, point cloud
sparsification or compression is often applied as a preprocessing step. The two
standard methods to compress dense 3D point clouds are random subsampling and
approximation schemes based on hierarchical tree structures, e.g., octree
representations. However, both approaches give little flexibility for adjusting
point cloud compression based on a-priori knowledge on the geometry of the
scanned object. Furthermore, these methods lead to suboptimal approximations if
the 3D point cloud data is prone to noise. In this paper we propose a
variational method defined on finite weighted graphs, which allows to sparsify
a given 3D point cloud while giving the flexibility to control the appearance
of the resulting approximation based on the chosen regularization functional.
The main contribution in this paper is a novel coarse-to-fine optimization
scheme for point cloud sparsification, inspired by the efficiency of the
recently proposed Cut Pursuit algorithm for total variation denoising. This
strategy gives a substantial speed up in computing sparse point clouds compared
to a direct application on all points as done in previous works and renders
variational methods now applicable for this task. We compare different settings
for our point cloud sparsification method both on unperturbed as well as noisy
3D point cloud data.
