Share Email Print

Proceedings Paper

Minimax optimal level set estimation
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper Abstract

Tree-structured partitions provide a natural framework for rapid and accurate extraction of level sets of a multivariate function f from noisy data. In general, a level set S is the set on which f exceeds some critical value (e.g. S = {x : f(x) ≥ γ}). Boundaries of such sets typically constitute manifolds embedded in the high-dimensional observation space. The identification of these boundaries is an important theoretical problem with applications for digital elevation maps, medical imaging, and pattern recognition. Because set identification is intrinsically simpler than function denoising or estimation, explicit set extraction methods can achieve higher accuracy than more indirect approaches (such as extracting a set of interest from an estimate of the function). The trees underlying our method are constructed by minimizing a complexity regularized data-fitting term over a family of dyadic partitions. Using this framework, problems such as simultaneous estimation of multiple (non-intersecting) level lines of a function can be readily solved from both a theoretical and practical perspective. Our method automatically adapts to spatially varying regularity of both the boundary of the level set and the function underlying the data. Level set extraction using multiresolution trees can be implemented in near linear time and specifically aims to minimize an error metric sensitive to both the error in the location of the level set and the distance of the function from the critical level. Translation invariant "voting-over-shifts" set estimates can also be computed rapidly using an algorithm based on the undecimated wavelet transform.

Paper Details

Date Published: 21 September 2005
PDF: 15 pages
Proc. SPIE 5914, Wavelets XI, 59141C (21 September 2005); doi: 10.1117/12.617905
Show Author Affiliations
Rebecca M. Willett, Univ. of Wisconsin, Madison (United States)
Robert D. Nowak, Univ. of Wisconsin, Madison (United States)

Published in SPIE Proceedings Vol. 5914:
Wavelets XI
Manos Papadakis; Andrew F. Laine; Michael A. Unser, Editor(s)

© SPIE. Terms of Use
Back to Top
Sign in to read the full article
Create a free SPIE account to get access to
premium articles and original research
Forgot your username?