Hallo Liebe Entwickler-Ecke!
Gleich vorweg das wird jetzt viel Text
Ich bastle seit einigen Jahren mit Lego-Mindstorms herum. Diesmal habe ich mir ein recht ambitioniertes Projekt vorgenommen. Einen Roboter-Arm der zeichnen kann.
In etwa so: (
KLICK) habe ich mir das vorgestellt. Das Lego-Teil ist gebaut und die Inverse-Kinematik ist bereits implementiert (also ich gebe dem Arm eine Positionsangabe und er bewegt den Stift an den Punkt den ich angegeben habe! Dabei kann ich aber auch eine Sammlung von Punkten übergeben und die Software interpoliert linear dazwischen um den Robo-Arm möglichst präzise zu bewegen!)
Was mir derzeit Kopfzerbrechen bereitet ist das Einlesen und Aufbereiten von Bildern , so wie es in dem Video gemacht wird.
Hiermal ein Überblick was ich bereits implementieren konnte!
Dabei habe ich derzeit eine Kantenerkennung mit dem
Canny-Algorithmus mehr oder weniger Implementiert.
- Konvertieren in Graustufenbild
- Weichzeichnen mit Gauss'schem Kernel
- Ableitung des Bildes in X und Y Richtung
- Kantenerkennung
- Winkelerkennung
- NonMaximumSupression-Algorithmus
- Hysterese
Am Ende der Kantendedektion habe ich 2 Arrays vorliegen. Einer speichert einen Boolean-Wert ob ein Pixel eine Kante ist oder nicht. Der andere einen Integer-Wert für die Richtung
Für das Nachfolgende würde ich eure Hilfe benötigen: (Ich hab mir natürlich zu jedem Thema Gedanken gemacht, die ich auch dazuschreiben werde!)
Problem 1: Zusammenhängende Kanten finden und als Linien abspeichern
Um einen möglichst guten Zeichenfluss für den Roboter zu gewährleisten ist es essentiell dass er ohne Absetzen möglichst lange Linien ziehen kann.
Meine Idee: Es müsste Theoretisch möglich sein ein beliebiges Pixel das als Kante erkannt wurde entlang des Winkels der gewonnen wurde zu vervolgen und immer zu Prüfen ob das folgende Pixel auch eine Kante ist. Somit könnte man zumindest ein paar Stücke von Kanten erkennen und zusammenfassen. Jedoch wird diese Methode bei Gabelungen scheitern weil die Richtungsangabe des Pixels eindeutig ist und somit garkeine Möglichkeit besteht herauszufinden ob sich gerade 2 Kanten schneiden. Damit kann es passieren dass das kürzere Stück verwendet wird obwohl die andere Seite der Gabelung eine viel längere zusammenhängende Kante ergeben hätte. Nimmt man das Problem mit der Gabelung aus, müsste man mit einer geeigneten Rekursion die längsten Kanten finden können. Sobald der eine Rekursionsbaum durchlaufen ist speichert man die Linie ab und geht zum nächsten Pixel dass noch nirgendwo zugeordnet wurde. usw.... Zum Schluss müssen alle Linien nochmal untersucht werden und Bereiche gleicher Richtung mit 2 Positionsangaben anstatt n-vieler angegeben werden.
Also z.B.
Gefundene Kante hat die Punkte: [0,0];[1,0];[2,0];[3,0];[3,1];[3,2];[3;3] dann könnte man das ja auch so schreiben: [0,0];[0,3];[3,3] ohne das Information verloren geht.
Frage: gibts da vielleicht schon einen Algorithmus der diese Aufgabe effizient löst? Oder hat jemand eine andere bessere Idee wie man das Problem angehen könnte?
Problem 2: Flächen erkennen
Nur die Umrisse zu zeichnen wäre ja langweilig
Leider bin ich noch nicht dahinter gekommen wie man zusammenhängende Flächen in einem Bild erkennt.
Meine Idee: Eine Herangehensweise könnte sein, Bereiche mit ungefähr gleichen Grauwerten zu untersuchen. Da habe ich aber leider garkeinen Plan wie das funktionieren könnte, oder ob meine Idee da überhaupt zum Ziel führen kann!
Frage:Gibts einen Algorithmus der das kann (Schlagwort würde genügen -- Meine Google-Suchen waren wohl sehr ineffizient), oder wie kann man sowas machen?
Problem 3: Vektorisieren
natürlich müssen die gefundenen Kanten und Flächen noch irgendwie für den Roboter "begreifbar" gemacht werden.
Meine Ideen: Für Kanten ist das ganze ja recht trivial, vorausgesetzt man konnte sie vorher als Linien abspeichern (Siehe Problem 1). Nicht mehr trivial wirds jedoch wenn man jetzt versucht die Flächen umzuwandeln. Aber ich denke da habe ich schon einen ganz guten Lösungansatz: Man nimmt einen Punkt aus der Fläche und sucht sich das näherste Pixel dass als Kante erkannt wurde, ließt die Richtung dieses Pixels aus undverwendet sie um das nächste Pixel aus der Fläche zu finden. Sobald die Kante "fertig" ist (wie auch immer man "fertig" letztendlich definiert) speichert man die so gewonnene Linie als Kante ab, so als ob man sie durch den Canny-Algorithmus gewonnen hätte. Und wiederholt den vorgang bis alle Pixel irgendwie verbaut wurden. Ich denke die in dem YouTube-Video gezeigte Software macht ähnliches. Zumindest verlaufen die Linien der Fläche verdächtig ähnlich wie die der Kanten.
Fraglich ist für mich nur wie man eine sinnvolle Ausstiegsbedingung formuliert, mit der man eine Linie als abgeschlossen betrachten kann und mit der nächsten anfängt.
Frage: Auch hier wären sachdienliche Hinweise zur Herangehensweise sehr nützlich!
Jeder der auch nur eine Idee hat wie man ein Teilproblem bewältigt seis jetzt Arbeitsweise des Algorithmus, Implementierung in C# oder einfach nur Verbresserungsvorschläge ist herzlich eingeladen mir seine Gedanken mitzuteilen.
Dennoch muss ich auch ein bisschen an euer Verständnis appellieren. Ich hab mir Programmieren usw. im Laufe der letzten 6 Jahre zwar recht solide aber dennoch "nur" selbst begebracht, es kann also sein dass ich bei dem einen oder anderen Fachterminus aussteige :p
mfg Namenlosnameless
