Pool-Billard Assistenz: Unterschied zwischen den Versionen

Aus HSHL Mechatronik
Zur Navigation springen Zur Suche springen
 
(22 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt)
Zeile 24: Zeile 24:
== Projektplan ==
== Projektplan ==


Die Gesamtaufgabe wurde wie folgt aufgeteilt:
Folgende Meilensteine wurden von uns bearbeiten:
 
* Automatische Erkennung von Queue- und Kugelpositionen in einem Videoframe
* Kevin Penner:
* sowie Unterscheidung der Kugeln in weiß- und Zielkugeln
** Automatische Erkennung von Queue- und Kugelpositionen in einer Videoquelle
* ein Algorithmus implementieren, der die Schlagrichtung der weißen Kugel berechnet
** sowie Unterscheidung der Kugeln, weiße- oder Zielkugel
* Erkennung, ob die weiße Kugel nach dem Schlag eine andere Kugel trifft
 
* falls die weiße Kugel eine andere Kugel trifft, soll die Abprallrichtung der getroffenen Zielkugel berechnet werden
* Christo Tsibadze:
* Visualisierung von Hilfslinien im Video
** Ein Algorithmus programmieren, der die Schlagrichtung der weißen Kugel berechnet
* Dokumentation
** 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.
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.
Zur Ideenfindung oder Besprechung der Problemlösungsstrategien wurden regelmäßige Wochen-Meetings gehalten.
<br /> <br />
<br /> <br />


= Erkennung von Queue- und Kugelpositionen =
= Bildverarbeitung: Erkennung von Queue- und Kugelpositionen =
[[Datei:Ablaufdiagramm Pool-Billard Assistenz.png|350px|thumb|right|Abbildung 2: Ablaufdiagramm zur Erkennung von Billardkugeln und Queue]]
[[Datei:Ablaufdiagramm Pool-Billard Assistenz.png|350px|thumb|right|Abbildung 2: Ablaufdiagramm zur Erkennung von Billardkugeln und Queue]]


Zeile 69: Zeile 67:
In Abbildung 3 ist die Ausgabe des Originalbildes (links) und des Binärbildes (rechts) zu sehen. An einigen Stellen treten jedoch einzelne Artefakte auf, welche im Nachhinein noch entfernt werden müssen.
In Abbildung 3 ist die Ausgabe des Originalbildes (links) und des Binärbildes (rechts) zu sehen. An einigen Stellen treten jedoch einzelne Artefakte auf, welche im Nachhinein noch entfernt werden müssen.
[[Datei:Unbereinigtes Binärbild Billard.png|800px|thumb|left|Abbildung 3: Unbereinigtes Binärbild Billard]]
[[Datei:Unbereinigtes Binärbild Billard.png|800px|thumb|left|Abbildung 3: Unbereinigtes Binärbild Billard]]
<br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br />
<br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br />


== Nachverarbeitung ==
== Nachverarbeitung ==
Zeile 225: Zeile 223:
</source> <br />
</source> <br />


= Berechnungen: Schlagrichtung, Aufprallpunkt und Zielrichtung =
= Billardprognose =


Nach der Bildverarbeitung jedes Videoframes wird die Vorhersagefunktion "'''BILLARD_FINAL_V2'''" mit folgenden Parametern und Rückgabewerten aufgerufen:  
Nach der Bildverarbeitung jedes Videoframes wird die Vorhersagefunktion "'''Billard_Prediction'''" mit folgenden Parametern und Rückgabewerten aufgerufen:  


<source lang="matlab">
<source lang="matlab">
function [ RICHTUNG_Koordinaten, ZIEL_KUGEL, RICHTUNG_Koord_Weiss ] = BILLARD_FINAL_V2( W,Z,Q,R )
function [ RICHTUNG_Koordinaten, ZIEL_KUGEL, RICHTUNG_Koord_Weiss ] = Billard_Prediction( W,Z,Q,R )
</source> <br />
</source> <br />


Zeile 337: Zeile 335:
== Falls Treffer: Abprallrichtung ==
== Falls Treffer: Abprallrichtung ==
Mithilfe des Algorithmus wird zunächst geprüft, ob die Zielkugel mit dem kleinsten Abstand zur weißen Kugel in aktueller Queuerichtung getroffen wird. Falls dies nicht der Fall ist, wird die Zielkugel mit dem nächstkleineren Abstand geprüft, bis eine Zielkugel gefunden wird, die getroffen wird. Ist eine Zielkugel gefunden, die getroffen wird, wird die Abprallrichtung der Zielkugel berechnet.  
Mithilfe des Algorithmus wird zunächst geprüft, ob die Zielkugel mit dem kleinsten Abstand zur weißen Kugel in aktueller Queuerichtung getroffen wird. Falls dies nicht der Fall ist, wird die Zielkugel mit dem nächstkleineren Abstand geprüft, bis eine Zielkugel gefunden wird, die getroffen wird. Ist eine Zielkugel gefunden, die getroffen wird, wird die Abprallrichtung der Zielkugel berechnet.  
<br />
[[Datei:Kosinus Satz.jpg|250px|thumb|right|Abbildung 10: Kosinus Satz]]
[[Datei:Kosinus Satz.jpg|250px|thumb|right|Abbildung 10: Kosinus Satz]]


<br />
<br />
Gegeben ist ein allgemeines Dreieck mit:
Gegeben ist ein allgemeines Dreieck mit:
* D_L: die Direkte Linie zwischen der weißen und der Zielkugel
* '''D_L''': die Direkte Linie zwischen der weißen und der Zielkugel
** Länge, Richtung und Position
** Länge, Richtung und Position
* Q_R: die Schlagrichtung der weißen Kugel
* '''Q_R''': die Schlagrichtung der weißen Kugel
** Startpunkt (weiße Kugel), Richtung, keine Länge
** Startpunkt (weiße Kugel), Richtung, keine Länge
* Alpha: Winkel Alpha ist ermittelbar durch die zwei Vektoren '''D_L''' und '''Q_R'''
* '''Alpha''': Winkel Alpha ist ermittelbar durch die zwei Vektoren '''D_L''' und '''Q_R'''
* 2 x R: Richtung zwischen der Zielkugel und der weißen Kugel beim Aufprall
* 2 x '''R''': Richtung zwischen der Zielkugel und der weißen Kugel beim Aufprall (Richtung unbekannt, nur Länge bekannt)
** Länge = 2 x Kugelradius
** Länge = 2 x Kugelradius
Gesucht: Der Winkel '''Beta''', die Position des Überschneidungspunktes '''W' ''', sowie der Winkel im Punkt '''Z''' --> '''Gamma'''.
Gesucht: Der Winkel '''Beta''', die Position des Überschneidungspunktes '''W' ''', sowie der Winkel im Punkt '''Z''' --> '''Gamma'''.
Zeile 364: Zeile 363:


=== Fallunterscheidungen ===
=== Fallunterscheidungen ===
[[Datei:Fallunterscheidungen.png|250px|thumb|right|Abbildung 11: Fallunterscheidungen]]
[[Datei:Fallunterscheidungen.png|280px|thumb|right|Abbildung 11: Fallunterscheidungen]]


Um die korrekte Abprallrichtung der Zielkugel zu berechnen, ist es notwendig verschiedene Fälle zu unterscheiden.
Um die korrekte Abprallrichtung der Zielkugel zu berechnen, ist es notwendig verschiedene Fälle zu unterscheiden.
Zeile 515: Zeile 514:


<br />
<br />
https://youtu.be/Nycr1tyazxY<br />
[http://www.youtube.com/watch?v=Nycr1tyazxY Youtube Video Pool-Billard Assistenz]
<br />
<br />
<br />
----
----


Zeile 526: Zeile 527:
<br /> <br />
<br /> <br />
Die Software befindet sich im folgenden SVN Ordner:
Die Software befindet sich im folgenden SVN Ordner:
[\SVN\User\SoSe2016\Christo_Tsibadze\Abgabe_Billard_Projekt]
[https://svn.hshl.de/svn/DSB/trunk/User/SoSe2016/Christo_Tsibadze/Abgabe_Billard_Projekt/ SVN Link zur Abgabe]
\SVN\User\SoSe2016\Christo_Tsibadze\Abgabe_Billard_Projekt
<br />
<br />
Hier muss die folgende Maindatei ausgeführt werden: Pool_Billard_Assistenz_Main.m
Hier muss die folgende Maindatei ausgeführt werden: Pool_Billard_Assistenz_Main.m

Aktuelle Version vom 15. Juni 2016, 17:10 Uhr

Abbildung 1: Pool-Billard Assistenz

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, welche aus einem Video (oder Live-Cam) Billardkugeln- und Queue -Positionen erkennt und anschließend mit einem Algorithmus die Abprallrichtung einer Zielkugel "vorhersagt" (berechnet). Vor dem Schlag soll anhand der Queue- und Kugelpositionen erkannt werden, in welche Richtung die weiße Kugel geschlagen wird. Falls die weiße Kugel eine andere Kugel auf dem Billardtisch trifft, soll im Voraus die Abprallrichtung dieser ermittelt werden. Die berechnete Richtungen soll auf dem Video eingeblendet werden. Für die Bildverarbeitung sowie Programmierung wurde die Matlabversion R2016a verwendet. Eine CAD-Software wurde während der Entwicklung des Algorithmus zur Überprüfung der Ergebnisse eingesetzt.


Erwartungen an die Projektlösung

  • Sammeln von weiteren Erfahrungen in der Bildverarbeitung mit MATLAB
  • Umsetzung der in der Vorlesung gewonnenen Erkenntnisse in die Praxis
  • Tieferer Einblick in die geometrische Physik
  • Lösen von Problemstellungen durch ingenieurmäßige Herangehensweisen
  • Erstellung eines benutzerfreundlichen Videos, welches die Software visualisiert


Plannung

Projektplan

Folgende Meilensteine wurden von uns bearbeiten:

  • Automatische Erkennung von Queue- und Kugelpositionen in einem Videoframe
  • sowie Unterscheidung der Kugeln in weiß- und Zielkugeln
  • ein Algorithmus implementieren, der die Schlagrichtung der weißen Kugel berechnet
  • Erkennung, ob die weiße Kugel nach dem Schlag eine andere Kugel trifft
  • falls die weiße Kugel eine andere Kugel trifft, soll die Abprallrichtung der getroffenen Zielkugel berechnet werden
  • Visualisierung von Hilfslinien im Video
  • Dokumentation

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 wurden regelmäßige Wochen-Meetings gehalten.

Bildverarbeitung: Erkennung von Queue- und Kugelpositionen

Abbildung 2: Ablaufdiagramm zur Erkennung von Billardkugeln und Queue

In Abbildung 2 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 Billardwettkämpfen genutzt. Diese können über die VideoReader Funktion eingelesen werden. Außerdem sind 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 3 ist die Ausgabe des Originalbildes (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 3: 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 Objekten, damit diese, homogene Flächen besitzen.
  2. Mithilfe der Funktionen imopen und bwareaopen werden kleine weiße Pixelregionen im Bild gelöscht

In Abbildung 4 (rechts) ist nun eine deutliche Veränderung im Gegensatz zu Abbildung 3 (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 4: 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 5: Punkt im Kreis












Der Abscannbereich eines jeden Kreises wird wie in Abbildung 5 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:

[Queue] = Detect_Queue_01(WhiteCenter, DetectionRadius, imClean);


Abbildung 6: 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.
In der Funktion wird auf der Kreisbahn mit einem Absuchradius um die weiße Kugel nach weißen Pixelwerten gesucht (ob ein Pixel auf der Kreisbahn liegt, wird mit derselben Kreisgleichung, wie bei der Erkennung der weißen Kugel, überprüft). Die Koordinaten der Pixelwerte, die zu dem Queue zugeordnet werden, werden in einen Vektor geschrieben. Um den Mittelpunkt des Queues zu erhalten, wird folgende Berechnung im Anschluss an die Erfassung der Pixelwerte durchgeführt:








In der Testphase des Algorithmus zur Erkennung hat sich jedoch herausgestellt, dass aufgrund der ungenauen Binarisierung und damit verbundenen schlechten Erkennung des Queues, eine Abweichung zwischen wahrer mittleren Position und erkannter mittleren Position des Queues resultierte. Diese Abweichung konnte durch das Erfassen von mehreren Punkten auf dem Queue minimiert werden (siehe Abbildung 6). Die Funktion wird nun in einer Schleife ausgeführt, in welcher der Absuchradius stetig erhöht wird:

%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


Die detektierten Punkte werden in einen Vektor geschrieben. Für das Erhalten eines eindeutigen Punktes auf dem Queue, wird nun noch der Mittelwert aller x- und y-Koordinaten gebildet.


Eingeschränkte Durchführung des Algorithmus

Da die Ermittlung der Queueposition nur erfolgen muss, wenn sich die weiße Kugel im Stillstand befindet, wird vor der Ausführung der Funktion zur Queueerkennung die Positionsveränderung der weißen Kugel kontrolliert. Hierfür wird die Differenz der alten Position der weißen Kugel mit der neuen Position gebildet und mit einem geringem Schwellwert verglichen:

Position_of_rest = ((abs(WhiteCenter(1)-WhiteCenterOld(1))<5) && (abs(WhiteCenter(2)-WhiteCenterOld(2))<5)) 
if Position_of_rest
.
.
.
end


Billardprognose

Nach der Bildverarbeitung jedes Videoframes wird die Vorhersagefunktion "Billard_Prediction" mit folgenden Parametern und Rückgabewerten aufgerufen:

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


  • W: X- und Y-Koordinate der weißen Kugel

Format:

[double x;double y]


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

Format:

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


  • Q: X- und Y-Koordinate der Queuespitze

Format:

[double x;double y]


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

Format:

[double r]


Als Rückgabe 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 Koordinate der anvisierten Zielkugel zurück

Format:

[double x;double y]


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

Format:

[double x;double y]


Falls keine Zielkugel anvisiert wird, werden alle Rückgabewerte mit 0 initialisiert.

Vorbereitung

Da die Y-Achse der Bildkoordinaten bei der Videoverarbeitung von oben nach unten verläuft (positive Y-Werte) und im Vorhersagealgorithmus von unten nach oben (negative Y-Werte), werden 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 in der Schlagrichtung der weißen Kugel mehrere Zielkugeln positioniert sind, ist es erforderlich zu unterscheiden, welche Kugel den kürzesten Abstand zur weißen Kugel besitzt bzw. welche Zielkugel 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 aller Zielkugeln zur weißen Kugel 
end
B = sortrows(B')'; % Matrix transponieren, nach Abstände zur weißen Kugel ordnen und zurücktransponieren


Die Anzahl der Spalten ist gleich der erkannten bzw. übrig gebliebenen Zielkugeln. Für die Sortierung nach der Entfernung wird eine neue Matrix B mit drei Zeilen erzeugt. Die X- und Y-Koordinaten aus der Z-Matrix werden in die zweite und dritte Zeile der B-Matrix eingetragen (1. --> 2 und 2. --> 3.). In der ersten Zeile wird für jede Zielkugel die Entfernung zur weißen Kugel berechnet und eingetragen.

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

  • Vektorbestimmung anhand der Koordinaten von Ziel- und weißer Kugel
    [x1-x1;y1-y2]
    

  • Entfernung: Länge des Vektors bestimmten
    sqrt(x^2 + y^2)
    

Nachdem alle Entfernungen der Zielkugeln in die erste Zeile der B-Matrix eingetragen wurden, wird mithilfe der MATLAB-Funktion sortrows die Matrix aufsteigend (nach Entfernungen) sortiert.

Da die Funktion

sortrows

den Inhalt der ersten Matrizenspalte aufsteigend ordnet, jedoch die Entfernungen in unserem Fall in der ersten Zeile stehen, 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 zur weißen Kugel (aufsteigend geordnet)
  • 2. Zeile: X-Koordinaten der Zielkugeln
  • 3. Zeile: Y-Koordinaten der Zielkugeln

Die Spaltenanzahl entspricht der Anzahl der Zielkugeln.

Schlagrichtung weiße Kugel

Abbildung 7: Schlagrichtung

Um herauszufinden in welche Richtung die weiße Kugel geschlagen bzw. anvisiert wird, wird mithilfe der Koordinaten des Queues Q(x;y) und der weißen Kugel W(x;y) ein Schlagrichtungsvektor berechnet und anschließend normiert.

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


Die Vektornormierung wird wie folgt berechnet: Der Vektor wird durch seine eigene Länge geteilt. Einfachheitshalber wird angenommen, dass mit der Queuespitze immer auf die Mitte der weißen Kugel gezielt wird, da das Projekt sonst im verfügbaren Zeitrahmen nicht machbar gewesen wäre.








Treffer oder kein Treffer

Abbildung 8: Phi_max fuer Treffer

Um herauszufinden, ob die weiße Kugel in der Schlagrichtung eine Zielkugel trifft, werden folgende Berechnungen durchgeführt:
Es wird ein imaginäres gleichschenkliges Dreieck aufgestellt mit folgenden gegebenen Seitenlängen (siehe Abbildung 8):

  • Länge der kleinen Seite: 2 x Kugelradius (bzw. 1 x Kugeldurchmesser)
  • Länge der langen Seite: Entfernung der weißen Kugel zur Zielkugel (direkte Linie: D_L)

Als Länge der kleinen Seite wurde der Kugeldurchmesser gewählt, da sich die Kugeln bei einem Kontakt berühren. Zu bestimmen ist der Winkel "Phi_max" (siehe Abbildung 8). Dieser Winkel ist zwischen der Schlagrichtung der weißen Kugel Q_R und der direkten Richtung D_L eingeschlossen und ist abhängig von der Entfernung der Zielkugel zur weißen Kugel. Die Zielkugel kann nur dann getroffen werden, wenn der aktuelle Winkel (Alpha) kleiner ist als Phi_max.

Abbildung 9: Phi_max fuer Treffer Zwischenrechnung

Für die Bestimmung von Phi_max von jeder Zielkugel wird zunächst nur die Hälfte des gleichschenkligen Dreiecks betrachtet --> rechtwinkliges Dreieck (siehe Abbildung 9)

  • D_L: Direkte Linie zwischen der Ziel- und weißen Kugel entspricht der Hypotenuse
    • Anfangsposition der D_L: Koordinaten der weißen Kugel
    • Endposition der D_L : Koordinaten der Zielkugel
    • Länge der D_L: Betrag des Vektors, welcher zwischen Ziel- und weißer Kugel aufgespannt wird
  • Länge der Gegenkathete: Kugelradius
  • Winkel zwischen Gegen- und Ankathete: 90°

Da die Hypotenuse, die Gegenkathete und ein Winkel bekannt sind, ist der gesuchte Winkel mithilfe des Sinus ermittelbar:
--> Phi_max = 2 * arcsin(Gegenkathete/Hypotenuse)

Phi_max=2*asind((R)/B(1,i,:)); %maximaler Winkel für Treffer


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


D_L=(B(2:3,i,:)-W);% direkte Richtung, zwischen Ziel- und weißer Kugel
%% aktueller Winkel Schlagrichtung bzw. direkte Richtung
Alpha = acosd((dot(Q_R,D_L))/((norm(Q_R) * norm(D_L)))); % Winkel zwischen Q_R und D_L


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

Falls Treffer: Abprallrichtung

Mithilfe des Algorithmus wird zunächst geprüft, ob die Zielkugel mit dem kleinsten Abstand zur weißen Kugel in aktueller Queuerichtung getroffen wird. Falls dies nicht der Fall ist, wird die Zielkugel mit dem nächstkleineren Abstand geprüft, bis eine Zielkugel gefunden wird, die getroffen wird. Ist eine Zielkugel gefunden, die getroffen wird, wird die Abprallrichtung der Zielkugel berechnet.

Abbildung 10: Kosinus Satz


Gegeben ist ein allgemeines Dreieck mit:

  • D_L: die Direkte Linie zwischen der weißen und der Zielkugel
    • 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 die zwei Vektoren D_L und Q_R
  • 2 x R: Richtung zwischen der Zielkugel und der weißen Kugel beim Aufprall (Richtung unbekannt, nur Länge bekannt)
    • Länge = 2 x Kugelradius

Gesucht: Der Winkel Beta, die Position des Überschneidungspunktes W' , sowie der Winkel im Punkt Z --> Gamma.

Da zwei Seiten des Dreiecks und der Winkel zwischen diesen Seiten bekannt ist, sind mithilfe des Kosinus die restlichen Parameter zu berechnen.
Siehe folgende Quelle: Berechnung eines beliebigen Dreiecks

    Beta=180-asind((B(1,j,:)/(2*R))*sind(Alpha)); %
    Gamma=180-Beta-Alpha;


Sind alle Winkel bekannt, ist es anhand des Winkels Gamma möglich, die Kugelabprallrichtung zu bestimmen. Denn genau um diesen Winkel muss der Vektor D_L rotiert werden, um den Kugelabprallrichtung zu erhalten.

Die Rotation einer Geraden bzw. eines Vektors ist durch Multiplikation mit einer Rotationsmatrix festzustellen.


Fallunterscheidungen

Abbildung 11: Fallunterscheidungen

Um die korrekte Abprallrichtung der Zielkugel zu berechnen, ist es notwendig verschiedene Fälle zu unterscheiden.
Die Zielkugel wird von:

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

geschlagen:

    %% Fallunterscheidung für Winkel Gamma, Anordnung W und Z
    if((W(1)<B(2,j,:))&&(W(2)>B(3,j,:)))
        Fall = 1; %Schlag von links oben
    end
    if((W(1)<B(2,j,:))&&(W(2)<B(3,j,:)))
        Fall = 2; %Schlag von links unten
    end
    if((W(1)>B(2,j,:))&&(W(2)>B(3,j,:)))
        Fall = 3; %Schlag von rechts oben
        Gamma=(180-Gamma);
    end
    if((W(1)>B(2,j,:))&&(W(2)<B(3,j,:)))
        Fall = 4; %Schlag von rechts unten
        Gamma=(180-Gamma);
    end


Außerdem muss überprüft werden, ob die Zielkugel auf der rechten oder linken Seite getroffen wird:

    %% Winkelberechnung für Orientierung im 2D-Raum
    Winkel_1 = acosd((dot(RefH,Q_R))/((norm(RefH) * norm(Q_R))));
    Winkel_2 = acosd((dot(RefH,D_L))/((norm(RefH) * norm(D_L))));
    if(Winkel_1 == Winkel_2)
            Gamma=0;
    else
        switch Fall
            case 1
                if(Winkel_1 > Winkel_2)
                    Gamma=-Gamma;
                end
            case 2
                if(Winkel_1 < Winkel_2)
                    Gamma=-Gamma;
                end
            case 3
                if(Winkel_1 < Winkel_2)
                    Gamma=-Gamma;
                end
            case 4
                if(Winkel_1 > Winkel_2)
                    Gamma=-Gamma;
                end
        end
    end


Je nach Kugelanordnung wird in der Rotationsmatrix der Winkel Gamma entweder als negativ, positiv oder 180°-Gamma angenommen.

Für die Ermittlung der richtigen Abprallrichtung sind mehrere Rotationen um 90° und Vektorumkehrungen (Multiplikation mit -1) notwendig. Um die Implementierungen bzw. das Debuggen zu vereinfachen, wurden selbst erstellte CAD-Skizzen und eine MATLAB-GUI herangezogen. Somit wurden alle möglichen Fälle va­li­die­rt und die Software dementsprechend angepasst.

    %% Rotation von D_L auf Abprallrichtung
    RICHTUNG_NEU=rot90(W-B(2:3,j,:))*[cosd(Gama) -sind(Gama); sind(Gama) cosd(Gama)];
    RICHTUNG_NEU=rot90(rot90(rot90((RICHTUNG_NEU)))).*-1;
    if(Fall==4 || Fall==3)
        RICHTUNG_NEU=RICHTUNG_NEU.*-1;1
    end;


Rückgabewerte

if(Q(1)~= 0 && Q(2) ~= 0) % Rückgabewerte nur wenn Queueposition bekannt ist
        RICHTUNG_NEU = RICHTUNG_NEU./norm(RICHTUNG_NEU); %normieren
        RICHTUNG_NEU = RICHTUNG_NEU.*50; %feste Vektorlänge von 50 Pixel
        RICHTUNG_Koordinaten(1) = B(2,j,:)+RICHTUNG_NEU(1); % X-Komponente der Rückgabevektor für Abprallrichtung mit Startpunkt (Zielkugel)
        RICHTUNG_Koordinaten(2) =  B(3,j,:).*-1+RICHTUNG_NEU(2).*-1; % Y-Komponente der Rückgabevektor für Abprallrichtung mit Startpunkt (Zielkugel),
        %Richtung angepasst                            
        ZIEL_KUGEL = [B(2,j,:) ; B(3,j,:).*-1]; % Koordinaten der aktuell anvisierten Zielkugel, Y-Koodrinate angepasst
        RICHTUNG_Koord_Weiss = B(1,j,:).*Q_R_Norm+W; % Hilfslinie Startpunkt Weiße Linie X-Komponente
        RICHTUNG_Koord_Weiss(2) = RICHTUNG_Koord_Weiss(2).*(-1);% Hilfslinie Startpunkt Weiße Linie Y-Komponente angepasst
end


Die Rückgabewerte werden so angepasst, dass die Y-Komponenten wieder den Bildkoordinaten entsprechen.

MATLAB GUI

Für Testzwecke wurde eine MATLAB GUI erstellt, womit jedes mögliche Szenario (Kugelanordnung und Schlagrichtung) simuliert wurde. Mithilfe dieser wurde die Software optimiert und von diversen kleineren Bugs befreit.

Abbildung 12: GUI Billard



Die Positionen der Kugeln können entweder per Schieberegler oder manuell eingegeben werden. Durch das Drücken auf die "GO"-Taste, berechnet die Software die Abprallrichtung und gibt diese Linie aus.

Ausgabe

Als Ausgabe erfolgt die Darstellung des zugeschnittenen Originalbildes (siehe Abbildung 12) inklusive folgender Geraden, Punkte und Kreise:

  • Gerade zwischen Queueposition und des Mittelpunktes der weißen Linie (rote Linie)
  • Gerade zwischen Mittelpunkt der weißen Kugel und Aufprallpunkt an der Zielkugel (grüne Linie)
  • Gerade zwischen Mittelpunkt der Zielkugel und Richtung der Zielkugel (gelbe Linie)
  • Mittelpunkt der weißen Kugel (blauer Punkt)
  • Umrandung aller Kugeln auf dem Billardtisch (rote Kreise)
Abbildung 13: Ausgabe


Resultat

Probleme

In der Endlösung sind nun noch folgende Probleme vorhanden, für welche schon theoretische Optimierungsansätze aufgestellt wurden:

Problem: Ungenaue Schlagrichtung der weißen Kugel
Ursache: Aufgrund einer ungenauen Ermittlung der Queueposition und des Mittelpunktes der weißen Kugel ergibt sich eine geringe Abweichung im Stoßwinkel. Umso größer die Distanz zu einer Zielkugel ist, desto größer wird hier die Abweichung des Aufprallpunktes an der Zielkugel.
Lösungsansätze:

  • Auswahl eines Videos mit höherer Auflösung, wodurch der Queue besser segmentiert werden könnte
  • Auswahl eines kontrastreicheren Queues, welcher besser vom Hintergrund segmenetiert werden könnte
  • Detektion des Queues mit anderen Methoden (z.B. Liniendetektion)



Problem: Fehlerhafte Queueerkennung, wenn sich eine Zielkugel im Absuchradius der weißen Kugel befindet
Ursache: Aufgrund dessen, dass im Absuchradius der weißen Kugel nach weißen Pixel gesucht wird, welche als Queue identifiziert werden, wird die Queueposition falsch ermittelt
Lösungsansätze:

  • Der Queue wird nur als solcher erkannt, wenn der weiße Pixelbereich im Absuchradius einer gewissen Breite entspricht (die des Queues)
  • Absuchradius um die weiße Kugel in einem gesonderten Binärbild durchsuchen, welches nur die Segmentierung des Queues beinhaltet. Hierzu müsste der Queue jedoch ein Alleinstellungsmerkmal in seiner Farbzusammensetzung besitzen, welches keiner anderen Kugel entspricht (ist in den Beispielvideos nicht der Fall)



Problem: Langsame Berechnung
Ursache: Matlab ist nicht für Echtzeitanforderungen gedacht
Lösungsansätze:

  • Umwandeln aller Funktionen in MEX Funktionen
  • Implementierung der Algorithmen in anderen Programmiersprachen


Potential

Die Software bietet noch einiges an Potential, welches aufgrund des gegebenen Zeitraums noch nicht implementiert wurde:

  • Erkennung von Banden und Einbeziehen dieser bei der Schlagrichtung der weißen Kugel. So könnten auch potentielle Zielkugeln ermittelt werden, welche über die Bande angespielt werden sollen.
  • Erkennung von Löchern und Ausgabe, ob die Zielkugel in eines dieser Löcher hineinfällt
  • Automatisches Punktesystem und die davon Ausgehende Ermittlung von halben und ganzen Kugeln
  • Echtzeitfähigkeit und Liveanwendung mit einem Embedded System (z.B. Raspberry Pi mit Webcam und einem Projektor, welcher die Hilflinien auf den Billardtisch projeziert)
  • Geschwindigkeitsermittlung der weißen Kugel nach dem Stoß und damit die genaue Position der Zielkugel/n nach einem Treffer
  • Berechnung der Aufprallpunkte weiterer Kugeln, welche von der Zielkugel getroffen werden (bis alle Kugeln zum Stillstand kommen)

Video


Youtube Video Pool-Billard Assistenz


Fazit

Die von uns angestrebte Ziele wurden erreicht. Die Bildverarbeitung sowie der anspruchsvolle Billardalgorithmus haben uns mit vielen nützlichen Erfahrungen bereichert und auch sehr viel Spaß gemacht. Mit mehr zeitlichen Ressource wären in diesem Projekt weitere Ziele denkbar (siehe Potential). Das angeeignete Wissen lässt sich nun einfacher auf andere Problemstellungen reflektieren. Außerdem ist das große Potential der Bildverarbeitung nun deutlicher für uns geworden, jedoch auch die Schwierigkeiten, welche sich daraus ergeben.

Die Software befindet sich im folgenden SVN Ordner: SVN Link zur Abgabe
Hier muss die folgende Maindatei ausgeführt werden: Pool_Billard_Assistenz_Main.m




→ zurück zum Hauptartikel: DSB SoSe2016