Puzzle Hilfe, Puzzle Löser

Gast #4401645
Lesenswert?

Hat von euch schon mal jemand etwas in Richtung Puzzle Helfer,
Puzzle Löser entwickelt?

Als Puzzle verstehe ich die Puzzles, in der folgenden Art:

https://www.google.de/search?q=Puzzle&biw=1024&bih=574&site=webhp&source=lnms&tbm=isch&sa=X&ved=0ahUKEwiJnayI0vbJAhVHUhQKHcDdBlkQ_AUIBigB

Ich könnte mir mehrere Varianten vorstellen:
- Man legt alle Teile auf einen (weißen oder bestimmt farbigen)
Untergrund, macht ein (oder mehrere) Foto(s). Dann gibt man dem Programm
diese Fotos und es löst das Puzzle bzw. teilt dem Benutzer mit,
dies und das passt zusammen, oder zuerst kommt Teil 17, dann Teil 54 
usw.

- Oder man scannt/fotografiert die Lösung ein und scannt/fotografiert
dann 1 Puzzle-Teil und Programm gibt dann aus, dass das Teil z.B.
oben links in der Ecke, 5 cm vom Rand hin kommt.

Ich weiß, dass damit der Reiz des normalen Puzzelns verloren geht,
aber so ein automatisches Lösen (vielleicht auch nur, wenn man
gar nicht mehr weiterkommt) würde mich auch reizen.

Ich habe gerade schon mal etwas gegoogelt, aber schwer zu finden,
zumindest, wenn man nicht die richtigen Stichwörter hat.

Auf Youtube gibt es ein paar Videos, die mit OpenCV und Bilderkennung
zumindest in der Art was umgesetzt haben, was in meine Richtung geht.

http://www.cs.bgu.ac.il/~icvl/icvl_projects/automatic-jigsaw-puzzle-solving/

(Dies scheint etwas mehr zu helfen "automatic jigsaw puzzle solving",
aber scheint nicht ganz so einfach zu sein...)
Gast #4401657
Lesenswert?

Korrigierter Link (war übrigens von 2003):
http://www.heise.de/newsticker/meldung/Fraunhofer-Institut-soll-zerrissene-Stasi-Akten-rekonstruieren-79891.html

Aktuelle Infos zu dem Thema:
Anfang 2015
http://www.heise.de/newsticker/meldung/Virtuelle-Rekonstruktion-von-Stasi-Unterlagen-noch-im-Test-2507501.html

Zitat aus dem heise-Artikel von 2015:
"Laut Stasi-Unterlagen-Behörde war die Software für das gigantische 
Computer-Puzzle schon vor einem Jahr fertig. Sie kann Risskanten, 
Schrift- und Papierarten eindeutig zuordnen. Aus Schnipseln seien in dem 
Projekt mehr als 24.000 Blätter wiederhergestellt worden. Problematisch 
ist bislang, dass die Schnipsel sehr aufwendig in herkömmlichen Geräten 
eingescannt werden müssen."
Gast #4401681
Lesenswert?

Interessantes Problem...

Ich würde die Teile auch mit OpenCV verarbeiten. Nach dem Einscannen die 
Teile als Objekte identifizieren und dann mit einem Muster der einzelnen 
Teile erstmal in die "Standardrichtung" verdrehen/ausrichten. Das geht 
möglicherweise über Hu-Momente oder sowas in der Art.

Vorteil an den Puzzles ist ja, dass es nur ein paar verschiedene Formen 
gibt, die auch nur an bestimmten Kanten zusammenpassen.
Über eine geeignete Datenstruktur kann man damit eine Vorauswahl 
treffen.

Für die Farbinformation würde ich die Farbwerte entlang der potenziell 
aneinanderpassenden Kanten betrachten und ein Ähnlichkeitsmaß 
ausrechnen. Z.B. die Quadrate der Differenzen der Farbwerte entlang der 
Kante aufsummieren. Das Teil mit dem niedrigsten Wert müsste das 
gesuchte sein.
#7653855
Lesenswert?

Herr Maier schrieb:

Ich habe gerade schon mal etwas gegoogelt, aber schwer zu finden, zumindest, wenn man nicht die richtigen Stichwörter hat.

Man müsste mal schauen, wie weit man mit einer Mustererkennung-KI bei solchen Problemstellungen kommt.

So grundsätzliche Programmierung (also ohne KI) kann man mit Problemstellungen mit Schachfiguren auf einem Schachbrett versuchen. Gute Schachprogramme, das weiß man mittlerweile auch, profitieren von einer großen Datenbank.

Antwort schreiben

Bitte melde dich an, um einen Beitrag zu schreiben.

oder

Mit Google-Account einloggen

Die Registrierung ist kostenlos und dauert nur eine Minute.

Jetzt registrieren