A complex equiangular tight frame (ETF) is a tight frame consisting of N unit vectors in C^d whose absolute inner products are identical. One may view complex ETFs as a natural geometric generalization of an orthonormal basis. Numerical evidence suggests that these objects do not arise for most pairs (d, N). The goal of this paper is to develop conditions on (d, N) under which complex ETFs can exist. In particular, this work concentrates on the class of harmonic ETFs, in which the components of the frame vectors are roots of unity. In this case, it is possible to leverage field theory to obtain stringent restrictions on the possible values for (d, N).

We show how to improve the properties of a Hilbert space frame by projecting it onto a subspace of the Hilbert space. For example, for any frame on a n-dimensional Hilbert space, there is an orthogonal projection onto a subspace of dimension n/2 (if n is even) or (n+1)/2 (if n is odd) so that the projection of the frame becomes a tight frame.

The central topic of this paper is the linear, redundant encoding of vectors using frames for the purpose of loss-insensitive data transmission. Our goal is to minimize the reconstruction error when frame coefficients are accidentally erased. Two-uniform frames are known to be optimal for handling up to two erasures, in the sense that they minimize the largest Euclidean error norm when up to two frame coefficients are set to zero. Here, we consider the case when an arbitrary number of the frame coefficients of a vector is lost. We derive general error bounds and apply these to concrete examples. We show that among the 227 known equivalence classes of two-uniform (36,15)-frames arising from Hadamard matrices, there are 5 that give smallest error bounds for up to 8 erasures.

Genetic image analysis is an interdisciplinary area, which combines microscope image processing techniques with the use of biochemical probes for the detection of genetic aberrations responsible for cancers and genetic diseases. Recent years have witnessed parallel and significant progress in both image processing and genetics. On one hand, revolutionary multiscale wavelet techniques have been developed in signal processing and applied mathematics in the last decade, providing sophisticated tools for genetic image analysis. On the other hand, reaping the fruit of genome sequencing, high resolution genetic probes have been developed to facilitate accurate detection of subtle and cryptic genetic aberrations. In the meantime, however, they bring about computational challenges for image analysis. In this paper, we review the fruitful interaction between wavelets and genetic imaging. We show how wavelets offer a perfect tool to address a variety of chromosome image analysis problems. In fact, the same word "subband" has been used in the nomenclature of cytogenetics to describe the multiresolution banding structure of the chromosome, even before its appearance in the wavelet literature. The application of wavelets to chromosome analysis holds great promise in addressing several computational challenges in genetics. A variety of real world examples such as the chromosome image enhancement, compression, registration and classification will be demonstrated. These examples are drawn from fluorescence in situ hybridization (FISH) and microarray (gene chip) imaging experiments, which indicate the impact of wavelets on the diagnosis, treatments and prognosis of cancers and genetic diseases.

The excess of a sequence in a Hilbert space H is the greatest number of elements that can be removed yet leave a set with the same closed span. {Forumlae available in paper}

We present some preliminary results of constructions of biorthogonal wavelets and associated filterbanks with optimality using a tool of pseudoframes for subspaces (PFFS). PFFS extends the theory of frames in that pseudoframe sequences need not reside within the subspace of interests. The flexibility so introduced proves favorably in the construction of biorthogonal wavelets. While past constructions pioneered by Cohen, Daubechies, and Feauveau can be reproduced precisely, results of additional optimalities are also obtained. Some preliminary examples are reported.

With the availability of new confocal laser scanning microscopes, fast biological processes, such as the blood flow in living organisms at early stages of the embryonic development, can be observed with unprecedented time resolution. When the object under study has a periodic motion, e.g. a beating embryonic heart, the imaging capabilities can be extended to retrieve 4D data. We acquire nongated slice-sequences at increasing depth and retrospectively synchronize them to build dynamic 3D volumes. Here, we present a synchronization procedure based on the temporal correlation of wavelet features. The method is designed to handle large data sets and to minimize the influence of artifacts that are frequent in fluorescence imaging techniques such as bleaching, nonuniform contrast, and photon-related noise.

Two-dimensional phase modulation is currently the basic model used in the interpretation of fringe patterns that contain displacement information, moire, holographic interferometry, speckle techniques. Another way to look to these two-dimensional signals is to consider them as frequency modulated signals. This alternative interpretation has practical implications similar to those that exist in radio engineering for handling frequency modulated signals. Utilizing this model it is possible to obtain frequency information by using the energy approach introduced by Ville in 1944. A natural complementary tool of this process is the wavelet methodology. The use of wavelet makes it possible to obtain the local values of the frequency in a one or two dimensional domain without the need of previous phase retrieval and differentiation. Furthermore from the properties of wavelets it is also possible to obtain at the same time the phase of the signal with the advantage of a better noise removal capabilities and the possibility of developing simpler algorithms for phase unwrapping due to the availability of the derivative of the phase.

This paper describes feasibility study of temporal phase analysis techniques using wavelet transform. In electronic speckle pattern interferometry (ESPI), a series of speckle patterns is captured during the deformation or vibration of the test specimen. The intensity variation on each pixel is analyzed along time axis. Phase values are evaluated point by point using complex Morlet wavelet transform. To demonstrate the validity of the proposed method, two experiments based on ESPI are conducted. These include instantaneous velocity and displacement measurement on continuous deformed objects; and absolute displacement measurement on vibrating objects using temporal carrier technique. Compared to temporal Fourier transform, wavelet analysis detects the optimized instantaneous frequency and performs an adaptive band-pass filtering of the measured signal, thus limits the influence of noise sources and increases the resolution of measurement significantly. It was observed that continuous wavelet transform (CWT) on each pixel generates a smoother spatial displacement distribution at different instants compared to a Fourier transform. The maximum displacement fluctuation due to noise is around 0.04 μm in Fourier transform, but only 0.02 μm in wavelet analysis. The wavelet transform proposed in this paper demonstrates a high potential for robust processing of continuous image sequences. The deep exploration on wavelet phase analysis techniques will broaden the applications in optical and non-destructive testing field.

The approximate behavior of wavelets as differential operators is often considered as one of their most fundamental properties. In this paper, we investigate how we can further improve on the wavelet's behavior as differentiator. In particular, we propose semi-orthogonal differential wavelets. The semi-orthogonality condition ensures that wavelet spaces are mutually orthogonal. The operator, hidden within the wavelet, can be chosen as a generalized differential operator ∂^γ_τ, for a γ-th order derivative with shift τ. Both order of derivation and shift can be chosen fractional. Our design leads us naturally to select the fractional B-splines as scaling functions. By putting the differential wavelet in the perspective of a derivative of a smoothing function, we find that signal singularities are compactly characterized by at most two local extrema of the wavelet coefficients in each subband. This property could be beneficial for signal analysis using wavelet bases. We show that this wavelet transform can be efficiently implemented using FFTs.

In this work we attempt to analize the structure of the classes of deficient spline functions, that is, the ones generated by traslations on the integers of the truncated power functions. Since these classes are correlated with multiresolution structures, the main pourpose of this presentation is to design vector scaling functions, with minimal support. For this, we do not apply Fourier techniques, but elemental properties of the truncated power functions. The double-scale or refinement relationship is demonstrated again from the autosimilarity property of these functions.

We use a comprehensive set of non-redundant orthogonal wavelet transforms and apply a denoising method called SUREshrink in each individual wavelet subband to denoise images corrupted by additive Gaussian white noise. We show that, for various images and a wide range of input noise levels, the orthogonal fractional (α, τ)-B-splines give the best peak signal-to-noise ratio (PSNR), as compared to standard wavelet bases (Daubechies wavelets, symlets and coiflets). Moreover, the selection of the best set (α, τ) can be performed on the MSE estimate (SURE) itself, not on the actual MSE (Oracle). Finally, the use of complex-valued fractional B-splines leads to even more significant improvements; they also outperform the complex Daubechies wavelets.

We build wavelet-like functions based on a parametrized family of pseudo-differential operators L_v^→ that satisfy some admissibility and scalability conditions. The shifts of the generalized B-splines, which are localized versions of the Green function of L_v^→, generate a family of L-spline spaces. These spaces have the approximation order equal to the order of the underlying operator. A sequence of embedded spaces is obtained by choosing a dyadic scale progression a=2ⁱ. The consecutive inclusion of the spaces yields the refinement equation, where the scaling filter depends on scale. The generalized L-wavelets are then constructed as basis functions for the orthogonal complements of spline spaces. The vanishing moment property of conventional wavelets is generalized to the vanishing null space element property. In spite of the scale dependence of the filters, the wavelet decomposition can be performed using an adapted version of Mallat's filterbank algorithm.

A fundamental issue of speech is that when different individuals enunciate the same perceived sound, the corresponding spectra are different, but since we perceive them to be the same, there must have a commonality that the ear extracts to recognize the same perceived sound. In previous publications we have established this commonality and have argued that the "spectra of sounds made by different individuals and perceived to be the same can be transformed into each other by a universal warping function". We call the warping function the speech scale and in previous works we have obtained it experimentally from actual speech. In this paper we give the mathematical equation that allows one to obtain the transformation function so that the transformation results in identical warped spectra except for a translation factor.

As is well known, wavelet filterbanks in general do not allow for shift invariance due to the downsampling operation. In this paper we discuss the design of a tight frame symmetric filterbank {h0, h1, h2, h3}, with the requirement that h2 and h1 be identical within a shift by one sample, or we seek h2 (n) = h1(n-1). This results in the wavelets ψ1 and ψ2 related as ψ2(t) = ψ1(t - 1/2).

In this paper, we present 3D image fusion using digital holography. We demonstrate experimentally that through image fusion technique using multi-resolution wavelet decomposition it is possible to increase details and contrast of the 3D reconstructed computational holographic images obtained by multi-wavelengths digital holograms.

In-line digital holography conciles the applicative interest of a simple optical set-up with the speed, low cost and potential of digital reconstruction. We address the twin-image problem that arises in holography due to the lack of phase information in intensity measurements. This problem is of great importance in in-line holography where spatial elimination of the twin-image cannot be carried out as in off-axis holography. Applications in digital holography of particle fields greatly depend on its suppression to reach greater particle concentrations, keeping a sufficient signal to noise ratio in reconstructed images. We describe in this paper methods to improve numerically the reconstructed images by twin-image reduction.

We study the continuous and semi-discrete wavelet transform applied to functions with values in Lebesgue spaces.

If a signal x is known to have a sparse representation with respect to a frame, the signal can be estimated from a noise-corrupted observation y by finding the best sparse approximation to y. The ability to remove noise in this manner depends on the frame being designed to efficiently represent the signal while it inefficiently represents the noise. This paper analyzes the mean squared error (MSE) of this denoising scheme and the probability that the estimate has the same sparsity pattern as the original signal. Analyses are for dictionaries generated randomly according to a spherically-symmetric distribution. Easily-computed approximations for the probability of selecting the correct dictionary element and the MSE are given. In the limit of large dimension, these approximations have simple forms. The asymptotic expressions reveal a critical input signal-to-noise ratio (SNR) for signal recovery.

Chirps arise in many signal processing applications, and have been extensively studied, especially in the case where chirps are regarded as functions of the real-line or of the integers. However, less attention has been paid to study of chirps over finite cyclic groups. We discuss the basic properties of such chirps, including a way in which they may be used to construct finite tight frames.

In this paper we study a notion of density for subsets of R² called accumulative density, which is similar to the density for sequences in the unit disc developed by Seip. Along the way we derive some new properties of Beurling density. Finally, we prove that the accumulative density and the Beurling density coincide.

The principle of complementarity lies at the heart of quantum mechanics. In finite dimensional quantum systems this principle is captured by pairs of observables which are given by mutually unbiased bases (MUBs). Two orthonormal bases B and C of C^d are mutually unbiased if |<b|c>|² = 1/d holds for all vectors b ∈ B and c ∈ C. This implies that whenever we are given a vector from one of these bases and perform a measurement with respect to any other of the bases, then there is no information gained from this measurement. A basic question about MUBs is how many of them can be found in a given dimension d. While constructions of maximal sets of d+1 such bases are known for system of prime power dimension d, it is unknown whether this bound can be achieved for any non-prime power dimension. We review the known constructions of MUBs and demonstrate that maximal sets of MUBs come with a rich combinatorial structure by showing that they actually are the same objects as the complex projective 2-designs with angle set {0,1/d}. Furthermore, we address the problem of constructing positive operator-valued measures (POVMs) in finite dimension d consisting of d² operators of rank one which have an inner product equal to uniform or very close to uniform. This is motivated by the related question of constructing symmetric informationally complete POVMs (SIC-POVMs) for which the inner products are perfectly uniform. We also give a simple proof of the fact that symmetric informationally complete POVMs are complex projective 2-designs with angle set {1/(d+1)}. Moreover, we show that MUBs and SIC-POVMs form uniform tight frames in C^d.

The Morphological Component Analysis (MCA) is a a new method which allows us to separate features contained in an image when these features present different morphological aspects. We show that MCA can be very useful for decomposing images into texture and piecewise smooth (cartoon) parts or for inpainting applications. We extend MCA to a multichannel MCA (MMCA) for analyzing multispectral data and present a range of examples which illustrates the results.

Analyzing data mapped to the sphere as may occur in a range of applications in geophysics, medical imaging or astrophysics, requires specific tools. This paper describes new multiscale decompositions for spherical images namely the isotropic undecimated wavelet transform, the ridgelet transform and the curvelet transform each of which is invertible. Several applications are described. We show how these transforms can be used in denoising and especially in a Combined Filtering Method, which uses both the wavelet and the curvelet transforms, thus benefiting from the advantages of both transforms. An application to component separation from multichannel data mapped to the sphere is also described where we take advantage of the spatiospectral localization on the sphere provided by the spherical wavelet functions.

A widespread problem in the applied sciences is to recover an object of interest from a limited number of measurements. Recently, a series of exciting results have shown that it is possible to recover sparse (or approximately sparse) signals with high accuracy from a surprisingly small number of such measurements. The recovery procedure consists of solving a tractable convex program. Moreover, the procedure is robust to measurement error; adding a perturbation of size ε to the measurements will not induce a recovery error of more than a small constant times ε. In this paper, we will briefly overview these results, describe how stable recovery via convex optimization can be implemented in an efficient manner, and present some numerical results illustrating the practicality of the procedure.

We present two-dimensional filter banks with directional vanishing moments. The directional-vanishing-moment condition is crucial for the regularity of directional filter banks. However, it is a challenging task to design orthogonal filter banks with directional vanishing moments. Due to the lack of multidimensional factorization theorems, traditional one-dimensional methods cannot be extended to higher dimensional cases. Kovacevic and Vetterli investigated the design of two-dimensional orthogonal filter banks and proposed a set of closed-form solutions called the lattice structure, where the polyphase matrix of the filter bank is characterized with a set of rotation parameters. Orthogonal filter banks with lattice structures have simple implementation. We propose a method of designing orthogonal filter banks with directional vanishing moments based on this lattice structure. The constraint of directional vanishing moments is imposed on the rotation parameters. We find the solutions of rotation parameters have special structure. Based on this structure, we find the closed-form solution for orthogonal filter banks with directional vanishing moments.

In this paper we describe a new class of multidimensional representation systems, called shearlets. They are obtained by applying the actions of dilation, shear transformation and translation to a fixed function, and exhibit the geometric and mathematical properties, e.g., directionality, elongated shapes, scales, oscillations, recently advocated by many authors for sparse image processing applications. These systems can be studied within the framework of a generalized multiresolution analysis. This approach leads to a recursive algorithm for the implementation of these systems, that generalizes the classical cascade algorithm.

In this paper we discuss recent developments on design tools and methods for multidimensional filter banks in the context of directional multiresolution representations. Due to the inherent non-separability of the filters and the lack of multi-dimensional factorization tools, one generally has to overcome factorization by indirect methods. One such method is the mapping technique. In the context of contourlets we review methods for designing filters with directional vanishing moments (DVM). The DVM property is crucial in guaranteeing the non-linear approximation efficacy of contourlets. Our approach allows for easy design of two-channel linear-phase filter banks with DVM of any order. Next we study the design via mapping of nonsubsampled filter banks. Our methodology allows for a fast implementation through ladder steps. The proposed design is then used to construct the nonsubsampled contourlet transform which is particularly efficiently in image denoising, as experiments in this paper show.

Recent studies in linear inverse problems have recognized the sparse representation of unknown signal in a certain basis as an useful and effective prior information to solve those problems. In many multiscale bases (e.g. wavelets), signals of interest (e.g. piecewise-smooth signals) not only have few significant coefficients, but also those significant coefficients are well-organized in trees. We propose to exploit the tree-structured sparse representation as additional prior information for linear inverse problems with limited numbers of measurements. We present numerical results showing that exploiting the sparse tree representations lead to better reconstruction while requiring less time compared to methods that only assume sparse representations.

We present a heuristic algorithm for the choice of the wedgelet regularization parameter for the purpose of denoising in the case where the noise variance σ² is not known. Numerical experiments comparing wavelet thresholding with wedgelet denoising, and with the related schemes quadtree approximation and platelet approximation, allow to assess the respective strengths of the different approaches. For small values of σ², wavelets are clearly superior to wedgelets, and they are better at restoring textured regions. For large σ², or for images of a predominantly geometric nature, wedgelets yield consistently better results. Moreover, the tests reveal that the heuristic algorithm is quite effective in choosing the regularization parameter.

Recently, it was shown that it is possible to sample classes of signals with finite rate of innovation. These sampling schemes, however, use kernels with infinite support and this leads to complex and instable reconstruction algorithms. In this paper, we show that many signals with finite rate of innovation can be sampled and perfectly reconstructed using kernels of compact support and a local reconstruction algorithm. The class of kernels that we can use is very rich and includes any function satisfying Strang-Fix conditions, Exponential Splines and functions with rational Fourier transforms. Our sampling schemes can be used for either 1-D or 2-D signals with finite rate of innovation.

We develop a quaternion wavelet transform (QWT) as a new multiscale analysis tool for geometric image features. The QWT is a near shift-invariant, tight frame representation whose coefficients sport a magnitude and three phase values, two of which are directly proportional to local image shifts. The QWT can be efficiently computed using a dual-tree filter bank and is based on a 2-D Hilbert transform. We demonstrate how the QWT's magnitude and phase can be used to accurately analyze local geometric structure in images. We also develop a multiscale flow/motion estimation algorithm that computes a disparity flow map between two images with respect to local object motion.

This paper reviews recent best basis search algorithms. The problem under consideration is to select a representation from a dictionary which minimizes an additive cost function for a given signal. We describe a new framework of multitree dictionaries, and an efficient algorithm for finding the best representation in a multitree dictionary. We illustrate the algorithm through image compression examples.

In recent years there is a growing interest in the study of sparse representation for signals. Using an overcomplete dictionary that contains prototype signal-atoms, signals are described as sparse linear combinations of these atoms. Recent activity in this field concentrated mainly on the study of pursuit algorithms that decompose signals with respect to a given dictionary. Designing dictionaries to better fit the above model can be done by either selecting pre-specified transforms, or by adapting the dictionary to a set of training signals. Both these techniques have been considered in recent years, however this topic is largely still open. In this paper we address the latter problem of designing dictionaries, and introduce the K-SVD algorithm for this task. We show how this algorithm could be interpreted as a generalization of the K-Means clustering process, and demonstrate its behavior in both synthetic tests and in applications on real data. Finally, we turn to describe its generalization to nonnegative matrix factorization problem that suits signals generated under an additive model with positive atoms. We present a simple and yet efficient variation of the K-SVD that handles such extraction of non-negative dictionaries.

Recent work on sparse approximation has focused on the theoretical performance of algorithms for random inputs. This average-case behavior is typically far better than the behavior for the worst inputs. Moreover, an average-case analysis fits naturally with the type of signals that arise in certain applications, such as wireless communications. This paper describes what is currently known about the performance of greedy prusuit algorithms with random inputs. In particular, it gives a new result for the performance of Orthogonal Matching Pursuit (OMP) for sparse signals contaminated with random noise, and it explains recent work on recovering sparse signals from random measurements via OMP. The paper also provides a list of open problems to stimulate further research.

In this paper, we present the first 3D discrete curvelet transform. This transform is an extension to the 2D transform described in Candes et al..¹ The resulting curvelet frame preserves the important properties, such as parabolic scaling, tightness and sparse representation for singularities of codimension one. We describe three different implementations: in-core, out-of-core and MPI-based parallel implementations. Numerical results verify the desired properties of the 3D curvelets and demonstrate the efficiency of our implementations.

We will construct new classes of Parseval frames for a Hilbert space which allow signal reconstruction from the absolute value of the frame coefficients. As a consequence, signal reconstruction can be done without using phase or its estimation.

Sigma-Delta (ΣΔ) schemes are shown to be an effective approach for quantizing finite frame expansions. Basic error estimates show that first order ΣΔ schemes can achieve quantization error of order 1/N, where N is the frame size. Under certain technical assumptions, improved quantization error estimates of order (logN)/N^1.25 are obtained. For the second order ΣΔ scheme with linear quantization rule, error estimates of order 1/N² can be achieved in certain circumstances. Such estimates rely critically on being able to construct sufficiently small invariant sets for the scheme. New experimental results indicate a connection between the orbits of state variables in ΣΔ schemes and the structure of constant input invariant sets.

We analyze a fundamental question in Hilbert space frame theory: What is the optimal decomposition of a Parseval frame? We will see that this question impacts several famous unsolved problems in different areas of mathematics. As a step towards the solution of this question, we give a new identity which holds for all Parseval frames.

The theory of localized frames is a recently introduced concept with broad implications to frame theory in general, as well as to the special cases of Gabor and wavelet frames. Using the new notion of a R-dual sequence associated with a Bessel sequence, we derive several duality principles concerning localization in abstract frame theory. As applications of our results we prove a duality principle of localization of Gabor systems in the spirit of the Ron-Shen duality principle, and obtain a Janssen representation for general frame operators.

•We study the problem of finding a Fourier representation R of m terms for a given discrete signal A of length N. The Fast Fourier Transform (FFT) can find the optimal N-term representation in time O(N log N) time, but our goal is to get sublinear time algorithms when m << N. Suppose ||A||₂ ≤M||A-R_opt||₂, where R_opt is the optimal output. The previously best known algorithms output R such that ||A-R||²₂≤(1+ε))||A-R_opt||²₂ with probability at least 1-δ in time* poly(m,log(1/δ),log N,log M,1/ε). Although this is sublinear in the input size, the dominating expression is the polynomial factor in m which, for published algorithms, is greater than or equal to the bottleneck at m² that we identify below. Our experience with these algorithms shows that this is serious limitation in theory and in practice. Our algorithm beats this m² bottleneck. Our main result is a significantly improved algorithm for this problem and the d-dimensional analog. Our algorithm outputs an R with the same approximation guarantees but it runs in time m•poly(log(1/δ),log N,log M,1/ε). A version of the algorithm holds for all N, though the details differ slightly according to the factorization of N. For the d-dimensional problem of size N₁ × N₂ × •• × N_d, the linear-in-m algorithm extends efficiently to higher dimensions for certain factorizations of the N_i's; we give a quadratic-in-m algorithm that works for any values of N_i's. This article replaces several earlier, unpublished drafts.

In this paper, we study families of images generated by varying a parameter that controls the appearance of the object/scene in each image. Each image is viewed as a point in high-dimensional space; the family of images forms a low-dimensional submanifold that we call an image appearance manifold (IAM). We conduct a detailed study of some representative IAMs generated by translations/rotations of simple objects in the plane and by rotations of objects in 3-D space. Our central, somewhat surprising, finding is that IAMs generated by images with sharp edges are nowhere differentiable. Moreover, IAMs have an inherent multiscale structure in that approximate tangent planes fitted to ε-neighborhoods continually twist off into new dimensions as the scale parameter ε varies. We explore and explain this phenomenon. An additional, more exotic kind of local non-differentiability happens at some exceptional parameter points where occlusions cause image edges to disappear. These non-differentiabilities help to understand some key phenomena in image processing. They imply that Newton's method will not work in general for image registration, but that a multiscale Newton's method will work. Such a multiscale Newton's method is similar to existing coarse-to-fine differential estimation algorithms for image registration; the manifold perspective offers a well-founded theoretical motivation for the multiscale approach and allows quantitative study of convergence and approximation. The manifold viewpoint is also generalizable to other image understanding problems.

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.

Classically, analysis on manifolds and graphs has been based on the study of the eigenfunctions of the Laplacian and its generalizations. These objects from differential geometry and analysis on manifolds have proven useful in applications to partial differential equations, and their discrete counterparts have been applied to optimization problems, learning, clustering, routing and many other algorithms.¹⁻⁷ The eigenfunctions of the Laplacian are in general global: their support often coincides with the whole manifold, and they are affected by global properties of the manifold (for example certain global topological invariants). Recently a framework for building natural multiresolution structures on manifolds and graphs was introduced, that greatly generalizes, among other things, the construction of wavelets and wavelet packets in Euclidean spaces.^8,9 This allows the study of the manifold and of functions on it at different scales, which are naturally induced by the geometry of the manifold. This construction proceeds bottom-up, from the finest scale to the coarsest scale, using powers of a diffusion operator as dilations and a numerical rank constraint to critically sample the multiresolution subspaces. In this paper we introduce a novel multiscale construction, based on a top-down recursive partitioning induced by the eigenfunctions of the Laplacian. This yields associated local cosine packets on manifolds, generalizing local cosines in Euclidean spaces.¹⁰ We discuss some of the connections with the construction of diffusion wavelets. These constructions have direct applications to the approximation, denoising, compression and learning of functions on a manifold and are promising in view of applications to problems in manifold approximation, learning, dimensionality reduction.

In this paper, two approaches for image denoising that take advantages of neighboring dependency in the wavelet domain are studied. The first approach is to take into account the higher order statistical coupling between neighboring wavelet coefficients and their corresponding coefficients in the parent level. The second is based on multivariate statistical modeling. The estimation of the clean coefficients is obtained by a general rule using Bayesian approach. Various estimation expressions can be obtained by a priori probability distribution, called multivariate generalized Gaussian distribution (MGGD). The experimental results show that both of our methods give comparatively higher peak signal to noise ratio (PSNR) as well as little visual artifact for monochrome images. In addition, we extend our approaches to a denoising algorithm for color image that has multiple color components. The proposed color denoising algorithm is a framework to consider the correlations between color components yet using the existing monochrome denoising method without modification. Denoising results in this framework give noticeable better improvement than in the case when the correlation between color components is not considered.

Gaussian Scale Mixtures (GSMs) in overcomplete oriented pyramids are, arguably, one of the most powerful available tools for image denoising: 1) they provide a new mathematical frame for modelling the variance-adaptation problem, an approach used in image denoising for the last 25 years; 2) they are applicable to contaminating sources of any spectral density; 3) they yield the smallest L2-norm distortion results in simulations under white Gaussian noise, up to this date; and 4) they allow for a solution, for the first time, to the problem of denoising images affected by unknown covariance noise. In this work, we focus first on the general properties of the GSMs. Then, we review the different ways GSMs have been used in overcomplete oriented pyramids (MAP-z-GSM, BLS-GSM, spatially variant GSM), and their applications: classical denoising, signal-dependent noise removal, unknown covariance noise removal and deblurring.

In this paper we consider the recovery of missing regions in images and we compare the performance of two recent prediction algorithms that utilize sparse recovery. The first algorithm is based on recent work that tries to find sparse atomic decompositions (AD) using l1-norm regularization, while the second algorithm employs iterated denoising (ID). Experimental results indicate that ID generally outperforms the l1 based technique and we investigate the reasons for the often substantial performance difference. We discuss many issues that effect the robustness of the l1 based technique and in particular, we point to inherent problems in the missing data prediction setting that challenge the underlying sparse atomic decomposition assumptions at their core. Inspired by what ID does right, we provide techniques that are expected to improve the performance of sparse atomic decomposition motivated algorithms and we establish connections with ID.

The objective of this paper is to design a new estimator for multicomponent image denoising in the wavelet transform domain. To this end, we extend the block-based thresholding method initially proposed by Cai and Silverman, which takes advantage of the spatial dependence between the wavelet coefficients. In the case of multispectral images, we develop a more general framework for block-based shrinkage, the blocks being built from various combinations of the wavelet coefficients of the different image channels at adjacent spatial positions, for a given orientation and resolution level. In the presence of possibly spectrally correlated Gaussian noise, the parameters of the resulting estimator are optimized from the data by exploiting Stein's principle. Simulations show the higher performance of our estimator for denoising multispectral satellite images.

We study an image denoising approach the core of which is a locally adaptive estimation of the probability that a given coefficient contains a significant noise-free component, which we call "signal of interest". We motivate this approach within the minimum mean squared error criterion and develop and analyze different locally adaptive versions of this method for color and for multispectral images in remote sensing. For color images, we study two different approaches: (i) using a joint spatial/spectral activity indicator in the RGB color space and (ii) componentwise spatially adaptive denoising in a luminance-chrominance space. We demonstrate and discuss the advantages of both of these approaches in different scenarios. We also compare the analyzed method to other recent wavelet domain denoisers for multiband data both on color and on multispectral images.

We describe new wavelet-based techniques for removing noise from digital images. In the proposed approaches, the subband decompositions of images are modelled using alpha-stable prior models, which have been shown to be flexible enough in order to capture the heavy-tailed nature of wavelet coefficients. For improved denoising performance interscale dependencies of coefficients should also be taken into account and we achieve this by employing bivariate stable distributions. We restrict our study to the particular cases of the isotropic stable and the sub-Gaussian distributions. Using Bayesian estimation principles, we design both the bivariate minimum absolute error (MAE) and the bivariate maximum a posteriori (MAP) processors based on alpha-stable signal statistics. We also discuss methods of estimating stable distributions parameters from noisy observations. In implementing our algorithms, we make use of the dual-tree complex wavelet transform, which features near shift-invariance and improved directional selectivity compared to the standard wavelet transform. We test our algorithms in comparison with several recently published methods and show that our proposed techniques are competitive with the best wavelet-based denoising systems.

Three dimensional (3D) surfaces can be sampled parametrically in the form of range image data. Smoothing/denoising of such raw data is usually accomplished by adapting techniques developed for intensity image processing, since both range and intensity images comprise parametrically sampled geometry and appearance measurements, respectively. We present a transform-based algorithm for surface denoising, motivated by our previous work on intensity image denoising, which utilizes a non-separable Parseval frame and an ensemble thresholding scheme. The frame is constructed from separable (tensor) products of a piecewise linear spline tight frame and incorporates the weighted average operator and the Sobel operators in directions that are integer multiples of 45°. We compare the performance of this algorithm with other transform-based methods from the recent literature. Our results indicate that such transform methods are suited to the task of smoothing range images.

Recent work by some of the authors presented a novel construction of a multiresolution analysis on manifolds and graphs, acted upon by a given symmetric Markov semigroup {T^t}t≥0, for which T^t has low rank for large t. This includes important classes of diffusion-like operators, in any dimension, on manifolds, graphs, and in nonhomogeneous media. The dyadic powers of an operator are used to induce a multiresolution analysis, analogous to classical Littlewood-Paley and wavelet theory, while associated wavelet packets can also be constructed. This extends multiscale function and operator analysis and signal processing to a large class of spaces, such as manifolds and graphs, with efficient algorithms. Powers and functions of T (notably its Green's function) are efficiently computed, represented and compressed. This construction is related and generalizes certain Fast Multipole Methods, the wavelet representation of Calderon-Zygmund and pseudo-differential operators, and also relates to algebraic multigrid techniques. The original diffusion wavelet construction yields orthonormal bases for multiresolution spaces {V_j}. The orthogonality requirement has some advantages from the numerical perspective, but several drawbacks in terms of the space and frequency localization of the basis functions. Here we show how to relax this requirement in order to construct biorthogonal bases of diffusion scaling functions and wavelets. This yields more compact representations of the powers of the operator, better localized basis functions. This new construction also applies to non self-adjoint semigroups, arising in many applications.

We introduce a practical and improved version of the Polyharmonic Local Fourier transform (PHLFT) called PHLFT5. After partitioning an input image into a set of rectangular blocks, the original PHLFT decomposes each block into the polyharmonic component and the residual. The polyharmonic component solves the polyharmonic equation with the boundary condition that matches the values and normal derivatives of first order up to higher order of the solution along the block boundary with those of the original image block. Thanks to this boundary condition, the residual component can be expanded into a complex Fourier series without facing the Gibbs phenomenon and its Fourier coefficients decay faster than those of the original block. Due to the difficulty of estimating the higher order normal derivatives, however, only the harmonic case (i.e., Laplace's equation) has been implemented to date. In that case, the Fourier coefficients of the residual decay as O (||k||^-2) where k is the frequency index vector. Unlike the original version, PHLFT5 only imposes the boundary values and the first order normal derivatives as the boundary condition, which can be estimated using our robust algorithm. We then derive a fast algorithm to compute a fifth degree polyharmonic function that satisfies such boundary condition. The Fourier coefficients of the residual now decay as O (||k||^-3). We shall also show our preliminary numerical experiments that demonstrates the superiority of PHLFT5 over the original PHLFT of harmonic case in terms of the decay rate of the residual and interpretability of oriented textures.

We analyze localized textural consistencies in high-resolution Micro CT scans of coronary arteries to identify the appearance of diagnostically relevant changes in tissue. For the efficient and accurate processing of CT volume data, we use fast algorithms associated with three-dimensional so-called isotropic multiresolution wavelets that implement a redundant, frame-based image encoding without directional preference. Our algorithm identifies textural consistencies by correlating coefficients in the wavelet representation.

In this paper, we propose an advanced wavelet domain denoising scheme for the Gaussian noise reduction in color video. In the proposed method, we perform the wavelet transform of the luminance component (Y) in full resolution and the wavelet transform of chrominance information (U and V) in a subsampled resolution (2:1) in order to extract edges belonging to luminance and chrominance gradients (in horizontal and vertical directions). We use the low-pass (approximation) subbands of the chrominance channels together with detail (wavelet) bands for recursive motion estimation and adaptive temporal filtering. The final part of the proposed filter is a spatial filter out of the recursive loop. The noise level is monitored and detected automatically, by the gradient histogram approach for each channel separately and the estimated noise variance is used for adapting the algorithm. The results on color video show good video denoising performance for different noise levels. In comparison to the other color video denoising methods, the method performs better both from subjective (visually) and objective point of view. Also, the estimated motion vector field is quite robust against noise and this is useful in other applications such as tracking.

In 1992, Bamberger and Smith proposed the directional filter bank (DFB) for an efficient directional decomposition of two-dimensional (2-D) signals. Due to the nonseparable nature of the system, extending the DFB to higher dimensions while still retaining its attractive features is a challenging and previously unsolved problem. This paper proposes a new family of filter banks, named 3DDFB, that can achieve the directional decomposition of 3-D signals with a simple and efficient tree-structured construction. The ideal passbands of the proposed 3DDFB are rectangular-based pyramids radiating out from the origin at different orientations and tiling the whole frequency space. The proposed 3DDFB achieves perfect reconstruction. Moreover, the angular resolution of the proposed 3DDFB can be iteratively refined by invoking more levels of decomposition through a simple expansion rule. We also introduce a 3-D directional multiresolution decomposition, named the surfacelet transform, by combining the proposed 3DDFB with the Laplacian pyramid. The 3DDFB has a redundancy factor of 3 and the surfacelet transform has a redundancy factor up to 24/7.

Sparse approximation is typically concerned with generating compact representation of signals and data vectors by constructing a tailored linear combination of atoms drawn from a large dictionary. We have developed an algorithm based on simultaneous matching pursuits that facilitates the concurrent approximation of multiple signals in a common, low-dimensional representation space. The algorithm leads to an effective method of extracting signal components from collections of noisy data, and in particular is robust against jitter as well as additive noise. We illustrate its utility and compare performance in several variations by numerical examples.

We propose a generalization of the Cohen-Daubechies-Feauveau (CDF) and 9/7 biorthogonal wavelet families. This is done within the framework of non-stationary multiresolution analysis, which involves a sequence of embedded approximation spaces generated by scaling functions that are not necessarily dilates of one another. We consider a dual pair of such multiresolutions, where the scaling functions at a given scale are mutually biorthogonal with respect to translation. Also, they must have the shortest-possible support while reproducing a given set of exponential polynomials. This constitutes a generalization of the standard polynomial reproduction property. The corresponding refinement filters are derived from the ones that were studied by Dyn et al. in the framework of non-stationary subdivision schemes. By using different factorizations of these filters, we obtain a general family of compactly supported dual wavelet bases of L₂. In particular, if the exponential parameters are all zero, one retrieves the standard CDF B-spline wavelets and the 9/7 wavelets. Our generalized description yields equivalent constructions for E-spline wavelets. A fast filterbank implementation of the corresponding wavelet transform follows naturally; it is similar to Mallat's algorithm, except that the filters are now scale-dependent. This new scheme offers high flexibility and is tunable to the spectral characteristics of a wide class of signals. In particular, it is possible to obtain symmetric basis functions that are well-suited for image processing.

In this work we investigate the image denoising problem. One common approach found in the literature involves manipulating the coefficients in the transform domain, e.g. shrinkage, followed by the inverse transform. Several advanced methods that model the inter-coefficient dependencies were developed recently, and were shown to yield significant improvement. However, these methods operate on the transform domain error rather than on the image domain one. These errors are in general entirely different for redundant transforms. In this work we propose a novel denoising method, based on the Basis-Pursuit Denoising (BPDN). Our method combines the image domain error with the transform domain dependency structure, resulting in a general objective function, applicable for any wavelet-like transform. We focus here on the Contourlet Transform (CT) and on a redundant version of it, both relatively new transforms designed to sparsely represent images. The performance of our new method is compared favorably with the state-of-the-art method of Bayesian Least Squares Gaussian Scale Mixture (BLS-GSM), which we adapted to the CT as well, with further improvements still to come.

For any automated distress inspection system, typically a huge number of pavement images are collected. Use of an appropriate image compression algorithm can save disk space, reduce the saving time, increase the inspection distance, and increase the processing speed. In this research, a modified EZW (Embedded Zero-tree Wavelet) coding method, which is an improved version of the widely used EZW coding method, is proposed. This method, unlike the two-pass approach used in the original EZW method, uses only one pass to encode both the coordinates and magnitudes of wavelet coefficients. An adaptive arithmetic encoding method is also implemented to encode four symbols assigned by the modified EZW into binary bits. By applying a thresholding technique to terminate the coding process, the modified EZW coding method can compress the image and reduce noise simultaneously. The new method is much simpler and faster. Experimental results also show that the compression ratio was increased one and one-half times compared to the EZW coding method. The compressed and de-noised data can be used to reconstruct wavelet coefficients for off-line pavement image processing such as distress classification and quantification.

An approach for fast frequency estimation using spline wavelet is introduced in this paper, which simply makes use of the zero-crossings of the spline wavelet transforms of a signal. We show that the scale and order of the wavelets have a close relation with the frequency components of the signal. For a random signal with zero means, the lowest frequency component can be obtained by counting the number of zero-crossings of its spline wavelet transforms at sufficiently large scales, while the highest frequency component can be estimated by increasing the order of vanishing moments. A number of numerical examples will be demonstrated. The fast frequency estimation can find many applications such as the search of periodicity and white noise testing. Finally, we show the intrinsic connection of this approach with the level-crossing analysis in statistics and the scaling theorem in computer vision.

A wavelet-based smoothing technique based on hard and soft thresholding is proposed to eliminate statistical noise interference in the reconstruction of emission computed tomography. The interference is due to Poisson noise in the projection data. Pre-smoothing for projection data is performed to reduce the noise interference, together with post-smoothing for reconstructed images from the pre-smoothed projection data. The present work also investigates not only optimal parameter values for hard and soft thresholding but also the reason why the parameter values produced good smoothing results. An analysis was made about parameter values for thresholding with which good smoothing results were produced for the purpose of explaining the reason. Based on this analysis, an ad-hoc denoising algorithm is proposed for pre- and post- smoothing.

The link between wavelets and optics goes back to the work of Dennis Gabor who both invented holography and developed Gabor decompositions. Holography involves 3-D images. Gabor decompositions involves 1-D signals. Gabor decompositions are the predecessors of wavelets. Wavelet image processing of holography, both optical holography and digital holography, will be examined with respect to past achievements and future challenges.

We present the characterization and design of multidimensional oversampled FIR filter banks. In the polyphase domain, the perfect reconstruction condition for an oversampled filter bank amounts to the invertibility of the analysis polyphase matrix, which is a rectangular FIR matrix. For a nonsubsampled FIR filter bank, its analysis polyphase matrix is the FIR vector of analysis filters. A major challenge is how to extend algebraic geometry techniques, which only deal with polynomials (that is, causal filters), to handle general FIR filters. We propose a novel method to map the FIR representation of the nonsubsampled filter bank into a polynomial one by simply introducing a new variable. Using algebraic geometry and Groebner bases, we propose the existence, computation, and characterization of FIR synthesis filters given FIR analysis filters. We explore the design problem of MD nonsubsampled FIR filter banks by a mapping approach. Finally, we extend these results to general oversampled FIR filter banks.

The polyharmonic local sine transform is a recently introduced transform that can be used to compress and interpolate datasets. This transform is based on both Fourier theory and the solution to the polyharmonic equation (e.g. Laplace equation, biharmonic equation). The efficiency of this transform can be traced to theorems from Fourier analysis that relate the smoothness of the input function to the decay of the transform coefficients. This decay property is crucial and allows us to neglect high order coefficients. We will discuss the case of the Laplace sine transform. We introduce an arbitrary dimensional version of this transform for datasets sampled on rectangular domains and generalize the 2-dimensional algorithm to n dimensions. Since the efficiency of the Laplace sine transform relies on the smoothness of the data, we cannot directly apply it to discontinuous data. In order to deal with this, we have developed a segmentation algorithm that allows us to isolate smooth regions from those with discontinuities. The result is a transform that will locally adapt to the features in a dataset,allowing us to perform meaningful tests on real, discontinuous datasets.

Beamlet processing is a powerful and flexible approach to the identification of line based structures in data. The processing method is efficient (O(n²)) and also robust to variation in direction of the line continuation. This paper identifies two weaknesses with the current approach: the inability to identify lines at variable intensity, and with variation in width. These are addressed with a simple modification to the process used in selecting the salient beamlets called maxbeam2. This is demonstrated on a line image with variation in signal intensity and line width. The technique appears to correct the above weaknesses with only a small amount of extra processing, and hence make beamlets more generally applicable.

This paper describes a new pruned dual-tree discrete wavelet transform (DWT), which is designed to reduce the redundancy while maintaining the orientations. The new transform is based on the dual-tree wavelet transform introduced by Kingsbury. The number of wavelets associated with the transform is reduced substantially for both 2D and 3D cases. Wavelets generated from the pruned dual-tree DWT have direction/motion selectivity and are free of the checkerboard artifact, which are efficient for signal applications, such as image and video processing. This paper also describes an algorithm to compute the Matching Pursuit decomposition with this transform. Examples are shown to illustrate the performance of the matching pursuit algorithm and the 2D and 3D pruned dual-tree wavelet transforms.