Search

In image processing, the rapid approximate solution of variational problems involving generic data-fitting terms is often of practical relevance, for example in real-time applications. Variational solvers based on diffusion schemes or the Euler-Lagrange equations are too slow and restricted in the types of data-fitting terms. Here, we present a filter-based approach to reduce variational energies that contain generic data-fitting terms, but are restricted to specific regularizations. Our approach is based on reducing the regularization part of the variational energy, while guaranteeing non-increasing total energy. This is applicable to regularization-dominated models, where the data-fitting energy initially increases, while the regularization energy initially decreases. We present fast discrete filters for regularizers based on Gaussian curvature, mean curvature, and total variation. These pixel-local filters can be used to rapidly reduce the energy of the full model. We prove the convergence of the resulting iterative scheme in a greedy sense, and we show several experiments to demonstrate applications in image-processing problems involving regularization-dominated variational models. [ABSTRACT FROM AUTHOR]

In this work, we revisit fast dimension reduction approaches, as with random projections and random sampling. Our goal is to summarize the data to decrease computational costs and memory footprint of subsequent analysis. Such dimension reduction can be very efficient when the signals of interest have a strong structure, such as with images. We focus on this setting and investigate feature clustering schemes for data reductions that capture this structure. An impediment to fast dimension reduction is then that good clustering comes with large algorithmic costs. We address it by contributing a linear-time agglomerative clustering scheme, Recursive Nearest Agglomeration (ReNA). Unlike existing fast agglomerative schemes, it avoids the creation of giant clusters. We empirically validate that it approximates the data as well as traditional variance-minimizing clustering schemes that have a quadratic complexity. In addition, we analyze signal approximation with feature clustering and show that it can remove noise, improving subsequent analysis steps. As a consequence, data reduction by clustering features with ReNA yields very fast and accurate models, enabling to process large datasets on budget. Our theoretical analysis is backed by extensive experiments on publicly-available data that illustrate the computation efficiency and the denoising properties of the resulting dimension reduction scheme. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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 $\ddot{\text{o}}$ 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. [ABSTRACT FROM AUTHOR]

In this paper a special class of functions called smoothlets is presented. They are defined as a generalization of wedgelets and second-order wedgelets. Unlike all known geometrical methods used in adaptive image approximation, smoothlets are continuous functions. They can adapt to location, size, rotation, curvature, and smoothness of edges. The M-term approximation of smoothlets is O(M^-3). In this paper, an image compression scheme based on the smoothlet transform is also presented. From the theoretical considerations and experiments, both described in the paper, it follows that smoothlets can assure better image compression than the other known adaptive geometrical methods, namely, wedgelets and second-order wedgelets. [ABSTRACT FROM AUTHOR]

Multiple-view triangulation by $\ell _\infty$ minimisation has become established in computer vision. State-of-the-art $\ell _\infty$ triangulation algorithms exploit the quasiconvexity of the cost function to derive iterative update rules that deliver the global minimum. Such algorithms, however, can be computationally costly for large problem instances that contain many image measurements, e.g., from web-based photo sharing sites or long-term video recordings. In this paper, we prove that $\ell _\infty$ triangulation admits a coreset approximation scheme, which seeks small representative subsets of the input data called coresets. A coreset possesses the special property that the error of the $\ell _\infty$ solution on the coreset is within known bounds from the global minimum. We establish the necessary mathematical underpinnings of the coreset algorithm, specifically, by enacting the stopping criterion of the algorithm and proving that the resulting coreset gives the desired approximation accuracy. On large-scale triangulation problems, our method provides theoretically sound approximate solutions. Iterated until convergence, our coreset algorithm is also guaranteed to reach the true optimum. On practical datasets, we show that our technique can in fact attain the global minimiser much faster than current methods. [ABSTRACT FROM AUTHOR]

This letter introduces a practical algorithm called fast M-term pursuit (FMTP) for sparse approximation in redundant dictionaries. As an extension of the popular matching pursuit (MP), FMTP presents a good trade-off between high approximation performance and efficient implementation. Based on the effective estimation of the incoherence among dictionary atoms, FMTP combines the strength of both sequential and parallel techniques. Experimental results show that with slight approximation losses, FMTP yields significant speed improvements over the latest fast algorithms. It achieves a speedup of 63.46 in comparison with the MP approach. [ABSTRACT FROM AUTHOR]

Improving the modeling of natural images is important to go beyond the state-of-the-art for many image processing tasks such as compression, denoising, inverse problems, and texture synthesis. Natural images are composed of intricate patterns such as regular areas, edges, junctions, oriented oscillations, and textures. Processing efficiently such a wide range of regularities requires methods that are adaptive to the geometry of the image. This adaptivity can be achieved using sparse representations in a redundant dictionary. The geometric adaptivity is important to search for efficient representations in a structured dictionary. Another way to capture this geometry is through non-local interactions between patches in the image. The resulting non-local energies can be used to perform an adaptive image restoration. This paper reviews these emerging technics and shows the interplay between sparse and non-local regularizations. [ABSTRACT FROM PUBLISHER]

X-ray scatter compensation is a very desirable technique in flat-panel X-ray imaging and cone-beam computed tomography. State-of-the-art U-net based scatter removal approaches yielded promising results. However, as there are no physics’ constraints applied to the output of the U-Net, it cannot be ruled out that it yields spurious results. Unfortunately, in the context of medical imaging, those may be misleading and could lead to wrong conclusions. To overcome this problem, we propose to embed B-splines as a known operator into neural networks. This inherently constrains their predictions to well-behaved and smooth functions. In a study using synthetic head and thorax data as well as real thorax phantom data, we found that our approach performed on par with U-net when comparing both algorithms based on quantitative performance metrics. However, our approach not only reduces runtime and parameter complexity, but we also found it much more robust to unseen noise levels. While the U-net responded with visible artifacts, the proposed approach preserved the X-ray signal’s frequency characteristics. [ABSTRACT FROM AUTHOR]

Approximate computing is an emerging paradigm that, by relaxing the requirement for full accuracy, offers benefits in terms of design area and power consumption. This paradigm is particularly attractive in applications where the underlying computation has inherent resilience to small errors. Such applications are abundant in many domains, including machine learning, computer vision, and signal processing. In circuit design, a major challenge is the capability to synthesize the approximate circuits automatically without manually relying on the expertise of designers. In this work, we review methods devised to synthesize approximate circuits, given their exact functionality and an approximability threshold. We summarize strategies for evaluating the error that circuit simplification can induce on the output, which guides synthesis techniques in choosing the circuit transformations that lead to the largest benefit for a given amount of induced error. We then review circuit simplification methods that operate at the gate or Boolean level, including those that leverage classical Boolean synthesis techniques to realize the approximations. We also summarize strategies that take high-level descriptions, such as C or behavioral Verilog, and synthesize approximate circuits from these descriptions. [ABSTRACT FROM AUTHOR]

Relaxing the traditional abstraction of "near-perfect" accuracy in hardware design can yield significant gains in efficiency, area, and performance. To exploit this opportunity, there is a need for design abstractions and synthesis tools that can systematically incorporate approximation in hardware design. The authors define Axilog, a set of language extensions for Verilog that provides the necessary syntax and semantics for approximate hardware design and reuse. Axilog lets designers safely relax the accuracy requirements in the design while keeping the critical parts strictly precise. Axilog is coupled with a Safety Inference Analysis that automatically infers the safe-to-approximate gates and connections from the annotations. The analysis provides formal guarantees that the safe-to-approximate parts of the design strictly adhere to the designer's intentions. The authors devise two synthesis flows that leverage Axilog's framework for safe approximation; one by relaxing the timing requirements and the other through gate resizing. They evaluate Axilog using a diverse set of benchmarks that gain 1.54× average energy savings and 1.82× average area reduction with 10 percent output quality loss. The results show that the intuitive nature of the language extensions coupled with the automated analysis enables safe approximation of designs even with thousands of lines of code. [ABSTRACT FROM PUBLISHER]

Building correct, efficient systems that reason about the approximations produced by sensors, machine learning, big data, humans, and approximate hardware and software requires new standards and abstractions. The Uncertain software abstraction aims to tackle these pervasive correctness, optimization, and programmability problems and guide hardware and software designers in producing estimates [ABSTRACT FROM PUBLISHER]

We present a general Fourier-based method which provides an accurate prediction of the approximation error, when the derivative of a signal s(t) is continuously reconstructed from uniform point samples or generalized measurements on s. This formalism applies to a wide class of convolution-based techniques. It provides a key tool, the frequency error kernel, for designing computationally efficient reconstruction schemes which are near optimal in the least-squares sense. [ABSTRACT FROM AUTHOR]

We show that \Delta\Sigma modulators can be interpreted as heuristic solvers for a particular class of optimization problems. Then, we exploit this theoretical result to propose a novel technique to deal with very large unconstrained discrete quadratic programming (UDQP) problems characterized by quadratic forms entailing a circulant matrix. The result is a circuit-based optimization approach involving a recast of the original problem into signal processing specifications, then tackled by the systematic design of an electronic system. This is reminiscent of analog computing, where untreatable differential equations were solved by designing electronic circuits analog to them. The approach can return high quality suboptimal solutions even when many hundreds of variables are considered and proved faster than conventional empirical optimization techniques. Detailed examples taken from two different domains illustrate that the range of manageable problems is large enough to cover practical applications. [ABSTRACT FROM AUTHOR]

In this paper, we present novel algorithms for statistically robust interpolation and approximation of diffusion tensors--which are symmetric positive definite (SPD) matrices--and use them in developing a significant extension to an existing probabilistic algorithm for scalar field segmentation, in order to segment diffusion tensor magnetic resonance imaging (DT-MRI) datasets. Using the Riemannian metric on the space of SPD matrices, we present a novel and robust higher order (cubic) continuous tensor product of B-splines algorithm to approximate the SPD diffusion tensor fields. The resulting approximations are appropriately dubbed tensor splines. Next, we segment the diffusion tensor field by jointly estimating the label (assigned to each voxel) field, which is modeled by a Gauss Markov measure field (GMMF) and the parameters of each smooth tensor spline model representing the labeled regions. Results of interpolation, approximation, and segmentation are presented for synthetic data and real diffusion tensor fields from an isolated rat hippocampus, along with validation. We also present comparisons of our algorithms with existing methods and show significantly improved results in the presence of noise as well as outliers. [ABSTRACT FROM AUTHOR]

Most signal processing applications are based on discrete-time signals although the origin of many sources of information is analog. In this paper, we consider the task of signal representation by a set of functions. Focusing on the representation coefficients of the original continuous-time signal, the question considered herein is to what extent the sampling process keeps algebraic relations, such as inner product, intact. By interpreting the sampling process as a bounded operator, a vector-like interpretation for this approximation problem has been derived, giving rise to an optimal discrete approximation scheme different from the Riemann-type sum often used. The objective of this optimal scheme is in the min-max sense and no bandlimitedness constraints are imposed. Tight upper bounds on this optimal and the Riemann-type sum approximation schemes are then derived. We further consider the case of a finite number of samples and formulate a closed-form solution for such a case. The results of this work provide a tool for finding the optimal scheme for approximating an L2 inner product, and to determine the maximum potential representation error induced by the sampling process. The maximum representation error can also be determined for the Riemann-type sum approximation scheme. Examples of practical applications are given and discussed [ABSTRACT FROM PUBLISHER]

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 [1] and hex-splines [2], 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. [ABSTRACT FROM AUTHOR]

In this paper, a novel technique for the approximation of three-dimensional (3-D) antenna radiation patterns is presented. The proposed method combines the two principal cuts in order to acquire an adequate estimate of the 3-D antenna radiation solid. The absolute error from the theoretical solution is analyzed along with other statistical measures for various types of antenna structures, namely omni-directional and directive arrays. The performance of the method is compared against other existing extrapolation algorithms. The proposed technique exhibits low approximation errors and is easily integrated into 3-D radio propagation planning tools (such as ray-tracing algorithms). [ABSTRACT FROM AUTHOR]

We present a method for the hierarchical approximation of functions in one, two, or three variables based on the finite element method (Ritz approximation). Starting with a set of data sites with associated function, we first determine a smooth (scattereddata) interpolant. Next, we construct an initial triangulation by triangulating the region bounded by the minimal subset of data sites defining the convex hull of all sites. We insert only original data sites, thus reducing storage requirements. For each triangulation, we solve a minimization problem: computing the best linear spline approximation of the interpolant of all data, based on a functional involving function values and first derivatives. The error of a best linear spline approximation is computed in a Sobolev-like norm, leading to element-specific error values. We use these interval/triangle/tetrahedron-specific values to identify the element to subdivide next. The subdivision of an element with largest error value requires the recomputation of all spline coefficients due to the global nature of the problem. We improve efficiency by 1) subdividing multiple elements simultaneously and 2) by using a sparse-matrix representation and system solver. [ABSTRACT FROM AUTHOR]

In this paper, we study the spectrum assignment problem for wireless access networks. We assume that each secondary user will bid a certain value for exclusive usage of some spectrum channels for a certain time period or for a certain time duration. A secondary user may also require the exclusive usage of a subset of channels, or require the exclusive usage of a certain number of channels. Thus, several versions of problems are formulated under various different assumptions. For the majority of problems, we design PTAS or efficient constant-approximation algorithms such that overall profit is maximized. Here, the profit is defined as the total bids of all satisfied secondary users. As a side product of our algorithms, we are able to show that a previously studied Scheduling Split Interval Problem (SSIP) [CHECK END OF SENTENCE], in which each job is composed of t intervals, cannot be approximated within O(t^1-\epsilon ) for any small \epsilon >0 unless NP=ZPP. Opportunistic spectrum usage, although a promising technology, could suffer from the selfish behavior of secondary users. In order to improve opportunistic spectrum usage, we then propose to combine the game theory with wireless modeling. We show how to design a truthful mechanism based on all of these algorithms such that the best strategy of each secondary user to maximize its own profit is to truthfully report its actual bid. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM PUBLISHER]