DOC PREVIEW
UW-Madison ECE 734 - THE VERY FAST CURVELET TRANSFORM

This preview shows page 1-2-3-4 out of 11 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Appendix.pdfAppendix A – MMX Optimization Example Appendix B – SSE Optimization ExampleTHE VERY FAST CURVELET TRANSFORMBrian [email protected] 734 - VLSI Structures for Digital Signal ProcessingFinal Project ReportABSTRACTThe Digital Curvelet Transform provides near-optimal recon-struction of twice-continuously differentiable (C2) curves. Pre-vious implementations of the algorithm have not exploitednewer technologies in modern processors, including the MMXand SSE instruction sets. Various optimization techniqueswere used on a form of the Digital Curvelet Transform re-sulting in the fastest Curvelet Transform currently available.1. INTRODUCTIONCurrent work in Computational Harmonic Analysis focuseson developing multiscale data representation techniques torepresent objects in a sparse manner. The sparser the repre-sentation, the fewer the number of coefficients that are neededto be transmitted (allowing for the use of various compressionschemes), and the better the denoising that will result fromcoefficient shrinkage ([2]). While fourier analysis works wellon periodic structures (such as textures), and wavelet analy-sis works well on singularities (such as corners), neither par-ticularly can reconstruct edges in a sparse matter. Curveletswere originally introduced in [1] as a non-adaptive transformthat achieves near optimal m-term approximation rates in L2for twice-continuously differentiable curves¡C2¢. While theperformance rates for the Curvelet Transform are quite good,the computational complexity of the algorithm is less promis-ing. Current state-of-the-art techniques allow for a lower boundcomputation time of between 8 and 10 times the speed of anFFT of the original image. For practical purposes, this com-putation time must be reduced.2. CONTINUOUS CURVELET TRANSFORMThe Continuous Curvelet Transform has gone through twomajor revisions. The first Continuous Curvelet Transform [1](commonly referred to as the ”Curvelet ’99” transform now)used a complex series of steps involving the ridgelet analysisof the radon transform of an image. Performance was exceed-ingly slow.The algorithm was updated in 2003 in [3]. The use of theRidgelet Transform was discarded, thus reducing the amountof redundancy in the transform and increasing the speed con-siderably. In this new method, an approach of curvelets astight frames is taken. Using tight frames, an individual curvelethas frequency support in a parabolic-wedge area of the fre-quency domain (as seen in figure 1.).Figure 1. Continuous Curvelet support in the frequency domainA sequence of curvelets {γj,l,k} are tight frames if thereexists some value for A such that :A ||f||2L2=Xj,l,k|hf, γj,l,ki|2: ∀f ∈ L2(1)Where each curvelet in the space domain is defined as:γj,l,k= 22j3γ (DjRθx − kδ) (2)(With Dj= Parabolic Scaling matrix, Rθ= Rotation matrix,kδ= translation parameter, γ = the ”mother” curvelet)Using the property of tight frames, the inverse of the curvelettransform is easily found as:f =Xj,l,khf, γj,l,ki γj,l,k(3)In [3], a heuristic argument is made that all curvelets fallinto one of three categories.1. A curvelet whose length-wise support does not inter-sect a discontinuity The curvelet coefficient magnitudewill be zero. (Figure 2..)2. A curvelet whose length-wise support intersects with adiscontinuity, but not at its critical angle. The curveletcoefficient magnitude will be close to zero. (Figure 3.)3. A curvelet whose length-wise support intersects with adiscontinuity, and is tangent to that discontinuity. Thecurvelet coefficient magnitude will be much larger thanzero. (Figure 4.)Figure 2. Curvelet Type AFigure 3. Curvelet Type B3. WHY CURVELETS?The fundamental questions should now be, ”Why exactly shouldI use this Curvelet Algorithm?” This can be answered in oneFigure 4. Curvelet Type Cword, sparsity. As can be seen in Figures 2-4, when perform-ing the curvelet transform on a C2curve, very few curveletcoefficients will be above negligible magnitude values. In[3], it is declared that curvelets offer optimal sparseness for”curve-punctuated smooth” images, where the image is smoothwith the exception of discontinuities along C2curves. Sparse-ness is measured by the rate of decay of the m-term approx-imation (reconstruction of the image using m number of co-efficients) of the algorithm. Having a sparse representation,along with offering improved compression possibilities, alsoallows for improving denoising performance [2] as additionalsparseness increases the amount of smooth areas in the image.In [6] it was shown that orthogonal systems have optimal m-term approximations that decay in L2with rate O¡m−2¢(as alower bound). Currently, there does not exist a single compu-tationally feasible transform that will obtain this lower bound.On images with C2boundaries, non-optimal systems have therates:Fourier Approximation:¯¯¯¯f − fFm¯¯¯¯2L2³ O³m−12´(4)Wavelet Approximation:¯¯¯¯f − fWm¯¯¯¯2L2³ O¡m−1¢(5)Curvelet Approximation:¯¯¯¯f − fCm¯¯¯¯2L2³ O³(log m)3m−2´(6)As seen from the m-term approximations, the Curvelet Trans-form offers the closest m-term approximation to the lowerbound. Therefore, in images with a large number of C2curves(i.e. an image with a great number of long edges), it would beadvantageous to use the Curvelet Algorithm.4. DISCRETE CURVELET TRANSFORM -WRAPPINGUsing the theoretical basis in [3] (where the continuous curvelettransform is created), two separate digital (or discrete) curvelettransform (DCT) algorithms are introduced in [4]. The firstalgorithm is the Unequispaced FFT Transform, where the curveletcoefficients are found by irregularly sampling the fourier co-efficients of an image. The second algorithm is the the Wrap-ping transform, using a series of translations and a wrap-around technique. Both algorithms having the same output,but the Wrapping Algorithm gives both a more intuitive al-gorithm and faster computation time. Because of this, theUnequispaced FFT method will be ignored in this paper withfocus solely on the Wrapping DCT method.Wrapping DCT Algorithm (as described in [4]):1. Take FFT of the image2. Divide FFT into collection of Digital Corona Tiles(Figure 5.)3. For each corona tile(a) Translate the tile to the origin (Figure 6.)(b) Wrap the parallelogram shaped support of thetile around a rectangle centered at the origin(Figure 7.).(c) Take the Inverse FFT of the wrapped support(d) Add the curvelet array to


View Full Document

UW-Madison ECE 734 - THE VERY FAST CURVELET TRANSFORM

Documents in this Course
Load more
Download THE VERY FAST CURVELET TRANSFORM
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view THE VERY FAST CURVELET TRANSFORM and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view THE VERY FAST CURVELET TRANSFORM 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?