Verteidigung zur Diplomarbeit
Fakultät Informatik, Institut für Technische Informatik, Professur für VLSI Entwurfssysteme, Diagnostik und Architektur
Dresden, 12.12.13
Simon [email protected]
3D-Punktkorrelation auf Basis von2D-Bildern auf einer FPGA-Plattform
TU Dresden, 12.12.13 Berechnung der 3D-Punktkorrelationauf hochparallelen Plattformen
Folie 2 von 34
Gliederung
1 Einleitung
2 Grundlagen
3 FPGA Entwurf
5 Ergebnisse
6 Diskussion
TU Dresden, 12.12.13 Berechnung der 3D-Punktkorrelationauf hochparallelen Plattformen
Folie 3 von 34
1 Einleitung
• 3D Scanning: viele Verfahren• Beispielanwendungen Computer Vision: Kinect, autonome Navigation
• Kooperation mit Wissenschaftlern vom Institut für angewandte Optik,Friedrich Schiller Universität Jena
• Optische Hochpräzisions-3D-Vermessung
• Großer Beleg: Analyse Hardwarebeschleunigungspotential
TU Dresden, 12.12.13 Berechnung der 3D-Punktkorrelationauf hochparallelen Plattformen
Folie 4 von 34
1 Einleitung
• Implementierung der 3D-Punktkorrelation auf dem FPGA
• Erstellung einer Programmbibliothek für Linux
• Evaluierung unter relevanten Parametrierungen
Aufgabenstellung
TU Dresden, 12.12.13 Berechnung der 3D-Punktkorrelationauf hochparallelen Plattformen
Folie 5 von 34
2 Grundlagen
• Pixelgenaue Tiefeninformation• keine Approximation von Objektkanten
(Bild)
• Fensterkorrelation schon in Hardware implementiert
• Neuentwicklung: Punktkorrelation
Motivation
Fensterkorrelation
Punktkorrelation
[2]
[2]
TU Dresden, 12.12.13 Berechnung der 3D-Punktkorrelationauf hochparallelen Plattformen
Folie 6 von 34
2 Grundlagen
• 2 Kameras (8bit Grauwerte)• Projektion zeitveränderlicher
statistischer Muster• Laser-Speckles (Bild)• Diaprojektor
• Aufnahme und Auswertung einer Sequenz von Stereobildern:„Stereobildsequenz“
Aufbau
LaserKamera 1
Messvolumen
Kamera 2
Messobjekt
TU Dresden, 12.12.13 Berechnung der 3D-Punktkorrelationauf hochparallelen Plattformen
Folie 7 von 34
2 Grundlagen
TU Dresden, 12.12.13 Berechnung der 3D-Punktkorrelationauf hochparallelen Plattformen
Folie 8 von 34
2 Grundlagen
• Suche nach homologen Punkten• Pixel im linken und rechten Bild
zeigen selben Objektpunkt• Berechnung mittels normalisierter
Kreuzkorrelation ρ• ρ liegt zwischen -1,0 und 1,0• Zwei Punkte sind homolog, wenn ρ
> 0,8• Objektpunkt nur von einer Kamera
sichtbar Schwellwert→
wird nicht erreicht
• Triangulation
Basisalgorithmus
Pixel (x, y) Pixel (x‘, y‘)
Kamera 1 Kamera 2
TU Dresden, 12.12.13 Berechnung der 3D-Punktkorrelationauf hochparallelen Plattformen
Folie 9 von 34
2 Grundlagen
• Punktsuche im ganzen Bild dauert sehr lange
• Beschränkung auf Epipolarlinien bei bekannten Kameraparametern
• Rektifizierung zur Verbesserung der Cachenutzung und Pipelinebarkeit der Speicherzugriffe (Burst-Zugriff)
Verbesserung der Performance
[3]
TU Dresden, 12.12.13 Berechnung der 3D-Punktkorrelationauf hochparallelen Plattformen
Folie 10 von 34
2 Grundlagen
• Rektifizierung
• Punktkorrelation• Normalisierung• Punktsuche
• Triangulation
Zusammenfassung des Algorithmus
ρx , y , x ' , y '=∑s=1
N
(gx , y ,s−gx , y)⋅(gx' , y' , s−gx' , y')
√ ∑s=1
N
(gx , y , s−gx, y)2⋅√∑s=1
N
(gx ' , y ' , s−gx' , y' )2
TU Dresden, 12.12.13 Berechnung der 3D-Punktkorrelationauf hochparallelen Plattformen
Folie 11 von 34
3 FPGA EntwurfÜberblick
Bildcache
externerDRAM
Rektifizierung
Zeilen-cache
Punkt-suche
DRAMSteuerlogik
Kommunikationsinterface
Normali-sierung
Host
TU Dresden, 12.12.13 Berechnung der 3D-Punktkorrelationauf hochparallelen Plattformen
Folie 12 von 34
• Festkomma-Arithmetik Pipelines
• Projektive Transformation• 3x2 Matrix-Vektor-Multiplikation• Division (Newton-Raphson Verfahren)
• Bikubische Interpolation• 4 horizontale Interpolationen (parallel)• 1 vertikale Interpolation
3 FPGA EntwurfRektifizierung
TU Dresden, 12.12.13 Berechnung der 3D-Punktkorrelationauf hochparallelen Plattformen
Folie 13 von 34
• Festkomma-Arithmetik Pipelines
• Projektive Transformation• 3x2 Matrix-Vektor-Multiplikation• Division (Newton-Raphson Verfahren)
• Bikubische Interpolation• 4 horizontale Interpolationen (parallel)• 1 vertikale Interpolation
3 FPGA EntwurfRektifizierung
TU Dresden, 12.12.13 Berechnung der 3D-Punktkorrelationauf hochparallelen Plattformen
Folie 14 von 34
• Festkomma-Arithmetik Pipelines
• Projektive Transformation• 3x2 Matrix-Vektor-Multiplikation• Division (Newton-Raphson Verfahren)
• Bikubische Interpolation• 4 horizontale Interpolationen (parallel)• 1 vertikale Interpolation
3 FPGA EntwurfRektifizierung
TU Dresden, 12.12.13 Berechnung der 3D-Punktkorrelationauf hochparallelen Plattformen
Folie 15 von 34
• Festkomma-Arithmetik Pipelines
• Projektive Transformation• 3x2 Matrix-Vektor-Multiplikation• Division (Newton-Raphson Verfahren)
• Bikubische Interpolation• 4 horizontale Interpolationen (parallel)• 1 vertikale Interpolation
3 FPGA EntwurfRektifizierung
TU Dresden, 12.12.13 Berechnung der 3D-Punktkorrelationauf hochparallelen Plattformen
Folie 16 von 34
• Festkomma-Arithmetik Pipelines
• Projektive Transformation• 3x2 Matrix-Vektor-Multiplikation• Division (Newton-Raphson Verfahren)
• Bikubische Interpolation• 4 horizontale Interpolationen (parallel)• 1 vertikale Interpolation
3 FPGA EntwurfRektifizierung
TU Dresden, 12.12.13 Berechnung der 3D-Punktkorrelationauf hochparallelen Plattformen
Folie 17 von 34
• Festkomma-Arithmetik Pipelines
• Projektive Transformation• 3x2 Matrix-Vektor-Multiplikation• Division (Newton-Raphson Verfahren)
• Bikubische Interpolation• 4 horizontale Interpolationen (parallel)• 1 vertikale Interpolation
3 FPGA EntwurfRektifizierung
TU Dresden, 12.12.13 Berechnung der 3D-Punktkorrelationauf hochparallelen Plattformen
Folie 18 von 34
Normalisierung
• DRAM Ausgabe liefert 8 Bursts je 6 Pixel
• Parallele Festkomma-Arithmetik Pipelines je Pixel• Mittelwert: Akkumulation und
Konstantenmultiplikation• Inverse Quadratwurzel: iteratives Newton
Verfahren
• Normalisierte Grauwerte weiter zum Zeilencache
3 FPGA Entwurf
nx, y , s=(gx , y ,s−gx , y)
√∑s=1
N
(gx , y, s−gx , y )2
TU Dresden, 12.12.13 Berechnung der 3D-Punktkorrelationauf hochparallelen Plattformen
Folie 19 von 34
Punktsuche und Zeilencache
• Suche homologe Punktpaare mit maximaler Korrelation
• Einfach in Hardware, aber:• hohe Zugriffsparallelität erforderlich
48 Worte je Takt• Speicherorganisation schlecht auf BlockRAM abbildbar
3 FPGA Entwurf
ρx , y , x ' , y '=∑s=1
N
(nx , y , s⋅nx ' , y' , s)
TU Dresden, 12.12.13 Berechnung der 3D-Punktkorrelationauf hochparallelen Plattformen
Folie 20 von 34
Punktsuche und Zeilencache
• Suche homologe Punktpaare mit maximaler Korrelation• Zur Erinnerung:
• Einfach in Hardware, aber:• hohe Zugriffsparallelität erforderlich
48 Worte je Takt• Speicherorganisation schlecht auf BlockRAM abbildbar: Schreibvorgang
3 FPGA Entwurf
ρx , y , x ' , y '=∑s=1
N
(nx , y , s⋅nx ' , y' , s)
TU Dresden, 12.12.13 Berechnung der 3D-Punktkorrelationauf hochparallelen Plattformen
Folie 21 von 34
Punktsuche und Zeilencache
• Suche homologe Punktpaare mit maximaler Korrelation• Zur Erinnerung:
• Einfach in Hardware, aber:• hohe Zugriffsparallelität erforderlich
48 Worte je Takt• Speicherorganisation schlecht auf BlockRAM abbildbar: Lesevorgang
3 FPGA Entwurf
ρx , y , x ' , y '=∑s=1
N
(nx , y , s⋅nx ' , y' , s)
TU Dresden, 12.12.13 Berechnung der 3D-Punktkorrelationauf hochparallelen Plattformen
Folie 22 von 34
• 11 Rekonstruktionen je Sekunde erreichbar• Vergleich Software: 2 Rekonstruktionen• Mit PCIe bis zu 34 Rekonstruktionen
• Ethernet stellt Flaschenhals dar• Teilmodule gut parallelisierbar
• Weitere Beschleunigung durch größere FPGAs möglich
• Verfeinerung der Punktzuordnung (Subpixelrefinement)• schlecht für FPGA geeignet• in Software sehr effizient
5 Ergebnisse
Software Virtex6 mit Ethernet
Virtex6 mit PCIe (geschätzt)
Virtex7 (geschätzt)
0
20
40
60
80
100
120
140
160
1,98
11,34
34,68
139,47
Rekonstruktionen je Sekunde
Hz
TU Dresden, 12.12.13 Berechnung der 3D-Punktkorrelationauf hochparallelen Plattformen
Folie 23 von 34
Quellen
[1] S. Willeke. Untersuchung der Berechnung der 3D-Punktkorrelation auf hochparallelen Plattformen. Großer Beleg, Technische Universität Dresden, Fakultät Informatik, Institut für Technische Informatik, November 2012.
[2] P. Albrecht et al. (1998): „Improvement of the Spatial Resolution of an optical 3-D measurement Procedure“, IEEE Transactions on Instrumentation and Measurement, Vol. 47. No. 1, February 1998.
[3] www2.informatik.hu-berlin.de/cv/index.php?menu=teaching& submenu=overviewteaching&mode=overviewteaching
[4] T. Luhmann. Nahbereichsphotogrammetrie. Grundlagen, Methoden und Anwendun-gen. Herbert Wichmann Verlag, Heidelberg, 2003.
[5] M. Schaffer, M. Grosse, R. Kowarschik. High-speed pattern projection for three-dimensional shape measurement using laser speckles. Applied Optics, 49(18): S 3622–3629, Juni 2010.
TU Dresden, 12.12.13 Berechnung der 3D-Punktkorrelationauf hochparallelen Plattformen
Folie 24 von 34
TU Dresden, 12.12.13 Berechnung der 3D-Punktkorrelationauf hochparallelen Plattformen
Folie 25 von 34
AnhangRektifizierung
Proje
ktiv
e Tra
nsf
orm
atio
n
Interpolation
Interpolation
Interpolation
Interpolation
Interpolation
Bildcache
TU Dresden, 12.12.13 Berechnung der 3D-Punktkorrelationauf hochparallelen Plattformen
Folie 26 von 34
AnhangRektifizierung
TU Dresden, 12.12.13 Berechnung der 3D-Punktkorrelationauf hochparallelen Plattformen
Folie 27 von 34
Normalisierung
Anhang
DRAM Output
1010 10 1010
MAC
10 10 10
Register
Normali-sierung
Zeilencache
MAC
Register
MAC
Register
MAC
Register
MAC
Register
MAC
Register
MAC
Register
MAC
Register
FIFO
Normali-sierung
Normali-sierung
Normali-sierung
Normali-sierung
Normali-sierung
Normali-sierung
Normali-sierung