Berechnung der Fourierkoeffizienten von Polygonzügen€¦ · H Burkhardt Institut für Informatik Universität Freiburg ME I Kap 4b 1 Berechnung der Fourierkoeffizienten von Polygonzügen

ME I Kap 4bH Burkhardt Institut für Informatik Universität Freiburg 1

Berechnung der Fourierkoeffizienten von Polygonzügen

Bei Polygonzügen lässt sich das Integral entlang der Geraden explizit lösen und man erhält Formeln mit expliziter Abhängigkeit von den Eckpunkten des Polygons. Bei der Abtastung von Konturen erhält man in der Regel nicht-äquidistante Polygonzüge. Damit ist der Einsatz der schnellen Fouriertrans-formation (FFT, siehe DBV-I) zur Berechnung der FK nicht unmittelbar möglich, bzw. man benötigt eine zusätzliche Interpolation der Daten. Die nachfolgende explizite Formulierung ist in der Regel vorzuziehen, insbesondere, wenn man die Punkte entlang von Geraden eliminiert.

xN=x0

x1=xN+1

x2

x3

xN-1=x4

Im(x)

Re(x)


Durch den abschnittweisen linearen Verlauf zerfällt das Integral in:

11

0

1 ( )

mit: cos( ) sin( )

k

k

tNjn t

nk t

jn t

c x t e dtT

e n t j n t

ω

ω ω ω

+−−

=

−

= ⋅

= −

∑ ∫

Die Interpolation entlang der Polygonabschnitte ergibt:

11

1

( ) ( )

mit:

bzw.: ( ) ( )

k k kk k

k

k kk k

tx t x x xt t

t t ttx t x t x x

t t

++

+

∆= + −

−∆ = −

∆∆ = − = ∆

−Re(x)

Im(x)

xk

tk

xk+1

tk+1

tx(t)


Abschnittweise analytische Integration:

2

2

und:1

( )1 = (1 )

( )

jn t jn t

jn t jn t jn t

jn t

je dt en

jte dt e ten n

e jn tn

ω ω

ω ω ω

ω

ω

ω ω

ωω

− −

− − −

−

=

= +

+

∫

∫


Für die Eckpunkte eines geschlossenen Polygonzugs:

für: modi kx x i k N= ≡

berechnet man die ersten und zweiten Differenzenglieder:

12

1 2 12i i i

i i i i i i

x x x

x x x x x x+

+ + +

∆ = −

∆ = ∆ −∆ = − +

und daraus normierte Differenzen:

21

/i i i

i i i

z x x

z z z+

∆ = ∆ ∆

∆ = ∆ −∆


Der nullte FK gibt die Lage des Linienschwerpunktes an und berechnet sich zu:

1

0 10

1 ( )2

N

k k kk

c x x xT

−

+=

= + ∆∑

Re(x)

Im(x)

1sx

2sx3sx

k km l∼

11

( )12

0

1

1 00

1

1 ( )2

k k k

s kk

k

Ns k x x

s k kkk x l

l T

N

k k kk

x mx x x

m T

x x x cT

+−

++

=

=

−

+=

⋅= = −

∑

= + ∆ =

∑ ∑∑

∑

∼


Alle anderen Fourierkoeffizienten berechnen sich bei nichtäquidistentenStützstellen exakt zu:

21 ( )

120

21 ( )212

0

( )(2 )

(2 )

k

k

N jn tT

n k kk

N jn tT

kk

Tc z z en

T z en

π

π

π

π

− −

−=

− −

−=

= ∆ −∆

= − ∆

∑

∑

Mit den Teilbogenlängen:1

00

0, 0k

k ii

t x k t−

=

= ∆ > =∑

Diese aus den zweiten Differenzen abgeleiteten, charakteristischen Konturgrößen stehen in enger Beziehung zur fundamentalen Kontur-beschreibung mit Hilfe der Krümmung bzw. deren Berechnung mit Hilfe von Differenzenquotienten.


Repräsentation der Kontur durch eine unterschiedliche Menge von Punkten

Von großer praktischer Bedeutung ist die Tatsache, dass als Grundlage der Fourierbeschreibung einer Kontur, die Anzahl und die Lage der Abtastpunkte entlang der Kontur unerheblich ist, solange diese den Verlauf hinreichend genau repräsentieren. In beiden Fällen erhält man annähernd die gleichen FK.

Dabei bietet sich insbesondere an, Zwischenpunkte entlang von Geraden zu unterdrücken!


Die Äquivalenzklasse aller ähnlicher Muster

Für die Gruppe der Ähnlichkeiten ergeben sich als zulässige Veränderungen eines Musters x(t) gegenüber einem Referenzmuster x0(t): 1. eine Translation um den komplexen Wert z, 2. eine Rotation um den Winkel Φ um eine körperfesten Bezugspunkt xB, 3. eine Aufpunktverschiebung um den Wert t0 und 4. eine radiale Streckung um den Faktor R bezüglich xB .

Angewandt auf das Referenzmuster ergibt dies:

x(t) = x0(t+ t0) áR á ejΦ+ z (4.1.5)


Die Äquivalenzklasse aller ähnlicher Fourierkoeffizienten

Die Auswirkungen der Ähnlichkeitstransformation auf die Fourier-koeffizienten ergeben sich wegen der Linearität der Fourier-transformation wie folgt. Deren Berechnung erfolgt unter der Annahme einer auf T = 2π normierten Bogenlänge.

0

00 0

( )0

(4.1.6)

für 0 (4.1.7)

j

j n tn n

c c R e z

c c R e n

Φ

Φ+ ⋅

= ⋅ ⋅ +

= ⋅ ⋅ ≠

Der Fourierkoeffizient c0 gibt lediglich die Lage des Linienschwerpunktes an und ist invariant gegen eine Aufpunktverschiebung. Die anderen Fourierkoeffizienten verändern ihr Argument in Abhängigkeit von Rotation und Aufpunktverschiebung und ihren Betrag in Abhängigkeit von einer zusätzlichen Streckung, sind aber unabhängig von einerTranslation.


Invarianzeigenschaften des Leistungsspektrums

Wie unschwer aus Gl. 4.1.7 hervorgeht, bildet das Amplitudenspektrum der Fouriertransformierten (die Beträge der Fourierkoeffizienten) lageinvariante Merkmale bzgl. der Äquivalenzklasse kongruenter Muster (Euklidsche Bewegung). Allerdings wird damit nur die notwendige Bedingung der Invarianz erfüllt; Vollständigkeit ist nicht gegeben, da beliebige Phasenvariationen unterdrückt werden.

Siehe dazu das Bild mit der Veränderung der Phase bei c1 (Kap. 4c, S. 3).


Ähnlichkeitsinvariante Fourierdeskriptoren

Hier kann im Gegensatz zur Klasse CT ein vollständiger Satz von lage-und vergrößerungsinvarianten Merkmalen (Fourierdeskriptoren) von den Fourierkoeffizienten abgeleitet werden, indem man deren Beträge normiert und ihre Argumente durch eine eindeutige Nebenbedingung fixiert.

Man muss dabei gegenüber den Fourierkoeffizienten zu genau vier Freiheitsgraden, entsprechend den vier angegebenen Veränderungen (R,Φ,t0,z) kommen. Die komplexen Invarianten werden definiert durch folgenden Satz


Satz: Bezüglich der komplexen Musterklasse x∈FN (bandbegrenzte Konturmuster) bilden die komplexen Merkmale

( ){ : } 1, 2, , / 2 (4.2.1a)

- -= =- -

(4.2.1b)Grad der Rotationssymmetrie

n r qjnn

q

cx e n N

c

q n r nr q r q

r q s qs

α β

α β

Φ + Φ − Φ= = ± ± ±

= + ∈

(ausschliesslich und ) einen vollständigen, minimalen Satz von Invarianten in Bezug auf die Gruppe der ebenen Bewegungen (Translation und Rotation) und der radialen Streckung (Gruppe der Ähnlichkeiten), bei einem auf die folgenden Werte normierten Referenzmuster

qx Im( )rx

0 ( )x t0 0

0

0

0

0 ( ) (4.2.1c)(d.h. der körperfeste Bezugspunkt liegt im Koordinatenursprung)

1 (4.2.1d)

0

B s

q

q

x c x

c

= =

=

Φ =0

(4.2.1d)

0 (4.2.1d)rΦ =


Die Menge der Invarianten sind minimal, d.h. streicht man eines derMerkmale, so geht die Vollständigkeit bzgl. der Klasse verloren.Die Minimalität wird auch deutlich daran, dass die Freiheitsgrade

{

NF

0 0

0,

, , ,Re( ),Im( )} genau um die Anzahl der Freiheitsgrade

des Musterraumes { , ,Re( ),Im( )} reduziert werden.q r qc c c

t R z z

Φ Φ

Φ


Beweis:Der Beweis erfolgt konstruktiv, indem alle charakteristischen Größen des

Referenzmusters in eindeutiger Weise aus den Invarianten rekonstruiert werden.

Die eigentliche Schwierigkeit bei der Phasennormierung ergibt sich aus der Phasenmehrdeutigkeit mod(2π); d.h. bei den gemessenen Phasen weiß man nicht wie oft 2π durchlaufen wurde.

Die in (4.2.1c-f) angegebenen Normierungsbedingungen für das Referenzmuster legen genau die vier Freiheitsgrade Lage (z), Größe (R), Orientierung (Φ) und Aufpunktverschiebung (t0) fest.

Für den Betrag der Invarianten ergibt sich aus (4.1.7) und (4.2.1d)

Also eine eineindeutige Beziehung zwischen: 0 und n nx c

|xàn| = |cq||cn|

= |c0q| áR|c0n| áR = |c0n| (4.2.2)


In manchen Anwendungsfällen kann eine Vergrößerungsinvarianz unerwünscht sein (z.B. Qualitätskontrolle). Für diesen Fall können die Beträge einfach definiert werden durch

(4.2.3)n nx c=

Da die Argumente der Fourierkoeffizienten nach (4.1.7) additiv durch die zu-lässigen Veränderungen beeinflusst werden, soll eine allgemeine Linearformzur Eliminierung verwendet werden. Beachtet man, dass alle Argumente der Fourierkoeffizienten eines unbekannten Musters x(t) nur bekannt sind mod(2π), und berücksichtigt man in einem Ansatz für die absoluten Werte ein entsprechend Vielfaches gi von 2π, so erhält man aus (4.2.1a) unter Beachtung von Gl. (4.1.7)

00

00

00

arg( )

2

( 2 )

( 2 ) (4.2.4)

n n r q

n n

r r

q q

x

n t g

r t g

q t g

α β

π

α π

β π

= Φ + Φ − Φ

= Φ +Φ + ⋅ + ⋅

+ Φ + Φ + ⋅ + ⋅

− Φ +Φ + ⋅ + ⋅


Und daraus mit (4.2.1e-f)

00arg( ) (1 ) ( )

2 ( ) (4.2.5)n n

n r q

x t n r qg g g

α β α βπ α β

= Φ +Φ + − + + − ++ + −

Wegen der Invarianz müssen die Faktoren bei Φ und t0 verschwinden:

1 0

0 (4.2.6)n r q

α β

α β

+ − =

+ − =

!

!

Daraus ergeben sich die in (4.2.1b) angegebenen Bedingungen für die Linearfaktoren:

(4.2.7)

q nr qr nr q

α

β

−=

−−

=−

Womit die notwendige Bedingung der Invarianz bereits erfüllt ist.


Die hinreichende Bedingung der Vollständigkeit erfordert jedoch eine einein-deutige Beziehung zwischen den Invarianten und der Referenzphase

Gl. (4.2.7) in (4.2.4) eingesetzt ergibt:arg( )nx 0

nΦ

0 2arg( ) [( ) ( ) ( ) ] (4.2.8)n n n r qx r q g q n g r n gr qπ

= Φ − − + − − −−

Geht ein Muster bei einer Rotation um den Schwerpunkt mit Φ=2π/s in sich selbst über, so liegt eine Rotationssymmetrie vom Grade s vor. Für Rotationswinkel und Aufpunktverschiebung bedeutet das die Äquivalenz von

0 0

mod(2 / ),mod(2 / ) (4.2.9)

st t s

ππ

Φ Φ∼∼

und für die Fourierkoeffizienten folgt daraus, dass nur für bestimmte Indizes ihre Werte von Null verschieden sein können, nämlich

0 für 1 , (4.2.10)nc n k s k≡ ≠ + ⋅ ∈


Macht man damit einen allgemeinen Ansatz für die Indizes r,q und n in (4.2.8), so ergibt sich

1

2 1 2

1 ,1 ,1 , , , (4.2.11)

n K sq K sr K s K K K

= + ⋅= + ⋅= + ⋅ ∈

Eingesetzt in Gl. (4.2.8) ergibt

02 1 1 2

0

arg( ) 2 [( ) ( ) ( ) ]

+2 g, (4.2.12)

n n n r q

n

sx K K g K K g K K gr qs g

r q

π

π

= Φ − − + − − −−

= Φ ⋅ ∈−


lässt sich in Gl. (4.2.12) ein eineindeutiger Zusammenhang zwischen der Referenz- und Invariantenphase herstellen. Gl. (4.2.12) lässt sich eindeutig nach Φn

0 auflösen, und man erhält

Mit der Bedingung von

0 (arg( ))mod(2 ) + (4.2.14)n n n r qx π α βΦ = = Φ ⋅Φ − Φ

(4.2.13)r q s− =

Die Minimalität der Invarianten erkennt man einfach wiederum daran, daß für eine Rekonstruktion eines Musters der Klasse FN i.a. alle Fourier-koeffizienten cn

0 und damit auch alle Invarianten erforderlich sind.

♣


Um eine große Störsicherheit bei der Berechnung der Invarianten zu bekommen, sollte man bei der Wahl der beiden Bezugsgrößen cq, cr darauf achten, die betragsgrößten Fourierkoeffizienten zu verwenden.

Bei gestörten Mustern ist (4.2.10) nicht ideal erfüllt. Als Maß für die Rotations-symmetrie vom Grade s bei gestörten Mustern kann die folgende Summe

1, (4.2.15)n

n ksc k

≠ +

∈∑mit einer zusätzlichen Schwellwertabfrage verwendet werden.

In den meisten Fällen eignet sich der i.a. dominante Fourierkoeffizient c1 zur Normierung (q = 1). Liegt außerdem keine Rotationssymmetrie vor (s = 1), so vereinfacht sich die Berechnung der Fourierdeskriptoren von Satz (4.2.1) zu

2 1( (1 ) (2 ) )

1

{ : } (4.2.16)

wegen1, 1, 2,(1 ), =(2 ) (4.2.1b)

nn j n nn

cx e

c

q s rn nα β

Φ + − Φ − − Φ=

= = == − −


Ermittlung der TransformationsparameterNeben der reinen Klassifikation ist in vielen Fällen auch die genaue Ermittlung

von Lage, Orientierung, Aufpunktverschiebung und Streckungsfaktor von Bedeutung. So z.B. für das gezielte Greifen eines Industrieroboters, wo man zusätzlich den körperfesten Bezugspunkt xB an einen für das Ergreifen günstigen Punkt legen kann.

Die unbekannten Werte erhält man aus den für die Normierung verwendeten Größen der Fourierkoeffizienten (4.2.1c-f). Für die Streckung ergibt sich

(4.2.18)qR c=

Rotationswinkel Φ und Aufpunktverschiebung t0 erhält man aus den Argumenten von cq und cr (vgl. 4.1.7), für deren Absolutwerte entsprechend Gl. (4.2.4) gilt

00

00

2 ,

2 (4.2.19)q q q

r r r

q t g

r t g

π

π

Φ = Φ +Φ + ⋅ + ⋅

Φ = Φ +Φ + ⋅ + ⋅


Daraus lässt sich unter Beachtung der Normierungsbedingungen (4.2.1e-f) (Φq0=

Φr0=0) und der Nebenbedingung r-q=s durch Subtraktion der unbekannte

Aufpunkt ermitteln

0 mod(2 / ) (4.2.20)r qt sr q

πΦ −Φ⎛ ⎞

= ⎜ ⎟−⎝ ⎠

Vergl. Gl. (4.2.9).

Die Rotation erhält man ebenfalls aus (4.2.19) zu

mod(2 / ) (4.2.21)q rr qs

r qπ

Φ − Φ⎛ ⎞Φ = ⎜ ⎟−⎝ ⎠

Aus dem Fourierkoeffizienten c0, welcher die Lage des Schwerpunktes angibt, kann die Translation ermittelt werden

00 0= (4.2.22)j

Bz x c c R e Φ= − ⋅ ⋅

Diese Größen sind alle in Bezug auf das durch Gl. (4.2.1c-f) normierte Referenzmuster zu sehen.


Transformation des Originalraums in eine kanonische Darstellung

Überführung der direkten Objektrepräsentation in die intrinsischen, invarianten Gestaltsparameter „Fourierdeskriptoren“ und die Transformations- oder Bewegungsparameter „Position, Größe und Drehlage“:

x(t) {cn}

Φ,R,z,t0

{ }nxF

T Invarianten

Transformations-parameter

Objektraum Kanonischer Darstellungsraum

Documents

Berechnung der Fourierkoeffizienten von Polygonzügen€¦ · H Burkhardt Institut für Informatik Universität Freiburg ME I Kap 4b 1 Berechnung der Fourierkoeffizienten von Polygonzügen