3D-Punktkorrelation auf Basis von 2D-Bildern auf einer ... · P r o j e k t i v e T r a n s f o r m a t i o n Interpolation Interpolation Interpolation Interpolation Interpolation

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


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


Folie 4 von 34

1 Einleitung

• Implementierung der 3D-Punktkorrelation auf dem FPGA

• Erstellung einer Programmbibliothek für Linux

• Evaluierung unter relevanten Parametrierungen

Aufgabenstellung


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]


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


Folie 7 von 34

2 Grundlagen


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


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]


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


Folie 11 von 34

3 FPGA EntwurfÜberblick

Bildcache

externerDRAM

Rektifizierung

Zeilen-cache

Punkt-suche

DRAMSteuerlogik

Kommunikationsinterface

Normali-sierung

Host


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


Folie 13 von 34






Folie 14 von 34






Folie 15 von 34






Folie 16 von 34






Folie 17 von 34






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


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)


Folie 20 von 34


• Suche homologe Punktpaare mit maximaler Korrelation• Zur Erinnerung:


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)


Folie 21 von 34


• Suche homologe Punktpaare mit maximaler Korrelation• Zur Erinnerung:


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)


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


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.


Folie 24 von 34


Folie 25 von 34

AnhangRektifizierung

Proje

ktiv

e Tra

nsf

orm

atio

n

Interpolation

Interpolation

Interpolation

Interpolation

Interpolation

Bildcache


Folie 26 von 34

AnhangRektifizierung


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


Folie 28 von 34

Normalisierung

Anhang

Sub

Mult

Akkumulator

FIFO

Register<1>

Muxgleich Null?

Mult

MultMult

Sub

Add

Register<2>

x2

Iterativ Newton

Mult

“0“

Register<3>

Documents

3D-Punktkorrelation auf Basis von 2D-Bildern auf einer ... · P r o j e k t i v e T r a n s f o r m a t i o n Interpolation Interpolation Interpolation Interpolation Interpolation