An algorithm for total variation inpainting based on nonlinear multi-grid methods

Image inpainting refers to restoring a damaged image with missing information. The total variation (TV) inpainting model is one such method that simultaneously fills in the regions with available information from their surroundings and eliminates noises. The method works well with small narrow inpainting domains. However there remains an urgent need to develop fast iterative solvers, as the underlying problem sizes are large. In addition one needs to tackle the imbalance of results between inpainting and denoising. When the inpainting regions are thick and large, the procedure of inpainting works quite slowly and usually requires a significant number of iterations and leads inevitably to oversmoothing in the outside of the inpainting domain. To overcome these difficulties, we propose a solution for TV inpainting method based on the nonlinear multi-grid algorithm.

Denoising di immagini mediante tecniche basate sulla Total Variation.

Il lavoro svolto in questa tesi è legato allo studio ed alla formulazione di metodi computazionali volti all’eliminazione del noise (rumore) presente nelle immagini, cioè il processo di “denoising” che è quello di ricostruire un’immagine corrotta da rumore avendo a disposizione una conoscenza a priori del fenomeno di degrado. Il problema del denoising è formulato come un problema di minimo di un funzionale dato dalla somma di una funzione che rappresenta l’adattamento dei dati e la Variazione Totale. I metodi di denoising di immagini saranno affrontati attraverso tecniche basate sullo split Bregman e la Total Variation (TV) pesata che è un problema mal condizionato, cioè un problema sensibile a piccole perturbazioni sui dati. Queste tecniche permettono di ottimizzare dal punto di vista della visualizzazione le immagini in esame.

Gibbs point process approximation: Total variation bounds using Stein's method

We obtain upper bounds for the total variation distance between the distributions of two Gibbs point processes in a very general setting. Applications are provided to various well-known processes and settings from spatial statistics and statistical physics, including the comparison of two Lennard-Jones processes, hard core approximation of an area interaction process and the approximation of lattice processes by a continuous Gibbs process. Our proof of the main results is based on Stein's method. We construct an explicit coupling between two spatial birth-death processes to obtain Stein factors, and employ the Georgii-Nguyen-Zessin equation for the total bound.

Total Variation Blind Deconvolution: The Devil Is in the Details

In this paper we study the problem of blind deconvolution. Our analysis is based on the algorithm of Chan and Wong [2] which popularized the use of sparse gradient priors via total variation. We use this algorithm because many methods in the literature are essentially adaptations of this framework. Such algorithm is an iterative alternating energy minimization where at each step either the sharp image or the blur function are reconstructed. Recent work of Levin et al. [14] showed that any algorithm that tries to minimize that same energy would fail, as the desired solution has a higher energy than the no-blur solution, where the sharp image is the blurry input and the blur is a Dirac delta. However, experimentally one can observe that Chan and Wong's algorithm converges to the desired solution even when initialized with the no-blur one. We provide both analysis and experiments to resolve this paradoxical conundrum. We find that both claims are right. The key to understanding how this is possible lies in the details of Chan and Wong's implementation and in how seemingly harmless choices result in dramatic effects. Our analysis reveals that the delayed scaling (normalization) in the iterative step of the blur kernel is fundamental to the convergence of the algorithm. This then results in a procedure that eludes the no-blur solution, despite it being a global minimum of the original energy. We introduce an adaptation of this algorithm and show that, in spite of its extreme simplicity, it is very robust and achieves a performance comparable to the state of the art.

A total variation discontinuous Galerkin approach for image restoration

The focal point of this paper is to propose and analyze a P 0 discontinuous Galerkin (DG) formulation for image denoising. The scheme is based on a total variation approach which has been applied successfully in previous papers on image processing. The main idea of the new scheme is to model the restoration process in terms of a discrete energy minimization problem and to derive a corresponding DG variational formulation. Furthermore, we will prove that the method exhibits a unique solution and that a natural maximum principle holds. In addition, a number of examples illustrate the effectiveness of the method.

A Clearer Picture of Total Variation Blind Deconvolution

Blind deconvolution is the problem of recovering a sharp image and a blur kernel from a noisy blurry image. Recently, there has been a significant effort on understanding the basic mechanisms to solve blind deconvolution. While this effort resulted in the deployment of effective algorithms, the theoretical findings generated contrasting views on why these approaches worked. On the one hand, one could observe experimentally that alternating energy minimization algorithms converge to the desired solution. On the other hand, it has been shown that such alternating minimization algorithms should fail to converge and one should instead use a so-called Variational Bayes approach. To clarify this conundrum, recent work showed that a good image and blur prior is instead what makes a blind deconvolution algorithm work. Unfortunately, this analysis did not apply to algorithms based on total variation regularization. In this manuscript, we provide both analysis and experiments to get a clearer picture of blind deconvolution. Our analysis reveals the very reason why an algorithm based on total variation works. We also introduce an implementation of this algorithm and show that, in spite of its extreme simplicity, it is very robust and achieves a performance comparable to the top performing algorithms.

Finite volume TVD formulation of lattice Boltzmann simulation on unstructured mesh

A numerical scheme is presented for accurate simulation of fluid flow using the lattice Boltzmann equation (LBE) on unstructured mesh. A finite volume approach is adopted to discretize the LBE on a cell-centered, arbitrary shaped, triangular tessellation. The formulation includes a formal, second order discretization using a Total Variation Diminishing (TVD) scheme for the terms representing advection of the distribution function in physical space, due to microscopic particle motion. The advantage of the LBE approach is exploited by implementing the scheme in a new computer code to run on a parallel computing system. Performance of the new formulation is systematically investigated by simulating four benchmark flows of increasing complexity, namely (1) flow in a plane channel, (2) unsteady Couette flow, (3) flow caused by a moving lid over a 2D square cavity and (4) flow over a circular cylinder. For each of these flows, the present scheme is validated with the results from Navier-Stokes computations as well as lattice Boltzmann simulations on regular mesh. It is shown that the scheme is robust and accurate for the different test problems studied.

Two-dimensional flow past circular cylinders using finite volume lattice Boltzmann formulation

In this article, an extension to the total variation diminishing finite volume formulation of the lattice Boltzmann equation method on unstructured meshes was presented. The quadratic least squares procedure is used for the estimation of first-order and second-order spatial gradients of the particle distribution functions. The distribution functions were extrapolated quadratically to the virtual upwind node. The time integration was performed using the fourth-order RungeKutta procedure. A grid convergence study was performed in order to demonstrate the order of accuracy of the present scheme. The formulation was validated for the benchmark two-dimensional, laminar, and unsteady flow past a single circular cylinder. These computations were then investigated for the low Mach number simulations. Further validation was performed for flow past two circular cylinders arranged in tandem and side-by-side. Results of these simulations were extensively compared with the previous numerical data. Copyright (C) 2011 John Wiley & Sons, Ltd.

Numerical-simulation of low supersonic-flow around a sphere

The controlled equations defined in a physical plane are changed into those in a computational plane with coordinate transformations suitable for different Mach number M(infinity). The computational area is limited in the body surface and in the vicinities of detached shock wave and sonic line. Thus the area can be greatly cut down when the shock wave moves away from the body surface as M(infinity) --> 1. Highly accurate, total variation diminishing (TVD) finite-difference schemes are used to calculate the low supersonic flowfield around a sphere. The stand-off distance, location of sonic line, etc. are well comparable with experimental data. The long pending problem concerning a flow passing a sphere at 1.3 greater-than-or-equal-to M(infinity) > 1 has been settled, and some new results on M(infinity) = 1.05 have been presented.

Run-up of solitary waves on twin conical islands using a boussinesq model

This paper investigates the interaction of solitary waves (representative of tsunamis) with idealized flat-topped conical islands. The investigation is based on simulations produced by a numerical model that solves the two-dimensional Boussinesq-type equations of Madsen and Sørensen using a total variation diminishing Lax-Wendroff scheme. After verification against published laboratory data on solitary wave run-up at a single island, the numerical model is applied to study the maximum run-up at a pair of identical conical islands located at different spacings apart for various angles of wave attack. The predicted results indicate that the maximum run-up can be attenuated or enhanced according to the position of the second island because of wave refraction, diffraction, and reflection. It is also observed that the local wave height and hence run-up can be amplified at certain gap spacing between the islands, owing to the interference between the incident waves and the reflected waves between islands. © 2012 American Society of Mechanical Engineers.

Eliminating discharge imbalances in predicting shallow water flows with shocks

The shallow water equations are widely used in modelling environmental flows. Being a hyperbolic system of differential equations, they admit shocks that represent hydraulic jumps and bores. Although the water surface can be solved satisfactorily with the modern shock-capturing schemes, the predicted flow rate often suffers from imbalances where shocks occur, eg the mass conservation is violated by failing to maintain a constant discharge rate at every cross-section in a steady open channel flow. A total-variation-diminishing Lax-Wendroff scheme is developed, and used to demonstrate how to achieve an exact flux balance. The performance of the proposed methods is inspected through some test cases, which include 1- and 2-dimensional, flat and irregular bed scenarios. The proposed methods are shown to preserve the mass exactly, and can be easily extended to other shock-capturing models.

Interaction between tsunami waves and isolated conical Islands

A newly developed computer model, which solves the horizontal two-dimensional Boussinesq equations using a total variation diminishing Lax-Wendroff scheme, has been used to study the runup of solitary waves, with various heights, on idealized conical islands consisting of side slopes of different angles. This numerical model has first been validated against high-quality laboratory measurements of solitary wave runups on a uniform plane slope and on an isoliated conical island, with satisfactory agreement being achieved. An extensive parametric study concerning the effects of the wave height and island slope on the solitary wave runup has subsequently been carried out. Strong wave shoaling and diffraction effects have been observed for all the cases investigated. The relationship between the runup height and wave height has been obtained and compared with that for the case on uniform plane slopes. It has been found that the runup on a conical island is generally lower than that on a uniform plane slope, as a result of the two-dimensional effect. The correlation between the runup with the side slope of an island has also been identified, with higher runups on milder slopes. This comprehensive study on the soliton runup on islands is relevant to the protection of coastal and inland regions from extreme wave attacks. © the Coastal Education & Research Foundation 2012.