Algorithmus gesucht um zusammenhängende Puzzlestücke zu finden



  • Ich habe hier viereckige Puzzles als Grafikdateien vorliegen.
    Nun suche ich eine Möglichkeit anhand der Informationen in den Rändern dieser Puzzleteile die einzelnen Teile richtig zu einem größeren Bild zusammenzufügen.

    Gibt es dafür brauchbare Algorithmen?



  • Für mich hört sich das erstmal nach einem Optimierungsproblem an, dessen zugehöriges Entscheidungsproblem NP-vollständig ist. Mit einem naiven Lösungsansatz wirst Du deshalb relativ schnell an die Grenzen der Rechenleistung Deines Computers stoßen.

    Das heißt aber nicht, dass Du deshalb gleich aufgeben solltest. Es gibt wahrscheinlich gute Ansätze, um den Zeitbedarf zur Lösung des Problems dennoch zu reduzieren. Vielleicht musst Du hierzu das Problem allerdings leicht umformulieren. Es könnte zum Beispiel Sinn ergeben, nicht das "beste" Puzzlestück zu suchen, das an ein anderes sehr gut passt, sondern nur eines, das sehr gut passt. Wenn Du dann bei Puzzlestücken anfängst, die sehr viel Struktur aufweisen, dann hast Du einen Ansatz, der es Dir ermöglicht, relativ gezielt nach einer Lösung zu suchen. Es wird auch Sinn machen, die Puzzlestücke anhand ihrer Struktur vorzusortieren.

    Aber generell kann ich Dir keine definitive Lösungsstrategie in Form von Quellcode oder ähnlichem liefern. Das ist eine Problemstellung, die vermutlich in der strengen Formulierung, die Du gewählt hast, nicht allgemein effizient lösbar ist. Wenn Du dafür einen sehr guten und sehr schneller Algorithmus hast, dann kannst Du damit vermutlich auch eine Menge Geld machen. Insgesamt erinnert mich das ganze ein bisschen an die DARPA Shredder Challenge. Im Prinzip ist das eine sehr ähnliche Problemstellung. Vielleicht findest Du in dem Zusammenhang einige interessante Lösungsansätze.

    EDIT: Die Entwicklung eines Algorithmus in diesem Zusammenhang sollte vermutlich mit der genauen Formulierung der zu optimierenden Funktion anfangen.

    EDIT2: Ich gehe von viereckigen Puzzleteilen aus, die keine besondere Form haben. Ist die Annahme richtig oder falsch?



  • Gregor schrieb:

    EDIT2: Ich gehe von viereckigen Puzzleteilen aus, die keine besondere Form haben. Ist die Annahme richtig oder falsch?

    Ja, im Prinzip ein Quadrat mit gleich langen Seiten.
    Danke für deinen Beitrag.



  • Kennst du das Zielbild?



  • Welche Anzahl von Puzzleteilen mit wievielen Pixeln? 😕

    Die Aufgabe ist knifflig, aber interessant. Jedes (hier quadratische) Puzzleteil muss mit den angrenzenden Puzzleteilen an den Rändern weitestgehend übereinstimmen. Man muss also eine Vielzahl von Puzzleteilen mit einer Vielzahl von Pixeln vergleichen. Eindeutig ist wohl nichts und jeder Algorithmus geht schnell in einen uferlosen Aufwand. Eine Vorsortierung nach Durchschnittswerten könnte den Aufwand reduzieren.

    Vielleicht bei der NSA nachfragen? Die machen möglicherweise schon etwas ähnliches oder haben Experten dafür. 😮



  • lkmmk schrieb:

    Kennst du das Zielbild?

    Nein, der Algorithmus sollte mit jedem Bild zurechtkommen ohne ein Zielbild dafür zu haben.

    Welche Anzahl von Puzzleteilen mit wievielen Pixeln?

    Auf die Idee bin ich gekommen, weil ich kürzlich im Internet ein Bild gesehen habe, bei welchem jemand die Gesichter dadurch unkenntlich gemacht hat, in dem der Bildteil, der die Gesichter abdeckt, in kleine Einzelbilder aufgeteilt wurde und diese Einzelbilder dann lediglich vertaucht, gedreht und verschoben wurden.

    D.h. meiner Meinung nach müssten noch alle Informationen vorhanden sein, um die Gesichter wieder vollständig kenntlich zu machen, man müsste die einzelnen Bildteile nur richtig anordnen und drehen.



  • Pro Teilbild dürften das so 4-9 Pixel sein.
    Also recht wenig um anhand von Rändern passende Nachbarteilbilder zu finden.

    Ich werde mal schauen ob ich das Bild wiederfinde.



  • Ich glaube ich habe das Bild gefunden, das hier könnte es gewesen sein:
    http://de.wikipedia.org/wiki/ESK_Mungo#mediaviewer/Datei:Mungo_gelaende.jpg



  • Puzzle schrieb:

    D.h. meiner Meinung nach müssten noch alle Informationen vorhanden sein, um die Gesichter wieder vollständig kenntlich zu machen, man müsste die einzelnen Bildteile nur richtig anordnen und drehen.

    Puzzle schrieb:

    Ich glaube ich habe das Bild gefunden, das hier könnte es gewesen sein:
    http://de.wikipedia.org/wiki/ESK_Mungo#mediaviewer/Datei:Mungo_gelaende.jpg

    Falls sich die Aussage auf das Bild da bezieht: Ich glaube, mit Deiner Annahme liegst Du falsch. Da ist nichts vertauscht und verdreht. Die Gesichter wurden einfach nur "grobgepixelt".


Log in to reply