Next: Anhang Main: Jufo: simPuzzle-Dokumentation Previous: Konzeption


Realisierung

Da der Vergleich die zentrale Schnittstelle zwischen den Modulen Bildverarbeitung und Zusammensetzen darstellt, mußten wir die Methoden dazu als erstes entwickeln. Die Bildverarbeitung muß jene Informationen aus den Bildern extrahieren, welche für das gewählte Verfahren notwendig sind. Daher folgt zunächst eine Darstellung des Vergleichs, dann die daraufhinarbeitende Bildverarbeitung und schließlich der Algorithmus des Zusammenbauens.


Vergleich

Der Vergleich soll das manuelle Ausprobieren des Menschen simulieren. Dieser legt die Puzzleteilkanten auf- bzw. ineinander und prüft, ob dies durch Überlappungen unmöglich ist oder ob Lücken zwischen beiden Teilen bleiben. Ist das nicht der Fall, dann passen die Teile aneinander.

Bei den meisten Puzzles kommen die Ecken nebeneinanderliegender Puzzleteile bis auf einen kleinen Abstand aneinander heran. Wir wollen uns auf solche Puzzles beschränken. Andernfalls hat man nämlich die unangenehme Aufgabe, allgemeine Kurven in allgemeiner Lage zum Vergleich aneinanderlegen zu müssen. Wir glauben nicht, daß dies mit unseren Rechnern in annehmbarer Zeit zu bewältigen wäre. Daher legen wir die Ecken - soweit möglich - auf- oder nahe nebeneinander und vergleichen die Randkurven zwischen den Ecken.

Das setzt jedoch voraus, daß die Ecken mit hoher Genauigkeit ermittelbar sind, weil bereits eine leichte Verschiebung oder Drehung zu hohen Diskrepanzen zwischen den Kurven führen kann. Auch macht es keinen Sinn, zwei Puzzlekanten miteinander zu vergleichen, deren Ecken sehr unterschiedliche Abstände haben und somit unmöglich zur Deckung zu bringen wären.

Sinnvoll ist noch eine grobe Klassifikation der Puzzlekanten nach Geschlecht, weil auch der Mensch auf diese Weise viele Teile von der Suche ausschließen kann. Auf weitere Klassifikationen haben wir jedoch verzichtet, da z.B. die Bestimmung von Lage, Breite und Tiefe einer Einbuchtung oder ähnliche Beschreibungen der Form nur auf die speziellen, typischen Puzzleteile anzuwenden sind.

Lassen sich die Ecken zweier zu vergleichender Puzzlekanten nicht zur Deckung bringen oder haben beide dasselbe Geschlecht, so kann der Vergleich nur den Wert E = 0 (paßt nicht) zurückgeben. Andernfalls wird der genaue Kurvenvergleich durchgeführt.

Die nächste zu klärende Frage war, wie die Randkurven mathematisch erfaßt werden können. B-Splines schienen uns nach den Angaben aus der Literatur [2][7] besonders geeignet. Ihre Eigenschaften werde im nächsten Abschnitt erläutert, bevor dann mit ihnen konkret auf die Klassifikation nach Geschlecht und auf das Vergleichsverfahren eingegangen wird.

 

Mathematische Grundlagen: B-Splines

B-Splines der Ordnung k sind Kurven, deren Koordinatenfunktionen stückweise durch Polynome vom Grad k-1 definiert sind. Nach [7]:

 

displaymath444

 

wobei tex2html_wrap_inline446 die Ortsvektoren der n+1 Ecken des definierenden Polygons sind. Die Funktionen tex2html_wrap_inline450 sind die sogenannten Basis-Funktionen, die sich wie folgt rekursiv definieren lassen:

 

displaymath452

 

 

displaymath454

 

Dabei sind tex2html_wrap_inline456 die Knoten, die den Parameterbereich tex2html_wrap_inline458 unterteilen. Für sie muß gelten tex2html_wrap_inline460 . Man setze außerdem, falls notwendig, tex2html_wrap_inline462 .

Die Basisfunktionen tex2html_wrap_inline450 bestimmen an jeder Stelle t, in welchem Verhältnis die Ecken des Polygons zu einem Punkt auf der Kurve überblendet werden. Denn man kann zeigen, daß tex2html_wrap_inline468 an jeder Stelle t gilt.

Der Spline verändert seine Form nicht, wenn man auf die Polygonpunkte eine beliebige affine Transformation anwendet. Das ist insbesondere wichtig, wenn nachher die Randkurven zum Vergleich aufeinander gedreht und geschoben werden sollen.

Für feste Knoten tex2html_wrap_inline456 und den gegebenen Parameterbereich lassen sich die Koeffizienten der Koordinatenfunktionen in den verschiedenen Teilstücken berechnen, wenn man die Polygonecken nicht mehr verändert. Damit können Gleichungen, in denen die Koordinatenfunktionen oder ihre Ableitungen vorkommen, als Gleichungen der Form tex2html_wrap_inline472 mit Standardverfahren gelöst werden.

Ein Kompromiß zwischen guter Annäherung des Randes mit wenigen Polygonpunkten und dem Grad der Polynome liegt bei k=3. Die quadratischen Koordinatenfunktionen sind sowohl für die Klassifikation der Teile, als auch für den Vergleich der Kurven gut handhabbar.

 

Klassifikation nach Geschlecht

Die zu klassifizierende Puzzleteilkante wird so in ein kartesisches Koordinatensystem gedreht, daß die x-Achse die Verbindungsgerade zwischen den die Kante begrenzenden Ecken bildet. Die anderen Ecken sollen dabei im negativen y-Bereich liegen.

Zur Klassifikation werden nun die Entfernungen zu den am weitesten oberhalb und unterhalb der x-Achse liegenden Punkten der Randkurve tex2html_wrap_inline476 verwendet:

displaymath478

 

Da für einen B-Spline der Ordnung k=3 die Koordinatenfunktion tex2html_wrap_inline482 eine stückweise quadratische Funktion ist, ist die Bestimmung dieser Extrema von tex2html_wrap_inline482 kein größeres Problem. Nun zur genauen Klassifikation:

Im Fall tex2html_wrap_inline500 birgt diese Klassifikation Risiken, weil leichte Fehler der Bildverarbeitung dazu führen können, daß eigentlich passende Kanten das gleiche Geschlecht zugewiesen bekommen und dann nicht mehr miteinander verglichen werden. In diesem Fall wird eine entsprechende Warnung ausgegeben.

Ist die Klassifikation für alle vorgelegten Teile durchgeführt, so erfolgt eine erste Überprüfung der Vollständigkeit des Puzzles. Auch die Größe des Puzzles wird jetzt aus der Zahl der Rand- und Innenraumteile ermittelt.

 

Genauer Kurvenvergleich

Es gilt, ein Maß zu finden, das den Abstand zwischen den zwei Randkurven der aneinanderzulegenden Puzzlekanten an möglichst vielen Stellen berücksichtigt.

Eine Methode wäre, die von beiden Kurven bis zu den Ecken eingeschloßene Fläche zu bestimmen, da sie alle Überdeckungen der Teile bzw. Lücken zwischen ihnen repräsentiert. Da wir aber davon ausgehen müssen, daß\ die Bildverarbeitung nie ganz genau arbeiten kann, sollten kleine Abweichungen - auch über größere Abschnitte - weniger stark ins Gewicht fallen als große Differenzen. Dies läßt sich aus der Fläche nur unzureichend ablesen, die ohnehin nur schwer zu bestimmen ist.

Wir haben uns daher entschieden, jede Kurve nach der Bogenlänge mit z.B. 20 Punkten in gleichlange Abschnitte zu unterteilen. Beim Vergleich bestimmt man nun jeweils den Abstand dieser Punkte zur anderen Kurve. All diese Abstände können mit einer Wertungsfunktion versehen werden, die kleine Abweichungen eher vernachlässigt, und somit zu einem Wert E zwischen 0 und 1 zusammengezogen werden, der angibt, wie gut die Kurven B zueinander passen.

Die Unterteilung der Kurven nach der Bogenlänge muß\ nicht besonders exakt sein, es reicht, in den jeweiligen Teilstücken der Kurve zu interpolieren. Die Länge eines Kurventeilstückes im Parameterbereich tex2html_wrap_inline504 beträgt:

displaymath506

 

mit konstanten tex2html_wrap_inline508 , tex2html_wrap_inline510 und tex2html_wrap_inline512 , da die Ableitungen der Koordinatenfunktionen tex2html_wrap_inline514 und tex2html_wrap_inline516 linear sind. In [3] findet man das unbestimmte Integral (Abkürzungen: tex2html_wrap_inline518 , tex2html_wrap_inline520 , tex2html_wrap_inline522 ):

displaymath524

 

tex2html_wrap_inline526ist durch die Quadrierung von tex2html_wrap_inline514 und tex2html_wrap_inline516 sichergestellt, für tex2html_wrap_inline532 ergibt sich ein einfacheres Integral. Damit kann die Bogenlänge entlang der Kurve bestimmt werden, so daß eine Aufteilung in etwa gleiche Abschnitte kein Problem mehr darstellt. Aus Gründen der Rechengeschwindigkeit ist es sinnvoll, diese Aufteilung nur einmal vorzunehmen und die erhaltenen Punkte abzuspeichern.

Die Bestimmung des (minimalen) Abstandes eines Punktes tex2html_wrap_inline534 zu einem B-Spline läuft auf die Minimierung des folgenden Ausdrucks hinaus:

displaymath536

 

Die notwendige Bedingung tex2html_wrap_inline538 für ein Extremum ist eine kubische Gleichung, die mit Standardverfahren gelöst werden kann.

Die Formel, mit der die so berechneten n Abstände tex2html_wrap_inline542 zum Gesamtergebnis E des Vergleichs zusammengezogen werden, sieht folgendermaßen aus:

displaymath546

Die Werte r und G sind empirisch zu ermitteln.


Bildverarbeitung

Die Bildverarbeitung muß alle für Klassifikation und Vergleich notwendigen Informationen aus den gescannten Bildern extrahieren, was folgende Teilprobleme aufwirft:

Im folgenden werden diese Teilprobleme erörtert.

 

Trennen der Puzzleteile vom Hintergrund

Für den Hintergrund hatten wir zwei Varianten vorgesehen:

Der Hintergrund sollte so gewählt werden, daß man für eine beliebige Stelle im gescannten Bild feststellen kann, ob dort Hintergrund oder ein Puzzleteil zu sehen ist.

 

Homogener Hintergrund

Am einfachsten zu bewerkstelligen ist ein einfarbiger, homogener Hintergrund. Man geht dann davon aus, daß ein im gewählten Ton gefärbter Bereich im Bild Hintergrund darstellt. Das führt spätestens dann zu Fehlern, wenn auf den Puzzleteilen dieser Farbton auch zu finden ist. Das ist bei größeren Puzzles aber durchaus wahrscheinlich.

Problematisch bei dieser Variante sind außerdem die unvermeidbaren Fehler, die der Scanner liefert. Da dieser die aufgelegten Teile nicht exakt senkrecht abtastet, kommt es zur Ausbildung von Schatten. Um auch schattige Bereiche noch als Hintergrund zu identifizieren, kann man den zu tolerierenden Farbbereich nur sehr unscharf eingrenzen.

 

Muster im Hintergrund

Zur Anwendung kommt bei uns ein Hintergrundraster aus Linien mit einem Abstand von 8 Pixeln bei 400 dpi (circa 0,5 mm). Durch Analyse der Helligkeitsverläufe in Bereichen, die sicher nur das Hintergrundraster zeigen, kann man den Verlauf der Linien ermitteln und auf andere Bereiche extrapolieren. Zur Identifikation von Hintergrund sucht man nach an einem charakteristischen Quadrat aus schwarzen Linien an den so ermittelten Koordinaten.

Daß in einem Puzzleteil genau dasselbe Raster in der richtigen Lage auftritt, kann mit großer Wahrscheinlichkeit ausgeschlossen werden. Auch die Schatten stellen kein allzu großes Problem dar, da der Kontrast zwischen Linien und Zwischenraum auch im Schatten noch hinreichend groß ist.

 

Grobe Randerkennung und Vereinzelung

In einem großen Bild mit mehreren Puzzleteilen setzt man nun irgendwo am Rand des Bildes an und geht das Raster entlang, bis man auf ein Teil trifft. Den Rand dieses Puzzleteiles ermittelt man mit folgendem Algorithmus, den man solange wiederholt, bis man am Ausgangspunkt angelangt ist (Siehe Bild 3.2.2a):

Hat man so ein Teil im Uhrzeigersinn umrundet, kann man es aus dem großen Bild ausschneiden und einzeln abspeichern, damit es besser zu handhaben ist. Die Vereinzelung aufgrund des groben Rasters reicht aus, wenn man die Teile beim Scannen nicht allzu dicht aneinanderlegt.

Man hat aber mit dem Raster im Hintergrund auch die Möglichkeit, innerhalb der so abgetrennten Blöcke nach Hintergrund zu suchen. Liegen zwei Teile so aneinander, daß das Verfahren um beide herumläuft, so kann man den Fehler bemerken, wenn man im Inneren des vermeintlichen Teils noch Hintergrund findet.

Verfeinerung der Randerkennung

Ausgehend von dem groben, in der Auflösung des Rasters vorliegenden Rand eines Puzzleteils kann man einzelne Linien verfolgen, bis sie auf das Teil treffen. Mit dieser Methode erhält man genaue Stützpunkte auf dem Rand (Siehe Bild oben).

Man erhält so eine Menge tex2html_wrap_inline554 von N Stützpunkten auf dem Rand, die sinnvollerweise so geordnet sind, daß man das Teil auf ihnen umrundet, ohne immer wieder vor- und zurückzuspringen. In der weiteren Argumentation ist für Punkte tex2html_wrap_inline558 mit i>=N die Festlegung tex2html_wrap_inline562 sinnvoll.

Ermittlung der Ecken eines Teils

Da die Ermittlung der Ecken die Qualität des späteren Vergleichs wesentlich bestimmt, nahm die Verbesserung dieses Verfahrens einige Zeit in Anspruch. Es existierten drei Lösungsansätze, die alle auf den Stützpunkten der vorherigen Randerkennung aufbauen.

 

Ausgleichsgeraden

Durch je n aufeinanderfolgende Stützpunkte tex2html_wrap_inline564 lege man nach der Methode der kleinsten Fehlerquadrate Ausgleichsgeraden tex2html_wrap_inline566 der Form

displaymath568

und bestimme jeweils den Winkel, den tex2html_wrap_inline566 und tex2html_wrap_inline572 um das Puzzleteil einschließen. Liegt dieser Winkel in der Gegend von 90 Grad, so ist man vermutlich an einer Ecke. Andernfalls macht die Randkurve einen Bogen.

Probleme hatte das Verfahren an den scharfen Bogen an weiblichen Puzzlekanten. Die Ausgleichsgeraden kamen unter Umständen so zu liegen, daß sie ähnlich aussahen wie eine Ecke, da sie die Stützpunkte nur schlecht approximerten. Auch eine Berücksichtigung der Korrelation brachte keine brauchbaren Aussagen. Es wurden entweder nicht alle Ecken erkannt, oder aber sehr viele Stellen irrtümlich für Ecken gehalten.

 

Krümmung von B-Splines

Der Ansatz sah vor, die Randkurve durch n aufeinanderfolgende Stützpunkte durch einen B-Spline tex2html_wrap_inline574 zu approximieren, dessen Krümmung

displaymath576

man bestimmen kann [3]. An Ecken sollte ein Maximum der Krümmung auftreten, das es zu bestimmen gilt. Damit aber die Krümmung eines B-Splines auch an den Knotenpunkten stetig ist, muß er mindestens von der Ordnung k=4 sein. Die Bedingung tex2html_wrap_inline580 führt dann aber auf Gleichungen 6. Grades, was im folgenden Ansatz vermieden wird.

 

Ausgleichsparabeln

Durch je n aufeinanderfolgende Stützpunkte tex2html_wrap_inline564 lege man nach der Methode der kleinsten Fehlerquadrate Ausgleichskurven tex2html_wrap_inline584 der Form

 

displaymath586

 

und bestimme jeweils die Stellen, an der die Krümmung tex2html_wrap_inline588 dieser Kurve maximal wird. Dazu ist die Gleichung tex2html_wrap_inline580 zu lösen, was nach elementaren Umformungen auf folgendes führt:

displaymath592

 

Liegt die so ermittelte Stelle in dem Parameterbereich, in dem die Stützpunkte liegen, und ist die Krümmung hinreichend groß, so kann man an in der Umgebung des entsprechenden Punktes auf der Kurve eine Ecke vermuten. Da die Ausgleichsparabel sich aber nie ganz in die Ecke hineinschmiegt, nimmt man doch besser den Schnittpunkt der Ausgleichsgeraden vom ersten Ansatz als Position der Ecke. Wenn auch der erste Ansatz ein schlechtes Kriterium für die Existenz einer Ecke ist, so beschreibt er doch die Position recht genau.

Falsche Ecken

Auch der letzte Ansatz liefert nicht nur die tatsächlichen Ecken, sondern zusätzlich einige irrtümlich als Ecken angesehene Stellen großer Krümmung, wie sie z.B. an den Einschnürungen der weiblichen Kanten zu beobachten sind.

Um die richtigen vier Ecken von den falschen zu trennen, wird jede 4-er Auswahl aller gefundenen Ecken überprüft. Liegen von diesen vieren zwei zu dicht aneinander, oder weichen die Winkel in dem durch sie gebildeten Viereck zu stark von jeweils 90 Grad ab, dann wird die Auswahl verworfen. Damit lassen sich die wirklichen Ecken gut ermitteln, wenn auch einige Beschränkungen für das Aussehen von Puzzleteilen in Kauf genommen werden müssen. Bei handelsüblichen Puzzles sind diese Beschränkungen aber meist erfüllt.

 

Darstellung der Randkurven als B-Splines

Die Randkurven zwischen den Ecken sollen jeweils als B-Splines dargestellt werden. Dazu benötigt man eine Methode zur Bestimmung der Polygonecken, so daß der B-Spline möglichst den Verlauf der Stützpunkte wiedergibt. Dabei soll sich der B-Spline nicht durch jeden Stützpunkt genau ``durchquälen'', es empfiehlt sich daher eine Ausgleichskurve.

In der Literatur fanden wir dazu Verfahren, die wir nur geringfügig an unsere Anforderungen anpassen mußten. Sie liefern eine sehr gute Darstellung des Randes. Die genaue Diskussion des Verfahrens kann aus Platzgründen hier nicht erfolgen, der interessierte Leser sei auf die entsprechende Fachliteratur [2][7] verwiesen.

Da die Ermittlung der B-Splines rechenintensiv ist, speichern wir das Ergebnis für jede Puzzlekante ab. Nach der Ermittlung der Polygonecken drehen wir diese - und damit den ganzen B-Spline - in eine normierte Lage (Siehe Klassifikation nach Geschlecht). Auch beim Vergleich braucht dann nur noch eine der Kurven entlang der x-Achse so verschoben zu werden, daß\ die Ecken jeweils möglichst dicht beieinander liegen. In dieser Lage werden auch die Koeffizienten der Koordinatenfunktionen berechnet und die Aufteilung der Kurve in gleichlange Abschnitte vorgenommen.


Zusammensetzen

Als Erweiterung der Schnittstelle zwischen den Modulen ist noch zu klären, wie bei einem Vergleich von mehreren Puzzlekanten eines Teils ein zusammenfassender Wert zustandekommt. Es erschien uns naheliegend, das Produkt aus den Werten für jede Puzzlekante zu bilden, was dann aussagt, wie gut das Teil an die schon liegenden in der Umgebung paßt. Wir können in Abhängigkeit von der Qualität des Puzzles (ausgefranste Ränder oder ähnliche Mängel) einen Wert q garantieren, den ein an einer Position richtiges Teil beim Vergleich mindestens zugewiesen bekommt.

 

Blockbildung

Die menschliche Methode, mehrere Blöcke parallel zu bearbeiten, ist wohl darauf zurückzuführen, daß ihm nach Farben und Mustern eine grobe Einteilung in Gruppen von Teilen möglich ist. Außerdem kann er dann immer dort weiterbauen, wo es gerade am einfachsten und eindeutigsten ist. Letzteres wäre auch für den Computer von Vorteil: Falls er an einer Stelle nicht so recht weiterkäme, kein passendes Teil finden würde, könnte er zunächst an einem anderen Block weiterbauen.

Die Verwaltung solcher Blöcke ist aber mit großem Aufwand verbunden. Man muß nämlich an mehreren Blöcken parallel arbeiten, ohne sich durch temporär falsch eingebaute Teile den richtigen Weg zu verbauen. Daher bauen wir das Puzzle von einem Punkt beginnend nach einem festen Schema bis zum Gesamtbild auf.

 

Das rekursive Verfahren

Es wird mit einem Eckteil begonnen. Dann wird eine Prozedur aufgerufen, die ein weiteres Puzzleteil legen soll. Bei jedem Aufruf werden jeweils jene Teile ermittelt, die mit mindestens dem Wert q (siehe oben) an die gerade bearbeitete Position passen. Das erste davon wird eingebaut, und die Prozedur ruft sich erneut für die nächste Position auf. Das wird solange fortgesetzt, bis das Puzzle fertiggestellt ist, oder aber an einer Position schon alle Teile mit einem Wert größer als q (soweit existent) ausprobiert wurden. In diesem Fall kehrt die Prozedur zu ihrem Aufrufer zurück, das dort zuletzt eingebaute Teil wird entfernt und durch das nächste aus der Liste ersetzt. Mit diesem wird dann ein neuer Versuch gestartet.

 

Reihenfolge

Bei der Erläuterung des rekursiven Verfahrens wurde noch nicht darauf eingegangen, welches die jeweils nächste Position ist, an der ein Teil angelegt werden soll. Man sollte ein Schema verfolgen, bei dem möglichst oft neue Teile an mindestens zwei Kanten zum bisherigen Aufbau passen müssen. Es ist sehr unwahrscheinlich, daß mehrere Teile an eine solche Position passen. Außerdem werden so falsch gesetzte Teile schnell entlarvt, da eine Kante des falschen Teils und eine Kante des bisherigen Aufbaus kaum zu einem existierenden Teil passen werden.

Wir haben die folgenden Verfahren geprüft: Einreihiges, zweireihiges, diagonales und spiralförmiges Verfahren.

Auf dem folgenden Bild ist das Einreihige und das Spiralförmige graphisch dargestellt.

Beim einreihigen Verfahren bleibt die erste Zeile zunächst ungeprüft, man verläßt sich immer nur auf eine Kante. Das zweireihige Verfahren prüft nach spätestens zwei weiteren Teilen jedes gelegte durch einen Vergleich mit zwei Kanten. Beim Diagonalverfahren bleiben die Teile am Anfang jeder Diagonalen bis zum Durchlauf mit der nächsten Diagonalen ungeprüft. Das spiralförmige Verfahren bietet den Vorteil, daß zunächst die nicht so zahlreichen Randteile die Möglichkeiten einschränken, und daher recht schnell eine sichere Basis für das weitere Puzzeln gebildet werden kann.

Wie der Mensch beginnen wir also mit dem Rand, auch wenn dieser von uns sofort durch Innenteile abgesichert wird.


chris
Sun Jun 22 11:48:53 MET DST 1997