In $D$istributed optimization and $L$earning, and even more in the modern framework of federated learning, communication, which is slow and costly, is critical. We introduce LoCoDL, a communication-efficient algorithm that leverages the two popular and effective techniques of $Lo$cal training, which reduces the communication frequency, and $Co$mpression, in which short bitstreams are sent instead of full-dimensional vectors of floats. LoCoDL works with a large class of unbiased compressors that includes widely-used sparsification and quantization methods. LoCoDL provably benefits from local training and compression and enjoys a doubly-accelerated communication complexity, with respect to the condition number of the functions and the model dimension, in the general heterogeneous regime with strongly convex functions. This is confirmed in practice, with LoCoDL outperforming existing algorithms.

Looking for sparsity is nowadays crucial to speed up the training of large-scale neural networks. Projections onto the$\ell_{1}$and$\ell_{1,\propto}$are among the most efficient techniques to sparsify and reduce the overall cost of neural networks. In this paper, we introduce a new projection algorithm for the$\ell_{1,\infty}$norm ball. Its worst-case time complexity is$\mathcal{O}(nm+J\log(nm))$for a matrix in$\mathbb{R}^{n\times m}. J$is a term that tends to 0 when the sparsity is high, and to$n\times m$in the worst case. The algorithm is easy to implement and it is guaranteed to converge to the exact solution in finite time. Moreover, we propose to incorporate the$\ell_{1,\infty}$ball projection while training an auto encoder to enforce feature selection and sparsity of the weights. Sparsification appears in the encoder to primarily do feature selection due to our application in biology, where only a very small part ($<$2%) of the data is relevant. We show that in both the biological and general cases of sparsity, our method is the fastest.

Optimization problems under affine constraints appear in various areas of machine learning. We consider the task of minimizing a smooth strongly convex function F(x) under the affine constraint Kx = b, with an oracle providing evaluations of the gradient of F and multiplications by K and its transpose. We provide lower bounds on the number of gradient computations and matrix multiplications to achieve a given accuracy. Then we propose an accelerated primal-dual algorithm achieving these lower bounds. Our algorithm is the first optimal algorithm for this class of problems.

In distributed or federated optimization and learning, communication between the different computing units is often the bottleneck and gradient compression is widely used to reduce the number of bits sent within each communication round of iterative methods. There are two classes of compression operators and separate algorithms making use of them. In the case of unbiased random compressors with bounded variance (e.g., rand-k), the DIANA algorithm of Mishchenko et al. (2019), which implements a variance reduction technique for handling the variance introduced by compression, is the current state of the art. In the case of biased and contractive compressors (e.g., top-k), the EF21 algorithm of Richtárik et al. (2021), which instead implements an error-feedback mechanism, is the current state of the art. These two classes of compression schemes and algorithms are distinct, with different analyses and proof techniques. In this paper, we unify them into a single framework and propose a new algorithm, recovering DIANA and EF21 as particular cases. Our general approach works with a new, larger class of compressors, which has two parameters, the bias and the variance, and includes unbiased and biased compressors as particular cases. This allows us to inherit the best of the two worlds: like EF21 and unlike DIANA, biased compressors, like top-k, whose good performance in practice is recognized, can be used. And like DIANA and unlike EF21, independent randomness at the compressors allows to mitigate the effects of compression, with the convergence rate improving when the number of parallel workers is large. This is the first time that an algorithm with all these features is proposed. We prove its linear convergence under certain conditions. Our approach takes a step towards better understanding of two so-far distinct worlds of communication-efficient distributed learning.

In manufacturing, the monitoring of the fabrication process is crucial in order to be sure that objects are compliant. For nano-objects, most of this monitoring is done manually. In this paper, we propose a method to segment different materials in a manufactured object. The method uses design information which represent the ideal object to manufacture. This representation visually gathers information about materials, shapes and relationships between these shapes. In our segmentation method we choose to encode this information in the tree of shapes to enforce the design characteristics into a real image of the object. To achieve such segmentation, we perform graph cuts on this particular tree structure using additional information such as the position in the design or the order of inclusion of the shapes.

Most algorithms for solving optimization problems or finding saddle points of convex-concave functions are fixed-point algorithms. In this work we consider the generic problem of finding a fixed point of an average of operators, or an approximation thereof, in a distributed setting. Our work is motivated by the needs of federated learning. In this context, each local operator models the computations done locally on a mobile device. We investigate two strategies to achieve such a consensus: one based on a fixed number of local steps, and the other based on randomized computations. In both cases, the goal is to limit communication of the locally-computed variables, which is often the bottleneck in distributed frameworks. We perform convergence analysis of both methods and conduct a number of experiments highlighting the benefits of our approach.

The Mumford-Shah model is a standard model in image segmentation, and due to its difficulty, many approximations have been proposed. The major interest of this functional is to enable joint image restoration and contour detection. In this work, we propose a general formulation of the discrete counterpart of the Mumford-Shah functional, adapted to nonsmooth penalizations, fitting the assumptions required by the Proximal Alternating Linearized Minimization (PALM), with convergence guarantees. A second contribution aims to relax some assumptions on the involved functionals and derive a novel Semi-Linearized Proximal Alternated Minimization (SL-PAM) algorithm, with proved convergence. We compare the performances of the algorithm with several nonsmooth penalizations, for Gaussian and Poisson denoising, image restoration and RGB-color denoising. We compare the results with state-of-the-art convex relaxations of the Mumford-Shah functional, and a discrete version of the Ambrosio-Tortorelli functional. We show that the SL-PAM algorithm is faster than the original PALM algorithm, and leads to competitive denoising, restoration and segmentation results.

The nonlinear inverse problem of 2-D phase unwrapping consists in estimating an image, while its pixel values are observed modulo 2π. A variational formulation is considered, which consists in minimizing an energy, convex or not, under the nonconvex data fidelity constraints. We propose a new convex relaxation of this combinatorial problem. It shows similar or better performances than the state of the art.

Splines are piecewise polynomials and widely used for interpolation and smoothing of observed data, due to their flexibility and optimality in the sense of certain variational problems for one-dimensional (1D) data. However, spline interpolation and smoothing are applicable only to the estimation of continuous functions, and not suitable for that of piecewise smooth functions. In this paper, we propose a novel spline smoothing technique for the estimation of 1D piecewise smooth functions. We newly define the set of breaking splines, which are permitted to have several discontinuous knots. Then, we estimate a piecewise smooth function as a breaking spline minimizing the sum of the data fidelity term, the roughness penalty term, and the number of the discontinuous knots. Numerical experiments show the effectiveness of the breaking splines compared to the conventional splines and the state-of-the-art total generalized variation (TGV) denoising.

We present a new convex formulation for the problem of recovering lines in degraded images. Following the recent paradigm of superresolution, we formulate a dedicated atomic norm penalty and we solve this optimization problem by means of a primal-dual algorithm. This parsimonious model enables the reconstruction of lines from lowpass measurements, even in presence of a large amount of noise or blur. Furthermore, a Prony method performed on rows and columns of the restored image, provides a spectral estimation of the line parameters, with subpixel accuracy.

In this paper, we propose an adaptation of the PAM algorithm to the minimization of a nonconvex functional designed for joint image denoising and contour detection. This new functional is based on the Ambrosio-Tortorelli approximation of the well-known Mumford-Shah functional. We motivate the proposed approximation, offering flexibility in the choice of the possibly non-smooth penalization, and we derive closed form expression for the proximal steps involved in the algorithm. We focus our attention on two types of penalization: ℓl-norm and a proposed quadratic-f. function. Numerical experiments show that the proposed method is able to detect sharp contours and to reconstruct piecewise smooth approximations with low computational cost and convergence guarantees. We also compare the results with state-of-the-art relaxations of the Mumford-Shah functional and a recent discrete formulation of the Ambrosio-Tortorelli functional.

In the context of data fusion, pansharpening refers to the combination of a panchromatic (PAN) and a multispectral (MS) image, aimed at generating an image that features both the high spatial resolution of the former and high spectral diversity of the latter. In this work we present a model to jointly solve the problem of data fusion and reconstruction of a compressed image; the latter is envisioned to be generated solely with optical on-board instruments, and stored in place of the original sources. The burden of data downlink is hence significantly reduced at the expense of a more laborious analysis done at the ground segment to estimate the missing information. The reconstruction algorithm estimates the target sharpened image directly instead of decompressing the original sources beforehand; a viable and practical novel solution is also introduced to show the effectiveness of the approach.

We derive distributed algorithms for projecting the local values of the agents of a computing network on the simplex or on the$\ell _1$ball. These algorithms are based on the distributed alternating direction method of multipliers to solve a convex optimization problem of the form$\min _x \sum _n f_n(x)$, where each function$f_n$is local to node$n$and has an easy-to-compute proximity operator.

Inpainting in hyperspectral imagery is a challenging research area and several methods have been recently developed to deal with this kind of data. In this paper we address missing data restoration via a convex optimization technique with regularization term based on Collaborative Total Variation (CTV). In particular we evaluate the effectiveness of several instances of CTV in conjunction with different dimensionality reduction algorithms.

Spectral unmixing is a central problem in hyperspectral imagery. It is usually assuming a linear mixture model. Solving this inverse problem, however, can be seriously impacted by a wrong estimation of the number of endmembers, a bad estimation of the endmembers themselves, the spectral variability of the endmembers or the presence of nonlinearities. These problems can result in a too large number of retained endmembers. We propose to tackle this problem by introducing a new formulation for robust linear unmixing enhancing sparsity. With a single tuning parameter the optimization leads to a range of behaviors: from the standard linear model (low sparsity) to a hard classification (maximal sparsity : only one endmember is retained per pixel). We solve the proposed new functional using a computationally efficient proximal primal dual method. The experimental study, including both realistic simulated data and real data demonstrates the versatility of the proposed approach.

Variational methods are widely used in image processing for problems ranging from denoising to data fusion. In this paper we focus on a recent regularization method, called Collaborative Total Variation, applied to the hyperspectral pansharpening, which deals with the fusion of low resolution hyperspectral and high resolution panchromatic images. The effectiveness of this novel approach is evaluated for different Collaborative Norms and the assessment is performed on the Pavia University dataset.

We propose a new definition for the gradient field of a discrete image defined on a twice finer grid. The differentiation process from an image to its gradient field is viewed as the inverse operation of linear integration, and the proposed mapping is nonlinear. Then, we define the total variation of an image as the $\ell_1$ norm of its gradient field amplitude. This new definition of the total variation yields sharp edges and has better isotropy than the classical definition.

Proximal splitting algorithms for convex optimization are largely used in signal and image processing. They make possible to call the individual proximity operators of an arbitrary number of functions, whose sum is to be minimized. But the larger this number, the slower the convergence. In this letter, we show how to compute the proximity operator of a sum of two functions, for a certain type of functions operating on objects having a graph structure. The gain provided by avoiding unnecessary splitting is illustrated by an application to depth map estimation.

A wide array of image recovery problems can be abstracted into the problem of minimizing a sum of composite convex functions in a Hilbert space. To solve such problems, primal-dual proximal approaches have been developed which provide efficient solutions to large-scale optimization problems. The objective of this paper is to show that a number of existing algorithms can be derived from a general form of the forward-backward algorithm applied in a suitable product space. Our approach also allows us to develop useful extensions of existing algorithms by introducing a variable metric. An illustration to image restoration is provided.

This paper presents a new framework for oriented texture modeling. We introduce a new class of Gaussian fields, called Locally Anisotropic Fractional Brownian Fields, with prescribed local orientation at any point. These fields are a local version of a specific class of anisotropic self-similar Gaussian fields with stationary increments. The simulation of such textures is obtained using a new algorithm mixing the tangent field formulation and a turning band method, this latter method having proved its efficiency for generating stationary anisotropic textures. Numerical experiments show the ability of the method for synthesis of textures with prescribed local orientation.

We propose new optimization algorithms to minimize a sum of convex functions, which may be smooth or not and composed or not with linear operators. This generic formulation encompasses various forms of regularized inverse problems in imaging. The proposed algorithms proceed by splitting: the gradient or proximal operators of the functions are called individually, without inner loop or linear system to solve at each iteration. The algorithms are easy to implement and have proven convergence to an exact solution. The classical Douglas-Rachford and forward-backward splitting methods, as well as the recent and efficient algorithm of Chambolle-Pock, are recovered as particular cases. The application to inverse imaging problems regularized by the total variation is detailed.

The development of multisensor systems in recent years has led to great increase in the amount of available remote sensing data. Image fusion techniques aim at inferring high quality images of a given area from degraded versions of the same area obtained by multiple sensors. This paper focuses on pansharpening, which is the inference of a high spatial resolution multispectral image from two degraded versions with complementary spectral and spatial resolution characteristics: a) a low spatial resolution multispectral image; and b) a high spatial resolution panchromatic image. We introduce a new variational model based on spatial and spectral sparsity priors for the fusion. In the spectral domain we encourage low-rank structure, whereas in the spatial domain we promote sparsity on the local differences. Given the fact that both panchromatic and multispectral images are integrations of the underlying continuous spectra using different channel responses, we propose to exploit appropriate regularizations based on both spatial and spectral links between panchromatic and the fused multispectral images. A weighted version of the vector Total Variation (TV) norm of the data matrix is employed to align the spatial information of the fused image with that of the panchromatic image. With regard to spectral information, two different types of regularization are proposed to promote a soft constraint on the linear dependence between the panchromatic and the fused multispectral images. The first one estimates directly the linear coefficients from the observed panchromatic and low resolution multispectral images by Linear Regression (LR) while the second one employs the Principal Component Pursuit (PCP) to obtain a robust recovery of the underlying low-rank structure. We also show that the two regularizers are strongly related. The basic idea of both regularizers is that the fused image should have low-rank and preserve edge locations. We use a variation of the recently proposed Split Augmented Lagrangian Shrinkage (SALSA) algorithm to effectively solve the proposed variational formulations. Experimental results on simulated and real remote sensing images show the effectiveness of the proposed pansharpening method compared to the state-of-the-art.

This paper provides an extension of the 1D Hilbert Huang transform for the analysis of images using recent optimization techniques. The proposed method consists of: 1) adaptively decomposing an image into oscillating parts called intrinsic mode functions (IMFs) using a mode decomposition procedure and 2) providing a local spectral analysis of the obtained IMFs in order to get the local amplitudes, frequencies, and orientations. For the decomposition step, we propose two robust 2D mode decompositions based on nonsmooth convex optimization: 1) a genuine 2D approach, which constrains the local extrema of the IMFs and 2) a pseudo-2D approach, which separately constrains the extrema of lines, columns, and diagonals. The spectral analysis step is an optimization strategy based on Prony annihilation property and applied on small square patches of the IMFs. The resulting 2D Prony–Huang transform is validated on simulated and real data.

We consider the recovery of a finite stream of Dirac pulses at nonuniform locations, from noisy lowpass-filtered samples. We show that maximum-likelihood estimation of the unknown parameters can be formulated as structured low rank approximation of an appropriate matrix. To solve this difficult, believed NP-hard, problem, we propose a new heuristic iterative algorithm, based on a recently proposed splitting method for convex nonsmooth optimization. Although the algorithm comes, in absence of convexity, with no convergence proof, it converges in practice to a local solution, and even to the global solution of the problem, when the noise level is not too high. It is also fast and easy to implement.

We propose a maximum likelihood estimation approach for the recovery of continuously-defined sparse signals from noisy measurements, in particular periodic sequences of derivatives of Diracs and piecewise polynomials. The conventional approach for this problem is based on total-least-squares (a.k.a. annihilating filter method) and Cadzow denoising. It requires more measurements than the number of unknown parameters and mistakenly splits the derivatives of Diracs into several Diracs at different positions. Further on, Cadzow denoising does not guarantee any optimality. The proposed parametric approach solves all of these problems. Since the corresponding log-likelihood function is non-convex, we exploit the stochastic method of particle swarm optimization (PSO) to find the global solution. Simulation results confirm the effectiveness of the proposed approach, for a reasonable computational cost.

A very fast noniterative algorithm is proposed for denoising or smoothing one-dimensional discrete signals, by solving the total variation regularized least-squares problem or the related fused lasso problem. A C code implementation is available on the web page of the author.

Joint demosaicking and denoising consists in reconstructing a color image from the noisy raw data output by the sensor of a digital camera. We adopt a variational formulation in which the reconstructed image has minimal total variation under the constraint of consistency with the available measurements. This way, the recovered color image has smooth chrominance but the sharp edges are maintained and the noise is transferred to the luminance channel. This channel is denoised subsequently.

In remote sensing, pansharpening refers to the technique that combines the complementary spectral and spatial resolution characteristics of a multispectral image and a panchromatic image, with the objective to generate a high-resolution color image. This paper presents a new pansharpening method based on the minimization of a variant of total variation. We consider the fusion problem as the colorization of each pixel in the panchromatic image. A new term concerning the gradient of the panchromatic image is introduced in the functional of total variation so as to preserve edges. Experimental results on IKONOS satellite images demonstrate the effectiveness of the proposed method.

This paper presents a novel method for the enhancement of spatial quality of Hyperspectral (HS) images while making use of a high resolution panchromatic (PAN) image. Due to the high number of bands the application of a pansharpening technique to HS images may result in an increase of the computational load and complexity. Thus a dimensionality reduction preprocess, compressing the original number of measurements into a lower dimensional space, becomes mandatory. To solve this problem we propose a pansharpening technique combining both dimensionality reduction and fusion, exploited by non-linear Principal Component Analysis (NLPCA) and Indusion respectively, to enhance the spatial resolution of a hyperspectral image.

Digital color cameras acquire color images by means of a sensor on which a color filter array (CFA) is overlaid. The Bayer CFA dominates the consumer market, but there has recently been a renewed interest for the design of CFAs . However, robustness to noise is often neglected in the design, though it is crucial in practice. In this paper, we present a new 2 × 3-periodic CFA which provides, by construction, the optimal tradeoff between robustness to aliasing, chrominance noise and luminance noise. Moreover, a simple and efficient linear demosaicking algorithm is described, which fully exploits the spectral properties of the CFA. Practical experiments confirm the superiority of our design, both in noiseless and noisy scenarios.

In most digital cameras, color images are captured by a sensor overlaid by the Bayer color filter array (CFA). Denoisaicking (joint demosaicking and denoising) consists in reconstructing a color image from the noisy “Bayerized” data output by the sensor. We show that the frequency analysis of the sampling pattern induced by the Bayer CFA provides a simple way to reconstruct the luminance and chrominance channels of the image. The process is reduced to adequate linear filtering operations and denoising of the grayscale luminance image.

We investigate the use of a Fourier-domain derivative error kernel to quantify the error incurred while estimating the gradient of a function from scalar point samples on a regular lattice. We use the error kernel to show that gradient reconstruction quality is significantly enhanced merely by shifting the reconstruction kernel to the centers of the principal lattice directions. Additionally, we exploit the algebraic similarities between the scalar and derivative error kernels to design asymptotically optimal gradient estimation filters that can be factored into an infinite impulse response interpolation prefilter and a finite impulse response directional derivative filter. This leads to a significant performance gain both in terms of accuracy and computational efficiency. The interpolation prefilter provides an accurate scalar approximation and can be re-used to cheaply compute directional derivatives on-the-fly without the need to store gradients. We demonstrate the impact of our filters in the context of volume rendering of scalar data sampled on the Cartesian and Body-Centered Cubic lattices. Our results rival those obtained from other competitive gradient estimation methods while incurring no additional computational or storage overhead.

We propose a new color filter array (CFA) with optimal characteristics for the acquisition of color scenes, since the luminance and chrominance information is encoded in the mosaicked image with the best achievable robustness to aliasing and noise. Our 2 × 3 pattern is based on the paradigm recently introduced by Hirakawa et al., which focuses on the spectral properties of CFAs. Moreover, these superior properties are fully exploited by a simple, linear and efficient demosaicking method.

We propose in this work a new random pattern with R,G,B colors, which can be used to design color filter arrays (CFA) with good spectral properties, since the chrominance is modulated at high frequencies. Hence, the demosaicking artifacts appear as incoherent noise, which is less visually disturbing than the moire¿ structures characteristic of periodic CFAs.

We propose a method to demosaick images acquired with a completely arbitrary color filter array (CFA).We adopt a variational approach where the reconstructed image has maximal smoothness under the constraint of consistency with the measurements. This optimization problem boils down to a large, sparse system of linear equations to solve, for which we propose an iterative algorithm. Although the approach is linear, it yields visually pleasing demosaicked images and provides a robust framework for comparing the performances of CFAs.

In this work, we propose a new image rotation algorithm. The main feature of our approach is the symmetric reversibility, which means that when using the same algorithm for the converse operation, then the initial data is recovered exactly. To that purpose, we decompose the lattice conversion process into three successive shear operations. The translations along the shear directions are implemented by 1-D convolutions, with new appropriate fractional delay filters. Also, the method is fast and provides high-quality resampled images.

We propose new discrete-to-continuous interpolation models for hexagonally sampled data, that generalize two families of splines developed in the literature for the hexagonal lattice, to say the hex-splines and three directional box-splines. This extension is inspired by the construction of MOMS functions in 1-D, that generalize and outperform classical 1-D B-splines [1]. Our new generators have optimal approximation theoretic performances, for exactly the same computation cost as their spline counterparts.

The fusion of multispectral (MS) and panchromatic (PAN) images is a useful technique for enhancing the spatial quality of low-resolution MS images. Liu recently proposed the smoothing-filter-based intensity modulation (SFIM) fusion technique. This technique upscales MS images using bicubic interpolation and introduces high-frequency information of the PAN image into the MS images. However, this fusion technique is plagued by blurred edges if the upscaled MS images are not accurately coregistered with the PAN image. In the first part of this letter, we propose the use of the Induction scaling technique instead of bicubic interpolation to obtain sharper, better correlated, and hence better coregistered upscaled images. In the second part, we propose a new fusion technique derived from induction, which is named ldquoIndusion.rdquo In this method, the high-frequency content of the PAN image is extracted using a pair of upscaling and downscaling filters. It is then added to an upscaled MS image. Finally, a comparison of SFIM (with both bicubic interpolation and induction scaling) is presented along with the fusion results obtained by IHS, discrete wavelet transform, and the proposed Indusion techniques using Quickbird satellite images.

A new grid conversion method is proposed to resample between two 2-D periodic lattices with the same sampling density. The main feature of our approach is the symmetric reversibility, which means that when using the same algorithm for the converse operation, then the initial data is recovered exactly. To that purpose, we decompose the lattice conversion process into (at most) three successive shear operations. The translations along the shear directions are implemented by 1-D fractional delay operators, which revert to simple 1-D convolutions, with appropriate filters that yield the property of symmetric reversibility. We show that the method is fast and provides high-quality resampled images. Applications of our approach can be found in various settings, such as grid conversion between the hexagonal and the Cartesian lattice, or fast implementation of affine transformations such as rotations.

In this work, we propose a new grid conversion algorithm between the hexagonal lattice and the orthogonal (a.k.a. Cartesian) lattice. The conversion process, named H2O, is easy to implement and is perfectlyreversibleusing the same algorithm to return from one lattice to the other. The key observation of our approach is a decomposition of the lattice conversion as a sequence of shearing operations along three well-chosen directions. Hence, only 1-D fractional sample delay operators are required, which can be implemented by simple convolutions. The proposed algorithm combines reversibility and fast 1-D operations, together with high-quality resampled images.

Image magnification has been attracting a great deal of attention for long, and many approaches have been proposed to date. Nevertheless, bicubic interpolation is still the standard approach since it can be easily computed and does not require a priori knowledge nor a complicated model. In spite of such convenience, the images enlarged bicubically are blurry, in particular for large magnification factors. In this paper, we propose a new method, which is as compact as bicubic interpolation, while performing better than it. The key technique we used in this method is a sampling theorem that preserves preferential components in input images. We show that, by choosing the edge enhancement components as the preferential components, the proposed method performs much better than bicubic interpolation, with the same, or even less amount of computation.

Pan-sharpening is the process of improving spatial resolution of multi-spectral (MS) satellite images using the spatial details of a high resolution Panchromatic (PAN) image. Pan sharpening can be divided into scaling and fusion processes. In the first part of this paper we use Induction instead of bicubic interpolation for up-scaling the MS images. SFIM (Smoothing Filter based Intensity Modulation) is used to obtain fused MS images for the two different scaling techniques. In the second part, “Indusion”, a new fusion technique, derived from Induction, is proposed. In this technique the high frequency content of the PAN image is extracted using a pair of up-scaling and down scaling filters. It is then added to the up-scaled MS images. Finally a comparison of Indusion with Intensity, Hue, Saturation (HIS), Discrete Wavelet Transform (DWT) and SFIM fusion techniques is presented for IKONOS satellite images.

The reconstruction of a continuous-domain representation from sampled data is an essential element of many image processing tasks, in particular, image resampling. Until today, most image data have been available on Cartesian lattices, despite the many theoretical advantages of hexagonal sampling. In this paper, we propose new reconstruction methods for hexagonally sampled data that use the intrinsically 2-D nature of the lattice, and that at the same time remain practical and efficient. To that aim, we deploy box-spline and hex-spline models, which are notably well adapted to hexagonal lattices. We also rely on the quasi-interpolation paradigm to design compelling prefilters; that is, the optimal filter for a prescribed design is found using recent results from approximation theory. The feasibility and efficiency of the proposed methods are illustrated and compared for a hexagonal to Cartesian grid conversion problem.

Three-directional box-splines are particularly well-suited to interpolate and approximate hexagonally sampled data. In this paper, we propose a computationally efficient end-to-end reconstruction process. First, we introduce a prefiltering step that is based on a quasi-interpolation scheme using low-complexity finite-impulse-response (FIR) filters. Second, we derive a closed analytical expression for three-directional box-splines of any order that leads to a fast evaluation of the spline surface. All operations act locally on the data, and thus are well adapted to applications dealing with large images. To demonstrate the feasibility of our method, we implemented the complete procedure and we present experimental results.

We propose a new characterization of three-directional box-splines, which are well adapted for interpolation and approximation on hexagonal lattices. Inspired by a construction already applied with success for exponential splines and hex-splines, we characterize a box-spline as a convolution of a generating function, which is a Green function of the spline's associated differential operator, and a discrete filter that plays the role of a localization operator. This process leads to an elegant analytical expression of three-directional box-splines. It also brings along a particularly efficient implementation

An original image magnification method called induction was proposed recently, whose specificity is to state the problem of image magnification as an inverse problem of image reduction. The methods usually employed, like interpolation, fail to verify this constraint, which provides a formalism for magnification and a framework for evaluating the quality of the enlarged images. In this paper, we revisit the induction through a new interpretation using wavelets. We put forward major improvements including a direct implementation, much more efficient than the iterative algorithm proposed previously.

We investigate the use of quasi-interpolating approximation schemes, to construct an estimate of an unknown function from its given discrete samples. We show theoretically and with practical experiments that such methods perform better than classical interpolation, for the same computation cost.

We provide a new comparison between hexagonal and orthogonal lattices, based on approximation theory. For each of the lattices, we select the "natural" spline basis function as generator for a shift-invariant function space; i.e., the tensor-product B-splines for the orthogonal lattice and the non-separable hex-splines for the hexagonal lattice. For a given order of approximation, we compare the asymptotic constants of the error kernels, which give a very good indication of the approximation quality. We find that the approximation quality on the hexagonal lattice is consistently better, when choosing lattices with the same sampling density. The area sampling gain related to these asymptotic constants quickly converges when the order of approximation of the basis functions increases. Surprisingly, nearest-neighbor interpolation does not allow to profit from the hexagonal grid. For practical purposes, the second-order hex-spline (i.e., constituted by linear patches) appears as a particularly useful candidate to exploit the advantages of hexagonal lattices when representing images on them.