Iterative Basis Pursuit for Image Sequence Denoising Brian Eriksson ECE 738 Final Project Abstract An iterative method is purposed in this paper using the basis pursuit algorithm for spatial denoising, coupled with temporal wavelet denoising to result in a denoised video signal. Introduction Several new techniques have been developed recently for the purposes of denoising images. The most promising of these techniques have been the curvelet and undecimated wavelet transforms. Using a basis pursuit algorithm, the advantages of each algorithm can be taken advantage of to produce a spatially denoised image. When working with image sequences, the correlation between frames can be used to denoise images. Considering each pixel as a time-domain signal across multiple frames, this signal can be denoised using hard thresholding of wavelets. This paper purposes a iterative method of basis pursuit spatial denoising combined with temporal denoising using wavelets to produce a denoised image sequence signal. Curvelet Algorithm The Curvelet transform (original purposed in [4]) consists of an overcomplete representation of an image using a series of L2 energy measurements ranging across scale, orientation, and position. Each curvelet consists of a tight frame constrained over a slice of the fourier domain. In the spatial domain, the curvelet is a scaled and rotated gabor signal along the width and is a scaled and rotated gaussian signal along the length. One of the most important properties of the curvelet is length = width^2 (length = 2^-J, width = 2^-(2*J), J = scale). This allows for the curvelet to act like a needle at fine scale representations. A brief overview of the mathematical framework from [2] is now presented to give the reader a formal representation of curvelets. Each curvelet is defined by three parameters (J, K, L). J = Scale L = orientation K = locationBrian Eriksson – Iterative Basis Pursuit for Image Sequence Denoising 2 Parabolic Scaling Matrix: ⎟⎟⎠⎞⎜⎜⎝⎛=JjJD20022 Rotation Angle: lJJ*2*2−=πθ Translation Parameter: 112 212(*, * ),_tankk knormalizing cons tsδδδδδ== Curvelet Basis Function: 12 1 21122(, ) ()*( )() ()() ()xxxxx Gabor xxGaussianxγψϕψϕ=== Finally, the curvelet parameterized by (J,K,L) can be defined as 32(,,) 1 2 1 2(, ) 2 *( * *(, ) )Jjjlk Jxx D R xx kθδγγ=− Curvelet Properties: -Anisotropy Scaling Law 2lengthwidth ≈ -Directional Sensitivity JnsOrientatioof1__# = -Spatial Localization -Curvelet coefficients form a Cartesian coordinate grid with spacing proportional to the length in Jθ direction and the width of the curvelet in the normal (respective to Jθ) direction. -Oscillatory Nature -Across a ridge, a curve displays an oscillatory nature. This is shown by the use of the gabor waveform in the normal direction.Brian Eriksson – Iterative Basis Pursuit for Image Sequence Denoising 3 Now a more intuitive graphical explaination of the curvelet transform is presented. (Spatial Domain) (Curvelet Coefficient Domain) Figure – Example of a group of curvelets at a fixed orientation and scale and its relationship to the curvelet transform. Each coefficient relates to an L2 energy measurement of the oval region in the spatial domain. Figure – Example of curvelets with fixed scale and location, varying along orientation Using curvelets of varying orientation (figure above) the resulting coefficients would be very close to zero for (A) due to only a small amount of edge energy included in the curvelet area. (B) would have a slightly larger coefficient but still relatively small in comparison to the coefficient related to figure (C) which would be quite large due to the tight frame of the curvelet being tangential to the edge. (A) (B) (C)Brian Eriksson – Iterative Basis Pursuit for Image Sequence Denoising 4 Figure – Example of curvelets with fixed orientation and location, varying across scale Using curvelets of varying scale aligned with an edge (figure), one can see how the changes in scale will affect the resulting coefficient. For a coarse scale decomposition (A), the curvelet coefficient resulting will be of moderate size due to the frame being tangential to the edge, but would contain a large amount of area without any edge energy. The medium scale decomposition (B) will be larger due to the length of the curvelet having increased therefore containing more of the edge. The fine scale representation (C) will result in the largest coefficient due to almost the entire curvelet frame being filled with the edge energy. Figure – Example of curvelets with fixed orientation and scale, varying across location Using curvelets of varying location the strength of the algorithm becomes obvious as figures (A) and (B) would result in a coefficient very close to zero (curvelets (A) (B) (C) (A) (B) (C)Brian Eriksson – Iterative Basis Pursuit for Image Sequence Denoising 5are not compactly supported), while the coefficient related to (C) would be very large due to the edge being contained in the curvelet frame. In [1] it is shown that curvelets give a sparse representation of edges in C2 space. The problem with curvelets is their poor presentation of point singularities, which relates to points or corners in an image. This is shown at length in [2], as using the curvelet transform to reconstruct a noisy version of the Lena image results in very high quality performance on the elongated potions of the image (hat edges, outline of lena’s face), but performs quite poorly on the fine scale edges (eyes, mouth). Undecimated Wavelet Algorithm The standard one-dimensional A Trous Wavelet filter structure has the appearance of: Figure - Analysis Phase Figure - Synthesis Phase This is the structure that is used when a normal orthogonal discrete wavelet transform is performed. HPF LPF 22HPFLPF22HPFLPF2222HPF LPF +22HPFLPF+22HPFLPF+Brian Eriksson – Iterative Basis Pursuit for Image Sequence Denoising 6 The undecimated wavelet transform is performed by removing all the upsampling and downsampling blocks from the filter bank. In this representation, the signal is never decimated (downsampled), so the wavelet coefficients at each level are the same size as the original signal. This is a change from the critically sampled orthogonal wavelet transform, where the size of the