Search

Image registration matches the features of two images by minimizing the intensity difference, so that useful and complementary information can be extracted from the mapping. However, in real life problems, images may be affected by the imaging environment, such as varying illumination and noise during the process of imaging acquisition. This may lead to the local intensity distortion, which makes it meaningless to minimize the intensity difference in the traditional registration framework. To address this problem, we propose a variational model for joint image registration and intensity correction. Based on this model, a related greedy matching problem is solved by introducing a multiscale approach for joint image registration and intensity correction. An alternating direction method (ADM) is proposed to solve each multiscale step, and the convergence of the ADM method is proved. For the numerical implementation, a coarse-to-fine strategy is further proposed to accelerate the numerical algorithm, and the convergence of the proposed coarse-to-fine strategy is also established. Some numerical tests are performed to validate the efficiency of the proposed algorithm. [ABSTRACT FROM AUTHOR]

We present the derivation, implementation, and analysis of a multiresolution adaptive grid framework for numerical simulations on octree-based three-dimensional block-structured collocated grids with distributed computational architectures. Our approach provides a consistent handling of nonlifted and lifted interpolating wavelets of arbitrary order demonstrated using second-, fourth-, and sixth-order wavelets, combined with standard finite-difference-based discretization op-erators. We first validate that the wavelet family used provides strict and explicit error control when coarsening the grid, and show that lifting wavelets increase the grid compression rate while conserving discrete moments across levels. Further, we demonstrate that high-order PDE discretization schemes combined with sufficiently high-order wavelets retain the expected convergence order even at resolution jumps. We then simulate the advection of a scalar to analyze convergence for the temporal evolution of a PDE. The results shows that our wavelet-based refinement criterion is successful at controlling the overall error while the coarsening criterion is effective at retaining the relevant information on a compressed grid. Our software exploits a block-structured grid data structure for efficient multilevel operations, combined with a parallelization strategy that relies on a one-sided MPI-RMA communication approach with active post-start-complete-wait synchronization. Using performance tests up to 16,384 cores, we demonstrate that this leads to a highly scalable performance. The associated code is available under a BSD-3 license at https://github.com/vanreeslab/murphy. [ABSTRACT FROM AUTHOR]

We introduce a near-linear complexity (geometric and meshless/algebraic) multigrid/multiresolution method for PDEs with rough (L1) coefficients with rigorous a priori accuracy and performance estimates. The method is discovered through a decision/game theory formulation of the problems of (1) identifying restriction and interpolation operators, (2) recovering a signal from incomplete measurements based on norm constraints on its image under a linear operator, and (3) gambling on the value of the solution of the PDE based on a hierarchy of nested measurements of its solution or source term. The resulting elementary gambles form a hierarchy of (deterministic) basis functions of H1 0 () (gamblets) that (1) are orthogonal across subscales/subbands with respect to the scalar product induced by the energy norm of the PDE, (2) enable sparse compression of the solution space in H1 0 (), and (3) induce an orthogonal multiresolution operator decomposition. The operating diagram of the multigrid method is that of an inverted pyramid in which gamblets are computed locally (by virtue of their exponential decay) and hierarchically (from fine to coarse scales) and the PDE is decomposed into a hierarchy of independent linear systems with uniformly bounded condition numbers. The resulting algorithm is parallelizable both in space (via localization) and in bandwidth/subscale (subscales can be computed independently from each other). Although the method is deterministic, it has a natural Bayesian interpretation under the measure of probability emerging (as a mixed strategy) from the information game formulation, and multiresolution approximations form a martingale with respect to the filltration induced by the hierarchy of nested measurements. [ABSTRACT FROM AUTHOR]

We present a detailed comparison between two adaptive numerical approaches to solve partial differential equations, adaptive multiresolution (MR) and adaptive mesh refinement (AMR). Both discretizations are based on finite volumes in space with second order shock-capturing and explicit time integration either with or without local time stepping. The two methods are benchmarked for the compressible Euler equations in Cartesian geometry. As test cases a twodimensional Riemann problem, Lax-Liu #6, and a three-dimensional ellipsoidally expanding shock wave have been chosen. We compare and assess their computational efficiency in terms of CPU time and memory requirements. We evaluate the accuracy by comparing the results of the adaptive computations with those obtained with the corresponding FV scheme using a regular fine mesh. We find that both approaches yield similar trends for CPU time compression for increasing number of refinement levels. MR exhibits more efficient memory compression than AMR and shows slightly enhanced convergence; however, a larger absolute overhead is measured for the tested codes. [ABSTRACT FROM AUTHOR]

There is a renewed surge in percolation-induced transport properties of diverse nanoparticle composites (cf. RSC Nanoscience & Nanotechnology Series, Paul O'Brien Editor-in-Chief). We note in particular a broad interest in nanocomposites exhibiting sharp electrical property gains at and above percolation threshold, which motivated us to revisit the classical setting of percolation in random resistor networks but from a multiscale perspective. For each realization of random resistor networks above threshold, we use network graph representations and associated algorithms to identify and restrict to the percolating component, thereby preconditioning the network both in size and accuracy by filtering a priori zero current-carrying bonds. We then simulate many realizations per bond density and analyze scaling behavior of the complete current distribution supported on the percolating component. We first confirm the celebrated power-law distribution of small currents at the percolation threshold, and second we confirm results on scaling of the maximum current in the network that is associated with the backbone of the percolating cluster. These properties are then placed in context with global features of the current distribution, and in particular the dominant role of the large current tail that is most relevant for material science applications. We identify a robust, exponential large current tail that 1. persists above threshold; 2. expands broadly over and dominates the current distribution at the expense of the vanishing power-law scaling in the small current tail; and 3. by taking second moments, reproduces the experimentally observed power-law scaling of bulk conductivity above threshold. [ABSTRACT FROM AUTHOR]

We consider the numerical treatment of the optical flow problem by evaluating the performance of the trust region method versus the line search method. To the best of our knowledge, the trust region method is studied here for the first time for variational optical flow computation. Four different optical flow models are used to test the performance of the proposed algorithm, combining linear and nonlinear data terms with quadratic and total variation (TV) regularization. We show that trust region often performs better than line search, especially in the presence of nonlinearity and nonconvexity in the model. [ABSTRACT FROM AUTHOR]

We evaluate the performance of different optimization techniques developed in the context of optical flow computation with different variational models. In particular, based on truncated Newton (TN) methods that have been an effective approach for large-scale unconstrained optimization, we develop the use of efficient multilevel schemes for computing the optical flow. More precisely, we compare the performance of a standard unidirectional multilevel algorithm--called multiresolution optimization (MR/Opt)--with that of a bidirectional multilevel algorithm--called full multigrid optimization (FMG/Opt). The FMG/Opt algorithm treats the coarse grid correction as an optimization search direction and eventually scales it using a line search. Experimental results on three image sequences using four models of optical flow with different computational efforts show that the FMG/Opt algorithm outperforms both the TN and MR/Opt algorithms in terms of the computational work and the quality of the optical flow estimation. [ABSTRACT FROM AUTHOR]

We present a computational method of coupling average interpolating wavelets with high-order finite volume schemes and its implementation on heterogeneous computer architectures for the simulation of multiphase compressible flows. The method is implemented to take advantage of the parallel computing capabilities of emerging heterogeneous multicore/multi-GPU architectures. A highly efficient parallel implementation is achieved by introducing the concept of wavelet blocks, exploiting the task-based parallelism for CPU cores, and by managing asynchronously all array of GPUs by means of OpenCL. We investigate the comparative accuracy of the GPU and CPU based simulations and analyze their discrepancy for two-dimensional simulations of shock-bubble interaction and Richtmeyer-Meshkov instability. The results indicate that the accuracy of the GPU/CPU heterogeneous solver is competitive with the one that uses exclusively the CPU cores. We report the performance improvements by employing up to 12 cores and 6 GPUs compared to the single-core execution. For the simulation of the shock-bubble interaction at Mach 3 with two million grid points, we observe a 100-fold speedup for the heterogeneous part and an overall speedup of 34. [ABSTRACT FROM AUTHOR]

We present an efficient method for computing the discrete orthonormal Stockwell transform (DOST). The Stockwell transform (ST) is a time-frequency decomposition transform that is showing great promise in various applications, but is limited because its computation is infeasible for most applications. The DOST is a nonredundant version of the ST, solving many of the memory and computational issues. However, computing the DOST of a signal of length N using basis vectors is still O(N²). The computational complexity of our method is O(N logN), putting it in the same category as the FFT. The algorithm is based on a simple decomposition of the DOST matrix. We also explore the way to gain conjugate symmetry for the DOST and propose a variation of the parameters that exhibits symmetry, akin to the conjugate symmetry of the FFT of a real-valued signal. Our fast method works equally well on this symmetric DOST. In this paper, we provide a mathematical proof of our results and derive that the computational complexity of our algorithm is O(N logN). Timing tests also confirm that the new method is orders-of-magnitude faster than the brute-force DOST, and they demonstrate that our fast DOST is indeed O(N logN) in complexity. [ABSTRACT FROM AUTHOR]

In this paper, we propose a novel multiresolution adaptive mesh refinement algorithm for solving initial-boundary value problems (IBVP) for evolution PDEs. The proposed algorithm dynamically adapts the grid to any existing or emerging irregularities in the solution, by refining the grid only at those places where the solution exhibits sharp features. The main advantage of the proposed grid adaptation method is that it results in a grid with a fewer number of nodes when compared to adaptive grids generated by existing multiresolution-based mesh refinement techniques. Several examples show the robustness and stability of the proposed algorithm. [ABSTRACT FROM AUTHOR]

Hybrid or multiphysics algorithms provide an efficient computational tool for combining micro- and macroscale descriptions of physical phenomena. Their use becomes imperative when microscale descriptions are too computationally expensive to be conducted in the whole domain, while macroscale descriptions fail in a small portion of the computation domain. We present a hybrid algorithm to model a general class of reaction-diffusion processes in granular porous media, which includes mixing-induced mineral precipitation on, or dissolution of, the porous matrix. These processes cannot be accurately described using continuum (Darcy-scale) models. The pore-scale/Darcy-scale hybrid is constructed by coupling solutions of the reaction-diffusion equations (RDE) at the pore scale with continuum Darcy-level solutions of the averaged RDEs. The resulting hybrid formulation is solved numerically by employing a multiresolution meshless discretization based on the smoothed particle hydrodynamics method. This ensures seamless noniterative coupling of the two components of the hybrid model. Computational examples illustrate the accuracy and efficiency of the hybrid algorithm. [ABSTRACT FROM AUTHOR]

This paper investigates the use of cascadic multiresolution methods for image deblurring. Iterations with a conjugate gradient-type method are carried out on each level, and terminated by a stopping rule based on the discrepancy principle. Prolongation is carried out by nonlinear edge-preserving operators, which are defined via PDEs associated with Perona-Malik or total variation-type models. Computed examples demonstrate the effectiveness of the methods proposed. [ABSTRACT FROM AUTHOR]

We investigate a recent algorithm, here called a discrete pulse transform (DPT), for the multiresolution analysis of a sequence. A DPT represents a sequence as a sum of pulses, where a pulse is a sequence which is zero everywhere except for a certain number of consecutive elements which have a constant nonzero value. Unlike the discrete Fourier and wavelet transforms, the DPT is not a discretization of an underlying continuous model, but is inherently discrete. The DPT is composed of nonlinear morphological filters based only on the order relations between elements of the sequence. It is comparable to, but computationally more efficient than, the median transform, and more amenable to theoretical analysis. In particular, we show that a DPT has remarkable shape preserving and consistency properties. [ABSTRACT FROM AUTHOR]

The Haar wavelets can represent exactly any piecewise constant function. The motivation for the present development is Alpert's family of compact orthogonal multiwavelets that can represent exactly any piecewise polynomial function. We choose to derive the algorithm in the style and notation of Harten's multiresolution analysis as extended to multiwavelets by the authors. We begin with a description of the nested grid hierarchy. Next comes the decomposition, which is the heart of the algorithm, and finally the reconstruction. The basis functions (which are nonfractal) retain the spatial compactness of the Haar basis functions, which enhances the algorithm application to nonperiodic and piecewise continuous data. [ABSTRACT FROM AUTHOR]

We generalize Harten's interpolatory multiresolution representation to include Her- mite interpolation. Compact Hermite interpolation with optimal order accuracy is used in both the decomposition and reconstruction algorithm. The resulting multiple basis functions (biorthogonal multiwavelets) are symmetric or skew-symmetric, compact, and analytic. Harten's approach has several advantages: the multiresolution scheme is inherently discrete, nonperiodic boundary conditions are easy to implement, and the representation can be extended to nonuniform grids in bounded do- mains. We demonstrate the compression features of the new multiple basis functions by application to several examples. [ABSTRACT FROM AUTHOR]

We present the details of a multiresolution method we proposed at the Taormina Wavelet Conference in 1993 (see ‘L-spline wavelets’ in Wavelets: Theory, Algorithms, and Applications, C. Chui, L. Montefusco, and L. Puccio, eds., Academic Press, New York, pp. 197–212) which is suitable for fitting functions or data on the sphere. The method is based on tensor products of polynomial splines and trigonometric splines and can be adapted to produce surfaces that are either tangent plane continuous or almost tangent plane continuous. The result is a convenient compression algorithm for dealing with large amounts of data on the sphere. We give full details of a computer implementation that is highly efficient with respect to both storage and computational cost. We also demonstrate the performance of the method on several test examples. [ABSTRACT FROM AUTHOR]

Classic wavelet methods were developed in the Euclidean spaces for multiscale representation and analysis of regularly sampled signals (time series) and images. This paper introduces a method of representing scattered spherical data by multiscale spherical wavelets. The method extends the recent pioneering work of Narcowich and Ward [Appl. Comput. Harmon. Anal., 3 (1996), pp. 324­336] by employing multiscale rather than single-scale spherical basis functions and by introducing a bottom-up procedure for network design and bandwidth selection. Decomposition and reconstruction algorithms are proposed for efficient computation. An analytical investigation confirms the localization property of the resulting spherical wavelets. The proposed method is illustrated by numerical examples. It is also employed to analyze and compress a real-data set consisting of the surface air temperatures observed on a global network of weather stations. [ABSTRACT FROM AUTHOR]

In this paper we describe and analyze a class of nonlinear multiresolution schemes for the multiresolution setting which corresponds to discretization by local averages with respect to the hat function. These schemes are based on the essentially-non-oscillatory (ENO) interpolatory procedure described in [A. Harten, B. Engquist, S. Osher, and S. Chakravarthy, J. Comput. Phys., 71 (1987), pp. 231–302]. We show that by allowing the approximation to fit the local nature of the data, one can improve the compression capabilities of the multiresolution algorithms. The question of stability for nonlinear (data-dependent) reconstruction techniques is also addressed. [ABSTRACT FROM AUTHOR]