5.2.1 Historisches Beispiel

Erstmalig wurde ein Problem als CSP im Rahmen einer Teilaufgabe der automatischen Bilderkennung von Waltz (1972)^5.5 bzw. Waltz (1975) behandelt. Die Aufgabe bestand für David L. Waltz darin, den dreidimensionalen Aufbau einer Szene (Blocks World) anhand einer Linienzeichnung zu bestimmen, von dem lediglich die zweidimensionale Kantenstruktur bekannt ist. Da die Linien der Szene als Objektkanten entsprechend ,,markiert`` werden, wird dieses spezielle CSP auch Consistent Labeling Problem bzw. Scene Labeling Problem genannt. Um die einzelnen Objekte bestimmen zu können, müssen die Linien der Szene folgendermaßen klassifiziert werden:^5.6

• Konvexe Kanten sind gegeben, wenn die beiden angrenzenden Ebenen von dem Betrachter weggerichtet sind. Konvexe Kanten werden mit einem ,,+`` markiert.

• Konkave Kanten sind Kanten, deren angrenzenden Ebenen auf den Betrachter zustreben. Sie sind mit einem ,,-`` markiert.

• Verdeckende Kanten sind konvexe Kanten, von denen nur eine angrenzende Ebene sichtbar ist, weil sie die andere Ebene verdeckt. Diese Kanten werden durch Pfeilsymbole (,,$\leftarrow$``, ,,$\rightarrow$``) markiert, wobei sich, bezogen auf die Pfeilrichtung, die für den Betrachter sichtbare Ebene jeweils rechts von der Kante befindet.

Verdeckende Kanten werden auch ,,Außenkanten``, konvexe und konkave Kanten entsprechend ,,Innenkanten`` genannt. In Abbildung 5.1 ist ein Beispiel für eine Linienzeichnung (a) sowie das Ergebnis der Klassifikation (b) zu sehen.

Abbildung 5.1: Beispiel und mögliche Lösung eines Labeling Problems

Zur Abbildung des Problems auf ein CSP wird jede Kante als eine Variable repräsentiert. Die Domäne jeder Variable besteht in der Ausgangssituation aus einer endlichen Menge der möglichen Klassen {+, -, $\leftarrow$, $\rightarrow$}. Die Menge der Constraints ergibt sich aus einer Reihe von allgemeinen, geometrischen Regeln. So lässt sich, bezogen auf die Eckpunkte, eine Aussage über die Markierungen der zusammentreffenden Kanten treffen: Die Constraints schränken die Anzahl der möglichen Markierungen der Szene auf zulässige Kombinationen ein, so dass sich eine korrekte, dreidimensionale Interpretation ergibt.

Da in der Praxis die Anwendung eines Suchalgorithmus aufgrund der Komplexität nicht adäquat ist, entwickelte Waltz eine Alternative, den ,,Waltz-Filteralgorithmus``. Dieser Algorithmus nimmt eine lokale Auswertung der Constraints vor, indem inkompatible Belegungen aus den Domänen der Constraint-Variablen herausgefiltert werden. Die Einschränkungen der Wertebereiche werden in den benachbarten Constraints propagiert, ohne dabei eine Menge von allen möglichen Kombinationen der Markierungen zu erzeugen. Dadurch wird eine effiziente Verarbeitung des Consistent Labeling Problems gewährleistet. Eine übersichtliche Darstellung des Waltz-Filteralgorithmus findet sich z.B. in den Arbeiten von Meyer (1995, S. 15) und Güsgen (1989, S. 25 f.).^5.7

Fußnoten

...^5.5

Zit. nach Chmeiss und Jégou (1998, S. 124); Freuder (1978, S. 959); Güsgen (1989, S. 22); Güsgen (2000, S. 267); Lhomme (1993, S. 235); Mackworth (1977a, S. 105); Meyer (1995, S. 49); Van Hentenryck (1989, S. 45).

...^5.6

Das von Waltz (1975) beschriebene System ist zudem in der Lage, eine Reihe weiterer Kanten zu klassifizieren, z.B. zur Interpretation von Schatten.

...^5.7

Das Verfahren erzeugt einen Konsistenzgrad, der dem der Kantenkonsistenz entspricht. Der Waltz-Filteralgorithmus selbst ist äquivalent zum AC-2 Algorithmus (vgl. Abschnitt 5.2.3.3).