Global Optimization for Shape Fitting
- 1 June 2007
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10636919,p. 1-8
Abstract
We propose a global optimization framework for 3D shape reconstruction from sparse noisy 3D measurements frequently encountered in range scanning, sparse feature-based stereo, and shape-from-X. In contrast to earlier local or banded optimization methods for shape fitting, we compute global optimum in the whole volume removing dependence on initial guess and sensitivity to numerous local minima. Our global method is based on two main ideas. First, we suggest a new regularization functional with a data alignment term that maximizes the number of (weakly-oriented) data points contained by a surface while allowing for some measurement errors. Second, we propose a touch-expand algorithm for finding a minimum cut on a huge 3D grid using an automatically adjusted band. This overcomes prohibitively high memory cost of graph cuts when computing globally optimal surfaces at high-resolution. Our results for sparse or incomplete 3D data from laser scanning and passive multi-view stereo are robust to noise, outliers, missing parts, and varying sampling density.Keywords
This publication has 14 references indexed in Scilit:
- Global Optimization for Shape Fitting2007
- What metrics can be approximated by geo-cuts, or global optimization of length/area and flux2005
- A multilevel banded graph cuts method for fast image segmentation2005
- An experimental comparison of min-cut/max- flow algorithms for energy minimization in visionIEEE Transactions on Pattern Analysis and Machine Intelligence, 2004
- Regularized Laplacian Zero Crossings as Optimal Edge IntegratorsInternational Journal of Computer Vision, 2003
- Surface Recovery from 3D Point Data Using a Combined Parametric and Geometric Flow ApproachLecture Notes in Computer Science, 2003
- Computing geodesics and minimal surfaces via graph cuts2003
- Flux maximizing geometric flowsIEEE Transactions on Pattern Analysis and Machine Intelligence, 2002
- Quasi-Dense Reconstruction from Image Sequence2002
- A Level-Set Approach to 3D Reconstruction from Range DataInternational Journal of Computer Vision, 1998