Ph.D. Theses

Range Data Analysis by Free-Space Modeling and Tensor Voting

By Bradford King
Advisor: Charles V. Stewart
December 1, 2008

This thesis presents two range data analysis methods to address challenges of modeling three-dimensional, outdoor, uncontrolled environments. We focus on scenes observed by ground-based, single-viewpoint laser-range scanners.

First, we infer free-space, the empty volume between scanner and scene, and model it with a new representation, the Free-Space Polyhedron. We use the Free- Space Polyhedron to create a change detection system, suitable for scenes scanned at multiple times from varying locations, that marks as change indicators points from any scan that lie inside the free-space of other scans. A novel spatial data structure, the Spherical Quad-Tree, efficiently tests points for presence in each of the free-space models. We organize the models globally with a Scan Index Octree to avoid loading all data simultaneously. We demonstrate the system with real data from several scenes including one observed by scans acquired over a three-year period.

Second, we make several theoretical contributions to the Tensor Voting Framework and then address practical issues of its application to range data analysis. An algebraic simplification of the voting procedure produces a closed-form tensor field that is both analytically differentiable and computationally cheaper than existing methods. We also replace the traditional vote attenuation profile with one that produces a smoother tensor field. Then, we propose a novel fine-to-coarse token selection and refinement procedure that makes Tensor Voting practical for analysis of range data. A sampling analysis determines parameters automatically for surface inference at any scale. We apply this method to extract terrain from natural scenes using a coarse-to-fine approach that spans gaps in the input caused by occlusion or missing data and adds detail where sampling is sufficient. Experiments show the method to be capable of producing desirable results on challenging cases in real scans.

Return to main PhD Theses page