Minimax Optimal Level-Set Estimation
Authors:
- R. M. WillettRWR. M. Willett
- R. D. NowakRNR. D. Nowak
- 19 November 2007
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Image Processing
- Vol. 16 (12) , 2965-2979
Abstract
This paper describes a new methodology and associated theoretical analysis for rapid and accurate extraction of level sets of a multivariate function from noisy data. The identification of the boundaries of such sets is an important theoretical problem with applications for digital elevation maps, medical imaging, and pattern recognition. This problem is significantly different from classical segmentation because level-set boundaries may not correspond to singularities or edges in the underlying function; as a result, segmentation methods which rely upon detecting boundaries would be potentially ineffective in this regime. This issue is addressed in this paper through a novel error metric sensitive to both the error in the location of the level-set estimate and the deviation of the function from the critical level. Hoeffding's inequality is used to derive a novel regularization term that is distinctly different from regularization methods used in conventional image denoising settings. Building upon this foundation, it is possible to derive error performance bounds for the proposed estimator and demonstrate that it exhibits near minimax optimal error decay rates for large classes of level-set problems. The proposed method automatically adapts to the spatially varying regularity of both the boundary of the level set and the underlying function.Keywords
This publication has 17 references indexed in Scilit:
- Morse Description and Geometric Encoding of Digital Elevation MapsIEEE Transactions on Image Processing, 2004
- Habitat monitoring with sensor networksCommunications of the ACM, 2004
- Multiscale likelihood analysis and complexity penalized estimationThe Annals of Statistics, 2004
- Topology preserving level set method for geometric deformable modelsIEEE Transactions on Pattern Analysis and Machine Intelligence, 2003
- Platelets: a multiscale approach for recovering edges and surfaces in photon-limited medical imagingIEEE Transactions on Medical Imaging, 2003
- Comparison of Methods for Image Analysis on cDNA Microarray DataJournal of Computational and Graphical Statistics, 2002
- Active contours without edgesIEEE Transactions on Image Processing, 2001
- On nonparametric estimation of density level setsThe Annals of Statistics, 1997
- Nonparametric Estimation of Regression Level SetsStatistics, 1997
- Asymptotical Minimax Recovery of Sets with Smooth BoundariesThe Annals of Statistics, 1995