Quadtree-based polynomial polygon fitting

In this paper, we present a novel method for surface reconstruction with a low execution time for segmenting and representing scattered scenes accurately. The surfaces are described in a memory-efficient fashion as polynomial functions and polygons. Segmentation and parameter determination is done in one pass by using a quadtree on ordered point clouds, which results in a complexity of O(log n). This paper includes an evaluation with respect to reconstruction accuracy, segmentation precision, execution time and compression ratio of everyday indoor scenes. Our surface reconstruction algorithm outperforms comparable approaches with respect to execution time and accuracy. More importantly, the new technique handles curved shapes accurately and enables complex tasks like 3D mapping for mobile robots in an unknown environment.

Authors

• Joshua Hampp
• Richard Bormann

Keywords

• Surface reconstruction
• Polynomials
• Accuracy
• Fitting
• Surface fitting
• Image segmentation
• Complexity theory
• Polygon Fitting
• Point Cloud
• Reconstruction Accuracy
• Mobile Robot
• Compression Ratio
• Precise Segmentation
• Quadtree
• Mobile Devices
• Partial Model
• Surface Model
• Least-squares Fitting
• Singular Value Decomposition
• Taylor Series
• Indoor Environments
• Lookup Table
• Line Segment
• Depth Images
• Complex Surface
• Border Points
• Neighboring Points
• Segmentation Points
• Color Information
• Indoor Navigation
• Binary Pattern
• Image Compression
• Depth Values
• Input Point Cloud
• Surface Representation