Fourier Theory and its Application to VisionRoad Map of the TalkSampling Theory - ADCSampling theory - DACNyquist Sampling TheoremAliasingExamples of aliasingAliasingSignals and VectorsComponent of a signalComponent of a signalComponent of a signalGibb’s phenomenonFourier transformWhy the Fourier transform?Discrete Fourier TransformFast Fourier TransformFFTConclusionReferencesFourier Theory and its Application to VisionMani ThomasCISC 489/689Road Map of the Talk Sampling and Aliasing Fourier Theory Basics Signals and Vectors 1D Fourier Theory DFT and FFT 2D Fourier Theory Linear Filter theory Image Processing in spectral domain ConclusionsSampling Theory - ADC Real signals are continuous, but the digital computer can only handle discretized version of the data. Analog to digital conversion and vice versa (ADC and DAC) Sampling measures the analog signal at different moments in time, recording the physical property of the signal (such as voltage) as a number. Approximation to the original signal From the vertical scale, we could transmit the numbers 0, 5, 3, 3, -4, ... as the approximationCourtesy of: http://puma.wellesley.edu/~cs110/lectures/M07-analog-and-digital/Courtesy of: http://www.cs.ucl.ac.uk/staff/jon/mmbook/book/node96.htmlSampling theory - DAC Digital to Analog conversion Reconstruct the signal from the digital signal Essentially drawing a curve through the points Multiple possible curve can be drawn in (a) First part appears correct but errors in the latter part In (b), sampling has been doubled Reconstructed curve is much better Increased amount of numbers to be transmitted.Courtesy of: http://puma.wellesley.edu/~cs110/lectures/M07-analog-and-digital/Nyquist Sampling Theorem How often must we sample? First articulated by Harry Nyquist and later proven by Claude Shannon Sample twice as often as the highest frequency you want to capture.fs≥ 2× fH(Nyquist rate) fsis the sampling frequency and fHis the highest frequency present in the signal For example, highest sound frequency that most people can hear is about 20 KHz (with some sharp ears able to hear up to 22 KHz), we can capture music by sampling at 44 KHz.  That's how fast music is sampled for CD-quality musicCourtesy of: http://puma.wellesley.edu/~cs110/lectures/M07-analog-and-digital/Aliasing If the sampling condition is not satisfied, then frequencies will overlap Aliasing is an effect that causes different continuous signals to become indistinguishable (or aliases of one another) when sampled.Courtesy of http://en.wikipedia.org/wiki/AliasingExamples of aliasing Example1 The sun moves east to west in the sky, with 24 hours between sunrises.  If one were to take a picture of the sky every 23 hours, the sun would appear to move west to east, with 24 × 23 = 552 hours between sunrises.  Wagon Wheel effect – Temporal Aliasing The same phenomenon causes spoked wheels to apparently turn at the wrong speed or in the wrong direction when filmed, or illuminated with a flashing light source. Moire pattern – Spatial Aliasing Stripes captured on a digital camera would cause aliasing between the stripes and the camera sensor. Distance between the stripes is smaller than what the sensor can capture Solution to this would be to go closer or to use a higher resolution sensorCourtesy of http://en.wikipedia.org/wiki/AliasingAliasing To prevent aliasing, two things can be done Increase the sampling rate  Introduce an anti-aliasing filter Anti- aliasing filter - restricts the bandwidth of the signal to satisfy the sampling condition.  This is not satisfiable in reality since a signal will have someenergy outside of the bandwidth.  The energy can be small enough that the aliasing effects are negligible (not eliminated completely). Anti- aliasing filter: low pass filters, band pass filters, non-linear filters Always remember to apply an anti- aliasing filter prior to signal down-sampling Adapted from http://en.wikipedia.org/wiki/Nyquist-Shannon_sampling_theoremSignals and Vectors Signals Ù Vectors (Perfect analogy) Projection of one vector on another Minimum Error when orthogonalfffe1e2ex x xxcxc1xc2xcferrr−=xcferrr11−= xcferrr22−=xfxfcfxcrrxxxrrrrrrr.1.cos ==⇒=θ.2Component of a signal Approximating in terms of another real signal over an interval  Minimizing the error signal,  Simplification of the above yields the following()tf()tx[]21,tt()()()⎩⎨⎧≤≤−=otherwisettttcxtfte021() ()[]0212=⎥⎥⎦⎤⎢⎢⎣⎡−∫ttdttcxtfdcd()()()∫212ttdttx∫=21ttdttxtfcComponent of a signal Generalizing over N-dimensions As the error energy , which makes the orthogonal set complete i.e. Generalizing to complex signals we have () () ()∑=−=Nnnntxctfte1() ()()∫∫=21212ttnttnndttxdttxtfc∞→N() () () () ()∑∞==+++=12211nnnnntxctxctxctxctf LL() ()() ()∫∗=211ttnnndttxtxc∫∗2ttndttxtf0→eEComponent of a signal The series so obtained is the GENERALIZED FOURIER SERIES of with respect to  The set is called the basis function or kernel Some well- known basis signals are  Trigonometric Exponential Walsh Bessel Legendre Hermite()tf(){}txn(){}txnGibb’s phenomenon Phenomenon of “ringing” The series exhibits an oscillatory phenomenon The overshoot remained 9% regardless of the number of terms First explained by Willard Gibbs Non uniform convergence at the points of discontinuities The 9% was approximately equal to 1/2n where n is the number of termscourtesy of H. Hel-OrFourier transform Using exponential basis of representation Modeling any aperiodic signal  Forward transform: time signal into frequency domain representation Inverse transform: frequency representation into the time domain representation Fourier transform pairs: http://130.191.21.201/multimedia/jiracek/dga/spectralanalysis/examples.html() () () ()∫∫∞∞−−∞∞−== dtetfwFdwewFtfjwtjwtπ21()tfWhy the Fourier transform? Some really useful properties Modulation Time differentiation But for computer vision, two of the most important properties are Convolution Time-shifting property() ()()0002121)cos()()(ωωωωωω−++=⇔= FFYttfty()()()ωωFjdttdfnnn⇔()()ωωFettftj0 0 −⇔−())()()(ωωGFtgtf⇔∗Discrete Fourier Transform