Building Your Own Wavelets at Home
Classifying image data
An image is represented as a two-dimentional array of coefficients, each coefficient representing the brightness level in that point. When looking from a higher perspective, we can't differentiate between coefficients as more important ones, and lesser important ones. But thinking more intuitively, we can. Most natural images have smooth colour variations, with the fine details being represented as sharp edges in between the smooth variations. Technically, the smooth variations in colour can be termed as low frequency variations and the sharp variations as high frequency variations.
The low frequency components (smooth variations) constitute the base of an image, and the high frequency components (the edges which give the detail) add upon them to refine the image, thereby giving a detailed image. Hence, the smooth variations are demanding more importance than the details.
Separating the smooth variations and details of the image can be done in many ways. One such way is the decomposition of the image using a Discrete Wavelet Transform (DWT).
The DWT of an image
The procedure goes like this.
A low pass filter and a high pass filter are chosen, such that they exactly halve the frequency range in the image source, this filter pair is called the Analysis Filter pair.
- the low pass filter is applied for each row of data The low frequency components of the row is got.
- the high pass filter is applied for the same row of data
- the filtering is done for each column of the currently filtered data
- The resulting two-dimensional array of coefficients contains four bands of data
- LL (low-low)
- HL (high-low)
- LH (low-high)
- HH (high-high)
The Inverse DWT of an image
Just as a forward transform to used to separate the image data into various classes of importance, a reverse transform is used to reassemble the various classes of data into a reconstructed image.
A pair of high pass and low pass filters are used here also. This filter pair is called the Synthesis Filter pair.
The filtering procedure is just the opposite - we start from the topmost level, apply the filters column-wise first and then row-wise, and proceed to the next level, till we reach the first level.
The Haar Wavelet and The Biorthogonal Wavelet Transforms of an Image
byProf. Teena Varma, Prof. Vidya Chitre, Prof.Dipti Patil
INTRODUCTION
Wavelets are mathematical functions that cut up data into different frequency components, and then study each component with a resolution matched to its scale.
Wavelet algorithms process data at different scales or resolutions. If we look at a signal with a large "window," we would notice gross features. Similarly, if we look at a signal with a small "window," we would notice small discontinuities. The result in wavelet analysis is to "see the forest and the trees."
The wavelet analysis procedure is to adopt a wavelet prototype function, called an "analyzing wavelet" or "mother wavelet." Temporal analysis is performed with a contracted, high-frequency version of the prototype wavelet, while frequency analysis is performed with a dilated, low-frequency version of the prototype wavelet.
I. DISCRETE WAVELET TRANSFORM
A) HAAR WAVELET TRANSFORM
Daubechies constructed the first wavelet family of scale functions that are orthogonal and have finite vanishing moments.
Haar wavelets are related to a mathematical operation called Haar transform, which serves as a prototype for all other wavelet transforms.
The Haar transform decomposes a discrete signal into two sub-signals of half its length. One sub-signal is a running average or trend, the other sub-signal is a running difference or fluctuation.
The Haar wavelet transform has the advantages of being conceptually simple, fast and memory efficient, since it can be calculated in place without a temporary array.
The Daubechies wavelet transforms are defined in the same way as the Haar wavelet transform by computing the running averages and differences via scalar products with scaling signals and wavelets
B) BIORTHOGONAL WAVELET TRANSFORM
It is well known that bases that span a space do not have to be orthogonal. In order to gain greater flexibility in the construction of wavelet bases, the orthogonality condition is relaxed allowing semi- orthogonal, biorthogonal or non-orthogonal wavelet bases.
In the biorthogonal case, rather than having one scaling and wavelet function, there are two scaling functions and accordingly two different wavelet functions.
The Lifting Scheme:
A New Philosophy in Biorthogonal Wavelet Constructions
byWim Sweldens
Abstract
The lifting scheme is a new construction of bi-orthogonal wavelets which does not use the Fourier Transform.Introduction
Wavelet are building blocks that can quickly de-correlate data.
This means that each element of a general class can be written in a stable way as a linear combination of the wavelets
The way to get this de-correlation power is to construct wavelets which already in some way resemble the data we want to represent.
The purpose of this paper is to introduce the lifting scheme, a new tool in the construction of bi-orthogonal wavelets. That is, there are two mother wavelets (scaling functions<)
The Fourier transform has been instrumental in wavelet constructions. The underlying reason is that wavelets are traditionally defined as translates and dilates of one function, and translation and dilation become algebraic operations after Fourier transform. The wavelet construction then relies on certain polynomial factorizations. We refer to this kind of wavelets as first generation wavelets.
Since lifting can be used to construct wavelets without using Fourier transform, we refer to such wavelet as second generation wavelets.
It's more natural to introduce lifting by understanding how lifting affects the wavelet transform.
2 The basic idea behind lifting
R'(-1) R(-1)
+----------->(-)------------+
/|\ /|\ |
| | \|/
S(0)-->S() P() U()
| /|\ |
\|/ | \|/
+-------------+------------(+)---------> S(-1)
S'(-1)
Assume there is a data set S(0), a canonical case of lifting consists of three stages:
- split We split the data set S(0) into two smaller subsets S'(-1) and R'(-1). We use negative indices here because the convention is that the smaller the data set, the smaller the index. We refer to R'(-1) as the wavelet subset. We do not impose any restriction on how the data should be split, nor on the relative size of each of the subsets. The only thing we need is some procedure to join S'(-1) and R'(-1) back into the original S(0). The simplest way to split the data is to cut the data set into two disjoint parts.(called the Lazy wavelet)
- predict If we can find a predictor P, we can use S'(-1) and the correlation in S(0) to predict R'(-1). Find a residual difference R(-1) between the R'(-1) and its prediction P( S'(-1) ) :
R(-1) = R'(-1) - P( S'(-1) )
3 A simple example
We can implement the Haar wavelet via lifting.
Suppose we sample a signal f(t) with the sampling rate 1 sample/second. We denote the original samples by
S(0) = { S(0, k) = f(k) }
- split The data is sub-sampled into even and odd indexed samples.
S'(-1, k) = S(0, 2k)
R'(-1, k) = S(0, 2k+1)
- predictor#1 The predict operator is simply x(2k).
P(-1, k) = S(0, 2k)
R(-1, k) = R'(-1,k) - P(-1, k)
= S(0, 2k+1) – S(0, 2k)
P(-1, k) = [ S(0, 2k) + S(0, 2k+1) ] / 2
R(-1, k) = R'(-1,k) - P(-1, k)
= S(0, 2k+1) – [ S(0, 2k) + S(0, 2k+1) ] / 2
= - [ S(0, 2k+1) - S(0, 2k) ] / 2
- with predictor#1
U(-1, k) = R(-1, k) / 2
S(-1, k) = S'(-1, k) + U(-1, k)
= S(0, 2k) + [ S(0, 2k+1) – S(0, 2k) ] / 2
= [ S(0, 2k) + S(0, 2k+1) ] / 2
U(-1, k) = - R(-1, k)
S(-1, k) = S'(-1, k) + U(-1, k)
= S(0, 2k) + [ S(0, 2k+1) – S(0, 2k) ] / 2
= [ S(0, 2k) + S(0, 2k+1) ] / 2
S(-1) is used to capture the low frequency, R(-1) is for capturing the high frequency.
This example shows how how the lifting scheme can speed up the implementation of the wavelet transform (the bi-ortogonal transform , Cohen - Daubechies -Feauveau).
4 In place calculation
Another feature of lifting is that we can replace the original data set with its wavelet transform without having to allocate extra memory, called in place calculation.
5 The basis functions
6 Second generation wavelets
If one wants to account for local irregularities, one cannot use the same filter(P,U) everywhere.
A Brief Introduction to First- and Second-Generation Wavelets
by
Raanan Fattal
The so-called first generation wavelets and scaling functions are dilations and translates of a single function. Fourier methods play a key role in the design of these wavelets. Designing new first generation wavelets requires expertise in Fourier analysis.
The lifting method proposed by Sweldens removes the necessity of expertise in Fourier analysis and allows you to generate an infinite number of discrete biorthogonal wavelets starting from an initial one. In addition to generation of first generation wavelets with lifting, the lifting method also enables you to design second generation wavelets, which cannot be designed using Fourier-based methods. With lifting, you can design wavelets that address the shortcomings of the first generation wavelets.
Multi-Resolution Analysis
MRA consists of
- a hierarchy of linear spaces, called approximation spaces
- the difference spaces, called the detail spaces as they contain the detail needed to refine one approximation level to the next
A wavelet basis for a MRA is constructed by two functions, the scaling function φ(t) and the wavelet function ψ(t).
The space V(j) and W(j) are spanned by dilating the scaling function and wavelet function with 2**j:
In finite spaces,
For every function f in V(j), it can be represented by the scaling functions in V(j):
or alternatively by the scaling functions and wavelets function in V(j+1):
where the first sum expresses f ’s coarser approximation in V(j+1) and the second sum expresses its components in W(j+1), the detail in V(j) missing from V(j+1).
The wavelet transform is the mapping between
Fast Wavelet Transform
Because
and
Therefore, they can both be expressed by means of φ(j,n), i.e.,
The filters h[n] and g[n] are known as the conjugate mirror filters (CMF).
Second-Generation Wavelets
Second-generation wavelets do not correspond to the translates and dilates of the same mother wavelet function and scaling function.
Second Generation Wavelets: Theory and Application
by
Fadil Santosa
1 Introduction
Second generation wavelets are actually easier to understand and use. Moreover, they offer some generalities that make them applicable to new areas such as computer graphics.
What are wavelets and why do they work?
For data which are highly correlated and contain redundancy, the type of digital data can be represented accurately with a few parameters by wavelets.
Consider a scalar function of a single variable f(x), and imagine a basis generated by a mother wavelet function ( represented by y(x) ) which
- Is compactly supported
- Is smooth
- Has zero moments
Lifting Biorthogonal Wavelet Design for Edge Detection
by
S.Devendra, P.M.K.Prasad
II Process of lifting wavelet
Consider a signal s(j) with 2**j samples which we want to transform into a coarser signal s(j-1) and detail signal d(j-1).- Split Lazy wavelet transform:
[ s(j, even), s(j, odd) ] = Split( s(j) )
d(j-1, n) = s(j, 2n+1) - s(j, 2n)
= s(j, odd, n) - P( s(j, even, n) )
s(j-1, n) = s(j, even, n) + U( d(j-1, n) )
III Method for Image Edge Detection Based on Biorthogoal Lifting Wavelet Transform
How many edges we want to get is set by the wavelet scale.
When process a 2-D image, the wavelet analysis is performed separately for the horizontal and the vertical directions.
The 2D image is decomposed into 4 sub-images:
- 1 approximation, LL The approximation is only 1/4 of original image size.
- 3 details
- LH Apply the low-pass filter to rows and high-pass filter to columns. Preserve the horizontal details.
- HL Apply the high-pass filter to rows and low-pass filter to columns. Preserve the vertical details.
- HH Apply the high-pass filter to both rows and columns. Preserve the diagonal details.
IV Simulation and Experiment result
Edge detection in medical images using the Wavelet Transform
by
Petrová Jana · MATLAB/Comsol, Medicína
1. 2D Discrete Wavelet Transform
This image decomposition by 2D DWT can by mathematically described by:
C = X * I * Y
- C the final matrix of wavelet coefficients
- X a matrix of row filters
- I an original image
- Y a matrix of column filters
- LowLow
- LowHight
- HighLow
- HighHigh
Building Your Own Wavelets at Home
by
Wim Sweldens, Peter Schro ̈der
1 Introduction
The purpose of this paper is to show that simple techniques exist which allow the construction of versatile families of scaling functions and wavelets under general circumstances.
We begin with the construction of scaling functions by interpolating subdivision, and average-interpolation.
留言