Version vom 12. Juni 2016, 18:14 Uhr

Autoren: Christo Tsibadze, Kevin Penner
Betreuer: Prof. Schneider

Aufgabenstellung

Realisierung einer Billard-Assistenz-Software, mit Hilfe von Matlab und dessen Bildverarbeitungs-Tools: Es soll ein "Billard-Assistenz-Software" entwickelt werden, die aus einem Video (oder Live-Cam) Billard Kugel- und Queue -Positionen erkennt und mit einer Algorithmus die Abprallrichtung einer Zielkugel "vorhersagt" (berechnet). Vor dem Schlag soll anhand der Queue- und Kugel-Positionen erkannt werden in welcher Richtung die weiße Kugel geschlagen wird und falls die weiße Kugel einen anderen Kugel trifft, dann in welcher Richtung diese abprallen wird. Die berechnete Richtungen sollen auf dem Video eingeblendet werden. Für die Bildverarbeitung sowie Programmierung wurde MATLAB R2016a verwendet. Eine CAD-Software wurde während der Entwicklung des Algorithmus zur Prüfung der Ergebnisse eingesetzt.

Erwartungen an die Projektlösung

Sammeln von weiteren Erfahrungen in Bildverarbeitung mit MATLAB
Umsetzung der in die Vorlesung gewonnenen Kenntnisse in die Praxis
Tieferer Einblick in die geometrische Physik
Sammeln von Erkenntnissen durch Problemstellungen
Erstellung eines spektakulären Videos, welches die Software demonstriert

Plannung

Projektplan

Die Gesamtaufgabe wurde wie folgt aufgeteilt:

Kevin Penner:
- Automatische Erkennung von Queue- und Kugelpositionen in einer Videoquelle
- sowie Unterscheidung der Kugeln, weiße- oder Zielkugel

Christo Tsibadze:
- Ein Algorithmus programmieren, der die Schlagrichtung der weißen Kugel berechnet
- Erkennung ob die weiße Kugel nach dem Schlag einen anderen Kugel trifft oder nicht
- Falls die weiße Kugel eine andere Kugel trifft, Berechnung in welcher Richtung die andere Kugel abprallt.

Die Aufgabe ist freiwillig. Zeitlich wurde für das Projekt im 6. Semester je ca. 3 Stunden pro Woche investiert. Zur Ideenfindung oder Besprechung der Problemlösungsstrategien wurde regelmäßiges Wochen-Meeting gehalten.

Erkennung von Queue- und Kugelpositionen

Im rechten Diagramm ist ein Ablaufplan zu sehen, welcher den Algorithmus zur Erkennung von Billardkugeln und dem Queue grob veranschaulicht. Im folgenden wird auf jeden dieser Punkte eingegangen:

Frame einlesen und Zuschneiden des Bildes

Damit das Testen der Algorithmen stattfinden kann, wurden öffentliche Videos von Billard-Wettkämpfen genutzt. Diese können über die VideoReader Funktion eingelesen werden. Außerdem ist der Anfangsframe (Startframe) und die Schrittweite (Frameschritte) der zu analysierenden Frames einstellbar.

video=VideoReader('001.mp4');
nframes = video.NumberOfFrames;
Frameschritte = 1;
Startframe = 1;

Da die Videos überflüssige Bildbereiche besitzen, wird zunächst der Billardtisch extrahiert, indem ein konstant definierter Bildbereich ausgewählt wird (ROI). Das zu analysierende Bild besitzt nun also einen homogenen Hintergrund (Farbe des Billardtisches), wodurch das Erkennen bzw. Segmentieren der Objekte vereinfacht wird.

Binarisierung

Für die Erkennung der Objekte im Bild (Kugeln und Queue) wird das RGB Bild in ein Binärbild umgewandelt. Da die Objekte jeweils einen unterschiedlichen Farbwert besitzen, muss für die Binarisierung jeder einzelne Farbkern mit einem Schwellwertverfahren umgewandelt werden. Zur Unterstützung wurde hier das Matlabtool "Color Thresholder" eingesetzt, welches aus einem vom Benutzer ausgewählten Bildbereiches automatische eine Funktion generiert. Dieser wird im Matlab Code ein RGB Bild als Parameter übergeben, woraufhin ein Binärbild zurückgegeben wird.
Diese Vorgehensweise muss jedoch für jeden spezifischen Billardtisch durchgeführt werden, falls ein anderer Tisch mit einer anderen Farbe angewendet wird.
In Abbildung 2 ist die Ausgabe des Originalsbildes (links) und des Binärbildes (rechts) zu sehen. An einigen Stellen treten jedoch einzelne Artefakte auf, welche im Nachhinein noch entfernt werden müssen.

Nachverarbeitung

Um später zu Verhindern das Artefakte als Objekte wahrgenommen werden, wird das Binärbild zusätzlich noch bereinigt. Matlab bietet hier eine große Anzahl an Funktionen und morphologischen Operationen an. Folgende zwei Nachverarbeitungsschritte werden durchgeführt:

Schwarze Pixel auf weißen Hintergrund werden gelöscht (Funktion: imfill). Diese Funktion füllt die Löcher in Objeken, damit diese eine zusammenhängende Fläche besitzen.
Mithilfe der Funktionen "imopen" und "bwareaopen" werden kleine weiße Pixelregionen im Bild gelöscht

In Abbildung 3 (rechts) ist nun eine deutliche Veränderung im Gegensatz zu Abbildung 2 (rechts) zu erkennen. Dieses Binärbild kann nun als Grundlage für die Erkennung der Objekte herangezogen werden.

%Binärbild bereinigen
imClean = imfill(BW,'holes');
se = strel('disk',1);
imClean = imopen(imClean,se);
imClean = bwareaopen(imClean, 80);

Kugelerkennung

Für die Erkennung von Kreisen bietet Matlab die Funktion "imfindcircles" an, welche folgende Parameter übergeben bekommt:

Bereinigtes Binärbild (imClean)
Maximalen und Minimalen Radius (in Pixeleinheiten) eines erkannten Kreises
Suche nach hellen Kreisen auf einem dunklen Hintergrund
Kreisformabweichung (wurde experimentell ermittelt)

Als Rückgabewert erhält man eine Liste von Bildkoordinaten der erkannten Kreise und deren Radien.

%Parameter für die Größe und "Genauigkeit" der Billardkugeln
RadiusMin = 6;
RadiusMax = 12;
Circle_Sensitivity = 0.9;

%Kreise im bereinigten Binärbild suchen
[Centers, Radii] = imfindcircles(imClean,[RadiusMin RadiusMax],'ObjectPolarity','bright','Sensitivity',Circle_Sensitivity);
AnzahlKreise = size(Centers);

Erkennung der weißen Kugel

Die Erkennung der weißen Kugel erfolgt über eine selbstgeschriebene Funktion:

function[WhiteCenter, WhiteRadius, WhiteIndex] = Detect_White_Sphere(Centers, Radii, Image)

Dieser werden die Bildkoordinaten und Radien aller erkannten Kreise übergeben, sowie das zugeschnittene RGB Bild. Als Rückgabewerte erhält man die Koordinaten, den Radius und den Index der weißen Kugel aus dem übergebenen Kreiskoordinatenvektor.
In dieser Funktion werden alle erkannten Kreise in einer Schleife auf deren Helligkeit (vorher muss das RGB Bild in ein Grauwertbild umwandelt werden) überprüft, indem der Mittelwert über alle Pixelwerte in einem Kreis gebildet wird und so der höchste Wert der weißen Kugel zugeordnet werden kann. Ob sich ein Pixel in einem Kreis befindet, kann mit folgender Formel berechnet werden:

${\displaystyle \mathtt{ PunktInKreis = (x-x_\text{center})^2 + (y-y_\text{center})^2 - r^2 }}$

${\displaystyle \mathtt{ PunktInKreis < 0 \Rightarrow Koordinaten\ liegen\ im\ Kreis }}$

${\displaystyle \mathtt{ PunktInKreis = 0 \Rightarrow Koordinaten\ liegen\ auf\ Kreisbahn }}$

${\displaystyle \mathtt{ PunktInKreis > 0 \Rightarrow Koordinaten\ liegen\ ausserhalb\ des\ Kreises }}$

Der Abscannbereich eines jeden Kreises wird wie in Abbildung 4 realisiert, indem ein Quadrat um den Kreis gebildet wird, in welchem anschließend nur die Pixel zum Mittelwert gezählt werden, welche mithilfe der Kreisgleichung zum Kreis zugeordnet werden können.
Der Matlabcode sieht wie folgt aus:

for j=1:AnzahlKreise
   %Boundingbox um Kugel ermitteln
   xmin = round(Centers(j,1)- Radii(j));
   xmax = round(Centers(j,1)+ Radii(j));
   ymin = round(Centers(j,2)- Radii(j));
   ymax = round(Centers(j,2)+ Radii(j));
   %Boundingbox "abscannen". Wenn Punkt im Kreis liegt, dann soll eine
   %Pixelsumme aller Helligkeitswerte gebildet werden. Aus diesen wird
   %dann der Mittelwert gebildet
   PxSum = 0;
   PxInd = 0;
   for m=ymin:ymax
      for n=xmin:xmax
         %PunktinKreis < 0 --> Koordinate liegt im Kreis
         %PunktinKreis = 0 --> Koordinate liegt auf Kreisbahn
         %PunktinKreis > 0 --> Koordinate liegt außerhalb des Kreises
         PunktinKreis = (n-Centers(j,1))^2 + (m-Centers(j,2))^2 - Radii(j)^2;
         if PunktinKreis <= 0 && n <= width && m <= height && n>0 && m>0
            PxSum = PxSum + double(GrayImage(m,n));
            PxInd = PxInd + 1;
         end
      end
   end
   PxMean(j) = PxSum/PxInd;
end

Queueerkennung

Nachdem die weiße Kugel erkannt ist, wird der Queue in der unmittelbaren Umgebung zur weißen Kugel gesucht. Hierzu wurde folgende Funktion implementiert:

%Absuchradius um weiße Kugel zum detektieren des Queue
DetectionRadius = 15;
DetectionSteps = 5;
Iterationen = 10;

for j=1:Iterationen
   [Queue] = Detect_Queue_01(WhiteCenter, DetectionRadius + (j-1)*DetectionSteps, imClean);
end

Der Funktion werden die Koordinaten der weißen Kugel, der Absuchradius zur Detektion des Queues und das bereinigte Binärbild übergeben. Als Rückgabewert wird die Position des Queues geliefert.

Algorithmus für Berechnungen

Schlagrichtung weiße Kugel

Nach der Bilderkennung werden folgende Positionen an die Funktion "BILLARD_FINAL_V2" über gegeben: Da zwei Positionen bekannt sind ( Queue-X, Queue-Y und Weiß-X, Weiß-Y) ist es leicht die Schlagrichtung zu ermitteln. Einen Vektor aus zwei gegebenen Punkten wird durch Differenzen der X- und Y-Komponenten bebildet. Je nach Verwendung wird der Vektor normalisiert, hierbei wird der Vektor durch eigene Länge geteilt. Länge eines Vektors errechnet man durch einen Wurzel von Summe aller Vektorkomponenten in Quadrat.

Einfachheitshalber wird angenommen das mit der Queuespitze immer auf die Mitte der weißen Kugel geschlagen wird. Sonst wäre das Projekt in verfügbaren Zeitrahmen nicht machbar.

Sortierung nach Entfernung

Wenn es in der Schlagrichtung der weißen Kugel mehrere Zielkugel positioniert sind, ist es erforderlich zu unterscheiden welche Kugel näher am weißen Kugel liegt bzw. zuerst getroffen wird. Nach der Kugelpositionserkennung wird eine Matrix bestehend aus 2 Zeilen über gegeben. In der ersten Zeile sind die X-Werte der Kugeln und in zweite die Y-Werte. Anzahl der Spalten ist gleich der erkannten bzw. übrig gebliebenen Zielkugeln. Für die Sortierung nach Entfernung wird der Matrix um eine Zeile erweitert und die bestehenden zwei Zeile werden nach unten geschoben (1. --> 2 und 2. --> 3.). In der ersten Zeile werden für jede Zielkugel die Entfernung zum weißen Kugel berechnet und eingetragen.

Die Entfernung einer Zielkugel zum weißen Kugel wird wie folgt ermittelt:

Vektorbestimmung anhand der Koordinaten der beiden Kugeln (wie im Schlagrichtung)
Entfernung: Länge des Vektors bestimmten

Nach dem alle Entfernungen der Zielkugeln in erste Zeile der Matrix eingetragen wurden, wird mit Hilfe der MATLAB-Funktion "sortrows" sortiert.

Diese Funktion ordnet aufsteigend Matrizen nach der ersten Spalte. Da wir nach der ersten Zeile ordnen wollen, wird die Matrix vor dem Sortierfunktion transponiert und nach der Sortierung wieder transponiert.

Beim Transponieren werden die Zeilen und Spalten vertauscht bzw. Zeilen in Spalten und Spalten in Zeilen umgewandelt.

Nach der Sortierung besteht eine Matrix aus drei Zeilen:

1. Zeile: Abstände zum weißen Kugel
2. Zeile: X-Koordinaten der Zielkugeln
3. Zeile: Y-Koordinaten der Zielkugeln

Spaltenanzahl ist gleich Zielkugelanzahl.

Treffer oder kein Treffer

Um herauszufinden ob die weiße Kugel in seiner Schlagrichtung einen Zielkugel trifft, wird wie folgt berechnet. Es wird ein imaginäres gleichschenkliges Dreieck aufgestellt mit folgenden Seitenlängen:

Länge der kleinen Seite: Kugelradius
Länge der restlichen beiden Seiten: Entfernung weiß- und ziel Kugel.

Die kleinste Seite wurde mit der Länge Kugelradius gewählt damit die Kugeln sich berühren. Zu bestimmen ist ein Winkel "Max. Winkel" (siehe Bild). Der Max.Winkel liegt zwischen der Schlagrichtung der weißen Kugel Q_R und den direkten Richtung weiß- zu ziel Kugel D_L. Max.Winkel ist abhängig von der Entfernung der Zielkugeln. Wenn der Winkel zwischen der Q_R und der D_L kleiner ist als der Max.Winkel, dann wird diese Zielkugel getroffen, sonst nicht.

Die Bestimmung von Max.Winkel: zunächst mit rechtwinkliges Dreieck (halbes gleichschenkliges Dreieck)

D_L: Direkte Linie (Direkte Richtung), zwischen der Ziel- und weißen Kugel ist die Hypothenuse
- Anfangsposition der D_L: Koordinaten der weißen Kugel
- Endposition der D_L : Koordinaten der Zielkugel
- Länge der D_L: Betrag von Vektor zwischen Ziel- und weißen Kugel
Länge der Gegenkathete: Kugelradius/2
Winkel zwischen Gegen- und Ankathete: 90°

Da es zwei Seiten und ein Winkel bekannt sind, ist der gesuchte Winkel mit der Sinus-Formel ermittelbar: Max.Winkel/2 = 2 * asin(Gegenkathete/Hypothenuse) --> Max.Winkel = 4 * asin(Gegenkathete/Hypothenuse)

Anschließend wird der aktuelle Winkel "Alpha" zwischen den D_L- und Q_R Vektoren wie folgt berechnet:

Skalarprodukt

Ist der Winkel Alpha kleiner als Max.Winkel --> Treffer, sonst kein Treffer.

Falls Treffer: Abprallrichtung

Dem Algorythmus nach wird erst geprüft ob die ziel Kugel mit kleinsten Entfernung zum weißen Kugel mit aktuellen Queue-richtung getroffen wird oder nicht, falls nicht dann wird die ziel Kugel mit nächst kleinsten Entfernung geprüft bis eine Zielkugel gefunden wird der mit getroffen wird. Ist eine Zielkugel gefunden der getroffen werden kann, dann wird versucht die Abprallrichtung der Zielkugel zu berechnen.

Bekannt sind:

D_L: die Direkte Linie zwischen den weißen- und ziel Kugel
- Länge, Richtung und Position
Q_R: die Schlagrichtung der weißen Kugel
- Startpunkt (weiße Kugel), Richtung, keine Länge
Alpha: Winkel Alpha ist ermittelbar durch zwei Vektoren ( D_L & Q_R)
2*R: Richtung zwischen den Zielkugel und den weißen Kugel beim aufprall
- Länge = 2 mal Kugelradius, ein Festpunkt bei Zielkugel

Gesucht: Überschneidungspunkt von 2*R und Q_R und der Winkel in diesem Dreieckspunkt.

Trigonometrisch gesehen sind Zwei lange Seiten des Dreiecks bekannt und der Winkel zwischen diesen Seiten. Also ist es möglich mit Hilfe des Kosinus-Satzes die restlichen Parameter herauszurechnen.
Siehe folgende Quelle: Berechnung eines beliebigen Dreiecks

Sind alle Winkeln bekannt, dann ist der Winkel der sich im Position von Z (Zielkugel) befindet relevant für die Bestimmung von Kugelabprallrichtung. Denn genau um diesen Winkel muss die Richtung D_L rotiert werden um den Kugelabprallrichtung zu bekommen.

Die Rotation einer Linie bzw. Vektor ist mit Multiplikation dessen mit einem Rotationsmatrix möglich.

Fallunterscheidungen

Die korrekte Abprallrichtung der Zielkugel zu berechnen ist es notwendige verschiedene Fälle zu unterscheiden.
Wird der Zielkugel von:

links nach rechts
rechts nach links
oben nach unten
unten nach oben

und Treffer auf linke oder rechte Hälfte der Zielkugel... Je nach Kugel-Anordnung ist im Rotationsmatrix entweder negative oder positive Alpha einzugeben. Deshalb wurde im CAD eine Skizze erstellt und alle Fälle durchgeprüft und die Software angepasst.

MATLAB GUI

Für die TEST_Versuche wurde eine MATLAB GUI erstellt womit jede mögliche Szenario (Kugelanordnung und Schlagrichtung) Simulierbar ist. Mit Hilfe dessen wurde die Software optimiert und von diversen kleineren Fehlern befreit.

Die einzelne Positionen sind einzeln entweder per Slider oder manuell eingebbar. Wird auf die "GO"-Taste gedrückt, dann berechnet die Software die Abprallrichtung und gibt diese als Darstellung aus.

Dokumentation

Video

Hier wird ein Link zum Youtube bereitstehen wenn das Video fertig ist.

Fazit

Die von uns angestrebte Ziele wurden erreicht!

... hat sehr viel Spaß gemacht.
...Die kreative Idee
Eigenkritik: BLALALALLLALALBLALALABLABLABLA
Mit mehr zeitlichen Ressource wären in diesem Projekt weitere Ziele denkbar:
- Eingelocht oder nicht
- Kugelabprall an den Banden
- Berechnung ob die getroffene Kugel weiteren Kugeln trifft und ob diese nochmals weitere Kugeln treffen und dessen Richtungen visualisieren.
- ...

Ende gut, alles gut :)

→ zurück zum Hauptartikel: DSB SoSe2016

Pool-Billard Assistenz: Unterschied zwischen den Versionen