Fast Polar Fourier TransformMichael Elad*Scientific Computing and Computational MathematicsStanford UniversityFoCM Conference, August 2002Image and Signal Processing WorkshopIMA - Minneapolis* Joint work with Dave Donoho (Stanford-Statistics), Amir Averbuch (TAU-CS-Israel), and Ronald Coifman (Yale-Math)1 -CollaboratorsDave DonohoStatistics Department StanfordAmir AverbuchCS Department Tel -Aviv UniversityRonald CoifmanMath. Department Yale 2 -Fast Polar Fourier Transformq FFT is one of top 10 algorithms of 20th century.q Well extend utility of FFT algorithms to new class of settings in image processing.q Create a tool which is:Free of emotional involvement, OR Y=Polar_FFT(X,St,Sr);46 -The Implementation7. Algorithm Analysisq The current Polar-FFT code implements Taylor method for the first interpolation stage and spline ONLY (no-derivatives) for the second stage.q For comparison, we demonstrate the performance of the USFFT method with over-sampling S and interpolation based on the Taylor interpolation (found to be the best). 47 -10203040506070809010010-310-210-1100101102StSr or S2|Approximation error|1Error for Specific Signal 7. Algorithm AnalysisTaylor USFFTSt=4 Input is random 32-by-32 array, USFFT method uses one parameter whereas there are two for the up-sampling in the Polar-FFT. Thumb rule: SrSt= S2.St=2 St=3St=1Thumb rule: Sr=4St 48 -Error For Specific Signals7. Algorithm Analysisq Similar curves obtained of |*| and |*|2 norms.q Similar behavior is found for other signals.q Conclusion: For the proper choice of St and Sr, we get 2-orders-of-magnitude improvement in the accuracy comparing to the best USFFT method. q Further improvement should be achieved for Taylor interpolation in the second stage. q US-FFT takes longer due the 2D operations.49 -The Transform as a Matrix7. Algorithm AnalysisAll the involved transformations (accurate and approximate) are linear - they can be represented as a matrix of size 4N2-by-N2. Ya=AxOr Yt=Tx ApproximateTrue50 -Regularization of T/A7. Algorithm Analysisq An input signal of N-by-N is transformed to an array or 2N-by-2N. q For N=16, T size is 1024-by-256, and 60,000 (bad for inversion).q Adding the assumption that the Frequency corners should be zeroed, we obtainand the condition number becomes 5 !51 -Discarding the Corners?7. Algorithm Analysis-q If the given signal was sampled at 1.4142 the Nyquist Rate, the corners can be removed.q If it is not, over- sampling it can be done by FFT.52 -7. Algorithm AnalysisError Analysis Worst SignalApproximation error is : Worst error :Worst relative error :53 -7. Algorithm AnalysisWorst Signal - ResultsN=16 TC 1024256, S=Sr=St=4USFFT worst signal (abs. Value) =3.469The worst case signal in the freq. Domain (abs. and shifted)Polar-FFT worst signal (abs. Value) =0.0319The worst case signal in the freq. Domain (abs. and shifted)54 -7. Algorithm AnalysisRelative Worst Signal - ResultsSame parameters: N=16 TC 1024256, S=Sr=St=4USFFT worst signal (abs. Value) =0.0613The worst case signal in the freq. Domain (abs. and shifted)Polar-FFT worst signal (abs. Value) =0.0023The worst case signal in the freq. Domain (abs. and shifted)55 -7. Algorithm AnalysisComparing Approximationsq Solve for the eigenvalue/vectors of the matrix and obtained ( in ascending order).q Compare to by computingusing the above eigenvectors and compare to .56 -7. Algorithm AnalysisComparing Approximations - Results02004006008001000120010-1010-810-610-410-2100102USFFTPolar-FFT Eigen-space of the Polar- FFTMean Squared ErrorN=3257 -Agenda Thinking Polar Continuum Thinking Polar Discrete Current State-Of-The-Art Our Approach - General The Pseudo-Polar Fast Transform From Pseudo-Polar to Polar Algorithm Analysis Conclusions58 -8. Conclusionsq We have proposed a fast, accurate, stable, and reliable Polar Discrete-Fourier-Transform.q By this we extend utility of FFT algorithms to new class of settings in image processing.q Future plans: Extend the analysis and improve further, Demonstrate applications, Publish the code for the procedure and some applications over the internet.59 -Beyond this slides are the appendix or redundant slides 60 -USFFT for T3. Current State-of-the-Artq Over-sample Polar grid (and possibly partial derivatives).q Associate polar neighbors to each Cartesian grid point. q Approximate interpolation to get the Cartesian grid values. q Perform the Cartesian 2D Inverse-FFT.61 -Our Reading of Literature3. Current State-of-the-Artq Natterer (1985).q Jackson, Meyer, Nishimura and Macovski (1991).q Schomberg and Timmer (1995). q Choi and Munson (1998). Direct Fourier method with over-sampling and interpolation (also called gridding) see 62 -The Pseudo-Polar SamplingBasically vertical line