Multiresolution analysis: Difference between revisions

Revision as of 15:39, 22 April 2012

Latest revision as of 15:22, 1 February 2025

(46 intermediate revisions by 37 users not shown)

Line 1:

{{Short description|Design method of discrete wavelet transforms}}

A '''multiresolution analysis (MRA)''' or '''multiscale approximation (MSA)''' is the design method of most of the practically relevant [[discrete wavelet transform]]s (DWT) and the justification for the [[algorithm]] of the [[fast wavelet transform]] (FWT). It was introduced in this context in 1988/89 by [[Stephane Mallat]] and [[Yves Meyer]] and has predecessors in the [[microlocal analysis]] in the theory of [[differential equation]]s (the ''[[ironing method]]'') and the [[pyramid (image processing)|pyramid method]]s of [[image processing]] as introduced in 1981/83 by Peter J. Burt, Edward H. Adelson and James Crowley.

{{Distinguish|Multiple-scale analysis}}

A '''multiresolution analysis''' ('''MRA)''') or '''multiscale approximation''' ('''MSA)''') is the design method of most of the practically relevant [[discrete wavelet transform]]s (DWT) and the justification for the [[algorithm]] of the [[fast wavelet transform]] (FWT). It was introduced in this context in 1988/89 by [[Stephane Mallat]] and [[Yves Meyer]] and has predecessors in the [[microlocal analysis]] in the theory of [[differential equation]]s (the ''[[ironing method]]'') and the [[pyramid (image processing)|pyramid method]]s of [[image processing]] as introduced in 1981/83 by Peter J. Burt, Edward H. Adelson and [http://www-prima.inrialpes.fr/Prima/Homepages/jlc/jlc.html James L. Crowley].

== Definition ==

A ''multiresolution analysis'' of the [[Lp space|Lebesgue space]] <math>L^2(\mathbb{R})</math> consists of a [[sequence]] of nested [[linear subspace|subspaces]]

::<math>\{0\}\subset \dots\subset V_1\subset V_0\subset V_1V_{-1}\subset\dots\subset V_nV_{-n}\subset V_{-(n+1)}\subset\dots\subset L^2(\R)</math>

A ''multiresolution analysis'' of the [[Lp space|space]] <math>L^2(\mathbb{R})</math> consists of a [[sequence]] of nested [[linear subspace|subspaces]]

that satisfies certain [[self-similarity]] relations in time/-space and scale/-frequency, as well as [[Complete metric space|completeness]] and regularity relations.

::<math>\{0\}\dots\subset V_0\subset V_1\subset\dots\subset V_n\subset V_{n+1}\subset\dots\subset L^2(\R)</math>

* ''Self-similarity'' in ''time'' demands that each subspace ''V_k'' is invariant under shifts by [[integer]] [[multiple (mathematics)|multiple]]s of ''2^-k''. That is, for each <math>f\in V_k,\; m\in\mathbb Z</math> therethe isfunction a <math>''g\in'' V_k</math>defined withas <math>\forall x\in\mathbb R:\;fg(x)=gf(x+-m2^{-k})</math> also contained in <math>V_k</math>.

that satisfies certain self-similarity relations in time/space and scale/frequency, as well as [[completeness]] and regularity relations.

* ''Self-similarity'' in ''scale'' demands that all subspaces <math>V_k\subset V_l,\; k<>l,</math> are time-scaled versions of each other, with [[Scaling_Scaling (geometry)|scaling]] respectively [[Dilation (metric space)|dilation]] factor ''2^l-''k-l''''. I.e., for each <math>f\in V_k</math> there is a <math>g\in V_l</math> with <math>\forall x\in\mathbb R:\;g(x)=f(2^{k-l-k}x)</math>. If f has limited [[support (mathematics)|support]], then as the support of g gets smaller, the resolution of the ''l''-th subspace is higher than the resolution of the ''k''-th subspace.

* In the sequence of subspaces, for ''k''>''l'' the space resolution 2^''l'' of the ''l''-th subspace is higher than the resolution 2^''k'' of the ''k''-th subspace.

* ''Self-similarity'' in ''time'' demands that each subspace ''V_k'' is invariant under shifts by [[integer]] [[multiple (mathematics)|multiple]]s of ''2^-k''. That is, for each <math>f\in V_k,\; m\in\mathbb Z</math> there is a <math>g\in V_k</math> with <math>\forall x\in\mathbb R:\;f(x)=g(x+m2^{-k})</math>.

* ''Regularity'' demands that the model [[linear subspace|subspace]] ''V₀'' be generated as the [[linear hull]] ([[algebraic closure|algebraically]] or even [[topologically closed]]) of the integer shifts of one or a finite number of generating functions <math>\phi</math> or <math>\phi_1,\dots,\phi_r</math>. Those integer shifts should at least form a frame for the subspace <math> V_0\subset L^2(\R) </math>, which imposes certain conditions on the decay at [[infinity]]. The generating functions are also known as '''[[Wavelet#Scaling function|scaling functions]]''' or '''[[father wavelets]]'''. In most cases one demands of those functions to be [[piecewise continuous]] with [[compact support]].

* ''Self-similarity'' in ''scale'' demands that all subspaces <math>V_k\subset V_l,\; k<l,</math> are time-scaled versions of each other, with [[Scaling_(geometry)|scaling]] respectively [[Dilation (metric space)|dilation]] factor ''2^l-k''. I.e., for each <math>f\in V_k</math> there is a <math>g\in V_l</math> with <math>\forall x\in\mathbb R:\;g(x)=f(2^{l-k}x)</math>. If f has limited [[support (mathematics)|support]], then as the support of g gets smaller, the resolution of the ''l''-th subspace is higher than the resolution of the ''k''-th subspace.

* ''Completeness'' demands that those nested subspaces fill the whole space, i.e., their union should be [[dense set|dense]] in <math> L^2(\mathbb{R}) </math>, and that they are not too redundant, i.e., their [[intersection]] should only contain the [[zero element]].

* ''Regularity'' demands that the model subspace ''V₀'' be generated as the [[linear hull]] ([[algebraic closure|algebraically]] or even [[topologically closed]]) of the integer shifts of one or a finite number of generating functions <math>\phi</math> or <math>\phi_1,\dots,\phi_r</math>. Those integer shifts should at least form a frame for the subspace <math>V_0\subset L^2(\R)</math>, which imposes certain conditions on the decay at infinity. The generating functions are also known as '''scaling functions''' or '''father wavelets'''. In most cases one demands of those functions to be [[piecewise continuous]] with [[compact support]].

* ''Completeness'' demands that those nested subspaces fill the whole space, i.e., their union should be [[dense set|dense]] in <math>L^2(\mathbb{R})</math>, and that they are not too redundant, i.e., their intersection should only contain the zero element.

== Important conclusions ==

In the case of one continuous (or at least with bounded variation) compactly supported scaling function with orthogonal shifts, one may make a number of deductions. The proof of existence of this class of functions is due to [[Ingrid Daubechies]].

ThereAssuming is,the becausescaling offunction has compact support, then <math>V_0\subset V_1V_{-1}</math>, implies that there is a finite sequence of coefficients <math>a_k=2 \langle\phi(x),\phi(2x-k)\rangle</math>, for <math>|k|\leq N</math>, and <math>a_k=0</math> for <math>|k|>N</math>, such that

:<math>\phi(x)=\sum_{k=-N}^N a_k\phi(2x-k).</math>

Defining another function, known as '''mother wavelet''' or just '''the wavelet'''

:<math>\psi(x):=\sum_{k=-N}^N (-1)^k a_{1-k}\phi(2x-k),</math>

one can seeshow that the space <math>W_0\subset V_1V_{-1}</math>, which is defined as the (closed) linear hull of the mother waveletswavelet's integer shifts, is the orthogonal complement to <math>V_0</math> inside <math>V_1V_{-1}</math>.<ref>{{Cite web|url=http://www.cmap.polytechnique.fr/~mallat/book.html|title=A Wavelet Tour of Signal Processing|last=Mallat, S.G.|website=www.di.ens.fr|access-date=2019-12-30}}</ref> Or put differently, <math>V_1V_{-1}</math> is the [[orthogonal direct sum|orthogonal sum]] (denoted by <math>\oplus</math>) of <math>W_0</math> and <math>V_0</math>. By self-similarity, there are scaled versions <math>W_k</math> of <math>W_0</math> and by completeness one has

:<math>L^2(\mathbb R)=\mbox{closure of }\bigoplus_{k\in\Z}W_k,</math>

one can see that the space <math>W_0\subset V_1</math>, which is defined as the linear hull of the mother wavelets integer shifts, is the orthogonal complement to <math>V_0</math> inside <math>V_1</math>. Or put differently, <math>V_1</math> is the orthogonal sum of <math>W_0</math> and <math>V_0</math>. By self-similarity, there are scaled versions <math>W_k</math> of <math>W_0</math> and by completeness one has

:<math>L^2(\mathbb R)=\mbox{closure of }\bigoplus_{k\in\Z}W_k,</math>

thus the set

:<math>\{\psi_{k,n}(x)=\sqrt2^{-k}\psi(2^kx{-k}x-n):\;k,n\in\Z\}</math>

:<math>\{\psi_{k,n}(x)=\sqrt2^k\psi(2^kx-n):\;k,n\in\Z\}</math>

is a countable complete [[orthonormal wavelet]] basis in <math>L^2(\R)</math>.

==See also==

* [[MultiscaleMultigrid modelingmethod]]

* [[ScaleMultiscale spacemodeling]]

* [[WaveletScale space]]

*[[Category:Time–frequency analysis]]

*[[Wavelet]]

== References ==

{{Reflist}}

* {{cite book|first=Charles K.|last=Chui|title=An Introduction to Wavelets|year=1992|publisher=Academic Press|___location=San Diego|isbn=0585470901}}

* {{cite book|first=Charles K.|last=Chui|title=An Introduction to Wavelets|year=1992|publisher=Academic Press|___location=San Diego|isbn=05854709010-585-47090-1}}

* {{cite book|author1-link=Ali Akansu|first1=A.N.|last1=Akansu|first2=R.A.|last2=Haddad|title=Multiresolution signal decomposition: transforms, subbands, and wavelets|publisher=Academic Press|year=1992|isbn=978-0-12-047141-6}}

* Crowley, J. L., (1982). [http://www-prima.inrialpes.fr/Prima/Homepages/jlc/papers/Crowley-Thesis81.pdf A Representations for Visual Information], Doctoral Thesis, Carnegie-Mellon University, 1982.

* {{cite book|author1-link=C. Sidney Burrus|first1=C.S.|last1=Burrus|first2=R.A.|last2=Gopinath|first3=H.|last3=Guo|title=Introduction to Wavelets and Wavelet Transforms: A Primer|publisher=Prentice-Hall|year=1997|isbn=01248960090-13-489600-9}}

* {{cite book|first=S.G.|last=Mallat|url=http://www.cmap.polytechnique.fr/~mallat/book.html|title=A Wavelet Tour of Signal Processing|publisher=Academic Press|year=1999|isbn=012466606X0-12-466606-X}}

[[Category:Time–frequency analysis]]

* {{cite book|author1-link=C. Sidney Burrus|first1=C.S.|last1=Burrus|first2=R.A.|last2=Gopinath|first3=H.|last3=Guo|title=Introduction to Wavelets and Wavelet Transforms: A Primer|publisher=Prentice-Hall|year=1997|isbn=0124896009}}

* {{cite book|first=S.G.|last=Mallat|url=http://www.cmap.polytechnique.fr/~mallat/book.html|title=A Wavelet Tour of Signal Processing|publisher=Academic Press|year=1999|isbn=012466606X}}

[[Category:Wavelets]]

[[Category:Time–frequency analysis]]

[[bg:Многомащабно приближение]]

[[cs:Multirozklad]]

[[de:Multiskalenanalyse]]

[[fr:Multirésolution]]

[[lt:Daugiaraiškė analizė]]

[[ru:Кратномасштабный анализ]]

[[zh:多解析度分析]]