Ferienakademie 2013 – Kurs 5Multi-Core = Multi-Performance

Sascha Roloff, Frank Hannig, Jürgen TeichFriedrich-Alexander-Universität Erlangen-Nürnberg

Erlangen, 10. Juli 2013

2

Praktischer Teil

● 1. Woche: Vornehmlich Vorträge● 2. Woche: Programmieraufgabe

● Programmieraufgabe● Ziel: Implementierung einer Kette von Bildverarbeitungsalgorithmen in

der Programmiersprache X10

● Bearbeitung in Teams● 2-3 Studenten pro Team● Jedes Team implementiert und testet einen Algorithmus separat

● Integration zu einer Kette● Teams arbeiten gemeinsam an der Integration der Algorithmen● Absprache über Austausch der Datenstrukturen● Testen der gesamten Algorithmenkette

3

Die Anwendung: Objekterkennung

● Typisches Anwendungsszenario aus der Robotik● Roboter erkennt ein Objekt und kann ihm folgen

(object detection, object tracking)

Objekt im Referenzbild

MerkmaleErkanntes Objekt

im SuchbildFehl-

Erkennungen

4

Die Algorithmen

●Harris Corner Detection● Erkennung der Ecken eines Bildes● Verwendung als Merkmale (Features) für nachfolgende Algorithmen

● SIFT Feature Description● SIFT – Scale-Invariant Feature Transform● Umwandlung der Harris Corner Features in SIFT Features

● SIFT Feature Matching● Vergleich der SIFT Features des Suchbildes mit den SIFT Features des

Referenzbildes und Finden des passendsten Kandidaten

CameraImage

Harris Corner Detection

SIFT FeatureDescription

SIFT Feature Matching

Object Location

Object Recognition Algorithm

5

Die Programmiersprache: X10

●Neuartige parallele Programmiersprache von IBM● Syntax: Mischung aus Java und Scala

● Bietet Sprachkonstrukte für Parallelität● Thread-level Parallelität (gemeinsamer Speicher)● Verteilung von Daten (verteilter Speicher)● Synchronisation, Atomarität

public class Test { public static def main(args:Array[String](1)) { finish for(p in Place.places()) async at (p) { Console.OUT.println(„Hello, World from “+here.id); } }}

6

● Implementierung der Algorithmen in X10● Erst sequentiell, dann parallel (wenn genug Zeit vorhanden)

● Kopplung der Algorithmen über eine X10 Task (Aktor) Bibliothek

Implementierung und Integration

Harris Corner Detection in X10

SIFT FeatureDescription in X10

SIFT Feature Matching in X10

func1

func3

func2

channelactor1

activities

channelactor2 actor3

CameraImage

Harris Corner Features

SIFT Features Object Position

7

Die Plattform

● Testen der Algorithmenkette auf einer Simulationsplattform

SIFTDetection

SIFTMatching

Harris Corner

Camera Images

8

Vorbereitungen für die Implementierung

● Laptop mit installiertem Linux● Keine virtuelle Maschine● Linux-spezifische Funktionen für Simulation benötigt

● Testen der Programmiersprache X10 auf eigenem Laptop● Download von der X10 Webseite (x10-lang.org)● Version 2.3.1● Eclipse-basierte Entwicklungsumgebung X10DT (x86, x86_64)● Vorkompilierter Compiler (x86, x86_64)

Detailliertere Beschreibung der Algorithmen

9

Harris Corner

Harris Corner

SIFT Features

Image Source

Edges may have FIFO semantic. Pointers can be exchanged instead of concrete data.

Create corresponding activities for execution on the allocated resources (= claim(actorHarris Corner))

src

sobelX

sobelY

calculateautocorrelation

matrix

get max response

thresholding response sink

…

10

Harris Corner

2)M(tracek)Mdet(R

Eigenvalues of M:

src

sobelX

sobelY

calculateautocorrelation

matrix

get max response

thresholding response sink

1.)

2.)

3.)

11

SIFT Feature Descriptor

keypoints

Harris Corner

SIFT features

image source

img

…

src

sobelX

sobelY

calc angles and magnitudes of

pixels around each keypoint

calc descriptor per keypoint relative to its orientation

sink

img

keypoints

calc orientation(s) per keypoint (additional

orientations = additional keypoints)

based on 36 bin histogram

12

SIFT Feature Descriptor

src

sobelX

sobelY

calc angles and magnitudes of the gradients of pixels

around each keypoint

calc descriptor per keypoint relative to its orientation

sink

img

keypoints

calc orientation(s) per keypoint (additional

orientations = additional keypoints)

Angle and magnitudes of pixel orientations (=gradients) can be obtained based on Sobel X/Y (which form x and y of the gradient)

Histogram with 36 bins (1 bin represents 10 degrees) build upon angles and magnitudes of pixel gradients in region around the keypoint (e.g. 16x16)

Result: maximal orientation; but possibly also further peak orientations new keypoints

descriptor of keypoint relative to its orientation based upon orientations of pixels in 16x16 regions around keypoint collected in 4x4 histograms with 8 bins (128 dimensions)

13

SIFT Feature Matching

src

find nearest neighbor feature in model (represented as

kdTree for fast search) for each SIFT

descriptor

SIFT descriptors filter matches;

only accept good (close) matches

register matches (not on the

feature vector but on the

coordinates); e.g., using RANSAC

sink

Harris Corner

SIFT features

SIFT descriptors

Feature matching

…

…

model

14