Methods for performing fast discrete curvelet transforms of data

• US 20070038691A1
• Filed: 04/07/2006
• Published: 02/15/2007
• Est. Priority Date: 04/07/2005
• Status: Active Grant

• Current Assignee: California Institute of Technology, Board of Trustees of the Leland Stanford Junior University (Stanford University)
• Original Assignee: Board of Trustees of the Leland Stanford Junior University (Stanford University)
• Inventors: Candes, Emmanuel, Donoho, David, Demanet, Laurent
• Granted Patent: US 7,840,625 B2
• Time in Patent Office: Days
• US Class Current: 708/400
• CPC Class Codes: G06F 17/141 Discrete Fourier transforms
• CPC Class Codes: G06F 17/148 Wavelet transforms

Abstract

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.

Claims

1. A method for manipulating data in a data processor, comprising performing a discrete curvelet transform on the data.

2. The method for manipulating data in a data processor according to claim 1, in which the step of performing the transform comprises:

(a) representing the data in the frequency space or Fourier domain by means of a Fourier transform; and

(b) dividing the Fourier transform of the data into dyadic annuli based on concentric squares for two-dimensional data or concentric cubes for three-dimensional data and each annulus is subdivided into trapezoidal regions for two-dimensional data or prismoids for three-dimensional data.

3. The method for manipulating data in a data processor according to claim 2 in which the step of division of the frequency plane comprises using a smooth partition of unity, or square-root thereof, made of overlapping indicators.

4. The method for manipulating data in a data processor according to claim 2 in which each trapezoidal or prismoidal region corresponds to a given scale/orientation combination.

5. The method for manipulating data in a data processor according to claim 2 in which the step of performing the transform further comprises:

(c) a step of resampling the array of the data within each trapezoidal or prismoidal region in the Fourier domain, according to an equispaced grid tilted to be aligned with the axes of the trapezoid or prismoid;

(d) a step of shearing each tilted grid into a Cartesian grid;

(e) a step of applying the inverse Fast Fourier Transform to the data array on each Cartesian grid.

6. The method according to claim 5 in which the step of resampling within each trapezoidal or prismoidal region further comprises the step of performing unequispaced Fast Fourier Transforms.

7. The method for manipulating data in a data processor according to claim 2 in which the step of performing a digital curvelet transform on the data further comprises:

(c) a step of wrapping the array of the data within each trapezoidal or prismoidal region in the Fourier domain into a rectangular or parallelepipedal region near the origin; and

(d) a step of applying the inverse Fast Fourier Transform to each wrapped data array, within the rectangular or parallelepipedal region near the origin.

8. The method according to claim 7 in which the step of wrapping data within each trapezoidal or prismoidal region comprises making use of periodization to extend Fourier samples inside the rectangular or parallelepipedal region.

9. The method according to claim 7 being an isometry in exact arithmetic.

10. The method according to claim 1 in which the step of performing the transform runs in O(n² log n) floating point operations for n by n Cartesian arrays, wherein n is the number of discrete information bits in a direction along an x or ay axis.

11. The method according to claim 1 in which the step of performing the transform runs in O(n³ log n) floating point operations for n by n by n Cartesian arrays, wherein n is the number of discrete information bits in a direction along an x, ay or a z axis.

12. The method according to claim 1 in which the step for performing the transform further comprises returning a table of digital curvelet coefficients indexed by a scale parameter, an orientation parameter, and a spatial location parameter.

13. The method according to claim 1 in which the transform is invertible by means of an inverse transform.

14. The method according to claim 13 in which the step of performing the inverse transform comprises (a) taking as input the table of digital curvelet coefficients;

(b) performing a Fast Fourier transform of the coefficients at each scale and angle.

15. The method according to claim 13 in which the step of performing the inverse transform further comprises:

(c) shearing the array of the Fourier-transformed data at each scale and angle onto a trapezoidal or prismoidal grid;

(d) resampling each sheared data onto a Cartesian grid;

(e) windowing by a corresponding indicator;

(f) summing a contribution at each scale and angle to produce a sum; and

(g) performing an inverse Fourier transform of the sum.

16. The method according to claim 15 in which the step of resampling sheared data comprises performing inverse unequispaced Fast Fourier transforms.

17. The method according to claim 13 in which the step of performing the inverse transform further comprises:

(c) unwrapping the array of the Fourier-transformed data at each scale and angle onto a trapezoidal or prismoidal region;

(d) windowing by the corresponding indicator;

(e) summing the contribution from each scale and angle; and

(f′

) performing an inverse Fourier transform of the sum.

18. The method according to claim 17 in which the step of unwrapping data onto a trapezoidal or prismoidal region comprises making use of periodization to extend Fourier samples inside the trapezoidal or prismoidal region.

19. The method according to claim 13 in which the inversion algorithm runs in about O(n² log n) floating point operations for n by n Cartesian arrays, wherein n is a number of discrete information bits in a direction along an x or ay axis.

20. The method according to claim 13 in which the inversion algorithm runs in about O(n³ log n) floating point operations for n by n by n Cartesian arrays, wherein n is a number of discrete information bits in a direction along an x, a y or a z axis.

21. The method according to claim 1 in which the transform is used to compress data.

22. The method according to claim 1 in which the transform is used to identify transients or salient features in the data.

23. The method according to claim 1 in which the transform is used to conduct numerical simulations of partial differential equations.

24. The method according to claim 1 in which the transform is used to remove noise from signals or images, or restore otherwise degraded datasets.

25. The method according to claim 1 in which the transform is used to solve inverse problems.

26. The method according to claim 25 in which the transform is used to solve inverse problems in computerized tomography.

27. The method according to claim 26 in which the transform is used to solve inverse problems in limited-angle tomography.