The reconstruction quality in compressed sensing MRI can be significantly improved by optimizing the k-space sampling. While previous works have mainly focused on total variation and other traditional regularizers, more recent denoising-driven regularizers have not been fully explored. We address this gap by developing a computational framework to learn the optimal sampling for Plug-and-Play (PnP) regularization. A technical challenge here is the computation of the gradient of the training loss with respect to the reconstruction variable, which is used within the learning algorithm to optimize the sampling. A notable finding in this direction is that the gradient can be computed analytically for a kernel denoiser such as the nonlocal means. Moreover, the superior regularization offered by PnP helps discover sampling patterns that significantly improve the reconstruction. We demonstrate the effectiveness of our proposal for different anatomical datasets.

Abstract. The effectiveness of denoising-driven regularization for image reconstruction has been widely recognized. Two prominent algorithms in this area are Plug-and-Play (PnP) and Regularization-by-Denoising (RED). We consider two specific algorithms, PnP-FISTA and RED-APG, where regularization is performed by replacing the proximal operator in the FISTA algorithm with a powerful denoiser. The iterate convergence of FISTA is known to be challenging with no universal guarantees. Yet, we show that for linear inverse problems and a class of linear denoisers, global linear convergence of the iterates of PnP-FISTA and RED-APG can be established through simple spectral analysis.

The widely used RED (Regularization-by-Denoising) framework uses pretrained denoisers as implicit regularizers for model-based reconstruction. Although RED generally yields high-fidelity reconstructions, the use of black-box denoisers can sometimes lead to instability. In this letter, we propose a data-driven mechanism to stabilize RED using the Koopman operator, a classical tool for analyzing dynamical systems. Specifically, we use the operator to capture the local dynamics of RED in a low-dimensional feature space, and its spectral radius is used to detect instability and formulate an adaptive step-size rule that is model-agnostic, has modest overhead, and requires no retraining. We test this with several pretrained denoisers to demonstrate the effectiveness of the proposed Koopman stabilization.

The problem of training a convolutional neural network (CNN) with a stipulated Lipschitz bound comes up in applications such as adversarial robustness, stability of closed-loop controllers, and image reconstruction. The present work was motivated by Plug-and-Play (PnP) and Regularization-by-Denoising (RED) which use CNN denoisers for image reconstruction. It has been shown that the convergence of these iterative algorithms can be guaranteed by constraining the Lipschitz bound of the denoiser. We make the case that using a contractive CNN denoiser is a straightforward means to certify convergence. In particular, we show how a contractive CNN denoiser can be trained using convex projections within the paradigm of gradient-based learning and how the projection problem can be reduced to a tractable convex program. Apart from the theoretical guarantee, the regularization capacity of the trained denoiser is shown to be competitive with BM3D and DnCNN.

Plug-and-Play (PnP) algorithms leverage the power of modern denoisers for image reconstruction. They have been shown to deliver state-of-the-art reconstructions using CNN denoisers. It was established in recent works that convergence of these iterative algorithms can be guaranteed using nonexpansive denoisers. However, integrating nonexpansivity into gradient-based learning is challenging. Existing algorithms for training nonexpansive denoisers often cannot guarantee nonexpansivity or are computationally intensive. The present work is based on the observation that the convergence of PnPFBS and PnP-BBS (PnP based on Forward-Backward and BackwardBackward Splittings) can be guaranteed using contractive denoisers. In this regard, we show that by unfolding FBS iterations applied to wavelet denoising, we can construct contractive image denoisers whose regularization capacity is comparable to CNN denoisers. To the best of knowledge, this is the first work to introduce a simple framework for training denoisers that are provably contractive.

Magnetic Resonance Imaging (MRI) is the preferred approach for soft-tissue imaging due to its good contrast and non-invasiveness. While traditional MRI yields high-quality images, low-field scanners, though affordable and portable, produce lower-resolution images due to time and hardware constraints. The resolution can be enhanced using deep learning; however, the end-to-end nature of such models necessitates retraining the network with changes in the measurement parameters, such as the downsampling factor. Moreover, conventional superresolution (SR) models are not ideally suited for MRI, where the measurements are obtained in the k space. To address these challenges, we propose to decouple the forward model from the network using the Plug-and-Play framework. Specifically, we use a trained denoiser for scale-agnostic regularization, i.e., the input to the network is independent of the downsampling factor. Consequently, our method can be used with different resolution scanners, which is not possible with end-to-end networks. The innovation of our approach is that (i) we use a loss function derived from an MRspecific forward model, and (ii) instead of a standard off-the-shelf Gaussian denoiser, we train a U-Net denoiser to remove “artifacts” from the intermediate reconstructions. Our method achieves stateof-the-art reconstructions and is robust to acquisition and resolution settings.

In the Plug-and-Play (PnP) method, a denoiser is used as a regularizer within classical proximal algorithms for image reconstruction. It is known that a broad class of linear denoisers can be expressed as the proximal operator of a convex regularizer. Consequently, the associated PnP algorithm can be linked to a convex optimization problem$\mathcal {P}$. For such a linear denoiser, we prove that$\mathcal {P}$exhibits strong convexity for linear inverse problems. Specifically, we show that the strong convexity of$\mathcal {P}$can be used to certify objective and iterative convergence ofanyPnP algorithm derived from classical proximal methods.

Theoretical understanding of Plug-and-Play (PnP) algorithms, where an off-the-shelf denoiser is used for image regularization , is an active research topic. In this work, we study the problems of exact and stable signal recovery from compressively sensed (CS) measurements using PnP algorithms. We focus on a class of linear denoisers for which it is possible to associate a convex regularizer Φ . We consider the CS problem of minimizing Φ ⁡ ( 𝒙 ) subject to 𝐀 ⁢ 𝒙 = 𝐀 ⁢ 𝛏 , where 𝐀 is the random sensing matrix and 𝛏 is the ground truth. We prove that if 𝐀 is Gaussian and 𝛏 lies in the range of the associated denoiser 𝐖 , then the minimizer is almost surely 𝛏 if 𝑟 𝑎 𝑛 𝑘 ⁡ ( 𝐖 ) is less than the number of measurements and almost never otherwise. We extend the result to subgaussian matrices, except that we can guarantee exact recovery only with high probability. For noisy measurements, we consider a robust analogue of the recovery problem and prove that the error between the recovered and the ground-truth signal is bounded by the noise strength . In particular, we derive the sample complexity of CS as a function of reconstruction error and success rate. We perform numerical experiments to validate our theoretical findings.

Presents corrections to the article “On the Contractivity of Plug-and-Play Operators”.

In plug-and-play (PnP) regularization, the proximal operator in algorithms such as ISTA and ADMM is replaced by a powerful denoiser. This formal substitution works surprisingly well in practice. In fact, PnP has been shown to give state-of-the-art results for various imaging applications. The empirical success of PnP has motivated researchers to understand its theoretical underpinnings and, in particular, its convergence. It was shown in prior work that for kernel denoisers such as the nonlocal means, PnP-ISTA provably converges under some strong assumptions on the forward model. The present work is motivated by the following questions: Can we relax the assumptions on the forward model? Can the convergence analysis be extended to PnP-ADMM? Can we estimate the convergence rate? In this letter, we resolve these questions using the contraction mapping theorem: (i) for symmetric denoisers, we show that (under mild conditions) PnP-ISTA and PnP-ADMM exhibit linear convergence; and (ii) for kernel denoisers, we show that PnP-ISTA and PnP-ADMM converge linearly for image inpainting. We validate our theoretical findings using reconstruction experiments.

We consider the problem of signal reconstruction from linearly corrupted data using plug-and-play (PnP) regularization. As opposed to traditional sparsity-promoting regularizers, PnP uses an off-the-shelf denoiser within a proximal algorithm such as ISTA or ADMM for image reconstruction. Although PnP has become popular in the imaging community, its regularization capacity is not fully understood. For example, it is not known if PnP can in theory recover a signal from few noiseless measurements as in classical compressed sensing and if the recovery is robust. We explore these questions in this work and present some theoretical and experimental results. In particular, we prove that if the denoiser in question has low rank and if the ground- truth lies in the range of the denoiser, then it can be recovered exactly from noiseless measurements. To the best of knowledge, this is first such result. Furthermore, we show using numerical simulations that even if the aforementioned conditions are violated, PnP recovery is robust in practice. We formulate a theorem regarding the recovery error based on these observations.

Multiband fusion involves combining an image having high spatial and low spectral resolution with another image having low spatial and high spectral resolution—resulting in a single multiband image with high spatial and spectral resolutions. In classical variational techniques, this problem is formulated as the minimization of an objective function consisting of two quadratic data-fidelity terms and an edge-preserving regularizer; the former account for blur, resolution mismatch and additive noise. In this work, we explore a constrained formulation of this problem where the regularization function is minimized subject to hard constraints on the data fidelity. Unlike the penalty approach, the advantage is that the user has direct control on the data fidelity of the reconstruction. We come up with an efficient ADMM solver for this constrained optimization problem. Moreover, for convex regularizers, we prove that that the ADMM iterates converge to an optimal solution (this is somewhat standard but requires the verification of certain technical conditions). To our knowledge, the use of constrained optimization for image fusion is novel. The proposed framework is shown to model the observations well and its fusion quality is competitive with state-of-the-art methods.

Hyperspectral (HS) images have high spectral but low spatial resolutions, while multispectral (MS) images, on the other hand, have low spectral but high spatial resolutions. In HS–MS fusion, the HS and MS images are combined to obtain a single image with high spatial and spectral resolutions. Such images are typically textured and exhibit repetitive structures. To exploit this prior, we propose a nonlocal weighted total-variation regularizer. The novelty of the design is that the following hold: 1) we use a weighted norm, where the weights are derived from the MS image and 2) pixel variations over nonlocal neighborhoods are considered. We incorporate the regularizer into a standard convex optimization framework involving quadratic data-fidelity terms. We develop an efficient ADMM algorithm for solving this optimization problem—the novelty in this regard is that we use a variable splitting technique that results in the closed-form solutions of the ADMM subproblems. We report results on standard datasets demonstrating that the proposed regularizer can recover fine textures (as opposed to local pixel-based methods) and outperform the state-of-the-art methods.

There has been tremendous research on the design of image regularizers over the years, from simple Tikhonov and Laplacian to sophisticated sparsity and CNN-based regularizers. Coupled with a model-based loss function, these are typically used for image reconstruction within an optimization framework. The technical challenge is to develop a regularizer that can accurately model realistic images and be optimized efficiently along with the loss function. Motivated by the recent plug-and-play paradigm for image regularization, we construct a quadratic regularizer whose reconstruction capability is competitive with state-of-the-art regularizers. The novelty of the regularizer is that, unlike classical regularizers, the quadratic objective function is derived from the observed data. Since the regularizer is quadratic, we can reduce the optimization to solving a linear system for applications such as superresolution, deblurring, inpainting, etc. In particular, we show that using iterative Krylov solvers, we can converge to the solution in few iterations, where each iteration requires an application of the forward operator and a linear denoiser. The surprising finding is that we can get close to deep learning methods in terms of reconstruction quality. To the best of our knowledge, the possibility of achieving near state-of-the-art performance using a linear solver is novel.

In plug-and-play (PnP) regularization, the knowledge of the forward model is combined with a powerful denoiser to obtain state-of-the-art image reconstructions. This is typically done by taking a proximal algorithm such as FISTA or ADMM, and formally replacing the proximal map associated with a regularizer by nonlocal means, BM3D or a CNN denoiser. Each iterate of the resulting PnP algorithm involves some kind of inversion of the forward model followed by denoiser-induced regularization. A natural question in this regard is that of optimality, namely, do the PnP iterations minimize some f+g , where f is a loss function associated with the forward model and g is a regularizer? This has a straightforward solution if the denoiser can be expressed as a proximal map, as was shown to be the case for a class of linear symmetric denoisers. However, this result excludes kernel denoisers such as nonlocal means that are inherently non-symmetric. In this paper, we prove that a broader class of linear denoisers (including symmetric denoisers and kernel denoisers) can be expressed as a proximal map of some convex regularizer g . An algorithmic implication of this result for non-symmetric denoisers is that it necessitates appropriate modifications in the PnP updates to ensure convergence to a minimum of f+g . Apart from the convergence guarantee, the modified PnP algorithms are shown to produce good restorations.

We propose a fast algorithm for an adaptive variant of the classical bilateral filter, where the range kernel is allowed to vary from pixel to pixel. Several fast and accurate algorithms have been proposed for bilateral filtering, but they assume that the same range kernel is used at each pixel and hence cannot be used for adaptive bilateral filtering (ABF). Only recently, it was shown that fast algorithms for ABF can be developed by approximating the local histogram around each pixel using polynomials. The present algorithm is derived using an entirely different approximation, namely, the range kernels across all pixels are jointly approximated (compressed) using singular value decomposition (SVD). The SVD involves a very large matrix and cannot be computed exactly; however, we are able to get a sufficiently accurate approximation using the Nyström method (without populating/storing the entire matrix). We show that this SVD-type decomposition allows us to approximate the adaptive bilateral filter using fast convolutions. To demonstrate the speed and accuracy of the proposed algorithm in relation to existing algorithms, we use it for texture filtering, JPEG deblocking, and detail enhancement.

Modern regularizers for image restoration are mostly nonquadratic and nonsmooth. They have been intensely researched and their capacity for promoting sparsity has been successfully exploited. In particular, nonquadratic regularizers are known to perform better than classical quadratic regularizers. However, in this work, we propose a quadratic regularizer of the form xTQx whose restoration capacity is superior to total-variation and Hessian regularization. The catch is that, unlike classical regularization (e.g. Tikhonov), the matrix Q is data-driven-it is computed from the observed image via a kernel (affinity) matrix. For linear restoration problems with quadratic data-fidelity (e.g. superresolution and deconvolution), the overall optimization reduces to solving a linear system; this can be done efficiently using conjugate gradient. The attractive aspect is that we are able to avoid the inner iterations in total-variation and Hessian regularization. In a sense, the proposed regularizer combines the computational efficiency of quadratic regularizers and the restoration (image modeling) power of nonquadratic regularizers.

We consider the problem of synthetically fusing a high-spatial, low-spectral resolution image with a low-spatial, high-spectral resolution image to achieve high spatial and spectral resolution. In practice, the images to be fused are usually misaligned and need to be registered before fusion is carried out. However, due to significant difference in spatial resolutions (between the input images), it can be difficult to register them accurately. We consider a variational framework for simultaneous registration and fusion along with regularization that is built upon a standard observation (forward) model. Using a mix of alternating minimization and proximal gradient descent, we obtain an algorithm in which we iteratively optimize over rotations/translations, the model mismatch, and the regularization term. Motivated by the “plug-and-play” paradigm for image restoration, we propose to replace (i) the alignment process by an efficient registration method, and (ii) the proximal map (of the regularizer) with a powerful denoiser. As the iterations proceed, we notice that better registration and regularization results in improved fusion. We demonstrate that our method is competitive with state-of-the-art fusion algorithms on standard datasets, and is particularly effective even for larger misalignments.

Plug-and-play (PnP) method is a recent paradigm for image regularization, where the proximal operator (associated with some given regularizer) in an iterative algorithm is replaced with a powerful denoiser. Algorithmically, this involves repeated inversion (of the forward model) and denoising until convergence. Remarkably, PnP regularization produces promising results for several restoration applications. However, a fundamental question in this regard is the theoretical convergence of the PnP iterations, since the algorithm is not strictly derived from an optimization framework. This question has been investigated in recent works, but there are still many unresolved problems. For example, it is not known if convergence can be guaranteed if we use generic kernel denoisers (e.g. nonlocal means) within the ISTA framework (PnP-ISTA). We prove that, under reasonable assumptions, fixed-point convergence of PnP-ISTA is indeed guaranteed for linear inverse problems such as deblurring, inpainting and superresolution (the assumptions are verifiable for inpainting). We compare our theoretical findings with existing results, validate them numerically, and explain their practical relevance.

In the classical bilateral filter, a range kernel is used together with a spatial kernel for smoothing out fine details while simultaneously preserving edges. More recently, it has been demonstrated that even coarse textures can be smoothed using joint bilateral filtering. In this paper, we demonstrate that the superior texture filtering results can be obtained by adapting the spatial kernel at each pixel. To the best of our knowledge, spatial adaptation (of the bilateral filter) has not been explored for texture smoothing. The rationale behind adapting the spatial kernel is that one cannot smooth beyond a certain level using a fixed spatial kernel, no matter how we manipulate the range kernel. In fact, we should simply aggregate more pixels using a sufficiently wide spatial kernel to locally enhance the smoothing. Based on this reasoning, we propose to use the classical bilateral filter for texture smoothing, where we adapt the width of the spatial kernel at each pixel. We describe a simple and efficient gradient-based rule for the latter task. The attractive aspect is that we are able to develop a fast algorithm that can accelerate the computations by an order without visibly compromising the filtering quality. We demonstrate that our method outperforms classical bilateral filtering, joint bilateral filtering, and other filtering methods, and is competitive with the optimization methods. We also present some applications of texture smoothing using the proposed method.

The bilateral filter is popularly used for image enhancement. By using a range kernel along with a spatial kernel, the filter is able to smooth images without excessive blurring of edges. It has been shown that the enhancement capacity of the filter can be boosted by adapting the width of the range kernel at each pixel. A fast algorithm for grayscale images was recently proposed for this so-called adaptive bilateral filter, which is otherwise computationally expensive. This can trivially be extended for color filtering using channelwise processing. However, developing an efficient algorithm that can exploit correlations between color channels is not straightforward. We show that such a fast algorithm can be developed by first expressing the filtering in terms of the local histogram and then approximating the latter by an uniform distribution. The distribution in question is along the direction of maximum variance in the RGB space, which we compute from the local covariance (this is done efficiently using power iterations). The local covariances in turn are computed using fast convolutions. To demonstrate the effectiveness of our fast algorithm, we apply it for sharpening, detail enhancement, and deblocking.

We consider the problem of enhancing images captured under low-light conditions. Several variational and filtering based solutions have been proposed for this problem that are based on the retinex model. The idea in retinex is to first estimate the illumination and reflectance from the observed image, enhance the illumination, and then combine it with the reflectance to get the rectified image. A variant of bilateral filtering, called bright-pass bilateral filtering (BPBF), can be used for illumination estimation. However, BPBF is computation intensive and takes up a significant amount of the processing time. Motivated by recent work, we propose a Fourier approximation of BPBF that can accelerate the filtering (by an order) without loss in visual quality. Experimental results demonstrate that our algorithm is sufficiently fast and can effectively enhance low-light images. In particular, our proposal is competitive with recent algorithms in terms of visual perception and quality metrics.

Image filtering is a fundamental preprocessing task in computer vision and image processing. While the dominant applications of kernel filtering are enhancement and denoising, it can also be used as a powerful regularizer for image reconstruction. In general, the brute-force implementations of kernel filtering is prohibitively expensive. They are often too slow for real-time applications. In the first half of the thesis, we propose fast algorithms for bilateral filtering (BLF) and nonlocal means (NLM). In particular, we demonstrate that by using the Fourier approximation of the underlying kernel, we can obtain state-of-the-art fast algorithms for BLF of grayscale images. We next extend the idea for fast filtering of color images, which involves the approximation of a three-dimensional kernel. We next propose a fast separable formulation for NLM of grayscale images. In the second half of the dissertation, we turn to some applications of kernel filtering. We introduce a scale-adaptive variant of BLF that is used for suppressing fine textures in images. We develop a fast implementation of a symmetrized variant of NLM that is used for regularization (i.e., as a prior) within the plug-and-play framework for image restoration. The core idea can be extended to other forms of kernel filtering.

Modern regularization techniques and iterative solvers have largely been the key to the success of Compressive Sensing (CS). Recently, deep neural networks (DNNs) with end-to-end training have shown promise for CS. However, because of their open-ended nature, it is difficult to ensure that the DNN output is consistent with the measurements. In contrast, iterative algorithms such as FISTA explicitly make use of the measurement model and are hence able to incorporate consistency. To strike a middle path, researchers have shown that the performance of traditional iterative solvers can be improved by formally replacing the proximal map at each iteration with powerful DNN denoisers. While existing denoisers are typically designed to handle additive white noise, the noise that the denoiser encounters during each iteration is highly correlated and difficult to characterize. Motivated by this observation, we propose to use iteration-dependent denoisers within the FISTA framework, i.e., we train separate DNNs that can specifically handle the noise encountered in the first few iterations. We are able to achieve state-of-the-art CS results with fewer iterations as result, while maintaining measurement consistency.

In hyperspectral image fusion, a high resolution multispectral (MS) image is combined with a low resolution hyperspectral (HS) image to obtain a high resolution HS image. In this work, we propose a "plug-and-play" framework for HS-MS fusion, where the inversion step at each iteration involves the solution of a linear system, and the regularization is performed using a high-dimensional kernel denoiser. The core contribution is the design of the denoiser, which can denoise an HS-image at low complexity using clustering and convolutions. In particular, it can exploit the inter-band correlations, which cannot be done using band-by-band denoising. An important technical aspect of our denoiser is that it can be expressed as the proximal map of a proper, closed, and convex regularizer, which guarantees the convergence of the plug-and-play iterations. Preliminary results suggest that we are competitive with state-of-the-art algorithms for HS-MS fusion in terms of speed and restoration accuracy.

In most state-of-the-art image restoration methods, the sum of a data-fidelity and a regularization term is optimized using an iterative algorithm such as ADMM (alternating direction method of multipliers). In recent years, the possibility of using denoisers for regularization has been explored in several works. A popular approach is to formally replace the proximal operator within the ADMM framework with some powerful denoiser. However, since most state-of-the-art denoisers cannot be posed as a proximal operator, one cannot guarantee the convergence of these so-called plug-and-play (PnP) algorithms. In fact, the theoretical convergence of PnP algorithms is an active research topic. In this letter, we consider the result of Chan et al. (IEEE TCI, 2017), where fixed-point convergence of an ADMM-based PnP algorithm was established for a class of denoisers. We argue that the original proof is incomplete, since convergence is not analyzed for one of the three possible cases outlined in the letter. Moreover, we explain why the argument for the other cases does not apply in this case. We give a different analysis to fill this gap, which firmly establishes the original convergence theorem.

The bilateral and nonlocal means filters are instances of kernel-based filters that are popularly used in image processing. It was recently shown that fast and accurate bilateral filtering of grayscale images can be performed using a low-rank approximation of the kernel matrix. More specifically, based on the eigendecomposition of the kernel matrix, the overall filtering was approximated using spatial convolutions, for which efficient algorithms are available. Unfortunately, this technique cannot be scaled to high-dimensional data such as color and hyperspectral images. This is simply because one needs to compute/store a large matrix and perform its eigendecomposition in this case. We show how this problem can be solved using the Nyström method, which is generally used for approximating the eigendecomposition of large matrices. The resulting algorithm can also be used for nonlocal means filtering. We demonstrate the effectiveness of our proposal for bilateral and nonlocal means filtering of color and hyperspectral images. In particular, our method is shown to be competitive with state-of-the-art fast algorithms, and moreover, it comes with a theoretical guarantee on the approximation error.

In the classical bilateral filter, a fixed Gaussian range kernel is used along with a spatial kernel for edge-preserving smoothing. We consider a generalization of this filter, the so-called adaptive bilateral filter, where the center and width of the Gaussian range kernel are allowed to change from pixel to pixel. Though this variant was originally proposed for sharpening and noise removal, it can also be used for other applications, such as artifact removal and texture filtering. Similar to the bilateral filter, the brute-force implementation of its adaptive counterpart requires intense computations. While several fast algorithms have been proposed in the literature for bilateral filtering, most of them work only with a fixed range kernel. In this paper, we propose a fast algorithm for adaptive bilateral filtering, whose complexity does not scale with the spatial filter width. This is based on the observation that the concerned filtering can be performed purely in range space using an appropriately defined local histogram. We show that by replacing the histogram with a polynomial and the finite range-space sum with an integral, we can approximate the filter using analytic functions. In particular, an efficient algorithm is derived using the following innovations: the polynomial is fitted by matching its moments to those of the target histogram (this is done using fast convolutions), and the analytic functions are recursively computed using integration-by-parts. Our algorithm can accelerate the brute-force implementation by at least , without perceptible distortions in the visual quality. We demonstrate the effectiveness of our algorithm for sharpening, JPEG deblocking, and texture filtering.

Cross-modal retrieval is gaining importance due to the availability of large amounts of multimedia data. Hashing-based techniques provide an attractive solution to this problem when the data size is large. For cross-modal retrieval, data from the two modalities may be associated with a single label or multiple labels, and in addition, may or may not have a one-to-one correspondence. This work proposes a simple hashing framework which has the capability to work with different scenarios while effectively capturing the semantic relationship between the data items. The work proceeds in two stages in which the first stage learns the optimum hash codes by factorizing an affinity matrix, constructed using the label information. In the second stage, ridge regression and kernel logistic regression is used to learn the hash functions for mapping the input data to the bit domain. We also propose a novel iterative solution for cases where the training data is very large, or when the whole training data is not available at once. Extensive experiments on single label data set like Wiki and multi-label datasets like MirFlickr, NUS-WIDE, Pascal, and LabelMe, and comparisons with the state-of-the-art, shows the usefulness of the proposed approach.

Existing fast algorithms for bilateral and nonlocal means filtering mostly work with grayscale images. They cannot easily be extended to high-dimensional data such as color and hyperspectral images, patch-based data, flow-fields, etc. In this paper, we propose a fast algorithm for high-dimensional bilateral and nonlocal means filtering. Unlike existing approaches, where the focus is on approximating the data (using quantization) or the filter kernel (via analytic expansions), we locally approximate the kernel using weighted and shifted copies of a Gaussian, where the weights and shifts are inferred from the data. The algorithm emerging from the proposed approximation essentially involves clustering and fast convolutions, and is easy to implement. Moreover, a variant of our algorithm comes with a guarantee (bound) on the approximation error, which is not enjoyed by existing algorithms.We present some results for high-dimensional bilateral and nonlocal means filtering to demonstrate the speed and accuracy of our proposal. Moreover, we also show that our algorithm can outperform state-of-the-art fast approximations in terms of accuracy and timing.

Several patch-based models have been proposed for image restoration in the literature. A common feature with these models is that patches are used for filtering or optimization, where the aggregation is often performed over a non-local (NL) neighborhood. We propose a NL patch-based regularizer, where patches are used (1) for computing weights between NL neighbors, and (2) for defining a TV-type norm in patch space. A general form of the latter construction was originally proposed by Peyre et al. and later studied by other authors. In most of these proposals, both the weights and the image are treated as variables, which makes the model non-convex. In particular, the corresponding numerical solvers cannot guarantee local optimality. On the other hand, our regularizer is convex. Along with an l2 data fidelity term, we apply the regularizer for denoising, deblurring and super-resolution, and develop an efficient ADMM solver for computing the global minimum. An interesting finding is that, while our model is weaker than the non-convex counterparts, the minimizer of the former is generally closer to the ground truth than the reconstruction from the latter. Moreover, we demonstrate that our regularizer can outperform existing regularization techniques for deblurring and super-resolution.

We consider the problem of approximating a truncated Gaussian kernel using Fourier (trigonometric) functions. The computation-intensive bilateral filter can be expressed using fast convolutions by applying such an approximation to its range kernel, where the truncation in question is the dynamic range of the input image. The error from such an approximation depends on the period, the number of sinusoids, and the coefficient of each sinusoid. For a fixed period, we recently proposed a model for optimizing the coefficients using least squares fitting. Following the compressive bilateral filter (CBF), we demonstrate that the approximation can be improved by taking the period into account during the optimization. The accuracy of the resulting filtering is found to be at least as good as the CBF, but significantly better for certain cases. The proposed approximation can also be used for non-Gaussian kernels, and it comes with guarantees on the filtering accuracy.

Due to availability of large amounts of multimedia data, cross-modal matching is gaining increasing importance. Hashing based techniques provide an attractive solution to this problem when the data size is large. Different scenarios of cross-modal matching are possible, for example, data from the different modalities can be associated with a single label or multiple labels, and in addition may or may not have one-to-one correspondence. Most of the existing approaches have been developed for the case where there is one-to-one correspondence between the data of the two modalities. In this paper, we propose a simple, yet effective generalized hashing framework which can work for all the different scenarios, while preserving the semantic distance between the data points. The approach first learns the optimum hash codes for the two modalities simultaneously, so as to preserve the semantic similarity between the data points, and then learns the hash functions to map from the features to the hash codes. Extensive experiments on single label dataset like Wiki and multi-label datasets like NUS-WIDE, Pascal and LabelMe under all the different scenarios and comparisons with the state-of-the-art shows the effectiveness of the proposed approach.

We consider the problem of aligning multiview scans obtained using a range scanner. The computational pipeline for this problem can be divided into two phases: (i) finding point-to-point correspondences between overlapping scans, and (ii) registration of the scans based on the correspondences. The focus of this work is on global registration in which the scans (modeled as point clouds) are required to be jointly registered in a common reference frame. We consider an optimization framework for global registration that is based on rank-constrained semidefinite programming. We propose to solve this semidefinite program using a non-convex variant of the ADMM (Alternating Direction Method of Multipliers) algorithm. This results in an efficient and scalable iterative method that requires just one eigendecompostion per iteration. We present simulations results on synthetic 3D models, using both clean and noisy correspondences. An interesting finding is that the algorithm is robust to wrong correspondences - it yields high-quality reconstructions even when a significant fraction of the correspondences are corrupted. Finally, by using ICP to infer the correspondences, we present some promising preliminary results for multiview reconstruction.

We consider the task of removing the effect of camera shake during a long exposure. Technically, this is a blind deconvolution problem in which both the image and the motion blur have to be jointly inferred. Several algorithms have been proposed till date for removing camera shake that work with one or more images. However, most of these algorithms are computationally expensive and hence cannot be used in real-time. In this work, we propose a simple and cheap algorithm that can effectively recover the original sharp image from multiple burst images (captured using the burst modality of modern cameras). In summary, we pick selected images from the burst (using ideas from lucky imaging), which are then aggregated using the discrete cosine transform (similar to the idea of Fourier burst accumulation). We present some preliminary results and comparisons to demonstrate the effectiveness of the proposal.

Several useful algorithms for image filtering involve non-linear processing of high-dimensional data. Instances of these so-called high-dimensional filters are the bilateral, joint-bilateral, and non-local means filters. Real-time implementation of high-dimensional filters can be challenging. In this paper, we present a simple and fast algorithm for generic high-dimensional filtering. The algorithm is based on a linearization mechanism, which allows us to approximate the high-dimensional filtering using a series of spatial convolutions. We use clustering for the linearization, whereby we are able to exploit the strong correlation between the components of the high-dimensional image. The highlight of our method is that we can prove that the approximation error (the gap between the fast approximation and the exact filtering) vanishes with the increase in the number of clusters. To the best of our knowledge, this is the first algorithm for high-dimensional filtering that enjoys this theoretical guarantee. In fact, we provide empirical evidence which suggests that this basic requirement is not met by the state-of-the-art Adaptive Manifolds algorithm. We use the proposed algorithm for edge-preserving smoothing and denoising of color and hyperspectral images. The results demonstrate that our algorithm is competitive with existing fast algorithms.

In non‐local means (NLM), each pixel is denoised by performing a weighted averaging of its neighbouring pixels, where the weights are computed using image patches. The authors demonstrate that the denoising performance of NLM can be improved by pruning the neighbouring pixels, namely, by rejecting neighbouring pixels whose weights are below a certain threshold . While pruning can potentially reduce pixel averaging in uniform‐intensity regions, they demonstrate that there is generally an overall improvement in the denoising performance. In particular, the improvement comes from pixels situated close to edges and corners. The success of the proposed method strongly depends on the choice of the global threshold , which in turn depends on the noise level and the image characteristics. They show how Stein's unbiased estimator of the mean‐squared error can be used to optimally tune , at a marginal computational overhead. They present some representative denoising results to demonstrate the superior performance of the proposed method over NLM and its variants.

A fundamental problem that comes up in computer vision, image processing, manifold learning, and sensor networks is that of registering multiple point sets using rigid transforms. A standard result in this regard is that the least-square formulation of the registration problem admits a closed-form solution for two point sets. However, since the group of rigid transforms is not convex, solving the least-square optimization for multiple point sets is computationally challenging. It was recently demonstrated that the least-square formulation can be relaxed into a tractable semidefinite program, and that the relaxation is provably tight under certain assumptions. The difficulty is that standard solvers for semidefinite programming (e.g., interior-point solvers) cannot be scaled to handle large-sized problems. In this letter, we propose an iterative solver based on variable splitting and the alternating direction method of multipliers. Since each iteration essentially involves an eigendecomposition, the proposed solver can be scaled to problems that are beyond the reach of interior-point solvers. We present results on simulated and real data to demonstrate the potential of the solver.

In this paper, we consider a natural extension of the edge-preserving bilateral filter for vector-valued images. The direct computation of this non-linear filter is slow in practice. We demonstrate how a fast algorithm can be obtained by first approximating the Gaussian kernel of the bilateral filter using raised-cosines, and then using Monte Carlo sampling. We present simulation results on color images to demonstrate the accuracy of the algorithm and the speedup over the direct implementation.

It was demonstrated in earlier work that, by approximating its range kernel using shiftable functions, the nonlinear bilateral filter can be computed using a series of fast convolutions. Previous approaches based on shiftable approximation have, however, been restricted to Gaussian range kernels. In this work, we propose a novel approximation that can be applied to any range kernel, provided it has a pointwise-convergent Fourier series. More specifically, we propose to approximate the Gaussian range kernel of the bilateral filter using a Fourier basis, where the coefficients of the basis are obtained by solving a series of least-squares problems. The coefficients can be efficiently computed using a recursive form of the QR decomposition. By controlling the cardinality of the Fourier basis, we can obtain a good tradeoff between the run-time and the filtering accuracy. In particular, we are able to guarantee subpixel accuracy for the overall filtering, which is not provided by the most existing methods for fast bilateral filtering. We present simulation results to demonstrate the speed and accuracy of the proposed algorithm.

The bilateral filter is a non-linear filter that uses a range filter along with a spatial filter to perform edge-preserving smoothing of images. A direct computation of the bilateral filter requires O(S) operations per pixel, where S is the size of the support of the spatial filter. In this paper, we present a fast and provably accurate algorithm for approximating the bilateral filter when the range kernel is Gaussian. In particular, for box and Gaussian spatial filters, the proposed algorithm can cut down the complexity to O(1) per pixel for any arbitrary S . The algorithm has a simple implementation involving N+1 spatial filterings, where N is the approximation order. We give a detailed analysis of the filtering accuracy that can be achieved by the proposed approximation in relation to the target bilateral filter. This allows us to estimate the order N required to obtain a given accuracy. We also present comprehensive numerical results to demonstrate that the proposed algorithm is competitive with the state-of-the-art methods in terms of speed and accuracy.

In this paper, we describe an algorithm for sensor network localization (SNL) that proceeds by dividing the whole network into smaller subnetworks, then localizes them in parallel using some fast and accurate algorithm, and finally registers the localized subnetworks in a global coordinate system. We demonstrate that this divide-and-conquer algorithm can be used to leverage existing high-precision SNL algorithms to large-scale networks, which could otherwise only be applied to small-to-medium sized networks. The main contribution of this paper concerns the final registration phase. In particular, we consider a least-squares formulation of the registration problem (both with and without anchor constraints) and demonstrate how this otherwise non-convex problem can be relaxed into a tractable convex program. We provide some preliminary simulation results for large-scale SNL demonstrating that the proposed registration algorithm (together with an accurate localization scheme) offers a good tradeoff between run time and accuracy.

The Euclidean Median (EM) of a set of points Ω in an Euclidean space is the point x minimizing the (weighted) sum of the Euclidean distances of x to the points in Ω. While there exits no closed-form expression for the EM, it can nevertheless be computed using iterative methods such as the Weiszfeld algorithm. The EM has classically been used as a robust estimator of centrality for multivariate data. It was recently demonstrated that the EM can be used to perform robust patch-based denoising of images by generalizing the popular Non-Local Means algorithm. In this paper, we propose a novel algorithm for computing the EM (and its box-constrained counterpart) using variable splitting and the method of augmented Lagrangian. The attractive feature of this approach is that the subproblems involved in the ADMM-based optimization of the augmented Lagrangian can be resolved using simple closed-form projections. The proposed ADMM solver is used for robust patch-based image denoising and is shown to exhibit faster convergence compared to an existing solver.

The bilateral filter is a versatile non-linear filter that has found diverse applications in image processing, computer vision, computer graphics, and computational photography. A common form of the filter is the Gaussian bilateral filter in which both the spatial and range kernels are Gaussian. A direct implementation of this filter requires O(σ2) operations per pixel, where σ is the standard deviation of the spatial Gaussian. In this paper, we propose an accurate approximation algorithm that can cut down the computational complexity to O(1) per pixel for any arbitrary σ (constant-time implementation). This is based on the observation that the range kernel operates via the translations of a fixed Gaussian over the range space, and that these translated Gaussians can be accurately approximated using the so-called Gauss-polynomials. The overall algorithm emerging from this approximation involves a series of spatial Gaussian filtering, which can be efficiently implemented (in parallel) using separability and recursion. We present some preliminary results to demonstrate that the proposed algorithm compares favorably with some of the existing fast algorithms in terms of speed and accuracy.

The bilateral filter is known to be quite effective in denoising images corrupted with small dosages of additive Gaussian noise. The denoising performance of the filter, however, is known to degrade quickly with the increase in noise level. Several adaptations of the filter have been proposed in the literature to address this shortcoming, but often at a substantial computational overhead. In this paper, we report a simple pre-processing step that can substantially improve the denoising performance of the bilateral filter, at almost no additional cost. The modified filter is designed to be robust at large noise levels, and often tends to perform poorly below a certain noise threshold. To get the best of the original and the modified filter, we propose to combine them in a weighted fashion, where the weights are chosen to minimize (a surrogate of) the oracle mean-squared-error (MSE). The optimally-weighted filter is thus guaranteed to perform better than either of the component filters in terms of the MSE, at all noise levels. We also provide a fast algorithm for the weighted filtering. Visual and quantitative denoising results on standard test images are reported which demonstrate that the improvement over the original filter is significant both visually and in terms of PSNR. Moreover, the denoising performance of the optimally-weighted bilateral filter is competitive with the computation-intensive non-local means filter.

It was recently demonstrated in [13] that the denoising performance of Non-Local Means (NLM) can be improved at large noise levels by replacing the mean by the robust Euclidean median. Numerical experiments on synthetic and natural images showed that the latter consistently performed better than NLM beyond a certain noise level, and significantly so for images with sharp edges. The Euclidean mean and median can be put into a common regression (on the patch space) framework, in which the ℓ2norm of the residuals is considered in the former, while the ℓ1norm is considered in the latter. The natural question then is what happens if we consider ℓp(0 <; p <; 1) regression? We investigate this possibility in this paper.

The Riesz transform is a natural multidimensional extension of the Hilbert transform, and it has been the object of study for many years due to its nice mathematical properties. More recently, the Riesz transform and its variants have been used to construct complex wavelets and steerable wavelet frames in higher dimensions. The flip side of this approach, however, is that the Riesz transform of a wavelet often has slow decay. One can nevertheless overcome this problem by requiring the original wavelet to have sufficient smoothness, decay, and vanishing moments. In this paper, we derive necessary conditions in terms of these three properties that guarantee the decay of the Riesz transform and its variants, and, as an application, we show how the decay of the popular Simoncelli wavelets can be improved by appropriately modifying their Fourier transforms. By applying the Riesz transform to these new wavelets, we obtain steerable frames with rapid decay.

Recently, it was demonstrated in , that the robustness of the classical Non-Local Means (NLM) algorithm can be improved by incorporatinglp(0p≤ 2) regression into the NLM framework. This general optimization framework, called Non-Local Patch Regression (NLPR), contains NLM as a special case. Denoising results on synthetic and natural images show that NLPR consistently performs better than NLM beyond a moderate noise level, and significantly so whenpis close to zero. An iteratively reweighted least-squares (IRLS) algorithm was proposed for solving the regression problem in NLPR, where the NLM output was used to initialize the iterations. Based on exhaustive numerical experiments, we observe that the IRLS algorithm is globally convergent (for arbitrary initialization) in the convex regime 1 ≤p≤ 2, and locally convergent (e.g., fails rarely using NLM initialization) in the non-convex regime 0p<; 1. In this letter, we study the cost associated with the IRLS updates, and this, along with the framework of bounded optimization, is used to analyze the convergence of the algorithm.

A direct implementation of the bilateral filter requires O(σ(s)(2)) operations per pixel, where σ(s) is the (effective) width of the spatial kernel. A fast implementation of the bilateral filter that required O(1) operations per pixel with respect to σ(s) was recently proposed. This was done by using trigonometric functions for the range kernel of the bilateral filter, and by exploiting their so-called shiftability property. In particular, a fast implementation of the Gaussian bilateral filter was realized by approximating the Gaussian range kernel using raised cosines. Later, it was demonstrated that this idea could be extended to a larger class of filters, including the popular non-local means filter. As already observed, a flip side of this approach was that the run time depended on the width σ(r) of the range kernel. For an image with dynamic range [0,T], the run time scaled as O(T(2)/σ(2)(r)) with σ(r). This made it difficult to implement narrow range kernels, particularly for images with large dynamic range. In this paper, we discuss this problem, and propose some simple steps to accelerate the implementation, in general, and for small σ(r) in particular. We provide some experimental results to demonstrate the acceleration that is achieved using these modifications.

In this letter, we note that the denoising performance of Non-Local Means (NLM) can be improved at large noise levels by replacing the mean by the Euclidean median. We call this new denoising algorithm the Non-Local Euclidean Medians (NLEM). At the heart of NLEM is the observation that the median is more robust to outliers than the mean. In particular, we provide a simple geometric insight that explains why NLEM performs better than NLM in the vicinity of edges, particularly at large noise levels. NLEM can be efficiently implemented using iteratively reweighted least squares, and its computational complexity is comparable to that of NLM. We provide some preliminary results to study the proposed algorithm and to compare it with NLM.

It is well-known that box filters can be efficiently computed using pre-integration and local finite-differences. By generalizing this idea and by combining it with a nonstandard variant of the central limit theorem, we had earlier proposed a constant-time or O(1) algorithm that allowed one to perform space-variant filtering using Gaussian-like kernels. The algorithm was based on the observation that both isotropic and anisotropic Gaussians could be approximated using certain bivariate splines called box splines. The attractive feature of the algorithm was that it allowed one to continuously control the shape and size (covariance) of the filter, and that it had a fixed computational cost per pixel, irrespective of the size of the filter. The algorithm, however, offered a limited control on the covariance and accuracy of the Gaussian approximation. In this paper, we propose some improvements of our previous algorithm.

It was recently demonstrated in that the nonlinear bilateral filter can be efficiently implemented using a constant-time orO(1) algorithm. At the heart of this algorithm was the idea of approximating the Gaussian range kernel of the bilateral filter using trigonometric functions. In this letter, we explain how the idea in can be extended to few other linear and nonlinear filters . While some of these filters have received a lot of attention in recent years, they are known to be computationally intensive. To extend the idea in , we identify a central property of trigonometric functions, called shiftability, that allows us to exploit the redundancy inherent in the filtering operations. In particular, using shiftable kernels, we show how certain complex filtering can be reduced to simply that of computing the moving sum of a stack of images. Each image in the stack is obtained through an elementary pointwise transform of the input image. This has a two-fold advantage. First, we can use fast recursive algorithms for computing the moving sum , , and, secondly, we can use parallel computation to further speed up the computation. We also show how shiftable kernels can also be used to approximate the (nonlinearshiftable) Gaussian kernel that is ubiquitously used in image filtering.

It is well known that spatial averaging can be realized (in space or frequency domain) using algorithms whose complexity does not scale with the size or shape of the filter. These fast algorithms are generally referred to as constant-time or O(1) algorithms in the image-processing literature. Along with the spatial filter, the edge-preserving bilateral filter involves an additional range kernel. This is used to restrict the averaging to those neighborhood pixels whose intensity are similar or close to that of the pixel of interest. The range kernel operates by acting on the pixel intensities. This makes the averaging process nonlinear and computationally intensive, particularly when the spatial filter is large. In this paper, we show how the O(1) averaging algorithms can be leveraged for realizing the bilateral filter in constant time, by using trigonometric range kernels. This is done by generalizing the idea presented by Porikli, i.e., using polynomial kernels. The class of trigonometric kernels turns out to be sufficiently rich, allowing for the approximation of the standard Gaussian bilateral filter. The attractive feature of our approach is that, for a fixed number of terms, the quality of approximation achieved using trigonometric kernels is much superior to that obtained by Porikli using polynomials.

The efficient realization of linear space-variant (non-convolution) filters is a challenging computational problem in image processing. In this paper, we demonstrate that it is possible to filter an image with a Gaussian-like elliptic window of varying size, elongation and orientation using a fixed number of computations per pixel. The associated algorithm, which is based upon a family of smooth compactly supported piecewise polynomials, the radially-uniform box splines, is realized using preintegration and local finite-differences. The radially-uniform box splines are constructed through the repeated convolution of a fixed number of box distributions, which have been suitably scaled and distributed radially in an uniform fashion. The attractive features of these box splines are their asymptotic behavior, their simple covariance structure, and their quasi-separability. They converge to Gaussians with the increase of their order, and are used to approximate anisotropic Gaussians of varying covariance simply by controlling the scales of the constituent box distributions. Based upon the second feature, we develop a technique for continuously controlling the size, elongation and orientation of these Gaussian-like functions. Finally, the quasi-separable structure, along with a certain scaling property of box distributions, is used to efficiently realize the associated space-variant elliptical filtering, which requires O(1) computations per pixel irrespective of the shape and size of the filter.

We provide an amplitude-phase representation of the dual-tree complex wavelet transform by extending the fixed quadrature relationship of the dual-tree wavelets to arbitrary phase-shifts using the fractional Hilbert transform (fHT). The fHT is a generalization of the Hilbert transform that extends the quadrature phase-shift action of the latter to arbitrary phase-shifts a real shift parameter controls this phase-shift action. Next, based on the proposed representation and the observation that the fHT operator maps well-localized B-spline wavelets (that resemble Gaussian-windowed sinusoids) into B-spline wavelets of the same order but different shift, we relate the corresponding dual-tree scheme to the paradigm of multiresolution windowed Fourier analysis.

We propose a novel method of constructing exact Hilbert transform (HT) pairs of wavelet bases using fractional B- splines and state necessary and sufficient conditions for generating such wavelet pairs. In particular, we demonstrate how HT pairs of biorthogonal wavelet bases of L2(K) can be constructed using well-localized scaling functions with identical Riesz bounds. Finally, we illustrate this concept by constructing a family of analytic Gabor-like wavelets that exhibit near optimal time-frequency localization.

We demonstrate that it is possible to filter an image with an elliptic window of varying size, elongation and orientation with a fixed computational cost per pixel. Our method involves the application of a suitable global pre-integrator followed by a pointwise-adaptive localization mesh. We present the basic theory for the ID case using a B-spline formalism and then appropriately extend it to 2D using radially-uniform box splines. The size and ellipticity of these radially-uniform box splines is adaptively controlled. Moreover, they converge to Gaussians as the order increases. Finally, we present a fast and practical directional filtering algorithm that has the capability of adapting to the local image features.