On Construction, Lifting Schemes And Applications Of Multivariate Wavelets

Major: Computational Mathematics Supervisor: Prof. Zhou Yun-shiThis dissertation has five parts including exordium and conclusion. Our main results covers chapter 1 to chapter 3.In the part of exordium, we have briefly introduced the history of wavelet analysis and its applications including the background of the dissertation.In chapter 1, we have discussed how to construct non-product wavelets based on known monovariate wavelets with directional integral. Theoretical analysis shows that the idea mentioned above is practical. We have also constructed a new non-product wavelet based on Daubechies 5x3 filter with the method proposed in this chapter.In chapter 2, we have discussed the characterizition of compactly supported refinable splines and showed that m-refinalbe spline in rectangular grids must be homogeneous differential of linear combinition of shifts of product B-splines. Under above conditions, the m-refinable spline must be a product B-spline if its shifts form the Riesz bases of closed subspace spaned by themselves.In chapter 3, we have discussed the algorithm of factoring bivariate product and non-product wavelets into lifting steps. After that, we have factored the non-product biorthonormal wavelet constructed in chapter 1 into non-separable lifting steps. At the end of this chapter, we give a new face recognition algorithm based on non-separable liftingand P2D-HMM.Finally, we have briefly summarized the research work in the dissertation and pointed out further problems to resolve.The main results from the dissertation can be listed as follow. 1. Constructing Multivariate Wavelets with Directional IntegralDefinition 1.1. An MRA of L2(Ra) consists of a set of closed subspaces Vj C Vj+i) that satisfies following conditions:? Vj,/(x) G Vj <=> f{2x) e Vj+1;? There exists ip(x) € Vo such that {(p(x - k)}kez> form the Riesz bases ofV0.From the definition of MRA , the following scaling equation holdsBy taking Fourier transformation, we obtain the following equationDefinition 1.2. We say the function f(x) defined on R3 is m-refinable, m > 2, m € Z, if there exist finite hk # 0, A; € Zs, such thatf{x) = J] WN " *) (3)Definition 1.3. Let x, v € W,s ^ 2. We say F(x) is the directional integral of f(x) along direction vector v if= IJf(x))= / f(x-tv)dt > h[ iFimx — i, my — j)m-lwhere h'itj = ^ ￡ hi-s9j-,-s-QDefinition 1.11. Let H be a Hilbert space and {9(x - k)\k € Is) be the members of H. If there exist two constants B > A > 0, such that each f(x) € H can be uniquely decomposited as:f(x) = Y, o<[k}0(x - k) and. (5)We say {9(x - k)\k € Zs} form the Riesz bases of H.Proposition 1.12. Let {x,y) = ip(x)(p(y) and 4>(x,y) = ip(x)ip(y) be compactly supported biorthonormal scaling function, and the z symbols of its filters are m^zi, z2) = im{zi)m{z2),m^{z\,Z2) = rh(z\)fh{z2), and Laurent polynomial m(zi),fh(zi) satisfy m(zi) = m{z~l), fh(zi) = m{z~l),i = 1,2.Define P{zuz2) = rnt(zU2*)mjte\z;1)(^^y{1 + *lz*1)',0< r,t 6 Z,then {P{(-l)uz),u 6 Z2,} and {P,,(z2),i/ € Z2,},* = {zuz2) e C2 have no common zeros in C2 \ {0}.By summarizing above results, We give the procedure of computing dual scaling function:Let Laurent polynomial m(z) and fh(z) be the z symbols of filters of the scaling functions (p(x) and lp(x) of monovariate biorthonormal wavelets.1. Let M{zuz2) = 1±f^m{zl)m{z2), Mx{zuz2) = l±^m{zl)rh(z2). For Laurent polynomial Q(zi,z2) with unknown coefficients, Let P(z\,z2) =2. Let P{zuz2) + P(-zuz2) + P{zi, -z2) + P{-zu -z2) = 1. By repeating the procedure: Solving the linear equations about the coefficients of Laurent polynomial Q{z\, z2), if the linear equations have solutions, then Q{z\,z2) can be obtained, otherwise increase the degree of Laurent polynomial Q{z\,z2) go to step 1.3. Let M(zi,z2) = Mi(z\, z2)Q{z^1,z^1), then M(zx,z2) is dual filter of M{z1,z2).4. Checking whether the scaling function with filter M{z\,z2) satisfies the conditions of L2 and Riesz bases.5. If the scaling function with filter of M(z\,z2) does not satisfy the condition of L2 and Riesz bases, increase the number of directional integral and go to step 1.The following proposition can be used for extension of polyphase matrix to construct wavelet functions.Proposition 1.18. Let V(zi,z2),V(zi,z2) be two 4-dimensional vectors with Laurent polynomial entries, and satisfyIf there exist three Laurent polymomials, who has no common zeros in C2 \ {0}, among the elements of V(zi, z2) or V(zi, z2), then there exist matrices A(zi,Z2) and A(zi,z2) with Lauent polynomial entries, whose determinant are Laurent monomials respectively such that A(zi,Z2)A*(zi,Z2) = \U, and the first row of each matrix of A(zi,z2) and A(zi,z2) is V{z\,Z2) and ,Z2) repectively.2. Characterization of Refinable Splines in Rectangular GridsIn this part, we define following symbols: i denotes \f-i. Let 1 < s G Z, a = (ai,a2,--- ,as) G Z", z = (21,22, *?? ,z$) G Cs, m G Z, define a + m = (al+m,a2 + m,--- ,as + m), a (a) = ￡j=1 a,-, 2Q = O^=i tf. z? = (^, z?, ? ? ? , 2?). For a, 0 € Rs, define a < 0, if for all j = 1,2, ? ? ? , s, a_j < fa, where a;, ^- denotes the j-th coeficient of a,fi respectively, a > /? and a = P can be similarly defined. Let c be a constant, define c < a if for all j = 1,2, ? ? ? , s, c < otj. c> a and c = a can be defined similarly. Let x,y e Cs, define xy = ]T)j=i x:/l/:?> where y;- denotes the complex conjugate of j/j. Xj, yj denote the j-th coeficient of x, y respectively. Forp = (pi, ? ? ? ,ps),q = (qx, ? ? ? , qs) G Rs,p < 9. define [p, g] = {x = (xi, ? ? ? , x,) eW \ Pj 0. We call function ^ a non-zero k spline, if : W —>? C, (/> is a polynomial with degree of k in 7￡t = [at,6t], where at, 6t G Rs, t = l; 2, ? ? ? , L. 0, -§p;{x) is not continuous at some points in Xj = c. If c is an integer, We call Xj = c integer knot plane. We suppose all knot planes are active unless specially declared.Definition 2.2. We say function f(x) is m refinable,! < m G Z, if thereexist a finite sequence ha (called scale sequence),M < a < K, such thatf(x)= J2 haf{mx-a) (6)M(x) = f(x + ^zj-), each refinable function can be transformed into standard form, that is, equation (6) can be written as: - a) (7)0{x) is [0, ^-].Lemma 2.4. SupposeTheorem 2.7. Let (f>(x),x G Es, be a spline with degree of k in rectangular grids, k = (ki,k2,- ?- ,ks). 1 < m € Z, then ^(z) is an m-refinable function which satisfies scaling equation (7) if and only if4>(x) =I j=lwhere / = (l\, l2, ■ ■ ? , ls) € Z4, pi is the coeficient of polynomial of P(z) = YliPiz1, and -PI-2) n^iC^j ~ l)nj ^s ^-closed, Bnj.(t) is nonovariate B spline with degree of rij — 1, n, — 1 > /c^, j = 1,2, ? ? ? , s, Q(D) is a homogeneous differential operator. Furthermore, the shifts of (j>(x) would form the Riesz bases of the space spaned by themselves if and only if the degree of Q(D) is zero and P(z) is a monomial.From Theorem 2.7, we know the following corollary hold: Corollary 2.8. The compactly supported spline $(x) , which satisfies scaling equation (6), with degree of k = (k\, k2, ? ? ? , ka) in rectangular grids if and only if there exists polynomial P(z) such that P(z) Ylj=i{zj ~ 1)"J is m closed andf(x) = Q(Z?)J>￡[￡?,(*, - I, - -2L-),1 1=1where Bnj is B spline with degree of rij — l> kj, a = (an, 0:2, ? ? ? ,a3) € Z*. Corollary 2.9. The shifts of compactly supported refinable spline (x) with degree of k form the Riesz bases of the space spaned by themselves if and only if (x) = ]J'j=1 cBnj (xj - lj - ^), where 1 = (h, l2, ? ? ■ , ls), a -From Corollary 2.9, the following corollary holds.Corollary 2.10. There is not refinable non-product spline 1 and z G C*. If p(z) is m-closed and is not monomial about variable z\, then there exist k G N, and a constant a G C, where |a| = 1, such that p{z\,Z2,- ? ? ,zs--\,d) is mfc-closed and is not monomial about variable z\.Proposition 2.18. If q(z) is an m-closed polynomial which is not a monomial, then there exists a = (?i, ■ ? ? , ota) € C* and |ai| = |a2| = ? ? ? = \as\ = 1 so that q(a) — 0.aProposition 2.19. For t = (ti,t2, ? ? ? ,ts) ￡ Z*, p(t) = Y\tn. -c is prime,where c ^ 0 is a constant and Uj ^ rij, when i ^ j.Proposition 2.20. Suppose that polynomial p(x,y) satisfies p(x,y) =xm _m-1p(x,y) = Y[(x-pjy) (12)3=0where $ = e-2ijV/m, j = 1,2, ? ? ? , m - 1 , % denotes V^I. Proposition 2.21. If I ± 0 € 1$ and p(?) = (z^+ - z("')+), then p(zm)/p(z) is a polynomial and its every prime factor has a root on Ts = {z = fa, ? ? ? , za) € C : M = 1, i = 1,2, ? ? ? ,5}.Lemma 2.22. Let p(z) be a non-zero polynomial, tr, ^ 0 € Zs, j = 1,2,-?? ,k and p(^) FI^iC-2^5"1" ~ z(~t(u>) # 0,a.e., and satisfies following equation:fa) = J2 "l~k-lTi(") (13)0j I 1 < t < L}\J{btj I 1 < t < L). at,j is the j-th coordinate of vertex at in the t-th rectangle [at, bt]. btj is similar to atJ.