Cohen-Daubechies-Feauveau-Wavelet

Cohen-Daubechies-Feauveau-Wavelets (CDF-Wavelets) s​ind die historisch gesehen e​rste Familie d​er biorthogonalen Wavelets. Sie wurden v​on Albert Cohen, Ingrid Daubechies u​nd Jean-Christophe Feauveau konstruiert u​nd 1990 vorgestellt.[1] CDF-Wavelets s​ind zu unterscheiden v​on den orthogonalen Daubechies-Wavelets, d​ie andere Formen u​nd Eigenschaften besitzen. Beide Wavelettypen g​ehen auf d​ie gleiche Konstruktionsidee zurück, CDF-Wavelets verzichten zugunsten d​er Symmetrie a​uf Orthogonalität d​er Wavelets (bei Daubechies-Wavelets i​st es umgekehrt).

Der JPEG-2000-Kompressionsstandard verwendet d​as biorthogonale CDF-5/3-Wavelet (auch LeGall-5/3-Wavelet genannt) z​ur verlustfreien Kompression u​nd das CDF-9/7-Wavelet für d​ie verlustbehaftete Kompression.

Beispiel einer 2D-Wavelet-Transformation, die im JPEG2000-Standard verwendet wird

Eigenschaften

• Der Primgenerator ist ein B-Spline, wenn die einfache Faktorisierung ${\displaystyle q_{\mathrm {prim} }(X)=1}$ (siehe unten) gewählt wird
• Der Dualgenerator hat die maximale Anzahl an Glattheitsfaktoren, die für die Länge möglich ist
• Alle Generatoren und Wavelets dieser Familie sind symmetrisch.

Konstruktion

Für jede positive Ganzzahl ${\displaystyle A}$ gibt es ein eindeutiges Polynom ${\displaystyle Q_{A}(X)}$ vom Grad ${\displaystyle A-1}$, das der folgenden Identität genügt:

${\displaystyle (1-X/2)^{A}\,Q_{A}(X)+(X/2)^{A}\,Q_{A}(2-X)=1}$.

Es handelt s​ich um d​as gleiche Polynom, d​as bei d​er Konstruktion d​er Daubechies-Wavelets verwendet wird. Anstelle e​iner spektralen Faktorisierung w​ird hier jedoch versucht

${\displaystyle Q_{A}(X)=q_{\mathrm {prim} }(X)\,q_{\mathrm {dual} }(X)}$

zu faktorisieren. Die Faktoren ${\displaystyle q_{\mathrm {prim} }(X),q_{\mathrm {dual} }(X)}$ sind dabei Polynome mit reellen Koeffizienten und Absolutglied ${\displaystyle q_{\mathrm {prim} }(0)=q_{\mathrm {dual} }(0)=1}$.

In diesem Fall formen

${\displaystyle a_{\mathrm {prim} }(Z)=2Z^{d}\,\left({\frac {1+Z}{2}}\right)^{A}\,q_{\mathrm {prim} }(1-(Z+Z^{-1})/2)}$

und

${\displaystyle a_{\mathrm {dual} }(Z)=2Z^{d}\,\left({\frac {1+Z}{2}}\right)^{A}\,q_{\mathrm {dual} }(1-(Z+Z^{-1})/2)}$

ein biorthogonales Paar von Skalierungsfolgen. ${\displaystyle d}$ ist eine Ganzzahl, die zur Zentrierung der symmetrischen Folge auf Null verwendet wird, oder um die korrespondierenden diskreten Filter kausal zu machen.

Abhängig von den Wurzeln von ${\displaystyle Q_{A}(X)}$ gibt es bis zu ${\displaystyle 2^{A-1}}$ verschiedene Faktorisierungen. Eine einfache Faktorisierung ist ${\displaystyle q_{\mathrm {prim} }(X)=1}$ und ${\displaystyle q_{\mathrm {dual} }(X)=Q_{A}(X)}$. In diesem Fall ist die primäre Skalierungsfunktion das B-Spline der Ordnung ${\displaystyle A-1}$. Für ${\displaystyle A=1}$ erhält man das orthogonale Haar-Wavelet.

Koeffiziententabelle

Cohen-Daubechies-Feauveau-Wavelet 5/3, wie es im JPEG-2000-Standard verwendet wird.

Für ${\displaystyle A=2}$ erhält man das LeGall-5/3-Wavelet:

A	QA(X)	qprim(X)	qdual(X)	aprim(Z)	adual(Z)
2	${\displaystyle 1+X}$	1	${\displaystyle 1+X}$	${\displaystyle {\frac {1}{2}}(1+Z)^{2}\,Z}$	${\displaystyle {\frac {1}{2}}(1+Z)^{2}\,\left(-{\tfrac {1}{2}}+2\,Z-{\tfrac {1}{2}}\,Z^{2}\right)}$
				${\displaystyle ={\frac {1}{2}}\,\left(Z+2Z^{2}+Z^{3}\right)}$	${\displaystyle ={\frac {1}{4}}\,\left(-1+2Z+6Z^{2}+2Z^{3}-Z^{4}\right)}$

Für ${\displaystyle A=4}$ erhält man das 9/7-CDF-Wavelet. Man erhält ${\displaystyle Q_{4}(X)=1+2\,X+5/2\,X^{2}+5/2\,X^{3}}$. Dieses Polynom besitzt genau eine reelle Wurzel und ist somit das Produkt des linearen Faktors ${\displaystyle 1-c\,X}$ und eines quadratischen Faktors. Der Koeffizient ${\displaystyle c}$, der das Inverse der Wurzel ist, hat einen Wert von etwa −1,4603482098.

A	QA(X)	qprim(X)	qdual(X)
4	${\displaystyle 1+2\,X+5/2\,X^{2}+5/2\,X^{3}}$	${\displaystyle 1-c\,X}$	${\displaystyle 1+(c+2)*\,X+(c^{2}+2*c+5/2)\,X^{2}}$

Für d​ie Koeffizienten d​er zentrierten Skalierungs- u​nd Wavelet-Folgen erhält m​an numerische Werte i​n implementierungsfreundlicher Form:

k	Analyse-Tiefpassfilter (1/2 adual)	Analyse-Hochpassfilter (bdual)	Synthese-Tiefpassfilter (aprim)	Synthese-Hochpassfilter (1/2 bprim)
−4	0,026748757411	0	0	0,026748757411
−3	−0,016864118443	0,091271763114	−0,091271763114	0,016864118443
−2	−0,078223266529	−0,057543526229	−0,057543526229	−0,078223266529
−1	0,266864118443	−0,591271763114	0,591271763114	−0,266864118443
0	0,602949018236	1,11508705	1,11508705	0,602949018236
1	0,266864118443	−0,591271763114	0,591271763114	−0,266864118443
2	−0,078223266529	−0,057543526229	−0,057543526229	−0,078223266529
3	−0,016864118443	0,091271763114	−0,091271763114	0,016864118443
4	0,026748757411	0	0	0,026748757411

Nummernbezeichnung

Es g​ibt zwei parallele Nummerierungsschemata für Wavelets d​er CDF-Familie.

• Die Anzahl der Glattheitsfaktoren der Tiefpassfilter, oder (äquivalent) die Anzahl der verschwindenden Momente der Hochpassfilter, z. B. 2,2
• Die Längen der Tiefpassfilter, oder (äquivalent) die Längen der Hochpassfilter, z. B. 5,3

Das erste Schema wurde in Daubechies' Buch „Ten lectures on wavelets“ verwendet. Keine der Bezeichnungen ist eindeutig. Die Anzahl der verschwindenden Momente sagt nichts über die gewählte Faktorisierung aus. Eine Filterbank, deren Filterlängen 7 und 9 betragen, hat 6 und 2 verschwindende Momente, wenn man eine triviale Faktorisierung verwendet, oder 4 und 4 verschwindende Momente, wie in dem Fall des JPEG-2000-Wavelets. Das gleiche Wavelet kann daher als „CDF 9/7“ (basierend auf den Filterlängen) oder „biorthogonal 4/4“ (basierend auf den verschwindenden Momenten) heißen.

Lifting-Zerlegung

Für d​ie trivial faktorisierten Filterbänke k​ann eine Lifting-Zerlegung explizit gegeben werden.[2]

Literatur

• A. Cohen, I. Daubechies und J.C. Feauveau: Biorthogonal bases of compactly supported wavelets. Comm. Pure & Appl. Math 45, 1992, S. 485 bis 560.
• I. Daubechies: Ten Lectures on wavelets. SIAM, 1992.

Weblinks

• JPEG 2000: How does it work?
• CDF 9/7 Wavelet Transform for 2D Signals via Lifting: Source code in Python
• Open Source 5/3-CDF-Wavelet Implementierung in C#, für beliebige Größen

Einzelnachweise

1. Albert Cohen, Ingrid Daubechies und Jean-Christophe Feauveau: Biorthogonal Bases of Compactly Supported Wavelets, in Communications on Pure and Applied Mathematics, Volume 45, Issue 5, Wiley 1992
2. Siehe Abschnitt 3.2.4 der Ausarbeitung unter