Next: Realisierung Main:
Jufo:
simPuzzle-Dokumentation Previous:
Einleitung
Der natürliche Ansatzpunkt unserer Überlegungen war die Frage ``Wie puzzelt der Mensch?''. Wir wollten versuchen, dem Computer dieselben Fähigkeiten zu vermitteln, die wir Menschen beim Puzzeln einsetzen. Dazu war zunächst eine Analyse des menschlichen Puzzelns vonnöten; die Umsetzung am Computer stellte erst den zweiten Schritt dar.
Der Mensch geht beim Puzzeln ohne Vorlage meist wie folgt vor:
Der Mensch verläßt sich bei der Suche nach einem passenden Teil auf verschiedene Kriterien:
Das Problem des Computers ist, daß er nicht ohne weiteres auf so leistungsfähige Bildverarbeitungverfahren zurückgreifen kann wie der Mensch. Das menschliche Gehirn ist in der Lage, in dem vom Auge erfaßten Bild Puzzleteile und Hintergrund klar voneinander zu trennen, Farben und Muster einander zuzuordnen und die Randkurven zu vergleichen. Dem Computer müssen erst ähnliche Methoden der Bildverarbeitung zur Verfügung gestellt werden, bevor man die im vorigen Abschnitt (Wie puzzelt der Mensch?) genannten Kriterien zum Puzzeln verwenden kann.
Wir mußten uns zunächst entscheiden, welcher Teil der Bildverarbeitung am wichtigsten ist. Die Erkennung von großflächig auftretenden Farben und andere auf dem Motiv des Puzzles aufbauende Untersuchungen konnten erst an zweiter Stelle stehen. Sie erlauben keine Simulation des menschlichen Ausprobierens, weshalb mit ihrer Hilfe lediglich eine ungefähre Einordnung der Teile in Gruppen möglich ist.
Dahingegen ist es jedoch zwingend notwendig, die Teile zunächst vom Hintergrund zu trennen und ihren Rand möglichst genau zu ermitteln. Durch eine Analyse der Randkurven kann man die Teile nach groben Kriterien wie beispielsweise dem Geschlecht klassifizieren und einen Vergleich zweier Randkurven als Methode des Ausprobierens ins Auge fassen.
Wir sind der Auffassung, daß auf dem Motiv aufbauende Untersuchungen bei handelsüblichen Puzzles für den Computer nicht unbedingt notwendig sind. Der Computer kann sehr viel schneller und häufiger als der Mensch ausprobieren und braucht daher weniger Kriterien zur groben Einordnung.
Der Schwerpunkt unserer Arbeit liegt daher auf den Methoden der Bildverarbeitung, speziell auf dem Trennen der Puzzleteile vom Hintergrund und der Analyse der Randkurven.
Als eine sinnvolle Aufteilung in Module mit klar definierten Schnittstellen erschien uns die folgende:
Das Zusammensetzen setzt die Bildverarbeitung voraus. Die Anzahl der Rand- und Innenteile muß bekannt sein, und eine Klassifikation nach Geschlecht soll eine Vorauswahl von Puzzleteilen ermöglichen. Diese Informationen werden von der Bildverarbeitung zur Verfügung gestellt.
Beim Zusammensetzen müssen wiederholt Teile auf ihre Paßgenauigkeit hin überprüft werden. Die dazu benötigte Funktion, die zwei Randkurven miteinander vergleicht, ist die zentrale Schnittstelle zwischen beiden Modulen. Sie prüft, wie gut die Kanten zweier Puzzleteile aneinander passen, und liefert als Ergebnis einen Wert E zwischen 0 (= paßt nicht) und 1 (paßt) zurück. Dabei bedient sich der Vergleich weiterer, detaillierter Informationen, die die Bildverarbeitung vorab ermittelt hat.
Da die Bildverarbeitung vor dem Zusammensetzen bereits abgeschlossen ist, können Probleme beim Zusammensetzen nicht durch Nachbesserungen in der Bildverarbeitung gelöst werden. Eine genaue Lokalisierung der Fehlerquellen ist dann ohnehin fast unmöglich.
Für die Puzzleteile mußte zunächst eine ausreichend genaue Methode der Bilderfassung gefunden werden. Des weiteren war die Entscheidung über Programmiersprache und Betriebssystem zu treffen.
Bei der Bilderfassung haben wir uns für einen Flachbettscanner entschieden, da dieser das verzerrungsfreie Erfassen mehrerer Teile gleichzeitig ermöglicht.
Die Wahl eines geeigneten Grafikformates war problematisch, da wir zunächst die Datenmengen der in hoher Auflösung eingescannten Bilder unterschätzten. Wir mußten feststellen, daß\ wir nicht ohne ein Grafikformat mit hoher Kompression auskommen würden. Nur JFIF (JFIF steht für JPEG (Joint Photographic Experts Group) File Interchange Format, einem Grafik-Dateiformat mit verlustbehafteter Kompression.) konnte dies bei unseren Bildern erreichen.
Da wir zunächst parallel auf einem Apple-Rechner und einem PC unter Linux entwickeln wollten, stand für uns die Portabilität an erster Stelle. ANSI-C schien uns hierfür die beste Lösung zu sein, da es auf allen Plattformen mit leistungsfähigen Compilern zur Verfügung steht.
Die Entscheidung für das Betriebssystem UNIX war dadurch bedingt, daß wir mit Linux gute Erfahrungen gemacht hatten und uns so die Option offenhalten konnten, unser Programm auch auf schnelleren Workstations laufen zu lassen.