Optical Flow im Browser - beschleunigt mit WebGL · Inhalt 1. Optischer Fluss mit der Census-Transformation 2. Parallele Implementierung im Browser mit Hilfe von WebGL 3. Demo 4

Optical Flow im Browser - beschleunigt mit WebGL

Michael Moese und Marvin KampfSeminar: Multi-Core Architectures and Programming, SS13

Inhalt

1. Optischer Fluss mit der Census-Transformation

2. Parallele Implementierung im Browser mit Hilfe von WebGL

3. Demo

4. Evaluation

5. Quellen und Referenzen

MAP - SS13 - Michael Moese und Marvin Kampf - Optical Flow - beschleunigt durch WebGL

Inhalt



3. Demo

4. Evaluation


1 Optischer Fluss mit der Census-Transformation

1. Motivation

2. Schritte des Algorithmus

a. Anwendung eines Weichzeichnungsfilters

b. Bildsignatur durch Census-Transformation

c. Vergleich mit Signatur des vorherigen Durchlaufs


1.1 Motivation

Was ist der Optische Fluss?

Vektorfeld, das Bewegungsrichtung und -Geschwindigkeit für jeden Bildpunkt einer Bildsequenz angibt.

Kann verstanden werden als auf Ebene projizierte Geschwindigkeitsvektoren von sichtbaren Objekten

(Quelle: http://de.wikipedia.org/wiki/Optischer_Fluss)


http://de.wikipedia.org/wiki/Optischer_Fluss

Eingabe für den Algorithmus: eine Folge von Bildern

Eingabe für den Algorithmus: eine Folge von Bildern

1.2.a Weichzeichner

Weichzeichnen entspricht Mittelung des Farbwerts eines Pixels mit den gewichteten Farbwerten seiner Umgebung (Tiefpass-Filter):

Resultierender neuer Farbwert: 114 .

1/16 1/8 1/16

1/8 1/4 1/8

1/16 1/8 1/4

120 100 110 115

100 80 110 120

80 60 115 125

60 60 100 110

Filter-Koeffizienten Auszug aus Bilddaten

120 * 1/16 100 * 1/8 110* 1/16

100 * 1/8 80 * 1/4 110 * 1/8

80 * 1/16 60 * 1/8 115 * 1/4

Berechnung

Anwendung eines Weichzeichners

1.2.b Generierung der Signaturen:Census-Transformation

Die Census-Transformation bildet die Umgebung eines Bildpunktes auf einen binären String ab:

Verdeutlicht an einem Beispiel:

Generierung der Signaturen: Census-Transformation

Erweiterung der Transformation um einen Parameter Epsilon:

Dadurch werden nicht nur identische, sondern ähnliche Punkte erfasst:

Bildsignatur - Illustration der Census-Transformation

1.2.c Der optische Fluss

Um den optischen Fluss zwischen zwei Bildern zu bestimmen, wird folgendermaßen verfahren:

1. Signaturberechnung für das 1. Bild2. Signaturdaten werden für die Bewertung des nächsten Bildes

gespeichert3. Signaturberechnung für das zweite Bild4. Für jeden Signaturwert wird in den Signaturen des 1. Bildes nach

Übereinstimmung gesucht5. Jedes so gefundene Paar wird als Vektor dargestellt

Der optische Fluss - dargestellte Vektoren

Inhalt



3. Demo

4. Evaluation



2. Parallele Implementierung im Browser mit WebGL

1. Native Implementierung in JavaScript

2. Beschleunigung durch WebGL

3. Implementierung der Kernel und Methoden

a. grayscale()b. filter()c. generateSignature()d. generateVectors()e. drawVectors()


2.1 Native Implementierung im Browser

● Implementierung des Algorithmus im Browser per JavaScript

● Input-Stream per JavaScript durch Webcam (Stream-API)

navigator.getUserMedia({video: true}, handleVideo, videoError);

● Dank HTML5 simple Anzeigemöglichkeit in einem Canvas

canvas.src = window.URL.createObjectURL(stream);

● Referenz-Implementierung: JavaScript sehr ähnlich zu C++

● Jedoch geringe Performance!

Beschleunigung mit WebGL


2.2 Beschleunigung durch WebGL

Was ist WebGL?

● Shader-basierte 3D-Grafik-Schnittstelle für Webbrowser

● Auf Basis von OpenGL ES 2.0

● Kernel werden in GLSL geschrieben

● Anzeige durch HTML5-Canvas

Was ist GPGL?

● Wrapper for General Purpose Computing with WebGL● API an OpenCL angelehnt

● Übernimmt Routineaufgaben bei der Initialisierung von WebGL, um

General-Purpose-Aufgaben effizient und einfach zu realisieren


2.2 Beschleunigung durch WebGL

Beispiel für Kernel-Ausführung mit GPGL:

1. Initialisierung von GPGL

var gpgl = new GPGL(canvas);

2. Implementierung eines Web-GL-Kernels

var kernel = gpgl.createKernel("void main() { ... }");

3. Übergabe eines Arguments an den Shader

kernel.setArgImage("img_in", gpgl.createImage2D(...));

4. Ausführen des Kernels mit Rückgabe-Parameter

kernel.run(img_out);


2.3 Implementierung der Kernel und Methoden

a. grayscale()

b. filter()

c. generateSignature()

d. generateVectors()


2.3.a grayscale()

Konvertierung eines Eingabebildes (RGBA) in Graustufen● Herausforderung:

● Abbildung einer Iteration der for-Schleife im Shader● Zugriff auf Pixelwert des Bildes

● Javascript:for (var i = 0; i < d_rgba.length; i += 4)

d_gray[i/4] = 0.34 * d_rgba[i] + 0.5 * d_rgba[i + 1] + 0.16 * d_rgba[i + 2];

● WebGL-Kernel:vec4 conv = vec4(0.299, 0.587 , 0.114 , 0.0 );\

float value = dot(texture2D(img_in, global_id_norm), conv);\

gl_FragColor = vec4(value, value, value, 1.0);\


2.3.b filter()

Anwendung eines Weichzeichnungsfilters(Herausforderung: Zugriff auf "fremde" Pixelwerte Schrittweite definieren)

● Javascript:for (var row = 1; row < height -1; ++row)

for (var col = 1; col < width - 1; ++col) {

// row-1 ...

// row c += 2 * data_process[row * width + (col - 1)];

c += 4 * data_process[row * width + col];

c += 2 * data_process[row * width + (col + 1)];

// row+1 ...

d_filt[row * width + col] = c/16; }

● WebGL-Kernel:vec2 step = vec2(1.0, 1.0) / global_size;\

vec4 value = texture2D(img_in, global_id_norm - step) +\

dot(vec4(2.0), texture2D(img_in, global_id_norm + vec2(0, step.y))) +\

texture2D(img_in, global_id_norm + vec2(-step.x, step.y)) +\ ...

gl_FragColor = dot(value,vec4(1.0, 0.0, 0.0, 0.0) ) + vec4(0.0, 0.0, 0.0, 1.0);\


1 2 1

42 2

1 2 1

2.3.c generateSignature()


Erstellen einer Signatur des gefilterten Bildes

● Herausforderung:● Iterationsgrenzen der for-Schleifen abbilden● Definition einer Subroutine (Funktion) im Kernel-Code (kein Problem!)

● Javascript:ctn_t32 = function(...) {...}

... for (var row = 4; row < height - 4; ++row)

for (var col = 4; col < width - 4; ++col) {

... c = ctn_t32(d_filt[(row - 4) * width + (col - 4)], z, c); }

● WebGL-Kernel:float ctn_t32(...) {...}\

int width = int(global_size.x), height = int(global_size.y);\

int col = int(global_id_abs.x), row = int(global_id_abs.y);\

if(row < 4 || row > height -4 || col < 4 || col > width - 4) { //return }\

... c = ctn_t32(texture2D(img_in, global_id_norm - step4), ...);\

2.3.d generateVectors()


Vergleich der vorherigen Signatur mit der aktuellen

● Herausforderung:● 4 verschachtelte for-Schleifen abbilden● Iterations-Schrittweite (i+=2) abbilden

● Javascript:for(var row = (WINDOW_SIZE_Y / 2); row < (height - (WINDOW_SIZE_Y / 2)); row += 2)

for(var col = (WINDOW_SIZE_X / 2); col < (width - (WINDOW_SIZE_X / 2)); col += 2)

for(var row_w = (row - (WINDOW_SIZE_Y / 2)); row_w <= (row + (WINDOW_SIZE_Y / 2)); row_w += 2)

for(var col_w = (col - (WINDOW_SIZE_X / 2)); col_w <= (col + (WINDOW_SIZE_X / 2)); col_w += 2)

● WebGL-Kernel:if(mod(float(col), 2.0) != mod(float(half_window_size_x), 2.0) || ... ) { //return

}\

for(int i = -half_window_size_y; i <= half_window_size_y; i+=2)\

for(int j = -half_window_size_x; j <= half_window_size_x; j+=2) {\

if(sig_last == sig_curr) { // vector found } }\

if( // vector found ) { // return vector coords }\

3. Demo


http://goo.gl/gv3uf

Inhalt



3. Demo

4. Evaluation



4. Evaluation

1. Optimierung

2. Messdaten

3. Ausblick

4. Zusammenfassung der Ergebnisse


4.1 Optimierung

● Anfangs: folgender Rahmen in jedem Schritt des Optical Flow:var img_in = gpgl.createImage2D(width, height, gpgl.Format.UBYTE8888, data1);var img_out = gpgl.createImage2D(width, height, gpgl.Format.UBYTE8888);// Kernel Executionreturn data2 = img_out.readPixels();

● Schlechte Idee!

● createImage2D(..., data1) und img_out.readPixels() bewegen Daten

zwischen Grafikspeicher und Arbeitsspeicher.

Device-Host-Transfer sehr teuer!

Lösung: Globale Variablen, die 2D-Images zwischen den Schritten

referenzieren. Nur finales Auslesen aus dem Grafikspeicher.


4.2 Messdaten


Variante Mittlere FPS2 Speedup3 ≈

JavaScript (nativ) 1.01 1

JavaScript + WebGL (vor Optimierung) 2.69 3

JavaScript + WebGL (nach Optimierung1) 21.31 21

C++ (nicht im Browser) 7.94 8

Testsystem: Intel(R) Core(TM) i5 CPU 760 @ 2.80GHz 3.04 GHz, 8 GB RAM, ATI Radeon HD 6870 mit 1024 MB GDDR5

1) Anzahl an Device-Host-Transfers wurde minimiert.

2) Arithmetisches Mittel nach 30s Anlaufzeit und 60s Messung

3) Speedup nach Formel S = T1 / Tp

4.3 Ausblick

● Weitere Optimierungsmöglichkeit

○ Zwei Bilder innerhalb konfigurierbaren Zeitraums Δt aufnehmen

○ Erst danach Anwendung des Algorithmus auf die beiden Bilder

○ Folgen:■ Unabhängig der Rechenleistung werden Bewegungen erfasst

■ Je nach Δt entfallen besonders schnelle / langsame Bewegungen

■ Analogie:


Tief-/Hochpass-Filterfür Frequenzen

Exklusive Erfassung von Bewegungen bestimmter Geschwindigkeit

4.4 Zusammenfassung der Ergebnisse

● Optical Flow Algorithmus besteht aus den Schritten:Graustufenkonvertierung WeichzeichnungsfilterSignaturberechnung Signaturvergleich Vektoren

● WebGL-Herausforderungen:○ Iterationsraum abbilden○ Zugriff auf Pixelwerte des übergebenen Bildes○ Umgang mit RGBA-Vektoren im Kernel○ Effizienter Umgang mit Device-Host-Transfers

● Speedup von ca. 21 durch WebGL-Beschleunigung● Alternative Herangehensweise: Erst Aufnahme zweier Bilder

innerhalb bestimmter Zeit, dann Anwendung des Algorithmus


Quellen und Referenzen

Oliver Reiche, GPGL, http://bitbucket.org/oreiche/gpgl

Sascha Roloff, Referenzimplementierung OpticalFlow in C++

Marvin Kampf und Michael Moese, Optical Flow (WebGL), http://goo.gl/gv3uf

Khronos Group, WebGL, http://www.khronos.org/webgl/

Fridtjof Stein, Efficient Computation of Optical Flow Using the Census Transform, In: Pattern Recognition, 3175, Springer, Berlin/Heidelberg 2004

https://bitbucket.org/oreiche/gpgl

http://www.khronos.org/webgl/

Dankeschön!

Michael Moese und Marvin KampfSeminar: Multi-Core Architectures and Programming, SS13

Documents

Optical Flow im Browser - beschleunigt mit WebGL · Inhalt 1. Optischer Fluss mit der Census-Transformation 2. Parallele Implementierung im Browser mit Hilfe von WebGL 3. Demo 4