Next: Anhang
Main: Jufo:
simPuzzle-Dokumentation Previous: Konzeption
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.
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.
B-Splines der Ordnung k sind Kurven, deren Koordinatenfunktionen stückweise durch Polynome vom Grad k-1 definiert sind. Nach [7]:
wobei 
die Ortsvektoren der n+1 Ecken des definierenden Polygons
sind. Die Funktionen 
sind die sogenannten Basis-Funktionen, die sich wie folgt rekursiv
definieren lassen:
Dabei sind 
die Knoten, die den Parameterbereich 
unterteilen. Für sie muß gelten 
. Man setze außerdem, falls notwendig, 
.
Die Basisfunktionen
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ß 
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
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 
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.
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
verwendet:
Da für einen B-Spline der Ordnung k=3 die
Koordinatenfunktion 
eine stückweise quadratische Funktion ist, ist die Bestimmung
dieser Extrema von
kein größeres Problem. Nun zur genauen Klassifikation:
und 
.Im Fall 
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.
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 
beträgt:
mit konstanten 
, 
und 
, da die Ableitungen der Koordinatenfunktionen 
und 
linear sind. In [3] findet
man das unbestimmte Integral (Abkürzungen: 
, 
, 
):
ist
durch die Quadrierung von
und
sichergestellt, für 
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 
zu einem B-Spline läuft auf die Minimierung des folgenden
Ausdrucks hinaus:
Die notwendige Bedingung 
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
zum Gesamtergebnis E des Vergleichs zusammengezogen werden,
sieht folgendermaßen aus:
Die Werte r und G sind empirisch zu ermitteln.
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.
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.
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.
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 
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 
mit i>=N die Festlegung 
sinnvoll.
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 
lege man nach der Methode der kleinsten Fehlerquadrate
Ausgleichsgeraden 
der Form
und bestimme jeweils den Winkel, den
und 
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 
zu approximieren, dessen Krümmung
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 
führt dann aber auf Gleichungen 6. Grades, was im folgenden
Ansatz vermieden wird.
Ausgleichsparabeln
Durch je n aufeinanderfolgende Stützpunkte
lege man nach der Methode der kleinsten Fehlerquadrate
Ausgleichskurven 
der Form
und bestimme jeweils die Stellen, an der die Krümmung
dieser Kurve maximal wird. Dazu ist die Gleichung
zu lösen, was nach elementaren Umformungen auf folgendes
führt:
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.
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.
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