Fitting einfacher geometrischer Modelle - TU Dresden · Fitting einfacher geometrischer Modelle 3/... Einleitung Definition Fitting: Einpassen mathematisch beschriebener, geometrischer

SS/09 Proseminar Aufgabenstellungen der Bildanalyse und Mustererkennung

Fitting einfacher geometrischer Modelle 1/...

Fitting einfacher geometrischer Modelle

Linien, Kurven und Transformationsmatrizen



Gliederung

● Einleitung

● Hough-Transformation

● Fitting von Linien mittels eines Maximum Likelihood / Least Squares Ansatz

● Fitting von Kurven

● Schätzen einer Homographie mit Hilfe der Singulärwertzerlegung



Einleitung

Definition Fitting: Einpassen mathematisch beschriebener, geometrischer Figuren wie Linien, Kreise, Ellipsen usw. in eine Familie oder Gruppe von Symbolen / Zeichen / Merkmalen (Token, z.B. aus Edge/Corner - Detektoren)

Allgemeiner:Einpassen von Matrizen, Vektoren oder anderen mathematischen Beschreibungen in einen Satz von Daten.

- Fitting als Segmentierungsprozess, kompakte Repräsentation der relevanten Bildstruktur



Generelle Aufgaben/Probleme beim Fitting

1. Zählen der Strukturen/geom. Figuren

- Anzahl und Art (2 Kreise, 1 Ellipse, 1 Linie)






2. Zuordnung Token Struktur- Annahme: 1. ist bekannt- Token gruppieren und Struktur bestimmen






2. Zuordnung Token Struktur- Annahme: 1. ist bekannt- Token gruppieren und Struktur bestimmen

3. Parameter Schätzung- Annahme: 1. und 2. ist bekannt- für jede Gruppe von Token Parameterwerte der Struktur schätzen, sodass Struktur optimal in Token passt




- 1. und 2. sind generell schwierige Probleme in der Praxis

- 1. Zählen: - Ergebnisse abhängig von Modellwahl

Beispiel mit Linien (Art der Struktur fest): geg: Menge von Punkten ges: Menge von Linien die gut „fitten“

extrem gutes Fitting, mangelnde Repräsentation (zu viele Strukturen gezählt)

Fitting schlechter, Repräsentation besser

Vereinfachtes Beispiel zeigt Schwierigkeiten




- 2. Zuordnung Token Struktur

- riesiger kombinatorischer Suchraum (alle möglichen Gruppen von Token)

- isolierte Token:K-means Clustering oder EM Algorithmus zur Gruppierung

- zusammenhängende Token:- Token mit Nachbarschaftsgraph - inkrementelles Fitting: beruht auf Idee, dass Token durch Qualität des Fitting der Struktur gruppiert werden



Inkrementelles Fitting von Linien

- geg: Pixel aus Kantendetekor mit Nachbarschaftsgraph = Kurve von Pixeln

- beginnend vom Startpixel, sukzessive benachbarte Pixel hinzunehmen u. Linie fitten

- ist Qualität des Fitting zu schlecht, d.h Summe d. Abstände der Pixel zur Linie zu groß → letzten Pixel verwerfen, verworfener Pixel ist neuer Startpixel

- Wiederholen bis keine Kurvenpixel mehr übrig

- Resultat: Gruppierung und Zuordnung der Token(Pixel) zur Struktur(Linie)



























































Gliederung

● Einleitung







Hough-Transformation

- Technik zur Extraktion geometrischer Merkmale (Linien,Kreise,usw.) aus einer Menge von Token

- Problemklasse Parameterschätzung

- Grundprinzip: - Abstimmung/Voting Prozess- für jeden Token t

i : jede geometrische Figur die durch t

i läuft erhält eine Stimme

- geom. Figuren mit vielen Stimmen sind potenzielle Fittings

- konkret für Linien: - für jeden interessanten Pixel p

i: für Linien, die durch p

i laufen, abstimmen

- Linien mit vielen Stimmen passen am besten in die Punkte pi

- Prinzip auf beliebige andere geom. Figuren anwendbar



Hough-Transformation - Linien

- Hough-Transformation für Linien:

- für jeden interessanten Pixel pi=(x

i,y

i): für Linien, die durch p

i laufen, abstimmen

- Linien mit vielen Stimmen passen am besten in die Punkte pi

- Darstellung von Linien im Bildraum: Anstieg/Y-Achsenabschnitt Form: y=f(x)=mx+n

BildraumHough-Raum / Akkumulator

x

y

n

m

?Pixel

Stimmenbehälter/ Anzahl der Stimmen für Linie (m,n)




- Betrachtung eines festen Pixel x,y

- alle Linien die durch x,y laufen:

- im Hough-Raum müssen also Stimmen entlang der Linie (m,n)=( ) akkumuliert werden

- Wiederholen des Prozesses für jeden Pixel x,y

- idealisiertes Beispiel:

f x : y=mxn ⇔ mn:m=−1xn y

x

−1x, yx

x

y

n

m

11

11

1










x

−1x, yx

x

y

n

m

21

11

11

11

1










x

−1x, yx

x

y

n

m

31

11

11

11

11

11

1

11

1










x

−1x, yx

x

y

n

m

31

11

11

11

11

11

1

11

1

Schnittpunkt d. Linien -> Anzahl max. Stimmen -> Fitting

Anz. Stimmen -> Aussage über Anz. der Punkte durch die Linie läuft




- Darstellung der Linie ist problematisch

- z.B. vertikale Linien :

- um alle Linien zu beschreiben: Hough-Raum/Akkumulator unbegrenzt

- Abhilfe schafft diese Darstellung: Linienbeschreibung durch kürzesten Abstand d zum Ursprung dem Winkel zwischen Linie u. Y-Achse

f x : y=mxn

m=∞

m∈[−∞ ,∞] n∈[−∞ ,∞]

d : cos xsin y=d

y=mxn

⇔ y=− 1tan

x dsin

⇔ y=− cos sin

x dsin

⇔cos xsin y=dx

y

d

a

a

n




- Liniendarstellung:

- Hough-Raum/ Akkumulator nun begrenzt: W,H – Bildraumbreite/-höhe

- statts Linien nun Kurven der Form im Hough-Raum

- Prinzip bleibt gleich: - zu festen x,y korrespondiert Kurve im Hough-Raum - jedes Paar m,n der Kurve im Akkumulator beschreibt Linie im Bildraum durch x,y

d : cos xsin y=d

∈[0 ,2] n∈[0,W 2H 2]

x

y

a

d

11

11

1

d =cos xsin y





- Hough-Raum/ Akkumulator nun begrenzt: W,H – Bildraumbreite/-höhe

- statts Linien nun Kurven der Form im Hough-Raum

- Prinzip bleibt gleich: - zu festen x,y korrespondiert Kurve im Hough-Raum - jedes Paar m,n der Kurve im Akkumulator beschreibt Linie im Bildraum durch x,y

d : cos xsin y=d

∈[0 ,2] d∈[0,W 2H 2]

d =cos xsin y

x

y

a

d

11

11

1

Schnittpunkt vieler Kurven→ max. Stimmen→ Fitting



Hough-Transformation - Probleme

- Praktische Probleme beim Fitting:

- Wahl der Rastergröße / Quantisierung des Akkumulators:

- Lösung: Systematisches Ausprobieren

Zu fein: - Fitting genau- Houghlinien von nicht kollinearer Punkten fallen in verschiedene Stimmenbehälter- keine oder viele kleine Stimmenmaxima

x

y

n

m

n

m

x

y

x

y Zu grob: - Fitting ungenau- Houghlinien von Punkten fallen in gleiche Stimmenbehälter- evtl. zu hohe Stimmenmaxima



Hough-Transformation - Probleme

- Praktische Probleme beim Fitting:

- „Phantom“-Fittings

- Stärke der Hough-Transformation: Verbindung weitverteilter Punkte, gleichzeitig eine Schwäche: annähernd uniform verteilte Punkte

(Bildrauschen, Texturen) → viele mögliche Linien („Phantom“-Fitting)

- kann im Akkumulator zu hohen Werten führen, übersteigen evtl. Maxima von gewünschten Fittings

- Lösung: - Belichtung bei Bildaufnahme → kontrastreiche Kanten- Vorverarbeitung: Glättung, Kantendetektoren Texturen verwischen lassen

- Trotz Probleme, Hough Transformation populär in Praxis



Gliederung

● Einleitung







Maximum Likelihood/Least Squares

- Technik zur Parameterschätzung von geometrischen Modellen (Statistik)

- Maximum Likelihood Schätzung:- statistische Untersuchungen oftmals nur Stichproben ( Aufwand)- Kennwerte wie Erwartungswert, Varianz usw. für gesamte stat. Sachverhalt gesucht- welche Kennwerte (→ Verteilung) machen Stichprobe am wahrscheinlichsten- Annahme: Art der Verteilung bekannt

- auf Linien übertragen:Suchen von Kennwerten einer Linie die durch die Stichprobe (Konstellation von Punkten) läuft, bzw. am besten zu den Punkten passt

- Was heißt passen?- Summe der Quadrate der Äbstande der Punkte zur Linie minimal → Least Squares , 2 Verfahren Total Least Squares, Least Squares

- Notwendigkeit eines generativen Modells bei ML Schätzung:- beschreibt Generierung/Verteilung der Punkte um Linie → liefert Ausdruck für die Wahrscheinlichkeit, benötigt für ML Schätzung



Maximum Likelihood/Total Least Squares

Total Least Squares

- Fit-Kriterium:Kürzester Abstand Punkt zur Linie


- Vereinfachung, cos() sin() nichtlineare Funktion- 3 statts 2 Parameter, 1 überflüssig → ergibt Constraint

- Kürzester Abstand Punkt zur Linie:Behauptung:

Beweis:

cos xsin yd=0 ⇒ axbyd=0

a2b2=1⇔a2b2=1

dist u , v =∣aubvd∣ wenn a2b2=1

r

v

distu , v

v=ab r=x−uy−vdist u ,v =∣projv r∣=

∣vr∣∣v∣=∣aubvd∣a2b2




Total Least Squares

- Beweis

r= x−uy−vaxby−d=0 ⇒ y=−a

bx−d

b ⇒ x−ab x−d

b =0−db −1

b −ba x ⇒ −ba ∥L ⇒ −ba .ab=0 ⇒ ab⊥ L ⇒ v=abdist u ,v =∣projv r∣=

∣v r∣∣v∣

=∣a x−ub y−v∣a2b2

=∣ax−auby−bv∣a2b2

=∣−au−bv−d∣a2b2

=∣aubvd∣a2b2

⇒ dist u , v=∣aubvd∣ wenn a2b2=1

r

v

dist

u , v

L

DarstellungAufpunkt/Richtungsvektor




Total Least Squares

- Generatives Modell für ML Schätzung: Punkte entlang Linie gleichverteilt, orthogonal zur Linie normalverteilt

- Einsetzen Abstandsterm in Normalverteilung, Betrag entfällt wegen Quadrierung

f norm x=1

2e−1

2 x−

2

⇒ f normx , y =1

2e−1

2 axbyd

2

=0=2

a=12

a2b2=1

b=12

d=1=2

Aussage über Wahrscheinlichkeit für einen Punkt x,y, dass er auf der Linie a,b,d liegtAbweichung vomErwartungswert⇒ Abstand Punkte zur Linie




Total Least Squares

- Wahrscheinlichkeitsfunktion mehrerer Punkte:

- Prinzip der stochastischen Unabhängigkeit:-für statistisch unabhängige Erreignisse gilt (bei Punkten gegeben)

- auf Wahrscheinlichkeitsfunktionen übertragbar

- bei ML Schätzung wird in den unbekannten der Linie neu interpretiert

f norm x , y=1 2

e−1

2axbyd

2

f norm x1, y1, x2, y2,... , xn , y n=∏i=1

n 1 2

e−1

2ax iby id

2 Aussage über Wahrscheinlichkeit

wie gut die Punkte xi,y

i zur Linie

a,b,d passen

P A∩B=P A∗P B

f norm

L a ,b ,d =∏i=1

n 12

e−1

2axiby id

2

Aussage über Wahrscheinlichkeit wie gut eine Linie a,b,d in die geg. Punkte x

i,y

i passt




Total Least Squares

- Likelihoodfunktion L

- ges: Linie a,b,c die am besten in die Punkte xi,y

i passt → Linie mit maximaler

Wahrscheinlichkeit → Maximum von L(a,b,d) → Extremwertaufgabe

- zuvor mathematische Vereinfachungen an L(a,b,c):

...

L a ,b ,d =∏i=1

n 1 2

e−1

2axiby id

2




Total Least Squares

- Likelihoodfunktion

- Log-Likelihoodfunktion ln(L), monotone Transformation, ln() monoton stetig→ Extrempunkte an selber Stelle→ Stelle des Extrempunkts interresant,

nicht das Ausmaß

L a ,b ,d =∏i=1

n 1 2

e−1

2axiby id

2

=1 2 n

∏i=1

n

e−1

2ax ibyid

2

=1 2 n

e∑i=1

n

−12axiby id

2

=1 2 n

e−

122∑

i=1

n

ax ibyid 2

L loga ,b , d =ln1 2 n

e−

122∑

i=1

n

axiby id 2

=ln1 2 nlne−1

22∑i=1

n

ax iby id 2=ln1 2

n−122∑

i=1

n

ax ibyid 2

=−∑i=1

n

ax iby id 2

2 2 C

e xe y=e x y

ln ab=ln a ln bML-Schätzer




Total Least Squares

- Extremstellen d. Log-Likelihoodfunktion / ML Schätzer bestimmen unter einer Randbedingung → Lagrange Multiplier

- Lagrange Multiplier: Maxima/Minima von multivariaten Funktionen f unter Randbedingung g

- Geometrische Veranschaulichung:

...

L loga ,b ,d =−∑i=1

n

ax iby id 2

22 C a2b2=1




Lagrange Multiplier:

- geg: f(x,y) g(x,y)=0 ges: Extrempunkte von f(x,y) unter g(x,y)=0

- f(x,y) lineare Funktion

x

y

f(x,y)

x

y

f(x,y)






- f(x,y) lineare Funktion, g(x,y) quadratisch g(x,y)=0 → implizite Funktion→ Nulldurchgang beschreibt alle zulässigen x,y (Randbedingung),

in denen f(x,y) maximiert,minimiert wird

x

y

f(x,y)








x

y

f(x,y)








x

y

f(x,y)








x

y

f(x,y)

x

y






- Betrachtung der Gradienten (Vektor partieller Ableitungen von f(x,y) u. g(x,y))- Gradienten zeigen immer in Richtung des größten Anstiegs

x

y

x

y

f(x,y)






- Lösung: Stellen an denen Gradienten gleiche Richtung haben sind Extrempunkteunabhängig der Skalierung der Vektoren

x

y

x

y

f(x,y)

∇ f x , y= ∇ g x , y




Total Least Squares

- Extremstellen d. Log-Likelihoodfunktion / ML Schätzer bestimmen unter einer Randbedingung → Lagrange Multiplier

f : L log a ,b ,d =−∑i=1

n

ax iby id 2

2 2 C g a ,b ,d =0a2b2=1 ⇒ a2b2−1=0

⇒ g a ,b ,d =a2b2−1=0

∇ f x , y , z ,...= ∇ g x , y , z , ...

∇ Llog a ,b ,d = ∇ g a ,b ,d

−12 ∑i=1

n

a x i2b x i y id x i

∑i=1

n

a x i y ib y i2d yi

∑i=1

n

a x ib y id=2a

2b0 ⇒ − 1

2 ∑i=1

n

x i2 ∑

i=1

n

x i yi ∑i=1

n

xi

∑i=1

n

x i y i ∑i=1

n

yi2 ∑

i=1

n

y i

∑i=1

n

x i ∑i=1

n

yi n abd=2a2b0




Total Least Squares

- Extremstellen d. Log-Likelihoodfunktion / ML Schätzer bestimmen unter einer Randbedingung → Langrange Multiplier

- Lösung: 3 Gleichungen + Randbedingung g(a,b,d) = 4 Gl.4 unbekannte a,b,d,l → lösbarLösung enthält Maxima und Minima!

∇ f x , y , z ,...= ∇ g x , y , z , ...

∇ Llog a ,b ,d = ∇ g a ,b , d

−12 ∑i=1

n

x i2 ∑

i=1

n

x i y i ∑i=1

n

x i

∑i=1

n

xi y i ∑i=1

n

y i2 ∑

i=1

n

yi

∑i=1

n

x i ∑i=1

n

y i n abd=2a2b0 ⇒ x2 x y x

x y y2 yx y 1abd=−2n2a

2b0

u=1n∑i=1

n

ui

'Skalierung unwichtig




Total Least Squares

- Extremstellen d. Log-Likelihoodfunktion / ML Schätzer bestimmen unter einer Randbedingung → Langrange Multiplier

- alternativ umformen in Eigenwertproblem

- Lösung: Linie aus Eigenvektoren(a,b) und Eigenwerte egal, Vorsicht: Lösungen können Maxima/Minima sein → nur Maxima sind Fittings

∇ f x , y , z ,...= ∇ g x , y , z , ...

x2 x y xx y y2 yx y 1abd=2a

2b0 ⇒ d=−a x−b y

⇒ a x2b xyd x=2a

a xyb y2d y=2b ⇒ a x

2b xy−a x x−b y x=2aa xyb y2−a x y−b y y=2b

⇒ x2− x x xy−x yxy− x y y2− y yab=ab

u=1n∑i=1

n

ui

Achtung :u v≠uv

∑i=1

n

u i∑i=1

n

v i≠∑i=1

n

ui v i

d=−a x−b y



Maximum Likelihood/Least Squares

Least Squares

- selbe Vorgehensweise wie ML/Total Least Squares

- Unterschied: - mathematisch simpler, Lösung ohne Lagrange Multiplier- Liniendarstellung y=mx+n- Fit-Kriterium: Abstand Punkt Linie nur in y Koordinate - Generatives Modell: Gauss Rauschen / Normalverteilung nur in Y Richtung,

Gleichverteilung in X

- ML Schätzer

- Problem: - „ärmliches“ Modell , vertikale Linien → unendlich große Abstände→ seltsame Fittings

- nur bedingt geeignet

y=mxnd ⇔ d= y−mx−n ⇒ dist u , v =d= y−mx−n d~N 0,

L logm ,n=−∑i=1

k

y−mx−n2

2 2 C ∇ Llog m ,n=0 y2

y =x2 xx 1mn

u=1n∑i=1

n

ui



Gliederung

● Einleitung







Fitting von Kurven

- Unterschied zu Linien Fitting gering, Ansatz wieder ML Schätzung

- Generatives Modell: Punkte entlang Kurve uniform verteilt, normal/orthogonal zur Kurve normalverteilt

- nur Repräsentation und Distanzbestimmung von Kurven von Interesse

- Fitten von impliziten Kurven:Distanz Punkte zur Kurve liefert Ausdruck für ML Schätzer → Lösung analog

- implizite Kurven, parametrische Kurven



Fitting von Kurven - implizite Kurven

Implizite Kurven:

- beschrieben durch implizite Funktionen , oftmals Polynome

- Bsp: allgemeine Kegelschnittgleichung (höherwertige Polynome unüblich → Stabilität d. Fittings)

x , y=0

x

y

f(x,y)

ax22bxycy22dx2ey f =0

Quelle: http://de.wikipedia.org/wiki/Kegelschnitt




Distanz von Punkten zu impliziten Kurven:

- kürzeste Distanz Punkt (dx,d

y) zu Kurvenpunkt (u,v):

ges: alle u,v für die gilt

- Normalenrichtung, Kurve am schnellsten verlassen

1. u , v=0

2. d x−ud y−v= N u , v ⇔ d x−u

d y−v. T=0

(dx,d

y)

(u,v)

N u , v

N= ∇u , v=∂∂ x u , v ∂∂ yu , v T . N=0 ⇒ T=∂∂ y u , v−∂

∂ xu , v

d x−ud y−v. T=0 ⇒ ∂

∂ yu , v d x−u−

∂∂ xu , vd y−v =0

dist d x , d y=mind x−uid y−v i

x

yf(x,y)

T u , v





- 2 Gleichungen in 2 Unbekannten u,v → lösbar, jedoch analytische Lösungenschwierig

- Anzahl Lös. steigt mit zunehm. Grad der Polynome quadratisch → Approximationen

- algebraische Distanz:

- keine exakte Distanz, Maß, Eigenschaften einer Distanzfunktion- auf Kurve Abstand = 0- orthogonal zur Kurve fällt/steigt Distanz - tangential zur Kurve Abstand gleichbleibend

→ Isolinien

∂∂ yu , v d x−u−

∂∂ xu , vd y−v=0

u , v=0

dist d x , d y=d x , d y

x

yf(x,y)





- algebraische Distanz:

- Problem: d.h implizite Funktionen mit unterschiedl. Parametern beschreiben gleiche

Kurven → Normalisierung der Polynomkoeffizienten

- bei ML/LS:

- 2 approximative Distanz: Normalisieren mitGradientenbetrag → Anstiege in x,y überall 1,

- 1 Schritt in x = Abstand 1→ eigentlich exakte Distanz


x

yf(x,y)

d x , d y =0⇔d x , d y=0

L loga ,b ,d =−∑i=1

n

ax iby id 2

22 C a2b2=1


∣∇d x , d y ∣





- Fazit:

- Analytische Lösungen schwierig

- Approximationen: algebraische Distanz, normalisierte algebraische Distanz

- beide seltsames Verhalten für weit entfernte Punkte , zu große Abweichungen

- algebraische Distanz vorrangig in Praxis, - weniger numerische Probleme - Eignung für höherdimensionale implizite Funktionen

z.B. implizite Flächen



Fitting von Kurven - parametrische Kurven

Parametrische Kurven:

- beschrieben durch 2 Funktionen in t als Komponenten des Kurvenvektors

- sukzessives Einsetzen von Werten zwischen t

min und t

max durchläuft Kurve

- typische parametrische Kurven

C t =x t y t t∈[tmin , tmax ]

∀ t∈[tmin , tmax] : C t Ortsvektor zu Kurvenpunkt

x

y

t

x

t

y

tmin tmax

y0

y1

y0

y1

x0

x0





- Fitting von parametrischen Kurven - Maximum Likelihood / Least Squares - Abstände Punkte zur Kurve minimieren, - Finden der Kennwerte der Kurve, die die Punkte am wahrscheinlichsten durchläuft

- Abstand zu parametrischen Kurven: - kürzeste Distanz Punkt (d

x,d

y) zu Kurvenpunkt

- Vektor Punkt zu Kurvenpunkt = Kurvennormale bzw. Vektor Punkt zu Kurvenpunkt orthogonal zur Kurventangente

- möglich: Punkt weit entfernt von Kurve → Abstand zum Anfang/Ende der Kurve

minimal


C

(dx,d

y)N

C

T





- Abstand zu parametrischen Kurven: - kürzeste Distanz Punkt (d

x,d

y) zu Kurvenpunkt

- 1 Gleichung, 1 Unbekannte → lösbar, Nullstellen


T=∂∂ t x ∂∂ y

y d x− x d y− y . T=0

⇒ ∂ x∂ td x− x −

∂ y∂ t d y− y =0

C

∈[tmin , tmax]

∈[tmin , tmax] ⇒ dist d x , d y =min∣d−C i∣=min∣d x−x id y− y i∣

∉[ tmin , tmax] ⇒ dist d x , d y=min∣d−C tmin∣,∣d−C tmax∣

(dx,d

y)N

C

T





- Fazit:

- oftmals große Anzahl an Nullstellen / Lösungen

- Kurven mit unterschiedl. Parametern/Koeffizienten beschreiben evtl. gleiche Kurven

- Distanzbestimmungsproblem abh. von Klasse der parametr. Kurve

- parametr. Kurven unpopulär


x t y t t∈[0,1] ⇔ 2x t 2yt t∈[0, 1

2]



Gliederung

● Einleitung







Homographieschätzung

Schätzen einer Homographie mit Hilfe der Singulärwertzerlegung

Beispiel: - Aufnahme Kalibrierfeld (Schachbrettmuster)- Koordinaten der Ecken X

i ,Y

i ,Z

i

des Schachbretts bekannt (im Objektkoordinatensystem)- Ecken im Bild x

i ,y

i messbar

(Hough-Transformation) → Punktkorrespondenzen- Bezug zwischen Objekt- und Bildraum durch Korrespondenzen herstellbar: → Transformationsmatrix → Aufnahmesituation

reproduziert, Kalibrierung

Nachteil: - Kalibrierfeldpunkte müssen bekannt sein, - dürfen nicht in einer Ebene liegen

xy1=M⋅ XYZ1 M=P⋅R⋅T





Besser: - mehrere Aufnahmen eines ebenen Kalibrierfelds- Koordinaten X

i ,Y

i ,Z

i unötig

- Ecken in Bildern xi ,y

i messen

→ nur noch 2D Punktkorrespondenzen

- Bezug zwischen beiden Aufnahmen herstellbar:

→ Homographie H (Abbildung proj. Ebene auf Ebene

mit 2D Punktkorrespondenzen)

xy1=M⋅ XYZ1 x 'y '1 =M '⋅XYZ1 M −1xy1=M ' −1x 'y '1 xy1=H

x 'y '1

M=P⋅R⋅T

H=M⋅M ' −1=P⋅R⋅T⋅T ' −1⋅R ' −1⋅P ' −1





- geg: xi ,y

i , x'

i ,y'

i

- Homogene Koordinaten, da Projektion nicht linear Lochkameramodell: Division durch Tiefe (nicht linear)

- Matrixschreibweise nicht mögl. - Abhilfe homogene Koordinaten - zusätliche Dimension,

w Komponente:für Vektoren 0, Punkte 1 (Vektoren werden nicht transliert)

Homogener Raum → euklidischer Raum

xy1=H x 'y '1

x= f XZ

y= f YZ

xhyhw =f 0 0 00 f 0 00 0 1 0XYZ1 = fXfYZ

Quelle: Multiple View Geometry in Computer Vision x=xhw= f X

Z y=

y hw= f Y

Z





- geg: xi ,y

i , x'

i ,y'

i

- 2 Punkte sind gleich wenn Kreuzprodukt 0

x iy i1 =H x i 'y i '1 ⇔ x iy i1 ×H

x i 'y i '1 =0 ∣u×v∣=∣u∣∣v∣sin

x iy i1 ×h1 h2 h3

h4 h5 h6

h7 h8 h9x i 'yi '1 =0 x iy i1×

h1 x i 'h2 y i 'h3

h4 x i 'h5 yi 'h6

h7 x i 'h8 y i 'h9=0

h7 x i ' y ih8 y i ' y ih9 y i−h4 x i '−h5 y i '−h6

h1 x i 'h2 yi 'h3−h7 x i ' x i−h8 yi ' x i−h9 x ih4 x i ' x ih5 yi ' x ih6 x i−h1 xi ' yi−h2 y i ' y i−h3 yi=0





- geg: xi ,y

i , x'

i ,y'

i

h7 x i ' y ih8 y i ' y ih9 yi−h4 xi '−h5 y i '−h6

h1 xi 'h2 y i 'h3−h7 x i ' x i−h8 y i ' xi−h9 x ih4 x i ' x ih5 y i ' x ih6 x i−h1 x i ' y i−h2 yi ' yi−h3 y i=0

0 0 0 −xi ' −y i ' −1 x i ' y i yi ' yi y ixi ' yi ' 1 0 0 0 −x i ' xi − yi ' x i −x i

−x i ' y i −y i ' y i −y i x i ' x i yi ' x i x i 0 0 0 h1

h2

h3

h4

h5

h6

h7

h8

=01.Zeile⋅−xi2.Zeile⋅−y i=3.Zeile lineare Abhängigkeit /Rang 2





- geg: xi ,y

i , x'

i ,y'

i

- homogenes Gleichungsystem , für jede Korrespondenz 2 Gleichungen- A ist 2*Nx9 Matrix

- Problem: - triviale Lösung → Normalisierung - A überbestimmt, nicht invertierbar (Pseudoinverse, bestmögliche Inverse)

0 0 0 −x i ' − y i ' −1 xi ' yi y i ' y i y ixi ' y i ' 1 0 0 0 −x i ' x i −y i ' xi −x i

h1

h2

h3

h4

h5

h6

h7

h8

=0 ⇔ A⋅h=0

h=0 ∣h∣=1





- homogenes GS unter im Least Squares Sinne lösen,d.h unter minimieren → Singulärwertzerlegung von A, Singulärvektor korrespondierend zum kleinsten

Singulärwert ist Lösung der Homographie (Kameraparameter, Relative Orientierung)

- Singulärwertzerlegung von A in - orthonormale Matrizen U,V ( normierte Singulärvektoren bilden Basis, stehen

orthogonal aufeinander, linear unabhängig ) - Diagonalmatrix D ( Diagonalelemente Singulärwerte, Rest 0)

- Eigentwertzerlegung für M=ATA in Matrix P mit orthonormalen Eigenvektoren u. Diagonalmatrix S ( Diagonalelemente Eigenwerte)

→ liefert Singulärvektoren in V und Singulärwerte in D

∣h∣=1A⋅h=0

A=U⋅D⋅V T U⋅U T= I V⋅V T=I

AT⋅A=U⋅D⋅V T T⋅U⋅D⋅V T=V⋅D⋅UT⋅U⋅D⋅V T=V⋅D 2⋅V T

A⋅AT=U⋅D 2⋅U T

∣A⋅h∣ ∣h∣=1

M=P⋅⋅P−1 ⇒ V=P D 2=

mxn mxm mxnnxn= . .

quadratisch

h

i2=i⇔ i=h=vi i=minii





Warum ist Singulärvektor v zum kleinsten Singulärwert s eine Lösung fürunter bzw. warum minimiert er unter ?

- Singulärwertproblem ist verallgemeinertes Eigenwertproblem,Abbildunng Singulärvektoren v durch A auf Singulärvektoren u einerAnderen Basis

da orthonormal, Länge 1, kleinster Singulärwert →

- SVD also universiell zur Lösung von überbestimmten homogenen GS

∣h∣=1A⋅h=0

M=P⋅⋅P−1 ⇐ M v=v A=U⋅D⋅V T ⇔ Av=u

∣A⋅h∣ ∣h∣=1

u ,v u≈0

Av=u ⇒ Av≈0 ⇒ h=v



Literatur



Danke für die Aufmerksamkeit !



Fragen ?

Documents

Fitting einfacher geometrischer Modelle - TU Dresden · Fitting einfacher geometrischer Modelle 3/... Einleitung Definition Fitting: Einpassen mathematisch beschriebener, geometrischer