Learning multiresolution schemes for compression of images

We introduce a new type of multiresolution based on the Harten's framework using learning theory. This changes the point of view of the classical multiresolution analysis and it transforms an approximation problem in a learning problem opening great possibilities. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)

A nonlinear algorithm for monotone piecewise bicubic interpolation

We present an algorithm for monotone interpolation on a rectangular mesh.We use the sufficient conditions for monotonicity of Carlton and Fritsch.We use nonlinear techniques to approximate the partial derivatives at the grid points.We develop piecewise bicubic Hermite interpolants with these approximations.We present some numerical examples where we compare different results. In this paper we present an algorithm for monotone interpolation of monotone data on a rectangular mesh by piecewise bicubic functions. Carlton and Fritsch (1985) develop conditions on the Hermite derivatives that are sufficient for such a function to be monotone. Here we extend our results of Arandiga (2013) to obtain…

Adaptive rational interpolation for cell-average

Abstract In this paper, we extend the rational interpolation introduced by G. Ramponi et al. (1997, 1998, 1996, 1995) to the cell average setting. We propose a new family of non linear interpolation operator. It consists on constructing new approximations using a non linear weighted combination of polynomials of degree 1 or 2 to obtain new interpolations of degree 2 or 4 respectively. New weights are proposed and analyzed. Gibbs phenomenon is studied and some experiments are performed comparing the new methods with classical linear and non linear interpolation as Weighted Essentially Non-Oscillatory (WENO).

The PCHIP subdivision scheme

In this paper we propose and analyze a nonlinear subdivision scheme based on the monotononicity-preserving third order Hermite-type interpolatory technique implemented in the PCHIP package in Matlab. We prove the convergence and the stability of the PCHIP nonlinear subdivision process by employing a novel technique based on the study of the generalized Jacobian of the first difference scheme. MTM2011-22741

Discrete multiresolution based on hermite interpolation: computing derivatives

Abstract Harten’s framework for multiresolution representation of data has been extended by Warming and Beam in [SIAM J. Sci. Comp. 22 (2000) 1269] to include Hermite interpolation. It needs the point-values of the derivative, which are usually unavailable, so they have to be approximated. In this work we show that the way in which the derivatives are approximated is crucial for the success of the method, and we present a new way to compute them that makes the scheme adequate for non-smooth data.

Cell-average multiresolution based on local polynomial regression. Application to image processing

In Harten (1996) [32] presented a general framework about multiresolution representation based on four principal operators: decimation and prediction, discretization and reconstruction. The discretization operator indicates the nature of the data. In this work the pixels of a digital image are obtained as the average of a function in some defined cells. A family of Harten cell-average multiresolution schemes based on local polynomial regression is presented. The stability is ensured by the linearity of the operators obtained and the order is calculated. Some numerical experiments are performed testing the accuracy of the prediction operators in comparison with the classical linear and nonli…

On Multiresolution Transforms Based on Weighted-Least Squares

This work is devoted to construct Harten’s multiresolution transforms using Weighted-Least squares for different discretizations. We establish a relation between the filters obtained using some decimation operators. Some properties and examples of filters are presented.

Tensor product multiresolution analysis with error control for compact image representation

A class of multiresolution representations based on nonlinear prediction is studied in the multivariate context based on tensor product strategies. In contrast to standard linear wavelet transforms, these representations cannot be thought of as a change of basis, and the error induced by thresholding or quantizing the coefficients requires a different analysis. We propose specific error control algorithms which ensure a prescribed accuracy in various norms when performing such operations on the coefficients. These algorithms are compared with standard thresholding, for synthetic and real images.

Non-linear Local Polynomial Regression Multiresolution Methods Using $$\ell ^1$$-norm Minimization with Application to Signal Processing

Harten’s Multiresolution has been developed and used for different applications such as fast algorithms for solving linear equations or compression, denoising and inpainting signals. These schemes are based on two principal operators: decimation and prediction. The goal of this paper is to construct an accurate prediction operator that approximates the real values of the signal by a polynomial and estimates the error using \(\ell ^1\)-norm in each point. The result is a non-linear multiresolution method. The order of the operator is calculated. The stability of the schemes is ensured by using a special error control technique. Some numerical tests are performed comparing the new method with…

Edge detection insensitive to changes of illumination in the image

In this paper we present new edge detection algorithms which are motivated by recent developments on edge-adapted reconstruction techniques [F. Arandiga, A. Cohen, R. Donat, N. Dyn, B. Matei, Approximation of piecewise smooth functions and images by edge-adapted (ENO-EA) nonlinear multiresolution techniques, Appl. Comput. Harmon. Anal. 24 (2) (2008) 225-250]. They are based on comparing local quantities rather than on filtering and thresholding. This comparison process is invariant under certain transformations that model light changes in the image, hence we obtain edge detection algorithms which are insensitive to changes in illumination.

Adaptive interpolation with maximum order close to discontinuities

Abstract Adaptive rational interpolation has been designed in the context of image processing as a new nonlinear technique that avoids the Gibbs phenomenon when we approximate a discontinuous function. In this work, we present a generalization to this method giving explicit expressions for all the weights for any order of the algorithm. It has a similar behavior to weighted essentially non oscillatory (WENO) technique but the design of the weights in this case is more simple. Also, we propose a new way to construct them obtaining the maximum order near the discontinuities. Some experiments are performed to demonstrate our results and to compare them with standard methods.

Weighted-Power p Nonlinear Subdivision Schemes

In this paper we present and analyze a generalization of the Powerp subdivision schemes proposed in [3,12]. The Weighted-Powerp schemes are based on a harmonic weighted version of the Power<emp average considered in [12], and their development is motivated by the desire to generalize the nonlinear analysis in [3,5] to interpolatory subdivision schemes with higher than second order accuracy.

On the reconstruction of discontinuous functions using multiquadric RBF–WENO local interpolation techniques

Abstract We discuss several approaches involving the reconstruction of discontinuous one-dimensional functions using parameter-dependent multiquadric radial basis function (MQ-RBF) local interpolants combined with weighted essentially non-oscillatory (WENO) techniques, both in the computation of the locally optimized shape parameter and in the combination of RBF interpolants. We examine the accuracy of the proposed reconstruction techniques in smooth regions and their ability to avoid Gibbs phenomena close to discontinuities. In this paper, we propose a true MQ-RBF–WENO method that does not revert to the classical polynomial WENO approximation near discontinuities, as opposed to what was pr…

Approximation of piecewise smooth functions and images by edge-adapted (ENO-EA) nonlinear multiresolution techniques

Abstract This paper introduces and analyzes new approximation procedures for bivariate functions. These procedures are based on an edge-adapted nonlinear reconstruction technique which is an intrinsically two-dimensional extension of the essentially non-oscillatory and subcell resolution techniques introduced in the one-dimensional setting by Harten and Osher. Edge-adapted reconstructions are tailored to piecewise smooth functions with geometrically smooth edge discontinuities, and are therefore attractive for applications such as image compression and shock computations. The local approximation order is investigated both in L p and in the Hausdorff distance between graphs. In particular, i…

Adaptive rational interpolation for point values

Abstract G. Ramponi et al. introduced in Carrato et al. (1997,1998), Castagno and Ramponi (1996) and Ramponi (1995) a non linear rational interpolator of order two. In this paper we extend this result to get order four. We observe the Gibbs phenomenon that is obtained near discontinuities with its weights. With the weights we propose we obtain approximations of order four in smooth regions and three near discontinuities. We also introduce a rational nonlinear extrapolation which is also of order four in the smooth region of the given function. In the experiments we calculate numerically approximation orders for the different methods described in this paper and see that they coincide with th…

Image compression based on a multi-directional map-dependent algorithm

Abstract This work is devoted to the construction of a new multi-directional edge-adapted compression algorithm for images. It is based on a multi-scale transform that is performed in two steps: a detection step producing a map of edges and a prediction/multi-resolution step which takes into account the information given by the map. A short analysis of the multi-scale transform is performed and an estimate of the error associated to the largest coefficients for a piecewise regular function with Lipschitz edges is provided. Comparisons between this map-dependent algorithm and different classical algorithms are given.

Weighted ENO interpolation and applications

Abstract Data-dependent interpolatory techniques such as essentially non-oscillatory (ENO) technique [J. Comput. Phys. 71 (1987) 231] have long been used as a reconstruction process in multiresolution schemes. In this work we analyze the weighted ENO (WENO) technique introduced by Liu et al. in the context of conservation laws [J. Comput. Phys. 115 (1994) 200] and improved by Jiang and Shu [J. Comput. Phys. 126 (1996) 202], and apply it to the compression of images, using multiresolution techniques.

Reconstructions that combine interpolation with least squares fitting

We develop a reconstruction that combines interpolation and least squares fitting for point values in the context of multiresolution a la Harten. We study the smoothness properties of the reconstruction as well as its approximation order. We analyze how different adaptive techniques (ENO, SR and WENO) can be used within this reconstruction. We present some numerical examples where we compare the results obtained with the classical interpolation and the interpolation combined with least-squares approximation. We develop a reconstruction that combines interpolation and least squares fitting.We study the smoothness properties of the reconstruction and its approximation order.We present some nu…

Data Compression with ENO Schemes: A Case Study

Abstract We study the compresion properties of ENO-type nonlinear multiresolution transformations on digital images. Specific error control algorithms are used to ensure a prescribed accuracy. The numerical results reveal that these methods strongly outperform the more classical wavelet decompositions in the case of piecewise smooth geometric images.

Cell-Average Multiwavelets Based on Hermite Interpolation

Multiresolution based on weighted averages of the hat function I: Linear reconstruction techniques

In this paper we analyze a particular example of the general framework developed in [A. Harten, {\it SIAM J. Numer. Anal}., 33 (1996) pp. 1205--1256], the case in which the discretization operator is obtained by taking local averages with respect to the hat function. We consider a class of reconstruction procedures which are appropriate for this multiresolution setting and describe the associated prediction operators that allow us to climb up the ladder from coarse to finer levels of resolution. In Part I we use data-independent (linear) reconstruction techniques as our approximation tool. We show how to obtain multiresolution transforms in bounded domains and analyze their stability with r…

Third-order accurate monotone cubic Hermite interpolants

Abstract Monotonicity-preserving interpolants are used in several applications as engineering or computer aided design. In last years some new techniques have been developed. In particular, in Arandiga (2013) some new methods to design monotone cubic Hermite interpolants for uniform and non-uniform grids are presented and analyzed. They consist on calculating the derivative values introducing the weighted harmonic mean and a non-linear variation. With these changes, the methods obtained are third-order accurate, except in extreme situations. In this paper, a new general mean is used and a third-order interpolant for all cases is gained. We perform several experiments comparing the known tec…

Non-separable local polynomial regression cell-average multiresolution operators. Application to compression of images

Abstract Cell-average multiresolution Harten׳s algorithms have been satisfactorily used to compress data. These schemes are based on two operators: decimation and prediction. The accuracy of the method depends on the prediction operator. In order to design a precise function, local polynomial regression has been used in the last years. This paper is devoted to construct a family of non-separable two-dimensional linear prediction operators approximating the real values with this procedure. Some properties are proved as the order of the scheme and the stability. Some numerical experiments are performed comparing the new methods with the classical linear method.

Design of Multiresolution Operators Using Statistical Learning Tools: Application to Compression of Signals

Using multiresolution based on Harten's framework [J. Appl. Numer. Math., 12 (1993), pp. 153---192.] we introduce an alternative to construct a prediction operator using Learning statistical theory. This integrates two ideas: generalized wavelets and learning methods, and opens several possibilities in the compressed signal context. We obtain theoretical results which prove that this type of schemes (LMR schemes) are equal to or better than the classical schemes. Finally, we compare traditional methods with the algorithm that we present in this paper.

Generalized wavelets design using Kernel methods. Application to signal processing

Abstract Multiresolution representations of data are powerful tools in signal processing. In Harten’s framework, multiresolution transforms are defined by predicting finer resolution levels of information from coarser ones using an operator, called the prediction operator, and defining details (or wavelet coefficients) that are the difference between the exact values and the predicted values. In this paper we present a multiresolution scheme using local polynomial regression theory in order to design a more accurate prediction operator. The stability of the scheme is proved and the order of the method is calculated. Finally, some results are presented comparing our method with the classical…

Non-consistent cell-average multiresolution operators with application to image processing

In recent years different techniques to process signal and image have been designed and developed. In particular, multiresolution representations of data have been studied and used successfully for several applications such as compression, denoising or inpainting. A general framework about multiresolution representation has been presented by Harten (1996) 20. Harten's schemes are based on two operators: decimation, D , and prediction, P , that satisfy the consistency property D P = I , where I is the identity operator. Recently, some new classes of multiresolution operators have been designed using learning statistical tools and weighted local polynomial regression methods obtaining filters…

Approximations of positive operators and continuity of the spectral radius III

AbstractWe prove estimates on the speed of convergence of the ‘peripheral eigenvalues’ (and principal eigenvectors) of a sequence Tn of positive operators on a Banach lattice E to the peripheral eigenvalues of its limit operator T on E which is positive, irreducible and such that the spectral radius r(T) of T is a Riesz point of the spectrum of T (that is, a pole of the resolvent of T with a residuum of finite rank) under some conditions on the kind of approximation of Tn to T. These results sharpen results of convergence obtained by the authors in previous papers.

Monotone cubic spline interpolation for functions with a strong gradient

Abstract Spline interpolation has been used in several applications due to its favorable properties regarding smoothness and accuracy of the interpolant. However, when there exists a discontinuity or a steep gradient in the data, some artifacts can appear due to the Gibbs phenomenon. Also, preservation of data monotonicity is a requirement in some applications, and that property is not automatically verified by the interpolator. Hence, some additional techniques have to be incorporated so as to ensure monotonicity. The final interpolator is not actually a spline as C 2 regularity and monotonicity are not ensured at the same time. In this paper, we study sufficient conditions to obtain monot…

Signal Denoising with Harten’s Multiresolution Using Interpolation and Least Squares Fitting

Harten’s multiresolution has been successfully applied to the signal compression using interpolatory reconstructions with nonlinear techniques. Here we study the applicability of these techniques to remove noise to piecewise smooth signals. We use two reconstruction types: interpolatory and least squares, and we introduce ENO and SR nonlinear techniques. The standard methods adaptation to noisy signals and the comparative of the different schemes are the subject of this paper.

Morse Description and Geometric Encoding of Digital Elevation Maps

Two complementary geometric structures for the topographic representation of an image are developed in this work. The first one computes a description of the Morse-topological structure of the image, while the second one computes a simplified version of its drainage structure. The topographic significance of the Morse and drainage structures of digital elevation maps (DEMs) suggests that they can been used as the basis of an efficient encoding scheme. As an application, we combine this geometric representation with an interpolation algorithm and lossless data compression schemes to develop a compression scheme for DEMs. This algorithm achieves high compression while controlling the maximum …