Pool-Billard Assistenz

Neue Richtung

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

Abbildung 1: Ablaufdiagramm zur Erkennung von Billardkugeln und Queue

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.

Abbildung 2: Unbereinigtes Binärbild Billard

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:

1. 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.
2. 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);

Abbildung 3: Bereinigtes Binärbild Billard

Kugelerkennung

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

1. Bereinigtes Binärbild (imClean)
2. Maximalen und Minimalen Radius (in Pixeleinheiten) eines erkannten Kreises
3. Suche nach hellen Kreisen auf einem dunklen Hintergrund
4. 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:

Abbildung 4: Punkt im Kreis

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

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

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

$\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

Abbildung 5: Queueerkennung

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

Nach der Bilderkennung jedes Video-Frames wird die Vorhersagefunktion "BILLARD_FINAL_V2" mit folgenden Parametern und Rückgabewerten aufgerufen:

function [ RICHTUNG_Koordinaten, ZIEL_KUGEL, RICHTUNG_Koord_Weiss ] = BILLARD_FINAL_V2( W,Z,Q,R )

• W: X- und Y-Koordinaten der Weißen Kugel

Format:

[double x;double y]

• Z: X- und Y-Koordinaten aller Zielkugeln in einem Matrix

Format:

[[double x1;double y1],[double x2;double y2],...,[double xn;double yn]];

• Q: X- und Y-Koordinaten der Queue-Spitze

Format:

[double x;double y]

• R: Kugelradius (Annahme, alle Kugeln sind gleich groß)

Format:

[double r]

Als Rückgabewerte liefert die Funktion folgende Werte:

• RICHTUNG_Koordinaten: ein Vektor mit der Länge von 50 Pixeln, dessen Startpunkt die anvisierte Zielkugel ist und dessen Richtung die vorhersagte Abprallrichtung der Zielkugel beschreibt.

Format:

[double x;double y]

• ZIEL_KUGEL: Gibt die Koordinaten von den anvisierten Zielkugel zurück

Format:

[double x;double y]

• RICHTUNG_Koord_Weiss: Gibt eine Hilfskoordinaten zurück um die "Anvisierlinie" der weißen Kugel zu visualisieren

Format:

[double x;double y]

Falls keine Ziel-Kugel anvisiert wird dann werden alle Rückgabewerte mit 0 zurückgegeben.

Vorbereitung

Da im Bildkoordinaten bei Videoverarbeitung die Y-Achse von oben nach unten verläuft und in Vorhersagealgorythmus von unten nach oben, werden die alle Y-Koordinaten vor- und nach der Berechnung umgekehrt.

%% Y-Achse Umkehren  
Z(2,:) = Z(2,:).*-1;
Q(2) = Q(2).*-1;
W(2) = W(2).*-1;

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.

%% Zielkugel mit kleinsten Abstand finden (und sortieren)
Anzahl_Zielkugeln = size(Z,2);
B(3,Anzahl_Zielkugeln)=zeros; %Neue Matrix vorbereiten
B(2,:,:)=Z(1,:); % in die zweite Zeile alle X-Koordinaten der Zielkugeln
B(3,:,:)=Z(2,:); % in die dritte Zeile alle Y-Koordinaten der Zielkugeln
for i = 1: Anzahl_Zielkugeln
    B(1,i,:) = norm(Z(:,i)-W); % in die erste Zeile --> Abstände zum weißen Kugel aller Zielkugeln
end
B = sortrows(B')'; % Matrix transponieren, nach Abstände zum weißen Kugel ordnen und zurücktransponieren

Die Anzahl der Spalten ist gleich der erkannten bzw. übrig gebliebenen Zielkugeln. Für die Sortierung nach Entfernung wird eine neue Matrix B mit drei Zeilen erzeugt. Die X- und Y-Koordinaten aus Z-Matrix werden in 2.- und 3. Zeile der B-Matrix eingetragen (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 von ziel- und weißen Kugeln

  [x1-x1;y1-y2]
  

• Entfernung: Länge des Vektors bestimmten

  sqrt(x^2 + y^2)
  

Nach dem alle Entfernungen der Zielkugeln in erste Zeile der B-Matrix eingetragen wurden, wird mit Hilfe der MATLAB-Funktion "sortrows" die Matrix mit der ersten Zeile aufsteigend (nach Entfernungen) sortiert.

Diese Funktion

sortrows

ordnet Matrizen aufsteigend mit der ersten Spalte. Da wir mit der ersten Zeile ordnen wollen, wird die Matrix vor- und nach dem Sortieren transponiert. Beim Transponieren werden die Zeilen und Spalten vertauscht bzw. Zeilen in Spalten und Spalten in Zeilen umgewandelt.

Nach der Sortierung besteht die B-Matrix aus drei Zeilen:

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

Spaltenanzahl ist gleich Zielkugelanzahl.

Schlagrichtung weiße Kugel

Schlagrichtung

Um herauszufinden in welcher Richtung die weiße Kugel geschlagen bzw. anvisiert wird, werden mit Hilfe der Koordinaten von Queue (Q(x;y)) und weißen Kugel (W(x;y)) ein Schlagrichtungsvektor berechnet und anschließend normiert.

%% Richtung Direkt
Q_R=(W-Q);% Richtung QW Queue-Weis
Q_R_Norm = Q_R./norm(Q_R); %Vektor normieren

Die Vektornormierung wird wie folgt berechnet: Der Vektor wird durch eigene Länge geteilt. 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.

Treffer oder kein Treffer

Max Winkel fuer 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 x 2
• Länge der restlichen beiden Seiten: Entfernung weiß- zu 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.

Max Winkel fuer Treffer 2

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.

Kosinus Satz

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

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.

GUI Billard

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