Ideen für einen Algorithmus

[new Account()]

Steinigt mich nicht, aber eventuell wären neuronale Netze eine Notlösung, falls es so nicht hinhaut

 

[Schwachkopp]

Steinigt mich nicht wenn ich Unsinn rede aber ist das nicht wie mit Kanonen auf Spatzen schiessen (Mein Wissen über neuronale Netze ist relativ überschaubar...)?

 

[new Account()]

Inwiefern?
Ist ja nicht so als sei dein Problem sehr einfach mit herkömmlichen Algorithmen zu lösen ...

 

[Schwachkopp]

Ich stell's mir aufwändiger vor als mit konventionelle Ansätzen. Brauch ich nicht erstmal ne Menge Samples womit ich das Netzwerk füttere?

 

[new Account()]

Klar brauchst du die. Und, wenn du die per Hand erzeugen musst, könnte das ätzend werden. Deswegen Notlösung.
(Du hast hier keinen Spatzen)

 

[kuddlmuddl]

Ist ja nicht so als sei dein Problem sehr einfach mit herkömmlichen Algorithmen zu lösen ...

Genau das ist es aber - siehe meine Links. In 2D sind das keine 10 Zeilen Python schätze ich mal.

Da meine vorigen Links ja schon keiner angeklickt hat ist hier noch ein fertiger Algo der funktioniert:
https://en.wikipedia.org/wiki/Region_growing
Seed ist der Innenpunkt und Growing findet statt, falls keine Wand im Umkreis ist.

Geht beides sehr einfach auch in 3D.

 

[Schwachkopp]

Ich hatte sie angeklickt. ;D

 

[new Account()]

Also ich sehe nicht Wie man damit das Problem Der Öffnungen löst. Ich Hoffe, ich habe nix überlesen.

 

[ayngush]

Eine Blockchain würde helfen die Fehler zu minimieren, falls man keinen deterministischen Algo dafür findet

 

[SoDaTierchen]

Opening und Closing finde ich einen guten Ansatz. Du könntest zum Beispiel das Bild so lange Closen (Wände verbreitern), bis du kein Loch mehr hast. Anschließend per Opening die Außenwände wieder reduzieren. Alles, was jetzt entweder Wand oder Innen ist und im Ursprungsbild undefiniert war, ist jetzt innen, alles andere außen.

Ein derartiger Algorithmus wird dann fehlschlagen, wenn es eine "Beule" in das Interieur gibt, die kleiner ist, als die größte erkannte Öffnung. Diese würde dann überschrieben werden.

Ein besserer Ansatz, der dem gleich kommt, was wir Menschen im Kopf machen: Die Öffnungen im Kopf mit "Türen" versehen, dann kann man sehr leicht den Innenraum abtasten. Hier sollten die Öffnungen nur so abgetastet werden, dass möglichst wenige Fehler auftreten. Dafür muss man aber zum Beispiel wissen: Können Öffnungen in einer Ecke liegen? Falls ja, wie wird damit Umgegangen? Kann es Punkte geben, an denen die Wand verzweigt, also gibt es Innenwände? Falls nein, macht das den Algrithmus viel einfacher, da an einer Kurve keine Öffnung zu erwarten ist, auch wenn die Abstände wegen U-Form des Bauwerkes dies suggerieren.


Neuronale Netze sind hier kein gelungener Ansatz. Das ist zwar super, um die Implementierung von neuronalen Netzen zu testen, aber andererseits ist das Problem zu überschaubar, als dass das Sinn ergeben würde. Den Ansatz würde ich verwerfen.

Der Ansatz von striker erinnert mich etwas an Monkey-Sort. Man kann hier relativ gute Ergebnisse erzählen, ist der Zufall aber unglücklich gewählt, werden die Ergebnisse ziemlich schlecht^^ Das Problem ist aber greifbar, da würde ich mit deterministischen Algorithmen herangehen.

Nachtrag: eine Idee für das finden von Öffnungen: Man geht davon aus, die Mauer läuft immer gerade. Endet die Mauer, dann gibt es 2 Varianten: a) Kurve. Die Mauer macht keine Kurve (in 3D mehrere Kurven möglich) und wird dort fortgesetzt (in 3D verzweigt der Algorithmus). b) Öffnung. Hier wird jetzt geprüft, ob in Laufrichtung eine weitere Mauer auftaucht. Falls ja: Öffnung (!), also alle abgelaufenen freien Punkte als "Wand" markieren. Falls nein: kreisförmig nach anderen Mauer-Endstücken suchen, das nächste gefundene ist die zugehörige Wand und die Öffnung wird dann nach einer Regel als Wand markiert (eckige Öffnung, runde Öffnung, schräge Öffnung, muss nur vorher klar sein).
Für 3D wichtig: Jedes Mauerstück, was bereits behandelt wurde, sollte als solches markiert werden und bei einem zweiten Ansteuern sollte der Algorithus stoppen. Durch die Verzweigungen kommen sonst zu schnell Endlosschleifen zustande. Auch für 3D wichtig: Zu jeder Wand eine Normale bestimmen. Fortsetzungen auf einem Lot der Normalen sind keine Verzweigung sondern noch dieselbe Wand.

 

[new Account()]

Das Problem ist aber greifbar,

bisher nicht - es wurde bisher keine Lösung genannt, die ohne Einschränkung des Problembereichs (welche ja nicht vorhanden ist) funktionieren.

BTW neuronale Netze sind auch deterministisch

 

[SoDaTierchen]

Ich hab mal nen kleinen Nachtrag zum möglichen Erkennen der Öffnungen geschrieben. Ich kann das gerne morgen auch mal als Pseudocode formulieren, sollte aber auch so klar sein, wie das funktionieren soll.

Das Problem ist mehr als greifbar. Das ist ein typisches Problem, was Informatik-Studenten im 3. bis 4. Semester des Bachelor-Studiums lösen. Es gibt krasse Sonderfälle, für die das nicht mehr greift, aber generell ist das Problem lösbar.

Betrachtest du die Vorgänge im neuronalen Netz als ganzes, dann funktioniert das deterministisch, betrachtest du den Lernvorgang aber als Blackbox und die aktuell gelernten Parameter sind dir nicht bekannt, dann sind neuronale Netze aus Anwendersicht nicht-deterministisch, da dieselbe Eingabe andere Ausgaben produzieren kann, abhängig vom (derzeit nicht bekannten) Lernzustand des Netzwerkes. Außerdem ist das Problem algorithmisch lösbar, dafür extra ein Netz anzutrainieren ist unverhältnismäßig, sofern es nicht um da Netz als solches geht.

 

[new Account()]

Es gibt krasse Sonderfälle, für die das nicht mehr greift, aber generell ist das Problem lösbar.

Du widersprichst dich im selben Satz.

Ich wollte das Thema nur mal angebracht haben - als Lösungsmöglichkeit, falls die nicht-gelernten Algorithmen nicht ausreichen. Ob das der Fall ist, darf immer noch der TE entscheiden, OK? Es ist nur sinnvoll alle Varianten in Betracht zu ziehen.

da dieselbe Eingabe andere Ausgaben produzieren kann

auch wenn man den (als undeterministisch angesehenen) Lernvorgang stoppt, ist die Ausgabe des Netzes nach dem Stoppen weiterhin deterministisch. Die Parameter bleiben die selben (egal welchen Wert sie haben), daher kann gar nichts anderes rauskommen bei gleicher Eingabe.

 

[SoDaTierchen]

Naja ... Wenn man jetzt den Kontext rauslässt (immer ne Top Idee!), dann widerspreche ich mir tatsächlich, denn aus wissenschaftlicher Sicht sind Ausnahmen nicht erlaubt und das Problem ist von dem von mir vorgeschlagenen Algorithmus nicht lösbar. Berücksichtigt man jetzt, dass der TE eine annähernd korrekte Lösung wollte, dann sieht das ganz anders aus. Aber warum sollte man sich auch am TE orientieren, wenn man am Thema auch völlig vorbei die Wissenschaftskeule schwingen kann.

Wie sinnvoll neuronale Netze sind hängt eigentlich immer davon ab, wie man sinnvoll definiert. Und das tut jeder anders. Du hältst es für eine sinnvolle Idee, ich nicht. Das liegt aber nicht an Fakten, sondern an unseren Auffassungen von sinnvoll. Damit liegt keiner von uns beiden falsch, aber es gibt eben auch nicht das eine Richtig.

Und Thema deterministisch: Genau das habe ich geschrieben. Ändert sich der Lernzustand nicht, dann sind die Ausgaben natürlich deterministisch. Aber, und jetzt schwinge ich mal die Wissenschaftskeule, ist der Lernzustand nicht bekannt, darf nicht über diesen geurteilt werden. Und da die Ausgabe vom Lernzustand abhängt, dieser aber nicht bestimmbar und vor allem nicht über Testläuft konstant ist, endet das Netz nichtdeterministisch.

So, unterm Strich will ich aber niemanden bashen, sondern dem TE helfen. Es wäre mir daher ganz lieb, wenn wir uns einigen könnten die Diskussion lieber zielorientiert denn wissenschaftlich zu führen. Und vom TE wünsche ich mir tatsächlich, diesbezüglich hier zu berichten, denn es ist schon spannend zu sehen, wie so ein Problem am Ende gelöst wird.

 

[new Account()]

vor allem nicht über Testläuft konstant ist, endet das Netz nichtdeterministisch.

letztendlich wird es irgendwann (beim Produktiveinsatz) fertig trainiert sein (wenn man sich denn nicht für kontinuierliches Weitertrainieren entscheidet). Danach ändert sich nichts mehr -> deterministisch. Egal, ob der Lernzustand (was sind die Parameter des Netzes?) bekannt ist oder nicht.
Du schreibst erst du hättest das gleiche wie ich geschrieben, sagst dann aber es wäre nicht deterministisch.

wie man sinnvoll definiert.

Dann definiere ich mal sinnvoll als "hilft dem TE bei seiner Lösungsfindung weiter" - um einen gemeinsamen Nenner herbeizuführen. (Auch, wenn ich der Meinung bin, dass Sinnhaftigkeit (bezogen auf Entscheidungen und nicht dem Sinn des Lebens) rational zu entscheiden ist.)
Neuronale Netze in Erwägung zu ziehen ist daher sinnvoll, weil es ihm eventuell hilft eine bessere Lösung für seine Problemstellung zu finden. Neuronale Netze nur auszuschließen, weil es neuronale Netze sind, ist hierbei nicht hilfreich.
Ob es letztendlich Sinn macht für den TE ("löst seine Problemstellung möglichst gut") eine spezifische Lösung zu benutzen, ist wieder eine andere Frage, und diese kann nur der TE beantworten, weil er sich mit seiner Problemstellung und dessen Umstände besser auskennt wie wir.

Ich klinke mich damit mal aus dieser Diskussion aus, dem TE hilft das hier nicht weiter, und es ist einfach OT.

 

[blöderidiot]

Ich glaube, ich habe eine einfache (jedenfalls konzeptionell) und allgemeingültige Lösung gefunden. Hast Du schon was programmiert und wozu nimmst Du das überhaupt? Ich frage das, weil ich erstmal eine Vorstellung von der Problemkomplexität (bzw. Simplizität) bekommen müßte.

Und nein, es wird kein neuronales Netz Das mag vielleicht irgendwann funktionieren -- aber man weiß dann nicht genau warum es funktioniert ...

 

[bog]

habe jetzt die antworten bloss ueberflogen, aber closing sah mir am intuitivsten aus. dazu koennte man bspw. einfach paare von oeffnungs-"raendern" (bloecke mit genau einem nachbar auf 2D) suchen, die am naechsten bei einander liegen, und diese distanzen dann minimieren, um "fehlende waende" einzusetzen. bei ungerader anzahl verwirft man dann einen uebrigbleibenden rand. einzelne punkte ignoriert man entweder, oder falls sie z.b. zwischen zwei luecken liegen geht man das ganze iterativ an und macht so lange bis keine luecke mehr bleibt. ob wir bei nem beliebigen pixel dann drinnen oder draussen liegen ginge z.b. per ray casting.

gibt dann sicher wieder pathologische faelle wo das nicht funktioniert, daher bin ich auf die loesung von @blöderidiot gespannt.

 

[blöderidiot]

meine Lösung wäre eine Clustersuche.

1. erzeuge einen 2D-Koordinatensatz von jedem schwarzen Punkt {x,y}[1..NP]
2. identifiziere alle direkt verbundenen schwarzen Punkte als Cluster (mit N(min)>3 oder so), alle Punkte liegen eindeutig in ihrem eigenen Cluster c[1..NC]
3. suche die minimalen kartesischen Abstände zwischen allen Clustern (durch Suche der Abstände der Punkte eines Clusters [ci] zu den Punkten der anderen Cluster[cj])
4. verbinde zwei Cluster miteinander an den entsprechenden Punkten nach sortiertem minimalen Abstand - bis es nur noch einen Cluster gibt (durch Erzeugung von einem oder zwei Punkten zwischen den Punkten mit dem geringsten Abstand).
5. Der letzte Cluster muss genau eine Öffnung haben (die größte, die es gab), diese wird ebenfalls geschlossen (finde die beiden Endpunkte und erzeuge adjazent die fehlenden Punkte. Der letzte Cluster ist ein "2D-Datensatz" von Koordinaten einer geschlossene Kurve von Punkten.
6. Jetzt kann vom Startpunkt angenommen werden, dass er "innen" liegt und ein normaler Flächenfüll-Methode zum gewünschten Resultat führt.

Könne mir jedenfalls vorstellen, dass das funktioniert ...

 

[new Account()]

Läuft glaube ich auf etwas ähnliches wie Opening&Closing raus - oder?

 

[blöderidiot]

etwas ähnliches wie Opening&Closing

Eigentlich nicht, da z. B. eine Punktdilatation eine implizite (Matrix/Kernel-) Operation auf der gesamten Ebene macht, während hier eine explizite bzw. gerichtete Suche (auf der gefragten Struktur) mit genau definierter Kontaktbedingung stattfindet. Das Verfahren wäre sozusagen "komplementär" zu opening/closing