Texture clustering with asymmetric Cheeger cut

Xavier Bresson

Cheeger cut has recently been shown to provide excellent partitioning results for two classes. While the classical Cheeger cut favors a 50-50 partition of the graph, we present here an asymmetric variant of the Cheeger cut which favors, for example, a 10-90 partition. This asymmetric Cheeger cut provides a powerful tool for unsupervised multi-class clustering. We use it in recursive bipartitioning to detach one after the other each of the classes. This asymmetric recursive algorithm handles equally well any number of classes, as opposed to symmetric recursive bipartitioning which is naturally better suited for 2m classes. We apply the asymmetric Cheeger cut to perform texture classification and show that our method outperforms related spectral methods.


Data-driven tight frame construction and image denoising

Jian-Feng Cai

The regularization methods for image restoration using the ℓ1 norm of the coefficients of the underlying image under some system assume that the image has a good sparse approximation under the given system. Such a system can be a basis, a frame or a general over-complete dictionary. One widely used system in image restoration is wavelet tight frame. There have been enduring efforts on seeking wavelet type of tight frames under which certain class of functions or images can have a good sparse approximation. However, the structure of images varies greatly in practice and a system working well for one type of images may not work for another. This talk presents a method that derives discrete tight frame system from the input image itself to provide a better sparse approximation to the input image. Such an adaptive tight frame construction scheme is applied on image denoising by constructing a tight frame tailor down to the given noisy data. The experiments showed the proposed approach performs better in image denoising than those wavelet tight frames designed for a class of images. Moreover, by ensuring the system derived from our approach is always a tight frame, our approach also runs much faster than some other adaptive over-complete dictionary based approaches with comparable PSNR performance.


Decoupling noises and features based on sparse analysis

Falai Chen

In this talk, I will discuss a new approach for decoupling noises and features on 3D models. The approach consisits of two phases. In the first phase, a smooth base model is generated to approximate the underlying model of the input noisy model by a global Laplacian regularization donosing scheme. The base model is guaranteed to asymptotically converge to the underlying model with probability one as the sampling points go to infinity. In the second phase, a sparse optimization scheme is proposed to recover shape features from the residual between the input model and the smooth base model. The algorithm is based on the observation that sharpe features can be sparsely represented in some coherent dictionary. Experiments show that our approch can robustly recover the sharpe features while remove noises on a 3D model.


Coupling Interface Method and Macromocules in Ionic Solution

I-Liang Chern

In this talk, I will first review the coupling interface method for solving the elliptic interface problems in arbitrary dimensions. It is a finite difference method on an underlying regular Cartesian grid. The method takes a dimension-splitting approach. In each dimension, it uses piecewise polynomials to approximate the solution from both sides of the interface. The information from different dimensions is linked through jump conditions, leading to a coupled linear equation for the principal second order derivatives. This approach reduces the size of stencil, and thus has mild restriction on the interfaces. It has more potential to handle complex interface problems. A recent progress on second-order accurate approximation for gradients on interfaces will be reported.

Secondly, I will show application of the coupling interface method on simulation of macromolecules in ionic solution, in which the Poisson-Boltzmann equation is solved. Various singularity removal techniques will be demonstrated.


Spline Spaces over T-meshes

Jiansong Deng

A T-mesh is a rectangular grid that allows T-junctions. Some types of spline spaces over T-meshes have been considered in the literature, including hierarchical B-splines, T-splines and LR splines. In the talk, I will explain why we need T-meshes in geometric modeling and how to define spline spaces over T-meshes. In the talk, I will introduce a new type of spline spaces over T-meshes and given their dimension formula and basis function construction. The applications in computer graphics, image processing and isogeometric analysis are reviewed as well.


Total Variation, Wavelet Frames, Sparsity and Imaging

Bin Dong

I will start my talk with a brief literature review of total variation and some more general variational models introduced in the literature for image restoration problems. Then I will review some basic concepts of wavelet frames and their recent applications in image restoration. Wavelet frame based and differential operator based variational models were generally considered as different approaches. However, they do share the same observation that images are generally sparse under certain. I will address the connections of wavelet frame based models to variational models based on one of our recent theoretical studies, which also granted geometric interpretations to the wavelet frame transform and enabled us to extend the applications of wavelet frames. To further utilize the property of sparse approximation by wavelet frames, I will present a model (as well as some fast algorithms) that penalizes the 0-norm of the frame coefficients, which has some advantages over the commonly used 1-norm for some specific types of images.


Seismic Imaging

Bjorn Engquist

Seismic imaging is the mot important process for finding out properties of the earth's interior. Seismic waves are generated and measured at the surface. An image is then generated based on high frequency wave propagation in variable velocity media. We will discuss imaging principles and key numerical techniques for seismic exploration.


4D compressive medical imaging via Split Bregman method

Hao Gao

I will present a few 4D compressive medical imaging examples with experimental data, including MRI, CT and optical imaging, to illustrate how the split Bregman method helps the real-world problems.


Computational Conformal Geometry Theories and Applications

Xianfeng David Gu

Conformal geometry studies the invariants under angle preserving transformations, which offers powerful tools for surface matching, classification and analysis.

This talk introduces the main theorems in computational conformal geometry, including discrete Hodge theory, discrete surface Ricci flow theory, discrete uniformization, conformal modules, Teichmuller map and so on.

The direct applications will be covered as well, including surface registration in computer vision, global parameterization in graphics, geometric routing in networks, homotopy detection in computational topology, brain mapping and virtual colonoscopy in medical imaging and so on.


Blind image de-blurring for removing the spatially-varying motion-blurring from a single image

Hui Ji

Blind image de-blurring problem is an ill-posed inverse problem, which is about how to remove image blurring from photographs without knowing all the information about the corresponding blur kernel. One such often seen problem is blind motion de-blurring for recovering the motion-blurred image due to the camera movement during the shutter time. Blind motion de-blurring has drawn a lot of attentions in recent years and most existing approaches consider a spatially invariant convolution model for image blurring. However, the practical motion blurring often is a spatially varying blurring process over the image. In this talk, I will start with the introduction of several important results on various aspects of blind image de-convolution. Then, based on these results, I will introduce a two-stage approach for removing the spatially-varying motion blurring from a single image.


Level Set Methods and their Applications in Biomedical Image Processing

Chiu-Yen Kao

Level set methods are well known for their flexibility in handling the shape and topological changes of moving interfaces. These methods have been successfully applied to study biomedical images and provide robust analysis tools. In this talk, we will give examples of morphology and connectome study of human brains and the shape analysis of ciliary muscle of human eyes.


Solving PDEs on Point clouds and applications

Ronjie Lai

In this talk, I will present two systematic methods to solve PDEs on manifolds represented as meshless point clouds. Global mesh structures or parameterizations are usually hard to construct in this case. While our methods only rely on the local structure at each data point and scale well with the total number of points and the intrinsic dimension of point clouds. Once the local structure is available, we propose numerical schemes to approximate differential operators and define integrals on point clouds, which can be used to solve partial differential equation (PDE) and variational problem on point clouds. The framework we proposed can be easily adapted to solve PDEs on k-manifolds in R^n. Numerical comparisons with existing methods demonstrate the accuracy of the proposed methods. Finally, several applications to geometric understanding of point clouds will be discussed based on solutions of PDEs on point clouds.


A Grid Based Particle Method for Solving Variational Problems on Manifolds

Shingyu Leung

We propose a numerical approach to solve variational problems on manifolds represented by the Grid Based Particle Method (GBPM). In particular, we propose a splitting algorithm for image segmentation on manifolds represented by unconnected sampling particles. To develop a fast minimization algorithm, we propose a new splitting method by generalizing the augmented Lagrangian method (ALM). To efficiently implement the resulting method, we incorporate with the local polynomial approximations of the manifold in the GBPM. The resulting method is flexible for segmentation on various manifolds including closed or open or even surfaces which are not orientable. This is a joint work with Jun Liu.


Teichmuller Extremal Mapping and its Applications

Ronald Lok Ming Lui

Registration, which aims to find an optimal 1-1 correspondence between shapes, is an important process in different research areas. Conformal mappings have been widely used to obtain a diffeomorphism between shapes that minimizes angular distortion. Conformal registrations are beneficial since it preserves the local geometry well. However, when landmark constraints are enforced, conformal mappings generally do not exist. This motivates us to look for a unique landmark matching quasiconformal registration, which minimizes the conformality distortion. Under suitable condition on the landmark constraints, a unique diffeomporphism, called the Teichmuller extremal mapping between two surfaces can be obtained, which minimizes the maximal conformality distortion. In this talk, an efficient iterative algorithm, called the Quasi-conformal (QC) iterations, to compute the Teichmuller mapping will be presented. The basic idea is to represent the set of diffeomorphisms using Beltrami coefficients (BCs), and look for an optimal BC associated to the desired Teichmuller mapping. The associated diffeomorphism can be efficiently reconstructed from the optimal BC using the Linear Beltrami Solver(LBS). Using BCs to represent diffeomorphisms guarantees the diffeomorphic property of the registration. Using the proposed method, the Teichmuller mapping can be accurately and efficiently computed within 10 seconds. The obtained registration is guaranteed to be bijective. This proposed algorithm can also be practically applied to real applications. In the second part of my talk, I will present how Teichmuller extremal mapping can be used for brain landmark matching registration, constrained texture mapping and face recognition.


On reinitializing level-set functions name: Chohong Min and Frederic Gibou affilation

Chohong Min

The level-set method has been successfully applied to image processing problems such as active contouring and computational fluid problems with interfaces. One of the hardest parts in its applications is the reinitialization of the level-set function, avoiding slopes near interface too steep or too flat. The reinitialization is implemented by a Hamilton-Jacobi equation with discontinuous source term that requires special cares. We present a stable and accurate spatial and temporal discretizations of the equation. With adaptive mesh and parallel implementation added, it becomes a state-of-the-art solution to reinitialization.


Variational Methods for Image Stitching

Michael Ng

We discuss image stitching algorithms to compute (i) weighting mask functions automatically on input images and stitch them together; and (ii) to handle color inconsistency across input images.

Experimental results will be shown to demonstrate the performance of the proposed algorithm.


High-Order Factorization Based High-Order Hybrid Fast Sweeping Methods for Point-Source Eikonal Equations

Jianliang Qian

The solution for the eikonal equation with a point-source condition has an upwind singularity at the source point as the eikonal solution behaves like a distance function at and near the source. As such, the eikonal function is not differentiable at the source so that all formally high-order numerical schemes for the eikonal equation yield first-order convergence and relatively large errors. Therefore, it is a long standing challenge in computational geometrical optics how to compute a uniformly high-order accuratesolution for the point-source eikonal equation in a global domain. In this paper, we propose high-order factorization based high-order hybrid fast sweeping methods for  point-source  eikonal equations to compute  just such solutions. Observing that the squared eikonal is differentiable at the source, we propose to factorize the eikonal into two multiplicative or additive factors, one of which is specified to approximate the eikonal up to arbitrary order of accuracy near the source, and the other of which serves as a higher-order correction term. This decomposition is achieved by using the eikonal equation and applying power series expansions to both the squared eikonal and the squared slowness function. We develop recursive formulas to compute the approximate eikonal up to arbitrary order of accuracy near the source. Furthermore, these approximations enable us to decompose the eikonal into two factors either multiplicatively or additively so that we can design two new types of hybrid, high-order fast sweeping schemes for the point-source eikonal equation. We also show that the hybrid first-order fast sweeping methods are monotone and consistent so that they are conver-gent in computing viscosity solutions. Two- and three-dimensional numerical examples demonstrate that a hybrid p-th order fast sweeping method yields desired, uniform, clean p-th order convergence in a global domain by using a p-th order factorization. This is a joint work with Songting Luo and Robert Burridge.


One-Bit Compressive Sampling

Lixin Shen

In this talk, we address the problem of 1-bit compressive sampling. We introduce an optimization model for reconstruction of sparse signals from 1-bit measurements and propose an algorithm for obtaining an approximation reconstruction of the sparse signals from it. Our model is to minimize the ℓ0 norm of the signal of interest subject to the signal satisfying convex consistency constraints. Our approach is to obtain a sequence of optimization problems by successively approximating the ℓ0 norm and to solve resulting problems by exploiting the proximity operator. Our approach does not require prior knowledge on the sparsity of the signal. Convergence analysis of our algorithm is presented. We examine the performance of our proposed algorithm and compare it with the binary iterative hard thresholding (BIHT) a state-of-the-art algorithm for 1-bit compressive sampling reconstruction.


Inverse Lax-Wendroff Procedure for Numerical Boundary Conditions of Hyperbolic Equations

Chi-Wang Shu

We develop a high order finite difference numerical boundary condition for solving hyperbolic Hamilton-Jacobi equations and conservation laws on a Cartesian mesh. The challenge results from the wide stencil of the interior high order scheme and the fact that the boundary may not be aligned with the mesh and can intersect the grids in an arbitrary fashion. Our method is based on an inverse Lax-Wendroff procedure for the inflow boundary conditions. We repeatedly use the partial differential equation to write the normal derivatives to the inflow boundary in terms of the tangential derivatives and the time derivatives (for time dependent equations). With these normal derivatives, we can then impose accurate values of ghost points near the boundary by a Taylor expansion. At the outflow boundaries, we use Lagrange extrapolation or least squares extrapolation if the solution is smooth, or a weighted essentially nonoscillatory (WENO) type extrapolation if a shock is close to the boundary. Extensive numerical examples are provided to illustrate that our method is high order accurate and has good performance when applied to one and two dimensional scalar or system cases with the physical boundary not aligned with the grids and with various boundary conditions including the solid wall boundary condition. This is a joint work with Ling Huang and Mengping Zhang (for the Hamilton-Jacobi equations) and with Sirui Tan (for the time dependent conservation laws).


A Fast Global Optimization-Based Approach to Evolving Contours with Generic Shape Prior

Xue-Cheng Tai

In this talk, we present a new global optimizationbased approach to contour evolution, with or without the novel variational shape constraint that imposes a generic star shape using a continuous max-flow framework. In theory, the proposed continuous max-flow model provides a dual perspective to the reduced continuous min-cut formulation of the contour evolution at each discrete time frame, which proves the global optimality of the discrete time contour propagation. The variational analysis of the flow conservation condition of the continuous max-flow model shows that the proposed approach does provide a fully time implicit solver to the contour convection PDE, which allows a large time-step size to significantly speed up the contour evolution. For the contour evolution with a star shape prior, a novel variational representation of the star shape is integrated to the continuous max-flow-based scheme by introducing an additional spatial flow. In numerics, the pro-posed continuous max-flow formulations lead to efficient duality-based algorithms using modern convex optimization theories. Our approach is implemented in a GPU, which significantly improves computing efficiency. We show the high performance of our approach in terms of speed and reliability to both poor initialization and large evolution step-size, using numerous experiments on synthetic, real-world and 2D/3D medical images.

This talk is based in a joint work by: J. Yuan, E. Ukwatta1, X.C. Tai, A. Fenster1, C. Schnorr.


An Implicit Interface Boundary Integral Method for Poisson’s and Helmholtz Equations on Arbitrary Domains

Richard Tsai

We propose a simple formulation for constructing boundary integral methods to solve Poisson’s and Helmholtz equations on domains with piecewise smooth boundaries defined through their signed distance function. Our formulation is based on averaging a family of parameterizations of an integral equation defined on the boundary of the domain, where the integrations are carried out in the level set framework using an appropriate Jacobian. By the coarea formula, the algorithm operates in the Euclidean space and does not require any explicit parameterization of the boundaries. We present numerical results in two and three dimensions.


Data Regularization Using Beams Decomposition and Sparse Optimization

Yanfei Wang

In seismic exploration, the process of acquisition records the continuous wavefield which is generated by thesource. In order to restore the seismic data correctly, the acquisition should satisfy the Nyquist/Shannon sampling theorem, i.e., the sampling frequency should be at least twice of the maximum frequency of original signal. In seismic acquisition, because of the influence of obstacles at land surface, rivers, bad receivers, noise, acquisition aperture, restriction of topography and investment, the obtained data usually does not satisfy the sampling theorem. A direct effect of the limitations of acquisition is the sub-sampled data will generate aliasing in the frequency domain; therefore, it may affect the subsequent processing such as filtering, de-noising, AVO (amplitude versus offset) analysis, multiple eliminating and migration imaging [1-5].

In order to remove the influence of sub-sampled data, the seismic data regularization technique is often used. Let us denote by m the original seismic wavefield, d the sampled data, and L the sampling operator, the data regularization can be written as

                                                           Lm = d.                                                                 (1)

Our purpose is to restore m from the sampled data d. Since d is usually incomplete and L is an underdetermined operator, this indicates that there are infinite solutions satisfying the seismic imaging equation (1). Hence, seismic data regularization is an ill-posed inverse problem.

In this research work, we develop some sparse optimization methods for the wavefield reconstruction problem. We consider Gaussian beams decomposition methods and sampling techniques and solve the problem by constructing different kinds of regularization models and study sparse optimization methods for solving the regularization model. The lp-lq model with p = 2 and q = 0, 1 is fully studied. Solving methods for the optimization problem are addressed. Numerical experiments are performed for solving the ill-posed data regularization problem. The results revealed that the proposed method can greatly improve the quality of wavefield recovery.


1. Wang Y.F., Liu P., Li Z. H., Sun T., Yang C. C. and Zheng Q. S. Data regularization using Gaussian beams decomposition and sparse norms. Journal of Inverse and Ill-posed Problems, DOI: 10.1515/jip-2012-0030, 2012.

2. Wang Y.F. Sparse optimization methods for seismic wavefields recovery. Proceedings of the Institute of Mathematics and Mechanics (Yekaterinburg) (2012) 18, No. 1, 42-55.

3. Wang Y.F., Yang C.C. and Cao J.J. On Tikhonov regularization and compressive sensing for seismic signal processing. Mathematical Models and Methods in Applied Sciences (2012) 22, No. 2, 1150008-1-1150008-24.

4. Wang Y.F., Cao J.J. and Yang C.C. Recovery of seismic wavefields based on compressive sensing by an l1-norm constrained trust region method and the piecewise random sub-sampling. Geophysical Journal International (2011) 187, 199-213.

5. Wang Y.F., Stepanova I.E., Titarenko V.N. and Yagola A.G. Inverse Problems in Geophysics and Solution Methods. Higher Education Press, Beijing, 2011.


Proximity Algorithms for Solving Convex Optimization Problems Arising from Image Processing

Yuesheng Xu

We consider a class of convex non-smooth optimization problems in the context of image denoising/deblurring. Solutions of the optimization problems are characterized as fixed-point equations in terms of the proximity operator of the functions appearing in their objective functions. Proximity algorithms are developed using the characterizations of the solutions. Convergence of the algorithms are shown by introducing the notion of the weakly firmly non-expansive operators. Existing algorithms are identified as special cases of the proposed algorithms. Numerical results will be presented to demonstrate the efficiency and accuracy of the proposed algorithms.


The Alternating Direction Method of Multipliers

Wotao Yin

Through examples, we argue that the alternating direction method of multipliers (ADMM) is suitable for problems arising in image processing, conic programming, machine learning, compressive sensing, as well as distributed data processing, and the method is able to solve very  large scale problem instances. The development of this method dates back to the 1950s and has close relationships with the Douglas-Rachford splitting, the augmented Lagrangian method, Bregman iterative algorithms, proximal-point algorithms, etc. This "old" method has recently become popular among researchers in image/signal processing, machine learning, and distributed/decentralized computation. After a brief overview, we explain its convergence behavior and then demonstrate how to solve very large scale conic programming problems and machine learning problems such as LASSO by ADMM.


A Fast Modified Newton's Method for Curvature Based Denoising of 1D Signals

Andy Yip

In this talk, we present a fast numerical method for denoising of 1D signals based on curvature minimization. Motivated by the primal-dual formulation for total variation minimization introduced by Chan, Golub, and Mulet, the proposed method makes use of some auxiliary variables to reformulate the stiff terms presented in the Euler-Lagrange equation which is a fourth-order differential equation. A direct application of Newtons method to the resulting system of equations often fails to converge. We propose a modified Newtons iteration which exhibits local superlinear convergence and global convergence in practical settings. The method is much faster than other existing methods for the model. Unlike all other existing methods, it also does not require tuning any additional parameter besides the model parameter. Numerical experiments are presented to demonstrate the effectiveness of the proposed method.


A primal-dual fixed point algorithm for conver separable
minimization with applications to image restoration

Xiaoqun Zhang

Recently, minimization of a sum of two convex functions has received considerable interests in
variational image restoration model. In this paper, we propose a general algorithmic framework for solving separable convex minimization problem from the point of view of fixed point algorithms based on proximity operators. Motivated from proximal forward-backward splitting (PFBS) and fixed point algorithms based on the proximity operator (FP2O) for image denoising,
we design a primal-dual fixed point algorithm based on proximity operator (PDFP2O for  ∈ [0, 1))
and obtain a scheme with close form for each iteration. Using the firmly nonexpansive properties of the proximity operator and with the help of a special norm over a product space, we achieve the convergence of the proposed PDFP2Oalgorithm. Moreover, under some stronger assumptions, we can prove the global linear convergence of the proposed algorithm. We also give the connection of the proposed algorithm with other existing first order methods. Finally, we illustrate the efficiency of PDFP2O through some numerical examples on image supperresolution, computerized tomographic reconstruction and parallel magnetic resonance imaging.  Generally speaking, our method PDFP2O is comparable with other state-of-the-art methods in numerical performance, while it has some advantages on parameters selection in real applications.

Quantitative Photoacoustic Imaging

Hongkai Zhao

I will present two recent works for quantitative photoacoustic imaging. Photoacoustic is a hybrid imaging modality that can achieve ultrasound resolution for optical contrast. Quantitative photoacoustic imaging includes two key steps. In the first step, one has to solve an inverse source problem for the acoustic wave to reconstruct initial acoustic source distribution from boundary measurements. We present a Neuman series based iterative algorithm that can recover the initial wave field efficiently and accurately. The second step is to reconstruct optical properties of the medium using internal measurements, namely, using the reconstructed initial acoustic source distribution from the first step. We propose a hybrid reconstruction procedure that uses both interior measurement and boundary current data, which is usually available in diffuse optical tomography. 



Copyright © 2010 Department of Mathematical Sciences All Rights Reserved.