PaperlayerView exact revision on arXiv

Source-linked AI summary

ShearLab 3D: Faithful Digital Shearlet Transforms based on Compactly Supported Shearlets

Gitta Kutyniok, Wang-Q Lim, Rafael Reisenhofer

arXiv:1402.5670v1math.NAcs.NA

TL;DR

Wavelets are deficient at sparsely approximating multivariate signals with curvilinear singularities. ShearLab 3D extends compactly supported shearlets to universal systems and 3D, and its sparse approximations perform best on the reported quantitative measures in most experiments.

  • Problem

    Wavelets do not provide optimally sparse approximations of 2D functions with curvilinear singularities, such as image edges.

    Source: §1 · p. 2

  • Method

    ShearLab 3D extends a faithful compactly supported shearlet realization to universal shearlets and 3D, with experiments comparing it against geometric multiscale algorithms.

    Source: §1.3 · p. 3

  • Results

    ShearLab 3D's sparse approximations yield the best results on applied quantitative measures in all experiments except some cases where the nonsubsampled shearlet transform slightly outperforms it.

    Source: §5.8 · p. 32

  • Takeaways & Limitations

    In computationally heavy tasks such as image or video inpainting, CUDA can increase speed by up to a factor of 10.

    Source: §5.8 · p. 32

    The lower frame bound requires sufficient frequency decay of ψ1 and φ1 and sufficient vanishing moments of ψ1.

    Source: §3.2.1 · p. 11, §3.3 · p. 15

Abstract

from arXiv · show

Wavelets and their associated transforms are highly efficient when approximating and analyzing one-dimensional signals. However, multivariate signals such as images or videos typically exhibit curvilinear singularities, which wavelets are provably deficient of sparsely approximating and also of analyzing in the sense of, for instance, detecting their direction. Shearlets are a directional representation system extending the wavelet framework, which overcomes those deficiencies. Similar to wavelets, shearlets allow a faithful implementation and fast associated transforms. In this paper, we will introduce a comprehensive carefully documented software package coined ShearLab 3D (www.ShearLab.org) and discuss its algorithmic details. This package provides MATLAB code for a novel faithful algorithmic realization of the 2D and 3D shearlet transform (and their inverses) associated with compactly supported universal shearlet systems incorporating the option of using CUDA. We will present extensive numerical experiments in 2D and 3D concerning denoising, inpainting, and feature extraction, comparing the performance of ShearLab 3D with similar transform-based algorithms such as curvelets, contourlets, or surfacelets. In the spirit of reproducible reseaerch, all scripts are accessible on www.ShearLab.org.

1. INTRODUCTION

Wavelets are effective for one-dimensional signals but poorly capture and orient curvilinear singularities in multivariate data. The paper presents ShearLab 3D, a faithful compactly supported shearlet-transform package, and evaluates it against geometric multiscale methods.

1. INTRODUCTION

  • Wavelets sparsely approximate one-dimensional signals, but their isotropic scaling limits their handling of curvilinear singularities and detection of edge orientation in multivariate data.For 2D functions with curvilinear singularities, wavelets do not achieve optimal sparse approximation rates.Source: §1 · pp. 1–2

1.1. Geometric Multiscale Analysis

  • Geometric multiscale analysis seeks systems that capture and sparsely approximate curvilinear geometry, including cartoon-like functions with C2 discontinuity curves.Curvelets achieve optimal sparse approximation for cartoon-like functions, but their rotation operator cannot be faithfully digitalized; contourlets use a filterbank approach.Source: §1.1 · p. 2

1.2. Shearlets and Beyond

  • Shearlets use parabolic scaling, translation, and shearing to change orientation, supporting a unified continuum and digital treatment.Compactly supported shearlets have theory for stable frame bounds and optimal sparse approximation; α-molecules generalize scaling anisotropy, while universal shearlets allow it to vary by scale.Source: §1.2 · pp. 2–3

1.3. Contributions

  • ShearLab 3D extends non-separable compactly supported shearlet transforms to universal shearlets and 3D, and outperforms comparison algorithms in most tested tasks, including speed.Comparisons cover denoising and inpainting in 2D and 3D, and separation in 2D; video denoising is only marginally beaten by BM3D.Source: §1.3 · pp. 3–4

1.4. Outline

  • The paper presents MATLAB software and comparison scripts, made freely accessible for reproducible research.The paper reviews theory, details forward and inverse transforms and implementation, then reports numerical experiments and comparisons.Source: §1.3 · p. 4, §1.4 · p. 4

2. DISCRETE SHEARLET SYSTEMS

The section reviews frames and defines 2D and 3D universal shearlet systems, whose scale-dependent anisotropy extends the parabolic case. It also surveys earlier Fourier- and spatial-domain implementations.

2.1. Review: Frame Theory

  • A frame permits stable, redundant expansions, and its reconstruction formula recovers each element; tight frames simplify inversion, while general frames may require iterative methods.The frame algorithm, Chebyshev method, and conjugate-gradient method are noted as alternatives when direct inversion is numerically difficult.Source: §2.1 · p. 4

2.2. Universal Shearlet Systems

  • Universal shearlets extend shearlet systems by allowing the anisotropy parameter to vary across scales, with parabolic scaling as a special case.The section introduces the 2D and 3D systems, first in the parabolic case and then in the general case.Source: §2.2 · p. 5, §2.2.1 · pp. 6–7, §2.2.2 · p. 7

2.2.1. 2D Situation.

  • In 2D, the shearlet system is indexed by scale j, shear k, and translation m; its associated transform maps functions to a sequence of shearlet coefficients.Source: §2.2.1 · p. 5

2.2.2. 3D Situation.

  • In 3D, universal shearlets use two-parameter shearing and direction-specific scaling and translation; the parabolic extension favors plate-like rather than needle-like elements.Compactly supported generators can yield frames with controllable bounds, while classical band-limited 3D shearlets form Parseval frames after small seam-line modifications.Source: §2.2.2 · pp. 7–8

2.3. Previous Implementations

  • Earlier implementations largely focused on the parabolic case, and Fourier-domain approaches were used for band-limited shearlet transforms.These approaches aim to reproduce frequency tiling, using either Laplacian-pyramid subband decomposition with directional filtering or a weighted pseudo-polar transform followed by windowing and inverse FFTs.Source: §2.3 · p. 8, §2.3.1 · p. 8

2.3.1. Fourier Domain Approaches.

  • Fourier-domain implementations exploit compact Fourier support and tight frames to reproduce frequency tiling, using subband filtering or a weighted pseudo-polar transform.The latter applies windowing and an inverse FFT to each windowed part.Source: §2.3.1 · p. 8

2.3.2. Spatial Domain Approaches.

  • Spatial-domain approaches implement transform filters by convolution and can be based on a broader range of shearlet systems than Fourier-based methods.The paper builds on a digitalization using non-separable compactly supported generators that approximate classical band-limited generators; earlier separable methods enabled fast transforms even without tight frames.Source: §2.3.2 · p. 9

3. DIGITAL SHEARLET TRANSFORM

This section develops digital shearlet transforms in 2D and 3D, including their construction and reconstruction from shearlet coefficients.

3.1. Digital Wavelet Transform

  • The 1D digital wavelet transform reduces to its common form for an orthonormal scaling function, and tensor products extend it to 2D.The 2D construction assumes an orthonormal scaling function.Source: §3.1 · p. 10

3.2.2. The General Case.

  • The 2D universal transform extends the parabolic case to scale-dependent α_j ∈ (0, 2), using integer scaling and adjusted shear ranges for digitalization.The digital scheme uses d_j = ⌈(2 − α_j)j/2⌉ and modifies the scaling and shear operator discretizations accordingly.Source: §3.2 · p. 11, §3.2.2 · pp. 14–15

3.2.1. The Parabolic Case.

  • Nonseparable compactly supported shearlet generators with a 2D fan filter improve frame bounds and directional selectivity over separable generators.Their wedge-shaped essential Fourier support approximates that of a classical shearlet.Source: §3.2.1 · p. 11
  • Refining the horizontal sampling grid makes it invariant under the shear operator, and the resulting digital shearing removes otherwise appearing aliasing.The refined grid is 2^-j/2 Z × Z; samples are interpolated, sheared, then resampled.Source: §3.2.1 · p. 13

3.3. 3D Shearlet Transform

  • For 3D parabolic transforms, the digital filters discretize shearlets by combining 2D shearlet-like components with a 1D wavelet filter.The 3D parabolic case uses scaling A_2^j = diag(2^j, 2^j/2, 2^j/2).Source: §3.3.1 · p. 16
  • The 3D universal transform generalizes scaling to A_dj = diag(2^j, 2^(j−d_j), 2^(j−d_j)) and adjusts both shear-parameter ranges for each scale.Here d_j = ⌈(2 − α_j)j/2⌉, and k_1 and k_2 range from −2⌈(2−α_j)j/2⌉ to 2⌈(2−α_j)j/2⌉.Source: §3.3.2 · p. 17
  • The 3D digital transform is defined using generalized shearlet filters built from Fourier coefficients of a 2D fan filter, a 1D filter, and a discrete shear operator.The definition acts on scaling coefficients and specifies the 3D shearlet coefficients.Source: §3.3.2 · p. 17

3.4. Inverse Shearlet Transform

  • The inverse transform provides stable reconstruction; generally it uses frame-based conjugate gradients, while a direct formula is developed for shift-invariant, unsubsampled 2D parabolic transforms and extended to universal systems and 3D.The direct approach uses dual shearlet filters; the derivation is presented for the 2D parabolic case, with extension to general 2D and 3D cases described as straightforward.Source: §3.4 · pp. 17–19

4. IMPLEMENTATION: SHEARLAB 3D

ShearLab 3D provides forward and inverse digital shearlet transforms for arbitrarily sized two- and three-dimensional signals. Its forward transform computes coefficients in the frequency domain and exposes parameters for scale and directional partitioning.

4. IMPLEMENTATION: SHEARLAB 3D

  • The MATLAB toolbox computes forward and inverse shearlet transforms for arbitrarily sized 2D and 3D signals.It requires MATLAB's Signal Processing and Image Processing Toolboxes; CUDA-compatible NVIDIA cards can be used when the Parallel Computing Toolbox is available.Source: §4 · p. 19

4.1. Forward Transform

  • The forward transform takes the signal, number of scales, shearLevels, a directional filter, and a quadrature mirror lowpass filter as inputs.nScales sets the scale bound, while shearLevels specifies the partition fineness at each scale.Source: §4.1 · pp. 19–20
  • The algorithm constructs frequency-domain shearlet filters from the signal dimensions, nScales, shearLevels, directional filters, and quadrature mirror filter.The output coefficient array has dimensions X × Y × Z × R, where R is the system's redundancy.Source: §4.1 · p. 20
  • The forward transform uses an FFT of the input and pointwise frequency-domain multiplication to compute each shearlet's coefficient vector.The coefficients have size X × Y × Z for a 3D signal, or two dimensions for a 2D input.Source: §4.1 · p. 20

end

ShearLab 3D builds digital shearlet filters from scale, shear, and filter choices, and reconstructs signals using dual filters. Its implementation also omits redundant boundary filters, supports 2D and 3D systems, and has complexity proportional to the system redundancy.

end

  • In 3D, scales correspond to sphere-like passbands and filters use two shear parameters across three pyramids; the parameters also determine the filters and redundancy.The default 2D directional filter is a maximally flat fan filter, and the default lowpass filter is a symmetric maximally flat 9-tap filter.Source: end · pp. 20–21

4.2. Inverse Transform

  • The inverse transform reconstructs a signal by summing convolutions of its coefficients with corresponding dual filters, computed with frequency-domain multiplication.The input is a set of shearlet coefficients and dual filters; an inverse FFT produces the reconstructed signal.Source: §4.2 · p. 21

4.3. Example

  • The MATLAB example displays decomposition and reconstruction, with coefficient-array dimensions indexing translates and the digital filters’ scale and shear parameters.The coefficient array has three dimensions for 2D data and four for 3D data.Source: Figure 6 · p. 22, §4.3 · p. 22

4.4. Omission of Boundary Shearlets

  • Omitting near-duplicate boundary filters reduces the 2D filter count to 2^(d_j+2) per scale; the 3D system similarly removes filters shared across pyramids.For d_j = ceil(j/2), the 2D example has 8, 8, 16, and 16 filters at scales 1–4; boundary filters can be restored if needed.Source: §4.4 · p. 23

4.5. Complexity

  • Both decomposition and reconstruction have complexity O(R · N log(N)), where R is system redundancy.The FFT-based algorithms reduce the transforms to repeated fast Fourier transform computations.Source: §4.5 · p. 23

5. NUMERICAL EXPERIMENTS

The experiments evaluate ShearLab 3D systems on denoising, inpainting, and feature extraction tasks, using parameter choices designed to examine redundancy. The selected filters and systems vary across 2D and 3D experiments.

5. NUMERICAL EXPERIMENTS

  • The experiments cover 2D and 3D denoising and inpainting, plus 2D decomposition of point-like and curvelike structures; scripts and input data are publicly available.The experiments were run with MATLAB 2013a on a Core 2 Duo E6750 CPU and a GeForce GTX 650 Ti GPU.Source: §5 · p. 23

5.1. Selection of Parameters

  • The 9-tap symmetric maximally flat lowpass filter has two vanishing moments; maximal flatness reduces frequency-response ripples and improves shearlet frequency localization.A maximally flat 2D fan filter is used for directional partitioning; the authors favor flatness for most applications over the CDF 9/7 filter’s higher regularity and four vanishing moments.Source: §5.1 · p. 24
  • Two parabolic systems per dimension test redundancy differences: SL2D1 has redundancy 25 and SL2D2 has redundancy 49, while SL3D1 and SL3D2 have redundancies 76 and 292.SL3D1 uses 13, 13, and 49 directions across its three scales; SL3D2 uses 49, 49, and 193.Source: §5.1 · pp. 24–25, Figure 10 · p. 25

5.2. Systems for Comparison

The paper compares ShearLab 3D with several transforms by applying the same sparse-representation algorithms and inputs, assessing output quality and runtime. The comparison spans shearlet, contourlet, curvelet, surfacelet, and wavelet transforms.

Systems for Comparison

  • Across five experiments, each transform is run with the same algorithm and input, and performance is assessed using task-specific output quality and total runtime.The comparison includes ShearLab 3D systems SL2D1, SL2D2, SL3D1, and SL3D2.Source: §5.2 · p. 25
  • The comparison includes NSST in 2D and 3D and NSCT in 2D; both use nonsubsampled multiscale decompositions with directional filters.NSST directional filters are not compactly supported in time, though small-matrix representations yield filters localized in time.Source: §5.2 · pp. 25–26
  • Other baselines are the 2D FDCT and SWT and the 3D surfacelet transform; curvelets use rotated atoms, while shearlets use anisotropic scaling and shearing.The SWT is redundant and translation invariant, using dyadically upsampled filter coefficients rather than downsampling.Source: §5.2 · p. 26

5.3. Image Denoising

The denoising experiments apply hard thresholding to sparse transform coefficients of noisy grayscale images and compare several transforms. Reconstruction quality is measured by PSNR, with running times and redundancies also reported.

Image Denoising

  • Denoising uses 512×512 grayscale images corrupted with Gaussian white noise, followed by hard thresholding of sparse-representation coefficients before reconstruction.Thresholds may vary by scale to improve performance.Source: §5.3 · pp. 26–27
  • For four scales, the typical scale-threshold parameters are K = [2.5, 2.5, 2.5, 3.8].The method uses different thresholds δ_j on different scales.Source: §5.3 · p. 27
  • PSNR measures reconstruction quality, and the comparison reports results, runtime, and redundancy for four images across several noise levels.The evaluated transforms are SL2D1, SL2D2, NSST, NSCT, FDCT, and SWT; the supplied passages do not report the numerical outcomes.Source: §5.3 · p. 27

5.4. Image Inpainting

Image inpainting reconstructs missing pixels from a masked grayscale image through iterative thresholding. The experiments use 300 iterations and compare two ShearLab systems with other transforms across three mask types.

5.4. Image Inpainting

  • Iterative thresholding alternates a forward transform, hard thresholding, and inverse synthesis while progressively lowering the threshold to approximate sparse coefficients consistent with observed pixels.Each iteration combines the unoccluded image with the current inpainting; the procedure follows Starck et al. and Fadili et al..Source: §5.4 · p. 27
  • The comparison uses 300 iterations and evaluates SL2D1 and SL2D2 against NSST, FDCT, and SWT using PSNR; NSCT is excluded because one iteration takes over seven minutes.The numerical results, running times, and redundancies are compiled in Figure 13.Source: §5.4 · pp. 27–28
  • Three mask types are used to represent typical inpainting problems, and the input is a grayscale image occluded by a binary mask.The masked image is formed by pointwise multiplying the image by the mask.Source: §5.4 · p. 27

5.5. Image Decomposition

The image-decomposition experiment separates curvilinear structures from isotropic, blob-like structures. It uses directional and stationary-wavelet transforms with iterative thresholding, then evaluates the resulting sparse representations.

5.5. Image Decomposition

  • The experiment assumes an image can be split into a curvilinear part and a part containing isotropic blob-like structures.Figure 14 depicts the input and the intended decomposition.Source: §5.5 · p. 28, Figure 14 · p. 30
  • The decomposition algorithm applies a directional transform to the residual for the blob-like component and a stationary wavelet transform to the residual for the curvilinear component, with hard thresholding before synthesis.Gradually decreasing the threshold approximates components sparse in their respective dictionaries.Source: §5.5 · p. 29
  • Evaluation is restricted to binary images and compares SL2D1 and SL2D2 with NSST and FDCT; Figures 15–16 compile numerical results, redundancies, and running times.Visual comparisons are provided in the appendix.Source: §5.5 · pp. 29–30

5.6. Video Denoising

The video-denoising experiment evaluates ShearLab 3D on noisy grayscale videos. It compares PSNR with the 3D nonsubsampled shearlet and surfacelet transforms across multiple videos and noise levels.

5.6. Video Denoising

  • The typical digital-transform configuration uses three scales with K = [3, 3, 4].The threshold schedule is described as scale-dependent.Source: §5.6 · p. 31
  • The evaluation uses three grayscale videos of size 192 × 192 × 192 with Gaussian noise levels σ = 10 to 50, comparing ShearLab 3D with 3D NSST and the surfacelet transform using PSNR.Numerical results are compiled in Figure 17.Source: §5.6 · pp. 30–31

5.7. Video Inpainting

Video inpainting reconstructs missing regions in grayscale videos using iterative thresholding. The experiments compare two ShearLab systems with the surfacelet transform under two mask patterns.

5.7. Video Inpainting

  • The video is partially occluded by a binary mask before the missing regions are reconstructed.The mask is defined over the three-dimensional video domain.Source: §5.7 · p. 31
  • The experiments use grayscale videos of size 192 × 192 × 192 and apply iterative thresholding for 50 iterations to fill missing regions.The algorithm follows Starck et al. and Fadili et al..Source: §5.7 · p. 31
  • The evaluation compares SL3D1 and SL3D2 with SURF using a random mask with 80% occlusion and random-size cubes with 5% occlusion.Numerical results are compiled in Figure 18.Source: §5.7 · p. 31, Figure 18 · p. 32

5.8. Discussion

ShearLab 3D generally leads the tested transforms on quantitative measures, with occasional NSST exceptions; CUDA can substantially shorten runtime in heavy tasks. The experiments compare transform applicability rather than claiming task-specific optimization.

5.8. Discussion

  • Across experiments, ShearLab 3D’s sparse approximations achieve the best quantitative results except in some cases where NSST slightly outperforms it.The discussion cites Figure 11 as an example of an NSST exception.Source: §5.8 · p. 32
  • For coastguard video denoising (144 × 176 × 300, σ = 30), BM3D’s PSNR is 29.69 versus 29.54 for SL3D2.The authors describe ShearLab 3D as only marginally beaten by BM3D in this example.Source: §5.8 · p. 32
  • CUDA can increase speed by up to a factor of 10 in computationally heavy image or video inpainting tasks.The discussion points to Figures 13 and 17.Source: §5.8 · p. 32
  • The experiments aim to compare ShearLab 3D’s applicability with similar transforms, not to establish specific adaptation to a task such as image denoising.Source: §5.8 · p. 32
Loading 1402.5670v1…