Partial Procedural Geometric Model Fitting for Point Clouds

Zongliang Zhang, Jonathan Li, Yulan Guo, Yangbin Lin, Ming Cheng, Cheng WangarXiv 2016 · arXiv

Abstract

Inverse Procedural Modeling (IPM) aims to discover the rules and parameters that generate a model matching a target shape. However, real-world point clouds from LiDAR or laser scanners are often incomplete, featuring occlusions and noise that confound traditional similarity metrics. This paper proposes a novel framework for Partial Procedural Geometric Model Fitting (PPGMF). The core of the approach is the Weighted Mean Measure (WMM), a similarity metric designed for partial rigid matching. Combined with a Markov chain Monte Carlo (MCMC) optimization strategy and a coarse-to-fine early rejection technique, the method robustly fits arbitrary procedural models to messy, real-world geometric data.

Introduction

The task of geometric model fitting involves finding a set of procedural parameters (e.g., the number of floors or window dimensions in a building grammar) that best approximate an input point cloud. While established for complete shapes, this process often fails when applied to "non-complete" data. Real-world scans are rarely perfect; they suffer from missing regions due to occlusions or extra clutter from the environment.

Existing metrics like the Symmetric Hausdorff Distance (SHD) or Voxel Difference (VD) require two-way comparisons that break down when the model and the target only partially overlap. To address this, the authors introduce a pipeline that prioritizes one-sided similarity and geometric measures to handle the inherent incompleteness of laser-scanned data.

Methodology

Weighted Mean Measure (WMM)

The primary contribution is the Weighted Mean Measure (WMM). Unlike SHD, which computes distances in both directions, WMM leverages the mathematical insight that two models are identical if the one-sided distance from the generated model to the query point cloud is zero and their intrinsic geometric measures (such as surface area) are equal.

For partial matching, the WMM divides the procedural model into sub-regions and applies an exponential decay weight based on their distance to the query points. This allows the metric to naturally ignore parts of the model that fall into voids or missing data areas of the point cloud, focusing only on the overlapping regions.

Optimization and Early Rejection

Because procedural grammars create a non-differentiable parameter space, the authors employ the Metropolis-Hastings algorithm for MCMC optimization. To handle the high computational cost of comparing dense models to large point clouds, they introduce a coarse-to-fine sampling strategy. By initially sampling the proposed model sparsely, the system can "fail fast" and reject poor candidates early, significantly reducing the total number of distance calculations required.

Key Results

The proposed method was evaluated on synthetic shapes, CGA building grammars, and real-world mobile laser scanner data.

Key findings include:

  • Robustness: WMM was the only metric tested that correctly identified ground-truth parameters for partially overlapping and noisy point clouds.
  • Efficiency: The coarse-to-fine early rejection strategy provided an approximate 3x speedup in the optimization process without compromising the accuracy of the fit.
  • Flexibility: The algorithm successfully handled variable-length parameter sets, such as determining the correct number of floors in a building before optimizing the dimensions of individual windows.

Conclusion and Future Work

While the PPGMF framework represents a significant step forward in handling incomplete data, it faces challenges with the "curse of dimensionality" as the number of procedural parameters grows. Additionally, while the method handles missing data well, "corrupted holes"—regions where occlusions contain undesired reflection points—require specialized handling, such as the Squared Mean Measure (SMM). Future work may involve integrating deep learning to guide the MCMC search or improving preprocessing to filter out background noise more effectively.

Summary updated

Abstract

Geometric model fitting is a fundamental task in computer graphics and computer vision. However, most geometric model fitting methods are unable to fit an arbitrary geometric model (e.g. a surface with holes) to incomplete data, due to that the similarity metrics used in these methods are unable to measure the rigid partial similarity between arbitrary models. This paper hence proposes a novel rigid geometric similarity metric, which is able to measure both the full similarity and the partial similarity between arbitrary geometric models. The proposed metric enables us to perform partial procedural geometric model fitting (PPGMF). The task of PPGMF is to search a procedural geometric model space for the model rigidly similar to a query of non-complete point set. Models in the procedural model space are generated according to a set of parametric modeling rules. A typical query is a point cloud. PPGMF is very useful as it can be used to fit arbitrary geometric models to non-complete (incomplete, over-complete or hybrid-complete) point cloud data. For example, most laser scanning data is non-complete due to occlusion. Our PPGMF method uses Markov chain Monte Carlo technique to optimize the proposed similarity metric over the model space. To accelerate the optimization process, the method also employs a novel coarse-to-fine model dividing strategy to reject dissimilar models in advance. Our method has been demonstrated on a variety of geometric models and non-complete data. Experimental results show that the PPGMF method based on the proposed metric is able to fit non-complete data, while the method based on other metrics is unable. It is also shown that our method can be accelerated by several times via early rejection.
BibTeX
@misc{zhang2016partial,
  author = {Zongliang Zhang and Jonathan Li and Yulan Guo and Yangbin Lin and Ming Cheng and Cheng Wang},
  title = {{Partial Procedural Geometric Model Fitting for Point Clouds}},
  year = {2016},
  eprint = {1610.04936},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1610.04936},
}
Figure