1CMU SCS15-826: Multimedia Databases and Data MiningDSP tools: Fourier and WaveletsC. Faloutsos15-826 Copyright: C. Faloutsos (2005) 2CMU SCSOutlineGoal: ‘Find similar / interesting things’• Intro to DB• Indexing - similarity search• Data Mining15-826 Copyright: C. Faloutsos (2005) 3CMU SCSIndexing - Detailed outline• primary key indexing• ..• multimedia• Digital Signal Processing (DSP) tools– Discrete Fourier Transform (DFT)– Discrete Wavelet Transform (DWT)15-826 Copyright: C. Faloutsos (2005) 4CMU SCSDSP - Detailed outline• DFT– what– why– how – Arithmetic examples– properties / observations– DCT– 2-d DFT– Fast Fourier Transform (FFT)15-826 Copyright: C. Faloutsos (2005) 5CMU SCSIntroductionGoal: given a signal (eg., sales over time and/or space)Find: patterns and/or compressyearcountlynx caught per year15-826 Copyright: C. Faloutsos (2005) 6CMU SCSWhat does DFT do?A: highlights the periodicities215-826 Copyright: C. Faloutsos (2005) 7CMU SCSWhy should we care?A: several real sequences are periodicQ: Such as?15-826 Copyright: C. Faloutsos (2005) 8CMU SCSWhy should we care?A: several real sequences are periodicQ: Such as?A: – sales patterns follow seasons;– economy follows 50-year cycle– temperature follows daily and yearly cyclesMany real signals follow (multiple) cycles15-826 Copyright: C. Faloutsos (2005) 9CMU SCSWhy should we care?For example: human voice!• Frequency analyzer http://www.relisoft.com/freeware/freq.html• speaker identification• impulses/noise -> flat spectrum• high pitch -> high frequencyFreq.exe15-826 Copyright: C. Faloutsos (2005) 10CMU SCS‘Frequency Analyzer’15-826 Copyright: C. Faloutsos (2005) 11CMU SCSDFT and stocks0.002000.004000.006000.008000.0010000.0012000.001 11 21 31 41 51 61 71 81 91 101 111 121Fourier a ppx actual• Dow Jones Industrial index, 6/18/2001-12/21/200115-826 Copyright: C. Faloutsos (2005) 12CMU SCSDFT and stocks0.002000.004000.006000.008000.0010000.0012000.001 11 21 31 41 51 61 71 81 91 101 111 121Fourier a ppx actual• Dow Jones Industrial index, 6/18/2001-12/21/2001• just 3 DFT coefficients give very good approximation11010010001000010000 0100000010000 0001 1 1 21 31 41 51 61 71 81 91 101 111 121Series1freqLog(ampl)315-826 Copyright: C. Faloutsos (2005) 13CMU SCSDFT: definition• Discrete Fourier Transform (n-point):)/2exp(*/1)1()/2exp(*/11010ntfjXnxjntfjxnXntftnttfππ+=−=−=∑∑−=−=inverse DFT15-826 Copyright: C. Faloutsos (2005) 14CMU SCSHow does it work?Decomposes signal to a sum of sine (and cosine) waves.Q:How to assess ‘similarity’ of x with a wave?01n-1timevaluex ={x0, x1, ... xn-1}Skip15-826 Copyright: C. Faloutsos (2005) 15CMU SCSHow does it work?A: consider the waves with frequency 0, 1, ...; use the inner-product (~cosine similarity)01n-1timevaluefreq. f=001n-1timevaluefreq. f=1 (sin(t * 2 π/n) )Skip15-826 Copyright: C. Faloutsos (2005) 16CMU SCSHow does it work?A: consider the waves with frequency 0, 1, ...; use the inner-product (~cosine similarity)01n-1timevaluefreq. f=2Skip15-826 Copyright: C. Faloutsos (2005) 17CMU SCSHow does it work?‘basis’ functions01n-101n-101n-1sine, freq =1sine, freq = 201n-101n-1cosine, f=1cosine, f=2Skip15-826 Copyright: C. Faloutsos (2005) 18CMU SCSHow does it work?• Basis functions are actually n-dim vectors, orthogonal to each other• ‘similarity’ of x with each of them: inner product• DFT: ~ all the similarities of x with the basis functionsSkip415-826 Copyright: C. Faloutsos (2005) 19CMU SCSHow does it work?Since ejf= cos(f) + j sin(f)(j=sqrt(-1)),we finally have:Skip15-826 Copyright: C. Faloutsos (2005) 20CMU SCSDFT: definition• Discrete Fourier Transform (n-point):)/2exp(*/1)1()/2exp(*/11010ntfjXnxjntfjxnXntftnttfππ+=−=−=∑∑−=−=inverse DFT15-826 Copyright: C. Faloutsos (2005) 21CMU SCSDFT: definition• Good news: Available in all symbolic math packages, eg., in ‘mathematica’x = [1,2,1,2];X = Fourier[x];Plot[ Abs[X] ];15-826 Copyright: C. Faloutsos (2005) 22CMU SCSDFT: definition(variations:• 1/n instead of 1/sqrt(n)• exp(-...) instead of exp(+...))15-826 Copyright: C. Faloutsos (2005) 23CMU SCSDFT: definitionObservations:• Xf : are complex numbers except– X0, who is real• Im (Xf): ~ amplitude of sine wave of frequency f• Re (Xf): ~ amplitude of cosine wave of frequency f• x: is the sum of the above sine/cosine waves15-826 Copyright: C. Faloutsos (2005) 24CMU SCSDFT: definitionObservation - SYMMETRY property:Xf = (Xn-f )*( “*”: complex conjugate: (a + b j)* = a - b j )515-826 Copyright: C. Faloutsos (2005) 25CMU SCSDFT: definitionDefinitions• Af= |Xf | : amplitude of frequency f• |Xf|2 = Re(Xf)2+ Im(Xf)2= energy of frequency f • phase φfat frequency fXfReImAfφf15-826 Copyright: C. Faloutsos (2005) 26CMU SCSDFT: definitionAmplitude spectrum: | Xf| vs f (f=0, 1, ... n-1)01 n-1SYMMETRIC (Thus, we plot the first half only)15-826 Copyright: C. Faloutsos (2005) 27CMU SCSDFT: definitionPhase spectrum | φf| vs f (f=0, 1, ... n-1):Anti-symmetric(Rarely used)15-826 Copyright: C. Faloutsos (2005) 28CMU SCSDFT: Amplitude spectrumactual mean mean+freq1211223344556677889100111yearcountFreq.Ampl.freq=12freq=0)(Im)(Re222fffXXA +=Amplitude:15-826 Copyright: C. Faloutsos (2005) 29CMU SCSDFT: examplesflat0.0000.0100.0200.0300.0400.0500.0600.0700 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1500.20.40.60.811.20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15timefreqAmplitude15-826 Copyright: C. Faloutsos (2005) 30CMU SCSDFT: examplesLow frequency sinusoid-0.150-0.100-0.0500.0000.0500.1000.1500 1 2 3 4 5 6 7 8 9 1 0 11 12 13 14 1500.20.40.60.811.20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15timefreq615-826 Copyright: C. Faloutsos (2005) 31CMU SCSDFT: examples• Sinusoid - symmetry property: Xf= X*n-f-0.150-0.100-0.0500.0000.0500.1000.1500 1 2 3 4 5 6 7 8 9 1 0 11 12 13 14 1500.20.40.60.811.20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15timefreq15-826 Copyright: C. Faloutsos (2005) 32CMU SCSDFT: examples• Higher freq. sinusoid-0.080-0.060-0.040-0.0200.0000.0200.0400.0600.0800 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1500.10.20.30.40.50.60 1 2 3 4 5 6 7 8 9 10 11 12 13 1 4 15timefreq15-826 Copyright: C. Faloutsos (2005) 33CMU SCSDFT: examplesexamples0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 150 1 2 3 4 5 6 7 8 9 1 0 11 12 13 14 150 1 2 3 4 5 6 7 8 9 1 0 11 12 13 14 150 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15=++15-826 Copyright: C. Faloutsos (2005) 34CMU SCSDFT: examplesexamples0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 150 1 2