Research Article
An Algorithm to Analyze of Two-dimensional Function by using Wavelet Coefficients and Relationship between Coefficients
Department of Statistics and Mathematics, Faculty of Sciences, Persian Gulf University, Bushehr, 75169, Iran
Wavelets are regarded by many as primarily a new subject in pure and applied math-ematics. Indeed, many papers published on wavelets contain esoteric-looking theorems with complicated proofs. Wavelet analysis was led by Daubechies (1988). Many colleagues contributed in different ways: Meyer (1990), Walter (1993), Vidakovic (1999), Cohen et al. (1993), Doosti et al. 2008, Afshari (2008), Antoniadis et al. (1994) and Clyed et al. (1998). Perhaps one of the most common applications of wavelets is in signal processing. A signal is a sequence of numerical measurements, typically obtained electronically.
To analyze and synthesize a signal- which can be any array of data- in terms of simple wavelets, we employ shifts and dilation of mathematical function, but do not involve either calculus or linear algebra.
The first step in applying wavelets to any signal consists in representing the signal under consideration by a mathematical function f. For example, a sound, the values s = f(t) measure the sound at each time t at a fixed location.
The first step in the analysis of a one-dimensional signal with wavelets consists in approximating its function by means of sample alone. One of the simplest methods of approximation uses a horizontal stair step extended through each sample point. The resulting steps form a new function denotes by and called a step function, which approximates the sampled function s = f(t). The analysis of the approximating function f in terms of wavelets requires a precise labeling of each step. By means of shifts and dilations of the basic unit step function, denoted by φ(0.1).
If a sample point (ti,sj) includes a value sj = f(tj) at height sj and abscissa (time or location) tj, then the sample point corresponds to the step function- which approximates f at height sj on the interval [tj,t(j+1)] , where
denotes the indicator function of set [tj,t(j+1)].
Adding all step functions approximating corresponding to all the points in the sample yields the simple step function below:
![]() | (1) |
To analyze a signal or function in term of wavelets, the fast Haar wavelet transform begins with initialization of an array with 2n entries, and then proceeds with n iterations of the basic transform explained in Eq. 1.
For each index jε{1,2,....,n}, before iteration number j, the array will consist of 2n(j1) coefficients of 2n(j1) step function φk,n(j1) defined below. After iteration number j, the array will consist of half as many 2nj coefficient of 2nj step function φk,nj and 2nj coefficient ψk,nj, such as:
![]() | (2) |
![]() | (3) |
MAIN RESULTS
Two dimensional wavelets algorithm: For any function fεL2(R) we can write a formal expansion (Daubechies, 1992):
![]() | (4) |
Here φ(x) and ψ(x) are the scale function and the orthogonal wavelet, respectively as the following:
![]() | (5) |
Constitute an (inhomogeneous) orthonormal basis of L2(R). It is clear that for Haar wavelet:
![]() | (6) |
So, we can write:
![]() | (7) |
Not that φεV0 therefore φεV1 , because V0⊂V1.
Since {φl,k,(x), kεZ is an orthonorml basis for V1, there exists a sequence bk such that:
![]() | (8) |
Know we consider a two-dimensional function f(x,y)εL2(R2). For approximating this function we using two dimensional of wavelets and obtaining an algorithm for estimation of function f with computation of wavelet coefficients. For two dimensional wavelets, encodings can consist of matrices, indexed by rows and columns. To expand this argument, we need some definition as the following:
• | Definition 1: Let f(x,y)εL2(R2) denote the two dimensional signal. We said ψj1,j2,k1,k2 = ψj1,k1(x).ψj2,k2 (x) is orthogonal wavelet basis |
• | Definition 2: For each pair functions f and g, the tensor product of f and g is the function denoted by f⊗ g as follows: |
![]() | (9) |
• | Definition 3: Suppose that function space, Vj,εz to be {Vj = f,gεL2(R2):f,g are piecewise constant on [k2j,(k+1)2j],kεz} = Vj⊗ Vj |
If this sequence of subspaces possesses has the following properties:
• | ...⊂V2 ⊂⊂V1 ⊂V0 ⊂V1 ⊂V... |
• | ![]() |
• | f(x,y)εVj ⇔f(2x,2y)εVj+1 |
• | f(x,y)εV0⇒f(xk1,yk2)ε V0∀k1,k2εZ |
• | There exists a function φ(x,y)=φ(x).φ(y)εV0 such that the set {φj,k1,k2(x,y)=2jφ(2jxk1,2jyk2),j,k1,k2εz} constitutes an orthonormal basis for V0, then we said (Vj)jεZ to be form a multiresolution analysis (MRA) of L2(R2). |
Remark 1: Suppose that function space, wj,jεz to be then we can write as the following:
• | ![]() |
• | Vj+1 = Vj+1 ⊗ Vj+1 = (Vj⊕ Wj) ⊗ (Vj ⊕ Wj) =(Vj ⊗ Vj) ⊕ (Vj ⊗ Wj)⊕ (Wj ⊗ Vj)⊕ (Wj ⊗ Wj) = (Vj ⊕ Wj) |
Theorem 1: In Definition 1, The wavelet space {Wj, jεZ} and scale space {(Vj, jεZ} are mutually orthogonal.
Proof: First we prove that the scaling function and mother wavelet are orthogonal.
![]() |
![]() |
The last step follows since the summand for k is the opposite of the summand for k12l, so each term is negated.
It can be seen similarly that each integer translation of the mother wavelet ψ is also orthogonal to φ as the following:
![]() |
The last step follows, since the summand for k is the opposite of the summand k12l, so each term is negated, because of the square sumability of the sequence bk.
Straightforward extension of this argument will show that ψj,k⊥φj,k for all k,lεZ and complete the proof.
Remark 2: Each basic square-step function has value l in a selected square and 0 everywhere as the following:
![]() | (10) |
Similarly we can write:
![]() | (11) |
![]() | (12) |
Lemmal:
![]() |
Proof: It is easy to see that ,
![]() | (13) |
By substituting φ(0,1) and ψ(0,1) instead of f and g in Eq. 9 and changing the place of them, we can write the tensor product of as follows:
![]() ![]() | (14) |
![]() ![]() | (15) |
![]() ![]() | (16) |
Remark 3: The subscript h and v and d indicates the correspondence of such wavelets with horizontal and vertical, and diagonal changes in the data, since the detail spaces tend to emphasize coefficient-cliques describing horizontal and vertical and diagonal futures the image. The spaces
are spanned by translation of:
![]() | (17) |
![]() | (18) |
For nonnegative integers j which is denoting the frequency and k,l which are denoting the location.
Algorithm: We consider a function f with sample values approximated by a square-function
and denote by a matrix:
![]() |
We can write as follows:
![]() | (19) |
Algorithm begins with one dimensional wavelet transform as described in algorithm, for each row as follows:
![]() |
We can repeat this algorithm and estimate function f.
EXAMPLE
Example 1: let for approximating f we chose sample values:
![]() |
The square-step approximation is:
![]() | (20) |
Consider again the above data. By the algorithm, we can write:
![]() |
The one-dimensional Fast wavelet transform extends to two- dimensional fast wavelet transform with tensor products, through alternating applications of the one-dimensional transform to each row and then to each new column.
So by the tensor product wavelet,
![]() | (21) |
Example 2: supposed that a function f sampled at 4x4 matrix values
![]() |
On a square grid, and we consider approximating f, by square-step function as following:
![]() |
The intermediate result just obtained corresponds to one basic two dimensional wavelet transform on each of the four adjacent 2x2 square matrixes.
• | All of the sums from the upper left hand corners of the four 2x2 blocks go into the upper left hand corner of the larger grade, corresponding to wavelets of the form φm,n ⊗ φk,l. |
• | All of the difference from the upper right-hand corners of the four 2x2 blocks go into the upper right-hand corner of the larger grade, corresponding to wavelets of the form φm,n ⊗ ψk,l. |
• | All of the difference from the lower right-hand corners of the four 2x2 blocks go into the lower right-hand corner of the larger grade, corresponding to wavelets of the form φm,n ⊗ φk,l. |
• | All of the difference from the lower left-hand corners of the four 2x2 blocks go into the lower left-hand corner of the larger grade, corresponding to wavelets of the form φm,n ⊗ ψk,l. |
Proposition: We can complete the two dimensional transform by the following method:
![]() |
Finally, perform a two dimensional wavelet transform only the four entries iv the upper left-hand corner as follows:
![]() |
Thus the matrix:
![]() |
The support of Research Committee of Persian Gulf University is greatly acknowledged.