Shredder Challenge

Gregor

Hi.

Die DARPA hat momentan einen kleinen Wettbewerb bezüglich der Rekonstruktion geschredderter Dokumente:

http://www.shredderchallenge.com

Da sind die Testdatensätze:

http://www.shredderchallenge.com/Download.aspx

Das hört sich nach einer ganz interessanten Herausforderung an.

...wollte Euch nur mal darauf aufmerksam machen.

Manuelles Lösen ist auch erlaubt.

Ich lade ein wenig pr0n hoch und lasse die Besucher das lösen, analog zu captchas. Die Horde an notgeilen Leuten schlägt jeden Supercomputer

Spass beiseite: Interessante Sache. Leider nichts für mich.

Interessant ...

Falls jemand Puzzle 5 runtergeladen hat, könnte derjenige dann einen kleine Ausschnitt des Bildes irgendwo hochladen damit ich einen Eindruck kriege?
Meine stark begrenzte Volumenflat ist leider fast dicht für diesen Monat

cooky451

Puzzle 5 besteht aus 20 einzelnen Dateien, jede Datei ist 50 MB und 4647x3609 Pixel groß. Also im Prinzip einfach 20 mal Puzzle 1.
Ich habe die erste Datei mal mit einem Viertel der Größe und als .png gepackt (jetzt ~1.5MB) hochgeladen: http://imageshack.us/photo/my-images/80/puzzle51of20400dpi.png/

Gregor

cooky451 schrieb:

Puzzle 5 besteht aus 20 einzelnen Dateien, jede Datei ist 50 MB und 4647x3609 Pixel groß. Also im Prinzip einfach 20 mal Puzzle 1.

...wenn man davon absieht dass die Puzzlestuecke auch erheblich kleiner sind.

otze

cooky451 schrieb:

Puzzle 5 besteht aus 20 einzelnen Dateien, jede Datei ist 50 MB und 4647x3609 Pixel groß. Also im Prinzip einfach 20 mal Puzzle 1.

Ne, die Nachrichten sind durcheinander gewürfelt. ich fürchte fast, dass du alle 20 Bilder gleichzeitig brauchst, um das Rätsel zu lösen.(wahrscheinlich wäre alles als großes Bild zu anstrengend für die üblichen Bildbetrachter )

@cooky451
Danke!

Für Puzzle-1 habe ich die Schnipsel isoliert (programmiertechnisch, ist klar, ne) und in separaten Dateien gespeichert. Der Hintergrund jeweils Schwarz.

Ich denke ich habe ne gute Idee wie es weiter gehen könnte, aber kaum noch Zeit, weil ich morgen früh wegfahren und noch packen muss

Also so:
http://imageshack.us/photo/my-images/198/69766421.png/

Das wäre der vierte oben links bei Puzzle 1.
Ich denke damit kommt man weiter ...

cooky451

@Gregor, otze
Ist ja schon gut, das bezog sich nur auf die Dateigröße.

Sieht mir ja irgendwie nach einer CSI Serie aus.

Ich war drauf und dran die Sache ernsthaft anzugehen und habe auch eine Idee, die zumindest für Puzzle 1 funktionieren könnte, aber ...

http://www.shredderchallenge.com/FAQ.aspx schrieb:

however, due to rules governing awarding prize money, a winning submission must be uploaded by a permanent resident or citizen of the United States.

.-.      
          | |      
          | |      
          | |      
         _| |_     
        | | | |-.  
       /|     ` |  
      | |       |  
      |         |  
      \         /  
       |       |   
       |       |

Gregor

µ schrieb:

Ich war drauf und dran die Sache ernsthaft anzugehen und habe auch eine Idee, die zumindest für Puzzle 1 funktionieren könnte, aber ...

http://www.shredderchallenge.com/FAQ.aspx schrieb:

however, due to rules governing awarding prize money, a winning submission must be uploaded by a permanent resident or citizen of the United States.

Oh ja, danke, dass Du darauf hinweist. Das ist natürlich bitter.

...andererseits: Die Problemstellung ist da und jetzt, wo es nicht mehr um einen Wettbewerb geht, den einer von uns gewinnen könnte, können wir uns vielleicht etwas darüber austauschen, wie man an die Sache herangehen sollte. Vielleicht haben einige Leute hier ja einige ganz interessante Ideen.

Also ich würde mir das in etwa so denken (habe so etwas allerdings vorher noch nie gemacht):

1. Man separiert die die einzelnen Puzzlestücke.

2. Man muss die Form der Puzzlestücke bestimmen. Hierzu würde ich Fourierdeskriptoren nutzen, um eine schöne Konturlinie zu bekommen. Dann würde ich äquidistante Punkte auf diese Konturlinie setzen.

3. Es wird nicht ausreichen, alleine mit der Form zu arbeiten. Man braucht auch noch die Farbinformationen. Im Prinzip sollte der Gedanke sein, dass die Bildfunktion stetig ist. Sprünge in den Farben zwischen benachbarten Puzzlestücken, sollten also vermieden werden. Hierzu speichere ich neben den Punkten der Konturlinie einfach auch Farbinformationen zu diesen Punkten ab. Dazu wird man sicherlich etwas Mitteln müssen, um ein stabiles Verfahren zu bekommen.

So, was bis jetzt gemacht wurde, geht vermutlich ruck-zuck. Was jetzt kommt, wird vom Algorithmus her mehr Zeit benötigen.

4. Wir bewerten zu jedem Paar von Puzzlestücken wie günstig es ist, sie in einer bestimmten Orientierung in Nachbarschaft zu setzen. Dafür müssen wir also diverse Positionen und Drehungen bewerten. Sollte vermutlich auch noch recht schnell gehen, aber wir haben jetzt einen recht großen Parameterraum. Natürlich wird eine bestimmte Konstellation als sehr gut bewertet, wenn die Stücke so einfach gut zusammenpassen. Interessante Bereiche sollten hierbei besonders stark gewertet werden. (Schwarze Striche und so). Den Parameterraum kann man vermutlich deutlich verkleinern, wenn man gerade Linien auf Puzzlestücken oder auch die längliche Form der Puzzlestücke nutzt, um nur bestimmte Orientierungen zuzulassen.

So, jetzt haben wir also lokale Informationen, welches Puzzlestück wie gut mit einem anderen zusammenpasst. Was bleibt, ist ein Optimierungsproblem, bei dem wir die Nachbarschaftsbeziehungen über das gesamte Bild optimieren wollen.

5. Jetzt wird es sehr diffus. Ich stelle mir eine Art Relaxationsmodell vor. Die Puzzlestücke ziehen sich gegenseitig bezüglich optimaler Nachbarschaften an und werden iterativ immer ein Stückchen näher in die Richtung der besten Nachbarschaft verschoben. ...alle gleichzeitig. Das stelle ich mir so ähnlich vor, wie beim "Iterative Closest Point" Algorithmus. Ich weiß nicht, ob das funktioniert, aber es wäre mein erster Ansatz, an diese Sache heranzugehen. Wenn das nicht klappt, dann würde ich eine Form von Backtracking versuchen, die ich nicht bis zum Ende durchziehe, sondern eben bis eine halbwegs gute Lösung existiert. Dabei ist es allerdings wichtig, in der richtigen Reihenfolge vorzugehen. Vor allem sollte man Puzzlestücke mit signifikantem Inhalt bevorzugt angehen.

Vermutlich gibt es die größten Probleme bei Punkt 5. Und es ist recht wahrscheinlich, dass man da in Wirklichkeit ganz anders herangehen muss. Zum Beispiel denke ich mir, dass man bei so einem Problem sicherlich irgendwie sehr gut mit bedingten Wahrscheinlichkeiten arbeiten kann. Ich weiß nur nicht, wie man sie genau einsetzen würde.

So, was sind Eure Ideen?

Dann kann ich ja auch meine Idee verraten.

So habe ich die Schnipsel bisher extrahiert:
-RGB zu HSV Umrechnung.
-Hue-Kanal extrahieren und zurück zu RGB.
-Binarisieren mit fester Schranke.
-Ränder sind noch etwas unsauber. Mit Abstandsmessung zu einem Referenzwert im HSV-Raum alles Rote rausrechnen.
-Isolierte Schnipsel als separate Bilder speichern.

Als nächstes wollte ich:
-Die Linien auf dem Papier ausnutzen um die Orientierung der Schnipsel zu bestimmen und mit einer Drehung zu korrigieren. Dazu erstmal die Linien mit ein paar Filtern etwas stärker herausheben und dann eine Hough-Transformation durchführen um Geradengleichungen für die Linien zu extrahieren.

-Die gedrehten Schnipsel paarweise "matchen". Dazu alle Kombinationen wie die Linien zweier Schnipsel zueinander passen würden durchprobieren. Das sind nicht sehr viele. Für jedes Paar an Kandidaten würde ich dann die zueinander liegenden Ränder der Schnipsel parallel abwandern mit einem Turtle-Algorithmus. Ein Rand definiert die Nulllinie. Der andere Rand zählt bei jeder Abweichung einen Fehlerwert hoch. Der minimale Fehlerwert aller Paare und aller Paarkombinationen ist der wahrscheinlichste Match.

So kriegt man Streifen.

Die können nun nach dem gleichen Schema gematcht werden.

Farbinformationen könnte man in den Fehlerwert auch schön einrechnen.

Alternativ habe ich über eine Vektorisierung des Randes nachgedacht, wenn die Linien nicht ausreichen. Aber ... ach ich muss ins Bett

volkard

Standardvorgehensweisen interessieren nicht. Da haben die genug Vollbeschäftigte, die lesen können.
Andere Sachen, wie ob virtuelle Ameisen gerne die Buchtstabenpfade gehen würden.
Ach, auch kalter Kaffee.
Besser noch verrückter.
Darum geht es!

Was glaubt ihr eigentlich, was ein Programm, dass diese Aufgabe einigermasen schnell lösen kann wert ist? Ich denke, dass das ein paar hunderttausend Euro sind.

mehrere Millionen

Viel weniger.
Das sollte mit Standardmitteln lösbar sein.

Es geht um diese konkreten Puzzles, nicht um ein allgemeines Tool, das dazu in der Lage ist. Also darf man viele Werte experimentel bestimmen und fest reinbauen.

µ schrieb:

Viel weniger.
Das sollte mit Standardmitteln lösbar sein.

Es geht um diese konkreten Puzzles, nicht um ein allgemeines Tool, das dazu in der Lage ist. Also darf man viele Werte experimentel bestimmen und fest reinbauen.

Wenn es nur für diese paar Puzzles geht, ist es natürlich nicht viel Wert.