It is not currently known if it is possible to accurately form a synthetic aperture radar image from N data
points in provable near-linear complexity, where accuracy is defined as the ℓ2 error between the full O(N2)
backprojection image and the approximate image. To bridge this gap, we present a backprojection algorithm
with complexity O(log(1/ε)N log N), with ε the tunable pixelwise accuracy. It is based on the butterfly scheme,
which works for vastly more general oscillatory integrals than the discrete Fourier transform. Unlike previous
methods this algorithm allows the user to directly choose the amount of acceptable image error based on a
well-defined metric. Additionally, the algorithm does not invoke the far-field approximation or place restrictions
on the antenna flight path, nor does it impose the frequency-independent beampattern approximation required
by time-domain backprojection techniques.
We present variants of both the digital curvelet transform, and the digital wave atom transform, which handle
the image boundaries by mirror extension. Previous versions of these transforms treated image boundaries by
periodization. The main ideas of the modifications are 1) to tile the discrete cosine domain instead of the
discrete Fourier domain, and 2) to adequately reorganize the in-tile data. In their shift-invariant versions, the
new constructions come with no penalty on the redundancy or computational complexity. For shift-variant wave
atoms, the penalty is a factor 2 instead of the naive factor 4.
These various modifications have been included in the CurveLab and WaveAtom toolboxes, and extend
the range of applicability of curvelets (good for edges and bandlimited wavefronts) and wave atoms (good for
oscillatory patterns and textures) to situations where periodization at the boundaries is uncalled for. The new
variants are dubbed ME-curvelets and ME-wave atoms, where ME stands for mirror-extended.
In this paper, we present the first 3D discrete curvelet transform. This transform is an extension to the 2D transform described in Candes et al..1 The resulting curvelet frame preserves the important properties, such as parabolic scaling, tightness and sparse representation for singularities of codimension one. We describe three different implementations: in-core, out-of-core and MPI-based parallel implementations. Numerical results verify the desired properties of the 3D curvelets and demonstrate the efficiency of our implementations.
We propose the construction of directional - or Gabor - continuous wavelets on the sphere. We provide a criterion to measure their angular selectivity. We finally discuss implementation issues and potential applications. The code for the spherical wavelet transform is available in the YAWTB Matlab Toolbox, http://www.yawtb.be.tf.