Dobble Spiel gegen den Computer

Projektteam: Benedikt Steinmeier Stefan Vogel

Betreuer: Prof. Schneider

Einleitung

Dieser Artikel wurde im Rahmen der Lehrveranstaltung Digitale Signal- und Bildverarbeitung verfasst und dokumentiert die Ergebnisse des Projektes "Dobble Spiel gegen den Computer". Die allgemeinen Ziele der Projekte können im Wiki-Artikel DSB SoSe2016 eingesehen werden.

Aufgabenstellung

Die Aufgabenstellung dieses semesterbegleitenden Projekts bestand daraus, mit Hilfe der Matlab Image Processing Toolbox einen Algorithmus zu entwickeln, der das Gleiche Objekt auf zwei verschiedenen Dobble-Karten findet, anzeigt und markiert.

Durchführung

Allgemeines

Übersicht der Programm Module

Das im Rahmen dieser Semesteraufgabe erstellte Programm besteht aus folgenden Modulen:

• find_same_objects.m
  • Hauptporgramm zur Bildverarbeitung und Objekt Findung

• SameObjectSearchEngine.m & SameObjectSearchEngine.fig
  • Testumgebung um Dobble-Spiel zu simulieren und zur Bildausgabe

• change_circle_area.m
  • Hilfsfunktion für die Testumgebung um den Dobble-Karten einen schwarzen Hintergrund zu geben

• save_teaching_list.m
  • generiert "object_teaching_list.mat",mit allen möglichen Objekten und deren Eigenschaften als Inhalt. "object_teaching_list.mat" wird von der Testumgebung geladen und anschließend an die Funktion "find_same_objects.m" übergeben.

Vorbereitung

Beispiel Dobble Karte

Zu Beginn des Projekts wurden alle Dobble-Karten unter zur Hilfenahme des HSHL Buchscanners der Bibliothek abfotografiert und anschließend vereinzelt. Insgesamt standen 12 Dobble-Karten mit insgesamt 29 verschiedenen Objekten zur Verfügung.

Objekt Teach-Verfahren

Um den Algorithmus das "maschinelle Sehen" und somit die Objekterkennung und Objektunterscheidung zu ermöglichen wurde eine Excel-Liste erstellt, in der jedes Objekt mit seinen jeweiligen Standartabweichungen und Mittelwerten der Farbanteile und Kreisförmigkeit aufgelistet wurden. Dazu wurde sich jedes einzelne Objekt von allen Dobble Karten in Matlab ausgegeben, manuell sortiert und deren Farbanteile und Kreisförmigkeit in die Excel-Liste eingetragen. Die Werte der Standartabweichungen und Mittelwerte sowie die Objektnamen wurden anschließend in die Funktion "save_teach_list.m" eingetragen um eine ".mat"-Datei daraus zugenerien.

Objekterkennung und Segmentierung der Objekte auf den Dobble-Karten

Die Objekterkennung und Segmentierung der einzelnen Objekte auf den Dobble-Karten wird in dem Matlab Script find_same_objects.m durchgeführt. Diese Funktion bekommt ein Bild mit zwei Dobble-Karten, sowie eine Liste mit allen möglichen Objekten und deren Eigenschaften übergeben. Die Rückgabe dieser Funktion besteht aus dem Namen des gefunden doppelten Objekts, sowie die X- und Y-Positionen der beiden gleichen Objekte auf dem Bild.

function [object_name x_pos1 y_pos1 x_pos2 y_pos2] = find_same_objects( image, teach_list)

Merkmalsextraktion

Als Merkmale wurden

• der durchschnittliche Rotton aller Pixel eines Objektes

• der durchschnittliche Grünton aller Pixel eines Objektes

• der durchschnittliche Blauton aller Pixel eines Objektes

• die Kreisförmigkeit des Umrisses eines Objektes

definiert

Die Merkmalsextraktion der Objekte auf den Dobble-Karten glieder sich in folgende Schritte auf:

Ausgangslage

• Umwandeln des Farbbildes in ein Graubild mittels der Funktion "rgb2gray"

• Gaus-Filtern des Graubildes mittels der Funktion "imgaussfilt"

• Umwandeln des Graubildes in ein Binäbild mittels der Funktion "im2bw"

• Ermitteln der Grenzen der zwei runden Dobble-Karten mittels der Funktion "bwboundaries"

• Bestimmen der Maxima und Minima in X- und Y-Richtung der jeweiligen gefundenen Dobble-Karten

• Abspeichern der Dobble-Karten in entsprechenden neuen temporären Bildern

Extrahierte Dobble-Karte

• Weißfärben des Hintergrundes des temporären Bilders mit der jeweiligen Dobble-Karte im Zentrum

• Bestimmen aller Objekte, die sich innheralb von anderen Objekten befinden, in den temporären Bildern mittels der Funktion "bwboundaries"

• Bestimmen der Maxima und Minima in X- und Y-Richtung der gefundenen Objekte

• Extrahieren der Objekte aus der Dobble-Karte

• Füllen von Löchern innerhalb des Objektes

• Entfernen von Regionen, die den Rand schneiden

Extrahiertes Objekt vor Bearbeitung

Extrahiertes Objekt nach Bearbeitung

• Ermitteln der Mediane des Grün-, Blau- und Rotanteils aller übrig gebliebenen Pixel

• Berechenen der Kreisförmigkeit des Objektes

Objekt mit berechneten Merkmalen

• Abspeichern der Parameter für jedes Objekt in einer Liste

Klassifikation der Objekte

Die Klassifikation der Objekte wird mit Hilfe der Funktion "check_attributes(...)" in "find_same_objects.m" vollzogen.

Dabei werden die auf den Dobble-Karten gefundenen Objekte einzeln, mit allen Objekten aus der am Anfang erstellten Vergleichsliste (teach_list), anhand ihrer Farbanteile und Kreisförmigkiet verglichen.

Die Funktion check_attributes liefert anschließend ein Bool zurück ob es sich bei dem gesuchten Objekt um das Objekt aus der Vergleichsliste handelt oder nicht.

function [return_bool] = check_attributes( red, red_variance, green, green_variance, blue, blue_variance, circle, circle_variance, compare_object_red, compare_object_green, compare_object_blue, compare_object_circle)
% function          :   check_attributes
%
% description       :   checks if the current object, which has to be
%                       identified matches the attributes of the object
%                       from the teach_list
%
%       inputs: 
%               red:            red rate of the object which has to be
%                               identified
%               
%               red_variance:   red vanriance of the object which has to be
%                               identified
%
%               green:          green rate of the object which has to be
%                               identified
%               
%               green_variance: green vanriance of the object which has to be
%                               identified
%
%               blue:           blue rate of the object which has to be
%                               identified
%               
%               blue_variance:  blue vanriance of the object which has to be
%                               identified
%
%               cirlce:         circle rate of the object which has to be
%                               identified
%               
%               circle_variance:circle vanriance of the object which has to be
%                               identified
%
%               compare_object_red:     red rate of the object from the
%                                   teach_list
%               
%               compare_object_green:	green rate of the object from the
%                                   teach_list
%
%               compare_object_blue:	blue rate of the object from the
%                                   teach_list
%
%               compare_object_cirlce:  circle rate of the object from the
%                                   teach_list
%       output: 
%               return_bool:    bool for showing if the object which has to be
%                               identified, matches the object from the
%                               teach_list
%                               true : yes
%                               false: no

    return_bool = false;
    if red < (compare_object_red + red_variance) && red > (compare_object_red -red_variance)
        if (green <= (compare_object_green + green_variance)) && (green>= (compare_object_green - green_variance))
            if (blue <= (compare_object_blue + blue_variance)) && (blue>= (compare_object_blue - blue_variance))
                if (circle <= (compare_object_circle + circle_variance)) && (circle>= (compare_object_circle - circle_variance))

                    return_bool = true;

                end
            end
        end
    end

Werden mehrere mögliche Objekte aus der Vergleichsliste gefunden, die zu dem gesuchten Objekt passen könnten, werden alle Farbanteile sowie die Kreisförmikkeit*Factor des gesuchten Objekts von denen der Vergleichs-Objekte subtrahiert und die absoluten Beträge davon anschließend addiert.

Das gesuchte Objekt wird anschließend als das Vergleichs-Objekt deklariert, welches den geringsten Abstand zu Null hat.

 % more than one possible objects were found
                % if there are more than one objects, all color attributes
                % and the circle (multiplied with the circle factor) are
                % getting aggregated with the current_object attributes
                % subtracted. The possible match will be the one with the
                % smallest gap to zero
                
            circle_factor = 10;  % gain for the circle match
            if size(possible_object_names,1) > 1
                for possible_matches_secound_search_counter = 1:size(possible_object_names,1)
                    compare_object = teach_list(cell2mat(possible_object_names(possible_matches_secound_search_counter,2)));
                    
                    tmp_object_circle_variance(possible_matches_secound_search_counter,1)= cell2mat(possible_object_names(possible_matches_secound_search_counter,2)); % cache for the object number
                    tmp_object_circle_variance(possible_matches_secound_search_counter,2)=  (abs(compare_object.circle - current_object.circle)*circle_factor)+ abs(compare_object.red - current_object.red) + abs(compare_object.green - current_object.green) + abs(compare_object.blue - current_object.blue); 
     
                end
                [MinValue,IndexOfMin] = min(tmp_object_circle_variance(:,2));
                object_list{object_list_card_counter}(object_list_counter).name = possible_object_names(IndexOfMin,1);
            end

Anschließend wird untersucht, welches der gefundenen Objekte auf beiden Karten vorhanden ist.

% find the same objects in the structs
for struct_object_counter_1 = 1:number_of_object_on_one_card
    for struct_object_counter_2 = 1:number_of_object_on_one_card
        
        if ismember(object_list{1}(struct_object_counter_1).name, object_list{2}(struct_object_counter_2).name)
            same_object_flag = true;
            object_number_struct_1 = struct_object_counter_1;
            object_number_struct_2 = struct_object_counter_2;
            
            break;
        end
    end
    
    if same_object_flag == true
        break;
    end
end

Abschließend werden der Objekt-Name sowie die Position der selben Objekte von der Funktion zurück gegeben.

Testumgebung: SameObjectSearchEngine.m

Um das Programm, zum Auffinden derselben Objekte des Dobble-Spiels, zu testen wurde eine Testumgebung in Form einer Matlab GUI erstellt und programmiert.(SameObjectSearchEngine.fig und SameObjectSearchEngine.m)

Testumgebungs GUI

Nach Betätigung des „NEW CARDS“ – Taster werden zwei zufällig ausgewählte Dobble-Karten, um einen zufälligen Winkel gedreht und anschließend auf einer zufälligen Position auf einem schwarzen Bild positioniert. Das neu erzeugte Bild wird anschließend an die Funktion „find_same_objects.m“ übergeben, um dieselben Objekte auf den beiden Dobble Karten zu finden. Die Funktion gibt den Name der beiden gleichen Objekte, sowie die deren X und Y Position zurück an die Testumgebung. Die Testumgebung gibt anschließend den Namen bei der Textbox „result“ aus und markiert die gefunden Objekte mit einem roten Kreis (siehe Abbildung oben).

Dokumentation

Youtube-Video https://www.youtube.com/watch?v=nNshUlWZYgc&feature=youtu.be

SVN Ordner http://svn.hshl.de/svn/DSB/trunk/User/SoSe2016/Dobble_Spiel

Fazit und Ausblick

Fazit

In diesen Projekt konnten wir gut das gelernte Wissen aus den Vorlesungen praktisch anwenden und vertiefen.

Der von uns programmierte Algorithmus findet in etwa 90% der Fälle die beiden selben Objekte auf den Dobble-Karten. Die Unterscheidung der grünen Objekte (Kaktus, Kleeblatt, Fragezeichen) wird durch diesem Algorithmus noch nicht optimal unterstützt und ist deshalb noch etwas Verbesserungswürdig.

Alles im allen konnten wir aber viel neues zur digitalen Signal- und Bildverarbeitung dazu lernen und unsere Kenntnisse für Matlab erweitern.

Ausblick

Der nächste Schritt wäre die Umsetzung und Erprobung mit Hilfe eines physikalischen Aufbaues mit einer Kamera und z.B. eines Raspberry PI, die das Dobble-Spiel in Echtzeit verarbeitet und das Ergebnis auf einem Monitor ausgibt.

möglicher physikalischer Aufbau

Die Echtzeit Erprobung konnte im Rahmen dieses Semesters leider noch nicht durchgeführt werden.

→ zurück zum Hauptartikel: DSB SoSe2016