Analysis of a New Nonlinear Subdivision Scheme. Applications in Image Processing

A nonlinear multiresolution scheme within Harten's framework is presented, based on a new nonlinear, centered piecewise polynomial interpolation technique. Analytical properties of the resulting subdivision scheme, such as convergence, smoothness, and stability, are studied. The stability and the compression properties of the associated multiresolution transform are demonstrated on several numerical experiments on images.     

Analysis of a class of nonlinear subdivision schemes and associated multiresolution transforms

This paper is devoted to the convergence and stability analysis of a class of nonlinear subdivision schemes and associated multiresolution transforms. As soon as a nonlinear scheme can be written as a specific perturbation of a linear and convergent subdivision scheme, we show that if some contractivity properties are satisfied, then stability and convergence can be achieved. This approach is applied to various schemes, which give different new results. More precisely, we study uncentered Lagrange interpolatory linear schemes, WENO scheme (Liu et al., J Comput Phys 115:200–212, 1994), PPH and Power-P schemes (Amat and Liandrat, Appl Comput Harmon Anal 18(2):198–206, 2005; Serna and Marquina, J Comput Phys 194:632–658, 2004) and a nonlinear scheme using local spherical coordinates (Aspert et al., Comput Aided Geom Des 20:165–187, 2003). Finally, a stability proof is given for the multiresolution transform associated to a nonlinear scheme of Marinov et al. (2005).     

Nonlinear thresholding of multiresolution decompositions adapted to the presence of discontinuities

A new nonlinear representation of multiresolution decompositions and new thresholding adapted to the presence of discontinuities are presented and analyzed. They are based on a nonlinear modification of the multiresolution details coming from an initial (linear or nonlinear) scheme and on a data dependent thresholding. Stability results are derived. Numerical advantages are demonstrated on various numerical experiments.     

Polyharmonic multiresolution analysis: an overview and some new results

This paper first presents a condensed state of art on multiresolution analysis using polyharmonic splines: definition and main properties of polyharmonic splines, construction of B-splines and wavelets, decomposition and reconstruction filters; properties of the so-obtained operators, convergence result and applications are given. Second this paper presents some new results on this topic: scattered data wavelet, new polyharmonic scaling functions and associated filters. Fourier transform is of extensive use to derive the tools of the various multiresolution analysis.     

Nonlinear multiscale decompositions: The approach of A. Harten

Datadependent interpolatory techniques can be used in the reconstruction step of a multiresolution scheme designed à la Harten. In this paper we carefully analyze the class of Essentially NonOscillatory (ENO) interpolatory techniques described in [11] and their potential to improve the compression capabilities of multiresolution schemes. When dealing with nonlinear multiresolution schemes the issue of stability also needs to be carefully considered.     

Normal Multiresolution Approximation of Curves

A multiresolution analysis of a curve is normal if each wavelet detail vector with respect to a certain subdivision scheme lies in the local normal direction. In this paper we study properties such as regularity, convergence, and stability of a normal multiresolution analysis. In particular, we show that these properties critically depend on the underlying subdivision scheme and that, in general, the convergence of normal multiresolution approximations equals the convergence of the underlying subdivision scheme.     

On some new variational problems for image denoising

This paper is devoted to image denoising problems using multiresolution schemes related to variational problems. We start with the linear approach of Donoho and Johnstone, that is related to a well known diffusion‐type variational problem. In order to improve the behavior of this approach, we propose some new nonlinear variational problems more adapted to the problem of denoising. Moreover, the discretization is performed using nonlinear multiresolution schemes. In particular, we obtain some fast and well adapted schemes for the considered problem of denoising.     

A family of stable nonlinear nonseparable multiresolution schemes in 2D

Multiresolution representations of data are powerful tools in data compression. For a proper adaptation to the edges, a good strategy is to consider a nonlinear approach. Thus, one needs to control the stability of these representations. In this paper, 2D multiresolution processing algorithms that ensure this stability are introduced. A prescribed accuracy is ensured by these strategies.     

Finite volume schemes on triangles coupled with multiresolution analysis

A multiresolution procedure is used to reduce the costs of flux evaluations in a finite volume scheme. A two-dimensional hyperbolic conservation law is solved on the finest grid among a hierarchy of nested grids. The mean values of the solution on triangles of a given grid are estimated from the coarser level using an original reconstruction algorithm. The size of the differences between the mean values and their reconstruction is a local regularity criterium and dictates the choice of the flux computation method. Numerical experiments with computing time comparisons are presented.     

On multiresolution schemes using a stencil selection procedure: applications to ENO schemes

This paper is devoted to multiresolution schemes that use a stencil selection procedure in order to obtain adaptation to the presence of edges in the images. Since non adapted schemes, based on a centered stencil, are less affected by the presence of texture, we propose the introduction of some weight that leads to a more frequent use of the centered stencil in regions without edges. In these regions the different stencils have similar weights and therefore the selection becomes an ill-posed problem with high risk of instabilities. In particular, numerical artifacts appear in the decompressed images. Our attention is centered in ENO schemes, but similar ideas can be developed for other multiresolution schemes. A nonlinear multiresolution scheme corresponding to a nonlinear interpolatory technique is analyzed. It is based on a modification of classical ENO schemes. As the original ENO stencil selection, our algorithm chooses the stencil within a region of smoothness of the interpolated function if the jump discontinuity is sufficiently big. The scheme is tested, allowing to compare its performances with other linear and nonlinear schemes. The algorithm gives results that are at least competitive in all the analyzed cases. The problems of the original ENO interpolation with the texture of real images seem solved in our numerical experiments. Our modified ENO multiresolution will lead to a reconstructed image free of numerical artifacts or blurred regions, obtaining similar results than WENO schemes. Similar ideas can be used in multiresolution schemes based in other stencil selection algorithms.      

曲线的一类非线性多分辨率算法及其收敛性

在曲线的多分辨率分析基础上,构造了一种新的非线性三分多分辨率算法.并研究这个正则三分多分辨率算法的收敛性和稳定性,进一步,证明了小波参数的收敛性精密地依靠这个基本的多分辨率细分算法的收敛性.     

Biorthogonal M-band filter construction using the lifting scheme

The lifting scheme has been proposed as a new idea for the construction of 2-band compactly supported wavelets with compactly-supported duals. The basic idea behind the lifting scheme is that it provides a simple relationship between all multiresolution analyses sharing the same scaling function. It is therefore possible to obtain custom-designed compactly supported wavelets with required regularity, vanishing moments, shape, etc. In this work, we generalize the lifting scheme for the construction of compactly-supported biorthogonal M-band filters. As in the previous case, we used the flexibility of the scheme to exploit the degree of freedom left after satisfying the perfect-reconstruction conditions in order to obtain finite filters with some interesting properties, such as vanishing moments, symmetry, shape, etc., or that satisfy certain optimality requests required for particular applications. Moreover, for these lifted biorthogonal M-band filters, we give an analysis-synthesis algorithm which is more efficient than the standard algorithm realized with filters with similar compression capabilities. This revised version was published online in June 2006 with corrections to the Cover Date.     

The template‐based procedure of biorthogonal ternary wavelets for curve multiresolution processing

Curve multiresolution processing techniques have been widely discussed in the study of subdivision schemes and many applications, such as surface progressive transmission and compression. The ternary subdivision scheme is the more appealing one because it can possess the symmetry, smaller topological support, and certain smoothness, simultaneously. So biorthogonal ternary wavelets are discussed in this paper, in which refinable functions are designed for cure and surface multiresolution processing of ternary subdivision schemes. Moreover, by the help of lifting techniques, the template‐based procedure is established for constructing ternary refinable systems with certain symmetry, and it also gives a clear geometric templates of corresponding multiresolution algorithms by several iterative steps. Some examples with certain smoothness are constructed.     

Multiresolution algorithms for the numerical solution of hyperbolic conservation laws

Given any scheme in conservation form and an appropriate uniform grid for the numerical solution of the initial value problem for one-dimensional hyperbolic conservation laws we describe a multiresolution algorithm that approximates this numerical solution to a prescribed tolerance in an efficient manner. To do so we consider the grid-averages of the numerical solution for a hierarchy of nested diadic grids in which the given grid is the finest, and introduce an equivalent multiresolution representation. The multiresolution representation of the numerical solution consists of its grid-averages for the coarsest grid and the set of errors in predicting the grid-averages of each level of resolution in this hierarchy from those of the next coarser one. Once the numerical solution is resolved to our satisfaction in a certain locality of some grid, then the prediction errors there are small for this particular grid and all finer ones; this enables us to compress data by setting to zero small components of the representation which fall below a prescribed tolerance. Therefore instead of computing the time-evolution of the numerical solution on the given grid we compute the time-evolution of its compressed multiresolution representation. Algorithmically this amounts to computing the numerical fluxes of the given scheme at the points of the given grid by a hierarchical algorithm which starts with the computation of these numerical fluxes at the points of the coarsest grid and then proceeds through diadic refinements to the given grid. At each step of refinement we add the values of the numerical flux at the center of the coarser cells. The information in the multiresolution representation of the numerical solution is used to determine whether the solution is locally well-resolved. When this is the case we replace the costly exact value of the numerical flux with an accurate enough approximate value which is obtained by an inexpensive interpolation from the coarser grid. The computational efficiency of this multiresolution algorithm is proportional to the rate of data compression (for a prescribed level of tolerance) that can be achieved for the numerical solution of the given scheme.     

Time-discretization of nonlinear control systems with state-delay via Taylor–Lie series

The state-delay is always existent in the practical systems. Analysis of the delay phenomenon in a continuous-time domain is sophisticated. It is appropriate to obtain its corresponding discrete-time model for implementation via digital computer. In this paper, we propose a new scheme for the discretization of nonlinear systems using Taylor series expansion and the zero-order hold assumption. This scheme is applied to the sample-data representation of a nonlinear system with constant state time-delay. The mathematical expressions of the discretization scheme are presented and the effect of the time-discretization method on equilibrium properties of nonlinear control system with state time-delay is examined. The proposed scheme provides a finite-dimensional representation for nonlinear systems with state time-delay enabling existing controller design techniques to be applied to them. The performance of the proposed discretization procedure is evaluated using a nonlinear system. For this nonlinear system, various sampling rates and time-delay values are considered.     

Data compression based on the cubic B-spline wavelet with uniform two-scale relation

The aim of this paper is to investigate the potential artificial compression which can be achieved using an interval multiresolution analysis based on a semiorthogonal cubic B-spline wavelet. The Chui-Quak [1] spline multiresolution analysis for the finite interval has been modified [2] so as to be characterized by natural spline projection and uniform two-scale relation. Strengths and weaknesses of the semiorthogonal wavelet as regards artificial compression and data smoothing by the method of thresholding wavelet coefficients are indicated.     

一类抛物型方程系数反问题的分裂算法

考虑利用终端时刻的温度u(x,T)=Z_T(x)反演热传导方程u_t-a~2u_(xx) q(x)u=0,x∈(0,1)中的未知系数q(x)的反问题.通过引进变换v(x,t)=(u_t(x,t)/u(x,t))将此非线性不适定问题的求解分解为两步.首先利用输入数据迭代求解一个非线性的正问题(该过程独立于未知系数),得到其迭代解v~(k)(x,t).其次利用q(x)与v(x,t)的关系式求出q(x)的近似解.对提出的反演方法,证明了采用的变换的可行性,得到了原反问题与由变换后的非线性正问题反演q(x)的等价性并且证明了迭代解的收敛性,给出了收敛速度.数值结果表明了该方法的有效性.     

Construction and reconstruction of tight framelets and wavelets via matrix mask functions

The paper develops construction procedures for tight framelets and wavelets using matrix mask functions in the setting of a generalized multiresolution analysis (GMRA). We show the existence of a scaling vector of a GMRA such that its first component exhausts the spectrum of the core space near the origin. The corresponding low-pass matrix mask has an especially advantageous form enabling an effective reconstruction procedure of the original scaling vector. We also prove a generalization of the Unitary Extension Principle for an infinite number of generators. This results in the construction scheme for tight framelets using low-pass and high-pass matrix masks generalizing the classical MRA constructions. We prove that our scheme is flexible enough to reconstruct all possible orthonormal wavelets. As an illustration we exhibit a pathwise connected class of non-MSF non-MRA wavelets sharing the same wavelet dimension function.     

"Push-the-Error" Algorithm for Nonlinear n-Term Approximation

This paper is concerned with further developing and refining the analysis of a recent algorithmic paradigm for nonlinear approximation, termed the "Push-the-Error" scheme. It is especially designed to deal with L_∞-approximation in a multilevel framework. The original version is extended considerably to cover all commonly used multiresolution frameworks. The main conceptually new result is the proof of the quasi-semi-additivity of the functional N(ε) counting the number of terms needed to achieve accuracy ε. This allows one to show that the improved scheme captures all rates of best n-term approximation.     

Hat Average Multiresolution with Error Control in 2-D

Multiresolution representations of data are a powerful tool in data compression. For a proper adaptation to the singularities, it is crucial to develop nonlinear methods which are not based on tensor product. The hat average framework permets develop adapted schemes for all types of singularities. In contrast with the wavelet framework these representations cannot be considered as a change of basis, and the stability theory requires different considerations. In this paper, non separable two-dimensional hat average multiresolution processing algorithms that ensure stability are introduced. Explicit error bounds are presented.