The dual-tree quaternion wavelet transform (QWT) is 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 phases: two phases encode local image shifts while the third contains image texture information. The QWT is based on an alternative theory for the 2-D Hilbert transform and can be computed using a dual-tree filter bank with linear computational complexity. To demonstrate the properties of the QWT's coherent magnitude/phase representation, we develop an efficient and accurate procedure for estimating the local geometrical structure of an image. We also develop a new multiscale algorithm for estimating the disparity between a pair of images that is promising for image registration and flow estimation applications. The algorithm features multiscale phase unwrapping, linear complexity, and sub-pixel estimation accuracy.

We propose an efficient multiscale image disparity estimation algorithm that estimates the local translations needed to align different regions in two images. The algorithm is based on the dual-tree quaternion wavelet transform (QWT). Each QWT coefficient features a magnitude and three phase angles; we exploit the fact that two of the phase angles are covariant with image shifts in the horizontal and vertical directions. By fusing phase information across multiple scales, we combat the phase unwrapping problem that has traditionally plagued phase-based disparity estimation techniques. The result is a linear-time algorithm that provides reliable estimates of both small and large image shifts. The algorithm is completely image-based; that is, it involves no extraction of feature points or other landmarks. It can be used as a front-end for image processing and computer vision tasks such as image registration, motion estimation, and stereo matching. We present results with a real-world image sequence.

In this paper, we present a novel geometry compression scheme for compactly representing 3-D sampled data. The proposed framework is based on the octree structured multiscale geometry representation, where local surface is expressed by multiscale plane descriptions. To reduce planar redundancy between different scale plane approximations in the multiscale pyramid, the multiscale plane pyramid is decomposed and the resulting refinement pyramid is encoded using the zerotree based coding method. The decomposition captures the geometry innovation to refine coarse geometry. Moreover, the zerotree based coding method offers the ordered bitstream according to the contribution for reconstructing the geometry innovation. Therefore, we demonstrate that the proposed algorithm compactly represents the 3-D point samples yielding progressive refinement of the surface geometry.

The wavelet transform provides a sparse representation for smooth images, enabling efficient approximation and compression using techniques such as zerotrees. Unfortunately, this sparsity does not extend to piecewise smooth images, where edge discontinuities separating smooth regions persist along smooth contours. This lack of sparsity hampers the efficiency of wavelet-based approximation and compression. On the class of images containing smooth C2 regions separated by edges along smooth C2 contours, for example, the asymptotic rate-distortion (R-D) performance of zerotree-based wavelet coding is limited to D(R) (< or = 1/R, well below the optimal rate of 1/R2. In this paper, we develop a geometric modeling framework for wavelets that addresses this shortcoming. The framework can be interpreted either as 1) an extension to the "zerotree model" for wavelet coefficients that explicitly accounts for edge structure at fine scales, or as 2) a new atomic representation that synthesizes images using a sparse combination of wavelets and wedgeprints--anisotropic atoms that are adapted to edge singularities. Our approach enables a new type of quadtree pruning for piecewise smooth images, using zerotrees in uniformly smooth regions and wedgeprints in regions containing geometry. Using this framework, we develop a prototype image coder that has near-optimal asymptotic R-D performance D(R) < or = (log R)2 /R2 for piecewise smooth C2/C2 images. In addition, we extend the algorithm to compress natural images, exploring the practical problems that arise and attaining promising results in terms of mean-square error and visual quality.

Many real world data sets can be viewed as points in a higher-dimensional space that lie concentrated around a lower-dimensional manifold structure. We propose a new multiscale representation for such point clouds based on lifting and perfect matching. The result is an adaptive wavelet transform that decomposes a point cloud into manifold approximations and details at multiple scales. We illustrate with several examples that the transform can extract an unknown smooth manifold from noisy point cloud samples using simple wavelet thresholding ideas.

The images generated by varying the underlying articulation parameters of an object (pose, attitude, light source position, and so on) can be viewed as points on a low-dimensional image parameter articulation manifold (IPAM) in a high-dimensional ambient space. In this paper, we develop theory and methods for the inverse problem of estimating, from a given image on or near an IPAM, the underlying parameters that produced it. Our approach is centered on the observation that, while typical image manifolds are not differentiable, they have an intrinsic multiscale geometric structure. In fact, each IPAM has a family of approximate tangent spaces, each one good at a certain resolution. Putting this structural aspect to work, we develop a new algorithm for high-accuracy parameter estimation based on a coarse-to-fine Newton iteration through the family of approximate tangent spaces. We test the algorithm in several idealized registration and pose estimation problems.

We extend the wavelet transform to handle multidimensional signals that are smooth save for singularities along lower-dimensional manifolds. We first generalize the complex wavelet transform to higher dimensions using a multidimensional Hilbert transform. Then, using the resulting hypercomplex wavelet transform (HWT) as a building block, we construct new classes of nearly shift-invariant wavelet frames that are oriented along lower-dimensional subspaces. The HWT can be computed efficiently using a 1D dual-tree complex wavelet transform along each signal axis. We demonstrate how the HWT can be used for fast line detection in 3D.

Using the concepts of two-dimensional Hubert transform and analytic signal, we construct a new quaternion wavelet transform (QWT). The QWT forms a tight frame and can be efficiently computed using a-2-D dual-tree filter bank. The QWT and the 2-D complex wavelet transform (CWT) are related by a unitary transformation, but the former inherits the quaternion Fourier-transform (QFT) phase properties, which are desirable for image analysis. The quaternion magnitude-phase representation of the QWT directly leads to near shift-invariance and the ability to encode phase shifts in an absolute x-y-coordinate system, which we can use for applications such as edge estimation and statistical image modeling.

We propose a new image denoising algorithm that exploits an image's representation in multiple wavelet domains. Besov balls are convex sets of images whose Besov norms are bounded from above by their radii. Projecting an image onto a Besov ball of proper radius corresponds to a type of wavelet shrinkage for image denoising. By defining Besov balls in multiple wavelet domains and projecting onto their intersection using the projection onto convex sets (POCS) algorithm, we obtain an estimate that effectively combines estimates from multiple wavelet domains. While simple, the algorithm provides significant improvement over conventional wavelet shrinkage algorithms based on a single wavelet domain.

A new algorithm for compressing three-dimensional triangular mesh data was used for representing surfaces. The estimation-quantization (EQ) algorithm was applied. EQ was originally designed for still image compression to the normal mesh wavelet coefficient. The EQ algorithm models the wavelet coefficients as a Gaussian random field with slowly varying standard deviation. By designing the quantizers in a rate-distortion optimal fashion, the previously proposed zerotree normal mesh compression algorithm has improved distortion by 0.5 to 1 dB.

Due to inherent factors such as a small and fragmented market and rapid hardware obsolescence, the conventional textbook is inadequate for DSP laboratory education. Freely available open-content materials that enable and promote both local customization and further development by a community of educators offers a fresh approach to lab text development that can surmount these barriers. We overview a joint effort under the aegis of the Connexions Project to develop a large pool of DSP lab modules sufficient to serve as the complete, stand-alone text for several types of DSP lab courses.

Wavelet-based image coders optimally represent smooth regions and isolated point singularities. However, wavelet coders are less adept at representing perceptually important edge singularities, and coding performance suffers significantly as a result. We propose a novel two-stage image coder framework based on modeling images as edge cartoons + textures. In stage 1, we infer and efficiently code the edge information from the image using a multiscale wedgelet decomposition. In stage 2, we code the residual, "edgeless" texture image using a standard wavelet coder. Our preliminary coder improves significantly over standard wavelet coding techniques in terms of visual quality.

Most wavelet-based image coders fail to model the joint coherent behavior of wavelet coefficients near edges. Wedgelets offer a convenient parameterization for the edges in an image, but they have yet to yield a viable compression algorithm. In this paper, we propose an extension of the zerotree-based space-frequency quantization (SFQ) algorithm by adding a wedgelet symbol to its tree-pruning optimization. This incorporates wedgelets into a rate-distortion compression framework and allows simple, coherent descriptions of the wavelet coefficients near edges. The resulting method yields improved visual quality and increased compression efficiency over the standard SFQ technique.

Multiresolution triangulation meshes are widely used in computer graphics for 3D modeling of shapes. We propose an image representation and processing framework using a multiscale triangulation of the grayscale function. Triangles have the potential of approximating edges better than the blocky structures of tensor-product wavelets. Among the many possible triangulation schemes, normal meshes are natural for efficiently representing singularities in image data, thanks to their adaptivity to the smoothness of the modeled image. Our non-linear, multiscale image decomposition algorithm, based on this subdivision scheme, takes edges into account in a way that is closely related to wedgelets and curvelets. The highly adaptive property of the normal mesh construction provides a very efficient representation of images, which potentially outperforms standard wavelet transforms. We demonstrate the approximation performance of the normal mesh representation through mathematical analyses for simple functions and simulations for real images.

Wavelet domain algorithms have risen to the forefront of image processing. The power of these algorithms is derived from the fact that the wavelet transform restructures images in a way that makes statistical modeling simpler. Since edge singularities account for the most important information in images, understanding how edges behave in the wavelet domain is the key to modeling. In the past, wavelet-domain statistical models have codified the tendency for wavelet coefficients representing an edge to be large across scale. We use the complex wavelet transform to uncover the phase behavior of wavelet coefficients representing an edge. This allows us to design a hidden Markov tree model that can discriminate between large magnitude wavelet coefficients caused by texture regions and ones caused by edges.

We introduce a new image texture segmentation algorithm, HMTseg, based on wavelets and the hidden Markov tree (HMT) model. The HMT is a tree-structured probabilistic graph that captures the statistical properties of the coefficients of the wavelet transform. Since the HMT is particularly well suited to images containing singularities (edges and ridges), it provides a good classifier for distinguishing between textures. Utilizing the inherent tree structure of the wavelet HMT and its fast training and likelihood computation algorithms, we perform texture classification at a range of different scales. We then fuse these multiscale classifications using a Bayesian probabilistic graph to obtain reliable final segmentations. Since HMTseg works on the wavelet transform of the image, it can directly segment wavelet-compressed images without the need for decompression into the space domain. We demonstrate the performance of HMTseg with synthetic, aerial photo, and document image segmentations.

Wavelet-domain hidden Markov models have proven to be useful tools for statistical signal and image processing. The hidden Markov tree (HMT) model captures the key features of the joint probability density of the wavelet coefficients of real-world data. One potential drawback to the HMT framework is the need for computationally expensive iterative training to fit an HMT model to a given data set (e.g., using the expectation-maximization algorithm). We greatly simplify the HMT model by exploiting the inherent self-similarity of real-world images. The simplified model specifies the HMT parameters with just nine meta-parameters (independent of the size of the image and the number of wavelet scales). We also introduce a Bayesian universal HMT (uHMT) that fixes these nine parameters. The uHMT requires no training of any kind, while extremely simple, we show using a series of image estimation/denoising experiments that these new models retain nearly all of the key image structure modeled by the full HMT. Finally, we propose a fast shift-invariant HMT estimation algorithm that outperforms other wavelet-based estimators in the current literature, both visually and in mean square error.

Multiresolution signal and image models such as the hidden Markov tree aim to capture the statistical structure of smooth and singular (edgy) regions. Unfortunately, models based on the orthogonal wavelet transform suffer from shift-variance, making them less accurate and realistic. We extend the HMT modeling framework to the complex wavelet transform, which features near shift-invariance and improved angular resolution compared to the standard wavelet transform. The model is computationally efficient (with linear-time computation and processing algorithms) and applicable to general Bayesian inference problems as a prior density for the data. In a simple estimation experiment, the complex wavelet HMT model outperforms a number of high-performance denoising algorithms, including redundant wavelet thresholding (cycle spinning) and the redundant HMT.

Multiresolution signal and image models such as the hidden Markov tree (HMT) aim to capture the statistical structures of smooth and singular (textured and edgy) regions. Unfortunately, models based on the orthogonal wavelet transform suffer from shift-variance, making them less accurate and realistic. We extend the HMT modeling framework to the complex wavelet transform, which features near shift-invariance and improved angular resolution compared to the standard wavelet transform. The model is computationally efficient (featuring linear-time computation and processing algorithms) and applicable to general Bayesian inference problems as a prior density for the data. We develop a simple multiscale maximum likelihood classification scheme based on the complex wavelet HMT that outperforms methods based on real-valued wavelet HMTs. The resulting classifier can be used as a front end in a more sophisticated multiscale segmentation algorithm.

We link concepts from nonuniform sampling, smoothness function spaces, interpolation, and denoising to derive a suite of multiscale, maximum-smoothness interpolation algorithms. We formulate the interpolation problem as the optimization of finding the signal that matches the given samples with smallest norm in a function smoothness space. For signals in the Besov space B/sub q//sup /spl alpha// (L/sub p/), the optimization corresponds to convex programming in the wavelet domain; for signals in the Sobolev space W/sup /spl alpha//(L/sub 2/), the optimization reduces to a simple weighted least-squares problem. An optional wavelet shrinkage regularization step makes the algorithm suitable for even noisy sample data, unlike classical approaches such as bandlimited and spline interpolation.

In this paper, we propose a new approach to wavelet-based deconvolution. Roughly speaking, the algorithm comprises Fourier-domain system inversion followed by wavelet-domain noise suppression. Our approach subsumes a number of other wavelet-based deconvolution methods. In contrast to other wavelet-based approaches, however, we employ a regularized inverse filter, which allows the algorithm to operate even when the inverse system is ill-conditioned or non-invertible. Using a mean-square-error metric, we strike an optimal balance between Fourier-domain and wavelet-domain regularization. The result is a fast deconvolution algorithm ideally suited to signals and images with edges and other singularities. In simulations with real data, the algorithm outperforms the LTI Wiener filter and other wavelet-based deconvolution algorithms in terms of both visual quality and MSE performance.

Wavelet-based image denoising algorithm depends upon the energy compaction property of wavelet transforms. However, for many real-world images, we cannot expect good energy compaction in a single wavelet domain, because most real-world images consist of components of a variety of smoothness. We can relieve this problem by using multiple wavelet bases to match different characteristics of images. In this paper, we propose a novel image denoising algorithm that uses multiple wavelet bases. By establishing a new relationship between the deterministic Besov space theory and the wavelet-domain statistical models, we generalize the Besov theory for finite sampled data. After defining convex sets in Besov spaces that contain the true image, we obtain an estimate of the true image by the method of projection onto convex sets. The algorithm outperforms existing multiple wavelet basis denoising algorithms; in particular, it shows excellent performance at low signal-to-noise ratios.

We propose a hybrid approach to wavelet-based image deconvolution that comprises Fourier-domain system inversion followed by wavelet-domain noise suppression. In contrast to conventional wavelet-based deconvolution approaches, the algorithm employs a regularized inverse filter, which allows it to operate even when the system is non-invertible. Using a mean-square-error metric, we strike an optimal balance between Fourier-domain regularization that is matched to the system and wavelet-domain regularization that is matched to the signal. Theoretical analysis reveals that the optimal balance is determined by economics of the input signal wavelet representation and the operator structure. The resultant algorithm is fast, O(N log/sub 2//sup 2/ N) where N denotes the number of samples, and is well-suited to data with spatially-localized phenomena such as edges. In addition to enjoying asymptotically near-optimal rates of error decay for some systems, the algorithm also achieves excellent performance at fixed data lengths. In simulations with real data, the algorithm outperforms the conventional LTI Wiener filter and other wavelet-based deconvolution algorithms in terms of both visual quality and MSE performance.

Wavelet-domain hidden Markov models have proven to be useful tools for statistical signal and image processing. The hidden Markov tree (HMT) model captures the key features of the joint statistics of the wavelet coefficients of real-world data. One potential drawback to the HMT framework is the need for computationally expensive iterative training (using the EM algorithm, for example). In this paper, we propose two reduced-parameter HMT models that capture the general structure of a broad class of grayscale images. The image HMT (iHMT) model leverages the fact that for a large class of images the structure of the HMT is self-similar across scale. This allows us to reduce the complexity of the iHMT to just nine easily trained parameters (independent of the size of the image and the number of wavelet scales). In the universal HMT (uHMT) we take a Bayesian approach and fix these nine parameters. The uHMT requires no training of any kind. While simple, we show using a series of image estimation/denoising experiments that these two new models retain nearly all of the key structures modeled by the full HMT. Based on these new models, we develop a shift-invariant wavelet denoising scheme that outperforms all algorithms in the current literature.

Studies the problem of interpolating a bandlimited signal from its nonuniform samples. The authors consider a class of interpolation algorithms that includes the least-squares optimal interpolator proposed by J.L. Yen, and derive a closed-form expression of the interpolation error for interpolators of this type. The expression for the interpolation error shows that the error depends on the eigenvalue distribution of a matrix, which is specified by the set of sampling points. The authors notice that the usual sinc-kernel interpolator is an approximation to the Yen interpolator, and suggest a method of choosing the weighting coefficients in the sinc-kernel interpolator. The new sinc-kernel interpolator is superior to the sinc interpolator with the usual Jacobian (area) weighting and is far easier to implement than the Yen interpolator.

Approaching targets can be imaged, with high resolution, using inverse synthetic aperture radar (ISAR). Image formation via the FFT, however, produces an image where the targets are shifted from their true locations. We begin by reviewing the Fourier model of ISAR image formation, which utilizes a Taylor series approximation to the range function. We then show that this Taylor series approximation is equivalent to the straight-line projection assumption in the tomographic model for ISAR. This approximation, plus the presumption that the acquired Fourier data lie on a Cartesian rather than polar grid, are shown to cause the target shifts. We derive formulas for accurately estimating the target shifts. These formulas can provide the basis for effectively compensating the ISAR image for scenarios with small, widely-spaced targets.>

Derives the wavenumber-domain SAR processing algorithm within a Hilbert-space framework. The derivation of the algorithm is motivated from geometrical considerations and the resulting image formation procedure is seen to be optimal. A new derivation of the algorithm, using a direct approximation of an exact Fourier identity, is given. The exact formulation is shown to be equivalent to previous derivations with appropriate approximations. Then, an approximate derivation of the algorithm is given which uses the principle of stationary phase to approximate the Fourier transforms. Fortunately, the approximations are exceedingly good for typical SAR imaging scenarios. Requirements on sampling for discrete implementation of the algorithm are discussed and the resolution achievable using this algorithm is shown to agree with that obtainable in a comparable spotlight scenario.>