Aufgabe
Schall
Licht
Abtastung
Quantisierung
MUSTERERKENNUNG
Teil II
Vorlesung im Sommersemester 2016
Diskretisierung
Binarisierung
Codierer
R
Binarisierung
Codierer
R
Σ
Prof. E.G. Schukat-Talamazzini
Stand: 11. März 2016
Aufgabe
Schall
Licht
Abtastung
Quantisierung
Binarisierung
Codierer
R
Σ
Aufgabe
Schall
Licht und Farbe
Abtastung
Quantisierung
Vorverarbeitung des Musters
Aufgabenstellung
Muster 7→ Digitalrechner 7→ „schöneres“ Muster
Aufnahme
Schallwellen — Geräusch, Klang, Sprache
Licht
f
Vorverarbeitung
Merkmale
Klassifikator
Ωκ
Arbeitsphase
Lernphase
Stichprobe
Lernen der
Klassenbereiche
Abtastung
Quantisierung
Binarisierung
Sonstige Codierer
Mathematische Hilfsmittel
Ziele
A/D-Wandlung
Datenreduktion
Störunterdrückung
Informationsfilterung
1. Diskretisierung
Sensordaten
maschinenlesbare (endliche!) Form
Diskretisierung
des
Definitionsbereichs (Abtastung)
Wertebereichs (Quantisierung)
2. Transformation
Gütekriterien
Diskretisiertes Muster
diskretisiertes Muster
Vorverarbeitung ⇒ Informationsverlust
Reproduzierbarkeit des Originals aus dem Resultat ?
Exakte Reproduktion
Perzeptuelle Äquivalenz
Semantische Äquivalenz
Σ
Aufgabe
Schall
Licht
Abtastung
Quantisierung
Binarisierung
Codierer
R
Σ
Aufgabe
Schall
Licht
Abtastung
Quantisierung
Binarisierung
Codierer
R
Codierer
R
Σ
Schallwellen
Aufgabenstellung
Geräusch, Klang, Sprache
Schallwellen — Geräusch, Klang, Sprache
Physikalische Substanz
Licht und Farbe
Zeitlicher Verlauf des Schalldrucks
Schallquelle und -sensor
Abtastung
Spektralzerlegung
Stationäres Signal = Wellensalat reiner (Sinus-)Töne
Frequenz, Amplitude, Phasenverschiebung
Quantisierung
Physikalischer Reiz
physiologische Wahrnehmung
Binarisierung
Schallintensität (Signaleigenschaft)
Lautstärkeempfindung (tonhöhenabhängig)
Sonstige Codierer
Mustererkennung als Funktionsmodell ?
„Ein Flugzeug schlägt nicht mit den Flügeln ...“
Mathematische Hilfsmittel
Aufgabe
Schall
Licht
Abtastung
Quantisierung
Binarisierung
Codierer
Σ
Aufgabe
Schall
Licht
Abtastung
Quantisierung
Binarisierung
Schallwelle als Zeitsignal
Reine Sinustöne
Schalldruck, Amplitude f : IR → IR
Wiederholrate · maximale Auslenkung · Zeitverschiebung
Definition
Definition
Sei f : IR → IR eine Schallwelle und [t0 , t1 ] ⊂ IR. Dann heißt
Z t1
def
E =
f 2 (t) dt
Die Schallwelle
f (t) = A · sin(2πωt + φ)
t0
heißt reiner Ton mit der Amplitude A, der Schwingungsfrequenz ω
und dem Phasenwinkel φ.
die Schallenergie und
def
Is =
1
·
t1 − t0
Z
t1
• Amplitude in Pascal oder Dezibel (N/m2 , dB)
• Frequenz in Hertz (1/s)
f 2 (t) dt
t0
der Schallpegel (oder Intensität, in N/m2 bzw. Pascal) des Schalls f im
Intervall [t0 , t1 ]. Die Größen
I =
Is
I0
bzw. ` = 10 log10
Is
I0
bezeichnen wir als (logarithmierte, in Dezibel [dB]) Lautstärke.
•
•
R
0dB:
Standardpegel I0 etwas unterhalb der Hörschwelle
3dB:
diese Zunahme entspricht einer Pegelverdopplung
mehr Information
• Phase in Radian (φ ∈ [0, 2π])
Σ
Aufgabe
Schall
Licht
Abtastung
Quantisierung
Binarisierung
R
Codierer
Σ
Aufgabe
Schall
Licht
Abtastung
Quantisierung
Binarisierung
Spektralzerlegung
Lautstärkeempfindung & Hörebene
Überlagerung von Sinuskomponenten unterschiedlicher Frequenz
Subjektiver Eindruck des Menschen ist frequenzabhängig!
Definition
Z
f˜ sei ein 1kHz-Schall gleicher subjektiver Lautstärke wie f .
Pegel(f )
ω = 1000 Hz
def
`(f ) [phon] =
˜
Pegel(f )
ω 6= 1000 Hz
∞
Aω · sin(2πωt + φω ) dω
f (t) =
0
heißt Spektralzerlegung des reellwertigen Signals f . Die
frequenzabhängigen Funktionen {Aω } und {φω } heißen
Amplitudenspektrum bzw. Phasenspektrum von f .
Beispielschallpegel
140 dB
120 dB
100 dB
80 dB
70 dB
50 dB
30 dB
20 dB
6 dB
0 dB
1
1.5
0
1
0.5
-1
0
-2
-0.5
-1
-3
-1.5
-2
-4
1
1.5
2
2.5
0
3
ω −1 · sin(2πωt), ω = 1, ..., 5
Aufgabe
Schall
Licht
Abtastung
0.5
1
P5
1
Quantisierung
1.5
2
2.5
Gewehrschuß nahebei
lautstarke Rockgruppe
Geschrei nahebei
belebte Straße
normale Unterhaltung
leise Unterhaltung
sanftes Flüstern
ländliche Gegend/Nacht
Hörschwelle bei 1000 Hz
Referenzpegel
Codierer
Aufgabe
Schall
Licht
40
40
20
20
3
0
20
Σ
60
60
3
R
80
80
ω −1 · sin(2πωt)
Binarisierung
100 phon
100
Pegel [dB]
2
0.5
Σ
Definition der Phonzahl
Die Darstellung
0
R
Codierer
Abtastung
50
100
200 Hz
Quantisierung
500
1
2 kHz
Binarisierung
5
10
20
Codierer
Kameraaufnahme
Aufgabenstellung
Vom Objekt zum Lichtermeer
Schallwellen — Geräusch, Klang, Sprache
P(x,y,z)
y
Licht und Farbe
P(x’,y’)
Lochkameramodell
x
z
Abtastung
Brennweite
Aufnahme:IR3 → IR2
Informationsverlust
(Verdeckung)
Quantisierung
Projektion
Binarisierung
Sonstige Codierer
Mathematische Hilfsmittel
Lineare Abbildung
Homogene Abbildung
perspektivisch
orthographisch
R
Σ
Aufgabe
Schall
Licht
Abtastung
Quantisierung
Binarisierung
Codierer
R
Σ
Aufgabe
Schall
Licht
Abtastung
Quantisierung
Binarisierung
Was ist Farbe ?
Subjektive Helligkeit eines Lichtpunkts
Farbe ist ein (elektromagnetischer) Wellensalat
Menschliche Helligkeitsempfindung ist wellenlängenabhängig
Codierer
R
Σ
Definition
Sei C (λ) = F 0 (λ) der Strahlungsenergieverlauf einer Lichtquelle. Der
Lichtstrom (in Lumen) ist definiert durch
Z ∞
def
∗
F = = K ·
Kλ · C (λ)dλ
C( λ)
λ
380 nm
780 nm
0
Definition
Er gibt die von einem Standardbeobachter wahrgenommene Helligkeit
einer Lichtquelle an.
Einen Strahlungsenergieverlauf C : [λmin , λmax ] → IR im Frequenzbereich
des sichtbaren Lichts bezeichnen wir als Farbe. Farben der speziellen
Gestalt
def
C (λ) = Cµmono (λ) = δ(λ − µ)
Photometrische Standards
1. Die Gewichtsfunktion (Kλ )λ∈IR ist ein CIE-Standard.
(CIE = Commission Internationale de l’Eclairage)
R
−1
2. Die Konstante lautet K ∗ =
Kλ dλ
= 683 [lm/W ].
heißen monochromatisch.
• Genauer: es ist C (λ) = F 0 (λ), und es ist F 0 (λ) dλ die Strahlungsenergie im
3. Der sichtbare Bereich farbigen Lichts liegt zwischen λ = 380nm und λ = 780nm.
Wellenlängebereich [λ, λ + dλ] in Watt.
Aufgabe
Schall
Licht
Abtastung
Quantisierung
Binarisierung
Codierer
R
Σ
Aufgabe
Schall
Licht
Abtastung
Quantisierung
Binarisierung
Codierer
Colorimetrie
Farbvergleichskurven
Darstellung in Farbräumen endlicher Dimension
Kurve der Tristimuluswerte über alle monochromatischen Farben
Empirische Wahrn.-Psychologie: Tristimulusdarstellung
• Die meisten Farben lassen sich (wahrnehmungsäquivalent) als
Definition
Linearkombination geeigneter Primärfarben erzeugen, z.B. Crprim , Cgprim , Cbprim
• Die erzeugenden Koeffizienten werden durch Wahrnehmungstest bestimmt.
• Beispiel Standardweiß: CW pz
= wr Crprim + wg Cgprim + wb Cbprim
• Betrachte weißnormierte Primärfarben, d.h. es gilt
Die Gewichtfunktionen αr (), αg (), αb () mit
pz X
Cµmono (λ) =
αx (µ) · Cxprim (λ)
r ,g ,b
pz
CW = Crprim + Cgprim + Cbprim (und damit wr = wg = wb = 1).
Definition
Bezogen auf ein weißnormales Primärfarbensystem
heißen die Koeffizienten in
pz
n
o
Crprim , Cgprim , Cbprim
C (λ) = ar Crprim (λ) + ag Cgprim (λ) + ab Cbprim (λ)
die Tristimuluswerte der Farbe C .
für jede monochromatische Farbe Cµmono heißen Farbvergleichskurven
n
o
(bezüglich Crprim , Cgprim , Cbprim ).
• CIE-Standard von 1931
drei monochromatische Primärfarben
ROT (λ = 700nm), GRÜN (λ = 546.1nm), BLAU (λ = 435.8nm)
R
Σ
Aufgabe
Schall
Licht
Abtastung
Quantisierung
Binarisierung
Codierer
R
Σ
Beweis.
Farbvergleichskurven
Wahrnehmungstreue Reproduzierbarkeit
X
βx · Cxprim (λ)
x
X Z ∞
=
αx (µ)C (µ) dµ · Cxprim (λ)
0
(
)
Zx ∞
X
prim
=
C (µ) ·
αx (µ) · Cx (λ) dµ
x
Z0 ∞
pz
C (µ) · Cµmono (λ) dµ
=
0
Z ∞
=
C (µ) · δλ−µ dµ
Lemma
=
PR
=
RP
Def. der Farbvergleichkurven αx (·)
monochromatische Farben
mit den (drei) Koeffizienten βx =
Licht
Abtastung
R∞
0
αx (µ) · C (µ) dµ für x = r , g , b.
Quantisierung
Binarisierung
Codierer
C (λ)
der tödliche Diracstoß
Bemerkung
pz
Die Wahrnehmungsgleichheit = ist im Gegensatz zu = keine Äquivalenzrelation; es
pz
pz
pz
gilt nämlich i.a. nicht die Transitivität a = b ∧ b = c ⇒ a = c.
r ,g ,b
Schall
einsetzen für βx
0
In einem weißnormalen Primärfarbensystem gilt für jede Farbe C (λ) die
Tristimulusdarstellung
pz X
C (λ) =
βx · Cxprim (λ)
Aufgabe
das sollte = C (λ) sein!
In oben angegebener Herleitung tritt aber glücklicherweise nur eine perzeptionelle
Gleichheit auf.
R
Σ
Aufgabe
Schall
Licht
Abtastung
Quantisierung
Binarisierung
Chromatizitätskoordinaten
Falsch-, besser: Pseudofarbendarstellung
Bezüglich Helligkeit normierte Tristimuluswerte
Grauwert-Farbwert-Transformation φ : [0, 1] → [0, 1]3
Codierer
φ : IR3 → IR3 =IR
˜ 2 mit
r
R
1
g =
· G
R +G +B
b
B
Originalaufnahme (grauwertig)
Zuordnungspfad
Pseudofarbendarstellung (rückwärts)
R
Σ
Aufgabe
Schall
Licht
Abtastung
Quantisierung
Binarisierung
Codierer
R
Σ
Aufgabe
Schall
Licht
Abtastung
Quantisierung
Binarisierung
Codierer
R
Σ
Diskretisierung
Aufgabenstellung
Endliche rechnerinterne Repräsentation eines Musters
Schallwellen — Geräusch, Klang, Sprache
f1 (x1 , x2 , . . . , xn )
f2 (x1 , x2 , . . . , xn )
f (x) =
···
fm (x1 , x2 , . . . , xn )
Licht und Farbe
Abtastung
Problem
Quantisierung
(Orte/Zeiten xj ∈ IR)
(Amplituden fi ∈ IR)
kontinuierlicher Definitionsbereich
kontinuierlicher Wertebereich
Binarisierung
Lösung
Amplitudenmessung nur an endlich vielen Stützstellen
Amplitudenwerte nur als Festkommagrößen darstellen
Sonstige Codierer
Mathematische Hilfsmittel
Aufgabe
Schall
Licht
Abtastung
Quantisierung
Binarisierung
Codierer
R
Σ
Aufgabe
Schall
Licht
Diskretisierung = Abtastung & Quantisierung
[?]
Analog-Digital-Wandlung (A/D)
Abtastung
Quantisierung
Binarisierung
CODEC — Kodierer / Dekodierer
Paradigma der Digitalen Signalverarbeitung (DSV/DSP)
Diskretisierung und Rekonstruktion
Abtastung
Quantisierung
·
·
·
·
·
·
·
·
Abtastperiode T [s]
Abtastfrequenz fA = 1/T [Hz]
Stützstellen {nT | n ∈ Z}
Abtastwerte fn = f˜(nT ), n ∈ Z
Speicherbedarf = fA · b [bit/s]
Wertebereich [−fmax , +fmax ] ⊂ IR
Kodierung mit b bit
2b Intervalle Iν = [aν−1 , aν ]
Intervallbreite ∆Q = 2fmax /2b
Aufnahme
Vorfilter
Abtasten
Quantisieren
Wiedergabe
Nachfilter
Dekodieren
(Verarbeiten)
Fragestellungen
Wieviele Abtastwerte?
Welche Schrittweite?
Wieviele Quantisierungsstufen?
Welche Quantisierungskennlinie?
Codierer
R
Σ
Aufgabe
Schall
Licht
Abtastung
Quantisierung
Binarisierung
Codierer
R
Σ
Abtastung bandbegrenzter Zeitsignale
Obergrenze B für die Frequenzen auftretender Spektralkomponenten
Definition
Beweis (1)
Fouriertransformationen vor und zurück:
Sei f : IR → C eine Zeitfunktion und
Z +∞
def
F (ξ) =
f (x)e −i ξx dx
+∞
Z
F (ξ)
f (x)e
=
, ξ ∈ IR
−i ξx
dx
−∞
−∞
f (x)
1
=
2π
ihre Fouriertransformierte. Die Funktion f heißt bandbegrenzt im
Frequenzbereich (−B, B), wenn für alle |ξ| > 2πB die Aussage F (ξ) = 0 gilt.
+∞
Z
·
F (ξ)e
i ξx
dξ
−∞
Fourierreihe einer Funktion, die in (−ξ0 , +ξ0 ) periodisch ist:
Satz (Abtasttheorem von Shannon)
Sei f : IR → IR bandbegrenzt im Frequenzbereich (−B, B) und
0 < ∆x ≤ 1/(2B) . Dann ist f vollständig durch seine Abtastwerte
fj := f (j · ∆x ), j = 0, ±1, ±2, . . . bestimmt und die
Rekonstruktionsgleichung lautet
+∞
X
f (x) =
x − j∆x
fj · sinc π ·
∆x
j=−∞
F (ξ)
+∞
X
=
aj e
2πi ·
jξ
2ξ0
j =−∞
aj
+ξ0
Z
1
=
·
2ξ0
F (ξ)e
−2πi ·
jξ
2ξ0
dξ
−ξ0
def
wobei sinc(r ) = sin(x)/x vereinbart sei.
Beweis (2)
Wir berechnen f (x) aus dem Umkehrintegral der Fouriertransformierten. Dabei betrachten wir F (ξ) als
eine Periode einer (gedanklich) periodisch fortgesetzten Funktion und entwickeln F (ξ) in eine
Fourierreihe mit den Koeffizienten:
aj
=
=
·
2ξ0
F (ξ)e
−2πi ·
jξ
2ξ0
2π ξ0
+ξ0
Z
·
F (ξ)e
f (x)
dξ
=
−j π
ξ0
1
2π
Z
·
·
=
f (−j∆x ) · ∆x
−ξ0
1
2B
=
Damit ergibt sich für F (ξ) die Darstellung als Fourierreihe:
=
+∞
X
=
2π
j =−∞
ξ0
=
+∞
X
·
jξ
2πi ·
2ξ0
aj e
+∞
X
f (−j∆x )e
f (j∆x )e
−ij ξ∆x
f (j∆x )e
+∞
X
=
+∞
X
∆x
∆x
∆x e
{z
i ξx
dξ
}
F (ξ)
Z
+ξ0
f (j∆x )
e
i ξ(x−j ∆x )
∆x dξ
−ξ0
f (j∆x ) ·
f (j∆x ) ·
fj ·
−ij ξ∆x
j =−∞
j =−∞
j =−∞
ij ξ∆x
+∞
X
j =−∞
j =−∞
j =−∞
+∞
X
π
=
j =−∞
=
1
ξ0
+∞
X
|
=
mit ∆x =
+ξ0
dξ
π
f
ξ0
i ξ·
−ξ0
−jπ
=
F (ξ)
Wir setzen F (ξ) in das Umkehrintegral für f (x) ein:
−ξ0
1 π
+ξ0
Z
1
Beweis (3)
∆x
2π
∆x
2π
·
·
1
i (x − j∆x )
e
i ξ(x−j ∆x )
+ξ
0
−ξ0
2 sin(ξ0 (x − j∆x ))
x − j∆x
sin(2πB(x − j∆x ))
2πB(x − j∆x )
Die letzte Zeile folgt wegen ξ0 = 2πB, ∆x = 1/(2B) und f (j∆x ) = fj , und die vorletzte Zeile wegen der
Eulergleichung e iy = cos y + i sin y .
Ist B die Bandbegrenzung in der Voraussetzung des Abtasttheorems, so gilt obige Darstellung für jedes
∆x < 1/(2B) , weil dann ∆x = 1/(2B 0 ) für ein B 0 > B gilt und f (x) natürlich auch B 0 -bandbegrenzt ist.
Aufgabe
Schall
Licht
Abtastung
Quantisierung
Binarisierung
R
Codierer
Σ
Aufgabe
Schall
Abtasten mit doppelter Nyquist-Grenzfrequenz
Licht
Abtastung
Quantisierung
Binarisierung
Codierer
R
Σ
Unschärfeprinzip der Wellenlehre
Erfolgreich in der Theorie und in der Praxis ?
f(t)
F( ω)
Theorie
Claude E. Shannon garantiert uns eine völlig verlustfreie
Abtastwertrepräsentation bandbegrenzter Signale.
t
ω
f(t)
F( ω)
Praxis
t
Die Signale (Zeitreihen, Bilder) der realen Welt sind nicht bandbegrenzt!
ω
f(t)
F( ω)
Definition
t
Die Funktion f : IR → C heißt zeitbegrenzt im Intervall (−b, b) wenn
gilt:
f (x) = 0 für alle |x| > b
ω
f(t)
F( ω)
t
ω
Satz (Paley & Wiener 1934)
Fakt
Fakt
Alle von Menschen und
Maschinen gemessenen
Sensorsignale sind zeitbzw. ortsbegrenzt!
Das (unendlich) periodische Fortsetzen
eines Signalintervalls erzeugt Unstetigkeiten
an den Nahtstellen, zerstört also
Frequenzbandbegrenzung!
Aufgabe
Schall
Licht
Abtastung
Quantisierung
Binarisierung
Es gibt (im Funktionenraum L2 ) keine Funktion außer der identisch
verschwindenden Funktion, die sowohl bandbegrenzt wie auch
zeitbegrenzt ist.
R
Codierer
Σ
Aufgabe
Schall
Licht
Abtastung
Schallabtastung
Quantisierung
Quadratisches Gitter
4/8-Nachbarschaft.
Beispielszenarien
• Analogtelefon (300 Hz – 3.4 kHz)
ATR = 8 kHz
• Sprache & HQ-Mikrofon
ATR = 16 kHz
• Musik
ATR = 44.1 kHz
• (analog vorgefiltert)
quadratisch
hexagonal
1
1
1
0.5
0.5
0.5
0
0
0
-0.5
-0.5
-0.5
-1
5
10
15
Analogsignal
20
triagonal
Hexagonale und
tridiagonale Gitter
besitzen „schönere“
Nachbarschaftsstruktur,
aber kompliziertere
Rasterpunktformeln.
Eindimensionale Muster (äquidistante Stützstellen)
ATR = . . . kHz
0
Codierer
Bildrasterung
Existenz und Lage der Bandbegrenzung ist anwendungsabhängig
-1
Binarisierung
Abtastung∆x :
5
10
15
suffiziente Abtastung
20
→
7→
J
IR
fj = f (x0 + j∆x )
,
J=
x1 − x0
∆x
Zweidimensionale Muster (quadratisches Gitter)
-1
0
IR[x0 ,x1 ]
{f (x)}
0
5
10
15
Unterabtastung
20
Rasterung∆x ,∆y :
IR[x0 ,x1 ]×[y0 ,y1 ]
{f (x, y )}
→
7→
Jx ·Jy
IR
fj,k = f (x0 + j∆x , y0 + k∆y )
R
Σ
Aufgabe
Schall
Licht
Abtastung
Quantisierung
Binarisierung
Codierer
R
Σ
Aufgabe
Schall
Licht
Abtastung
Quantisierung
Binarisierung
Codierer
R
Σ
Skalare Quantisierung
Aufgabenstellung
• Das Intervall [fmin , fmax ] wird mit 2B Stufen quantisiert
Schallwellen — Geräusch, Klang, Sprache
• Reelle Werte werden mit ihrem Intervallindex kodiert (B bit/ATW)
Licht und Farbe
f’
1
j
f
f’
1
j
j
fmin
0
Abtastung
fmax
0
f
j
S
Quantisierung
lineare Quantisierung
Zerlegung in Teilintervalle gleicher Länge (s. Abb.)
Binarisierung
nichtlineare Quantisierung
Sonstige Codierer
· Intervalle unterschiedlicher Länge
· Kompandierungsfunktion & lineare Quantisierung
Mathematische Hilfsmittel
Vektorquantisierung
Aufgabe
Schall
Licht
Abtastung
Quantisierung
Binarisierung
Codierer
R
Σ
Aufgabe
Schall
Licht
Quantisierungsfehler
Abtastung
Quantisierung
Binarisierung
Codierer
Lineare Quantisierer
„Jedes Bit verbessert die SNR eines Quantisierers um etwa 6 dB“
Definition
Sei {fj } eine Abtastfolge und {fj0 } das Ergebnis ihrer Quantisierung. Die
Differenzfolge
def
nj = fj − fj0
heißt Quantisierungsrauschen, das Erwartungswertverhältnis
r0 =
E[fj2 ]
E[nj2 ]
bzw. r = 10 · log10 r 0
wird als (logarithmiertes, in dB) Signal-Rausch-Verhältnis oder
Störabstand bezeichnet (SNR = „signal-to-noise ratio“).
Bemerkung
Die Schreibweise der Energie als zweites Moment setzt Mittelwertfreiheit der
beteiligten Signale voraus.
0 dB: Rauschenergie = Nutzsignalenergie
6 dB: relative Steigerung/Senkung des Nutzpegels/Rauschpegels um den Faktor 2
20 dB: Nutzpegel zehnmal höher als Rauschpegel
Satz
Für einen linearen Quantisierer mit 2B Quantisierungsstufen beträgt das
Signal-Rausch-Verhältnis unter den im Beweis genannten
Voraussetzungen
r = 6B − 7.2
[dB]
Idealisierte Voraussetzungen
1. kein Übersteuern:
fj ∈ [fmin , fmax ] für alle j
2. Amplitudenkonzentration wie N (µ, σ) oder besser:
3. näherungsweise uniformes Rauschen:
4σ-Regel
B
Intervallzahl 2 hinreichend groß
Folgerung
Mit fmax = −fmin = C σf beträgt der SRA r = 6B + 4.8 − 20 log10 C .
R
Σ
Aufgabe
Beweis.
Es bezeichne ∆ := (fmax − fmin )
2
B
Schall
Licht
Abtastung
Quantisierung
Binarisierung
Codierer
die Schrittweite des Quantisierers.
Beispielszenarien
Ist die Zahl 2B der Quantisierungsstufen hinreichend groß und wird der Quantisierer niemals übersteuert,
so dürfen wir den Quantisierungsfehler (das Rauschen) als näherungsweise gleichverteilt annehmen:
Quantisierung audiovisueller Daten
−∆/2 ≤ nj ≤ ∆/2
sonst
1/∆
0
P(nj ) =
• Bilder — 1 Byte = 8 bit (ggf. je Farbkanal)
Wegen E[nj ] = 0 (Mittelwertfreiheit) besitzt der Quantisierungsfehler die Varianz
+∆/2
Z
2
E[nj ] =
1
2
−∆/2 ∆
· nj dnj =
∆2
• Sprache — 8 bit für Telefonqualität
12
• Audio (CD/DAT) — 2×16 bit (1.41 Mb/s)
Sei nun o.B.d.A. unser Signal mittelwertfrei, d.h. E[fj ] = 0. Die Intervallgrenzen
fmin
def
= −4σf ,
fmax
def
= +4σf ,
σf
def
• DAB (Digital Audio Broadcasting) — 256 kb/s
q
E[fj2 ]
=
vermeiden fast sicher eine Übersteuerung des Quantisierers und implizieren die konkrete Schrittweite
∆ =
(+4σf ) − (−4σf )
2B
=
8σf
Aufgabe
0
=
Schall
E[fj2 ]
E[nj2 ]
Licht
=
σ2
f
2
∆ /12
12σ 2
f
=
64σ 2 /(2B )2
=
f
Abtastung
12
64
·2
Quantisierung
2B
= 12 · 2
f min
j
Binarisierung
fmax
a0 a1
8 kHz 1×8 bit
44.1 kHz 2×16 bit
44.1 kHz 2×16 bit
Video MPEG–2
Video NTSC
Video HDTV
2B−6
Nichtlineare Quantisierer
f
SPEZIFIKATION
2B
und den Störabstand (s.u.); die Logarithmierung von r 0 ergibt dann das erwünschte Resultat.
r
TYP
Audio verständlich
Audio MPEG-Codierung
Audio CD/DAT
a2 a3 a4 a5
Codierer
24 bit/pel 640×480
24 bit/pel 640×480
24 bit/pel 1280×720
b2
bL
0.42 MB/s
27 MB/s
81 MB/s
Beweis.
Wir bilden die partiellen Ableitungen von εP nach bν und setzen sie gleich Null:
aL
b3 b4 b5
kbit/s
kbit/s
Mbit/s
MB/h)
Σ
Z
∂εP
aν
!
−2 · (f − bν ) · P(f ) df = 0
=
∂bν
b1
64
384
1.41
(635
R
f’
j
DATENRATE
aν−1
Daraus folgt auch schon die Bestimmungsgleichung für die bν .
Analog erhalten wir für die Intervallgrenzen aν :
Satz
Die optimale Quantisierungskennlinie, die den Verzerrungfehler
εP =
L Z
X
ν=1
∂εP
∂aν
aν
(f − bν )2 · P(f )df
aν−1
=
=
!
=
∂
∂aν
"Z
aν
Z
2
(f − bν ) · P(f ) df +
aν−1
2
aν+1
#
2
(f − bν+1 ) · P(f ) df
aν
2
(aν − bν ) P(aν ) − (aν − bν+1 ) P(aν )
0
Auflösen nach aν ergibt das obere System von Bestimmungsgleichungen.
minimiert, ist durch die Gleichungen
Im Beweis ist zu fordern, daß P(aν ) 6= 0 (∀ν) gilt.
aν =
bν + bν+1
2
R aν
und
bν =
f · P(f ) df
aν−1
R aν
P(f ) df
aν−1
für ν = 1, 2, . . . , L − 1 bzw. ν = 1, 2, . . . , L gegeben.
Die Bestimmungsgleichungen des Satzes sind gekoppelt und daher nur für eine iterative Berechnung der
Kennlinie zu verwenden.
R
Σ
Aufgabe
Schall
Licht
Abtastung
Quantisierung
Binarisierung
Codierer
R
Σ
Nichtlineare Quantisierung
32000*log10(1+100*x/32000)/log10(1+100)
32000*log10(1+500*x/32000)/log10(1+500)
Schall
Licht
Abtastung
Quantisierung
Binarisierung
Codierer
R
Binarisierung
Codierer
R
Σ
Aufgabenstellung
Näherungsweise gleichverteilende Transformation + lineare Quantisierung
35000
Aufgabe
32000*log10(1+100*x/32000)/log10(1+100)
32000*log10(1+500*x/32000)/log10(1+500)
35000
Schallwellen — Geräusch, Klang, Sprache
30000
30000
25000
Quantisierung
Quantisierung
25000
20000
15000
Licht und Farbe
20000
15000
10000
10000
Abtastung
5000
5000
0
0
5000
10000
15000
20000
Signalamplitude
25000
30000
0
1
Bereiche großer Amplituden komprimiert
Bereiche kleiner Amplituden expandiert
10
100
Signalamplitude
1000
10000
(einfach logarithmische Darstellung)
Quantisierung
Das logarithmische Kompandierungsgesetz (µ-Law)
Binarisierung
|f |
0 def
fj = fmax · sign(fj ) ·
j
log(1 + µ fmax
)
log(1 + µ)
,
Sonstige Codierer
µ ∈ 100 . . . 500
überführt betragsmäßig exponentiell verteilte Amplitudenwerte in eine
Gleichverteilung.
Aufgabe
Schall
Licht
Abtastung
Quantisierung
Binarisierung
Mathematische Hilfsmittel
Codierer
R
Σ
Aufgabe
Schall
Binarisierung von Grauwertbildern
Graustufen {0, 1, . . . , L − 1}
Licht
Abtastung
Quantisierung
Binarisierung von Grauwertbildern
Schwarz-Weiß-Codes {0, 1}
Objekt-Hintergrund-Entscheidung durch Schwellwertvergleich
GRAUWERTGEBIRGE EINER BILDZEILE
160
140
Grauwertstufe
120
100
SCHWELLWERT = 90
80
60
40
20
0
100
200
300
400
500
x-Ordinate
Originalbild
(512 × 512, 8 bit)
Binärbild
Objekt(S) · Hintergrund(W )
Horizontaler Grauverlauf
(Zeile 250)
Binarisierung
· dient der Objekt-Hintergrund-Segmentierung
· gelingt wenn alle O-Punkte dunkler als alle H-Punkte
· gelingt wenn alle O-Punkte heller
als alle H-Punkte
Nachbearbeitung
· erfordert i.a. Korrektur durch
des Binärbildes
Vorverarbeitung
Originalbild
(512 × 512, 8 bit)
Binärbild
(Objekt: fjk ≤ 130)
Binärbild
(Objekt: fjk ≤ 80)
Definition
Sei f : D → {0, . . . , L − 1} ein Grauwertbild und θ ein Grauwert. Das
Binärbild f θ : D → {0, 1} mit
1
fjk > θ
θ
fjk =
, (j, k) ∈ D
0
fjk ≤ θ
heißt Binarisierung von f zum Schwellwert θ.
Σ
Aufgabe
Schall
Licht
Abtastung
Quantisierung
Binarisierung
Codierer
R
Σ
Aufgabe
Schall
Licht
Abtastung
Quantisierung
Binarisierung
Codierer
Binarisierung von Grauwertbildern
Grauwerthistogramm
Funktioniert nicht immer & ist manchmal richtig schwierig
Häufigkeitsstatistik der im Bild auftretenden Grauwerte
R
Σ
GRAUWERTGEBIRGE EINER BILDZEILE
200
MIKROSKOPISCHE BODENPROBE IN ACRYL
16000
180
14000
160
140
12000
Absolute H ufigkeit
Grauwertstufe
SCHWELLWERT = 128
120
100
80
60
10000
8000
6000
4000
40
20
0
100
200
300
400
2000
500
x-Ordinate
Originalbild
(512 × 512, 8 bit)
Binärbild
(Objekt: fjk ≤ 128)
60
80
100
Grauwertstufe
def
120
140
160
Quantisierung
(0 ≤ ` < L)
Binarisierung
Codierer
R
Σ
Aufgabe
Schall
Licht
Abtastung
Quantisierung
Binarisierung
Codierer
Binarisierungsschwellwert
Gaußsches Mischverteilungsmodell
Kriterien zur Bestimmung aus dem Grauwerthistogramm
Grauwerte von Objekt/Hintergrund folgen je einer Normalverteilung
MIKROSKOPISCHE BODENPROBE IN ACRYL
Mittiger Grauwert
16000
Histogramm-Minimum
14000
θ = L/2
θ = argmin q` = argmin Q`
θ = E[`|{q` }] =
L−1
X
q` · `
`=0
Histogramm-Hauptsenken
· das zentralste relative Minimum
· das absolute Minimum in [`max
, `max
]
1
2
Ein Wert θ mit der Eigenschaft
10000
8000
6000
4000
2000
Maximale Entropie
Hθ ({q` }) ist definiert als
Grauwertmedian
12000
`
Absolute H ufigkeit
`
Grauwertdurchschnitt
n
o
n
o
(1 − λθ ) · H( q`<θ ) + λθ · H( q`>θ )
0
0
20
q(`) =
=
θ−1
X
`=0
q` ≤ 1/2 und
L−1
X
`=θ+1
q` ≤ 1/2
180
heißt absolutes
Grauwerthistogramm von f , das Zahlenfeld {q` } mit
P
q` = Q` / m Qm heißt normiertes Grauwerthistogramm von f .
viele Objekte, Verdeckungen, problematische Beleuchtung, ...
Abtastung
40
Q` = Anzahl der (j, k) ∈ D mit fjk = ` ,
Komplexe Szenen
Licht
20
Sei f : D → {0, . . . , L − 1} ein Grauwertbild. Das Zahlenfeld {Q` } mit
· Finden eines optimalen Schwellwertes
· Vermeidung u/o Korrektur von Fehlzuordnungen
· Trick 17: Einfärben des Hintergrundes o.ä.
Schall
0
Definition
Einfache Objektansichten
Aufgabe
0
Bodenprobe in Acryl
Horizontaler Grauverlauf
(Zeile 250)
mit
Teilhistogrammen
n den
o unteren/oberen
n
o
q`<θ und q`>θ
=
40
60
80
100
Grauwertstufe
120
140
160
180
λu · qu (`) + λo · qo (`)
λu · N (` | µu , σu2 ) + λo · N (` | µo , σo2 )
1 `−µu 2
1 `−µo 2
1
1
λu · √ · e − 2 ( σu ) + λo · √ · e − 2 ( σo )
σu 2π
σo 2π
R
Σ
Aufgabe
Schall
Licht
Abtastung
Quantisierung
Binarisierung
Codierer
R
Σ
Intermeans-Algorithmus
hAlgorithmusi
Wähle θ0 beliebig (z.B. Mittelwert); setze r = 0
1
Berechne unteren und oberen Grauwertdurchschnitt:
, θ −1
, L−1
θX
L−1
r −1
r
X
X
X
<
>
µr =
q` · `
q` und µr =
q` · `
q`
2
`=θr
3
Abtastung
Codierer
R
Binarisierung
Codierer
R
Σ
Binarisierung
Sonstige Codierer
Bemerkung
Der Intermeans-Algorithmus ist ein sehr einfacher Spezialfall der
Mischverteilungsidentifikation mittels EM-Prinzip (’expectation-maximization’).
Licht
Binarisierung
Quantisierung
µ<
µ>
r
+ r
2
2
Abbruch oder Schritt (1)
Schall
Quantisierung
Abtastung
`=θr
isumhtiroglAh
Aufgabe
Abtastung
Licht und Farbe
Berechne neue Grauwertschwelle
θr +1 =
Licht
Schallwellen — Geräusch, Klang, Sprache
0
`=0
Schall
Aufgabenstellung
Iterative Berechnung des optimalen GMV-Schwellwertes für λu = λo , σu2 = σo2
`=0
Aufgabe
Quantisierung
Binarisierung
Codierer
Mathematische Hilfsmittel
R
Σ
Aufgabe
Schall
Sonstige Mustercodierverfahren
Licht
Abtastung
Quantisierung
Σ
Kettencode (’Freeman code’)
Codierung von Linienmustern oder Konturen (Objektumrissen)
Lauflängencodierung
3
Es werden Paare der Art hGrauwert, Daueri angegeben. (Binärbilder!)
2
1
Differentielle Codierung
Statt der fj werden die Differenzen fj∆ = fj − fj−1 quantisiert.
(hohe Abtastfrequenz
kleine fj∆ )
0
4
Transformationscodierung
Die Abtastfolge f wird durch das Ergebnis einer Reihenentwicklung f 0 = Af ,
A ∈ IR(M×N) , repräsentiert.
Vektorquantisierung
Statt skalarer Abtastwerte fj werden komplette Vektoren (fj , . . . , fj+S ) auf
Quantisierercodewörter abgebildet.
Fraktale Codierung
Eine (affine) Selbstähnlichkeit der Abtastfolgen wird ausgenutzt:
f 7→ (A, b) mit f = Af + b und dem Fixpunktdecoder f n = Af n−1 + b
5
(Kontur-)Linienrasterpunkte
werden durch die Folge ihrer Richtungselemente codiert.
Beispiel
Obiges Linienmuster wird durch den Kettencode
4 4 3 2 3 2 1 2 0 0 1 0 0 0 7 0 7 7 7 7 6 7 6
verschlüsselt.
6
7
Aufgabe
Schall
Licht
Abtastung
Quantisierung
Binarisierung
Codierer
R
Σ
Aufgabe
Schall
Licht
Abtastung
Binarisierung
kontinuierliche
Funktion
kontinuierliches
Frequenzspektrum
f(x)
Licht und Farbe
Σ
F( ξ)
ξ
x
Satz (Fourierintegrale)
Abtastung
Wenn
R +∞ f : IR → C die Dirichletbedingungen erfüllt und das Integral
|f (x)| dx konvergiert, dann gilt für f die folgende Darstellung:
−∞
Quantisierung
f (x)
=
F (ξ)
=
Binarisierung
Z +∞
1
F (ξ) · e i ξx dξ
2π −∞
Z +∞
f (x) · e −i ξx dx
−∞
Sonstige Codierer
Bemerkung
Die Funktion F : IR → C heißt Fouriertransformierte von f , die zweite Gleichung des
Satzes ist die Hintransformation, die erste Gleichung die Rücktransformation.
Mathematische Hilfsmittel
Schall
Licht
Abtastung
Quantisierung
Binarisierung
Codierer
R
Σ
Aufgabe
Schall
Licht
Abtastung
Quantisierung
Binarisierung
Kontinuierliche Fouriertransformation
Rechenregeln für Fouriertransformierte
Spezialfall: reellwertige Funktionen f : IR → IR
Zeitbereich — Frequenzbereich
Definition
Eine Funktion f : IR → IR heißt gerade, wenn für alle x ∈ IR die Aussage
f (−x) = f (x) gilt. Sie heißt ungerade, wenn für alle x ∈ IR die Aussage
f (−x) = −f (x) gilt.
Bemerkung
cos(x) ist gerade, sin(x) ist ungerade, die Gerade f (x) = a · x ist ungerade.
Lemma
Jede Funktion f : IR → IR läßt sich eindeutig in eine Summe aus geradem und
ungeradem Anteil zerlegen; wähle
f (x) + f (−x)
fg (x) =
2
def
und
f (x)
F (ξ)
f (ax)
1
F (ξ/a )
|a|
Verschiebung
f (x − x0 )
e −i ξx0 F (ξ)
Symmetrie
1
− 2π
F (x)
f (−ξ)
Ableitung
d n f (x)
dx n
(iξ)n F (ξ)
Faltungssatz
f ?g
F (ξ) · G (ξ)
Skalierung
f (x) − f (−x)
fu (x) =
.
2
def
Definition (kontinuierliche Faltung)
Folgerung
Für reellwertige Funktionen lauten die speziellen Gleichungen der
Fouriertransformation:
1
2π
R
Komplexwertige Funktionen im Zeit- und Frequenzbereich[?]
Schallwellen — Geräusch, Klang, Sprache
f (x) =
Codierer
Kontinuierliche Fouriertransformation
Aufgabenstellung
Aufgabe
Quantisierung
Z
+∞
−∞
Aξ cos(ξx) + Bξ sin(ξx) dξ und
R
Aξ = R f (x) cos(ξx) dx
Bξ =
f (x) sin(ξx) dx
Für zwei Funktionen f , g : IR → C heißt
Z +∞
h(x) =
f (ξ) · g (x − ξ) dξ
−∞
das Faltungsintegral; wir schreiben auch kürzer h = f ? g .
Codierer
R
Σ
Aufgabe
Schall
Licht
Abtastung
Quantisierung
Binarisierung
Codierer
R
Σ
Aufgabe
Schall
Licht
Abtastung
Quantisierung
Binarisierung
Fourierreihen periodischer Funktionen
Fourierreihen periodischer Funktionen
Komplexwertige Funktionen im Zeit- und Frequenzbereich
Reellwertige Funktionen im Zeit- und Frequenzbereich
periodische
kontinuierliche
Funktion
f(x)
diskretes
Frequenzspektrum
Codierer
R
Σ
|Fκ|
Definition (reelle Fourierreihe)
x
T
Besitzt f : IR → IR die Periode T , so heißt
κ
∞
a0 X
f˜(x) =
+
{ak cos(kωx) + bk sin(kωx)}
2
Definition (komplexe Fourierreihe)
k=1
Besitzt f : IR → C die Periode T und ist ω = 2π/T , so heißt
f˜(x) =
+∞
X
mit den Fourierkoeffizienten
Z
2 T
f (x) cos(kωx) dx
ak =
T 0
Fk · e ikωx
k=−∞
mit den komplexen Fourierkoeffizienten
Z
1 T
Fk =
f (x) · e −ikωx dx
T 0
und
bk =
2
T
T
Z
f (x) sin(kωx) dx
0
die Fourierreihe von f . Dabei bezeichnet ω = 2π/T die zu T gehörende
Kreisfrequenz.
die komplexe Fourierreihe von f .
Aufgabe
Schall
Licht
Abtastung
Quantisierung
Binarisierung
Codierer
R
Σ
Aufgabe
Umrechnen der Fourierkoeffizienten
Fk
k=0
k>0
k<0
und
Licht
Abtastung
Quantisierung
Binarisierung
Codierer
Konvergenz & Parsevalsche Gleichung
Satz
Komplexe und reelle Koeffizienten
a0 /2
(ak − ibk )/2
=
(a−k + ib−k )/2
Schall
Ist die periodische Funktion f beschränkt und erfüllt die Dirichlet-Bedingungen,
so konvergiert ihre Fourierreihe im Mittel gegen f .
ak = Fk + F−k
bk = i · (Fk − F−k )
Polare und reelle Koeffizienten
Summe von cos- und sin-Anteilen ist auch durch Phasenverschiebung
darstellbar:
ak cos(kωx) + bk sin(kωx) = Ak · cos(kωx + φk )
Satz
Für konvergierende reelle (komplexe) Fourierreihen periodischer Funktionen
gelten die Gleichungen
Z
∞
2 T
a02 X 2
|f (x)|2 dx =
+
ak + bk2
T 0
2
k=1
Z T
+∞
X
1
|f (x)|2 dx =
|Fk |2
T 0
k=−∞
mit den Koeffizienten
Ak =
q
ak2 + bk2
und
bzw. ak = A · cos φk und bk = −A · sin φk .
tan φk = −
bk
ak
Bemerkung
Periodische Funktionen können also im Konvergenzfall durch ein diskretes Spektrum
repräsentiert werden.
Die Signalenergie einer Periode kann im Zeitbereich integriert werden oder aber im
Spektralbereich summiert.
R
Σ
Aufgabe
Schall
Licht
Abtastung
Quantisierung
Binarisierung
Codierer
R
Σ
Aufgabe
Schall
Licht
Abtastung
Quantisierung
Binarisierung
Fouriertransformation diskreter Abtastfolgen
Frequenzband & Einheitskreis
f ist diskret genau dann, wenn F periodisch ist
Was bedeuten die komplexen Spektralkoeffizienten Fω ?
iω
F(e )
π
2π
ω
is
0
2π
κ
0
re
sk
fκ
eit
nh
periodisches
kontinuierliches
Frequenzspektrum
Ei
diskrete
Abtastwertfolge
Codierer
ω
z−Ebene
B
2B
Bandgrenze
AT−Frequenz
Hz
Definition
1. Das Spektrum Fω ist 2π-periodisch
Ist f = [fk ] eine Abtastwertfolge, so heißt
2. Nach Abtastung mit 2B Hertz repräsentiert Fω die Spektralinformation
für ω · B/π Hertz
F (e i ω ) = Fω =
+∞
X
fk · e −i ωk
3. Für reellwertige [fk ] sind Fω , F−ω konjugiert komplex
k=−∞
4. Die Fourierkoeffizienten sind komplexe Zahlen
die Fouriertransformierte von f und
Z +π
1
f˜k =
F (e i ω ) · e i ωk dω
2π −π
Fω = Aω · e i φω = |Fω | · e i arg Fω
5. Reelle Funktionen besitzen bei ω die Schwingungskomponente
Fω · e 2i ωBx + F−ω · e −2i ωBx = 2Aω · cos(2Bωx + φω )
die Rücktransformierte; die Summe heißt Spektralzerlegung der Folge.
Aufgabe
Schall
Licht
Abtastung
Quantisierung
Binarisierung
Codierer
Zusammenfassung (2)
1. Die Vorverarbeitung eines Musters besteht aus Diskretisierung und
Transformation.
2. Schall ist ein Gemisch aus reinen Sinustönen mit frequenzabhängigem
Lautstärkeeindruck.
3. Farbiges Licht ist ein Gemisch aus monochromen Anteilen mit
frequenzabhängigem Helligkeitseindruck.
4. Trotzdem läßt sich jede Farbe wahrnehmungstreu durch nur drei
Primärfarbkoordinaten repräsentieren.
5. Die Abtastung eines Musters ist informationsverlustfrei, wenn mindestens
mit der doppelten Nyquistfrequenz gearbeitet wird.
6. Beim linearen Quantisierer verbessert sich der Signal-Rausch-Abstand
um 6 dB je aufgewendetem Darstellungsbit.
7. Die Binarisierung eines Grauwertbildes dient der Trennung von Objekt
und Hintergrund.
8. Die optimale Grauwertschwelle wird automatisch auf Grundlage des
Grauwerthistogramms bestimmt.
9. Der Freeman-Code wird zur Repräsentation von Linienmustern oder
Objektkonturen genutzt.
R
Σ
R
Σ
© Copyright 2024 ExpyDoc
