Methods for performing fast discrete curvelet transforms of data

• US 7,840,625 B2
• Filed: 04/07/2006
• Issued: 11/23/2010
• 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 Management Co.)
• Original Assignee: California Institute of Technology, Stanford University
• Inventors: Donoho, David, Demanet, Laurent, Candes, Emmanuel
• Primary Examiner(s): Mai; Tan V
• Application Number:
  US11/400,048
• Publication Number:
  US 20070038691A1
• Time in Patent Office: 1,691 Days
• Field of Search: 708400-402
• US Class Current: 708/402
• 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 transforming an image for use with a data processor comprising:

converting said image to a plurality of image pixel data; and

performing a discrete curvelet transformation on the plurality of image pixel data,

wherein the performing of the discrete curvelet transform comprises;

representing the plurality of image pixel data in the frequency space or Fourier domain by means of a Fourier transform; and

dividing the Fourier transform of the plurality of image pixel 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.

2. The method for transforming an image according to claim 1, wherein the division of the frequency plane comprises using a smooth partition of unity, or square-root thereof, made of overlapping indicators.

3. The method for transforming an image according to claim 1, wherein each trapezoidal or prismoidal region corresponds to a given scale/orientation combination.

4. The method for transforming an image according to claim 1, wherein which the performing of the discrete curvelet transform further comprises:

resampling the array of the plurality of image pixel 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;

shearing each tilted grid into a Cartesian grid; and

applying the inverse Fast Fourier Transform to the data array on each Cartesian grid.

5. The method according to claim 4, wherein the resampling within each trapezoidal or prismoidal region further comprises performing unequispaced Fast Fourier Transforms.

6. The method for transforming an image according to claim 1, wherein the performing of the digital curvelet transform on the plurality of image pixel data further comprises:

wrapping the array of the plurality of image pixel data within each trapezoidal or prismoidal region in the Fourier domain into a rectangular or parallelepipedal region near the origin; and

applying the inverse Fast Fourier Transform to each wrapped data array, within the rectangular or parallelepipedal region near the origin.

7. The method according to claim 6, wherein the wrapping of the plurality of image pixel data within each trapezoidal or prismoidal region comprises making use of periodization to extend Fourier samples inside the rectangular or parallelepipedal region.

8. The method according to claim 6 being an isometry in exact arithmetic.

9. The method according to claim 1, wherein the performing of the discrete curvelet 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 a y axis.

10. The method according to claim 1, wherein the performing of the discrete curvelet 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, a y, or a z axis.

11. The method according to claim 1, wherein the performing of the discrete curvelet transform further comprises returning a table of digital curvelet coefficients indexed by a scale parameter, an orientation parameter, and a spatial location parameter.

12. The method according to claim 1, wherein the discrete curvelet transform is invertible by means of an inverse discrete curvelet transform.

13. The method according to claim 12, wherein the performing of the inverse discrete curvelet transform comprises:

taking as input the table of digital curvelet coefficients; and

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

14. The method according to claim 13, wherein the performing of the inverse discrete curvelet transform further comprises:

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

resampling each sheared data onto a Cartesian grid;

windowing by a corresponding indicator;

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

performing an inverse Fourier transform of the sum.

15. The method according to claim 14, wherein the resampling of the sheared data comprises performing inverse unequispaced Fast Fourier transforms.

16. The method according to claim 13, wherein the performing of the inverse discrete curvelet transform further comprises:

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

windowing by the corresponding indicator;

summing the contribution from each scale and angle; and

performing an inverse Fourier transform of the sum.

17. The method according to claim 16, wherein the unwrapping of the array of the Fourier-transformed data onto a trapezoidal or prismoidal region comprises making use of periodization to extend Fourier samples inside the trapezoidal or prismoidal region.

18. The method according to claim 13, wherein the inverse discrete curvelet transform 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 a y axis.

19. The method according to claim 13, wherein the inverse discrete curvelet transform 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.

20. The method according to claim 1, wherein the transforming of the image comprises compressing the plurality of image pixel data.

21. The method according to claim 1, wherein the transforming of the image comprises identifying transients or salient features in the plurality of image pixel data.

22. The method according to claim 1, wherein the transforming of the image is used to conduct numerical simulations of partial differential equations.

23. The method according to claim 1, wherein the transforming of the image further comprises removing noise from the plurality of image pixel data, or restore otherwise degraded image pixel datasets.

24. The method according to claim 1, wherein the transforming of the image is used to solve inverse problems.

25. The method according to claim 24, wherein the transforming of the image is used to solve inverse problems in computerized tomography.

26. The method according to claim 25, wherein the transforming of the image is used to solve inverse problems in limited-angle tomography.