close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

Kapitel 2 Was ist Mustererkennung? - LMB

EinbettenHerunterladen
Was ist Mustererkennung?
Mustererkennung ist die Theorie der bestmöglichen
Zuordnung eines unbekannten Musters oder
Beobachtung zi zu einer Bedeutungs- oder
Äquivalenzklasse j (Klassifikation).
Kapitel 2
Eine Äquivalenzklasse besteht aus einer Menge von Mustern {xi} und
einer zweistelligen Verknüpfung (Äquivalenzrelation) mit den
folgenden drei Eigenschaften:
Grundlagen der Mustererkennung
a)
xi~xi
reflexiv (jedes Element ist zu sich selbst äquivalent)
b)
xi~xj Ÿ xj~xi
c)
(x~y)&(y~z) Ÿ x~z
symmetrisch
transitiv
xi~xj : d.h. xi ist äquivalent zu xj in Bezug auf die Relation ~
H. Burkhardt, Institut für Informatik, Universität Freiburg
ME-I, Kap. 2a
1
Relevante and irrelevante Änderungen in
Signalen und Bildern
1D
H. Burkhardt, Institut für Informatik, Universität Freiburg
H. Burkhardt, Institut für Informatik, Universität Freiburg
ME-I, Kap. 2a
2
Bedeutungs- oder Äquivalenzklassen
2D
Äquivalenzklassen können durch zwei Arten definiert werden,
nämlich
1) Angabe aller Repräsentanten von , da die Veränderungen
nicht systematisch formuliert werden können, oder:
2a) Durch ein erzeugendes Element x0 und eine
mathematische Gruppe (Abgeschlossenheit der Daten)
2b) Abgeschlossene Abbildung mit anschließender Abbildung
auf einen Unterraum (Projektion, Okklusion),
z.B. Bewegung eines 3D-Objektes im Raum mit
anschließender Projektion auf die Kameraebene
ME-I, Kap. 2a
3
H. Burkhardt, Institut für Informatik, Universität Freiburg
ME-I, Kap. 2a
4
Beispiel für 1):
Die Menge aller handgeschriebenen
Buchstaben oder Ziffern:
Äquivalenzklasse
für den Druckbuchstaben A
Hier ist eine parametrische Beschreibung der
Äquivalenzklasse praktisch unmöglich.
H. Burkhardt, Institut für Informatik, Universität Freiburg
ME-I, Kap. 2a
5
H. Burkhardt, Institut für Informatik, Universität Freiburg
ME-I, Kap. 2a
6
ME-I, Kap. 2a
7
H. Burkhardt, Institut für Informatik, Universität Freiburg
ME-I, Kap. 2a
8
Beispiel für 2a: Geometrische Transformationen
ZentralProjektionen
(8 FG)
Affine
Abbildungen
(6 FG)
(paralleltreu)
Ähnlichkeiten
(4 FG)
(winkeltreu)
H. Burkhardt, Institut für Informatik, Universität Freiburg
Kongruenzen
(3 FG)
Translationen
(2 FG)
Beispiel für 2b: Bewegung im Raum (Translation und Rotation)
mit anschliessender Abbildung auf einen Unterraum;
unvollständige Beobachtungen
Geometrische Transformationen
Zentralprojektionen
(8 FG)
Affine Abbildungen
(6 FG)
Ähnlichkeiten
(4 FG)
(erhält Parallelitäten)
(erhält Winkel)
H. Burkhardt, Institut für Informatik, Universität Freiburg
Kongruenzen
(3 FG)
Translationen
(2 FG)
ME-I, Kap. 2a
9
Def.: Eine algebraische Struktur mit einer zweistelligen inneren
Verknüpfung x heißt Gruppe, wenn für beliebige Elemente
a,b,c folgende Gesetze gelten:
1) ax(bxc)=(axb)xc
assoziativ
2) Es existiert ein Einselement e, mit
axe=exa=a
a
3)
Zu jedem a gibt es ein inverses Element a-1, mit:
axa-1= a-1xa=e
Aus 1)-3) folgt, daß es genau ein Einselement und zu jedem a
genau ein inverses Element a-1 gibt.
Für eine abelsche Gruppe gilt die Kommutativeigenschaft:
axb=bxa
a,b
ME-I, Kap. 2a
ME-I, Kap. 2a
10
Beispiel für 2a):
Die Gruppe (p) der geometrische Abbildungen, welche die
Bewegung von Objekten, einschließlich projektiver Abbildungen
charakterisieren. Man erhält eine Äquivalenzklasse durch Angabe
eines erzeugenden Elementes x0 sowie einer Bewegungsgruppe,
welche auch parametrisiert mit dem Vektor p beschrieben werden
kann. Dies kann z. B. die Gruppe der ebenen (Euklidschen)
Bewegungen (Translation und Rotation):
Gruppe
H. Burkhardt, Institut für Informatik, Universität Freiburg
H. Burkhardt, Institut für Informatik, Universität Freiburg
(x 0 ) : {gi (x 0 ) | gi  }
Für zwei Objekte x,y der selben Äquivalenzklasse gilt demnach:
x y œ gi  :x
11
H. Burkhardt, Institut für Informatik, Universität Freiburg
gi ( y )
ME-I, Kap. 2a
12
Affine Transformation bzgl. der
zweidimensionalen Koordinaten t=(t0,t1):
Die affine Abbildung
t' At a
6 Freiheitsgrade
t' At a
mit:
A=I
ATA=I
ATA=kI
det(A)z0
die Gruppe der Translationen
die Gruppe der Kongruenzen
die Gruppe der Ähnlichkeiten
die Gruppe der affinen Abbildungen
,
+
(dim(p)=2)
(dim(p)=3)
(dim(p)=4)
(dim(p)=6)
lineare (homogene) Abbildungen
affine Abbildungen
Affine (schiefwinklige) Koordinaten, als Verallgemeinerung
der kartesischen
H. Burkhardt, Institut für Informatik, Universität Freiburg
ME-I, Kap. 2a
13
H. Burkhardt, Institut für Informatik, Universität Freiburg
ME-I, Kap. 2a
14
Die Gruppe der Translationen , als abgeschlossene Operation
Die Gruppe der Translationen , für kontinuierlich definierte
Signale und Bilder
Auf unendlich ausgedehnten Koordinaten lässt sich die Translation natürlich als
abgeschlossene Operation definieren. Die Abgeschlossenheit ist erforderlich, damit nicht
Elemente bei der Operation verschwinden und andere hinzukommen. Man verlangt:
Die Menge der Translationen {W} bilden hinsichtlich der Verknüpfung durch
Zusammensetzung W1(W2(...))=(W1x W2)(...) eine abelsche Gruppe.
x X } ü(x) X
ü G
2D
1D
t2
Die Abgeschlossenheit der Daten bei einer Translation, angewendet auf
Signale oder Bilder, welche nur auf einem endlichen Bereich definiert sind
(Signal- oder Bildfenster), erreicht man durch zyklisches Verschieben.
Übertragen auf unendlich ausgedehnte Koordinaten ließe sich dies auch
durch eine periodische Fortsetzung eines endlichen Definitionsbereichs oder
Fensters erreichen.
A
A
t
x(t 0) = x(t à a)
t1
X (t1c, t 2c ) X ( t )
X (t1c a1 , t 2c a 2 )
H. Burkhardt, Institut für Informatik, Universität Freiburg
Kompakte Gruppe: die die Gruppe beschreibenden Parameter sind auf einen
endlichen Bereich begrenzt!!
X (t a )
ME-I, Kap. 2a
Eine mathematische Gruppe garantiert die Abgeschlossenheit, da ein
inverses Element exisitiert!
15
H. Burkhardt, Institut für Informatik, Universität Freiburg
ME-I, Kap. 2a
16
Die Gruppe der Translationen , für abgetastete
endliche Signale und Bilder
Die 2D-Translation kann in zwei 1D-Translationen
faktorisiert werden (Zeilen/Spaltenpermutation):
Abgetastete endliche Muster:
x := {xi}
X := {Xi,j}
i = 0, á á á, N à 1
i, j = 0, á á á, N à 1
üp,r = üp ï ür = ür ï üp
Translation als zyklische Permutation:
ük(x) := {x(i+k)modN} = {x<i+k> N}
ük,l(X) := {X<i+k> M,<j+l> N}
Beispiel:
10
1
2
3
4
14
5
6
7
8
A=
} ü2,1(A) = 2
9 10 11 12
6
13 14 15 16
11 12
15 16
3
4
7
8
9
13 1
5
H. Burkhardt, Institut für Informatik, Universität Freiburg
ME-I, Kap. 2a
17
Spaltenpermutation
ü 1,1(A) = P AP
bzw: ü p,r(A) = (P ) AP
p T
t' At a
Die Permutationsmatrix ist
orthogonal und somit gilt:
So zum Beispiel
für N=4:
ò
Pà1 = PT
0
0
P=
0
1
18
Die Gruppe der Kongruenzen entstehen durch Translation und Rotation,
was man auch mit Euklidscher Bewegung bezeichnet.
r
Zeilenpermutation
ME-I, Kap. 2a
Die Gruppe der Kongruenzen für kontinuierlich
definierte Bilder
Die zyklische Permutation von Zeilen und Spalten einer
Bildmatrix mit Hilfe von Permutationsmatrizen:
T
H. Burkhardt, Institut für Informatik, Universität Freiburg
1
0
0
0
H. Burkhardt, Institut für Informatik, Universität Freiburg
0
1
0
0
A=
0
0 mit: P 0 = P 4 = I
1
0
ME-I, Kap. 2a
cos() sin()
à sin() cos()
ó
;
a6=0
Die Drehmatrix A ist orthogonal und es gilt:
A à1 = A T sowie: det(A) = 1
19
H. Burkhardt, Institut für Informatik, Universität Freiburg
ME-I, Kap. 2a
20
Die Gruppe der Ähnlichkeiten + für kontinuierlich
definierte Bilder
Z. Bsp.: stauchen und verschieben
eines eindimensionalen Signals
Die Gruppe der Ähnlichkeiten entsteht durch Verschieben, Drehen und
Stauchen:
x(t)
t' At a
ò
A=k
cos() sin()
à sin() cos()
x(t´)=x(kt-a)
ó
;
a6=0, k6=0
Daraus folgt:
AAT = k2I sowie: det(A) = k2
Sowie:
A à1 = k12A T
Z. Bsp. Defekt an einem rotierenden Teil
(z.Bsp. Einer Turbinenschaufel) bei
unterschiedlicher Drehzahl (oder sogar
zeitvarianter Drehzahl (siehe unten).
H. Burkhardt, Institut für Informatik, Universität Freiburg
ME-I, Kap. 2a
21
Allgemeinere Äquivalenzklassen:
Beliebige Zeitmodulationen
x(t´)=x(f(t))
t´=f(t)
t
22
• z. Bsp.: unterschiedliche Sprechergeschwindigkeit bei der
Spracherkennung oder variierende Tempi bei der
Musikerkennung
• Dieser Fall ist schwieriger als das Beispiel mit der
Turbinenschaufel, da man ja dort einen Drehzahlmesser
anbringen könnte und die Zeitschwankungen korrigieren
könnte
t´
x(t´)=x(f(t))
ME-I, Kap. 2a
Allgemeinere Äquivalenzklassen:
Beliebige Zeitmodulationen
f(t) monoton (Kausalität, Zeit
läuft nicht zurück),
aber sonst beliebig
x(t)
H. Burkhardt, Institut für Informatik, Universität Freiburg
t
Ähnlichkeiten im Sinne einer verallgemeinerten Metrik!
H. Burkhardt, Institut für Informatik, Universität Freiburg
ME-I, Kap. 2a
23
H. Burkhardt, Institut für Informatik, Universität Freiburg
ME-I, Kap. 2a
24
Document
Kategorie
Gesundheitswesen
Seitenansichten
2
Dateigröße
426 KB
Tags
1/--Seiten
melden