Tag Archives: Fast Fourier Transform

ATI Instructor Releases A New Book On Wavelets + 25% discount!

ATI offers Wavelets: A Conceptual Practical Approach course on Jun 12-14, 2012 in Columbia, MD.  We thought our reader might be interested in the fact that our instructor Amir Nijami released a new book called Wavelets: A Concise Guide.  You can follow this link to purchase the book and receive 25% discount http://www.aticourses.com/Book_JHUPress.pdf

Introduced nearly three decades ago as a variable resolution alternative to the Fourier transform, awavelet is a short oscillatory waveform for analysis of transients. The discrete wavelet transformhas remarkable multi-resolution and energy-compaction properties. Amir-Homayoon Najmi’sintroduction to wavelet theory explains this mathematical concept clearly and succinctly.Wavelets are used in processing digital signals and imagery from myriad sources. They form thebackbone of the JPEG2000 compression standard, and the Federal Bureau of Investigation usesbiorthogonal wavelets to compress and store its vast database of fingerprints. Najmi provides themathematics that demonstrate how wavelets work, describes how to construct them, and discussestheir importance as a tool to investigate and process signals and imagery. He reviews key conceptssuch as frames, localizing transforms, orthogonal and biorthogonal bases, and multi-resolution.His examples include the Haar, the Shannon, and the Daubechies families of orthogonal andbiorthogonal wavelets.Our capacity and need for collecting and transmitting digital data is increasing at an astonishingrate. So too is the importance of wavelets to anyone working with and analyzing digital data.Najmi’s primer will be an indispensable resource for those in computer science, the physicalsciences, applied mathematics, and engineering who wish to obtain an in-depth understanding andworking knowledge of this fascinating and evolving field.

To receive a 25% discount, please send an email to ATI@ATIcourses.com requesting the discount form.

Sign Up For ATI Courses eNewsletter

ATI’s Short Course on Wavelets: A Conceptual Practical Approach

Video Clip: Click to Watch

Wavelets can be used to identify the time, the frequency, and the shape of a transient signal 

Fast Fourier Transforms (FFT) are in wide use and work very well if your signal stays at a constant frequency (“stationary”). But if the signal could vary, have pulses, “blips” or any other kind of interesting behavior then you need Wavelets. Wavelets are remarkable tools that can stretch and move like an amoeba to find the hidden “events” and then simultaneously give you their location, frequency, and shape. Wavelet Transforms allow this and many other capabilities not possible with conventional methods like the FFT

In this class you will learn how Wavelets can be used to identify the time, the frequency, and the shape of a transient signal (radar pulse, heartbeat, stock market tic, image edge detection in baggage, etc,) and do all 3 simultaneously! For example, in the figure above (a 3-D wavelet transform of a chirp signal), the horizontal axis indicates time, the vertical axis indicates frequency, and the colors indicate magnitude (at that particular time and frequency)

This course is vastly different from traditional math-oriented Wavelet courses or books in that we use examples, figures, and computer demonstrations to show how to understand and work with Wavelets. This is a comprehensive, in-depth, up-to-date treatment of the subject, but from an intuitive, conceptual point of view. 

We do look at a few key equations from the traditional literature but only AFTER the concepts are demonstrated and understood. If desired, further study from scholarly texts and papers is then made much easier and more palatable when you already understand the fundamental equations and how they relate to the real world. Each student will receive extensive course slides, a CD with MATLAB demonstrations, and a copy of the instructor’s new book, Conceptual Wavelets. 

What you will learn: 

• How to use Wavelets as a “microscope” to analyze data that changes over time or has hidden “events” that would not show up on an FFT. 

• How to understand and efficiently use the three types of Wavelet Transforms to better analyze and process your data using state-of-the-art methods and applications. 

• How to compress and de-noise data using advanced Wavelet techniques. How to avoid potential pitfalls by understanding the concepts. A “safe” method if in doubt. 

• How to increase productivity and reduce cost by choosing (or building) a Wavelet that best matches your particular application. 

Course Outline, Samplers, and Notes 

1. What is a Wavelet? Examples and Uses. “Waves” that can start, stop, move and stretch. Real-world applications in many fields: Signal and Image Processing, Internet Traffic, Airport Security, Medicine, JPEG, Finance, Pulse and Target Recognition, Radar, Sonar, etc. 

2. Comparison with traditional methods. The concept of the FFT, the STFT, and Wavelets as all being various types of comparisons with the data. Strengths, weaknesses, optimal choices. 

3. The Continuous Wavelet Transform (CWT). Stretching and shifting the Wavelet for optimal correlation. Predefined vs. Constructed Wavelets. 

4. The Discrete Wavelet Transform (DWT). Shrinking the signal by factors of 2 through downsampling. Understanding the DWT in terms of correlations with the data. Relating the DWT to the CWT. Demonstrations and uses. 

5. The Redundant Discrete Wavelet Transform (RDWT). Stretching the Wavelet by factors of 2 without downsampling. Tradeoffs between the alias-free processing and the extra storage and computational burdens. A hybrid process using both the DWT and the RDWT. Demonstrations and uses. 

6. “Perfect Reconstruction Filters”. How to cancel the effects of aliasing. How to recognize and avoid any traps. A breakthrough method to see the filters as basic Wavelets. The “magic” of alias cancellation demonstrated in both the time and frequency domains. 

7. Highly useful properties of popular Wavelets. How to choose the best Wavelet for your application. When to create your own and when to stay with proven favorites. 

8. Compression and De-Noising using Wavelets. How to remove unwanted or non-critical data without throwing away the alias cancellation capability. A new, powerful method to extract signals from large amounts of noise. Demonstrations. 

9. Additional Methods and Applications. Image Processing. Detecting Discontinuities, Self-Similarities and Transitory Events. Speech Processing. Human Vision. Audio and Video. BPSK/QPSK Signals. Wavelet Packet Analysis. Matched Filtering. How to read and use the various Wavelet Displays. Demonstrations. 

10. Further Resources. The very best of Wavelet references. 

Determine for yourself the value of this course before you sign up. 

See Slide Samples of our Wavelets: A Conceptual Practical Approach 

After attending the course you will receive a full set of detailed notes from the class for future reference, as well as a certificate of completion. Please visit our website for more valuable information. 

Comments from participants: 

“Your Wavelets course was very helpful in our Radar studies. We often use wavelets now instead of the Fourier Transform for precision de-noising.” 

–Long To, NAWC WD, Point Wugu, CA 

“I was looking forward to this course and it was very rewarding–Your clear explanations starting with the big picture immediately contextualized the material allowing us to drill a little deeper with a fuller understanding” 

–Steve Van Albert, Walter Reed Army Institute of Research 

“Good overview of key wavelet concepts and literature. The course provided a good physical understanding of wavelet transforms and applications.” 

–Stanley Radzevicius, ENSCO, Inc. 

The Instructor 

Dr. Lee Fugal is the Founder and President of an independent consulting firm. He has over 30 years of industry experience in Digital Signal Processing (including Wavelets) and Satellite Communications. 

He has been a full-time consultant on numerous assignments since 1991. Recent projects include Excision of Chirp Jammer Signals using Wavelets, design of Space-Based Geolocation Systems (GPS & Non-GPS), and Advanced Pulse Detection using Wavelet Technology. 

He has taught upper-division University courses in DSP and in Satellites as well as Wavelet short courses and seminars for Practicing Engineers and Management. He holds a Masters in Applied Physics (DSP) from the University of Utah, is a Senior Member of IEEE, and a recipient of the IEEE Third Millennium Medal. 

About ATI 

Since 1984, the Applied Technology Institute (ATI) has provided leading-edge public courses and onsite technical training to DoD and NASA personnel, as well as contractors. 

Our mission here at ATI is to provide expert training and the highest quality professional development in space, communications, defense, sonar, radar, and signal processing. We are not a one-size-fits-all educational facility. 

Our short classes include both introductory and advanced courses. ATI’s instructors are world-class experts who are the best in the business. They are carefully selected for their ability to clearly explain advanced technology. 

Times, Dates, and Locations 

Wavelets: A Conceptual Practical Approach 

Feb 22-24, 2011 San Diego, CA 

Jun 7-9, 2011 Beltsville, MD 


The ATI Courses Team 

P.S Call today for registration at 410-956-8805 or 888-501-2100 or access our website at www.ATIcourses.com. For general questions please email us at ATI@ATIcourses.com. 

Wavelets — “Beyond Comparison”

by D. Lee Fugal

Radar, Sonar, Geology and many other varied fields use Wavelets . They are usually presented in mathematical formulae, but can actually be understood in terms of simple comparisons with your data.

As a background, we first look at the Discrete Fourier Transform (DFT) or it’s faster and more famous cousin, the Fast Fourier Transform (FFT). These transforms can be thought of as a series of comparisons with your data, which we will call for now a “signal” for consistency. Signals that are simple waves of constant frequencies can be processed with ordinary DFT/FFT methods.

Real-world signals, however, often have frequencies that can change over time or have pulses, anomalies, or other “events” at certain specific times. This type of signal can tell us where something is located on the planet, the health of a human heart, the position and velocity of a “blip” on a Radar screen, stock market behavior, or the location of underground oil deposits. For these signals, we will often do better with wavelets. We now demonstrate both the Fourier and Wavelet Transforms of a simple pulse signal.

The Discrete Fourier Transform/Fast Fourier Transform (DFT/FFT)
We start with a point-by-point comparison of the pulse signal (D) with a high frequency wave or “sinusoid” of constant frequency (A) as shown in Figure 1 below. We obtain a single “goodness” value from this comparison (a correlation value) which indicates how much of that particular sinusoid is found in our own pulse signal.
Figure 1
Figure 2 We can observe that the pulse has 5 cycles in 1/4 of a second. This means that it has a frequency of 20 cycles in one second or “20 Hz.” The comparison sinusoid, A, has twice the frequency or 40 Hz. Even in the area where the signal is non-zero (the pulse) the comparison is not very good.

By lowering the frequency of A from 40 to 20 Hz (waveform B) we are effectively “stretching” the sinusoid (A) by 2 so it has only 20 cycles in 1 second. We compare point-by-point again over the 1-second interval with the pulse (D). This next correlation gives us another value indicating how much of this lower frequency sinusoid (now the same frequency as our pulse) is contained in our signal. This time the correlation of the pulse with the comparison sinusoid is very good. The peaks and valleys of B and the pulse portion of D align (or can be easily shifted to align) and thus we have a large correlation value.

Figure 1 shows us one more comparison of our original sinusoid (A) stretched by 4 and trimmed so it has only 10 cycles in the 1 second interval (C). This comparison with D is poor again. We could continue stretching and trimming until the sinusoid becomes a straight line having zero frequency or “DC” (named for the zero frequency of Direct Current) but all these comparisons will be increasingly poor.

Figure 3 An actual DFT (or functionally equivalent FFT) compares many “stretched” sinusoids (“analysis signals”) to the pulse rather than just the three shown here. The best correlation is found when the sinusoid frequency best matches that of the pulse. Figure 2 shows the first part of an actual FFT of our pulse signal D. The locations of our sample comparison sinusoids A, B, and C are indicated. Notice that the FFT tells us correctly that the pulse has primarily a frequency of 20 Hz, but does NOT tell us where the pulse is located in time!

The Continuous Wavelet Transform (CWT)
Wavelets are exciting because they too are comparisons, but instead of cor-relating with various stretched, infinite length unchanging sinusoids, they use smaller or shorter waveforms (“wave–lets”) that can start and stop where we wish.

By stretching and shifting the wavelet numerous times we get numerous correlations. If our signal has some interesting events embedded, we will get the best correlation when the stretched wavelet is similar in frequency to the event and is shifted to line up with it in time. Knowing the amounts of stretching and shifting we can determine both location and frequency.

Figure 3 demonstrates the process. Instead of sinusoids for our comparisons, we will use wavelets. Waveform A shows a Daubechies 20 (Db20) wavelet about 1/8 second long that starts at the beginning (t = 0) and effectively ends well before 1/4 second. The zero values are extended to the full 1 second. The point-by-point comparison with our pulse signal D will be very poor and we will obtain a very small correlation value.

Figure 4 In the previous FFT/DFT discussion we proceeded directly to stretching. In the Wavelet Transforms we shift the wavelet slightly to the right and per-form another comparison with this new waveform to get another correlation value. We continue to shift until the Db20 wavelet is in the position shown in B. We get a little better comparison than A, but still very poor because B and D are different frequencies.

After we have shifted the wavelet all the way to the end of the 1 second time interval we start over with a slightly stretched wavelet at the beginning and repeatedly shift to the right to obtain another full set of these correlation values. C shows the Db20 wavelet stretched to where the frequency is roughly the same as the pulse (D) and shifted to the right until the peaks and valleys line up fairly well. At this particular shifting and stretching we should obtain a very good comparison and large correlation value. Further shifting to the right, however, even at this same stretching will yield increasingly poor correlations.

In the CWT we thus have one correlation value for every shift of every stretched wavelet. To show the data for all these stretches and shifts, we use a 3-D display with the stretching (roughly inverse of frequency) as the vertical axis, the shifting in time as the horizontal axis, and brightness (or color) to indicate the strength of the correlation. Figure 4 shows a Continuous Wavelet Transform (CWT) display for this particular pulse signal (D). Note the strong correlation of the three larger peaks and valleys of the pulse with the Db20 wavelet, the strongest being where all the peaks and valleys best align.

The display shows that the best correlation occurs at the brightest point or at about 3/8 second. This agrees with what we already know about the pulse, D. The display also tells us how much the wavelet had to be stretched (or “scaled”) and this indicates the approximate frequency of the pulse. Thus we know not only the frequency of the pulse, but also the time of it’s occurrence!
Figure 5
We run into this simultaneous time/frequency concept in everyday life. For example, a bar of sheet music may tell the pianist to play a C-chord of three different frequencies at exactly the same time on the first beat of the measure.

For the simple example above we could have just looked at the pulse (D) to see its location and frequency. The next example is more representative of wavelets in the real world.

Figure 5 shows a signal with a very small, very short discontinuity at time 180. The Amplitude vs. Time plot of the signal is shown at the upper left but does not show the tiny “event”. The Magnitude vs. Frequency FFT plot tells what frequencies are present but does not indicate the time associated with those frequencies.

With the wavelet display, however, we can clearly see a vertical line at 180 at low scales when the wavelet has very little stretching, indicating a very high frequency. The CWT display also “finds” the large oscillating wave at the higher scales where the wavelet has been stretched and compares well with the lower frequencies. For this short discontinuity we used a short wavelet (a Db4) for best comparison.

This is an example of why wavelets have been referred to as a “mathematical microscope” for their ability to find interesting events of various lengths and frequencies hidden in data.

Besides acting as a “microscope” to find hidden events in our data, wavelets can also separate the data into various frequency components, as does the FFT. The FFT/DFT is used extensively to remove unwanted noise that is prevalent throughout the entire signal such as a 60 Hz hum. Unlike the FFT, however, the wavelet transform allows us to remove frequency components at specific times in the data. This allows us a powerful capability to throw out the “bad” and keep the “good” part of the data in that frequency range.

These types of transforms are called “Discrete Wavelet Transforms” (DWT). They also have easily computed inverse transforms (IDWT) that allow us to reconstruct the signal after we have identified and removed the noise or superfluous data for denoising or compression.

Undecimated or “Redundant” Discrete Wavelet Transforms (UDWT/RDWT)
In one type of DWT, the Redundant Discrete Wavelet Transform, or RDWT, we first compare (correlate) the Wavelet “filter” with itself. This produces a “Highpass Halfband Filter” or “superfilter.” When we compare or correlate our signal with this superfilter we extract the highest half of the frequencies. For a very simple denoising, we could just discard these high frequencies (for whatever time period we choose) and then reconstruct a denoised signal.

Multi-level RDWT’s allow us to stretch the wavelet, similar to what we did in the CWT, except that it is done by factors of 2 (twice as long, 4 times as long, etc.). This allows us stretched superfilters that can be halfband, quarter-band, eighth-band and so forth.
Figure 6
Conventional (Decimated) Discrete Conventional Transforms (DWT)
We stretched the wavelet in the CWT and the RDWT. In the conventional DWT, we shrink the signal instead and compare it to the unchanged wavelet. We do this by “downsampling by 2.” Every other point in the signal is discarded. We have to deal with “aliasing” (not having enough samples left to represent the high frequency components and thus producing a false signal). We must also be concerned with “shift invariance” (do we throw away the odd or the even values? — it matters!).

If we are careful, we can deal with these concerns. One amazing capability of the filters in the conventional DWT is alias cancellation where the basic wavelet and 3 similar “filters” combine to allow us to reconstruct the original signal perfectly. The stringent requirements on the wavelets to be able to do this is part of why they often look so strange (see Figure 8).

Figure 7 As with the RDWT, we can denoise our signal by discarding portions of the frequency spectrum — as long as we are careful not to throw away vital parts of the alias cancellation capability. Correct and careful downsampling also aids with compression of the signal. Modern JPEG compression uses wavelets. Figure 6 shows JPEG image compression. The image on the right was compressed by a ratio of 157:1 using a Biorthogonal 9/7 set of wavelets.

There are many types of Wavelets. Some come from mathematical expressions. Others are built from basic Wavelet Filters having as little as 2 points. The Db4, Db20, and Biorthogonal wavelets shown earlier are examples of this 2nd type. Figure 7 shows a 768 point approximation of a continuous Db4 wavelet with the 4 filter points (plus 2 zeros) superimposed.

Some wavelets have symmetry (valuable in human vision perception) such as the Biorthogonal Wavelet pairs. Shannon or “Sinc” Wavelets can find events with specific frequencies (these are similar to the Sinc Function filters found in traditional DSP). Haar Wavelets (the shortest) are good for edge detection and reconstructing binary pulses. Coiflets Wavelets are good for data with self-similarities (fractals) such as financial trends. Some of the wavelet families are shown in Figure 8.
Figure 8
You can even create your own wavelets, if needed. However there is “an embarrassment of riches” in the many wavelets that are already out there and ready to go. We have already seen that with their ability to stretch and shift that wavelets are extremely adaptable. You can usually get by very nicely with choosing a less-than-perfect wavelet. The only “wrong” choice is to avoid wavelets due to an abundant selection.

Bio + ad There is much more to discover than can be presented in this short overview. The time spent, however, in learning, understanding and correctly using wavelets for these “non-stationary” signals with anomalies at specific times or changing frequencies (the fascinating, real-world kind!) will be re-paid handsomely.

Article © 2009 Space & Signals Technologies LLC,
All Rights Reserved.


About the author
D. Lee Fugal is Founder and President of Space & Signals Technologies, LLC., a company specializing in the presentation of difficult concepts in an intuitive, understandable manner. He has over 30 years of industry experience in Digital Signal Processing (including Wavelets) and Satellite Communications. He has been a full-time consultant on numerous assignments since 1991. Additionally, Mr. Fugal offers short courses for Jim Jenkins at ATI (http://www.aticourses.com).