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 Suchbild
Fehl-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