Report

Sparse Approximation by Wavelet Frames and Applications Bin Dong Department of Mathematics The University of Arizona 2012 International Workshop on Signal Processing , Optimization, and Control June 30- July 3, 2012 USTC, Hefei, Anhui, China Outlines I. Wavelet Frame Based Models for Linear Inverse Problems (Image Restoration) 1-norm based models Connections to variational model 0-norm based model Comparisons: 1-norm v.s. 0-norm II. Applications in CT Reconstruction Quick Intro of Conventional CT Reconstruction CT Reconstruction with Radon Domain Inpainting Tight Frames in Orthonormal basis Riesz basis Tight frame: Mercedes-Benz frame Expansions: Unique Not unique Tight Frames General tight frame systems • They are redundant systems satisfying Parseval’s identity • Or equivalently Tight wavelet frames where and Construction of tight frame: unitary extension principles [Ron and Shen, 1997] Tight Frames Example: Fast transforms Decomposition Reconstruction Perfect Reconstruction Redundancy Lecture notes: [Dong and Shen, MRA-Based Wavelet Frames and Applications, IAS Lecture Notes Series,2011] Image Restoration Model Image Restoration Problems • Denoising, when is identity operator • Deblurring, when is some blurring operator • Inpainting, when is some restriction operator • CT/MR Imaging, when is partial Radon/Fourier transform Challenges: large-scale & ill-posed Frame Based Models Image restoration model: Balanced model for image restoration [Chan, Chan, Shen and Shen, 2003], [Cai, Chan and Shen, 2008] When , we have synthesis based model [Daubechies, Defrise and De Mol, 2004; Daubechies,Teschke and Vese, 2007] When , we have analysis based model [Stark, Elad and Donoho, 2005; Cai, Osher and Shen, 2009] Resembles Variational Models Connections: Wavelet Transform and Differential Operators Nonlinear diffusion and iterative wavelet and wavelet frame shrinkage o 2nd-order diffusion and Haar wavelet: [Mrazek, Weickert and Steidl, 2003&2005] o High-order diffusion and tight wavelet frames in 1D: [Jiang, 2011] Difference operators in wavelet frame transform: Filters Transform Approximation True for general wavelet frames with various vanishing moments [Weickert et al., 2006; Shen and Xu, 2011] Connections: Analysis Based Model and Variational Model [Cai, Dong, Osher and Shen, Journal of the AMS, 2012]: Converges For any differential operator when proper parameter is chosen. The connections give us • Geometric interpretations of the wavelet frame transform (WFT) • WFT provides flexible and good discretization for differential operators • Different discretizations affect reconstruction results • Good regularization should contain differential operators with varied orders (e.g., total generalized variation [Bredies, Kunisch, and Pock, 2010]) Leads to new applications of wavelet frames: Image segmentation: [Dong, Chien and Shen, 2010] Standard Discretization Piecewise Linear WFT Surface reconstruction from point clouds: [Dong and Shen, 2011] Frame Based Models: 0-Norm Nonconvex analysis based model [Zhang, Dong and Lu, 2011] Motivations: • Restricted isometry property (RIP) is not satisfied for many applications • Penalizing “norm” of frame coefficients better balances sparsity and smoothnes Related work: • • “norm” with quasi-norm with : [Blumensath and Davies, 2008&2009] : [Chartrand, 2007&2008] Fast Algorithm: 0-Norm Penalty decomposition (PD) method [Lu and Zhang, 2010] Change of variables Quadratic penalty Algorithm: Fast Algorithm: 0-Norm Step 1: Subproblem 1a): quadratic Subproblem 1b): hard-thresholding Convergence Analysis [Zhang, Dong and Lu, 2011] : Numerical Results Balanced Comparisons (Deblurring) PFBS/FPC: [Combettes and Wajs, 2006] /[Hale, Yin and Zhang, 2010] Analysis Split Bregman: [Goldstein and Osher, 2008] & [Cai, Osher and Shen, 2009] 0-Norm PD Method: [Zhang, Dong and Lu, 2011] Numerical Results Comparisons Portrait Couple Balanced Analysis Faster Algorithm: 0-Norm Start with some fast optimization method for nonsmooth and convex optimizations: doubly augmented Lagrangian (DAL) method [Rockafellar, 1976]. Given the problem: The DAL method: where We solve the joint optimization problem of the DAL method using an inexact alternative optimization scheme Faster Algorithm: 0-Norm Start with some fast optimization method for nonsmooth and convex optimizations: doubly augmented Lagrangian (DAL) method [Rockafellar, 1976]. Given the problem: The DAL method: where The inexact DAL method: Hard thresholding Faster Algorithm: 0-Norm However, the inexact DAL method does not seem to converge!! Nonetheless, the sequence oscillates and is bounded. The mean doubly augmented Lagrangian method (MDAL) [Dong and Zhang, 2011] solve the convergence issue by using arithmetic means of the solution sequence as outputs instead: MDAL: Comparisons: Deblurring Comparisons of best PSNR values v.s. various noise level Comparisons: Deblurring Comparisons of computation time v.s. various noise level Comparisons: Deblurring What makes “lena” so special? 1-norm 0-norm: PD Decay of the magnitudes of the wavelet frame coefficients is very fast, which is what 0-norm prefers. Similar observation was made earlier by [Wang and Yin, 2010]. 0-norm: MDAL With the Center for Advanced Radiotherapy and Technology (CART), UCSD APPLICATIONS IN CT RECONSTRUCTION 3D Cone Beam CT Cone Beam CT v z g(u) u* f(x) y x x n xS 0 0 u 3D Cone Beam CT Discrete = Animation created by Dr. Xun Jia Cone Beam CT Image Reconstruction Goal: solve Unknown Image Difficulties: Related work: Projected Image • In order to reduce dose, the system is highly underdetermined. Hence the solution is not unique. •Projected image is noisy. Total Variation (TV): [Sidkey, Kao and Pan 2006], [Sidkey and Pan, 2008], [Cho et al. 2009], [Jia et al. 2010]; EM-TV: [Yan et al. 2011]; [Chen et al. 2011]; Wavelet Frames: [Jia, Dong, Lou and Jiang, 2011]; Dynamical CT/4D CT: [Chen,Tang and Leng, 2008], [Jia et al. 2010], [Tian et al., 2011]; [Gao et al. 2011]; CT Image Reconstruction with Radon Domain Inpainting Idea: start with Instead of solving We find both • and is close to such that: but with better quality • • Prior knowledge of them should be used Benefits: • Safely increase imaging dose • Utilizing prior knowledge we have for both CT images and the projected images CT Image Reconstruction with Radon Domain Inpainting Model [Dong, Li and Shen, 2011] where • p=1, anisotropic • p=2, isotropic Algorithm: alternative optimization & split Bregman. CT Image Reconstruction with Radon Domain Inpainting Algorithm [Dong, Li and Shen, 2011]: block coordinate descend method [Tseng, 2001] Problem: Algorithm: Convergence Analysis Note: If each subproblem is solved exactly, then the convergence analysis was given by [Tseng, 2001], even for nonconvex problems. CT Image Reconstruction with Radon Domain Inpainting Results: N denoting number of projections N=15 N=20 CT Image Reconstruction with Radon Domain Inpainting Results: N denoting number of projections N=15 N=20 W/O Inpainting With Inpainting Thank You Collaborators: Mathematics Stanley Osher, UCLA Zuowei Shen, NUS Jia Li, NUS Jianfeng Cai, University of Iowa Yifei Lou, UCLA/UCSD Yong Zhang, Simon Fraser University, Canada Zhaosong Lu, Simon Fraser University, Canada Medical School Steve B. Jiang, Radiation Oncology, UCSD Xun Jia, Radiation Oncology, UCSD Aichi Chien, Radiology, UCLA