Analysis with Wavelets, Signals and Geometry

April 4-6, 2001
DIMACS Center, Rutgers University, Piscataway, NJ

Richard Gundy, Rutgers University,
Ingrid Daubechies, Princeton University,
Wil Sweldens, Bell Labs,
Guido Weiss, Washington University,
Presented under the auspices of the Special Focu on Mathematics and Foundations of Computer and Information Science



Besov, Bayes and Plato in Multiscale Image Modeling

Richard G. Baraniuk, Rice University

There currently exist two distinct paradigms for modeling
images.  In the first, images are regarded as functions
from a deterministric function space, such as a Besov
smoothness class.  In the second, images are treated
statistically as realizations of a random process.
This talk with review and indicate the links between
the leading deterministic and statistical image models,
with an emphasis on multiresolution techniques and
wavelets.  To overcome the major shortcomings of the
Besov smoothness characterization, we will develop
new statistical models based on mixtures on graphs.
To illustrate, we will discuss applications in image
estimation and segmentation.

2. Toward Sparse Multiscale Geometric Representation of Images Albert Cohen, Universite Pierre et Marie Curie In the first part of this talk, I shall review several results concerning the sparsity of image representations by wavelet basis, and their impact on practical applications such as denoising and encoding. After pointing out the inherent limitations of these representations in terms of coping with the geometry of edges, I shall present an approach - based on numerical techniques introduced in the context of shock computations - which aim to combine the simple multiscale structure of wavelet algorithms with a proper treatment of geometry.
3. Handling Irregular 3D Data in Graphics Mathieu Desbrun, University of Southern California When fast, yet robust techniques in modeling or animation are needed, adaptive sampling is highly desired to reduce the number of data to proceed while bounding the numerical errors introduced. In the case of regularly sampled data, a lot of tools (from FFT to finite differences) exists, enabling us to edit or animate virtual objects. But when those objects have mesh with arbitrary connectivity, there is a lack of mathematical foundations to deal with them. A long term goal in both animation and modeling is thus to be able to manipulate any irregular data with predictive power. In this talk, I will present some recent results on smoothing of arbitrary data (3D geometry or tensor fields), as well as on lossless compression of arbitrary meshes using single-rate or progressive encoders.
4. Vladimir Dobric, Lehigh University An Application of Wavelet Series to Brownian Motion
5. Plancherel Theory and Continuous Wavelet Transforms Hartmut Fuehr, Germany We give an overview of the connection between generalized continuous wavelet transforms -- or "coherent state transforms" defined by use of a unitary representation of a locally compact group, and the Plancherel transform of the underlying group. The approach via Plancherel measure allows to decide for an arbitrary representation whether there exists a reconstruction formula involving the Haar measure of the group. This considerable widens the scope of such transforms; in particular it allows to study non-irreducible representations. As an illystration we consider semidirect products and their quasiregular representations.
6. Wavelets on the Integers Philip Gressman, Washington University We will introduce the theory of wavelets on the integers. Our results allow us to identify a larger class of such wavelets than previously known. We will also show that natural MRA structures arise on the integers and these MRAs correspond in many cases to MRAs on the real line.
7. Hybrid Meshes Igor Guskov, Caltech Hybrid mesh is a novel multiresolution mesh structure which combines the flexibility of irregular and the simplicity of (semi)-regular meshes. I will show how to contruct hybrid meshes using both regular refinement to build smooth patches and irregular operations to allow topology changes. A user driven procedure for remeshing scanned geometry with hybrid meshes will be demonstrated. This is joint work with Andrei Khodakovsky, Peter Schroeder and Wim Sweldens.
8. Complete Interpolating Sequences for Classes of Frequency Band Limited Functions. W.R. Madych, University of Connecticut Let PWp be the classical Paley-Wiener space of entire functions of exponential type no greater than p which are square integrable on the real line IR. A real complete interpolating sequence for PWp is a bi-infinite increasing sequence of real numbers C={xn} which has the property that the interpolation problem F|x=y has a unique solution F in PWp for every square integrable sequence y = {yn}. As a sequence of sampling nodes, each such sequence X plays a role similar to that played by the integer lattice ZZ; for instance, every F in PWp can be recovered from samples of its values on C via a Lagrange type interpolation series which in the case X = ZZ reduces to the classical Whittaker cardinal series. Every complete interpolating sequence X = {xn} for PWp must necessarily satisfy a separateness condition: there is a positive constant d, whose value may vary from sequence to sequence, such that xn+1-xn ³d for all n. On the other hand it is well known that functions F in PWp can be unambiguously recovered from their values on sampling sequences which do not enjoy this condition; the nature of the data F|x however will be different. Thus the notion of complete interpolating sequence for PWp, as defined above, may be too restrictive. In this talk, in addition to supplying necessary background, we introduce an extension of this notion which is not subject to the aforementioned separateness restriction. Our method involves extending the notion of complete interpolating sequence to the class PWp¥ which consists of those functions which have a derivative of some order, not necessarily the first, in PWp Note that PWp¥ contains PWp and, in fact, is significantly larger than PWp. The corresponding class of suitable sampling sequences is also significantly larger, indeed its members need not satisfy the separateness condition mentioned above. Since functions F in PWp¥ can have polynomial growth on the real line they cannot, in general, be recovered from their values on sampling sequences X via classical Lagrange type interpolation series directly. However various summability methods can be used. In particular, if sk is the classical piecewise polynomial spline of order 2k with knots on the sampling nodes X which interpolates F on X then lim k®¥sk(x)=F(x) uniformly for all x in IR.
9. Multiplicative Network Modeling and Multifractal Estimators Rolf Riedi, Rice University Recent studines have made it clear that network traffic is multifractal in nature. Using moments of (possibly) all orders multifractal analysis traces and goes beyond the second order approximations of linear processes. Multifractal structures are naturally tied to multiplicative frameworks. Indeed, a simple stochastic traffice model based on the Haar wavelet demonstrates the effectiveness of a multiplicative approach and its superiority over the typical additive schemes, both in multifractal statistics capturing burstiness as well as in network relevant metrics. After making these points this talk explores novel multiscale multiplicative models and elaborates on wavelet based estimators of multifractal parameters.
10. Multi-Resolution Storage of Optimally Encoded, Adaptively Accessed Data Robert Sharpley, University of South Carolina Many commercial and military applications have the goal of generating fused databases of images (photographic, infrared, SAR, stereo) and higher dimensional data which may be used for autonomous navigation, data registration, and the fast query and retrieval of information. For example in the area of remote sensing, databases of images, digital elevation models and associated cultural data for specified regions have been developed and archived, but are not currently amenable to efficient data navigation or registration. We discuss how the recently developed theory of Cohen, Dahmen, DeVore and Daubechies for optimal entropy tree encoders may be used to address such problems. The class of scalable algorithms resulting from this theory yield optimal (in an information-theoretic sense), progressive, universal, locally refinable encoders for purposes of compression, storage and transmission of multiply resolved data.
11. Digital Geometry Compression Wim Sweldens, Bell Labs Due to rapid progress in scanning technology, digital geometry is becoming the fourth wave of digital multimedia after audio, images, and video. Last year, a two billion triangle model of Michelangelo's David with sub millimeter accuracy was built. As a result, digital geometry compression has established itself as a new branch of data compression. Traditionally one observes that meshes consist both of geometric information (vertex positions) and connectivity or graph information. Compression methods for both geometry and connectivity have been proposed. In this work, we observe that meshes actually consist of three distrinct components; geometry, parameter, and connectivity information. More importantly, the latter two do not contribute to the reduction of error in a rate-distortion setting. We show that using so-called semi-regular meshes, parameter and connectivity information can be eliminated. Combined with wavelet transforms, zerotree coding, and subdivision, we build a progressive geometry compression algorithm which improves the standard methods by 12dB.
12. Regular Symmetric Wavelets in Higher Dimensions Yang Wang, Georgia Tech In this talk, I will discuss the design of orthogonal filters in higher dimensions from filters in the one dimension. The technique is powerful, easy to implement and can be easily modified for designing other filters such as biorthogonal filters or tight frame filters. We use the technique to construct smooth symmetric wavelets in the higher dimensions.
13. The Mathematical Theory of Wavelets Guido Weiss, Washington University The definitions and properties of "wavelets" and related notions that are used by researchers in this area are varied. There are continuous, discrete, singly generated, multi and several other types of wavelets. They are generated by dyadic and more general matricial dilations and by several different types of lattices. There are :analyzing" and "reconstructing" wavelets, as in the phi and psi-transform theory and in the case of bi-orthogonal wavelets. Other operations, such as modulations, can replace the role of dilations (as in the case of Gabor systems). There are group-theoretic approaches for obtaining "wavelet- like" reproducing forumulae. There are several ways of unifying these different ways of developing this theory. This unification not only leads to a better understanding but it also provides many new ways for the construction af wavelet (and related) systems.
14. Affine Groups Admitting Continuous Wavelets and their Characterization Edward Wilson, Washington University We consider affine groups on R^n. The most general such group G is the semi-direct product of a topological subgroup D of GL(n,R) and the translation group R^n. D is said to be admissible if there exists a function on R^n satisfying a generalization of the Calderon reproducing formula relative to G with any such function said to be a continuous wavelet relative to G. We are able to give a nearly complete characterization of the admissible groups. If D is admissible, then G cannot be unimodular and the stability subgroup for the transpose action of D must be compact at almost every point of R^n. Conversely, if G is non-unimodular and at almost every point, there is a compact epsilson stabilizer for the action of D, then D is admissible. These conditions are easily checked in practice and give rise to numerous examples of both admissible and non-admissible groups. The examples suggest that the compact epsilon stabilizer property may be necessary as well as sufficient for admissibility.
15. Subdivision on Irregular Meshes Denis Zorin, NYU The theory of stationary subdivision, closely related to wavelet theory, is well developed and numerous results are estabilshed on smoothness and approximation properties of subdivision schemes. However, most of these results were obtained for subdivision of regular grids and in functional setting. However, the main practical application of subdivision is construction of smooth surfaces on irregular meshes. This makes analysis of geometric properties in irregular setting particularly important. In this talk I review the known facts subdivision surfaces: necessary and sufficient conditions for tangent plane continuity and CÙk continuity, regularity of surfaces and approximation properties of subdivision bases. Finally, I will discuss open problems and directions for future research.

Previous: Participation
Next: Registration
Workshop Index
DIMACS Homepage
Contacting the Center
Document last modified on March 29, 2001.