Methods for performing fast discrete curvelet transforms of data

摘要

Fast digital implementations of the second generation curvelet transform for use in data processing are disclosed. One such digital transformation is based on unequally-spaced fast Fourier transforms (USFFT) while another is based on the wrapping of specially selected Fourier samples. Both digital transformations return a table of digital curvelet coefficients indexed by a scale parameter, an orientation parameter, and a spatial location parameter. Both implementations are fast in the sense that they run in about O(n² log n) flops for n by n Cartesian arrays or about O(N log N) flops for Cartesian arrays of size N=n³; in addition, they are also invertible, with rapid inversion algorithms of about the same complexity.