Fast Polar Fourier Transform - Technion快速极坐标傅里叶变换-技术研究.pptVIP

Fast Polar Fourier Transform Michael Elad* Scientific Computing and Computational Mathematics Stanford University FoCM Conference, August 2002 Image and Signal Processing Workshop IMA - Minneapolis Collaborators 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 Conclusions ? 1. Thinking Polar - Continuum For today f(x,y) function of (x,y)??2 Continuous Fourier Transform Natural Operations: 1. Rotation Using the polar coordinates, rotation is simply a shift in the angular variable. 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 Conclusions ? 2. Thinking Polar - Discrete Certain procedures very important to digitize Rotation, Scaling, Registration, Tomography, and … These look so easy in continuous theory – Can’t we use it in the discrete domain? Why not Polar-FFT? Polar FFT - Current Status 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 Conclusions ? 3. Current State-Of-The-Art Assessing T: Unequally-spaced FFT (USFFT) Data in Cartesian set. Approximate transform in non-Cartesian set. Oriented to 1D – not 2D and definitely not Polar. 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 Conclusions 4. Our Approach - General Low complexity – O(Const·N2log2N) Vectorizability – 1D operations only Non-Expansiveness – Factor 2 (or 4) only Stability – via Regularization Accuracy – 2 orders of magnitude over USFFT methods Agenda Thinking Polar – Continuum Thinking Polar –